Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.02099

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

Ryan Anselm, Srijita Kundu, Olivier Lalonde, Ashwin Nayak

quant-phSubmitted Oct 1, 2026• Announced Oct 2, 2026• 0 citations• Revised Oct 5, 2026 (v2)
v1 · Oct 1, 2026v2 · Oct 5, 2026
arXivHTMLPDF

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.

No sign of AI-generated textAI use disclosed
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.

Related papers

A new exponential separation between quantum and classical one-way communication complexity

Ashley Montanaro

We present a new example of a partial boolean function whose one-way quantum communication complexity is exponentially lower than its one-way classical communication complexity. The problem is a natural generalisation of the previously studied Subgroup Membership problem: Alice receives a bit string $x$, Bob receives a permutation matrix $M$, and their task is to determine whether $Mx=x$ or $Mx$ is far from $x$. The proof uses Fourier analysis and an inequality of Kahn, Kalai and Linial.

arXiv:1007.3587•Quantum Information and Computation•Jul 1, 2011•14 citations

Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography

Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis +2 more

We give an exponential separation between one-way quantum and classical communication protocols for a partial Boolean function (a variant of the Boolean hidden matching problem of Bar-Yossef et al.). Previously, such an exponential separation was known only for a relational problem. The communication problem corresponds to a strong extractor that fails against a small amount of quantum information about its random source. Our proof uses the Fourier coefficients inequality of Kahn, Kalai, and Linial. We also give a number of applications of this separation. In particular, we show that there are privacy amplification schemes that are secure against classical adversaries but not against quantum adversaries; and we give the first example of a key-expansion scheme in the model of bounded-storage cryptography that is secure against classical memory-bounded adversaries but not against quantum ones.

SIAM Journal on Computing•Dec 19, 2008•90 citations

Trade-Offs Between Entanglement and Communication

Srinivasan Arunachalam, Uma Girish

We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on $n$ bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. For every $k\ge 1$: $Q\|^*$ versus $R2^*$: We show that quantum simultaneous protocols with $\tildeΘ(k^5 \log^3 n)$ qubits of entanglement can exponentially outperform two-way randomized protocols with $O(k)$ qubits of entanglement. This resolves an open problem from [Gav08] and improves the state-of-the-art separations between quantum simultaneous protocols with entanglement and two-way randomized protocols without entanglement [Gav19, GRT22]. $R\|^*$ versus $Q\|^*$: We show that classical simultaneous protocols with $\tildeΘ(k \log n)$ qubits of entanglement can exponentially outperform quantum simultaneous protocols with $O(k)$ qubits of entanglement, resolving an open question from [GKRW06, Gav19]. The best result prior to our work was a relational separation against protocols without entanglement [GKRW06]. $R\|^*$ versus $R1^*$: We show that classical simultaneous protocols with $\tildeΘ(k\log n)$ qubits of entanglement can exponentially outperform randomized one-way protocols with $O(k)$ qubits of entanglement. Prior to our work, only a relational separation was known [Gav08]. Our techniques can also be used to show advantages of quantum communication models over hybrid classical-quantum models, i.e., models that have a large amount of both classical communication and quantum simultaneous communication.

arXiv:2306.01233•Leibniz international proceedings in informatics•Jan 1, 2023•4 citations

Two Results about Quantum Messages

Hartmut Klauck, Supartha Podder

We show two results about the relationship between quantum and classical messages. Our first contribution is to show how to replace a quantum message in a one-way communication protocol by a deterministic message, establishing that for all partial Boolean functions $f:\{0,1\}^n\times\{0,1\}^m\to\{0,1\}$ we have $D^{A\to B}(f)\leq O(Q^{A\to B,*}(f)\cdot m)$. This bound was previously known for total functions, while for partial functions this improves on results by Aaronson, in which either a log-factor on the right hand is present, or the left hand side is $R^{A\to B}(f)$, and in which also no entanglement is allowed. In our second contribution we investigate the power of quantum proofs over classical proofs. We give the first example of a scenario, where quantum proofs lead to exponential savings in computing a Boolean function. The previously only known separation between the power of quantum and classical proofs is in a setting where the input is also quantum. We exhibit a partial Boolean function $f$, such that there is a one-way quantum communication protocol receiving a quantum proof (i.e., a protocol of type QMA) that has cost $O(\log n)$ for $f$, whereas every one-way quantum protocol for $f$ receiving a classical proof (protocol of type QCMA) requires communication $Ω(\sqrt n/\log n)$.

arXiv:1402.4312•Feb 18, 2014•0 citations

