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:2607.10273

Certified quantum supremacy in entanglement-assisted prepare-measure random-access-code

Rajdeep Paul, Prabuddha Roy, A. K. Pan

quant-phSubmitted Jul 11, 2026• Announced Jul 14, 2026• 0 citations
arXivHTMLPDF

Abstract

We develop a family of semi-device-independent (SDI) entanglement-assisted prepare-measure (PM) communication games involving two parties, within the $n\rightarrow l$ random-access code (RAC) framework where the sender Alice holds a n-bit string and communicates $l<n$ bits or qubits to the receiver Bob. In contrast to the standard quantum PMRAC, here the parties share a prior entanglement, and Alice applies quantum operations on her sub-system to encode her inputs and sends to Bob. We first consider the $4\rightarrow l$ entanglement-assisted PMRAC with $l=1$ and $2$ and derive the optimal quantum success probabilities using an elegant analytical technique. We demonstrate quantum supremacy over both classical RACs and conventional quantum PMRACs. Moreover, we exhibit that the optimal quantum advantage allows one to certify Alice's unitary operations. We then derive an upper bound on the quantum success probabilities for $5\rightarrow l$ entanglement-assisted PMRAC with $l=1,2$ and $3$. Further, we extend the demonstration of quantum advantage for $n\rightarrow n-2$ case where n is arbitrary.

Related papers

Semi-device-independent self-testing of unitary operations

Rajdeep Paul, Prabuddha Roy, A. K. Pan

We present a hitherto unexplored semi-device-independent (SDI) self-testing protocol designed to certify unitary operations within a variant of prepare-measure framework. We consider a communication game which we refer to as a variant of $3$-bit prepare-measure random access code (PMRAC) involving two parties, Alice and Bob, who share a prior two-qubit quantum state. Alice encodes her message by applying unitary operations on her subsystem and sends it to Bob. To decode the message, Bob performs a measurement on the whole system. We demonstrate that the optimal quantum advantage of the variant of $3$-bit PMRAC over the classical bound enables the self-testing of Alice's unitary operations and Bob's measurements. The derivation of the optimal quantum success probability is fully analytical. The approach is so elegant that it can be generalized for any arbitrary $n$-bit PMRAC and may also be extended to other prepare-measure communication games.

quant-pharXiv:2604.19911•Physical Review A•Apr 23, 2026•1 citation

Certified quantum advantage in entanglement-assisted prepare-measure random-access-code

Rajdeep Paul, Prabuddha Roy, A. K. Pan

Abstract We develop a family of semi-device-independent (SDI) entanglement-assisted prepare-measure (PM) communication games involving two parties, within the n → l random-access code (RAC) framework where the sender Alice holds a n -bit string and communicates l < n bits or qubits to the receiver Bob. In contrast to the standard quantum PMRAC, here the parties share a prior entanglement, and Alice applies quantum operations on her sub-system to encode her inputs and sends to Bob. We first consider the 4 → l entanglement-assisted PMRAC with l = 1 and 2 and derive the optimal quantum success probabilities using an elegant analytical technique. We demonstrate quantum supremacy over both classical RACs and conventional quantum PMRACs. Moreover, we exhibit that the optimal quantum advantage allows one to certify Alice’s unitary operations. We then derive an upper bound on the quantum success probabilities for 5 → l entanglement-assisted PMRAC with l = 1 , 2 and 3 . Further, we extend the demonstration of quantum advantage for n → n − 2 case where n is arbitrary.

New Journal of Physics•Sep 21, 2026•0 citations

Sufficient conditions for quantum advantage in random access code protocols with two-qubit states

Som Kanjilal, Chellasamy Jebarathinam, Tomasz Paterek +1 more

