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:0906.0524 · Physical Review A

Entanglement-assisted random access codes

Marcin Pawłowski, Marek Żukowski

Published Apr 27, 2010• 106 citations
arXivHTMLPDF

Abstract

An $(n,m,p)$ random access code (RAC) makes it possible to encode $n$ bits in an $m$-bit message in such a way that a receiver of the message can guess any of the original $n$ bits with probability $p$ greater than $\frac{1}{2}$. In quantum RACs (QRACs), one transmits $n$ qubits. The full set of primitive entanglement-assisted random access codes (EARACs) is introduced, in which parties are allowed to share a two-qubit singlet. It is shown that via a concatenation of these, one can build for any $n$ an $(n,1,p)$ EARAC. QRACs for $n>3$ exist only if parties also share classical randomness. We show that EARACs outperform the best of known QRACs not only in the success probabilities but also in the amount of communication needed in the preparatory stage of the protocol. Upper bounds on the performance of EARACs are given and shown to limit also QRACs.

DOI
10.1103/physreva.81.042326

Related papers

Quantum Random Access Codes for Boolean Functions

João Fernando Doriguello, Ashley Montanaro

An n↦pm random access code (RAC) is an encoding of n bits into m bits such that any initial bit can be recovered with probability at least p , while in a quantum RAC (QRAC), the n bits are encoded into m qubits. Since its proposal, the idea of RACs was generalized in many different ways, e.g. allowing the use of shared entanglement (called entanglement-assisted random access code, or simply EARAC) or recovering multiple bits instead of one. In this paper we generalize the idea of RACs to recovering the value of a given Boolean function f on any subset of fixed size of the initial bits, which we call f -random access codes. We study and give protocols for f -random access codes with classical ( f -RAC) and quantum ( f -QRAC) encoding, together with many different resources, e.g. private or shared randomness, shared entanglement ( f -EARAC) and Popescu-Rohrlich boxes ( f -PRRAC). The success probability of our protocols is characterized by the noise stability of the Boolean function f . Moreover, we give an upper bound on the success probability of any f -QRAC with shared randomness that matches its success probability up to a multiplicative constant (and f -RACs by extension), meaning that quantum protocols can only achieve a limited advantage over their classical counterparts.

arXiv:2011.06535•Quantum•Mar 7, 2021•20 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

Complementarity between entanglement-assisted and quantum distributed random access code

Alley Hameedi, Debashis Saha, Piotr Mironowicz +2 more

Collaborative communication tasks such as random access codes (RACs) employing quantum resources have manifested great potential in enhancing information processing capabilities beyond the classical limitations. The two quantum variants of RACs, namely, quantum random access code (QRAC) and the entanglement-assisted random access code (EARAC), have demonstrated equal prowess for a number of tasks. However, there do exist specific cases where one outperforms the other. In this article, we study a family of $3\ensuremath{\rightarrow}1$ distributed RACs [J. Bowles, N. Brunner, and M. Paw\l{}owski, Phys. Rev. A 92, 022351 (2015)] and present its general construction of both the QRAC and the EARAC. We demonstrate that, depending on the function of inputs that is sought, if QRAC achieves the maximal success probability then EARAC fails to do so and vice versa. Moreover, a tripartite Bell-type inequality associated with the EARAC variants reveals the genuine multipartite nonlocality exhibited by our protocol. We conclude with an experimental realization of the $3\ensuremath{\rightarrow}1$ distributed QRAC that achieves higher success probabilities than the maximum possible with EARACs for a number of tasks.

arXiv:1701.08713•Physical Review A•May 25, 2017•25 citations

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

Rajdeep Paul, Prabuddha Roy, A. K. Pan

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.

quant-pharXiv:2607.10273•New Journal of Physics•Jul 14, 2026•0 citations

Quantum Random Access Codes encoding every possible number of bits into m qubits

Ola Liabøtrø

A (Quantum) Random Access Code ((Q)RAC) is a scheme that encodes $n$ bits into $m$ (qu)bits such that any of the $n$ bits can be recovered with a worst case probability $p>\frac{1}{2}$. Such a code is denoted by the triple $(n,m,p)$. It is known that $n<4^m$ for all QRACs and $n<2^m$ for classical RACs. These bounds are also known to be tight, as explicit constructions exist for $n=4^m-1$ and $n=2^m-1$ for quantum and classical codes respectively. We generalize (Q)RACs to a scheme encoding $n$ $d$-levels into $m$ (qu)-$d$-levels such that any $d$-level can be recovered with the probability for every wrong outcome value being less than $\frac{1}{d}$. We construct explicit solutions for all $n\leq \frac{d^{2m}-1}{d-1}$. For $d=2$, the constructions coincide with those previously known. We show that the (Q)RACs are $d$-parity-oblivious, generalizing ordinary parity-obliviousness. We further investigate optimization of the success probabilities. For $d=2$, we use the measure operators of the previously best known solutions, but improve the encoding states to give a higher success probability. We conjecture that for maximal $(n=4^m-1,m,p)$ QRACs, $p=\frac{1+\frac{1}{(\sqrt{3}+1)^m-1}}{2}$ is possible and show that it is an upper bound for the measure operators that we use. When we compare $(n,m,p_q)$ QRACs with classical $(n,2m,p_c)$ RACs, we can always find $p_q\geq p_c$, but the classical code gives information about every input bit simultaneously, while the QRAC only gives information about a subset. For several different $(n,2,p)$ QRACs, we see the same trade-off, as the best $p$ values are obtained when the number of bits that can be obtained simultaneously is as small as possible. The trade-off is connected to parity-obliviousness, since high certainty information about several bits can be used to calculate probabilities for parities of subsets.

