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

ACM Symposium on Theory of Computing (STOC)

On quantum and probabilistic communication

Hartmut Klauck

Published May 1, 2000• 75 citations
Publisher

Abstract

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.

DOI
10.1145/335305.335396

Related papers

One-Way Communication Complexity and the Nečiporuk Lower Bound on Formula Size

Hartmut Klauck

In this paper the Nečiporuk method for proving lower bounds on the size of Boolean formulas is reformulated in terms of one-way communication complexity. We investigate the settings of probabilistic formulas, nondeterministic formulas, and quantum formulas. In all cases we can use results about one-way communication complexity to prove lower bounds on formula size. The main results regarding formula size are as follows: We show a polynomial size gap between probabilistic/quantum and deterministic formulas, a near-quadratic gap between the sizes of nondeterministic formulas with limited access to nondeterministic bits and nondeterministic formulas with access to slightly more such bits, and a near-quadratic lower bound on quantum formula size. Furthermore we give a polynomial separation between the sizes of quantum formulas with and without multiple read random inputs. The lower bound methods for quantum and probabilistic formulas employ a variant of the Nečiporuk bound in terms of the Vapnik–Chervonenkis dimension. To establish our lower bounds we show optimal separations between one-way and two-way protocols for limited nondeterministic and quantum communication complexity, and we show that zero-error quantum one-way communication complexity asymptotically equals deterministic one-way communication complexity for total functions.

SIAM Journal on Computing•Jan 1, 2007•31 citations

One-way communication complexity and the Neciporuk lower bound on formula size

Hartmut Klauck

In this paper the Neciporuk method for proving lower bounds on the size of Boolean formulae is reformulated in terms of one-way communication complexity. We investigate the scenarios of probabilistic formulae, nondeterministic formulae, and quantum formulae. In all cases we can use results about one-way communication complexity to prove lower bounds on formula size. In the latter two cases we newly develop the employed communication complexity bounds. The main results regarding formula size are as follows: A polynomial size gap between probabilistic/quantum and deterministic formulae. A near-quadratic size gap for nondeterministic formulae with limited access to nondeterministic bits. A near quadratic lower bound on quantum formula size, as well as a polynomial separation between the sizes of quantum formulae with and without multiple read random inputs. The methods for quantum and probabilistic formulae employ a variant of the Neciporuk bound in terms of the VC-dimension. Regarding communication complexity we give optimal separations between one-way and two-way protocols in the cases of limited nondeterministic and quantum communication, and we show that zero-error quantum one-way communication complexity asymptotically equals deterministic one-way communication complexity for total functions.

arXiv:cs/0111062•Nov 29, 2001•2 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

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

Quantum communication complexity of block-composed functions

Yaoyun Shi, Y.-F. Zhu

A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical ones for computing a {\em total} Boolean function in the two-party interactive model. Razborov's result ({\em Izvestiya: Mathematics}, 67(1):145--159, 2002) implies the conjectured negative answer for functions $F$ of the following form: $F(x, y)=f_n(x_1\cdot y_1, x_2\cdot y_2, ..., x_n\cdot y_n)$, where $f_n$ is a {\em symmetric} Boolean function on $n$ Boolean inputs, and $x_i$, $y_i$ are the $i$'th bit of $x$ and $y$, respectively. His proof critically depends on the symmetry of $f_n$. We develop a lower-bound method that does not require symmetry and prove the conjecture for a broader class of functions. Each of those functions $F$ is the ``block-composition'' of a ``building block'' $g_k : \{0, 1\}^k \times \{0, 1\}^k \rightarrow \{0, 1\}$, and an $f_n : \{0, 1\}^n \rightarrow \{0, 1\}$, such that $F(x, y) = f_n( g_k(x_1, y_1), g_k(x_2, y_2), ..., g_k(x_n, y_n) )$, where $x_i$ and $y_i$ are the $i$'th $k$-bit block of $x, y\in\{0, 1\}^{nk}$, respectively. We show that as long as g_k itself is "hard'' enough, its block-composition with an arbitrary f_n has polynomially related quantum and classical communication complexities. For example, when g_k is the Inner Product function with k=\Omega(\log n), the deterministic communication complexity of its block-composition with any f_n is asymptotically at most the quantum complexity to the power of 7.

arXiv:0710.0095•Quantum Information and Computation•May 1, 2009•67 citations

A lower bound on entanglement-assisted quantum communication complexity

Ashley Montanaro, Andreas Winter

We prove a general lower bound on the bounded-error entanglement-assisted quantum communication complexity of Boolean functions. The bound is based on the concept that any classical or quantum protocol to evaluate a function on distributed inputs can be turned into a quantum communication protocol. As an application of this bound, we give a very simple proof of the statement that almost all Boolean functions on n+n bits have linear communication complexity, even in the presence of unlimited entanglement.

