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:2310.02406

One Clean Qubit Suffices for Quantum Communication Advantage

Srinivasan Arunachalam, Uma Girish, Noam Lifshitz

Published Oct 3, 2023• 0 citations
arXivHTMLPDF

Abstract

We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost $O(\log N)$ in this model, however, every interactive randomized protocol has cost $Ω(\sqrt{N})$, settling a conjecture of Klauck and Lim. In contrast, all prior quantum versus classical communication separations required at least $Ω(\log N)$ clean qubits. The function demonstrating our separation also has an efficient protocol in the quantum-simultaneous-with-entanglement model of cost $O(\log N )$. We thus recover the state-of-the-art separations between quantum and classical communication complexity. Our proof is based on a recent hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and Minzer, in conjunction with tools from the representation theory of compact Lie groups.

DOI
10.48550/arxiv.2310.02406

Related papers

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•0 citations

The Power of One Clean Qubit in Communication Complexity

Hartmut Klauck, Debbie Lim

We study quantum communication protocols, in which the players' storage starts out in a state where one qubit is in a pure state, and all other qubits are totally mixed (i.e. in a random state), and no other storage is available (for messages or internal computations). This restriction on the available quantum memory has been studied extensively in the model of quantum circuits, and it is known that classically simulating quantum circuits operating on such memory is hard when the additive error of the simulation is exponentially small (in the input length), under the assumption that the polynomial hierarchy does not collapse. We study this setting in communication complexity. The goal is to consider larger additive error for simulation-hardness results, and to not use unproven assumptions. We define a complexity measure for this model that takes into account that standard error reduction techniques do not work here. We define a clocked and a semi-unclocked model, and describe efficient simulations between those. We characterize a one-way communication version of the model in terms of weakly unbounded error communication complexity. Our main result is that there is a quantum protocol using one clean qubit only and using O(log n) qubits of communication, such that any classical protocol simulating the acceptance behaviour of the quantum protocol within additive error 1/poly(n) needs communication Ω(n). We also describe a candidate problem, for which an exponential gap between the one-clean-qubit communication complexity and the randomized communication complexity is likely to hold, and hence a classical simulation of the one-clean-qubit model within constant additive error might be hard in communication complexity. We describe a geometrical conjecture that implies the lower bound.

arXiv:1807.07762•Leibniz international proceedings in informatics•Jul 20, 2018•2 citations

Optimal and Verifiable Quantum Advantages in Communication Complexity

Ryan Anselm, Michelle Ding, Dar Gilboa +1 more

We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an $n$-qubit quantum one-way protocol, whereas every randomized two-way protocol requires $Ω(2^n)$ bits of communication. We then introduce a variant of this problem whose solutions can be verified in polynomial time. This variant also admits an $n$-qubit quantum one-way protocol, while every randomized one-way protocol requires $Ω(2^n)$ bits of communication. We also construct a family of efficiently verifiable total search problems achieving an $n$ versus $Ω_d(n^d)$ separation between quantum one-way and randomized one-way communication for every fixed $d \ge 2$. In the quantum protocol, Alice prepares her message using a single unitary from the $d$th level of the Clifford hierarchy, and Bob performs a Clifford measurement. This separation is asymptotically optimal under this restriction on Alice's message. For $d = 2$, Alice's message is a stabilizer state and Bob's measurement is Clifford, so the protocol uses no magic, yet achieves an optimal quadratic quantum advantage. Finally, we discuss how these separations can be adapted to near-term quantum advantage experiments in which the demonstrated advantage is both unconditional and efficiently verifiable.

quant-pharXiv:2610.05585•Oct 6, 2026•0 citations

Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations

Harumichi Nishimura

Private simultaneous quantum messages (PSQM) provide a minimal model of noninteractive secure multiparty quantum computation, yet their communication complexity for concrete functions remains poorly understood. We show that familiar total functions already exhibit both genuine quantum advantages and strong structural limitations. For three-party equality on $n$-bit inputs, which determines whether the players' $n$-bit strings are identical, we construct an entanglement-assisted protocol with asymptotic communication $(1.633\ldots)n$ qubits, whereas every perfectly correct protocol without prior entanglement requires at least $3n$ qubits. For three-bit majority, one shared GHZ state and one transmitted qubit per player suffice for perfect correctness and perfect privacy, reducing the communication from the optimal classical cost of six bits to three qubits. Three-bit AND behaves differently. No perfectly correct and perfectly private protocol exists when the players share an arbitrary three-qubit state, apply arbitrary local unitary encodings, and transmit one qubit each. However, increasing the local dimension overcomes this obstruction: one shared three-qutrit GHZ state and one transmitted qutrit per player yield a one-shot protocol with total communication $3\log_2 3$. Together with the six-bit classical lower bound, this gives a strict quantum communication advantage. More generally, for every $k\geq 3$, we construct a perfectly correct and perfectly private one-shot protocol for $k$-bit AND using one qudit of dimension at most $k$ per player, and hence at most $k\log_2 k$ qubits in total.

