Optimal and Verifiable Quantum Advantages in Communication Complexity

AI summary

Overview

Research area: Quantum communication complexity, with links to quantum query complexity, the Clifford hierarchy, and near-term quantum advantage experiments ("quantum information supremacy").

Technical level: Advanced. The paper assumes familiarity with communication-complexity models (one-way, two-way, simultaneous message passing), Fourier analysis of Boolean functions, and the Clifford hierarchy. The high-level results and the experimental motivation are accessible to an intermediate reader.

Scope (one sentence): The paper constructs total search problems that achieve the largest possible separation between quantum and classical communication, including versions whose solutions can be checked efficiently, and a tunable family of problems where the separation is provably optimal given the cost of preparing Alice's quantum message.

What This Paper Is About

A single quantum message of n qubits can, in the worst case, be simulated by roughly 2^n classical bits, so n versus Ω(2^n) is the ceiling for any quantum–classical communication separation. For decades, the best known separation for a total search problem — where every input pair admits some valid answer — was only n versus Ω(2^{n/2}) (Hidden Matching), and against two-way randomized communication only n versus Ω(2^{n/3}). The paper asks whether search problems can reach the ceiling, and whether they can do so with answers that a classical verifier can check efficiently. It answers both questions affirmatively and then studies how large a separation is possible when the quantum protocol itself is restricted to be cheap to implement.

Key Contributions

1. Pelagic Fourier Fishing (Theorem 1.1). A total search problem with an n-qubit quantum one-way protocol succeeding with probability at least 3/4 on every input, while every randomized two-way protocol succeeding with probability at least 2/3 on average over uniformly random inputs needs Ω(2^n) bits. This closes the gap left open for roughly two decades and answers a question of Aaronson, Buhrman, and Kretschmer.

2. Affine Pelagic Fourier Fishing (Theorem 1.2). A variant with efficiently verifiable solutions — checkable in poly(n) time using poly(n) input queries — that retains the n versus Ω(2^n) separation, this time against randomized one-way protocols. Bob's quantum computation is only a Clifford measurement, and Bob's input is exponentially shorter than Alice's.

3. The Directional Derivative Problem, DDP_{n,d} (Theorem 1.3). For every fixed d ≥ 2, a total search problem with efficiently verifiable solutions admitting an exact n-qubit one-way protocol, while every randomized one-way protocol succeeding with probability at least 2/3 on average requires Ω_d*(n^d*) bits. Alice's message is prepared with O_d*(n^d*/log n) gates — asymptotically matching the trivial bound that a G-gate circuit has an O(G log n)-bit classical description — and Bob performs a Clifford measurement.

4. Optimality within the Clifford hierarchy (Corollary 1.4). If Alice may send only an m-qubit state prepared by a single unitary from the k-th level of the Clifford hierarchy, then for every fixed 1 ≤ k ≤ d, any protocol succeeding with probability at least 2/3 over uniform inputs must satisfy m = Ω_{d,k}(n^{d/k}). The n-qubit, level-d protocol is therefore asymptotically optimal, and for k < d, n qubits never suffice for large n.

Main Findings

• The classical simulation bound is tight even for total search problems and even against two-way communication. Pelagic Fourier Fishing gives Ω(2^n) against randomized two-way protocols, whereas the previous best against two-way was Ω(2^{n/3}) (a partial function of Klartag and Regev) and the previous best for total search problems against one-way was Ω(2^{n/2}) (Hidden Matching, by Ben-Aroya, Jain, and Klartag-style attribution in the paper as [BJK08]).

• An improved query-complexity corollary. Via the standard communication-to-query reduction, Pelagic Fourier Fishing yields an optimal 1 versus Ω(N) separation between quantum and randomized query complexity for a total search problem, where N is the size of the oracle's truth table. This improves the previous 1 versus Ω(N/ log N) separation for Fourier Fishing due to Aaronson and Chen.

