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:2006.14870 · Quantum Information and Computation

Quantum communication complexity of distribution testing

Aleksandrs Belovs, Arturo Castellanos, François Le Gall, Guillaume Malod, Alexander A. Sherstov

Published Oct 7, 2021• 1 citation
arXivHTMLPDF

Abstract

The classical communication complexity of testing closeness of discrete distributions has recently been studied by Andoni, Malkin and Nosatzki (ICALP'19). In this problem, two players each receive $t$ samples from one distribution over $[n]$, and the goal is to decide whether their two distributions are equal, or are $\epsilon$-far apart in the $l_1$-distance. In the present paper we show that the quantum communication complexity of this problem is $\tilde{O}(n/(t\epsilon^2))$ qubits when the distributions have low $l_2$-norm, which gives a quadratic improvement over the classical communication complexity obtained by Andoni, Malkin and Nosatzki. We also obtain a matching lower bound by using the pattern matrix method. Let us stress that the samples received by each of the parties are classical, and it is only communication between them that is quantum. Our results thus give one setting where quantum protocols overcome classical protocols for a testing problem with purely classical samples.

DOI
10.26421/qic21.15-16-1

Related papers

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

Quantum Algorithms for Testing Properties of Distributions

Sergey B. Bravyi, Aram W. Harrow, Avinatan Hassidim

Suppose one has access to oracles generating samples from two unknown probability distributions p and q on some N-element set. How many samples does one need to test whether the two distributions are close or far from each other in the L1-norm? This and related questions have been extensively studied during the last years in the field of property testing. In the present paper we study quantum algorithms for testing properties of distributions. It is shown that the L1-distance ∥p-q∥1can be estimated with a constant precision using only O(N1/2) queries in the quantum settings, whereas classical computers need Ω(N1-o(1)) queries. We also describe quantum algorithms for testing uniformity and orthogonality with query complexity O(N1/3). The classical query complexity of these problems is known to be Ω(N1/2).

arXiv:0907.3920•IEEE Transactions on Information Theory•May 25, 2011•44 citations

Quantum Communication Complexity of Distributed Set Joins

Stacey Jeffery, François Le Gall

Computing set joins of two inputs is a common task in database theory. Recently, Van Gucht, Williams, Woodruff and Zhang [PODS 2015] considered the complexity of such problems in the natural model of (classical) two-party communication complexity and obtained tight bounds for the complexity of several important distributed set joins. In this paper we initiate the study of the *quantum* communication complexity of distributed set joins. We design a quantum protocol for distributed Boolean matrix multiplication, which corresponds to computing the composition join of two databases, showing that the product of two $n\times n$ Boolean matrices, each owned by one of two respective parties, can be computed with $\widetilde{O}(\sqrt{n}\ell^{3/4})$ qubits of communication, where $\ell$ denotes the number of non-zero entries of the product. Since Van Gucht et al. showed that the classical communication complexity of this problem is $\widetildeΘ(n\sqrt{\ell})$, our quantum algorithm outperforms classical protocols whenever the output matrix is sparse. We also show a quantum lower bound and a matching classical upper bound on the communication complexity of distributed matrix multiplication over $\mathbb{F}_2$. Besides their applications to database theory, the communication complexity of set joins is interesting due to its connections to direct product theorems in communication complexity. In this work we also introduce a notion of *all-pairs* product theorem, and relate this notion to standard direct product theorems in communication complexity.

arXiv:1608.06617•Leibniz international proceedings in informatics•Jan 1, 2016•0 citations

The communication complexity of distributed estimation

Parikshit Gopalan, Raghu Meka, Prasad Raghavendra +2 more

We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions $p$ and $q$ over domains $X$ and $Y$, respectively. Their goal is to estimate \[ \mathbb{E}_{x \sim p,\, y \sim q}[f(x, y)] \] to within additive error $\varepsilon$ for a bounded function $f$, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of $f$ and the error parameter $\varepsilon$. The random sampling approach -- estimating the mean by averaging $f$ over $O(1/\varepsilon^2)$ random samples -- requires $O(R(f)/\varepsilon^2)$ total communication, where $R(f)$ is the randomized communication complexity of $f$. We design a new debiasing protocol which improves the dependence on $1/\varepsilon$ to be linear instead of quadratic. Additionally we show better upper bounds for several special classes of functions, including the Equality and Greater-than functions. We introduce lower bound techniques based on spectral methods and discrepancy, and show the optimality of many of our protocols: the debiasing protocol is tight for general functions, and that our protocols for the equality and greater-than functions are also optimal. Furthermore, we show that among full-rank Boolean functions, Equality is essentially the easiest.

arXiv:2511.21015•Nov 26, 2025•0 citations

Exponential separation of quantum and classical communication complexity

Ran Raz

Communication complexity has become a central completity model.In that model, we count the amount of communication bits needed between two parties in order to solve certain computational problems.We show that for certain communication complezity problems quantum communication protocols are exponentially faster than classical ores.More explicitly, we give an example for a communication complexity relation (0~ promise problem) P such that: 1) The quantum communication complexity of P is O(log m). 2) The classical probabilistic communication complexity of P is Q(m'l'/ logm).(where m is the length of the inputs).This gives an ezponential gap between quantum communication complexity and classical probabilistic communication complexity.Only a quadratic gap was previously known.Our problem P is of geometrical nature, and is a finite precision variation of the following problem: Player I gets as input a unit vector z E R" and two orthogonal subspaces MO, MI c R". Player II gets as input an orthogonal matrixT : R" + R".Their goal is to answer 0 if T(x) E MO and 1 if T(x) E M,, (and any an~luer in any other case).We give an almost tight analysis for the quantum communication complexity and for the classical-probabilistic communication complexity of this problem.

