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:quant-ph/0604061 · New Journal of Physics

(4,1)-Quantum random access coding does not exist—one qubit is not enough to recover one of four bits

Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita

Published Aug 4, 2006• 74 citations
arXivHTMLPDF

Abstract

An ( n ,1, p )-quantum random access (QRA) coding, introduced by Ambainis et al (1999 ACM Symp. Theory of Computing p 376), is the following communication system: the sender which has n -bit information encodes his/her information into one qubit, which is sent to the receiver. The receiver can recover any one bit of the original n bits correctly with probability at least p , through a certain decoding process based on positive operator-valued measures. Actually, Ambainis et al shows the existence of a (2,1,0.85)-QRA coding and also proves the impossibility of its classical counterpart. Chuang immediately extends it to a (3,1,0.79)-QRA coding and whether or not a (4,1, p )-QRA coding such that p > 1/2 exists has been open since then. This paper gives a negative answer to this open question. Moreover, we generalize its negative answer for one-qubit encoding to the case of multiple-qubit encoding

DOI
10.1088/1367-2630/8/8/129

Related papers

(4, 1)-Quantum Random Access Coding Does Not Exist

Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura +2 more

An (n,1,p)-quantum random access (QRA) coding, introduced by Ambainis, Nayak, Ta-shma and Vazirani in ACM Symp. on Theory of Computing 1999, is the following communication system: The sender which has n-bit information encodes his/her information into one qubit, which is sent to the receiver. The receiver can recover any one bit of the original n bits correctly with probability at least p, through a certain decoding process based on positive operator-valued measures. Actually, Ambainis et al. shows the existence of a (2,1,0.85)-QRA coding and also proves the impossibility of its classical counterpart. Chuang immediately extends it to a (3,1,0.79)-QRA coding and whether or not a (4,1,p)-QRA coding such that p > 1/2 exists has been open since then. This paper gives a negative answer to this open question

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•5 citations

Quantum Random Access Codes with Shared Randomness

Andris Ambainis, Debbie Leung, Laura Mancinska +1 more

We consider a communication method, where the sender encodes n classical bits into 1 qubit and sends it to the receiver who performs a certain measurement depending on which of the initial bits must be recovered. This procedure is called (n,1,p) quantum random access code (QRAC) where p > 1/2 is its success probability. It is known that (2,1,0.85) and (3,1,0.79) QRACs (with no classical counterparts) exist and that (4,1,p) QRAC with p > 1/2 is not possible. We extend this model with shared randomness (SR) that is accessible to both parties. Then (n,1,p) QRAC with SR and p > 1/2 exists for any n > 0. We give an upper bound on its success probability (the known (2,1,0.85) and (3,1,0.79) QRACs match this upper bound). We discuss some particular constructions for several small values of n. We also study the classical counterpart of this model where n bits are encoded into 1 bit instead of 1 qubit and SR is used. We give an optimal construction for such codes and find their success probability exactly--it is less than in the quantum case. Interactive 3D quantum random access codes are available on-line at http://home.lanet.lv/~sd20008/racs .

arXiv:0810.2937•Oct 16, 2008•169 citations

Getting almost all the bits from a quantum random access code

Han-Hsuan Lin, Ronald de Wolf

A quantum random access code (QRAC) is a map $x\mapstoρ_x$ that encodes $n$-bit strings $x$ into $m$-qubit quantum states $ρ_x$, in a way that allows us to recover any one bit of $x$ with success probability $\geq p$. The measurement on $ρ_x$ that is used to recover, say, $x_1$ may destroy all the information about the other bits; this is in fact what happens in the well-known QRAC that encodes $n=2$ bits into $m=1$ qubits. Does this generalize to large $n$, i.e., could there exist QRACs that are so "obfuscated" that one cannot get much more than one bit out of them? Here we show that this is not the case: for every QRAC there exists a measurement that (with high probability) recovers the full $n$-bit string $x$ up to small Hamming distance, even for the worst-case $x$.