• The Pelagic condition is what removes a 1/n factor. Ordinary distributed Fourier Fishing has randomized two-way communication complexity Θ(2^n/n), short of optimal. Requiring the output coefficient's magnitude to sit "in the bulk" of the spectrum — at least 1/8 of the squared Fourier mass on coefficients of magnitude at most |ĥ(y)|, and at least 1/8 on coefficients of magnitude at least |ĥ(y)| — makes a large shift no longer intrinsically useful: a two-sided window can be chosen so that sup over b of the Gaussian probability of landing in the window is less than 2/3.

• The quantum protocol is simple and succeeds with probability at least 3/4 on every input. Alice sends the phase state encoding f; Bob applies the diagonal unitary |x⟩ ↦ g(x)|x⟩, applies H^{⊗n}, and measures, sampling y with probability |ĥ(y)|². Parseval's identity then guarantees the Pelagic condition holds with probability at least 3/4.

• Verification is achieved by a hidden partition. In Affine Pelagic Fourier Fishing, Bob receives a linear subspace V of logarithmic dimension; the affine cosets of V partition the input space into polynomially sized instances. Verification requires querying only the poly(n) coordinates in the chosen coset. Load-balancing results of Alon et al., sharpened by Jaber, Kumar, and Zuckerman, ensure that no coset can concentrate the information in Alice's message.

• An exact quantum protocol for the Directional Derivative Problem. Alice sends the degree-at-most-d phase state; Bob measures in the basis (|x⟩ + (−1)^b|x+a⟩)/√2, and any outcome (x,b) satisfies b = q(x) + q(x+a) = D_a q(x). The measurement is Clifford and uses at most n − 1 CNOT gates and one Hadamard gate. The matching classical protocol — Alice sends the Θ_d*(n^d*) coefficients — is essentially optimal.

• Quantum advantage without magic. At d = 2, Alice's message is an n-qubit stabilizer state and Bob's measurement is Clifford, yet the randomized classical one-way complexity is Ω(n²), giving a Θ(n²) separation. Since every n-qubit stabilizer state has an O(n²)-bit classical description, this is optimal within the restricted model, and it answers a question raised by Kalai and Aaronson on Shtetl-Optimized. The result contrasts with odd-prime-dimensional qudit stabilizer states and Clifford measurements, where the nonnegative discrete-Wigner representation rules out a superlinear advantage, and complements Karanjai, Wallman, and Bartlett's Ω(n²) memory lower bound for classical simulations of the qubit stabilizer subtheory.

• A gate-count optimality ceiling. Any n-qubit message preparable with G one- and two-qubit gates has an O(G log n)-bit classical description, so an n versus Ω(K) separation forces G = Ω(K/ log n). Theorem 1.3 saturates this.

• Experimental relevance. Kretschmer et al. demonstrated an unconditional quantum advantage on a trapped-ion device using 12 qubits against at least 62 classical bits, but their task is not efficiently verifiable; Hidden Matching is verifiable but its Ω(2^{n/2}) separation is too small at accessible instance sizes. The paper's Theorem 1.2 removes the asymptotic bottleneck, and the Directional Derivative Problem offers a tunable d to trade separation size against circuit complexity on noisy hardware.

Methodology in Plain English

The authors build three families of two-player games, each designed so that a short quantum message is provably far more useful than any classical message of comparable length.

The first game adapts Fourier Fishing. Alice holds a Boolean function f, Bob holds g, and Bob must output a large Fourier coefficient of the product fg. Alice's quantum message is a uniform superposition over all inputs with signs given by f, so Bob can "apply" g by a phase flip and then measure — sampling indices with probability equal to squared Fourier mass. The classical difficulty is that Alice does not know g, so her message cannot anticipate where the Fourier mass of fg will concentrate. The key twist ("pelagic") is that Bob must find a coefficient near the middle of the spectrum rather than a large one. Classical protocols can only shift the spectrum by revealing raw coordinates, and a two-sided window defeats this shifting strategy, forcing exponential communication.

The second game wraps the first in a hidden partition: Bob holds a small random subspace, whose cosets cut Alice's input into many tiny instances. Bob solves one instance and names the coset he used, so verification touches only polynomially many input bits. Combinatorial load-balancing theorems guarantee that Alice's message cannot be concentrated on whichever coset Bob happens to pick. This trick, however, creates an easy two-way protocol, which is why the lower bound here holds only against one-way communication.