quant-pharXiv:2610.23090•Oct 19, 2026•0 citations

Quantum versus Randomized Communication Complexity, with Efficient Players

Uma Girish, Ran Raz, Avishay Tal

We study a new type of separations between quantum and classical communication complexity, separations that are obtained using quantum protocols where all parties are efficient , in the sense that they can be implemented by small quantum circuits, with oracle access to their inputs. Our main result qualitatively matches the strongest known separation between quantum and classical communication complexity Gavinsky (2016) and is obtained using a quantum protocol where all parties are efficient. More precisely, we give an explicit partial Boolean function f over inputs of length N , such that: f can be computed by a simultaneous-message quantum protocol with communication complexity polylog( N ) (where at the beginning of the protocol Alice and Bob also have polylog( N ) entangled EPR pairs). Any classical randomized protocol for f , with any number of rounds, has communication complexity at least \(\tilde{\Omega}\left(N^{1/4}\right)\) . All parties in the quantum protocol of Item (1) (Alice, Bob and the referee) can be implemented by quantum circuits of size polylog( N ) (where Alice and Bob have oracle access to their inputs). Items (1), (2) qualitatively match the strongest known separation between quantum and classical communication complexity, proved by Gavinsky (2016). Item (3) is new. (Our result is incomparable to the one of Gavinsky. While he obtained a quantitatively better lower bound of \(\Omega\left(N^{1/2}\right)\) in the classical case, the referee in his quantum protocol is inefficient). Exponential separations of quantum and classical communication complexity have been studied in numerous previous works, but to the best of our knowledge the efficiency of the parties in the quantum protocol has not been addressed, and in most previous separations the quantum parties seem to be inefficient. The only separations that we know of that have efficient quantum parties are the recent separations that are based on lifting Göös et al. (2017), Chattopadhyay et al. (2019a). However, these separations seem to require quantum protocols with at least two rounds of communication, so they imply a separation of two-way quantum and classical communication complexity, but they do not give the stronger separations of simultaneous-message quantum communication complexity vs. two-way classical communication complexity (or even one-way quantum communication complexity vs. two-way classical communication complexity). Our proof technique is completely new, in the context of communication complexity, and is based on techniques from Raz & Tal (2019). Our function f is based on a lift of the forrelation problem, using xor as a gadget.

arXiv:1911.02218•Computational Complexity•Oct 28, 2022•8 citations

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

Ryan Anselm, Srijita Kundu, Olivier Lalonde +1 more

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.

