Quantum Advantage in Information Retrieval

Pierre-Emmanuel Emeriau, Mark Howard, Shane Mansfield

Published 2020-07-30Version 1

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 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.