Round elimination in exact communication complexity

1.1 Promise equality

• For promise equality, the chromatic number characterizes overall classical communication complexity because any classical protocol can be reduced to one round without extra communication.The one-round complexity is ⌈log χ(G)⌉.Source: §1.1 · p. 3
• Unlike the classical case, the quantum chromatic-number hierarchy for promise equality is not redundant: one-round complexity is characterized by orthogonal rank, but more rounds can change complexity.A one-round quantum protocol corresponds to an orthonormal representation of the associated graph.Source: §1.1 · p. 3
• A family of promise equality problems has one-round quantum complexity at least cn but a two-round protocol using at most C log n qubits.The inputs are n-bit strings that are equal or differ in exactly n/4 coordinates, for n a positive multiple of 8.Source: §1.1 · p. 3

1.2 The list problem

• The list problem can be represented by a family of subsets: Bob receives a list, Alice an element in it, and Bob must identify that element.The paper also frames its graph-parameter results as strengthening the link between communication complexity and graph theory established by de Wolf.Source: §1.2 · p. 4, §1.3 · p. 6
• For some list problems, the four-round classical protocol of Naor, Orlitsky, and Shor is asymptotically optimal, with a lower bound of log log χ(GL) + (2 − ε) log ω(L).For some such instances, ω(L) = log χ(GL), and the communication complexity is at least (3 − ε) max{log log χ(GL), log ω(L)}.Source: §1.2 · p. 5
• For quantum list problems, the authors conjecture that a graph family's orthogonal rank is at least n^ω(1); if true, this would imply super-logarithmic one-round complexity despite a simple two-round protocol.The graph is associated with lists of maximal cardinality whose strings have Hamming distances from n/2 through n.Source: §1.2 · pp. 5–6

Graph theory

• The paper considers simple undirected graphs without loops or multiple edges and uses base-two logarithms unless specified otherwise.Source: §2 · p. 6
• The orthogonal rank ξ(G) is the minimum dimension of a complex orthonormal representation, assigning orthogonal vectors to adjacent vertices; the paper uses complex rather than real vectors.The preliminaries note ω(G) ≤ ξ(G).Source: §2 · p. 7
• A graph's chromatic number χ(G) is the minimum number of colors needed to assign different colors to adjacent vertices.The preliminaries also give χ(G)α(G) ≥ |V(G)|.Source: §2 · p. 7
• H(n,d) has n-bit strings as vertices, with adjacency exactly when two strings differ in d positions.Equivalently, using ±1 strings, adjacent vertices have inner product n − 2d.Source: §2 · p. 7

Orthogonality lemma

• A collection of pure quantum states is perfectly distinguishable by measurement exactly when the states are pairwise orthogonal.The Orthogonality Lemma gives an equivalent condition for distinguishing positive semidefinite matrices using a measurement.Source: §2 · p. 7

3.1 General properties of promise equality

• Classical promise equality complexity is attained in one round, and its one-round cost is ⌈log χ(G)⌉ for the associated graph G.Alice simulates the transcript under the assumption that Bob’s input equals hers; Bob checks it against his input.Source: §3.1 · pp. 7–8
• The one-round quantum communication complexity of promise equality is ⌈log ξ(G)⌉, where ξ(G) is the graph’s orthogonal rank.The correspondence follows because inputs paired by an edge must be encoded by orthogonal states.Source: §3.1 · p. 8

3.2 Proof of Theorem 1.2

• For EQ on n-bit inputs equal or differing in exactly n/4 positions (n a multiple of 8), the cited communication bounds are at least Ω(n) and at most 2⌈log n⌉+1 qubits.Source: §3.2 · p. 8, §3.2.1 · p. 9, §3.2.2 · p. 13

3.2.1 One-round quantum communication complexity of EQ-

• For every 0 < α < 1/2 with n and αn even, multi-round quantum protocols can be exponentially more efficient than one-round protocols.The one-round lower bound uses the Lovász theta number as a lower bound on complex orthogonal rank, then bounds it through Hamming-graph eigenvalues.Source: §3.2 · p. 9, §3.2.1 · pp. 9, 13

3.2.2 Two-round quantum communication

• The two-round protocol applies distributed Grover search to the XOR of the inputs, then sends a differing-bit index and Alice’s bit to Bob.A Grover query to the XOR is implemented by sequentially applying the inputs’ query unitaries; the total cost is 2⌈log n⌉+1 qubits.Source: §3.2.2 · p. 13
• For constants α < 1/2 independent of n, the protocol extends to solve EQ- in a constant number of rounds using an exact Grover-search variant.The more general exact version is described in Appendix C.Source: §3.2.2 · p. 13

3.3 Distances close to n/2

• When d = n/2 − ℓ, ℓ ≤ O(log n), and n and d are even, EQ- has one-round quantum communication complexity at most O(log n).Alice can send the first 2ℓ bits; if they match, the remaining inputs have length n′ = n − 2ℓ and are equal or differ in n′/2 positions.Source: §3.3 · p. 14

4.1 Classical communication complexity of the list problem

• For all k-element subsets of [N], a four-round classical protocol uses at most log log N + 2 log k + O(log log k) bits.The bound can also be written as log log χ(GL) + (2 − o(1)) log ω(L), with o(1) tending to zero as k grows.Source: §4.1 · p. 14
• A classical protocol induces a (k − 1)-cover-free family of transcript sets, because Bob must distinguish Alice’s different inputs in each k-element list.The proof associates each input x with transcripts consistent with x and Alice’s message sequence.Source: §4.1 · p. 15

4.2 Quantum communication complexity of the list problem

