Substituting a qubit for an arbitrarily large number of classical bits

Abstract

We show that a qubit can be used to substitute for an arbitrarily large number of classical bits. We consider a physical system S interacting locally with a classical field phi(x) as it travels directly from point A to point B. The field has the property that its integrated value is an integer multiple of some constant. The problem is to determine whether the integer is odd or even. This task can be performed perfectly if S is a qubit. On the otherhand, if S is a classical system then we show that it must carry an arbitrarily large amount of classical information. We identify the physical reason for such a huge quantum advantage, and show that it also implies a large difference between the size of quantum and classical memories necessary for some computations. We also present a simple proof that no finite amount of one-way classical communication can perfectly simulate the effect of quantum entanglement.

8 pages, LaTeX, no figures. v2: added result on entanglement simulation with classical communication; v3: minor correction to main proof, change of title, added reference

References in corpus (10)

• Substituting Quantum Entanglement for Communication
• The cost of exactly simulating quantum entanglement with classical communication
• Quantum Entanglement and Communication Complexity
• Multiparty Quantum Communication Complexity
• Quantum vs. Classical Communication and Computation
• Classical simulation of quantum entanglement without local hidden variables
• Classical Teleportation of a Quantum Bit
• Quantum Telecomputation
• A feasible quantum communication complexity protocol
• Foundations of quantum theory and quantum information applications

Cited by in corpus (26)

• Quantum Computing with NMR
• Are quantum states real?
• A cross-disciplinary introduction to quantum annealing-based algorithms
• Memory cost of quantum contextuality
• Quantum Theory and Determinism
• Quantum Advantage from Sequential-Transformation Contextuality
• Quantum advantages in classically defined tasks
• Non-classicality of temporal correlations
• Testing dimension and non-classicality in communication networks
• Dimension of physical systems, information processing, and thermodynamics
• Computing with a single qubit faster than the computation quantum speed limit
• Communication tasks with infinite quantum-classical separation
• Memory cost for simulating all quantum correlations of the Peres-Mermin scenario
• Classical Cost of Transmitting a Qubit
• Almost qudits in the prepare-and-measure scenario
• Probing the Non-Classicality of Temporal Correlations
• Simple Information Processing Tasks with Unbounded Quantum Advantage
• Qubit versus bit for measuring an integral of a classical field
• Classical analogue of quantum superdense coding and communication advantage of a single quantum system
• Quantum states cannot be transmitted efficiently classically
• Maximal Elements of Quantum Communication
• Identifying the value of a random variable unambiguously: Quantum versus classical approaches
• Quantum Simulation of Neutrino Oscillation and Dirac Particle Dynamics in Curved Space-time
• Measurement of an integral of a classical field with a single quantum particle
• Quantum advantage in a unified scenario and secure detection of resources
• Advice Coins for Classical and Quantum Computation