quant-pharXiv:2610.02099•Oct 2, 2026•0 citations
We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost O(log⁡N)O(\log N)O(logN) in this model, however, every interactive randomized protocol has cost Ω(N)Ω(\sqrt{N})Ω(N​), settling a conjecture of Klauck and Lim. In contrast, all prior quantum versus classical communication separations required at least Ω(log⁡N)Ω(\log N)Ω(logN) clean qubits. The function demonstrating our separation also has an efficient protocol in the quantum-simultaneous-with-entanglement model of cost O(log⁡N)O(\log N )O(logN). We thus recover the state-of-the-art separations between quantum and classical communication complexity. Our proof is based on a recent hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and Minzer, in conjunction with tools from the representation theory of compact Lie groups.
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 study quantum communication protocols, in which the players' storage starts out in a state where one qubit is in a pure state, and all other qubits are totally mixed (i.e. in a random state), and no other storage is available (for messages or internal computations). This restriction on the available quantum memory has been studied extensively in the model of quantum circuits, and it is known that classically simulating quantum circuits operating on such memory is hard when the additive error of the simulation is exponentially small (in the input length), under the assumption that the polynomial hierarchy does not collapse. We study this setting in communication complexity. The goal is to consider larger additive error for simulation-hardness results, and to not use unproven assumptions. We define a complexity measure for this model that takes into account that standard error reduction techniques do not work here. We define a clocked and a semi-unclocked model, and describe efficient simulations between those. We characterize a one-way communication version of the model in terms of weakly unbounded error communication complexity. Our main result is that there is a quantum protocol using one clean qubit only and using O(log n) qubits of communication, such that any classical protocol simulating the acceptance behaviour of the quantum protocol within additive error 1/poly(n) needs communication Ω(n). We also describe a candidate problem, for which an exponential gap between the one-clean-qubit communication complexity and the randomized communication complexity is likely to hold, and hence a classical simulation of the one-clean-qubit model within constant additive error might be hard in communication complexity. We describe a geometrical conjecture that implies the lower bound.
We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an nnn-qubit quantum one-way protocol, whereas every randomized two-way protocol requires Ω(2n)Ω(2^n)Ω(2n) bits of communication. We then introduce a variant of this problem whose solutions can be verified in polynomial time. This variant also admits an nnn-qubit quantum one-way protocol, while every randomized one-way protocol requires Ω(2n)Ω(2^n)Ω(2n) bits of communication. We also construct a family of efficiently verifiable total search problems achieving an nnn versus Ωd(nd)Ω_d(n^d)Ωd​(nd) separation between quantum one-way and randomized one-way communication for every fixed d≥2d \ge 2d≥2. In the quantum protocol, Alice prepares her message using a single unitary from the dddth level of the Clifford hierarchy, and Bob performs a Clifford measurement. This separation is asymptotically optimal under this restriction on Alice's message. For d=2d = 2d=2, Alice's message is a stabilizer state and Bob's measurement is Clifford, so the protocol uses no magic, yet achieves an optimal quadratic quantum advantage. Finally, we discuss how these separations can be adapted to near-term quantum advantage experiments in which the demonstrated advantage is both unconditional and efficiently verifiable.
Private simultaneous quantum messages (PSQM) provide a minimal model of noninteractive secure multiparty quantum computation, yet their communication complexity for concrete functions remains poorly understood. We show that familiar total functions already exhibit both genuine quantum advantages and strong structural limitations. For three-party equality on nnn-bit inputs, which determines whether the players' nnn-bit strings are identical, we construct an entanglement-assisted protocol with asymptotic communication (1.633…)n(1.633\ldots)n(1.633…)n qubits, whereas every perfectly correct protocol without prior entanglement requires at least 3n3n3n qubits. For three-bit majority, one shared GHZ state and one transmitted qubit per player suffice for perfect correctness and perfect privacy, reducing the communication from the optimal classical cost of six bits to three qubits. Three-bit AND behaves differently. No perfectly correct and perfectly private protocol exists when the players share an arbitrary three-qubit state, apply arbitrary local unitary encodings, and transmit one qubit each. However, increasing the local dimension overcomes this obstruction: one shared three-qutrit GHZ state and one transmitted qutrit per player yield a one-shot protocol with total communication 3log⁡233\log_2 33log2​3. Together with the six-bit classical lower bound, this gives a strict quantum communication advantage. More generally, for every k≥3k\geq 3k≥3, we construct a perfectly correct and perfectly private one-shot protocol for kkk-bit AND using one qudit of dimension at most kkk per player, and hence at most klog⁡2kk\log_2 kklog2​k qubits in total.
We study a new type of separations between quantum and classical communication complexity, separations that are obtained using quantum protocols where all parties are efficient , in the sense that they can be implemented by small quantum circuits, with oracle access to their inputs. Our main result qualitatively matches the strongest known separation between quantum and classical communication complexity Gavinsky (2016) and is obtained using a quantum protocol where all parties are efficient. More precisely, we give an explicit partial Boolean function f over inputs of length N , such that: f can be computed by a simultaneous-message quantum protocol with communication complexity polylog( N ) (where at the beginning of the protocol Alice and Bob also have polylog( N ) entangled EPR pairs). Any classical randomized protocol for f , with any number of rounds, has communication complexity at least Ω~(N1/4)\tilde{\Omega}\left(N^{1/4}\right)Ω~(N1/4) . All parties in the quantum protocol of Item (1) (Alice, Bob and the referee) can be implemented by quantum circuits of size polylog( N ) (where Alice and Bob have oracle access to their inputs). Items (1), (2) qualitatively match the strongest known separation between quantum and classical communication complexity, proved by Gavinsky (2016). Item (3) is new. (Our result is incomparable to the one of Gavinsky. While he obtained a quantitatively better lower bound of Ω(N1/2)\Omega\left(N^{1/2}\right)Ω(N1/2) in the classical case, the referee in his quantum protocol is inefficient). Exponential separations of quantum and classical communication complexity have been studied in numerous previous works, but to the best of our knowledge the efficiency of the parties in the quantum protocol has not been addressed, and in most previous separations the quantum parties seem to be inefficient. The only separations that we know of that have efficient quantum parties are the recent separations that are based on lifting Göös et al. (2017), Chattopadhyay et al. (2019a). However, these separations seem to require quantum protocols with at least two rounds of communication, so they imply a separation of two-way quantum and classical communication complexity, but they do not give the stronger separations of simultaneous-message quantum communication complexity vs. two-way classical communication complexity (or even one-way quantum communication complexity vs. two-way classical communication complexity). Our proof technique is completely new, in the context of communication complexity, and is based on techniques from Raz & Tal (2019). Our function f is based on a lift of the forrelation problem, using xor as a gadget.
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.