⚛️ quantum physics

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

This paper resolves a longstanding open question in quantum communication complexity by demonstrating an exponential separation for total Boolean functions, showing that a specific subgroup membership problem can be solved with $O(\log n)$ classical bits using prior entanglement but requires $\Omega(n^{1/3})$ qubits without it.

Original authors: Ryan Anselm, Srijita Kundu, Olivier Lalonde, Ashwin Nayak

Published 2026-10-02

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ryan Anselm, Srijita Kundu, Olivier Lalonde, Ashwin Nayak

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of information, there is a fundamental rule that has long puzzled scientists: sharing a mysterious connection does not, by itself, allow two people to send a message to one another. This principle, known as the no-communication theorem, dictates that if two people, Alice and Bob, share a special quantum link called entanglement, Alice cannot simply act on her part of the link to instantly transmit a thought to Bob. The connection is silent. However, this rule leaves a critical question unanswered: if Alice and Bob are allowed to speak, but every word they say costs something, how much can that silent, pre-existing connection help them save? For decades, researchers have wondered if this hidden resource could allow them to solve complex problems with a tiny whisper of communication, whereas without it, they would need to shout a massive amount of data. This question sits at the heart of a field called communication complexity, which studies the minimum effort required to solve a task when information is split between two distant parties.

A team of researchers has now answered this question with a definitive and surprising result. They have demonstrated that for a specific type of problem involving a total function—a task where an answer must be given for every possible combination of inputs—entanglement can provide an exponential advantage. In their scenario, Alice and Bob are trying to determine if a specific mathematical condition holds true between their separate pieces of data. When they are allowed to share entanglement before the task begins, they can solve the problem by sending a message that grows only logarithmically with the size of the input. In practical terms, if the input size doubles, the message length increases by a tiny, almost negligible amount. However, if they are stripped of this shared entanglement, even if they are allowed to send quantum messages instead of classical ones, the amount of information they must exchange grows much faster, following a power law that is vastly larger. The gap between these two scenarios is not just a little bit; it is exponential, meaning the difference in effort becomes astronomical as the problem gets bigger.

The researchers achieved this by constructing a family of problems based on the concept of subgroup membership. Imagine a large collection of items organized into groups, where Alice knows the rules for a specific small group, and Bob holds a single item. Their goal is to decide if Bob's item belongs to Alice's group. The team designed a variation of this problem where the groups are guaranteed to be small. They showed that with entanglement, Alice can use a technique called remote state preparation to essentially "teleport" a description of her group to Bob using only a small number of classical bits. This process relies on the fact that entanglement allows them to prepare a specific quantum state on Bob's side without sending the state itself, provided they share the necessary quantum link beforehand. Bob then performs a simple test to see if his item fits the pattern. Without the shared link, however, Alice must send a message that is large enough to describe the group in a way that Bob can verify without any prior quantum connection. The researchers proved mathematically that this unassisted message must be significantly longer, specifically requiring a number of quantum bits that scales with the cube root of the input size, a stark contrast to the logarithmic scale of the entangled version.

This finding resolves a long-standing debate in the field. Previously, it was known that entanglement could help in specific, restricted settings, such as when the two parties cannot talk directly to each other but must send messages to a referee, or when the problem allows for "no" answers to be ambiguous. But for a standard, total function where a definite yes or no is required for every input, and where Alice sends a single message to Bob, it was an open question whether entanglement could offer such a dramatic advantage. The new work proves that it can. It also rules out the possibility that a simple trick, similar to one used for shared randomness, could remove the need for entanglement without a massive cost. The researchers showed that to simulate their efficient entangled protocol using only classical communication and shared randomness, one would need to send a message that is exponentially longer, confirming that the quantum link is not just a convenience but a fundamental resource that changes the nature of the communication required.