arXiv:2506.01903•Jun 2, 2025•7 citations

Quantum Random Access Coding

Harumichi Nishimura, Rudy Raymond

Quantum random access coding (QRAC) is one of the basic tools in quantum computing. It uses a quantum state for encoding the sender's bit string so that the receiver can recover any single bit of the bit string with high probability. This article surveys recent developments of QRAC, with some concrete examples of QRAC using one quantum bit, and its applications, focusing on communication complexity and locally decodable codes.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2009•3 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

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•4 citations
An ( n ,1, p )-quantum random access (QRA) coding, introduced by Ambainis et al (1999 ACM Symp. Theory of Computing p 376), is the following communication system: the sender which has n -bit information encodes his/her information into one qubit, which is sent to the receiver. The receiver can recover any one bit of the original n bits correctly with probability at least p , through a certain decoding process based on positive operator-valued measures. Actually, Ambainis et al shows the existence of a (2,1,0.85)-QRA coding and also proves the impossibility of its classical counterpart. Chuang immediately extends it to a (3,1,0.79)-QRA coding and whether or not a (4,1, p )-QRA coding such that p > 1/2 exists has been open since then. This paper gives a negative answer to this open question. Moreover, we generalize its negative answer for one-qubit encoding to the case of multiple-qubit encoding
An (n,1,p)-quantum random access (QRA) coding, introduced by Ambainis, Nayak, Ta-shma and Vazirani in ACM Symp. on Theory of Computing 1999, is the following communication system: The sender which has n-bit information encodes his/her information into one qubit, which is sent to the receiver. The receiver can recover any one bit of the original n bits correctly with probability at least p, through a certain decoding process based on positive operator-valued measures. Actually, Ambainis et al. shows the existence of a (2,1,0.85)-QRA coding and also proves the impossibility of its classical counterpart. Chuang immediately extends it to a (3,1,0.79)-QRA coding and whether or not a (4,1,p)-QRA coding such that p > 1/2 exists has been open since then. This paper gives a negative answer to this open question
We consider a communication method, where the sender encodes n classical bits into 1 qubit and sends it to the receiver who performs a certain measurement depending on which of the initial bits must be recovered. This procedure is called (n,1,p) quantum random access code (QRAC) where p > 1/2 is its success probability. It is known that (2,1,0.85) and (3,1,0.79) QRACs (with no classical counterparts) exist and that (4,1,p) QRAC with p > 1/2 is not possible. We extend this model with shared randomness (SR) that is accessible to both parties. Then (n,1,p) QRAC with SR and p > 1/2 exists for any n > 0. We give an upper bound on its success probability (the known (2,1,0.85) and (3,1,0.79) QRACs match this upper bound). We discuss some particular constructions for several small values of n. We also study the classical counterpart of this model where n bits are encoded into 1 bit instead of 1 qubit and SR is used. We give an optimal construction for such codes and find their success probability exactly--it is less than in the quantum case. Interactive 3D quantum random access codes are available on-line at http://home.lanet.lv/~sd20008/racs .
A quantum random access code (QRAC) is a map x↦ρxx\mapstoρ_xx↦ρx​ that encodes nnn-bit strings xxx into mmm-qubit quantum states ρxρ_xρx​, in a way that allows us to recover any one bit of xxx with success probability ≥p\geq p≥p. The measurement on ρxρ_xρx​ that is used to recover, say, x1x_1x1​ may destroy all the information about the other bits; this is in fact what happens in the well-known QRAC that encodes n=2n=2n=2 bits into m=1m=1m=1 qubits. Does this generalize to large nnn, i.e., could there exist QRACs that are so "obfuscated" that one cannot get much more than one bit out of them? Here we show that this is not the case: for every QRAC there exists a measurement that (with high probability) recovers the full nnn-bit string xxx up to small Hamming distance, even for the worst-case xxx.
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 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.