Simple Information Processing Tasks with Unbounded Quantum Advantage

Abstract

Communication scenarios between two parties can be implemented by first encoding messages into some states of a physical system which acts as the physical medium of the communication and then decoding the messages by measuring the state of the system. We show that already in the simplest possible scenarios it is possible to detect a definite, unbounded advantage of quantum systems over classical systems. We do this by constructing a family of operationally meaningful communication tasks each of which on one hand can be implemented by using just a single qubit but which on the other hand require unboundedly larger classical system for classical implementation. Furthemore, we show that even though with the additional resource of shared randomness the proposed communication tasks can be implemented by both quantum and classical systems of the same size, the number of coordinated actions needed for the classical implementation also grows unboundedly. In particular, no finite storage can be used to store all the coordinated actions needed to implement all the possible quantum communication tasks with classical systems. As a consequence, shared randomness cannot be viewed as a free resource.

accepted version

References in corpus (27)

• Quantum Computing in the NISQ era and beyond
• Quantum computational advantage using photons
• Quantum fingerprinting
• On the reality of the quantum state
• Boson sampling with 20 input photons in 60-mode interferometers at $10^{14}$ state spaces
• The Communication Cost of Simulating Bell Correlations
• Device-independent tests of classical and quantum dimensions
• Conditions for compatibility of quantum state assignments
• Classical simulation of quantum entanglement without local hidden variables
• On the Geometric Interpretation of the Nonnegative Rank
• Conclusive Exclusion of Quantum States
• Positive semidefinite rank
• Limitations of Quantum Advice and One-Way Communication
• Classical information storage in an $n$-level quantum system
• Device-Independent Tests of Entropy
• Substituting a qubit for an arbitrarily large number of classical bits
• Heuristics for Exact Nonnegative Matrix Factorization
• Communication tasks with infinite quantum-classical separation
• Antidistinguishability of Pure Quantum States
• Quantum Advantage in Information Retrieval
• Classical Cost of Transmitting a Qubit
• Noncontextuality Inequalities from Antidistinguishability
• Communication of partial ignorance with qubits
• Simple Communication Complexity Separation from Quantum State Antidistinguishability
• Communication tasks in operational theories
• Advantage of Quantum Theory Over Non-classical Models of Communication
• A note on the inner products of pure states and their antidistinguishability

Cited by in corpus (9)

• Quantum thermodynamic advantage in work extraction from steerable quantum correlations
• Quantum Advantage: A Single Qubit's Experimental Edge in Classical Data Storage
• Entanglement-breaking channels are a quantum memory resource
• Maximal Elements of Quantum Communication
• How contextuality and antidistinguishability are related
• Quantum state exclusion for group-generated ensembles of pure states
• Can a qudit carry more information than a dit?
• Quantum advantage in a unified scenario and secure detection of resources
• Random Exclusion Codes: Quantum Advantages of Single-Shot Communication