Quantum Communication Complexity

The most active modern thread is distributed and networked quantum computing. When a single computation is split across two physically separated quantum processors joined by a scarce quantum link — the architecture of essentially every proposed modular quantum computer and of the emerging quantum internet — the number of qubits that must cross the link to complete a joint operation is exactly $Q(f)$ or $Q^*(f)$, and the teleportation/superdense accounting is what schedules entanglement distribution against gate teleportation. A second live area is streaming and sketching: one-way communication complexity lower-bounds the memory of a streaming algorithm, and the exponential one-way quantum advantage for Hidden Matching motivates the search for genuinely quantum streaming sketches, while classical Index lower bounds certify $\Omega(n)$ memory for exact problems. Communication arguments also remain the backbone of unconditional lower bounds elsewhere — VLSI area-time tradeoffs ($A\cdot T^2=\Omega(D(f)^2)$ from a cut of the chip), data-structure cell-probe bounds, and extended-formulation limits on linear programs. And the ideas feed directly upward into interactive proofs: the qubit cost of conveying a quantum witness or a verifier's challenge is a communication quantity, and the message-compression questions here are the small-scale ancestors of the message and entanglement accounting that culminated in the MIP\* = RE resolution. Open problems remain sharp: the log-rank conjecture (is $D(f)$ always polylog in the rank of $M_f$?) and the exact quantum-classical gap for total functions are both still unresolved.

Picture the whole computation as two labs joined by a single wire. Alice's lab may perform any local operation on her input $x$ and any private ancillas — a full simulation of the universe, if she likes — and it costs nothing. The meter runs only when a symbol travels down the wire. In the classical model those symbols are bits; in Yao's quantum model they are qubits carried by a clean quantum channel; in the Cleve–Buhrman model Alice and Bob additionally hold halves of an unlimited supply of EPR pairs, arranged before either input arrived, and those pairs are free. The first figure fixes exactly what is on the meter and what is not.

The reason quantum helps at all is that a qubit on the wire need not report one bit of $x$ or one bit of $y$; after interference it can report an answer that depends on all of them at once. The second figure is the field's signature result made quantitative: the Disjointness function, where Alice and Bob must decide whether their sets share any element. Classically this stubbornly costs a linear number of bits, but a quantum protocol that runs Grover's search across the wire drives the cost down to roughly $\sqrt{n}$, and no quantum protocol can do better. This single curve — a genuine quadratic gap with a matching lower bound — is the number the whole subject is organized around.

The complexity measures are all worst-case minima over protocols, and they nest. The deterministic cost is the number of bits an errorless protocol sends on the hardest input; it is the ceiling above every other measure. Reading it correctly means remembering that the minimum is over protocols and the maximum is over inputs.

where: $f:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}$ — the function to be computed; $P$ — a deterministic protocol that always outputs $f(x,y)$; $x,y$ — Alice's and Bob's private inputs. The best protocol is chosen first, then an adversary picks the worst input for it, so $D(f)$ is the guaranteed communication no matter what the inputs are. Allowing a small failure probability collapses many costs dramatically. The bounded-error randomized cost lets Alice and Bob toss coins (private or shared) and be wrong with probability at most $\varepsilon$, conventionally $1/3$; any constant $\varepsilon<1/2$ gives the same measure up to a constant factor by majority amplification.

where: $\varepsilon$ — allowed error, fixed to $1/3$ unless stated; $\mathrm{cost}(P)$ — worst-case bits exchanged; $\Pr$ — probability over the coins. The gap $D$ versus $R$ is already dramatic for Equality, which needs $n{+}1$ bits deterministically but only $O(\log n)$ with randomness. The quantum cost replaces bits on the wire with qubits. In Yao's model Alice and Bob start unentangled and alternate local unitaries with rounds in which an $m$-qubit register is physically handed across; the meter adds $m$ each round. In the Cleve–Buhrman model they additionally share unlimited EPR pairs at no charge, giving $Q^*_\varepsilon(f)\le Q_\varepsilon(f)$.

