.png){kind=icon}
.png){kind=icon}
Return
Quantum states cannot be transmitted efficiently classically
.png){kind=icon}
OA
AI
DOI：10.22331/q-2019-06-28-154.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 is an element of-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.
Keywords:
ONE-WAY COMMUNICATION
EXPONENTIAL SEPARATION
COMPLEXITY