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

IEEE International Symposium on Information Theory (ISIT)

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

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

Published Jul 1, 2006• 4 citations
Publisher

Abstract

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

DOI
10.1109/isit.2006.261708

Related papers

(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 +2 more

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

arXiv:quant-ph/0604061•New Journal of Physics•Aug 4, 2006•66 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•48 citations

Classical codes violate the conjectured square-root bound for quantum random access codes

Kangqiao Liu

We consider whether every quantum random access code (QRAC) with density-operator encodings and arbitrary decoding measurements obeys the conjectured bound $p\leq(1+\sqrt{m/n})/2$, where $n$ classical bits are encoded into $m$ qubits and $p$ is the worst-case success probability. We find that classical random access codes with private randomness, which form a subclass of this QRAC model, violate the bound. We embed these classical codes as QRACs with diagonal encoding states and commuting decoding measurements, and construct pure-state realizations with identical decoding statistics. The achievability theorem of Ambainis, Nayak, Ta-Shma, and Vazirani then yields violations for every fixed $p\in(1/2,1)$ at sufficiently large input length. The counterexamples span the full open interval between the conjectured and Nayak bounds at each fixed compression rate. A finite-blocklength analysis further yields order-optimal logarithmic qubit scaling for a recovery bias scaling as $\sqrt{\log_2 n/n}$ with a sufficiently large prefactor. These results identify the classical coding rate as the source of the separation and motivate restricted bounds based on quantitative spectral properties of decoding measurements.

quant-pharXiv:2607.15617•Jul 20, 2026•0 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•2 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•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
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
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
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 .
We consider whether every quantum random access code (QRAC) with density-operator encodings and arbitrary decoding measurements obeys the conjectured bound p≤(1+m/n)/2p\leq(1+\sqrt{m/n})/2p≤(1+m/n​)/2, where nnn classical bits are encoded into mmm qubits and ppp is the worst-case success probability. We find that classical random access codes with private randomness, which form a subclass of this QRAC model, violate the bound. We embed these classical codes as QRACs with diagonal encoding states and commuting decoding measurements, and construct pure-state realizations with identical decoding statistics. The achievability theorem of Ambainis, Nayak, Ta-Shma, and Vazirani then yields violations for every fixed p∈(1/2,1)p\in(1/2,1)p∈(1/2,1) at sufficiently large input length. The counterexamples span the full open interval between the conjectured and Nayak bounds at each fixed compression rate. A finite-blocklength analysis further yields order-optimal logarithmic qubit scaling for a recovery bias scaling as log⁡2n/n\sqrt{\log_2 n/n}log2​n/n​ with a sufficiently large prefactor. These results identify the classical coding rate as the source of the separation and motivate restricted bounds based on quantitative spectral properties of decoding measurements.
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.