A random access code (RAC) encodes an $L$-bit string into a $k$-bit $(L>k)$ message from which any designated source bit can be recovered with high probability. Its quantum counterpart, a quantum random access code (QRAC), replaces the $k$-bit message with $k$ qubits. While upper bounds on the decoding success probability have long been studied in both classical and quantum settings, explicit constructions of optimal codes are known only in special cases, even for classical RACs. In this paper, we develop a constructive framework for classical $(L,k)$-RACs under both average- and worst-case criteria. We show that optimal code design reduces to selecting $2^k$ points in $\{0,1\}^L$ and $[0,1]^L$ for the average- and worst-case criteria, respectively, so as to minimize a distance-like objective. This characterization yields explicit constructions for general $(L,k)$. For $k=L-1$, we further obtain closed-form optimal encoders and decoders for both criteria, and show that the resulting classical $(L,L-1)$-RACs attain the corresponding proved upper bounds. We also show that these optimal classical codes induce $(L,L-1)$-QRACs that attain a conjectured upper bound on the decoding success probability. Numerical optimization suggests little difference between RACs and QRACs in the average-case setting, but a potentially large classical-quantum gap in the worst-case nonasymptotic regime.
A random access code (RAC) encodes an L-bit string into a k-bit (L>k) message from which any designated source bit can be recovered with high probability. Its quantum counterpart, a quantum random access code (QRAC), replaces the k-bit message with k qubits. While upper bounds on the decoding success probability have long been studied in both classical and quantum settings, explicit constructions of optimal codes are known only in special cases, even for classical RACs. In this paper, we develop a constructive framework for classical (L,k)-RACs under both average- and worst-case criteria. We show that optimal code design reduces to selecting 2k points in {0,1}L and [0,1]L for the average- and worst-case criteria, respectively, so as to minimize a distance-like objective. This characterization yields explicit constructions for general (L,k). For k=L−1, we further obtain closed-form optimal encoders and decoders for both criteria, and show that the resulting classical (L,L−1)-RACs attain the corresponding proved upper bounds. We also show that these optimal classical codes induce (L,L−1)-QRACs that attain a conjectured upper bound on the decoding success probability. Numerical optimization suggests little difference between RACs and QRACs in the average-case setting, but a potentially large classical-quantum gap in the worst-case nonasymptotic regime.
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>21. We generalize (Q)RACs to a scheme encoding nd-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 d1. 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,pq) QRACs with classical (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) 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.
Analytical construction of (n,n−1) quantum random access codes saturating the conjectured bound
Quantum Random Access Codes (QRACs) embody the fundamental trade-off between the compressibility of information into limited quantum resources and the accessibility of that information, serving as a cornerstone of quantum communication and computation. In particular, the (n,n−1)-QRACs, which encode n bits of classical information into n−1 qubits, provides an ideal theoretical model for verifying quantum advantage in high-dimensional spaces; however, the analytical derivation of optimal codes for general n has remained an open problem. In this paper, we establish an analytical construction method for (n,n−1)-QRACs by using an explicit operator formalism. We prove that this construction strictly achieves the numerically conjectured upper bound of the average success probability, P=1/2+(n−1)/n/2, for all n. Furthermore, we present a systematic algorithm to decompose the derived optimal POVM into standard quantum gates. Since the resulting decoding circuit consists solely of interactions between adjacent qubits, it can be implemented with a circuit depth of O(n) even under linear connectivity constraints. Additionally, we analyze the high-dimensional limit and demonstrate that while the non-commutativity of measurements is suppressed, an information-theoretic gap of O(logn) from the Holevo bound inevitably arises for symmetric encoding. This study not only provides a scalable implementation method for high-dimensional quantum information processing but also offers new insights into the mathematical structure at the quantum-classical boundary.
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>21. Such a code is denoted by the triple (n,m,p). It is known that n<4m for all QRACs and n<2m for classical RACs. These bounds are also known to be tight, as explicit constructions exist for n=4m−1 and n=2m−1 for quantum and classical codes respectively. We generalize (Q)RACs to a scheme encoding nd-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 d1. We construct explicit solutions for all n≤d−1d2m−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=4m−1,m,p) QRACs, 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) QRACs with classical (n,2m,pc) RACs, we can always find pq≥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) 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.
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, Pn,mQ,avg,opt, which was numerically conjectured to satisfy the bound Pn,mQ,avg,opt≤21+21nm. 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∈{n−1,n−2}, thereby precisely determining Pn,n−1Q,avg,opt and Pn,n−2Q,avg,opt. 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,avg,opt n,m .The square-root expression 1 2 + 1 2 m/n was conjectured to upper-bound this quantity, and recent constructions of (n, n -1) QRACs by Suzuki and (n, n -2) QRACs by Akibue et al. meet it exactly.In this work, we prove that these constructions are optimal, thereby determining P Q,avg,opt n,n-1 and P Q,avg,opt n,n-2 .The proof uses the local-to-global reconstruction framework of Lin and de Wolf, based on the pretty good measurement (PGM), together with dimensional and positive-semidefinite (PSD) constraints on the induced channel.Based on these constraints, we also derive an efficient linear-programming (LP) converse for general binary (n, m) QRACs.We evaluate this converse in closed form for two infinite parameter families and prove that it is strictly tighter than Akibue et al.'s bound at every point in those families except (n, m) = (3, 1), where the two coincide.
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)/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∈(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 log2n/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.