Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2007.15643 · PRX Quantum

Quantum Advantage in Information Retrieval

Pierre-Emmanuel Emeriau, Mark Howard, Shane Mansfield

Published Apr 11, 2022• 29 citations
arXivHTMLPDF

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 noncontextual hidden variables, revealing logical paradoxes with respect to those assumptions.

DOI
10.1103/prxquantum.3.020307

Related papers

Role of fine-grained uncertainty in determining the limit of preparation contextuality

Gautam Sharma, Sk Sazim, Shiladitya Mal

The optimal success probability of a communication game sets fundamental limitations on an operational theory. The quantum advantage of a parity oblivious random access code (PORAC), a communication game, over classical resources reveals the preparation contextuality of quantum theory [R. W. Spekkens et al., Phys. Rev. Lett. 102, 010401 (2009)]. The optimal quantum advantage in the $N$-dit PORAC game for finite dimensions is an open problem. Here, we show that the degree of uncertainty allowed in an operational theory determines the amount of preparation contextuality. We connect the upper bound of the fine-grained uncertainty relation to the success probability of a PORAC game played with the quantum resource. Subsequently, we find the optimal success probability for a 2-dit PORAC game using mutually unbiased bases for the decoding strategy. Finally, we also derive an upper bound on the quantum advantage for the $N$-dit PORAC game.

arXiv:1905.09695•Physical Review A•Sep 28, 2021•8 citations

Perfect Games in Dimension-Bounded Communication

Emmanuel Zambrini Cruzeiro

Perfect prepare-and-measure games exhibit an all-or-nothing quantum advantage: a quantum system of dimension $d$ satisfies every prescribed winning constraint, whereas a classical $d$-level message cannot. We establish three structural results for such forbidden-output support constraints. First, every binary-output support game reduces exactly to a conflict graph: perfect classical realization with a $d$-level message is equivalent to $d$-colorability, perfect $d$-dimensional quantum realization is equivalent to a $d$-dimensional orthogonal representation, and the minimum number of Bob inputs realizing a fixed conflict graph is its edge biclique-cover number. Second, for an arbitrary finite output alphabet, every perfect qubit strategy admits a perfect classical-bit realization. Third, with at most two Bob inputs every perfect qutrit strategy admits a perfect classical-trit realization. An explicit seven-preparation qutrit game with three Bob inputs satisfies $C_3=20<Q_3=S=21$, so three Bob inputs are necessary and sufficient in dimension three. Conversely, a two-input, six-output game in dimension five satisfies $C_5=39<Q_5=S=40$. Thus the smallest dimension admitting a two-input perfect same-dimensional separation is either four or five; the four-dimensional case remains open. As a flagship binary application, the $13$-ray qutrit graph yields a compressed game $(X,Y,B)=(13,8,2)$ with $C_3=39<Q_3=S=40$, and eight Bob inputs are minimal among all binary-output realizations of that graph. Graph extensions demonstrate the mechanism in every dimension, while Torpedo and antidistinguishability games illustrate the genuinely nonbinary regime. These results connect exact communication, graph coloring, contextuality, state exclusion, and zero-error information theory.

quant-pharXiv:2608.05092•Aug 6, 2026•2 citations

Sequential vs parallel Strategies for Sharing Quantum Advantage in Communication Tasks

Satyaki Manna, Arindam Mitra, Sumit Mukherjee

Information can be extracted from a quantum system in a sustainable manner, allowing the system to be reused for further information extraction through subsequent interactions. We investigate the possibility of consensus between two experimentally feasible methods, namely, parallel and sequential sharing, that enable multiple observers to extract information encoded in a quantum system. We show that any statistics generated by a parallel sharing strategy can be reproduced by a sequential strategy when only two observers are involved. However, when more than two observers participate in sharing quantum correlations, certain statistics achievable through parallel strategies cannot be reproduced by sequential strategies. Moreover, we demonstrate that sharing quantum advantage through a parallel strategy is impossible for a class of communication tasks involving two decoding measurements, thereby establishing an arbitrarily large gap between the sustainability of quantum advantage under sequential and parallel strategies. This naturally raises the question of whether this impossibility extends to communication tasks involving more than two decoding measurements. We show that, while parallel sharing of quantum advantage is impossible in a 3-bit random access code (RAC), it becomes possible in a 3-bit parity-oblivious RAC, where at most two observers can simultaneously obtain a quantum advantage by performing measurements on two imperfect clones of the initially prepared quantum system. Our findings have potential applications in the development of quantum communication networks and distributed quantum information processing.

arXiv:2611.12753•Nov 9, 2026•0 citations

Intraparticle entanglement-based Random Access Code protocols: Contextuality-enabled quantum advantage and implications

Nilaj Saha, Sumit Mukherjee, Dipankar Home

