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

ACM SIGACT News

Classical versus quantum communication complexity

Amnon Ta‐Shma

Published Sep 1, 1999• 23 citations
Publisher

Abstract

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.
DOI
10.1145/333623.333628

Related papers

Quantum Proofs for Classical Theorems

Andrew Drucker, Ronald de Wolf

Alongside the development of quantum algorithms and quantum complexity theory in recent years, quantum techniques have also proved instrumental in obtaining results in diverse classical (non-quantum) areas, such as coding theory, communication complexity, and polynomial approximations. In this paper we survey these results and the quantum toolbox they use.

arXiv:0910.3376•Theory of Computing•Jan 1, 2011•49 citations

The Quantum Communication Complexity of Sampling

Andris Ambainis, Leonard J. Schulman, Amnon Ta‐Shma +2 more

Sampling is an important primitive in probabilistic and quantum algorithms. In the spirit of communication complexity, given a function $f: X \times Y \rightarrow \{0,1\}$ and a probability distribution ${\cal D}$ over $X \times Y$, we define the sampling complexity of $(f, {\cal D})$ as the minimum number of bits that Alice and Bob must communicate for Alice to pick $x \in X$ and Bob to pick $y \in Y$ as well as a value z such that the resulting distribution of $(x,y,z)$ is close to the distribution $({\cal D}, f({\cal D}))$. In this paper we initiate the study of sampling complexity, in both the classical and quantum models. We give several variants of a definition. We completely characterize some of these variants and give upper and lower bounds on others. In particular, this allows us to establish an exponential gap between quantum and classical sampling complexity for the set-disjointness function.

SIAM Journal on Computing•Jan 1, 2003•48 citations

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, 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.

arXiv:quant-ph/0504087•Mathematical Structures in Computer Science•Feb 1, 2009•13 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•242 citations

Quantum information technology: Theory and applications

Paata J. Kervalishvili

In the last decade quantum information theory and technology evolve and show their great potential. There are a set of problems for which it's more efficient and even not possible with classical communication to solve than with quantum equivalent. The best known example is Quantum Key Distribution, though there are quantum non-locality (entanglement), quantum teleportation, communication complexity and many more. Quantum communication relies on some phenomenon like entanglement which gives plenty of opportunities, but at the same time it's very tricky. Present knowledge lets us define entanglement as a property of quantum system when two or more objects are linked together (quantum states).

International Conference on Intelligent Computing and Information Systems (ICICIS)•Dec 1, 2015•2 citations

Control Communication Complexity of Nonlinear Systems

John B. Baillieul, Wing Shing Wong

The interaction of information and control has been a topic of interest to system theorists that can be traced back at least to the 1950's when the fields of communications, control, and information theory were new but developing rapidly.Recent advances in our understanding of this interplay have emerged from work on the dynamical effect of state quantization together with results connecting communication channel data rates and system stability.Although this work has generated considerable interest, it has been centrally concerned with the relationship between control system performance and feedback information processing rates while ignoring the complexity (i.e. the cost of information processing).The concepts of communication and computation complexity of a controlled dynamical system based on digitized information lie in what is largely an uncharted area.In our recent work an attempt was made to explore this area by introducing a new measure of communication complexity for a two-player distributed control system.This complexity is named control communication complexity (CCC).It is based on the communication complexity concept defined in distributed computing and seeks to connect the complexity of information exchange over finite bandwidth channels with the control system dynamics.The purpose of the present paper is to extend the study of control communication complexity to an interesting class of continuous-time control systems that have appeared in the recent literature dealing with quantum communication and control systems.An interesting aspect of this extension is that it brings together heretofore independent research themes that have been prominent in the research career of Roger Brockett.

Communications in Information and Systems•Jan 1, 2009•24 citations
Sampling is an important primitive in probabilistic and quantum algorithms. In the spirit of communication complexity, given a function f:X×Y→{0,1}f: X \times Y \rightarrow \{0,1\}f:X×Y→{0,1} and a probability distribution D{\cal D}D over X×YX \times YX×Y, we define the sampling complexity of (f,D)(f, {\cal D})(f,D) as the minimum number of bits that Alice and Bob must communicate for Alice to pick x∈Xx \in Xx∈X and Bob to pick y∈Yy \in Yy∈Y as well as a value z such that the resulting distribution of (x,y,z)(x,y,z)(x,y,z) is close to the distribution (D,f(D))({\cal D}, f({\cal D}))(D,f(D)). In this paper we initiate the study of sampling complexity, in both the classical and quantum models. We give several variants of a definition. We completely characterize some of these variants and give upper and lower bounds on others. In particular, this allows us to establish an exponential gap between quantum and classical sampling complexity for the set-disjointness function.
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.
In the last decade quantum information theory and technology evolve and show their great potential. There are a set of problems for which it's more efficient and even not possible with classical communication to solve than with quantum equivalent. The best known example is Quantum Key Distribution, though there are quantum non-locality (entanglement), quantum teleportation, communication complexity and many more. Quantum communication relies on some phenomenon like entanglement which gives plenty of opportunities, but at the same time it's very tricky. Present knowledge lets us define entanglement as a property of quantum system when two or more objects are linked together (quantum states).
The interaction of information and control has been a topic of interest to system theorists that can be traced back at least to the 1950's when the fields of communications, control, and information theory were new but developing rapidly.Recent advances in our understanding of this interplay have emerged from work on the dynamical effect of state quantization together with results connecting communication channel data rates and system stability.Although this work has generated considerable interest, it has been centrally concerned with the relationship between control system performance and feedback information processing rates while ignoring the complexity (i.e. the cost of information processing).The concepts of communication and computation complexity of a controlled dynamical system based on digitized information lie in what is largely an uncharted area.In our recent work an attempt was made to explore this area by introducing a new measure of communication complexity for a two-player distributed control system.This complexity is named control communication complexity (CCC).It is based on the communication complexity concept defined in distributed computing and seeks to connect the complexity of information exchange over finite bandwidth channels with the control system dynamics.The purpose of the present paper is to extend the study of control communication complexity to an interesting class of continuous-time control systems that have appeared in the recent literature dealing with quantum communication and control systems.An interesting aspect of this extension is that it brings together heretofore independent research themes that have been prominent in the research career of Roger Brockett.