Exponential Separation of Quantum and Classical One-Way Communication Complexity

Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM$_n$: Alice gets as input a string ${\bf x}\in\{0, 1\}^n$, and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple $\langle i,j,b \rangle$ such that the edge $(i,j)$ belongs to the matching M and $b=x_i\oplus x_j$. We prove that the quantum one-way communication complexity of HM$_n$ is $O(\log n)$, yet any randomized one-way protocol with bounded error must use $\Omega({\sqrt{n}})$ bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM), and hence we provide the first exponential separation between quantum SM and randomized SM with public coins. For a Boolean decision version of HM$_n$, we show that the quantum one-way communication complexity remains $O(\log n)$ and that the 0-error randomized one-way communication complexity is $\Omega(n)$. We prove that any randomized linear one-way protocol with bounded error for this problem requires $\Omega(\sqrt[3]{n \log n})$ bits of communication.

SIAM Journal on Computing•Jan 1, 2008•57 citations

Exponential separations for one-way quantum communication complexity, with applications to cryptography

Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis +2 more

We give an exponential separation between one-way quantum and classical communication protocols for twopartial Boolean functions, both of which are variants of the Boolean Hidden Matching Problem of Bar-Yossef et al. Earlier such an exponential separation was known only for a relational version of the Hidden Matching Problem. Our proofs use the Fourier coefficients inequality of Kahn, Kalai, and Linial. We give a number of applications of this separation. In particular, in the bounded-storage model of cryptography we exhibita scheme that is secure against adversaries with a certain amount of classical storage, but insecure against adversaries with a similar (or even much smaller) amount of quantum storage; in the setting of privacy amplification, we show that there are strong extractors that yield a classically secure key, but are insecure against a quantum adversary.