We provide the first explicit identification and quantitative characterization of the physical origin of the quantum advantage in the Random Access Code (RAC) protocol. This is achieved by formulating the protocol in terms of intraparticle entanglement between co-measurable degrees of freedom of a single particle and establishing a fundamental correspondence between the protocol's success probability and the underlying resource powering it. For this purpose, we use a relevant Bell-type inequality derived from the assumption of noncontextuality of measurement outcomes. The formulated analysis reveals that the magnitude of quantum-mechanical violation of this inequality, signifying a form of quantum contextuality, is quantitatively commensurate with the ``quantum enhancement" of success probability in any intraparticle entanglement-assisted $n$-bit RAC protocol. In particular, the maximal success probability achievable in a quantum $n \mapsto 1$ RAC protocol corresponds to the maximal quantum violation of the relevant Bell-type inequality. Our framework not only demonstrates how quantum contextuality entailed by intraparticle entanglement serves as an effective resource for enhancing RAC performance, but also offers a significant operational advantage: the proposed scheme is readily implementable in a single-particle interferometric setup requiring coherence preservation only for a single particle, rather than between spatially separated entangled systems.

quant-pharXiv:2605.13350•May 14, 2026•0 citations

Unbounded Communication Power of a Qubit

Souradeep Sasmal, Som Kanjilal, Debarshi Das

Quantum mechanics enables information-processing advantages even at the level of a single qubit. A paradigmatic example is the 2$\to$1 random access code (RAC), where a qubit outperforms a classical bit in retrieving encoded information. In the standard form, however, this quantum advantage is restricted to a single receiver, since decoding measurements inevitably destroy the encoded information. Contrary to this, we address how long the information encoded in a single qubit remains accessible even after multiple decoding, each with a quantum advantage. Introducing preparation distinguishability as an operational resource associated with the sender, we show that its interplay with measurement incompatibility on the receiver's side can mitigate measurement-induced disturbance, thereby enabling an arbitrarily long sequence of receivers to each retain a quantum advantage. Our results show that, even under repeated measurements, the information encoded in a qubit need not be entirely exhausted, revealing a stronger communication feature than previously recognised.

quant-pharXiv:2605.16093•May 18, 2026•4 citations

Quantum advantages in (n,d) ↦ 1 random access codes

Andris Ambainis, Dmitry Kravchenko, Sk Sazim +2 more

Abstract A random access code (RAC), corresponding to a communication primitive with various applications in quantum information theory, is an instance of a preparation-and-measurement scenario. In this work, we consider (n, d)-RACs constituting an n-length string, constructed from a d size set of letters, and send an encoding of the string in a single d-level physical system and present their quantum advantages. We first characterize optimal classical RACs and prove that a known classical strategy, called majority-encoding-identity-decoding, is optimal. We then construct a quantum protocol by exploiting only two incompatible measurements (the minimal requirement) and show the advantages beyond the classical one. We also discuss the generality of our results and whether quantum advantages are valid for all types of ( n , d ) ↦ 1 RACs.