•Jul 9, 2016•0 citations

Improved classical and quantum random access codes

Ola Liabøtrø

A (quantum) random access code ((Q)RAC) is a scheme that encodes $n$ bits into $m$ (qu)bits such that any of the $n$ bits can be recovered with a worst case probability $p>\frac{1}{2}$. We generalize (Q)RACs to a scheme encoding $n$ $d$-levels into $m$ (quantum) $d$-levels such that any $d$-level can be recovered with the probability for every wrong outcome value being less than $\frac{1}{d}$. We construct explicit solutions for all $n\ensuremath{\le}\frac{{d}^{2m}\ensuremath{-}1}{d\ensuremath{-}1}$. For $d=2$, the constructions coincide with those previously known. We show that the (Q)RACs are $d$-parity oblivious, generalizing ordinary parity obliviousness. We further investigate optimization of the success probabilities. For $d=2$, we use the measure operators of the previously best-known solutions, but improve the encoding states to give a higher success probability. We conjecture that for maximal $(n={4}^{m}\ensuremath{-}1,m,p)$ QRACs, $p=\frac{1}{2}{1+{[{(\sqrt{3}+1)}^{m}\ensuremath{-}1]}^{\ensuremath{-}1}}$ is possible, and show that it is an upper bound for the measure operators that we use. We then compare $(n,m,{p}_{q})$ QRACs with classical $(n,2m,{p}_{c})$ RACs. We can always find ${p}_{q}\ensuremath{\ge}{p}_{c}$, but the classical code gives information about every input bit simultaneously, while the QRAC only gives information about a subset. For several different $(n,2,p)$ QRACs, we see the same trade-off, as the best $p$ values are obtained when the number of bits that can be obtained simultaneously is as small as possible. The trade-off is connected to parity obliviousness, since high certainty information about several bits can be used to calculate probabilities for parities of subsets.

