Random access codes are a type of communication task that is widely used in quantum information science. The optimal average success probability that can be achieved through classical strategies is known for any random access code. However, only a few cases are solved exactly for quantum random access codes. In this paper, we provide bounds for the fully general setting of n independent variables, each selected from a d-dimensional classical alphabet and encoded in a D-dimensional quantum system subject to an arbitrary quantum measurement. The bound recovers the exactly known special cases, and we demonstrate numerically that even though the bound is not tight overall, it can still yield a good approximation.Random access codes are a type of communication task that is widely used in quantum information science. The optimal average success probability that can be achieved through classical strategies is known for any random access code. However, only a few cases are solved exactly for quantum random access codes. In this paper, we provide bounds for the fully general setting of n independent variables, each selected from a d-dimensional classical alphabet and encoded in a D-dimensional quantum system subject to an arbitrary quantum measurement. The bound recovers the exactly known special cases, and we demonstrate numerically that even though the bound is not tight overall, it can still yield a good approximation.

arXiv:2312.14142Dec 21, 20231 citation

Optimal Average Success Probabilities of Binary $(n,n-1)$ and $(n,n-2)$ Quantum Random Access CodesOptimal Average Success Probabilities of Binary $(n,n-1)$ and $(n,n-2)$ Quantum Random Access Codes

Shuo Tan, Syed A. Jafar

A binary $(n,m)$ quantum random access code (QRAC) compresses an $n$ -bit classical string into an $m$ -qubit quantum state, from which a decoder attempts to recover a randomly selected target bit. Of particular interest is the optimal average probability of success, $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}$ , which was numerically conjectured to satisfy the bound $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\leq \frac{1}{2}+\frac{1}{2}\sqrt{\frac{m}{n}}$ . Recent constructions of $(n,n-1)$ QRACs by Suzuki and $(n,n-2)$ QRACs by Akibue et al. meet this bound exactly, raising the question of their strict optimality. In this work, we settle this question by proving the conjectured upper bound for $m\in\{n-1,n-2\}$ , thereby precisely determining $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-1}$ and $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-2}$ . The proof utilizes a translation recently studied by Lin and de Wolf from local to global reconstruction via pretty good measurement, along with dimensional and positive-semidefinite constraints on an induced channel.A binary $(n,m)$ quantum random access code (QRAC) compresses an $n$-bit classical string into an $m$-qubit quantum state, from which a decoder attempts to recover a randomly selected target bit. Of particular interest is the optimal average probability of success, $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}$, which was numerically conjectured to satisfy the bound $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\leq \frac{1}{2}+\frac{1}{2}\sqrt{\frac{m}{n}}$. Recent constructions of $(n,n-1)$ QRACs by Suzuki and $(n,n-2)$ QRACs by Akibue et al. meet this bound exactly, raising the question of their strict optimality. In this work, we settle this question by proving the conjectured upper bound for $m\in\{n-1,n-2\}$, thereby precisely determining $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-1}$ and $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-2}$. The proof utilizes a translation recently studied by Lin and de Wolf from local to global reconstruction via pretty good measurement, along with dimensional and positive-semidefinite constraints on an induced channel.

quant-pharXiv:2607.10414Jul 14, 20260 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.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, 20160 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.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.02667Physical Review AMay 8, 201718 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.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.21274Apr 24, 20260 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.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.5153New Journal of PhysicsApr 8, 201685 citations

Optimal Average Success Probabilities of Binary

(n,n-1)

and

(n,n-2)

Quantum Random Access Codes

A binary

(n,m)

quantum random access code (QRAC) compresses an

n

-bit classical string into an

m

-qubit quantum state, from which a decoder attempts to recover a randomly selected target bit. Of particular interest is the optimal average probability of success,

P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}

, which was numerically conjectured to satisfy the bound

P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\leq \frac{1}{2}+\frac{1}{2}\sqrt{\frac{m}{n}}

. Recent constructions of

(n,n-1)

QRACs by Suzuki and

(n,n-2)

QRACs by Akibue et al. meet this bound exactly, raising the question of their strict optimality. In this work, we settle this question by proving the conjectured upper bound for

m\in\{n-1,n-2\}

, thereby precisely determining

P^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-1}

and

P^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-2}

. The proof utilizes a translation recently studied by Lin and de Wolf from local to global reconstruction via pretty good measurement, along with dimensional and positive-semidefinite constraints on an induced channel.

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.

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.

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.