Exponential communication gap between weak and strong classical simulations of quantum communication

Abstract

The most trivial way to simulate classically the communication of a quantum state is to transmit the classical description of the quantum state itself. However, this requires an infinite amount of classical communication if the simulation is exact. A more intriguing and potentially less demanding strategy would encode the full information about the quantum state into the probability distribution of the communicated variables, so that this information is never sent in each single shot. This kind of simulation is called weak, as opposed to strong simulations, where the quantum state is communicated in individual shots. In this paper, we introduce a bounded-error weak protocol for simulating the communication of an arbitrary number of qubits and a subsequent two-outcome measurement consisting of an arbitrary pure state projector and its complement. This protocol requires an amount of classical communication independent of the number of qubits and proportional to Delta^{-1}, where Delta is the error and a free parameter of the protocol. Conversely, a bounded-error strong protocol requires an amount of classical communication growing exponentially with the number of qubits for a fixed error. Our result improves a previous protocol, based on the Johnson-Lindenstrauss lemma, with communication cost scaling as Delta^{-2} log Delta^{-1}.

References in corpus (14)

• On the reality of the quantum state
• Randomizing quantum states: Constructions and applications
• The Communication Cost of Simulating Bell Correlations
• Is a system's wave function in one-to-one correspondence with its elements of reality?
• Matchgates and classical simulation of quantum circuits
• Distinct Quantum States Can Be Compatible with a Single State of Reality
• Reconstruction of Gaussian quantum mechanics from Liouville mechanics with an epistemic restriction
• Implications of the Pusey-Barrett-Rudolph quantum no-go theorem
• Exponential complexity and ontological theories of quantum mechanics
• Dynamics of a qubit as a classical stochastic process with time-correlated noise: minimal measurement invasiveness
• Epistemic view of quantum states and communication complexity of quantum channels
• State space dimensionality in short memory hidden variable theories
• Communication cost of classically simulating a quantum channel with subsequent rank-1 projective measurement
• Compressing the hidden variable space of a qubit

Cited by in corpus (6)

• No Return to Classical Reality
• Information-based measure of nonlocality
• Necessary and sufficient optimality conditions for classical simulations of quantum communication processes
• Communication Complexity of Channels in General Probabilistic Theories
• Quantum states cannot be transmitted efficiently classically
• Reality, Causality, and Quantum Theory