ACM Symposium on Theory of Computing (STOC)•May 1, 1999•222 citations

Distributed Quantum Property Testing with Quantum Carrier Pigeons

Kenny Chen, Mina Doosti, Ryan Sweke +1 more

We introduce a framework for distributed quantum inference under communication constraints. In our model, $m$ distributed nodes each receive one copy of an unknown $d$-dimensional quantum state $ρ$, before communicating via a constrained one-way communication channel with a central node, which aims to infer some property of $ρ$. This framework generalizes the classical distributed inference framework introduced by Acharya, Canonne, and Tyagi [COLT 2019], by allowing quantum resources such as quantum communication and shared entanglement. Within this setting, we focus on the fundamental problem of quantum state certification: Given a complete description of some state $σ$, decide whether $ρ=σ$ or $\|ρ-σ\|_1\geq ε$. Additionally, we focus on the case of limited communication between distributed nodes and the central node: we assume each communication channel is limited to only $n_c$ bits and $n_q$ qubits with $n_c + n_q \leq \log d$. When all nodes can make use of a shared source of randomness, we show that the copy complexity of distributed state certification is $Θ(\frac{d^2}{2^{n_q} 2^{n_c/2}ε^2})$. We further demonstrate that shared randomness is necessary to achieve the above complexity, by proving an $Ω(\frac{d^3}{4^{n_q} 2^{n_c} ε^2})$ lower bound in the $\textit{private-coin}$ setting. Moreover, we develop a private-coin algorithm that matches this bound up to a $\sqrt{\log d}$ factor, showing this complexity is near-optimal. Together, our work establishes a general framework for distributed quantum inference with communication constraints and characterizes the complexity of distributed state certification with limited communication.