arXiv:1510.03045•New Journal of Physics•Dec 1, 2024•18 citations
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 noncontextual hidden variables, revealing logical paradoxes with respect to those assumptions.
The optimal success probability of a communication game sets fundamental limitations on an operational theory. The quantum advantage of a parity oblivious random access code (PORAC), a communication game, over classical resources reveals the preparation contextuality of quantum theory [R. W. Spekkens et al., Phys. Rev. Lett. 102, 010401 (2009)]. The optimal quantum advantage in the NNN-dit PORAC game for finite dimensions is an open problem. Here, we show that the degree of uncertainty allowed in an operational theory determines the amount of preparation contextuality. We connect the upper bound of the fine-grained uncertainty relation to the success probability of a PORAC game played with the quantum resource. Subsequently, we find the optimal success probability for a 2-dit PORAC game using mutually unbiased bases for the decoding strategy. Finally, we also derive an upper bound on the quantum advantage for the NNN-dit PORAC game.
Perfect prepare-and-measure games exhibit an all-or-nothing quantum advantage: a quantum system of dimension ddd satisfies every prescribed winning constraint, whereas a classical ddd-level message cannot. We establish three structural results for such forbidden-output support constraints. First, every binary-output support game reduces exactly to a conflict graph: perfect classical realization with a ddd-level message is equivalent to ddd-colorability, perfect ddd-dimensional quantum realization is equivalent to a ddd-dimensional orthogonal representation, and the minimum number of Bob inputs realizing a fixed conflict graph is its edge biclique-cover number. Second, for an arbitrary finite output alphabet, every perfect qubit strategy admits a perfect classical-bit realization. Third, with at most two Bob inputs every perfect qutrit strategy admits a perfect classical-trit realization. An explicit seven-preparation qutrit game with three Bob inputs satisfies C3=20<Q3=S=21C_3=20<Q_3=S=21C3​=20<Q3​=S=21, so three Bob inputs are necessary and sufficient in dimension three. Conversely, a two-input, six-output game in dimension five satisfies C5=39<Q5=S=40C_5=39<Q_5=S=40C5​=39<Q5​=S=40. Thus the smallest dimension admitting a two-input perfect same-dimensional separation is either four or five; the four-dimensional case remains open. As a flagship binary application, the 131313-ray qutrit graph yields a compressed game (X,Y,B)=(13,8,2)(X,Y,B)=(13,8,2)(X,Y,B)=(13,8,2) with C3=39<Q3=S=40C_3=39<Q_3=S=40C3​=39<Q3​=S=40, and eight Bob inputs are minimal among all binary-output realizations of that graph. Graph extensions demonstrate the mechanism in every dimension, while Torpedo and antidistinguishability games illustrate the genuinely nonbinary regime. These results connect exact communication, graph coloring, contextuality, state exclusion, and zero-error information theory.
Information can be extracted from a quantum system in a sustainable manner, allowing the system to be reused for further information extraction through subsequent interactions. We investigate the possibility of consensus between two experimentally feasible methods, namely, parallel and sequential sharing, that enable multiple observers to extract information encoded in a quantum system. We show that any statistics generated by a parallel sharing strategy can be reproduced by a sequential strategy when only two observers are involved. However, when more than two observers participate in sharing quantum correlations, certain statistics achievable through parallel strategies cannot be reproduced by sequential strategies. Moreover, we demonstrate that sharing quantum advantage through a parallel strategy is impossible for a class of communication tasks involving two decoding measurements, thereby establishing an arbitrarily large gap between the sustainability of quantum advantage under sequential and parallel strategies. This naturally raises the question of whether this impossibility extends to communication tasks involving more than two decoding measurements. We show that, while parallel sharing of quantum advantage is impossible in a 3-bit random access code (RAC), it becomes possible in a 3-bit parity-oblivious RAC, where at most two observers can simultaneously obtain a quantum advantage by performing measurements on two imperfect clones of the initially prepared quantum system. Our findings have potential applications in the development of quantum communication networks and distributed quantum information processing.
We provide the first explicit identification and quantitative characterization of the physical origin of the quantum advantage in the Random Access Code (RAC) protocol. This is achieved by formulating the protocol in terms of intraparticle entanglement between co-measurable degrees of freedom of a single particle and establishing a fundamental correspondence between the protocol's success probability and the underlying resource powering it. For this purpose, we use a relevant Bell-type inequality derived from the assumption of noncontextuality of measurement outcomes. The formulated analysis reveals that the magnitude of quantum-mechanical violation of this inequality, signifying a form of quantum contextuality, is quantitatively commensurate with the ``quantum enhancement" of success probability in any intraparticle entanglement-assisted nnn-bit RAC protocol. In particular, the maximal success probability achievable in a quantum n↦1n \mapsto 1n↦1 RAC protocol corresponds to the maximal quantum violation of the relevant Bell-type inequality. Our framework not only demonstrates how quantum contextuality entailed by intraparticle entanglement serves as an effective resource for enhancing RAC performance, but also offers a significant operational advantage: the proposed scheme is readily implementable in a single-particle interferometric setup requiring coherence preservation only for a single particle, rather than between spatially separated entangled systems.
Quantum mechanics enables information-processing advantages even at the level of a single qubit. A paradigmatic example is the 2$\to$1 random access code (RAC), where a qubit outperforms a classical bit in retrieving encoded information. In the standard form, however, this quantum advantage is restricted to a single receiver, since decoding measurements inevitably destroy the encoded information. Contrary to this, we address how long the information encoded in a single qubit remains accessible even after multiple decoding, each with a quantum advantage. Introducing preparation distinguishability as an operational resource associated with the sender, we show that its interplay with measurement incompatibility on the receiver's side can mitigate measurement-induced disturbance, thereby enabling an arbitrarily long sequence of receivers to each retain a quantum advantage. Our results show that, even under repeated measurements, the information encoded in a qubit need not be entirely exhausted, revealing a stronger communication feature than previously recognised.
Abstract A random access code (RAC), corresponding to a communication primitive with various applications in quantum information theory, is an instance of a preparation-and-measurement scenario. In this work, we consider (n, d)-RACs constituting an n-length string, constructed from a d size set of letters, and send an encoding of the string in a single d-level physical system and present their quantum advantages. We first characterize optimal classical RACs and prove that a known classical strategy, called majority-encoding-identity-decoding, is optimal. We then construct a quantum protocol by exploiting only two incompatible measurements (the minimal requirement) and show the advantages beyond the classical one. We also discuss the generality of our results and whether quantum advantages are valid for all types of ( n , d ) ↦ 1 RACs.