arXiv:1607.02667•Physical Review A•May 8, 2017•22 citations
An (n,m,p)(n,m,p)(n,m,p) random access code (RAC) makes it possible to encode nnn bits in an mmm-bit message in such a way that a receiver of the message can guess any of the original nnn bits with probability ppp greater than 12\frac{1}{2}21​. In quantum RACs (QRACs), one transmits nnn qubits. The full set of primitive entanglement-assisted random access codes (EARACs) is introduced, in which parties are allowed to share a two-qubit singlet. It is shown that via a concatenation of these, one can build for any nnn an (n,1,p)(n,1,p)(n,1,p) EARAC. QRACs for n>3n>3n>3 exist only if parties also share classical randomness. We show that EARACs outperform the best of known QRACs not only in the success probabilities but also in the amount of communication needed in the preparatory stage of the protocol. Upper bounds on the performance of EARACs are given and shown to limit also QRACs.
An n↦pm random access code (RAC) is an encoding of n bits into m bits such that any initial bit can be recovered with probability at least p , while in a quantum RAC (QRAC), the n bits are encoded into m qubits. Since its proposal, the idea of RACs was generalized in many different ways, e.g. allowing the use of shared entanglement (called entanglement-assisted random access code, or simply EARAC) or recovering multiple bits instead of one. In this paper we generalize the idea of RACs to recovering the value of a given Boolean function f on any subset of fixed size of the initial bits, which we call f -random access codes. We study and give protocols for f -random access codes with classical ( f -RAC) and quantum ( f -QRAC) encoding, together with many different resources, e.g. private or shared randomness, shared entanglement ( f -EARAC) and Popescu-Rohrlich boxes ( f -PRRAC). The success probability of our protocols is characterized by the noise stability of the Boolean function f . Moreover, we give an upper bound on the success probability of any f -QRAC with shared randomness that matches its success probability up to a multiplicative constant (and f -RACs by extension), meaning that quantum protocols can only achieve a limited advantage over their classical counterparts.
$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.
Collaborative communication tasks such as random access codes (RACs) employing quantum resources have manifested great potential in enhancing information processing capabilities beyond the classical limitations. The two quantum variants of RACs, namely, quantum random access code (QRAC) and the entanglement-assisted random access code (EARAC), have demonstrated equal prowess for a number of tasks. However, there do exist specific cases where one outperforms the other. In this article, we study a family of $3\ensuremath{\rightarrow}1$ distributed RACs [J. Bowles, N. Brunner, and M. Paw\l{}owski, Phys. Rev. A 92, 022351 (2015)] and present its general construction of both the QRAC and the EARAC. We demonstrate that, depending on the function of inputs that is sought, if QRAC achieves the maximal success probability then EARAC fails to do so and vice versa. Moreover, a tripartite Bell-type inequality associated with the EARAC variants reveals the genuine multipartite nonlocality exhibited by our protocol. We conclude with an experimental realization of the $3\ensuremath{\rightarrow}1$ distributed QRAC that achieves higher success probabilities than the maximum possible with EARACs for a number of tasks.
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.
A (Quantum) Random Access Code ((Q)RAC) is a scheme that encodes nnn bits into mmm (qu)bits such that any of the nnn bits can be recovered with a worst case probability p>12p>\frac{1}{2}p>21​. Such a code is denoted by the triple (n,m,p)(n,m,p)(n,m,p). It is known that n<4mn<4^mn<4m for all QRACs and n<2mn<2^mn<2m for classical RACs. These bounds are also known to be tight, as explicit constructions exist for n=4m−1n=4^m-1n=4m−1 and n=2m−1n=2^m-1n=2m−1 for quantum and classical codes respectively. We generalize (Q)RACs to a scheme encoding nnn ddd-levels into mmm (qu)-ddd-levels such that any ddd-level can be recovered with the probability for every wrong outcome value being less than 1d\frac{1}{d}d1​. We construct explicit solutions for all n≤d2m−1d−1n\leq \frac{d^{2m}-1}{d-1}n≤d−1d2m−1​. For d=2d=2d=2, the constructions coincide with those previously known. We show that the (Q)RACs are ddd-parity-oblivious, generalizing ordinary parity-obliviousness. We further investigate optimization of the success probabilities. For d=2d=2d=2, we use the measure operators of the previously best known solutions, but improve the encoding states to give a higher success probability. We conjecture that for maximal (n=4m−1,m,p)(n=4^m-1,m,p)(n=4m−1,m,p) QRACs, p=1+1(3+1)m−12p=\frac{1+\frac{1}{(\sqrt{3}+1)^m-1}}{2}p=21+(3​+1)m−11​​ is possible and show that it is an upper bound for the measure operators that we use. When we compare (n,m,pq)(n,m,p_q)(n,m,pq​) QRACs with classical (n,2m,pc)(n,2m,p_c)(n,2m,pc​) RACs, we can always find pq≥pcp_q\geq p_cpq​≥pc​, but the classical code gives information about every input bit simultaneously, while the QRAC only gives information about a subset. For several different (n,2,p)(n,2,p)(n,2,p) QRACs, we see the same trade-off, as the best ppp values are obtained when the number of bits that can be obtained simultaneously is as small as possible. The trade-off is connected to parity-obliviousness, since high certainty information about several bits can be used to calculate probabilities for parities of subsets.
A (quantum) random access code ((Q)RAC) is a scheme that encodes nnn bits into mmm (qu)bits such that any of the nnn bits can be recovered with a worst case probability p>12p>\frac{1}{2}p>21​. We generalize (Q)RACs to a scheme encoding nnn ddd-levels into mmm (quantum) ddd-levels such that any ddd-level can be recovered with the probability for every wrong outcome value being less than 1d\frac{1}{d}d1​. We construct explicit solutions for all $n\ensuremath{\le}\frac{{d}^{2m}\ensuremath{-}1}{d\ensuremath{-}1}$. For d=2d=2d=2, the constructions coincide with those previously known. We show that the (Q)RACs are ddd-parity oblivious, generalizing ordinary parity obliviousness. We further investigate optimization of the success probabilities. For d=2d=2d=2, we use the measure operators of the previously best-known solutions, but improve the encoding states to give a higher success probability. We conjecture that for maximal $(n={4}^{m}\ensuremath{-}1,m,p)$ QRACs, $p=\frac{1}{2}{1+{[{(\sqrt{3}+1)}^{m}\ensuremath{-}1]}^{\ensuremath{-}1}}$ is possible, and show that it is an upper bound for the measure operators that we use. We then compare (n,m,pq)(n,m,{p}_{q})(n,m,pq​) QRACs with classical (n,2m,pc)(n,2m,{p}_{c})(n,2m,pc​) RACs. We can always find ${p}_{q}\ensuremath{\ge}{p}_{c}$, but the classical code gives information about every input bit simultaneously, while the QRAC only gives information about a subset. For several different (n,2,p)(n,2,p)(n,2,p) QRACs, we see the same trade-off, as the best ppp values are obtained when the number of bits that can be obtained simultaneously is as small as possible. The trade-off is connected to parity obliviousness, since high certainty information about several bits can be used to calculate probabilities for parities of subsets.