Quantum Advantage in Information Retrieval
arXiv:2007.15643 · doi:10.1103/PRXQuantum.3.020307
Abstract
Random access codes have provided many examples of quantum advantage in communication, but concern only one kind of information retrieval task. We introduce a related task - the Torpedo Game - and show that it admits greater quantum advantage than the comparable random access code. Perfect quantum strategies involving prepare-and-measure protocols with experimentally accessible three-level systems emerge via analysis in terms of the discrete Wigner function. The example is leveraged to an operational advantage in a pacifist version of the strategy game Battleship. We pinpoint a characteristic of quantum systems that enables quantum advantage in any bounded-memory information retrieval task. While preparation contextuality has previously been linked to advantages in random access coding we focus here on a different characteristic called sequential contextuality. It is shown not only to be necessary and sufficient for quantum advantage, but also to quantify the degree of advantage. Our perfect qutrit strategy for the Torpedo Game entails the strongest type of inconsistency with non-contextual hidden variables, revealing logical paradoxes with respect to those assumptions.
arXiv comment15 pages, 11 figures; new presentation, additional figures and references
References in corpus (48)
- Information Causality as a Physical Principle
- A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
- Contextuality for preparations, transformations, and unsharp measurements
- Contextuality supplies the magic for quantum computation
- The Resource Theory of Stabilizer Computation
- Positive Wigner functions render classical simulation of quantum computation efficient
- The Sheaf-Theoretic Structure Of Non-Locality and Contextuality
- Discrete phase space based on finite fields
- State-independent experimental test of quantum contextuality
- Negative Quasi-Probability as a Resource for Quantum Computation
- Graph-Theoretic Approach to Quantum Correlations
- Hudson's Theorem for finite-dimensional quantum systems
- Device-independent tests of classical and quantum dimensions
- Experimental non-classicality of an indivisible quantum system
- SIC-POVMs and the Extended Clifford Group
- State-independent quantum contextuality with single photons
- Preparation contextuality powers parity-oblivious multiplexing
- Estimating outcome probabilities of quantum circuits using quasiprobabilities
- The contextual fraction as a measure of contextuality
- Contextuality as a resource for models of quantum computation on qubits
- Wigner function negativity and contextuality in quantum computation on rebits
- Quantum Random Access Codes using Single -level Systems
- Discrete Wigner functions and quantum computational speedup
- Contextual advantage for state discrimination
- Compatibility and noncontextuality for sequential measurements
- Self-testing mutually unbiased bases in the prepare-and-measure scenario
- Optimal bounds for parity-oblivious random access codes
- Equivalence between contextuality and negativity of the Wigner function for qudits
- State independent contextuality advances one-way communication
- A Kochen-Specker inequality from a SIC
- Enabling computation of correlation bounds for finite-dimensional quantum systems via symmetrisation
- Connections Between Mutually Unbiased Bases and Quantum Random Access Codes
- Quantum Advantage from Sequential-Transformation Contextuality
- Communication games reveal preparation contextuality
- Characterizing finite-dimensional quantum behavior
- Noise Thresholds for Higher Dimensional Systems using the Discrete Wigner Function
- Extrema of discrete Wigner functions and applications
- When Are Popescu-Rohrlich Boxes and Random Access Codes Equivalent?
- Limited preparation contextuality in quantum theory and its relation to the Cirel'son bound
- Nonlocality, steering and quantum state tomography in a single experiment
- Spectra of phase point operators in odd prime dimensions and the extended Clifford group
- Mutually Unbiased Balanced Functions & Generalized Random Access Codes
- Classical multiparty computation using quantum resources
- State-injection schemes of quantum computation in Spekkens' toy theory
- Tsirelson's bound and Landauer's principle in a single-system game
- Quantum Random Access Codes for Boolean Functions
- Consequences and applications of the completeness of Hardy's nonlocality
- Classical codes in quantum state space
Cited by in corpus (13)
- Quantum contextuality provides communication complexity advantage
- Characterising and bounding the set of quantum behaviours in contextuality scenarios
- Entanglement in prepare-and-measure scenarios: many questions, a few answers
- Simple Information Processing Tasks with Unbounded Quantum Advantage
- Tight bounds for antidistinguishability and circulant sets of pure quantum states
- Closing Bell: Boxing black box simulations in the resource theory of contextuality
- Connecting XOR and XOR* games
- Maximal Elements of Quantum Communication
- Higher-dimensional symmetric informationally complete measurement via programmable photonic integrated optics
- Harvesting Contextuality from the Vacuum
- Demonstration of universal contextuality through communication games free of both operational inequivalence and compatibility loopholes
- The Interplay between Quantum Contextuality and Wigner Negativity
- Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits