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:quant-ph/0005032

Quantum Communication Complexity

Hartmut Klauck

Published May 8, 2000• 18 citations
arXivHTMLPDF

Abstract

This paper surveys the field of quantum communication complexity. Some interesting recent results are collected concerning relations to classical communication, lower bound methods, one-way communication, and applications of quantum communication complexity.
DOI
10.48550/arxiv.quant-ph/0005032

Related papers

On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity

Shengyu Zhang

Lecture notes in computer science•Jan 1, 2011•2 citations

Quantum communication complexity: a survey

Gilles Brassard A

Summary form only given. This is a survey talk on the topic of quantum communication complexity. A full survey paper by the author is available in Foundations of Physics (G. Brassard, vol.33(11), p.1593-1616, 2003).

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•Sep 28, 2004•24 citations

Direct information lower bounds for one-way communication complexity problems: Applications to the demonstration of an unconditional quantum advantage and to cryptography (Short Paper)

Romain Alléaume, Gabriel Blanchot, Philippe Gaborit +1 more

Information cost is often treated as a secondary quantity in communication complexity, even when the operational resource of interest is the information revealed by a protocol rather than its message length. This mismatch becomes particularly important in quantum communication and cryptography, where classical leakage must be compared directly with the information carried by quantum states. For this reason, we derive direct finite-size lower bounds, with explicit constants, on the information cost of one-way private-coin protocols for Hidden Matching, a communication-complexity problem, and two related tasks: Sampling Matching and Beta-Partial Matching. These bounds lead to two concrete applications. First, they provide a universal classical benchmark for coherent-state implementations of Sampling Matching, opening a route to an unconditional quantum advantage in information cost for a one-way communication complexity problem on a photonic platform. Second, they substantially tighten the analysis of HM-QCT, a recent everlastingly secure hybrid post-quantum/QKD protocol, bringing its implementation closer to realistic optical parameters while preserving the possibility of exceeding the fundamental rate-loss limits of standard QKD.

ACM Conference on Post-Quantum and Quantum-based Security•Oct 26, 2026•0 citations

Classical versus quantum communication complexity

Amnon Ta‐Shma

Classical communication complexity has been intensively studied since its conception two decades ago. Recently, its quantum analogue, the quantum communication complexity model, was defined and studied. In this paper we present some of the main results in the area.

ACM SIGACT News•Sep 1, 1999•23 citations

Limitations of Quantum Advice and One-Way Communication

Scott Aaronson

Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that $\mathsf{BQP/qpoly}\subseteq\mathsf{PP/poly}$, where $\mathsf{BQP/qpoly}$ is the class of problems solvable in quantum polynomial time, given a polynomial-size “quantum advice state” that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which $\mathsf{NP}\not \subset \mathsf{BQP/qpoly}$. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols. A preliminary version of this paper appeared in the 2004 Conference on Computational Complexity (CCC).

arXiv:quant-ph/0402095•Theory of Computing•Jan 1, 2005•140 citations

Quantum communication complexity of block-composed functions

ShiYaoyun, ZhuYufan

A major open problem in communication complexity is whether or not quantum protocolscan be exponentially more efficient than classical ones for computing a total Booleanfunction in the two-party in...

Quantum Information and Computation•May 1, 2009•1 citation
Information cost is often treated as a secondary quantity in communication complexity, even when the operational resource of interest is the information revealed by a protocol rather than its message length. This mismatch becomes particularly important in quantum communication and cryptography, where classical leakage must be compared directly with the information carried by quantum states. For this reason, we derive direct finite-size lower bounds, with explicit constants, on the information cost of one-way private-coin protocols for Hidden Matching, a communication-complexity problem, and two related tasks: Sampling Matching and Beta-Partial Matching. These bounds lead to two concrete applications. First, they provide a universal classical benchmark for coherent-state implementations of Sampling Matching, opening a route to an unconditional quantum advantage in information cost for a one-way communication complexity problem on a photonic platform. Second, they substantially tighten the analysis of HM-QCT, a recent everlastingly secure hybrid post-quantum/QKD protocol, bringing its implementation closer to realistic optical parameters while preserving the possibility of exceeding the fundamental rate-loss limits of standard QKD.
Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly⊆PP/poly\mathsf{BQP/qpoly}\subseteq\mathsf{PP/poly}BQP/qpoly⊆PP/poly, where BQP/qpoly\mathsf{BQP/qpoly}BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size “quantum advice state” that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP⊄BQP/qpoly\mathsf{NP}\not \subset \mathsf{BQP/qpoly}NP⊂BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols. A preliminary version of this paper appeared in the 2004 Conference on Computational Complexity (CCC).