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

Mathematical Structures in Computer Science

Quantum multiparty communication complexity and circuit lower bounds

Iordanis Kerenidis

Published Feb 1, 2009• 6 citations
Publisher

Abstract

We define a quantum model for multiparty communication complexity and prove a simulation theorem between the classical and quantum models. As a result, we show that if the quantum k-party communication complexity of a function f is Ω(n/2k), its classical k-party communication is Ω(n/2k/2). Finding such an f would allow us to prove strong classical lower bounds for k ≥ log n players and make progress towards solving a major open question about symmetric circuits.

DOI
10.1017/s0960129508007263

Related papers

Quantum multiparty communication complexity and circuit lower bounds

Iordanis Kerenidis

We define a quantum model for multiparty communication complexity and prove a simulation theorem between the classical and quantum models. As a result of our simulation, we show that if the quantum k-party communication complexity of a function f is $Ω(n/2^k)$, then its classical k-party communication is $Ω(n/2^{k/2})$. Finding such an f would allow us to prove strong classical lower bounds for (k>log n) players and hence resolve a main open question about symmetric circuits. Furthermore, we prove that for the Generalized Inner Product (GIP) function, the quantum model is exponentially more efficient than the classical one. This provides the first exponential separation for a total function between any quantum and public coin randomized communication model.

arXiv:quant-ph/0504087•Apr 12, 2005•1 citation

Lower Bounds on Quantum Multiparty Communication Complexity

Troy Lee, Gideon Schechtman, Adi Shraibman

A major open question in communication complexity is if randomized and quantum communication are polynomially related for all total functions. So far, no gap larger than a power of two is known, despite significant efforts. We examine this question in the number-on-the-forehead model of multiparty communication complexity. We show that essentially all lower bounds known on randomized complexity in this model also hold for quantum communication. This includes bounds of size Omega(n/2k) for the k-party complexity of explicit functions, bounds for the generalized inner product function, and recent work on the multiparty complexity of disjointness. To the best of our knowledge, these are the first lower bounds of any kind on quantum communication in the general number-on-the-forehead model. We show this result in the following way. In the two-party case, there is a lower bound on quantum communication complexity in terms of a norm gamma2, which is known to subsume nearly all other techniques in the literature. For randomized complexity there is another natural bound in terms of a different norm mu which is also one of the strongest techniques available. A deep theorem in functional analysis, Grothendieck's inequality, implies that gamma2and mu are equivalent up to a constant factor. This connection is one of the major obstacles to showing a larger gap between randomized and quantum communication complexity in the two-party case. The lower bound technique in terms of the norm mu was recently extended to the multiparty number-on-the-forehead model. Here we show how the gamma2norm can be also extended to lower bound quantum multiparty complexity. Surprisingly, even in this general setting the two lower bounds, on quantum and classical communication, are still very closely related. This implies that separating quantum and classical communication in this setting will require the development of new techniques. The relation between these extensions of mu and gamma2is proved by a multi-dimensional version of Grothendieck's inequality.

IEEE Conference on Computational Complexity (CCC)•Jul 1, 2009•21 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

Communication complexity lower bounds by polynomials

Harry Buhrman, Ronald de Wolf

The quantum version of communication complexity allows the two communicating parties to exchange qubits and/or to make use of prior entanglement (shared EPR-pairs). Some lower bound techniques are available for qubit communication complexity, but except for the inner product function, no bounds are known for the model with unlimited prior entanglement. We show that the "log rank" lower bound extends to the strongest variant of quantum communication complexity (qubit communication+unlimited prior entanglement). By relating the rank of the communication matrix to properties of polynomials, we are able to derive some strong bounds for exact protocols. In particular, we prove both the "log rank conjecture" and the polynomial equivalence of quantum and classical communication complexity for various classes of functions. We also derive some weaker bounds for bounded-error quantum protocols.

arXiv:cs/9910010•IEEE Conference on Computational Complexity (CCC)•Nov 13, 2002•127 citations