A random access code (RAC) is an important communication protocol to obtain information about a randomly specified substring of an $n$-bit string, while only having limited information about the $n$-bit string. Quantum RACs usually utilize either communication of quantum bits or a shared-in-advance quantum state used in conjunction with classical communication. Here we consider the latter version of the quantum protocols under the constraint of single-bit communication and with a shared arbitrary state of two qubits. Taking the worst-case success probability as the figure of merit, we demonstrate that any state with an invertible correlation matrix can be used to outperform the best classical RAC for $n=3$. We derive an additional condition sufficient to beat the best classical performance in the case of $n=2$. In particular, separable states turn out to be a useful resource behind the quantum advantage for $n=2,3$. For $n\ensuremath{\ge}4$, RACs assisted with a single copy of a quantum state do not outperform the classical RACs.

arXiv:1912.09900•Physical Review A•Jul 19, 2023•5 citations

Optimal bounds for parity-oblivious random access codes

André Chailloux, Iordanis Kerenidis, Srijita Kundu +1 more

Random access coding is an information task that has been extensively studied and found many applications in quantum information. In this scenario, Alice receives an n -bit string x , and wishes to encode x into a quantum state , such that Bob, when receiving the state , can choose any bit and recover the input bit x i with high probability. Here we study two variants: parity-oblivious random access codes (RACs), where we impose the cryptographic property that Bob cannot infer any information about the parity of any subset of bits of the input apart from the single bits x i ; and even-parity-oblivious RACs, where Bob cannot infer any information about the parity of any even-size subset of bits of the input. In this paper, we provide the optimal bounds for parity-oblivious quantum RACs and show that they are asymptotically better than the optimal classical ones. Our results provide a large non-contextuality inequality violation and resolve the main open problem in a work of Spekkens et al (2009 Phys. Rev. Lett. 102 010401 ). Second, we provide the optimal bounds for even-parity-oblivious RACs by proving their equivalence to a non-local game and by providing tight bounds for the success probability of the non-local game via semidefinite programming. In the case of even-parity-oblivious RACs, the cryptographic property holds also in the device independent model.

arXiv:1404.5153•New Journal of Physics•Apr 8, 2016•85 citations

Random Access Codes: Explicit Constructions, Optimality, and Classical-Quantum Gaps

Ruho Kondo, Yuki Sato, Hiroshi Yano +3 more

A random access code (RAC) encodes an $L$-bit string into a $k$-bit message, $L>k$, so that any requested bit can be recovered with high probability; a quantum RAC (QRAC) uses $k$ qubits instead. We give a geometric characterization of optimal classical $(L,k)$-RACs under average and worst-case decoding criteria. The average criterion is reduced to choosing $2^k$ representatives in $\{0,1\}^L$, while the worst-case criterion is reduced to a minimax problem over $2^k$ points in $[0,1]^L$ with a distance-like objective. This framework proves optimality for several parameter families, with many optimal constructions arising from standard infinite families of binary linear codes. It also yields two explicit classical--quantum separations. First, for every $L>1$, we construct a $(L,1)$-QRAC whose average decoding success probability strictly exceeds the optimal classical value. Second, for the family $(2^k-1,k)$, we prove worst-case optimality of a classical RAC and construct a QRAC with strictly larger worst-case success probability. For the family $(L,L-1)$, the framework identifies a classical RAC that is average-case optimal and, under a stated conjecture, also worst-case optimal. The same viewpoint further recovers explicit $(L,L-1)$-QRACs attaining a previously conjectured upper-bound value.

quant-pharXiv:2604.21274•Apr 24, 2026•0 citations

Experimental generation of entanglement-assisted quantum random access code

Xiao-Run Wang, Luyan Wu, Chenxi Liu +3 more

