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

BRICS Report Series

Quantum Entanglement and Communication Complexity

Harry Buhrman, Richard Cleve, Wim van Dam

Published Jun 10, 1997• 21 citations
Publisher

Abstract

We consider a variation of the multi-party communication complexity scenario where the parties are supplied with an extra resource: particles in an entangled quantum state. We show that, although a prior quantum entanglement cannot be used to simulate a communication channel, it can reduce the communication complexity of functions in some cases. Specifically, we show that, for a particular function among three parties (each of which possesses part of the function's input), a prior quantum entanglement enables them to learn the value of the function with only three bits of communication occurring among the parties, whereas, without quantum entanglement, four bits of communication are necessary. We also show that, for a particular two-party probabilistic communication complexity problem, quantum entanglement results in less communication than is required with only classical random correlations (instead of quantum entanglement). These results are a noteworthy contrast to the well-known fact that quantum entanglement cannot be used to actually simulate communication among remote parties.

DOI
10.7146/brics.v4i40.18966

Related papers

Quantum Entanglement and Communication Complexity

Harry Buhrman, Richard Cleve, Wim van Dam

We consider a variation of the communication complexity scenario, where the parties are supplied with an extra resource: particles in an entangled quantum state. We note that "quantum nonlocality" can be naturally expressed in the language of communication complexity. These are communication complexity problems where the "output" is embodied in the correlations between the outputs of the individual parties. Without entanglement, the parties must communicate to produce the required correlations; whereas, with entanglement, no communication is necessary to produce the correlations. In this sense, nonlocality proofs can also be viewed as communication complexity problems where the presence of quantum entanglement reduces the amount of necessary communication. We show how to transform examples of nonlocality into more traditional communication complexity problems, where the output is explicitly determined by each individual party. The resulting problems require communication with or without entanglement, but the required communication is less when entanglement is available. All these results are a noteworthy contrast to the well-known fact that entanglement cannot be used to actually simulate or compress classical communication between remote parties.

arXiv:quant-ph/9705033•SIAM Journal on Computing•Jan 1, 2001•142 citations

Substituting quantum entanglement for communication

Richard Cleve, Harry Buhrman

We show that quantum entanglement can be used as a substitute for communication when the goal is to compute a function whose input data are distributed among remote parties. Specifically, we show that, for a particular function among three parties (each of which possesses part of the function's input), a prior quantum entanglement enables one of them to learn the value of the function with only two bits of communication occurring among the parties, whereas, without quantum entanglement, three bits of communication are necessary. This result contrasts the well-known fact that quantum entanglement cannot be used to simulate communication among remote parties.

arXiv:quant-ph/9704026•Physical Review A•Aug 1, 1997•416 citations

Multiparty quantum communication complexity

Harry Buhrman, Wim van Dam, Peter Høyer +1 more

Quantum entanglement cannot be used to achieve direct communication between remote parties, but it can reduce the communication needed for some problems. Let each of $k$ parties hold some partial input data to some fixed $k$-variable function $f.$ The communication complexity of $f$ is the minimum number of classical bits required to be broadcasted for every party to know the value of $f$ on their inputs. We construct a function $G$ such that for the one-round communication model and three parties, $G$ can be computed with $n+1$ bits of communication when the parties share prior entanglement. We then show that without entangled particles, the one-round communication complexity of $G$ is $(3/2)n+1.$ Next we generalize this function to a function $F.$ We show that if the parties share prior quantum entanglement, then the communication complexity of $F$ is exactly $k.$ We also show that, if no entangled particles are provided, then the communication complexity of $F$ is roughly $k{\mathrm{log}}_{2}k.$ These two results prove communication complexity separations better than a constant number of bits.

arXiv:quant-ph/9710054•Physical Review A•Oct 1, 1999•114 citations

Deterministically Reducing the Communication Complexity with Quantum Entanglement

Bin Cao

We propose a two-party deterministic communication complexity scenario with a set of pairs of particles in an arbitrary pure entangled state. For an arbitrary two-variable Boolean function, the prior entanglement results in less communication than that is required with only classical random correlations.

Acta Sinica Quantum Optica•Jan 1, 2002•0 citations

Three-party quantum communication complexity via entangled tripartite pure states

Peng Xue, Chuan‐Feng Li, Yongsheng Zhang +1 more

We propose a probabilistic three-party communication complexity scenario: with a prior entangled tripartite pure state, to learn the value of a particular function determined by each communication player. It results in less communication than is required with only classical random correlations. If they share a Greenberger-Horne-Zeilinger (GHZ) state, this protocol is deterministic.

Journal of Optics B Quantum and Semiclassical Optics•Jul 4, 2001•4 citations

Improvements in communication complexity using quantum entanglement

Angad Mohandas Kamat

Quantum computing resources have been known to provide speed-ups in computational complexity in many algorithms. The impact of these resources in communication, however, has not attracted much attention. We investigate the impact of \nquantum entanglement on communication complexity. We provide a positive result, \nby presenting a class of multi-party communication problems wherein the presence of \na suitable quantum entanglement lowers the classical communication complexity. We \nshow that, in evaluating certains function whose parameters are distributed among \nvarious parties, the presence of prior entanglement can help in reducing the required \ncommunication. We also present an outline of realizing the required entanglement \nthrough optical photon quantum computing. We also suggest the possible impact of \nour results on network information flow problems, by showing an instance of a lower \nbound which can be broken by adding limited power to the communication model.

•Oct 10, 2008•0 citations
We consider a variation of the multi-party communication complexity scenario where the parties are supplied with an extra resource: particles in an entangled quantum state. We show that, although a prior quantum entanglement cannot be used to simulate a communication channel, it can reduce the communication complexity of functions in some cases. Specifically, we show that, for a particular function among three parties (each of which possesses part of the function's input), a prior quantum entanglement enables them to learn the value of the function with only three bits of communication occurring among the parties, whereas, without quantum entanglement, four bits of communication are necessary. We also show that, for a particular two-party probabilistic communication complexity problem, quantum entanglement results in less communication than is required with only classical random correlations (instead of quantum entanglement). These results are a noteworthy contrast to the well-known fact that quantum entanglement cannot be used to actually simulate communication among remote parties.
We consider a variation of the communication complexity scenario, where the parties are supplied with an extra resource: particles in an entangled quantum state. We note that "quantum nonlocality" can be naturally expressed in the language of communication complexity. These are communication complexity problems where the "output" is embodied in the correlations between the outputs of the individual parties. Without entanglement, the parties must communicate to produce the required correlations; whereas, with entanglement, no communication is necessary to produce the correlations. In this sense, nonlocality proofs can also be viewed as communication complexity problems where the presence of quantum entanglement reduces the amount of necessary communication. We show how to transform examples of nonlocality into more traditional communication complexity problems, where the output is explicitly determined by each individual party. The resulting problems require communication with or without entanglement, but the required communication is less when entanglement is available. All these results are a noteworthy contrast to the well-known fact that entanglement cannot be used to actually simulate or compress classical communication between remote parties.
We show that quantum entanglement can be used as a substitute for communication when the goal is to compute a function whose input data are distributed among remote parties. Specifically, we show that, for a particular function among three parties (each of which possesses part of the function's input), a prior quantum entanglement enables one of them to learn the value of the function with only two bits of communication occurring among the parties, whereas, without quantum entanglement, three bits of communication are necessary. This result contrasts the well-known fact that quantum entanglement cannot be used to simulate communication among remote parties.
Quantum entanglement cannot be used to achieve direct communication between remote parties, but it can reduce the communication needed for some problems. Let each of kkk parties hold some partial input data to some fixed kkk-variable function f.f.f. The communication complexity of fff is the minimum number of classical bits required to be broadcasted for every party to know the value of fff on their inputs. We construct a function GGG such that for the one-round communication model and three parties, GGG can be computed with n+1n+1n+1 bits of communication when the parties share prior entanglement. We then show that without entangled particles, the one-round communication complexity of GGG is (3/2)n+1.(3/2)n+1.(3/2)n+1. Next we generalize this function to a function F.F.F. We show that if the parties share prior quantum entanglement, then the communication complexity of FFF is exactly k.k.k. We also show that, if no entangled particles are provided, then the communication complexity of FFF is roughly klog2k.k{\mathrm{log}}_{2}k.klog2​k. These two results prove communication complexity separations better than a constant number of bits.
Quantum computing resources have been known to provide speed-ups in computational complexity in many algorithms. The impact of these resources in communication, however, has not attracted much attention. We investigate the impact of \nquantum entanglement on communication complexity. We provide a positive result, \nby presenting a class of multi-party communication problems wherein the presence of \na suitable quantum entanglement lowers the classical communication complexity. We \nshow that, in evaluating certains function whose parameters are distributed among \nvarious parties, the presence of prior entanglement can help in reducing the required \ncommunication. We also present an outline of realizing the required entanglement \nthrough optical photon quantum computing. We also suggest the possible impact of \nour results on network information flow problems, by showing an instance of a lower \nbound which can be broken by adding limited power to the communication model.