Quantum communication complexity

DOI10.1023/A:1026009100467zbMATH Open1222.81104arXivquant-ph/0101005OpenAlexW1793119275MaRDI QIDQ720535FDOQ720535

Authors: Gilles Brassard 

Publication date: 17 October 2011

Published in: Foundations of Physics (Search for Journal in Brave)

Abstract: Can quantum communication be more efficient than its classical counterpart? Holevo's theorem rules out the possibility of communicating more than n bits of classical information by the transmission of n quantum bits --- unless the two parties are entangled, in which case twice as many classical bits can be communicated but no more. In apparent contradiction, there are distributed computational tasks for which quantum communication cannot be simulated efficiently by classical means. In extreme cases, the effect of transmitting quantum bits cannot be achieved classically short of transmitting an exponentially larger number of bits. In a similar vein, can entanglement be used to save on classical communication? It is well known that entanglement on its own is useless for the transmission of information. Yet, there are distributed tasks that cannot be accomplished at all in a classical world when communication is not allowed, but that become possible if the non-communicating parties share prior entanglement. This leads to the question of how expensive it is, in terms of classical communication, to provide an exact simulation of the spooky power of entanglement.

Full work available at URL: https://arxiv.org/abs/quant-ph/0101005

Recommendations

• Quantum entanglement and communication complexity
• Quantum communication and complexity.
• scientific article; zbMATH DE number 1406113
• Quantum entanglement and the communication complexity of the inner product function
• QUANTUM COMMUNICATION COMPLEXITY PROTOCOLS BASED ON HIGHER-DIMENSIONAL ENTANGLED SYSTEMS

Mathematics Subject Classification ID

Coding theorems (Shannon theory) (94A24) Quantum measurement theory, state operations, state preparations (81P15) Quantum cryptography (quantum-theoretic aspects) (81P94)

Cited In (35)

• A short review on quantum identity authentication protocols: how would Bob know that he is talking with Alice?
• QUANTUM COMMUNICATION COMPLEXITY PROTOCOLS BASED ON HIGHER-DIMENSIONAL ENTANGLED SYSTEMS
• Generalizations of the distributed Deutsch–Jozsa promise problem
• Title not available (Why is that?)
• Exponential quantum enhancement for distributed addition with local nonlinearity
• Quantum computing without entanglement
• Title not available (Why is that?)
• Quantum Multiparty Communication Complexity and Circuit Lower Bounds
• A universal framework for entanglement detection under group symmetry
• On the role of shared entanglement
• Communication Over Quantum Channels With Parameter Estimation
• Quantum entanglement as a new information processing resource
• Lower bounds on the entanglement needed to play XOR non-local games
• Lifting Bell inequalities
• Quantum communication and complexity.
• Strong simulation of linear optical processes
• Two party non-local games
• Communication complexity as a principle of quantum mechanics
• Objective computation versus subjective computation
• Quantum pseudo-telepathy
• Bell-type inequalities for nonlocal resources
• Quantum Communication Complexity with Coherent States and Linear Optics
• Non-local setting and outcome information for violation of Bell's inequality
• Entangled states cannot be classically simulated in generalized Bell experiments with quantum inputs
• Matrix discrepancy from Quantum communication
• Title not available (Why is that?)
• Quantum entanglement and communication complexity
• Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial
• Multi-party Quantum Communication Complexity with Routed Messages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum speed-up for unsupervised learning
• Quantum communication protocols as a benchmark for programmable quantum computers
• Quantum weakly nondeterministic communication complexity
• The Morita theory of quantum graph isomorphisms

This page was built for publication: Quantum communication complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q720535)