The third game restricts Hidden Matching to algebraically structured inputs: Alice holds a low-degree polynomial and Bob holds a direction, and they must output the derivative along that direction at some point. The quantum protocol exploits the fact that the required measurement basis aligns exactly with the derivative's structure. For the lower bound, the authors show that predicting derivatives along many directions requires information about many linearly independent parities of the polynomial's coefficients, and each such independent parity costs classical bits — yielding the Ω_d*(n^d*) bound.

Why This Matters

Impact on research. The paper settles the question of how large a quantum–classical communication gap total search problems can achieve, showing the general O(2^n) simulation bound is tight against both one-way and two-way classical communication. It also introduces a new axis of study: how the separation scales with the cost and the "magic" level of the quantum protocol, connecting communication complexity to the Clifford hierarchy and to recent work linking magic to communication power.

Potential applications (as framed by the paper):

• Near-term quantum advantage demonstrations. The verifiable Affine Pelagic Fourier Fishing gives an unconditional, efficiently checkable task suitable for "quantum information supremacy" experiments, where one-way protocols are reinterpreted as state preparation followed by measurement on a single device.
• Hardware benchmarking. Reproducing an n-qubit versus M-bit separation requires preparing complex states at high fidelity, so a large demonstrated advantage is evidence of state-preparation quality.
• Tuning experiments to hardware. The d parameter in the Directional Derivative Problem lets experimenters pick the largest separation compatible with the circuits a given noisy device can implement reliably.
• Probing the size of classical state space. Any classical finite-state model reproducing the experiment needs at least 2^M distinguishable internal states, giving unconditional evidence for the effective exponentiality of Hilbert space.

Industry relevance. The work is directly relevant to quantum hardware groups designing advantage experiments on trapped-ion, superconducting, and neutral-atom platforms, and to groups interested in how far classically simulable ("magic-free") quantum computation can go.

Future Directions

• Finite-size and constant-factor optimization. The paper notes that asymptotic separation is only part of the story for near-term experiments, where constant factors and circuit complexity matter equally; identifying the most favorable concrete instances of these problems remains open.
• Implementations on additional platforms. The authors explicitly propose reproducing quantum information supremacy demonstrations on superconducting and neutral-atom devices and pushing to substantially larger separations than the reported 12 qubits versus 62 classical bits.
• Certifying the prepared state. A large advantage gives evidence of high-fidelity preparation, but formally certifying that the intended state was prepared would require a self-testing theorem, which the paper flags as missing.
• Extending the hierarchy-based limits. Whether the Clifford-hierarchy optimality (Corollary 1.4) can be strengthened, or matched by problems with additional structural properties, is left open; Appendix A is truncated in the provided content.

Target Audience

Quantum information researchers working in communication and query complexity; theoretical computer scientists interested in separations, total search problems, and relational problems; quantum algorithm and error-correction researchers interested in the Clifford hierarchy and magic; and experimentalists and hardware teams planning verifiable near-term quantum advantage demonstrations. Readers without a background in communication complexity will find the introduction and Section 1.2 accessible, but the theorems and proofs require graduate-level quantum complexity theory.

Authors’ abstract

We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an $n$-qubit quantum one-way protocol, whereas every randomized two-way protocol requires $Ω(2^n)$ bits of communication. We then introduce a variant of this problem whose solutions can be verified in polynomial time. This variant also admits an $n$-qubit quantum one-way protocol, while every randomized one-way protocol requires $Ω(2^n)$ bits of communication. We also construct a family of efficiently verifiable total search problems achieving an $n$ versus $Ω_d(n^d)$ separation between quantum one-way and randomized one-way communication for every fixed $d \ge 2$. In the quantum protocol, Alice prepares her message using a single unitary from the $d$th level of the Clifford hierarchy, and Bob performs a Clifford measurement. This separation is asymptotically optimal under this restriction on Alice's message. For $d = 2$, Alice's message is a stabilizer state and Bob's measurement is Clifford, so the protocol uses no magic, yet achieves an optimal quadratic quantum advantage. Finally, we discuss how these separations can be adapted to near-term quantum advantage experiments in which the demonstrated advantage is both unconditional and efficiently verifiable.