$n\ensuremath{\rightarrow}m$ random access code (RAC) is an information task to encode an $n$-bit random message into a shorter $m$-bit string. Resulting from the compression loss from $n$ to $m$ bits, there exists success probabilities for the string receiver to recover any bits of the initial message. It has been shown that success probabilities of bit recovery can be enhanced by employing quantum resources. Here we present experimental realizations of $2\ensuremath{\rightarrow}1$ and $3\ensuremath{\rightarrow}1$ distributed entanglement-assisted random access codes (EARACs) with a two-photon entangled source. The average success probabilities obtained in our experiment are $0.8491(41)$ for a $2\ensuremath{\rightarrow}1$ EARAC and $0.7724(34)$ for a $3\ensuremath{\rightarrow}1$ EARAC, exceeding the classical counterparts, respectively. Moreover, through the existing experimental data, success probabilities for $n$ varying from 4 to 10 ($m=1$) are estimated.

Physical Review A•May 9, 2019•8 citations
We develop a family of semi-device-independent (SDI) entanglement-assisted prepare-measure (PM) communication games involving two parties, within the n→ln\rightarrow ln→l random-access code (RAC) framework where the sender Alice holds a n-bit string and communicates l<nl<nl<n bits or qubits to the receiver Bob. In contrast to the standard quantum PMRAC, here the parties share a prior entanglement, and Alice applies quantum operations on her sub-system to encode her inputs and sends to Bob. We first consider the 4→l4\rightarrow l4→l entanglement-assisted PMRAC with l=1l=1l=1 and 222 and derive the optimal quantum success probabilities using an elegant analytical technique. We demonstrate quantum supremacy over both classical RACs and conventional quantum PMRACs. Moreover, we exhibit that the optimal quantum advantage allows one to certify Alice's unitary operations. We then derive an upper bound on the quantum success probabilities for 5→l5\rightarrow l5→l entanglement-assisted PMRAC with l=1,2l=1,2l=1,2 and 333. Further, we extend the demonstration of quantum advantage for n→n−2n\rightarrow n-2n→n−2 case where n is arbitrary.
We present a hitherto unexplored semi-device-independent (SDI) self-testing protocol designed to certify unitary operations within a variant of prepare-measure framework. We consider a communication game which we refer to as a variant of 333-bit prepare-measure random access code (PMRAC) involving two parties, Alice and Bob, who share a prior two-qubit quantum state. Alice encodes her message by applying unitary operations on her subsystem and sends it to Bob. To decode the message, Bob performs a measurement on the whole system. We demonstrate that the optimal quantum advantage of the variant of 333-bit PMRAC over the classical bound enables the self-testing of Alice's unitary operations and Bob's measurements. The derivation of the optimal quantum success probability is fully analytical. The approach is so elegant that it can be generalized for any arbitrary nnn-bit PMRAC and may also be extended to other prepare-measure communication games.
Abstract We develop a family of semi-device-independent (SDI) entanglement-assisted prepare-measure (PM) communication games involving two parties, within the n → l random-access code (RAC) framework where the sender Alice holds a n -bit string and communicates l < n bits or qubits to the receiver Bob. In contrast to the standard quantum PMRAC, here the parties share a prior entanglement, and Alice applies quantum operations on her sub-system to encode her inputs and sends to Bob. We first consider the 4 → l entanglement-assisted PMRAC with l = 1 and 2 and derive the optimal quantum success probabilities using an elegant analytical technique. We demonstrate quantum supremacy over both classical RACs and conventional quantum PMRACs. Moreover, we exhibit that the optimal quantum advantage allows one to certify Alice’s unitary operations. We then derive an upper bound on the quantum success probabilities for 5 → l entanglement-assisted PMRAC with l = 1 , 2 and 3 . Further, we extend the demonstration of quantum advantage for n → n − 2 case where n is arbitrary.
A random access code (RAC) is an important communication protocol to obtain information about a randomly specified substring of an nnn-bit string, while only having limited information about the nnn-bit string. Quantum RACs usually utilize either communication of quantum bits or a shared-in-advance quantum state used in conjunction with classical communication. Here we consider the latter version of the quantum protocols under the constraint of single-bit communication and with a shared arbitrary state of two qubits. Taking the worst-case success probability as the figure of merit, we demonstrate that any state with an invertible correlation matrix can be used to outperform the best classical RAC for n=3n=3n=3. We derive an additional condition sufficient to beat the best classical performance in the case of n=2n=2n=2. In particular, separable states turn out to be a useful resource behind the quantum advantage for n=2,3n=2,3n=2,3. For $n\ensuremath{\ge}4$, RACs assisted with a single copy of a quantum state do not outperform the classical RACs.
Random access coding is an information task that has been extensively studied and found many applications in quantum information. In this scenario, Alice receives an n -bit string x , and wishes to encode x into a quantum state , such that Bob, when receiving the state , can choose any bit and recover the input bit x i with high probability. Here we study two variants: parity-oblivious random access codes (RACs), where we impose the cryptographic property that Bob cannot infer any information about the parity of any subset of bits of the input apart from the single bits x i ; and even-parity-oblivious RACs, where Bob cannot infer any information about the parity of any even-size subset of bits of the input. In this paper, we provide the optimal bounds for parity-oblivious quantum RACs and show that they are asymptotically better than the optimal classical ones. Our results provide a large non-contextuality inequality violation and resolve the main open problem in a work of Spekkens et al (2009 Phys. Rev. Lett. 102 010401 ). Second, we provide the optimal bounds for even-parity-oblivious RACs by proving their equivalence to a non-local game and by providing tight bounds for the success probability of the non-local game via semidefinite programming. In the case of even-parity-oblivious RACs, the cryptographic property holds also in the device independent model.
A random access code (RAC) encodes an LLL-bit string into a kkk-bit message, L>kL>kL>k, so that any requested bit can be recovered with high probability; a quantum RAC (QRAC) uses kkk qubits instead. We give a geometric characterization of optimal classical (L,k)(L,k)(L,k)-RACs under average and worst-case decoding criteria. The average criterion is reduced to choosing 2k2^k2k representatives in {0,1}L\{0,1\}^L{0,1}L, while the worst-case criterion is reduced to a minimax problem over 2k2^k2k points in [0,1]L[0,1]^L[0,1]L with a distance-like objective. This framework proves optimality for several parameter families, with many optimal constructions arising from standard infinite families of binary linear codes. It also yields two explicit classical--quantum separations. First, for every L>1L>1L>1, we construct a (L,1)(L,1)(L,1)-QRAC whose average decoding success probability strictly exceeds the optimal classical value. Second, for the family (2k−1,k)(2^k-1,k)(2k−1,k), we prove worst-case optimality of a classical RAC and construct a QRAC with strictly larger worst-case success probability. For the family (L,L−1)(L,L-1)(L,L−1), the framework identifies a classical RAC that is average-case optimal and, under a stated conjecture, also worst-case optimal. The same viewpoint further recovers explicit (L,L−1)(L,L-1)(L,L−1)-QRACs attaining a previously conjectured upper-bound value.
$n\ensuremath{\rightarrow}m$ random access code (RAC) is an information task to encode an nnn-bit random message into a shorter mmm-bit string. Resulting from the compression loss from nnn to mmm bits, there exists success probabilities for the string receiver to recover any bits of the initial message. It has been shown that success probabilities of bit recovery can be enhanced by employing quantum resources. Here we present experimental realizations of $2\ensuremath{\rightarrow}1$ and $3\ensuremath{\rightarrow}1$ distributed entanglement-assisted random access codes (EARACs) with a two-photon entangled source. The average success probabilities obtained in our experiment are 0.8491(41)0.8491(41)0.8491(41) for a $2\ensuremath{\rightarrow}1$ EARAC and 0.7724(34)0.7724(34)0.7724(34) for a $3\ensuremath{\rightarrow}1$ EARAC, exceeding the classical counterparts, respectively. Moreover, through the existing experimental data, success probabilities for nnn varying from 4 to 10 (m=1m=1m=1) are estimated.