Quantum states cannot be transmitted efficiently classically

Abstract

We show that any classical two-way communication protocol with shared randomness that can approximately simulate the result of applying an arbitrary measurement (held by one party) to a quantum state of $n$ qubits (held by another), up to constant accuracy, must transmit at least $\Omega (2^n)$ bits. This lower bound is optimal and matches the complexity of a simple protocol based on discretisation using an $\epsilon$-net. The proof is based on a lower bound on the classical communication complexity of a distributed variant of the Fourier sampling problem. We obtain two optimal quantum-classical separations as easy corollaries. First, a sampling problem which can be solved with one quantum query to the input, but which requires $\Omega (N)$ classical queries for an input of size $N$. Second, a nonlocal task which can be solved using $n$ Bell pairs, but for which any approximate classical solution must communicate $\Omega (2^n)$ bits.

24 pages; v3: accepted version incorporating many minor corrections and clarifications

References in corpus (5)

• Randomizing quantum states: Constructions and applications
• The Communication Cost of Simulating Bell Correlations
• Remote preparation of quantum states
• The Learnability of Quantum States
• Robust Bell inequalities from communication complexity

Cited by in corpus (5)

• Distributed sampling, quantum communication witnesses, and measurement incompatibility
• Simple Communication Complexity Separation from Quantum State Antidistinguishability
• The Hadamard gate cannot be replaced by a resource state in universal quantum computation
• Reality, Causality, and Quantum Theory
• Lower bounds for quantum-inspired classical algorithms via communication complexity