A Quantum Measurement Scenario which Requires Exponential Classical Communication for Simulation

2002/03/21 by Allison Coates, Coates, Allison
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0203112

7 pages, latex2e two-column format. Submitted to the Sixth International Conference on Quantum Communication, Measurement and Computing

arxiv created 2002/03/21 · arxiv updated 2009/12/01

Abstract

In this paper we consider the following question: how many bits of classical communication and shared random bits are necessary to simulate a quantum protocol involving Alice and Bob where they share k entangled quantum bits and do not communicate at all. We prove that 2^k classical bits are necessary, even if the classical protocol is allowed an εchance of failure.

Related

• No-Go Theorem for Generic Simulation of Qubit Channels with Finite Classical Resources
• The Power of One Clean Qubit in Communication Complexity
• Faithful Simulation of Distributed Quantum Measurement with Coding for Computing
• Noisy Interactive Quantum Communication
• Quantum Communication Complexity (A Survey)