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:0706.3265 · Lecture notes in computer science

Unbounded-Error One-Way Classical and Quantum Communication Complexity

Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita

Published Aug 25, 2007• 19 citations
arXivHTMLPDF
DOI
10.1007/978-3-540-73420-8_12

Related papers

Unbounded-Error Classical and Quantum Communication Complexity

Kazuo Iwama, Harumichi Nishimura, Rudy Raymond +1 more

arXiv:0709.2761•Springer eBooks•Dec 6, 2007•6 citations

A linear lower bound on the unbounded error probabilistic communication complexity

Jürgen Forster

Journal of Computer and System Sciences•Dec 1, 2002•189 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•4 citations

Unbounded quantum advantage in communication with minimal input scaling

Sumit Rout, Nitica Sakharwade, Some Sankar Bhattacharya +2 more

In communication complexity-like problems, previous studies have shown either an exponential quantum advantage or an unbounded quantum advantage with an exponentially large input set Θ ( 2 n ) bit with respect to classical communication Θ ( n ) bit. In the former, the quantum and classical separation grows exponentially in input while the latter's quantum communication resource is a constant. Remarkably, it was still open whether an unbounded quantum advantage exists while the inputs do not scale exponentially. Here we answer this question affirmatively using an input size of optimal order. Considering two variants as tasks: (1) distributed computation of relation and (2) , we study the one-way zero-error communication complexity of a relation induced by a distributed clique labeling problem for orthogonality graphs. While we prove no quantum advantage in the first task, we show an in relation reconstruction without public coins. Specifically, for a class of graphs with order m , the quantum complexity is Θ ( 1 ) while the classical complexity is Θ ( log 2 m ) . Remarkably, the input size is Θ ( log 2 m ) bit and the order of its scaling with respect to classical communication is . This is exponentially better compared to previous works. Additionally, we prove a lower bound (linear in the number of maximum cliques) on the amount of classical public coin necessary to overcome the separation in the scenario of restricted communication and connect this to the existence of orthogonal arrays. Finally, we highlight some applications of this task to semi-device-independent dimension witnessing as well as to the detection of mutually unbiased bases.

arXiv:2305.10372•Physical Review Research•Apr 30, 2025•5 citations

New bounds on classical and quantum one-way communication complexity

Rahul Jain, Shengyu Zhang

arXiv:0802.4101•Theoretical Computer Science•Oct 18, 2008•14 citations

Quantum Communication Complexity

Gilles Brassard

arXiv:quant-ph/0101005•Foundations of Physics•Oct 24, 2003•186 citations
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.
In communication complexity-like problems, previous studies have shown either an exponential quantum advantage or an unbounded quantum advantage with an exponentially large input set Θ ( 2 n ) bit with respect to classical communication Θ ( n ) bit. In the former, the quantum and classical separation grows exponentially in input while the latter's quantum communication resource is a constant. Remarkably, it was still open whether an unbounded quantum advantage exists while the inputs do not scale exponentially. Here we answer this question affirmatively using an input size of optimal order. Considering two variants as tasks: (1) distributed computation of relation and (2) , we study the one-way zero-error communication complexity of a relation induced by a distributed clique labeling problem for orthogonality graphs. While we prove no quantum advantage in the first task, we show an in relation reconstruction without public coins. Specifically, for a class of graphs with order m , the quantum complexity is Θ ( 1 ) while the classical complexity is Θ ( log 2 m ) . Remarkably, the input size is Θ ( log 2 m ) bit and the order of its scaling with respect to classical communication is . This is exponentially better compared to previous works. Additionally, we prove a lower bound (linear in the number of maximum cliques) on the amount of classical public coin necessary to overcome the separation in the scenario of restricted communication and connect this to the existence of orthogonal arrays. Finally, we highlight some applications of this task to semi-device-independent dimension witnessing as well as to the detection of mutually unbiased bases.