An exponential separation between entanglement-assisted and unassisted one-way quantum communication

arXiv:2610.02099 · quant-ph · Submitted 2026-10-01 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "An exponential separation between entanglement-assisted and unassisted one-way quantum communication".

Mira: An exponential separation between entanglement-assisted and unassisted one-way quantum communication demonstrates that shared entanglement can provide an exponential reduction in the cost of classical communication for computing total Boolean functions.

Kai: First, who's behind it and why it matters.

Paper summary: Kai: So, what we're looking at here is this paper titled "An exponential separation between entanglement-assisted and unassisted one-way quantum communication," Ryan Anselm, Srijita Kundu, Olivier Lalonde, and Ashwin Nayak. The main point they're making is that they found an exponential separation for total Boolean functions in the one-way setting. Basically, they show a family of functions where you need only O(log n) bits if you have entanglement beforehand for the classical communication part.

Mira: That’s what caught my eye; it resolves a long-standing question about whether such a separation exists for total functions specifically. The paper claims an exponential separation between an entanglement-assisted classical protocol and an unassisted one-way quantum protocol, where the former is bounded by O(log n) bits and the latter by Omega(n(one/three)) qubits <ref:2610.02099#pg0>.

Kai: It seems like they tackle a really deep problem in communication complexity by using a special case of the subgroup membership problem called MembG,k. That function takes Alice's input as a subgroup H of order at most k in a group G, and Bob gets an element g, and they have to decide if g is in H.

Mira: And they construct this specific instance called the "shifted equality problem," ShiftEqG,r, which is reducible to MembG,k. This reduction is what lets them use existing results for subgroup membership while building a function that shows the trade-off they're after.

Kai: The entanglement-assisted upper bound they found involves Alice preparing two copies of a mixed state on Bob's side, and Bob performing a Hadamard test on each copy with respect to the unitary Ug, which applies right multiplication by g. They show this leads to an entanglement-assisted classical communication cost of O(log k) bits.

Mira: And when they restrict the subgroup order such that k is polylog(G), that communication cost drops further to O(log log G), which sets them apart from the unassisted quantum setting that requires at most O(log G) qubits.

Kai: It's a pretty specific construction, and I'm curious about what kind of group structures they use for this separation to hold up as an asymptotic result.

Mira: That’s exactly what they explore further in the technical details, but the core claim is that this separation exists for total functions in the one-way setting. This finding really addresses that central question about whether entanglement helps significantly when you're only considering one-way quantum communication.

Conclusion: Kai: So, looking at the title "An exponential separation between entanglement-assisted and unassisted one-way quantum communication," it really summarizes the main contribution here: they proved that there are total functions where entanglement helps you save a lot on classical bits, but without entanglement, you still need a significant amount of quantum resources for one-way communication.

Mira: I think the implication is that we have to be careful about assuming entanglement can always provide an exponential reduction in cost for every single computation when we're limited to one-way communication. The paper shows that for total functions, this isn't strictly necessary to achieve certain computational goals without entanglement being present.

Kai: So, if you distill it down simply, the key finding is that the entanglement-assisted classical communication cost can be very small, O(log n) bits, while the unassisted quantum and randomized complexities are much larger at Omega(n(one/three)) <ref:2610.02099#pg0>. It establishes a clear asymptotic gap between these two models for a functional problem.

Mira: That gap is what matters because it confirms that entanglement isn't always the deciding factor when you're only talking about one-way quantum communication for solving total functions. It shows that while entanglement helps considerably in the presence of communication, it isn't an absolute necessity to reach certain computational targets in this specific setting.

Kai: It’s a result that shows a fine line between what’s possible with and without entanglement when you restrict ourselves to one-way quantum communication models for total functions. I wonder how this separation translates into practical limits for things we build today.

Mira: That's the big question, Kai; it pushes the boundary on how we think about communication resources in quantum computation and communication simultaneously. It really forces us to re-evaluate the assumptions we make when modeling these tasks in a one-way setting without entanglement <ref:2610.02099#pg2>.

Kai: Exactly; it means we need to keep pushing the boundaries on understanding these limits, even when the results are about theoretical functions rather than practical hardware. That separation is a piece of information that could inform future designs for quantum networks and communication protocols.

Mira: Indeed, this paper provides a concrete framework for studying these separations in total function settings, which is what was previously open to research <ref:2610.02099#pg2>. It’s a solid piece of work showing how specific constructions can yield these kinds of results.