Multiparty Communication Complexity of Disjointness

Arkadev Chattopadhyay, Anil Ada

We obtain a lower bound of n^Omega(1) on the k-party randomized communication complexity of the Disjointness function in the `Number on the Forehead' model of multiparty communication when k is a constant. For k=o(loglog n), the bounds remain super-polylogarithmic i.e. (log n)^omega(1). The previous best lower bound for three players until recently was Omega(log n). Our bound separates the communication complexity classes NP^{CC}_k and BPP^{CC}_k for k=o(loglog n). Furthermore, by the results of Beame, Pitassi and Segerlind \cite{BPS07}, our bound implies proof size lower bounds for tree-like, degree k-1 threshold systems and superpolynomial size lower bounds for Lovasz-Schrijver proofs. Sherstov \cite{She07b} recently developed a novel technique to obtain lower bounds on two-party communication using the approximate polynomial degree of boolean functions. We obtain our results by extending his technique to the multi-party setting using ideas from Chattopadhyay \cite{Cha07}. A similar bound for Disjointness has been recently and independently obtained by Lee and Shraibman.

arXiv:0801.3624•Jan 23, 2008•63 citations

New bounds on the classical and quantum communication complexity of some graph properties

Gábor Ivanyos, Hartmut Klauck, Troy Lee +2 more

We study the communication complexity of a number of graph properties where the edges of the graph $G$ are distributed between Alice and Bob (i.e., each receives some of the edges as input). Our main results are: * An Omega(n) lower bound on the quantum communication complexity of deciding whether an n-vertex graph G is connected, nearly matching the trivial classical upper bound of O(n log n) bits of communication. * A deterministic upper bound of O(n^{3/2}log n) bits for deciding if a bipartite graph contains a perfect matching, and a quantum lower bound of Omega(n) for this problem. * A Theta(n^2) bound for the randomized communication complexity of deciding if a graph has an Eulerian tour, and a Theta(n^{3/2}) bound for the quantum communication complexity of this problem. The first two quantum lower bounds are obtained by exhibiting a reduction from the n-bit Inner Product problem to these graph problems, which solves an open question of Babai, Frankl and Simon. The third quantum lower bound comes from recent results about the quantum communication complexity of composed functions. We also obtain essentially tight bounds for the quantum communication complexity of a few other problems, such as deciding if G is triangle-free, or if G is bipartite, as well as computing the determinant of a distributed matrix.

arXiv:1204.4596•Leibniz international proceedings in informatics•Jan 1, 2012•11 citations
We define a quantum model for multiparty communication complexity and prove a simulation theorem between the classical and quantum models. As a result, we show that if the quantum k-party communication complexity of a function f is Ω(n/2k), its classical k-party communication is Ω(n/2k/2). Finding such an f would allow us to prove strong classical lower bounds for k ≥ log n players and make progress towards solving a major open question about symmetric circuits.
We define a quantum model for multiparty communication complexity and prove a simulation theorem between the classical and quantum models. As a result of our simulation, we show that if the quantum k-party communication complexity of a function f is Ω(n/2k)Ω(n/2^k)Ω(n/2k), then its classical k-party communication is Ω(n/2k/2)Ω(n/2^{k/2})Ω(n/2k/2). Finding such an f would allow us to prove strong classical lower bounds for (k>log n) players and hence resolve a main open question about symmetric circuits. Furthermore, we prove that for the Generalized Inner Product (GIP) function, the quantum model is exponentially more efficient than the classical one. This provides the first exponential separation for a total function between any quantum and public coin randomized communication model.
A major open question in communication complexity is if randomized and quantum communication are polynomially related for all total functions. So far, no gap larger than a power of two is known, despite significant efforts. We examine this question in the number-on-the-forehead model of multiparty communication complexity. We show that essentially all lower bounds known on randomized complexity in this model also hold for quantum communication. This includes bounds of size Omega(n/2k) for the k-party complexity of explicit functions, bounds for the generalized inner product function, and recent work on the multiparty complexity of disjointness. To the best of our knowledge, these are the first lower bounds of any kind on quantum communication in the general number-on-the-forehead model. We show this result in the following way. In the two-party case, there is a lower bound on quantum communication complexity in terms of a norm gamma2, which is known to subsume nearly all other techniques in the literature. For randomized complexity there is another natural bound in terms of a different norm mu which is also one of the strongest techniques available. A deep theorem in functional analysis, Grothendieck's inequality, implies that gamma2and mu are equivalent up to a constant factor. This connection is one of the major obstacles to showing a larger gap between randomized and quantum communication complexity in the two-party case. The lower bound technique in terms of the norm mu was recently extended to the multiparty number-on-the-forehead model. Here we show how the gamma2norm can be also extended to lower bound quantum multiparty complexity. Surprisingly, even in this general setting the two lower bounds, on quantum and classical communication, are still very closely related. This implies that separating quantum and classical communication in this setting will require the development of new techniques. The relation between these extensions of mu and gamma2is proved by a multi-dimensional version of Grothendieck's inequality.
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.
The quantum version of communication complexity allows the two communicating parties to exchange qubits and/or to make use of prior entanglement (shared EPR-pairs). Some lower bound techniques are available for qubit communication complexity, but except for the inner product function, no bounds are known for the model with unlimited prior entanglement. We show that the "log rank" lower bound extends to the strongest variant of quantum communication complexity (qubit communication+unlimited prior entanglement). By relating the rank of the communication matrix to properties of polynomials, we are able to derive some strong bounds for exact protocols. In particular, we prove both the "log rank conjecture" and the polynomial equivalence of quantum and classical communication complexity for various classes of functions. We also derive some weaker bounds for bounded-error quantum protocols.
We obtain a lower bound of n^Omega(1) on the k-party randomized communication complexity of the Disjointness function in the `Number on the Forehead' model of multiparty communication when k is a constant. For k=o(loglog n), the bounds remain super-polylogarithmic i.e. (log n)^omega(1). The previous best lower bound for three players until recently was Omega(log n). Our bound separates the communication complexity classes NP^{CC}_k and BPP^{CC}_k for k=o(loglog n). Furthermore, by the results of Beame, Pitassi and Segerlind \cite{BPS07}, our bound implies proof size lower bounds for tree-like, degree k-1 threshold systems and superpolynomial size lower bounds for Lovasz-Schrijver proofs. Sherstov \cite{She07b} recently developed a novel technique to obtain lower bounds on two-party communication using the approximate polynomial degree of boolean functions. We obtain our results by extending his technique to the multi-party setting using ideas from Chattopadhyay \cite{Cha07}. A similar bound for Disjointness has been recently and independently obtained by Lee and Shraibman.
We study the communication complexity of a number of graph properties where the edges of the graph GGG are distributed between Alice and Bob (i.e., each receives some of the edges as input). Our main results are: * An Omega(n) lower bound on the quantum communication complexity of deciding whether an n-vertex graph G is connected, nearly matching the trivial classical upper bound of O(n log n) bits of communication. * A deterministic upper bound of O(n^{3/2}log n) bits for deciding if a bipartite graph contains a perfect matching, and a quantum lower bound of Omega(n) for this problem. * A Theta(n^2) bound for the randomized communication complexity of deciding if a graph has an Eulerian tour, and a Theta(n^{3/2}) bound for the quantum communication complexity of this problem. The first two quantum lower bounds are obtained by exhibiting a reduction from the n-bit Inner Product problem to these graph problems, which solves an open question of Babai, Frankl and Simon. The third quantum lower bound comes from recent results about the quantum communication complexity of composed functions. We also obtain essentially tight bounds for the quantum communication complexity of a few other problems, such as deciding if G is triangle-free, or if G is bipartite, as well as computing the determinant of a distributed matrix.