• The one-round quantum communication complexity of L-list is exactly ⌈log ξ(GL)⌉.Alice’s input states must be orthogonal for every pair of distinct elements in a list, and an orthogonal representation supplies a protocol.Source: §4.2 · pp. 15–16
• Multi-round quantum communication complexity is at least max{Ω(log log χ(GL)), log ω(L)}.The two terms follow from the chromatic-number lower bound and the need to distinguish among ω(L) possible inputs.Source: §4.2 · p. 16

4.3 Proof of Theorem 1.7

• For lists of strings at a fixed Hamming distance d, an input-dependent quantum state makes every pair in a list orthogonal, allowing Bob to identify Alice’s input.The construction uses ⌈log n⌉ + 1 qubits; K is the union of the maximal lists for distances n/2 through n.Source: §4.3 · p. 16

4.4 Entanglement-assisted and non-signaling communication complexity of the list problem

• For K-list, a two-round entanglement-assisted protocol has Bob send one bit and Alice reply with ⌈log n⌉ + 2 bits.The paper also describes the communication cost as ⌈log n⌉ + 3 classical bits using ⌈log n⌉ + 2 EPR pairs.Source: §4.4 · p. 17
• With non-signaling correlations, every list problem has an optimal one-round protocol using ⌈log ω(L)⌉ bits.Alice sends a shared random label, and Bob subtracts it from his correlated value to recover the label of Alice’s input.Source: §4.4 · p. 18

A Orthogonal rank is NP-hard

• For every fixed k ≥ 3, deciding whether ξ(G) ≤ k is NP-hard.The proof extends the k = 3 result using suspension, which adds a clique adjacent to all original vertices and increases orthogonal rank by its size.Source: A Orthogonal rank is NP-hard · pp. 21–22
• For k = 3, the reduction constructs G′ so that χ(G) ≤ 3 exactly when χ(G′) = 3, and χ(G′) = 3 exactly when ξ(G′) = 3.The graph adds a gadget H_ij for each pair of distinct vertices; its constraints force the corresponding represented subspaces to be equal or orthogonal.Source: A Orthogonal rank is NP-hard · pp. 21–22
• A three-dimensional orthogonal representation of G′ yields a three-coloring of G by assigning colors to the at most three distinct represented subspaces.For each original vertex i, the reduction associates the one-dimensional subspace spanned by its representation vector.Source: A Orthogonal rank is NP-hard · p. 22

B Kremer’s Theorem

• An ℓ-qubit quantum protocol for a function with arbitrary range can be converted into a one-round classical protocol using 2^O(ℓ) bits.The stated result applies to general protocols, not only exact ones.Source: B Kremer’s Theorem · pp. 22–23
• The proof represents the final state of an interactive quantum protocol as a sum indexed by communication transcripts, with factors depending separately on Alice’s and Bob’s inputs.This representation supports the one-round simulation and allows the theorem to handle protocols with different message lengths across rounds.Source: B Kremer’s Theorem · p. 23
• The proof approximates quantum-protocol amplitudes with finite-bit representations, then has Bob estimate each output’s acceptance probability.If the original protocol succeeds with probability 1, Bob selects the unique outcome whose estimate is strictly greater than 1/2.Source: B Kremer’s Theorem · p. 24

C Multi-round quantum protocols for EQ-

• For α < 1/2, the section gives a multi-round quantum protocol with a logarithmic number of qubits; the α = 1/4 case is handled by an earlier theorem.The protocol turns exact Grover search into communication by distributing query operations between Alice and Bob.Source: C Multi-round quantum protocols for EQ- · pp. 24–25
• For d = αn with α ∈ (1/4, 1/2), two-round quantum communication uses at most 2⌈log n⌉ + 2⌈log(4α)⌉ + 1 qubits.The inputs are padded with zeros so that the new strings have length 4d and differ in one quarter of their positions when unequal.Source: C Multi-round quantum protocols for EQ- · p. 25
• For d = αn with α ∈ (0, 1/4), the quantum communication complexity is at most O(log n) qubits.This construction uses technical adjustments to obtain an exact version of Grover’s search algorithm.Source: C Multi-round quantum protocols for EQ- · p. 25
• When the strings differ in exactly d positions, exact Grover search lets Alice find a differing index, after which she sends the index and her bit to Bob.The resulting protocol uses (ℓ + 2)⌈log n⌉ + 2 qubits in ℓ + 2 rounds when the search uses ℓ queries.Source: C Multi-round quantum protocols for EQ- · pp. 25–26

• The binary entropy function is H(p) = −p log p − (1−p) log(1−p) for p ∈ [0, 1].Source: D Bound on binary entropy function · p. 26
• For every p ∈ [0, 1], H(p) ≥ 1 − (1 − 2p)^2.Source: D Bound on binary entropy function · p. 26
• Equality in this entropy lower bound holds exactly at p ∈ {0, 1/2, 1}.Source: D Bound on binary entropy function · pp. 26–27
• A Taylor expansion around 1/2, together with the Mercator series for ln 2, establishes the bound.Source: D Bound on binary entropy function · pp. 26–27

• ξ(GK) ≤ 2H(1/4)n+1 ≈ 20.81n+1, via a polynomial construction yielding an orthonormal representation.Source: E Partial results on ξ(GK) · pp. 27–28
• The upper-bound construction multiplies even- and odd-distance vanishing polynomials; the resulting degree and monomial count control representation dimension.Source: E Partial results on ξ(GK) · pp. 27–28
• ξ(GK) ≥ Ω(n), using spherical-cap covering and a diameter bound on the resulting independent set.A cap contains only representation points corresponding to an independent set; Kleitman's theorem bounds its size.Source: E Partial results on ξ(GK) · p. 28
• ϑ′(GK) ≤ 2n, so this Lovász-theta variant does not yield a stronger lower bound on ξ(GK) than the presented linear bound.Source: E Partial results on ξ(GK) · pp. 28–29