Skip to content
naulon
Not checkedNot checked for notices yet.

Quantum states cannot be transmitted efficiently classically

Ashley Montanaro

Quantum · 2019

doi:10.22331/q-2019-06-28-154 (opens in a new tab)

We email you when a new notice or a question about this paper appears.

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 Ω ( 2 n ) 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 Ω ( 2 n ) bits.

Abstract licence: CC BY

References46

    40 more references, whose wording the paper’s licence keeps private.

    All 46 references

    Reads

    Read by people on this page

    None yet.

    Checked or read by AI through naulon

    None yet.

    A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.

    Are you an author?

    Is this your paper?

    Claim it to add your note and be paid when agents cite it. Free.