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

Two Results about Quantum Messages

Hartmut Klauck, Supartha Podder

Published Feb 18, 2014• 0 citations
arXivHTMLPDF

Abstract

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)$.

DOI
10.48550/arxiv.1402.4312

Related papers

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

On quantum and probabilistic communication

Hartmut Klauck

We investigate the power of quantum communication protocols compared to classical probabilistic protocols.In our first result we describe a total Boolean function that has a quantum Las Vegas protocol communicating at most O(N 1°/11+~) qubits for all e > 0, while any classical probabilistic protocol (with bounded error) needs ~(N/log N) bits.Then we investigate quantum one-way communication complexity.First we show that the VC-dimension lower bound on one-way probabilistic communication of [26] holds for quantum protocols, too.Then we prove that for oneway protocols computing total functions quantum Las Vegas communication is asymptotically as efficient as exact quantum communication, which is exactly as efficient as deterministic communication.We describe applications of the lower bounds for one-way communication complexity to quantum finite automata and quantum formulae.

ACM Symposium on Theory of Computing (STOC)•May 1, 2000•75 citations

Quantum Versus Classical Proofs and Advice

Scott Aaronson, Greg Kuperberg

This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA=QCMA. We prove three results about this question. First, we give a "quantum oracle separation" between QMA and QCMA. More concretely, we show that any quantum algorithm needs $Ω(\sqrt{2^n/(m+1)})$ queries to find an $n$-qubit "marked state" $\lvertψ\rangle$, even if given an $m$-bit classical description of $\lvertψ\rangle$ together with a quantum black box that recognizes $\lvertψ\rangle$. Second, we give an explicit QCMA protocol that nearly achieves this lower bound. Third, we show that, in the one previously-known case where quantum proofs seemed to provide an exponential advantage, classical proofs are basically just as powerful. In particular, Watrous gave a QMA protocol for verifying non-membership in finite groups. Under plausible group-theoretic assumptions, we give a QCMA protocol for the same problem. Even with no assumptions, our protocol makes only polynomially many queries to the group oracle. We end with some conjectures about quantum versus classical oracles, and about the possibility of a classical oracle separation between QMA and QCMA.

arXiv:quant-ph/0604056•Electronic colloquium on computational complexity•Apr 10, 2006•4 citations

Quantum-Classical Equivalence for AND-Functions

Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay +2 more

A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form $$ F(x,y) = f(x_1 \land y_1, \ldots, x_n \land y_n), $$ when the outer function $f$ is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all AND-functions has remained open and has been posed by several authors. In this work, we settle this problem in a strong way. We show that for every Boolean function $f$, the bounded-error quantum and classical deterministic communication complexities of the function $f \circ \mathrm{AND}_2$ are polynomially related, up to polylogarithmic factors in $n$. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of $f$. Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions.

cs.CCCross-listedarXiv:2606.03249•Jun 3, 2026•0 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

Limitations of Quantum Advice and One-Way Communication

Scott Aaronson

Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that $\mathsf{BQP/qpoly}\subseteq\mathsf{PP/poly}$, where $\mathsf{BQP/qpoly}$ is the class of problems solvable in quantum polynomial time, given a polynomial-size “quantum advice state” that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which $\mathsf{NP}\not \subset \mathsf{BQP/qpoly}$. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols. A preliminary version of this paper appeared in the 2004 Conference on Computational Complexity (CCC).

arXiv:quant-ph/0402095•Theory of Computing•Jan 1, 2005•140 citations
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 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.
We investigate the power of quantum communication protocols compared to classical probabilistic protocols.In our first result we describe a total Boolean function that has a quantum Las Vegas protocol communicating at most O(N 1°/11+~) qubits for all e > 0, while any classical probabilistic protocol (with bounded error) needs ~(N/log N) bits.Then we investigate quantum one-way communication complexity.First we show that the VC-dimension lower bound on one-way probabilistic communication of [26] holds for quantum protocols, too.Then we prove that for oneway protocols computing total functions quantum Las Vegas communication is asymptotically as efficient as exact quantum communication, which is exactly as efficient as deterministic communication.We describe applications of the lower bounds for one-way communication complexity to quantum finite automata and quantum formulae.
This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA=QCMA. We prove three results about this question. First, we give a "quantum oracle separation" between QMA and QCMA. More concretely, we show that any quantum algorithm needs Ω(2n/(m+1))Ω(\sqrt{2^n/(m+1)})Ω(2n/(m+1)​) queries to find an nnn-qubit "marked state" ∣ψ⟩\lvertψ\rangle∣ψ⟩, even if given an mmm-bit classical description of ∣ψ⟩\lvertψ\rangle∣ψ⟩ together with a quantum black box that recognizes ∣ψ⟩\lvertψ\rangle∣ψ⟩. Second, we give an explicit QCMA protocol that nearly achieves this lower bound. Third, we show that, in the one previously-known case where quantum proofs seemed to provide an exponential advantage, classical proofs are basically just as powerful. In particular, Watrous gave a QMA protocol for verifying non-membership in finite groups. Under plausible group-theoretic assumptions, we give a QCMA protocol for the same problem. Even with no assumptions, our protocol makes only polynomially many queries to the group oracle. We end with some conjectures about quantum versus classical oracles, and about the possibility of a classical oracle separation between QMA and QCMA.
A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form F(x,y)=f(x1∧y1,…,xn∧yn), F(x,y) = f(x_1 \land y_1, \ldots, x_n \land y_n), F(x,y)=f(x1​∧y1​,…,xn​∧yn​), when the outer function fff is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all AND-functions has remained open and has been posed by several authors. In this work, we settle this problem in a strong way. We show that for every Boolean function fff, the bounded-error quantum and classical deterministic communication complexities of the function f∘AND2f \circ \mathrm{AND}_2f∘AND2​ are polynomially related, up to polylogarithmic factors in nnn. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of fff. Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions.
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.
Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly⊆PP/poly\mathsf{BQP/qpoly}\subseteq\mathsf{PP/poly}BQP/qpoly⊆PP/poly, where BQP/qpoly\mathsf{BQP/qpoly}BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size “quantum advice state” that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP⊄BQP/qpoly\mathsf{NP}\not \subset \mathsf{BQP/qpoly}NP⊂BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols. A preliminary version of this paper appeared in the 2004 Conference on Computational Complexity (CCC).