Quantum Advantage in Information Retrieval

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.

15 pages, 11 figures; new presentation, additional figures and references

References in corpus (18)

• A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
• State-independent experimental test of quantum contextuality
• Device-independent tests of classical and quantum dimensions
• Experimental non-classicality of an indivisible quantum system
• State-independent quantum contextuality with single photons
• Preparation contextuality powers parity-oblivious multiplexing
• The contextual fraction as a measure of contextuality
• Wigner function negativity and contextuality in quantum computation on rebits
• Quantum Random Access Codes using Single $d$-level Systems
• Discrete Wigner functions and quantum computational speedup
• Noise Thresholds for Higher Dimensional Systems using the Discrete Wigner Function
• Extrema of discrete Wigner functions and applications
• Nonlocality, steering and quantum state tomography in a single experiment
• Spectra of phase point operators in odd prime dimensions and the extended Clifford group
• Classical multiparty computation using quantum resources
• Mutually Unbiased Balanced Functions & Generalized Random Access Codes
• Quantum Random Access Codes for Boolean Functions
• Consequences and applications of the completeness of Hardy's nonlocality

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