where: $P$ — a quantum protocol (local unitaries interleaved with qubit transmissions); $\text{out}$ — the measured output announced as $f$'s value; $Q^*_\varepsilon$ — the same measure with free pre-shared entanglement. Local unitaries and ancillas are free precisely because they never touch the wire; only the transmitted register is billed. The three quantum currencies — transmitted qubits, transmitted classical bits with shared entanglement, and shared entanglement itself — are locked together by two textbook protocols. Teleportation spends one EPR pair and two classical bits to move one qubit; superdense coding spends one EPR pair and one qubit to move two classical bits.

where: $\text{EPR}$ — a shared Bell pair $\tfrac{1}{\sqrt2}(\lvert00\rangle+\lvert11\rangle)$; $\text{cbit}$ — a transmitted classical bit; $\text{qubit}$ — a transmitted qubit. These fixed exchange rates mean $Q^*(f)$ and entanglement-assisted classical cost differ by at most a factor of $2$, so any super-constant separation is robust to which currency you count. Lower bounds start from the communication matrix. Arrange all of $f$'s values into the $2^n\times2^n$ matrix $M_f$; a deterministic protocol tiles $M_f$ into monochromatic combinatorial rectangles, and rank cannot exceed the number of one-rectangles, which bounds the number of leaves.

where: $M_f$ — the sign or 0/1 communication matrix with $(M_f)_{x,y}=f(x,y)$; $\mathrm{rank}$ — rank over the reals. The log-rank conjecture asserts the lower bound is nearly tight, $D(f)=\mathrm{polylog}\,\mathrm{rank}(M_f)$; the quantum cost is bounded below by $\log$ of the approximate rank and the $\gamma_2$ norm, the spectral relaxations that survive entanglement. The flagship upper bound turns Grover's quadratic search speedup into a communication speedup. Because deciding Disjointness is deciding whether the AND function $g(i)=x_i\wedge y_i$ has a satisfying index, distributed Grover finds a witness in $O(\sqrt n)$ queries, each query costing one round-trip of a $\lceil\log n\rceil$-qubit index register.

where: $\mathrm{DISJ}_n$ — Disjointness, $f(x,y)=1$ iff $\sum_i x_iy_i=0$; the $\log n$ factor — the size of the index register moved per query. The matching quantum lower bound $Q^*(\mathrm{DISJ}_n)=\Omega(\sqrt n)$ (Razborov) makes the gap exactly quadratic up to the logarithm, which later distributed-Grover refinements remove. Hardness that even entanglement cannot beat is certified by small discrepancy. The discrepancy of $M_f$ under a distribution $\mu$ measures how unbalanced any rectangle can be; a low-cost protocol forces some large, unbalanced rectangle to exist, so small global discrepancy forces large cost.

where: $\mathrm{disc}(M_f)=\max_{\mu}\max_{R}\big|\sum_{(x,y)\in R}(-1)^{f(x,y)}\mu(x,y)\big|$ over rectangles $R$; $\delta$ — the small discrepancy bound. The extra factor $\tfrac12$ relative to the classical discrepancy bound is the only price entanglement extracts, because discrepancy also lower-bounds the $\gamma_2^\infty$ / trace-norm quantity controlling $Q^*$. Finally, the ceiling on what any qubit can carry is the Holevo bound, which is why entanglement alone cannot signal and why one-way quantum lower bounds exist. The accessible classical information about an ensemble is at most its Holevo quantity, itself at most the number of transmitted qubits.

where: $\chi$ — Holevo information; $S(\rho)=-\mathrm{Tr}(\rho\log_2\rho)$ — von Neumann entropy; $m$ — qubits transmitted; $I(X{:}B)$ — mutual information Bob can extract about Alice's input $X$. Setting $m=0$ forces $\chi=0$: a party who receives nothing learns nothing, no matter how much entanglement was shared beforehand.

