Quantum states cannot be transmitted efficiently classically

Research output: Contribution to journalArticle (Academic Journal)peer-review

1 Citation (Scopus)
145 Downloads (Pure)

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 Ω(2n) bits. This lower bound is optimal and matches the complexity of a simple protocol based on discretisation using an -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 Ω(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 Ω(2n) bits.
Original languageEnglish
Pages (from-to)154-177
Number of pages24
JournalQuantum
Volume3
DOIs
Publication statusPublished - 28 Jun 2019

Structured keywords

  • Bristol Quantum Information Institute
  • QITG

Fingerprint Dive into the research topics of 'Quantum states cannot be transmitted efficiently classically'. Together they form a unique fingerprint.

Cite this