quant-pharXiv:2609.08864•Sep 9, 2026•0 citations
The classical communication complexity of testing closeness of discrete distributions has recently been studied by Andoni, Malkin and Nosatzki (ICALP'19). In this problem, two players each receive ttt samples from one distribution over [n][n][n], and the goal is to decide whether their two distributions are equal, or are ϵ\epsilonϵ-far apart in the l1l_1l1​-distance. In the present paper we show that the quantum communication complexity of this problem is O~(n/(tϵ2))\tilde{O}(n/(t\epsilon^2))O~(n/(tϵ2)) qubits when the distributions have low l2l_2l2​-norm, which gives a quadratic improvement over the classical communication complexity obtained by Andoni, Malkin and Nosatzki. We also obtain a matching lower bound by using the pattern matrix method. Let us stress that the samples received by each of the parties are classical, and it is only communication between them that is quantum. Our results thus give one setting where quantum protocols overcome classical protocols for a testing problem with purely classical samples.
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.
Suppose one has access to oracles generating samples from two unknown probability distributions p and q on some N-element set. How many samples does one need to test whether the two distributions are close or far from each other in the L1-norm? This and related questions have been extensively studied during the last years in the field of property testing. In the present paper we study quantum algorithms for testing properties of distributions. It is shown that the L1-distance ∥p-q∥1can be estimated with a constant precision using only O(N1/2) queries in the quantum settings, whereas classical computers need Ω(N1-o(1)) queries. We also describe quantum algorithms for testing uniformity and orthogonality with query complexity O(N1/3). The classical query complexity of these problems is known to be Ω(N1/2).
Computing set joins of two inputs is a common task in database theory. Recently, Van Gucht, Williams, Woodruff and Zhang [PODS 2015] considered the complexity of such problems in the natural model of (classical) two-party communication complexity and obtained tight bounds for the complexity of several important distributed set joins. In this paper we initiate the study of the *quantum* communication complexity of distributed set joins. We design a quantum protocol for distributed Boolean matrix multiplication, which corresponds to computing the composition join of two databases, showing that the product of two n×nn\times nn×n Boolean matrices, each owned by one of two respective parties, can be computed with O~(nℓ3/4)\widetilde{O}(\sqrt{n}\ell^{3/4})O(n​ℓ3/4) qubits of communication, where ℓ\ellℓ denotes the number of non-zero entries of the product. Since Van Gucht et al. showed that the classical communication complexity of this problem is Θ~(nℓ)\widetildeΘ(n\sqrt{\ell})Θ(nℓ​), our quantum algorithm outperforms classical protocols whenever the output matrix is sparse. We also show a quantum lower bound and a matching classical upper bound on the communication complexity of distributed matrix multiplication over F2\mathbb{F}_2F2​. Besides their applications to database theory, the communication complexity of set joins is interesting due to its connections to direct product theorems in communication complexity. In this work we also introduce a notion of *all-pairs* product theorem, and relate this notion to standard direct product theorems in communication complexity.
We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions ppp and qqq over domains XXX and YYY, respectively. Their goal is to estimate Ex∼p, y∼q[f(x,y)] \mathbb{E}_{x \sim p,\, y \sim q}[f(x, y)] Ex∼p,y∼q​[f(x,y)] to within additive error ε\varepsilonε for a bounded function fff, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of fff and the error parameter ε\varepsilonε. The random sampling approach -- estimating the mean by averaging fff over O(1/ε2)O(1/\varepsilon^2)O(1/ε2) random samples -- requires O(R(f)/ε2)O(R(f)/\varepsilon^2)O(R(f)/ε2) total communication, where R(f)R(f)R(f) is the randomized communication complexity of fff. We design a new debiasing protocol which improves the dependence on 1/ε1/\varepsilon1/ε to be linear instead of quadratic. Additionally we show better upper bounds for several special classes of functions, including the Equality and Greater-than functions. We introduce lower bound techniques based on spectral methods and discrepancy, and show the optimality of many of our protocols: the debiasing protocol is tight for general functions, and that our protocols for the equality and greater-than functions are also optimal. Furthermore, we show that among full-rank Boolean functions, Equality is essentially the easiest.
Communication complexity has become a central completity model.In that model, we count the amount of communication bits needed between two parties in order to solve certain computational problems.We show that for certain communication complezity problems quantum communication protocols are exponentially faster than classical ores.More explicitly, we give an example for a communication complexity relation (0~ promise problem) P such that: 1) The quantum communication complexity of P is O(log m). 2) The classical probabilistic communication complexity of P is Q(m'l'/ logm).(where m is the length of the inputs).This gives an ezponential gap between quantum communication complexity and classical probabilistic communication complexity.Only a quadratic gap was previously known.Our problem P is of geometrical nature, and is a finite precision variation of the following problem: Player I gets as input a unit vector z E R" and two orthogonal subspaces MO, MI c R". Player II gets as input an orthogonal matrixT : R" + R".Their goal is to answer 0 if T(x) E MO and 1 if T(x) E M,, (and any an~luer in any other case).We give an almost tight analysis for the quantum communication complexity and for the classical-probabilistic communication complexity of this problem.
We introduce a framework for distributed quantum inference under communication constraints. In our model, mmm distributed nodes each receive one copy of an unknown ddd-dimensional quantum state ρρρ, before communicating via a constrained one-way communication channel with a central node, which aims to infer some property of ρρρ. This framework generalizes the classical distributed inference framework introduced by Acharya, Canonne, and Tyagi [COLT 2019], by allowing quantum resources such as quantum communication and shared entanglement. Within this setting, we focus on the fundamental problem of quantum state certification: Given a complete description of some state σσσ, decide whether ρ=σρ=σρ=σ or ∥ρ−σ∥1≥ε\|ρ-σ\|_1\geq ε∥ρ−σ∥1​≥ε. Additionally, we focus on the case of limited communication between distributed nodes and the central node: we assume each communication channel is limited to only ncn_cnc​ bits and nqn_qnq​ qubits with nc+nq≤log⁡dn_c + n_q \leq \log dnc​+nq​≤logd. When all nodes can make use of a shared source of randomness, we show that the copy complexity of distributed state certification is Θ(d22nq2nc/2ε2)Θ(\frac{d^2}{2^{n_q} 2^{n_c/2}ε^2})Θ(2nq​2nc​/2ε2d2​). We further demonstrate that shared randomness is necessary to achieve the above complexity, by proving an Ω(d34nq2ncε2)Ω(\frac{d^3}{4^{n_q} 2^{n_c} ε^2})Ω(4nq​2nc​ε2d3​) lower bound in the private-coin\textit{private-coin}private-coin setting. Moreover, we develop a private-coin algorithm that matches this bound up to a log⁡d\sqrt{\log d}logd​ factor, showing this complexity is near-optimal. Together, our work establishes a general framework for distributed quantum inference with communication constraints and characterizes the complexity of distributed state certification with limited communication.