The entire landscape of separations and equivalences is organized by whether $f$ is a total function, a partial (promise) function, or a relation — and by whether communication is present at all.

1 · The Disjointness speedup by the numbers (fully worked)

Alice and Bob each hold a subset of $\{1,\dots,n\}$ with $n=1024$, encoded as $x,y\in\{0,1\}^{1024}$, and must decide whether the sets are disjoint. Compare the classical and quantum communication costs and identify every factor.

Step 1. Classically, Disjointness is complete for this kind of problem: $R_{1/3}(\mathrm{DISJ}_n)=\Theta(n)$, so at $n=1024$ any bounded-error classical protocol must exchange on the order of 1024 bits. This is the Kalyanasundaram–Schmidt / Razborov linear lower bound — no fingerprint or hashing trick helps, because a shared intersection can hide in any coordinate.

Step 2. Quantumly, reduce to search for a marked index of $g(i)=x_i\wedge y_i$. Grover uses $\lceil\tfrac{\pi}{4}\sqrt n\rceil$ queries; at $n=1024$ that is about $\tfrac{\pi}{4}\cdot32\approx 25$ iterations, rounded to $O(\sqrt n)=32$ for the scaling estimate.

Step 3. Each distributed query ships a $\lceil\log_2 1024\rceil=\mathbf{10}$-qubit index register from Alice to Bob and back, so the per-query communication is $O(\log n)=10$ qubits (times a constant for the round-trip and workspace).

Step 4. Multiply: $\sqrt n\cdot\log_2 n=32\times10=\mathbf{320}$ qubits, versus $1024$ bits classically — a better-than-3× saving at this modest size that widens without bound as $n$ grows, since $\sqrt n\log n / n=\log n/\sqrt n\to0$. Quantum ≈ 320 qubits vs classical ≈ 1024 bits; the $32$ is $\sqrt n$ (Grover) and the $10$ is $\log_2 n$ (the index register).

2 · Fingerprint size and error for Equality (fully worked)

Alice and Bob hold $n=1000$-bit strings and must test $x=y$ with error at most a few percent. How large is a classical fingerprint, and what is its collision probability?

Step 1. Deterministically this is hopeless-by-design: $D(\mathrm{EQ}_{1000})=1001$ bits, essentially sending all of $x$. The identity communication matrix has full rank $2^{1000}$, forcing a distinct leaf per input.

Step 2. Randomized, Alice picks a random prime $p\le n^2=10^6$ and sends $(p,\,x\bmod p)$. The message is about $2\log_2 n=2\log_2 1000\approx\mathbf{20}$ bits — a $50\times$ compression over $1000$.

Step 3. A false "equal" verdict needs $p\mid(x-y)$ with $x\ne y$. The difference has at most $\log_2(2^{1000})=1000$ prime factors, and there are $\pi(10^6)=78498$ primes below $10^6$, so the collision probability is at most $1000/78498\approx\mathbf{1.3\%}$ per run; two independent runs push it below $0.02\%$.

Step 4. The quantum fingerprint reaches the same $O(\log n)$ with no shared randomness: an $O(\log n)$-qubit state $\lvert h_x\rangle$ plus a SWAP test accepts equal inputs with probability $1$ and unequal ones (overlap $\le\tfrac12$) with probability $\le\tfrac58$. 20-bit classical fingerprint, ≤ 1.3% error per run; the quantum version matches $O(\log n)$ but does not beat it — as required for a total function.

3 · Why entanglement gives at most a factor of two (conceptual, with arithmetic)

A protocol uses $q$ transmitted qubits and unlimited shared entanglement. Bound its cost in the entanglement-assisted classical model, and explain why no exponential gap can open between the two.

Step 1. By superdense coding, each transmitted qubit backed by an EPR pair carries $2$ classical bits, so $q$ qubits can be simulated by $2q$ entanglement-assisted classical bits: $R^*(f)\le 2\,Q^*(f)$.

