arXiv:2610.02099
An exponential separation between entanglement-assisted and unassisted one-way quantum communication
Ryan Anselm, Srijita Kundu, Olivier Lalonde, Ashwin Nayak
Abstract
A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement, yet require much more quantum communication in the absence of entanglement. Separations of this nature were previously known for relational problems and, in the simultaneous message passing model, for partial functions. But it has remained unresolved whether any such separation exists for a total Boolean function. We resolve this question with an exponential separation in the one-way setting: we exhibit a family of total Boolean functions $f_n\colon \{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ that can be computed with $O(\log n)$ bits of one-way classical communication given prior entanglement, but that require $Ω(n^{1/3})$ qubits of one-way quantum communication without entanglement. Our function is a special case of the subgroup membership problem, first studied in the communication setting by Aaronson, Le Gall, Russell, and Tani.
AI Summary
The paper asks whether prior entanglement can substantially reduce quantum communication for computing a total Boolean function. It constructs a family $f_n:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}$ with entanglement-assisted one-way classical communication complexity $\Theta(\log n)$, whereas both unassisted one-way quantum and randomized classical complexity are $\Theta(n^{1/3})$, at worst-case error at most $1/3$. The assisted protocol uses $\Theta(n)$ EPR pairs. The construction proceeds through bounded-order subgroup membership: Alice holds a subgroup $H\leq G$ with $|H|\leq k$, and Bob tests membership of an element. An assisted protocol uses $O(\log k)$ classical bits and $O(\log|G|)$ EPR pairs by remotely preparing a uniform mixture of left-coset states, then applying Hadamard tests. A total “shifted equality” function over group-valued arrays reduces to this problem. Its unassisted quantum lower bound combines an operator-norm characterization of one-way protocols, matrix moment bounds, and nonabelian Fourier analysis controlling correlations through representation dimensions. Generalized Heisenberg groups yield the stated parameters. The paper also sharpens classical SMP simulations of entanglement-assisted classical protocols to $O(2^C)$ communication for one-way protocols and $O(2^{2C})$ for interactive protocols. The separation is restricted to one-way communication; the subgroup-membership construction has an efficient two-way classical protocol. The entanglement requirement remains unresolved: the lower bound implies $E+C=\Omega(n^{1/3})$, leaving a gap between necessary and sufficient entanglement for logarithmic communication. Separations against two-way unassisted quantum protocols, simpler separating functions, and unassisted quantum–classical one-way separations for total functions remain open.
After many rounds of interaction, GPT-6 Astra eventually produced a concrete instantiation of the problem in the form of the shifted equality problem and the corresponding quantum lower bound.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.