arXiv:quant-ph/0611209•ACM Symposium on Theory of Computing (STOC)•Jun 11, 2007•160 citations
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 fn ⁣:{0,1}n×{0,1}n→{0,1}f_n\colon \{0,1\}^n \times \{0,1\}^n \to \{0,1\}fn​:{0,1}n×{0,1}n→{0,1} that can be computed with O(log⁡n)O(\log n)O(logn) bits of one-way classical communication given prior entanglement, but that require Ω(n1/3)Ω(n^{1/3})Ω(n1/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.
The paper asks whether prior entanglement can substantially reduce quantum communication for computing a total Boolean function. It constructs a family fn:{0,1}n×{0,1}n→{0,1}f_n:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}fn​:{0,1}n×{0,1}n→{0,1} with entanglement-assisted one-way classical communication complexity Θ(log⁡n)\Theta(\log n)Θ(logn), whereas both unassisted one-way quantum and randomized classical complexity are Θ(n1/3)\Theta(n^{1/3})Θ(n1/3), at worst-case error at most 1/31/31/3. The assisted protocol uses Θ(n)\Theta(n)Θ(n) EPR pairs.
The construction proceeds through bounded-order subgroup membership: Alice holds a subgroup H≤GH\leq GH≤G with ∣H∣≤k|H|\leq k∣H∣≤k, and Bob tests membership of an element. An assisted protocol uses O(log⁡k)O(\log k)O(logk) classical bits and O(log⁡∣G∣)O(\log|G|)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(2C)O(2^C)O(2C) communication for one-way protocols and O(22C)O(2^{2C})O(22C) 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=Ω(n1/3)E+C=\Omega(n^{1/3})E+C=Ω(n1/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.
We present a new example of a partial boolean function whose one-way quantum communication complexity is exponentially lower than its one-way classical communication complexity. The problem is a natural generalisation of the previously studied Subgroup Membership problem: Alice receives a bit string xxx, Bob receives a permutation matrix MMM, and their task is to determine whether Mx=xMx=xMx=x or MxMxMx is far from xxx. The proof uses Fourier analysis and an inequality of Kahn, Kalai and Linial.
We give an exponential separation between one-way quantum and classical communication protocols for a partial Boolean function (a variant of the Boolean hidden matching problem of Bar-Yossef et al.). Previously, such an exponential separation was known only for a relational problem. The communication problem corresponds to a strong extractor that fails against a small amount of quantum information about its random source. Our proof uses the Fourier coefficients inequality of Kahn, Kalai, and Linial. We also give a number of applications of this separation. In particular, we show that there are privacy amplification schemes that are secure against classical adversaries but not against quantum adversaries; and we give the first example of a key-expansion scheme in the model of bounded-storage cryptography that is secure against classical memory-bounded adversaries but not against quantum ones.
We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on nnn bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. For every k≥1k\ge 1k≥1: Q∥∗Q\|^*Q∥∗ versus R2∗R2^*R2∗: We show that quantum simultaneous protocols with Θ~(k5log⁡3n)\tildeΘ(k^5 \log^3 n)Θ~(k5log3n) qubits of entanglement can exponentially outperform two-way randomized protocols with O(k)O(k)O(k) qubits of entanglement. This resolves an open problem from [Gav08] and improves the state-of-the-art separations between quantum simultaneous protocols with entanglement and two-way randomized protocols without entanglement [Gav19, GRT22]. R∥∗R\|^*R∥∗ versus Q∥∗Q\|^*Q∥∗: We show that classical simultaneous protocols with Θ~(klog⁡n)\tildeΘ(k \log n)Θ~(klogn) qubits of entanglement can exponentially outperform quantum simultaneous protocols with O(k)O(k)O(k) qubits of entanglement, resolving an open question from [GKRW06, Gav19]. The best result prior to our work was a relational separation against protocols without entanglement [GKRW06]. R∥∗R\|^*R∥∗ versus R1∗R1^*R1∗: We show that classical simultaneous protocols with Θ~(klog⁡n)\tildeΘ(k\log n)Θ~(klogn) qubits of entanglement can exponentially outperform randomized one-way protocols with O(k)O(k)O(k) qubits of entanglement. Prior to our work, only a relational separation was known [Gav08]. Our techniques can also be used to show advantages of quantum communication models over hybrid classical-quantum models, i.e., models that have a large amount of both classical communication and quantum simultaneous communication.
We show two results about the relationship between quantum and classical messages. Our first contribution is to show how to replace a quantum message in a one-way communication protocol by a deterministic message, establishing that for all partial Boolean functions f:{0,1}n×{0,1}m→{0,1}f:\{0,1\}^n\times\{0,1\}^m\to\{0,1\}f:{0,1}n×{0,1}m→{0,1} we have DA→B(f)≤O(QA→B,∗(f)⋅m)D^{A\to B}(f)\leq O(Q^{A\to B,*}(f)\cdot m)DA→B(f)≤O(QA→B,∗(f)⋅m). This bound was previously known for total functions, while for partial functions this improves on results by Aaronson, in which either a log-factor on the right hand is present, or the left hand side is RA→B(f)R^{A\to B}(f)RA→B(f), and in which also no entanglement is allowed. In our second contribution we investigate the power of quantum proofs over classical proofs. We give the first example of a scenario, where quantum proofs lead to exponential savings in computing a Boolean function. The previously only known separation between the power of quantum and classical proofs is in a setting where the input is also quantum. We exhibit a partial Boolean function fff, such that there is a one-way quantum communication protocol receiving a quantum proof (i.e., a protocol of type QMA) that has cost O(log⁡n)O(\log n)O(logn) for fff, whereas every one-way quantum protocol for fff receiving a classical proof (protocol of type QCMA) requires communication Ω(n/log⁡n)Ω(\sqrt n/\log n)Ω(n​/logn).
We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn_nn​: Alice gets as input a string x∈{0,1}n{\bf x}\in\{0, 1\}^nx∈{0,1}n, and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple ⟨i,j,b⟩\langle i,j,b \rangle⟨i,j,b⟩ such that the edge (i,j)(i,j)(i,j) belongs to the matching M and b=xi⊕xjb=x_i\oplus x_jb=xi​⊕xj​. We prove that the quantum one-way communication complexity of HMn_nn​ is O(log⁡n)O(\log n)O(logn), yet any randomized one-way protocol with bounded error must use Ω(n)\Omega({\sqrt{n}})Ω(n​) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM), and hence we provide the first exponential separation between quantum SM and randomized SM with public coins. For a Boolean decision version of HMn_nn​, we show that the quantum one-way communication complexity remains O(log⁡n)O(\log n)O(logn) and that the 0-error randomized one-way communication complexity is Ω(n)\Omega(n)Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(nlog⁡n3)\Omega(\sqrt[3]{n \log n})Ω(3nlogn​) bits of communication.
We give an exponential separation between one-way quantum and classical communication protocols for twopartial Boolean functions, both of which are variants of the Boolean Hidden Matching Problem of Bar-Yossef et al. Earlier such an exponential separation was known only for a relational version of the Hidden Matching Problem. Our proofs use the Fourier coefficients inequality of Kahn, Kalai, and Linial. We give a number of applications of this separation. In particular, in the bounded-storage model of cryptography we exhibita scheme that is secure against adversaries with a certain amount of classical storage, but insecure against adversaries with a similar (or even much smaller) amount of quantum storage; in the setting of privacy amplification, we show that there are strong extractors that yield a classically secure key, but are insecure against a quantum adversary.