Step 2. Conversely, teleportation moves each qubit using $1$ EPR pair and $2$ classical bits, so $Q^*(f)\le R^*(f)$ (up to the free entanglement). Combining, $Q^*(f)\le R^*(f)\le 2\,Q^*(f)$.

Step 3. Hence the two entanglement-assisted currencies agree within a factor of $2$: any super-constant separation survives regardless of whether you count qubits or entanglement-assisted bits, which is why the field's separations are stated so robustly.

Quantum communication complexity has one clear intellectual parent: the same person defined the classical model that stripped computation down to communication, and then defined its quantum successor fourteen years later.

Texts. Kushilevitz and Nisan, Communication Complexity (the classical foundations: rank, rectangles, discrepancy, fooling sets) · Nielsen and Chuang, Quantum Computation and Quantum Information, §1.3, §2.3 (teleportation, superdense coding, Holevo) · Watrous, The Theory of Quantum Information (entropy and the Holevo bound) · Wilde, Quantum Information Theory (accessible information, superdense coding) · de Wolf, Quantum Computing: Lecture Notes, chapters on communication complexity.

Papers. Yao, "Some complexity questions related to distributive computing," STOC 1979 · Yao, "Quantum circuit complexity," FOCS 1993 · Cleve and Buhrman, "Substituting quantum entanglement for communication," Phys. Rev. A 1997 · Buhrman, Cleve, Wigderson, "Quantum vs.\ classical communication and computation," STOC 1998 · Buhrman, Cleve, Watrous, de Wolf, "Quantum fingerprinting," Phys. Rev. Lett. 2001 · Raz, "Exponential separation of quantum and classical communication complexity," STOC 1999 · Razborov, "Quantum communication complexity of symmetric predicates," 2003 · Bar-Yossef, Jayram, Kerenidis, "Exponential separation of quantum and classical one-way communication complexity," STOC 2004.

Provenance. The complexity measures $D,R,Q,Q^*$ and the rank/rectangle/discrepancy machinery follow Kushilevitz–Nisan and de Wolf. A verifier should recompute: (1) $M_{\mathrm{EQ}}$ is the identity, rank $2^n$, so $D(\mathrm{EQ}_n)=n+1$; (2) the fingerprint message is $\approx2\log_2 n\approx20$ bits at $n=1000$ with collision $\le 1000/\pi(10^6)=1000/78498\approx1.3\%$; (3) the SWAP test accepts overlap-$c$ states with probability $(1+c^2)/2$, so overlap $\le\tfrac12$ gives $\le\tfrac58$ (the base article's $7/8$ requires overlap $\approx0.87$ and is corrected here); (4) BCW cost $\sqrt n\log_2 n=320$ at $n=1024$ against $R=\Theta(n)=1024$; (5) the resource conversions $1\,\mathrm{EPR}+2\,\mathrm{cbit}=1\,\mathrm{qubit}$ and $1\,\mathrm{EPR}+1\,\mathrm{qubit}=2\,\mathrm{cbit}$, giving the factor-2 robustness $Q^*\le R^*\le 2Q^*$; (6) the no-signalling calculation $\rho_B^{(x)}=\mathrm{Tr}_A\rho_{AB}$ independent of $x$, so $\chi=0$. All named scalings ($\sqrt n$, $\log n$, factor $2$, $n+1$, $\Omega(\sqrt n)$) are standard textbook values; no constants are fabricated.

Prerequisites. Quantum Query Complexity · The Polynomial Method for Quantum Lower Bounds · The Complexity Class BQP. Leads to. Quantum Interactive Proofs (QIP) · MIP\* = RE · Quantum Merlin-Arthur (QMA).

Ask the tutor: Ask me to walk through the distributed-Grover Disjointness protocol qubit by qubit, or to show why the discrepancy bound survives free entanglement.