Kai: So, to wrap up this discussion on "An exponential separation between entanglement-assisted and unassisted one-way quantum communication," the core message is that for total functions, the trade-off between classical bits with entanglement and quantum qubits without entanglement is quite stark asymptotically.

Mira: Precisely; it shows that for specific problems, the presence of shared EPR pairs provides a substantial advantage in terms of communication cost reduction over what you can achieve with just one-way quantum messages.

Kai: We'll keep an eye on how this theoretical separation guides our experimental efforts to build systems where these models interact in ways we can actually measure and test.

Mira: I agree; it’s a result that solidifies the understanding of resource trade-offs in this area of communication complexity.

Department of Computer Science, University of Texas at Austin · Hon Hai (Foxconn) Research Institute · School of Computer Science, and Institute for Quantum Computing, University of Waterloo

quant-ph

Submitted: 2026-10-01

Updated: 2026-10-05

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 86/100

The gist: An exponential separation between entanglement-assisted and unassisted one-way quantum communication demonstrates that shared entanglement can provide an exponential reduction in the cost of

Key concepts

Entanglement-Assisted Communication: This model allows Alice and Bob to share pre-existing entangled quantum pairs (EPR pairs) before starting the computation. This shared resource helps reduce the amount of classical information they need to exchange, potentially lowering the total communication cost for solving a problem.
Unassisted One-Way Quantum Communication: This model involves Alice sending a quantum state to Bob, and Bob performing local operations. Crucially, there is no pre-shared entanglement between them. The complexity here measures the minimum number of qubits needed to solve the problem using only this one-way transmission.
Total Boolean Function: A total function is a function that must output a definite result for every possible input combination. In this context, it refers to any computational problem where Alice and Bob need to compute a specific output based on their inputs, rather than just checking membership in a set.
Shifted Equality Problem (ShiftEqG,r): This is the specific mathematical problem used as an example to demonstrate the separation. It involves determining if a shifted product of two elements in a group G equals a target element h. This problem is constructed to exhibit the desired trade-off between entanglement-assisted and unassisted communication complexities.

Terminology

Entanglement — 133× in this paper · explained in 4 episodes
Annual Symposium on Foundations of Computer Science — 3× in this paper
Core — 3× in this paper · explained in 2 episodes
Trace — 3× in this paper · explained in 2 episodes
Accuracy — 2× in this paper · explained in 1 episode
Generalization — 2× in this paper · explained in 13 episodes
Query Complexity — 2× in this paper · explained in 2 episodes

Summary

An exponential separation between entanglement-assisted and unassisted one-way quantum communication demonstrates that shared entanglement can provide an exponential reduction in the cost of classical communication for computing total Boolean functions. This finding resolves a long-standing question regarding whether such a separation exists for total functions, showing that while entanglement helps significantly in the presence of communication, it is not strictly necessary to achieve certain computational goals when considering only one-way quantum communication.

The Core Result

The main result establishes an asymptotic separation between two communication models for computing a total Boolean function: an entanglement-assisted one-way classical protocol and an unassisted one-way quantum protocol. Specifically, the paper shows that there exists a family of total Boolean functions where the entanglement-assisted classical communication cost is bounded by O(log n) bits, while the unassisted quantum and randomized communication complexities are both bounded by omega(n(1/3)). This provides the first known asymptotic separation between these two models for a functional problem in the one-way setting, answering a central question about whether entanglement can save on (quantum) communication.

The Function and Problem

The separation is achieved using a special case of the subgroup membership problem, specifically bounded-order subgroup membership denoted as MembG,k. This function takes Alice's input as a subgroup H of order at most k in a finite group G, and Bob's input as an element g ∈ G, requiring them to decide if g ∈ H. The paper constructs a specific instance of this problem called the shifted equality problem, ShiftEqG,r, which is reducible to MembG,k. This reduction allows the authors to leverage known results for subgroup membership while constructing a function that exhibits the desired communication complexity trade-off.

The Entanglement-Assisted Upper Bound

The entanglement-assisted classical upper bound is derived by reducing the problem to a remote state preparation task. The protocol involves Alice remotely preparing two copies of a mixed state ρ on Bob’s side, where ρ is the uniform mixture of all of the left coset states of H. Bob then performs a Hadamard test on each copy with respect to the unitary Ug, which applies right multiplication by g. The paper shows that this construction allows for an entanglement-assisted classical communication cost of O(log k) bits and uses 2⌈log2G⌉ shared EPR pairs. When the subgroup order is restricted such that k = polylog(G), the communication cost drops to O(log log G), enabling an exponential separation from unassisted quantum communication, which requires at most O(log G) qubits.