The specific problem the team used to prove this is a generalization of a puzzle known as the Boolean Hidden Matching problem, but adapted to work with groups of numbers rather than simple bits. They created a scenario where Alice and Bob must check if a complex relationship holds between their data across many points. By carefully choosing the mathematical structure of the groups involved, specifically using a type of group known as a generalized Heisenberg group, they ensured that the unassisted quantum protocol would fail unless it sent a massive amount of information. The proof relies on deep properties of how these groups behave mathematically, showing that without the entangled link, the information Alice sends is too weak to distinguish the correct answer from a wrong one with high probability. The result is a clear, mathematical separation: a task that can be solved with a whisper when entanglement is present, but requires a shout when it is absent.

This work does not just settle a theoretical argument; it clarifies the limits of what is possible in quantum communication. It shows that while entanglement cannot transmit information on its own, it acts as a powerful amplifier for communication when it is allowed. The researchers also noted that their efficient protocol requires a large amount of shared entanglement—specifically, a number of entangled pairs that grows linearly with the input size. This raises a new question for the future: is it possible to achieve this same exponential saving with much less entanglement, or is the large reserve of shared links a necessary cost? For now, the answer remains open, but the path forward is clear. The team has established that for total functions in a one-way setting, the power of entanglement is real, profound, and capable of shrinking communication costs in ways that were previously thought impossible.

Technical Summary: An Exponential Separation between Entanglement-Assisted and Unassisted One-Way Quantum Communication

Problem Statement

The central question addressed by this work is whether shared entanglement can provide an exponential advantage in communication complexity for total Boolean functions in the one-way setting. While exponential separations between entanglement-assisted and unassisted models were previously known for relational problems and partial functions (e.g., in the simultaneous message passing model), it remained an open question whether such a separation exists for total functions when communication is restricted to a single message from Alice to Bob. Specifically, the authors investigate if a task can be solved with $O(\log n)$ classical bits given prior entanglement, while requiring $\Omega(n^{1/3})$ qubits without entanglement.

Methodology

The authors construct a family of total Boolean functions based on a variant of the subgroup membership problem, specifically tailored to facilitate both an efficient entanglement-assisted upper bound and a strong unassisted lower bound.

1. The Core Function: Shifted Equality

The primary object of study is the Shifted Equality problem, denoted as $\text{ShiftEq}_{G,r}$ .

Inputs: Alice receives two functions $g_1, g_2: \mathbb{Z}_2^r \to G$ , and Bob receives a function $h: \mathbb{Z}_2^r \to G$ and a shift vector $s \in \mathbb{Z}_2^r$ .
Task: Determine if $g_1(x)g_2(x+s) = h(x)$ for all $x \in \mathbb{Z}_2^r$ .
Relation to Subgroup Membership: The authors reduce $\text{ShiftEq}_{G,r}$ to the Bounded-Order Subgroup Membership problem ( $\text{Memb}_{\tilde{G}, k}$ ). They construct a larger group $\tilde{G}$ such that the shifted equality condition is equivalent to checking if a specific element belongs to a subgroup of order at most $k = 2^{r+1}$ .

2. Upper Bound: Entanglement-Assisted Protocol

For the bounded-order subgroup membership problem, the authors design an entanglement-assisted one-way classical protocol:

Technique: Instead of Alice sending a quantum state (as in standard quantum protocols), she uses Remote State Preparation (RSP).
Mechanism: Alice remotely prepares a specific mixed state $\rho$ on Bob's side. This state is a uniform mixture of left coset states of the subgroup $H$ .
Efficiency: Because the state $\rho$ is a mixed state of rank $m = [G:H]$ , RSP allows Alice to communicate the necessary information using $O(\log |H|)$ bits. Since the subgroup order is bounded by $k$ , the communication cost is $O(\log k)$ .
Verification: Bob performs a Hadamard test on the received state using a unitary operator corresponding to right multiplication by his input element $g$ . The test accepts with probability 1 if $g \in H$ and 0 otherwise (in the ideal case).

3. Lower Bound: Unassisted Quantum Protocol

