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:0709.2761 · Springer eBooks

Unbounded-Error Classical and Quantum Communication Complexity

Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita

Published Dec 6, 2007• 6 citations
arXivHTMLPDF
DOI
10.1007/978-3-540-77120-3_11

Related papers

Unbounded-Error One-Way Classical and Quantum Communication Complexity

Kazuo Iwama, Harumichi Nishimura, Rudy Raymond +1 more

arXiv:0706.3265•Lecture notes in computer science•Aug 25, 2007•19 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

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

Quantum Communication Complexity

Gilles Brassard

arXiv:quant-ph/0101005•Foundations of Physics•Oct 24, 2003•186 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

A linear lower bound on the unbounded error probabilistic communication complexity

Jüurgen Forster

We prove a general lower bound on the complexity of unbounded error probabilistic communication protocols. This result improves on a lower bound for bounded error protocols from Krause (1996). As a simple consequence we get the, to our knowledge, first linear lower bound on the complexity of unbounded error probabilistic communication protocols for the functions defined by Hadamard matrices. We also give an upper bound on the margin of any embedding of a concept class in half spaces.

IEEE Conference on Computational Complexity (CCC)•Nov 13, 2002•15 citations
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.