The Unassisted Quantum Lower Bound

The lower bound for the unassisted quantum one-way setting is established using Yao’s min-max principle. The paper shows that the success probability of any entanglement-unassisted protocol with low communication is bounded by an expression involving a maximum over collections of binary POVMs. By imposing specific structure on the group G—specifically, assuming G has a central element ζ of order 3—the authors derive a sharp upper bound on this success probability, leading to the lower bound: omega(n(1/3)) qubits of communication. This lower bound is shown to hold for the shifted equality problem ShiftEqG,r under a hard distribution.

The Trade-Off and Optimality

Theorem 1.1 concludes that any one-way protocol for this function using E shared EPR pairs and C bits or qubits of communication must satisfy a trade-off: E + C = omega(n(1/3)). The paper further shows that the entanglement-assisted protocol uses Θ(n) shared EPR pairs, while the lower bound requires omega(n(1/3)) EPR pairs. This implies that an exponential blowup in simulation cost is necessary, even for total functions. Furthermore, the authors show that the O(log n)-bit entanglement-assisted protocol is asymptotically optimal by relating its communication cost to a simulation theorem and the lower bound on randomized one-way communication.

Technical Details of the Reduction

The reduction from ShiftEqG,r to MembG,k is detailed through a construction involving a group Ge which encodes pairs of elements from GS. The subgroup H0 within Ge is defined such that its size is 2r+1. The paper proves that the shifted product g1shifts(g2) equals h if and only if the corresponding element in the larger group Ge belongs to the subgroup X(g1, g2). This intricate construction provides a rigorous link between the functional problem and established communication complexity bounds for subgroup membership. Finally, Theorem 6.1 instantiates a concrete family of groups—the generalized Heisenberg group Hm over F3—to provide an explicit example where the required dimension D is 3(2r), thereby completing the proof of Theorem 1.1.

Improvements for AI systems

As a fastidious and diligent researcher, I have analyzed this seminal paper by Anselm et al., An exponential separation between entanglement-assisted and unassisted one-way quantum communication, which establishes a fundamental trade-off in quantum communication complexity.

The core finding is that for certain total Boolean functions (specifically, those reducible to the bounded-order subgroup membership problem), shared entanglement provides an exponential speedup in classical communication cost when Alice sends a single message to Bob (one-way setting).

Here are the specific improvements and capabilities an AI system could gain by leveraging these theoretical insights:

)

AI System Improvements Based on Theorem 1.1 and Related Results:

The primary improvement is the ability to design quantum-enhanced communication protocols that outperform classical ones, even in scenarios where entanglement is only shared beforehand, provided the communication channel is restricted to one-way classical messages.

Specific Capabilities:

[MembG,k] Function Solving with Entanglement Assistance (Theorem 4.1):
[O(log k)] Communication Bound: The AI system can solve the Bounded-Order Subgroup Membership problem for any finite group and subgroup order constraint (order at most k) using only a communication cost of only logarithmic in the size of the subgroup, i.e., O(log k) bits, when shared entanglement is available.
[Exponential Separation]: The system can exploit the exponential gap between entanglement-assisted protocols (O(log k)) and unassisted quantum protocols (Ω(n(1/3))) for specific total functions like ShiftEqG,r. This means it can determine whether a problem requires exponentially more quantum communication without entanglement than with prior entanglement.
[Protocol Design for Remote State Preparation]: The system can design protocols that achieve the task of remotely preparing rank-r flat states (Definition 3.1) using only O(log d/r) classical bits and shared EPR pairs, where d is the dimension of the state space, demonstrating near-optimal resource utilization for quantum state preparation tasks.
[Complexity Classification]: The system can rigorously classify communication problems based on their entanglement advantage. It can identify functions that are entanglement-hard (requiring high entanglement resources) versus those that are communication-hard (requiring high classical communication without entanglement).
[Lower Bound Verification]: The system can use the analytic lower bounds derived from the paper (e.g., Theorem 5.2, Theorem 5.3) to verify that a given one-way quantum protocol is indeed sub-optimal under certain input distributions, specifically by showing that any protocol achieving a high success probability must exceed the established communication bounds if entanglement is absent.
[Group Theory Optimization]: The system can optimize the choice of groups and parameters (e.g., using the generalized Heisenberg group Hm over F3) to maximize the separation factor between entanglement-assisted and unassisted quantum complexity, allowing for targeted cryptographic or computational problem instances where this gap is maximized relative to input size.

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 0,1 n times 0,1 n to 0,1 that can be computed with O(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.