arXiv:quant-ph/0610085•Oct 11, 2006•0 citations
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.
In this paper the Nečiporuk method for proving lower bounds on the size of Boolean formulas is reformulated in terms of one-way communication complexity. We investigate the settings of probabilistic formulas, nondeterministic formulas, and quantum formulas. In all cases we can use results about one-way communication complexity to prove lower bounds on formula size. The main results regarding formula size are as follows: We show a polynomial size gap between probabilistic/quantum and deterministic formulas, a near-quadratic gap between the sizes of nondeterministic formulas with limited access to nondeterministic bits and nondeterministic formulas with access to slightly more such bits, and a near-quadratic lower bound on quantum formula size. Furthermore we give a polynomial separation between the sizes of quantum formulas with and without multiple read random inputs. The lower bound methods for quantum and probabilistic formulas employ a variant of the Nečiporuk bound in terms of the Vapnik–Chervonenkis dimension. To establish our lower bounds we show optimal separations between one-way and two-way protocols for limited nondeterministic and quantum communication complexity, and we show that zero-error quantum one-way communication complexity asymptotically equals deterministic one-way communication complexity for total functions.
In this paper the Neciporuk method for proving lower bounds on the size of Boolean formulae is reformulated in terms of one-way communication complexity. We investigate the scenarios of probabilistic formulae, nondeterministic formulae, and quantum formulae. In all cases we can use results about one-way communication complexity to prove lower bounds on formula size. In the latter two cases we newly develop the employed communication complexity bounds. The main results regarding formula size are as follows: A polynomial size gap between probabilistic/quantum and deterministic formulae. A near-quadratic size gap for nondeterministic formulae with limited access to nondeterministic bits. A near quadratic lower bound on quantum formula size, as well as a polynomial separation between the sizes of quantum formulae with and without multiple read random inputs. The methods for quantum and probabilistic formulae employ a variant of the Neciporuk bound in terms of the VC-dimension. Regarding communication complexity we give optimal separations between one-way and two-way protocols in the cases of limited nondeterministic and quantum communication, and we show that zero-error quantum one-way communication complexity asymptotically equals deterministic one-way communication complexity for total functions.
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.
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).
A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical ones for computing a {\em total} Boolean function in the two-party interactive model. Razborov's result ({\em Izvestiya: Mathematics}, 67(1):145--159, 2002) implies the conjectured negative answer for functions FFF of the following form: F(x,y)=fn(x1⋅y1,x2⋅y2,...,xn⋅yn)F(x, y)=f_n(x_1\cdot y_1, x_2\cdot y_2, ..., x_n\cdot y_n)F(x,y)=fn​(x1​⋅y1​,x2​⋅y2​,...,xn​⋅yn​), where fnf_nfn​ is a {\em symmetric} Boolean function on nnn Boolean inputs, and xix_ixi​, yiy_iyi​ are the iii'th bit of xxx and yyy, respectively. His proof critically depends on the symmetry of fnf_nfn​. We develop a lower-bound method that does not require symmetry and prove the conjecture for a broader class of functions. Each of those functions FFF is the ``block-composition'' of a ``building block'' gk:{0,1}k×{0,1}k→{0,1}g_k : \{0, 1\}^k \times \{0, 1\}^k \rightarrow \{0, 1\}gk​:{0,1}k×{0,1}k→{0,1}, and an fn:{0,1}n→{0,1}f_n : \{0, 1\}^n \rightarrow \{0, 1\}fn​:{0,1}n→{0,1}, such that F(x,y)=fn(gk(x1,y1),gk(x2,y2),...,gk(xn,yn))F(x, y) = f_n( g_k(x_1, y_1), g_k(x_2, y_2), ..., g_k(x_n, y_n) )F(x,y)=fn​(gk​(x1​,y1​),gk​(x2​,y2​),...,gk​(xn​,yn​)), where xix_ixi​ and yiy_iyi​ are the iii'th kkk-bit block of x,y∈{0,1}nkx, y\in\{0, 1\}^{nk}x,y∈{0,1}nk, respectively. We show that as long as g_k itself is "hard'' enough, its block-composition with an arbitrary f_n has polynomially related quantum and classical communication complexities. For example, when g_k is the Inner Product function with k=\Omega(\log n), the deterministic communication complexity of its block-composition with any f_n is asymptotically at most the quantum complexity to the power of 7.
We prove a general lower bound on the bounded-error entanglement-assisted quantum communication complexity of Boolean functions. The bound is based on the concept that any classical or quantum protocol to evaluate a function on distributed inputs can be turned into a quantum communication protocol. As an application of this bound, we give a very simple proof of the statement that almost all Boolean functions on n+n bits have linear communication complexity, even in the presence of unlimited entanglement.