Quantum Entanglement and Communication Complexity
arXiv:quant-ph/9705033 · doi:10.1137/S0097539797324886
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.
10 pages, latex, no figures
References in corpus (5)
Cited by in corpus (68)
- Quantum entanglement
- Distributed Quantum Computation over Noisy Channels
- Non-locality and Communication Complexity
- High-dimensional quantum communication: benefits, progress, and future challenges
- Causal and localizable quantum operations
- Generalizations of entanglement based on coherent states and convex sets
- Unbounded violation of tripartite Bell inequalities
- Qudit versions of the qubit "pi-over-eight" gate
- Entanglement assisted random access codes
- Demonstration of active routing of entanglement in a multi-user network
- Sequential random access codes and self-testing of quantum measurement instruments
- Family of Bell-like inequalities as device-independent witnesses for entanglement depth
- An Introduction to Quantum Complexity Theory
- The challenge and opportunities of quantum literacy for future education and transdisciplinary problem-solving
- Bounds on Quantum Correlations in Bell Inequality Experiments
- Improved Quantum Communication Complexity Bounds for Disjointness and Equality
- Quantum communication complexity advantage implies violation of a Bell inequality
- Experimental quantum communication complexity
- Correlations in entanglement-assisted prepare-and-measure scenarios
- Substituting a qubit for an arbitrarily large number of classical bits
- Quantum Entanglement and the Communication Complexity of the Inner Product Function
- On the power of non-local boxes
- Spatial versus Sequential Correlations for Random Access Coding
- Quantifying multipartite nonlocality via the size of the resource
- A feasible quantum communication complexity protocol
- Communication tasks with infinite quantum-classical separation
- Hyperbits: the information quasiparticles
- Foundations of quantum theory and quantum information applications
- Time-reversal formalism applied to maximal bipartite entanglement: Theoretical and experimental exploration
- Entanglement in prepare-and-measure scenarios: many questions, a few answers
- Anonymous Quantum Nonlocality
- Complementarity between entanglement-assisted and quantum distributed random access code
- Photonic entanglement as a resource in quantum computation and quantum communication
- Does violation of a Bell inequality always imply quantum advantage in a communication complexity problem?
- Quantum communication complexity beyond Bell nonlocality
- Classical Cost of Transmitting a Qubit
- Introduction to Quantum Information Processing
- Bounds on the power of proofs and advice in general physical theories
- The Magical Number Seven: An Unexpected Dimensional Threshold in Quantum Communication Complexity
- Multi-partite Quantum Entanglement versus Randomization: Fair and Unbiased Leader Election in Networks
- Complexity of causal order structure in distributed quantum information processing and its trade-off with entanglement
- Multipartite Nonlocality as a Resource and Quantum Correlations Having Indefinite Causal Order
- Quantum advantages of communication complexity from Bell nonlocality
- Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement
- Adaptive advantage in entanglement-assisted communications
- Quantum Communication Complexity (A Survey)
- High fidelity GHZ generation within nearby nodes
- Quantum Blackjack or Can MIT Bring Down the House Again?
- Combinatorial Approaches in Quantum Information Theory
- Information Causality, the Tsirelson Bound, and the 'Being-Thus' of Things
- Scalable & Noise-Robust Communication Advantage of Multipartite Quantum Entanglement
- An unconditional experimental test of Nonclassicality
- Recasting Mermin's multi-player game into the framework of pseudo-telepathy
- Allowing leakage can increase quantum transmission
- Noncontextuality, Finite Precision Measurement and the Kochen-Specker Theorem
- Towards Characterizing the Non-Locality of Entangled Quantum States
- Measurement of an integral of a classical field with a single quantum particle
- Stronger Nonlocality in GHZ States: A Step Beyond the Conventional GHZ Paradox
- Constant communication complexity protocols for multiparty accumulative boolean functions
- A Quantum Measurement Scenario which Requires Exponential Classical Communication for Simulation
- Correlations, Bell Inequality Violation & Quantum Entanglement
- Entanglement Structure Certification Based on Energy-Restricted State Discrimination
- Hypergraph-theoretic charaterizations for LOCC incomparable ensembles of multipartite CAT states
- Applications of Monotone Rank to Complexity Theory
- Quantum Routing and Entanglement Dynamics Through Bottlenecks
- Thermodynamics of bipartite entanglement
- Separability of pure n-qubit states: two characterizations
- Maximum expectation of observables with restricted purity states