Ask a quantum information theorist whether pre-shared entanglement can make communication dramatically cheaper, and the honest answer for a long time has been “sometimes, in special settings.” Superdense coding saves a factor of two. Bigger gaps were known only for relational tasks, or for partial functions in the simultaneous-message model, and those gaps tend to disappear once the two parties are allowed to talk to each other directly. A new paper by Ryan Anselm, Srijita Kundu, Olivier Lalonde and Ashwin Nayak closes one version of this question: for a total Boolean function and one-way communication, prior entanglement can make the message exponentially shorter.
This article was drafted with Claude and fact-checked against the cited primary sources. The paper is a theory preprint (arXiv v1, 1 October 2026) and has not yet been peer reviewed.
Why this question matters
The no-communication theorem says entanglement alone cannot carry a message. But once some communication is allowed, entanglement is a resource that might replace a lot of it. Buhrman and de Wolf, and Brassard, asked early on how large that saving can be. Two standard models frame the comparison:
Unassisted quantum communication (Yao’s model): Alice and Bob may send qubits, but share no entanglement at the start.
Entanglement-assisted classical communication (Cleve–Buhrman model): Alice and Bob may share any input-independent entangled state, but send only classical bits.
Teleportation means the second model can simulate the first at twice the cost, so the interesting direction is whether the entanglement-assisted model can be much cheaper. A recurring obstacle, the authors note, is that most quantum communication lower-bound techniques apply equally to protocols with and without entanglement, so they cannot detect such a gap.
What the paper shows
The main result (Theorem 1.1) exhibits a family of total Boolean functions fn on n-bit inputs for Alice and Bob such that:
with prior entanglement, a one-way classical protocol from Alice to Bob computes fn with O(log n) bits and worst-case error at most 1/3, using Θ(n) shared EPR pairs;
without shared entanglement, the one-way quantum communication complexity, and also the one-way randomized complexity, is Θ(n1/3).
Because the function is total, there is no promise on the inputs: every pair of inputs must be answered correctly. The authors describe this as the first asymptotic separation between these two models for any functional problem, answering the Buhrman–de Wolf and Brassard question in the one-way setting. They also point out consequences: it rules out a direct shared-entanglement analogue of Newman’s theorem (which removes shared randomness at small cost), and, combined with a simulation result of Shi and Zhu, it shows the O(log n) protocol is asymptotically optimal and that an exponential blow-up in simulating entanglement-assisted protocols classically is unavoidable even for total functions.
The key idea: subgroup membership, sent as a mixed state
The function is a special case of subgroup membership, a problem introduced by Watrous and brought to one-way communication by Aaronson, Le Gall, Russell and Tani. Alice holds a subgroup H of a finite group G, Bob holds an element g, and they must decide whether g ∈ H. In the known quantum protocol, Alice sends the uniform superposition over H, and Bob runs a Hadamard test with “multiply by g”: the test always passes if g ∈ H and passes with probability 1/2 otherwise. That costs O(log |G|) qubits.
The new protocol uses a variant the authors call bounded-order subgroup membership, where |H| is at most some k. Instead of sending a pure state, Alice uses remote state preparation (which, unlike teleportation, exploits the fact that the sender knows a classical description of the state) to give Bob the uniform mixture of all coset states of H. Any coset state works for Bob’s test, and this mixed state has high rank, which is exactly what makes remote preparation cheap: O(log |H|) classical bits plus O(log |G|) EPR pairs. When |H| is tiny compared with G, the message becomes exponentially shorter than the unassisted quantum protocol.
How the lower bound works
The hard part is proving that, without entanglement, no short quantum message suffices. The authors reduce a new “shifted equality” problem to bounded-order subgroup membership. In it, Alice holds two arrays g1, g2 of group elements indexed by the r-bit strings, Bob holds an array h and a shift s, and they must decide whether g1(x) g2(x+s) = h(x) for every x. The structure mirrors the Boolean Hidden Matching problem, with XOR replaced by a group operation and, crucially, no promise on the no-instances.
The argument then proceeds in steps:
For unassisted one-way protocols, the best success probability under an input distribution is an expected operator norm of Bob’s averaged measurement operators (Lemma 3.2). With entanglement, Bob’s measurement also acts on an arbitrarily large shared state, so this characterization no longer applies. That asymmetry is what lets the bound separate the two models.
The hard distribution multiplies Bob’s array by a central group element ζ of order 3, chosen with probabilities 1/2, 1/4, 1/4.
The operator norm is bounded through Schatten-p moments, after approximating the dependent sum by one with independent random “rotations,” where a matrix concentration bound applies.
The approximation error reduces, via Fourier analysis on G, to 1/D, where D is the smallest dimension of an irreducible representation that acts nontrivially on ζ.
The final ingredient is a group where D is huge: the generalized Heisenberg group over 𝔽3, where D equals 3m. In the instantiation, the input length is Θ(23r), the entanglement-assisted cost is Θ(r) bits, and the unassisted cost is Θ(2r), which gives the log n versus n1/3 separation.
Why it matters
Demonstrated: an exponential gap, for a total function, between entanglement-assisted classical and unassisted quantum one-way communication. Also demonstrated, as a side result (Section 3.3), are sharper classical simulations of entanglement-assisted protocols. The result settles a question that had remained open despite progress in nearby settings (SMP separations by Gavinsky–Kempe–Regev–de Wolf and Arunachalam–Girish, and a relational separation by Hasegawa–Le Gall–Modanese).
Technical perspective (interpretation)
My reading is that the conceptual lever is small and transferable: when the receiver only needs some member of a family of states, sending a high-rank mixture instead of one pure state can make remote state preparation far cheaper than teleportation. The lower-bound technique matters just as much, because it targets a feature unassisted protocols have and assisted ones lack. Whether it extends beyond one-way communication is unclear, and the authors themselves expect their approach not to.
The paper also contains an unusually explicit AI disclosure. The authors write that large language models (including GPT and Claude models) were used extensively, that they discovered the bounded-order problem and its upper bounds themselves, and that after many rounds of prompting GPT-6 Astra produced the shifted-equality instantiation and the corresponding quantum lower bound, which they then independently verified, developed and simplified. They state that they wrote the paper and take responsibility for its content. Readers should weigh that as the authors present it; independent refereeing has not yet happened.
Limitations and open questions
One-way only. The separation is against one-way unassisted protocols. Bounded-order subgroup membership has an efficient two-way classical protocol, so this function is not expected to give a gap against two-way communication.
Polynomial, not exponential, in n. The unassisted cost is Θ(n1/3), so the gap is exponential relative to O(log n), not an “n versus log n” gap.
Lots of entanglement. The protocol uses Θ(n) EPR pairs, while the lower bound only forces Ω(n1/3). How much entanglement is truly needed is open.
A complicated function. The construction relies on Heisenberg groups over 𝔽3; the authors ask for simpler functions and groups.
Other models remain open. Open: separations against SMP-assisted protocols, two-way versions, and whether any asymptotic quantum–classical one-way separation exists for a total function without entanglement.
This is a pure-theory result with no experiment, code or data.
Paper information
Title: An exponential separation between entanglement-assisted and unassisted one-way quantum communication
Authors: Ryan Anselm (University of Texas at Austin), Srijita Kundu (Hon Hai (Foxconn) Research Institute), Olivier Lalonde (University of Waterloo, School of Computer Science and Institute for Quantum Computing), Ashwin Nayak (University of Waterloo, Department of Combinatorics and Optimization and Institute for Quantum Computing)
arXiv: 2610.02099v1 [quant-ph], submitted 1 October 2026
Code/data: none (theory paper)