To prove the lower bound for unassisted quantum one-way communication, the authors develop a novel analytic technique that distinguishes between entanglement-assisted and unassisted protocols.

Hard Distribution: They define a distribution where Alice's inputs are random functions, and Bob's input $h$ is a "shifted product" of Alice's functions multiplied by a central element $\zeta \in Z(G)$ of order 3. The value of the function depends on whether the multiplier is the identity.
Success Probability Bound: Using Yao's min-max principle, the success probability is bounded by the operator norm of an expectation over Bob's POVM elements.
Analytic Approximation: The core technical innovation is approximating the expectation of a sum of dependent terms (arising from the shift structure) by an expectation of independent terms. This is achieved by introducing random phase rotations $\zeta^{\phi_s}$ for each shift $s$ .
Group Representation Theory: The difference between the dependent and independent cases is bounded by the spectral norm of an operator $(I-P)K$ acting on the space of functions over the group. By moving to the Fourier domain, this norm is shown to be $1/D$ , where $D$ is the minimum dimension of an irreducible representation (irrep) of $G$ in which the central element $\zeta$ is non-trivial.
Group Instantiation: The authors instantiate the group $G$ as a generalized Heisenberg group $H_m$ over the field $\mathbb{F}_3$ . For this group, they prove that $D = 3^m$ . By choosing parameters such that $m \approx 2^{2r}$ , they ensure $D$ is exponentially large relative to the input size, forcing the success probability of any low-communication unassisted quantum protocol to be close to random guessing.

Key Contributions and Results

Main Theorem (Theorem 1.1)

The authors exhibit a family of total Boolean functions $f_n: \{0, 1\}^n \times \{0, 1\}^n \to \{0, 1\}$ such that:

Entanglement-Assisted: There exists a one-way classical protocol with communication cost $O(\log n)$ and error $\le 1/3$ , utilizing $\Theta(n)$ shared EPR pairs.
Unassisted: Any one-way quantum (or randomized classical) protocol without entanglement requires $\Omega(n^{1/3})$ bits/qubits to achieve the same error bound.

Technical Contributions

First Exponential Separation for Total Functions: This is the first known asymptotic separation between entanglement-assisted classical communication and unassisted quantum communication for a total function in the one-way setting.
Refined Simulation Theorem: The authors sharpen the simulation theorem of Shi and Zhu [SZ08], showing that an entanglement-assisted one-way classical protocol using $C$ bits can be simulated by an unassisted randomized one-way protocol using $O(2^C)$ bits. Combined with their lower bound, this proves the $O(\log n)$ upper bound is asymptotically optimal.
New Lower Bound Technique: They introduce a method for proving lower bounds on unassisted quantum protocols that relies on the representation theory of the underlying group, specifically exploiting the spectral gap of operators related to central elements of order 3. This technique avoids the limitations of standard lower-bound methods that apply equally to entanglement-assisted protocols.

Significance and Claims

The paper claims to resolve a longstanding open question in quantum communication complexity raised by Buhrman and de Wolf [BW01] and Brassard [Bra03]. Specifically:

It demonstrates that shared entanglement can enable exponential savings in communication for total functions, even when restricted to a single message.
It rules out a direct analogue of Newman's theorem for entanglement-assisted protocols, showing that shared randomness (which can be simulated with $O(\log n)$ bits) cannot replace shared entanglement in this context.
The result highlights that the "power" of entanglement in communication complexity is not merely a feature of relational or partial problems but extends to fundamental functional tasks.

The authors note that while their protocol uses a polynomial amount of shared entanglement ( $\Theta(n)$ EPR pairs) to achieve the $O(\log n)$ communication, the lower bound only requires $\Omega(n^{1/3})$ EPR pairs to establish the trade-off. They leave open the question of whether the amount of entanglement required for such a separation can be reduced further.

The paper concludes by identifying open problems, including whether similar separations exist for two-way communication models or in the simultaneous message passing (SMP) setting against unassisted quantum protocols, and whether simpler total functions can achieve this separation.