Random Access Codes: Explicit Constructions, Optimality, and Classical–Quantum Gaps

Ruho Kondo, Yuki Sato, Hiroshi Yano, Yota Maeda, Kosuke Ito, Naoki Yamamoto · 2026

Read Random Access Codes: Explicit Constructions, Optimality, and Classical–Quantum Gaps by Ruho Kondo, Yuki Sato, Hiroshi Yano, Yota Maeda, Kosuke Ito, Naoki Yamamoto (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-21274.txt.

Introduction

Ruho Kondo and five colleagues give a geometric account of random access codes. Such a code packs an L-bit string into a shorter message so any requested bit can be recovered with high probability. Average-case optimality becomes choosing representatives in a binary cube. Worst-case optimality becomes a minimax problem over points in a unit cube. The framework proves optimality for several code families and yields two classical-quantum separations, including a one-qubit code beating the best classical average for every length.

Catalog record

CREATORRuho Kondo, Yuki Sato, Hiroshi Yano, Yota Maeda, Kosuke Ito, Naoki Yamamoto
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63758
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.21274

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Random Access Codes: Explicit Constructions, Optimality, and Classical–Quantum Gaps Ruho Kondo, Yuki Sato, Hiroshi Yano, Yota Maeda, Kosuke Ito, Naoki Yamamoto Abstract A random access code (RAC) encodes an L L -bit string into a k k -bit ( L > k ) (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 k -bit message with k 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 ) (L,k) -RACs under both average- and worst-case criteria. We show that optimal code design reduces to selecting 2 k 2^{k} points in { 0 , 1 } L \{0,1\}^{L} and [ 0 , 1 ] L [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 ) (L,k) . For k = L − 1 k=L-1 , we further obtain closed-form optimal encoders and decoders for both criteria, and show that the resulting classical ( L , L − 1 ) (L,L-1) -RACs attain the corresponding proved upper bounds. We also show that these optimal classical codes induce ( L , L − 1 ) (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. I Introduction A random access code (RAC) is a protocol that encodes multiple bits of information into a message shorter than the original information, such that a receiver can probabilistically recover any designated bit position from the message. When the message is encoded into a quantum state, the protocol is called a quantum random access code (QRAC). The idea dates back to Wiesner’s conjugate coding [ 24 ] and was later rediscovered and formulated explicitly as a random access code by Ambainis et al. [ 3 ] . By convention, a protocol that encodes L bits into a k -(quantum)bit message is referred to as an (L,k) -(Q)RAC. In [ 3 ] , (2,1) -QRACs and (3,1) -QRACs were proposed, and it is known that they achieve higher decoding success probabilities than the corresponding classical (2,1) -RAC and (3,1) -RAC. Leveraging their compressibility, QRACs have also been applied to accelerating combinatorial optimization problems [ 7 , 22 , 20 , 13 , 18 , 10 , 16 ] . In this way, it is known that QRACs can outperform RACs in terms of decoding success probability for certain specific choices of L and k . However, for general L and k , the extent to which a quantum advantage can be achieved remains unclear. We next summarize several theoretical results known for RACs and QRACs. First, it has been shown that there exists no ({L},k) -RAC for L\geq 2^{k} whose worst-case decoding success probability exceeds \tfrac{1}{2} , whereas an (2^{k}-1,k) -RAC does exist [ 12 , Corollary 5.3] . Similarly, there exists no ({L},k) -QRAC for L\geq 4^{k} , while a (4^{k}-1,k) -QRAC exists. Note that there exists (L,k) -(Q)RAC for arbitrary L,k\in\mathbb{N} whose average decoding success probability exceeds \tfrac{1}{2} . For the worst-case decoding success probability of an (L,k) -RAC, P^{*}_{\rm C}(L,k) , the following upper bound is known [ 3 , Theorem 2.1] : P^{*}_{\rm C}(L,k)\leq\mathcal{H}_{2}^{-1}\left(1-\frac{k}{L}\right)<\frac{1}{2}+\frac{1}{2}\sqrt{\frac{(2\ln 2)k}{L}}. (1) Here \mathcal{H}_{2}(p)=-p\log_{2}p-(1-p)\log_{2}(1-p) denotes the binary entropy function. Moreover, the worst-case decoding success probability of an (L,k) -QRAC, P^{*}_{\rm Q}(L,k) , is known to satisfy the same upper bound [ 17 , Theorem 2.3] : P^{*}_{\rm Q}(L,k)\leq\mathcal{H}_{2}^{-1}\left(1-\frac{k}{L}\right)<\frac{1}{2}+\frac{1}{2}\sqrt{\frac{(2\ln 2)k}{L}}. (2) That is, the worst-case decoding success probabilities of RACs and QRACs are known to satisfy the same upper bound. However, the tightness of this bound has not been evaluated, and the extent of the gap between the actual supremum of the worst-case decoding success probabilities of RACs and QRACs remains unknown. More recently, a new upper bound on the average decoding success probability of an (L,k) -QRAC, \overline{P}_{\rm Q}(L,k) , was established in [ 15 , Theorem 10] : \overline{P}_{\rm Q}(L,k)\leq\frac{1}{2}+\frac{1}{2}\sqrt{\frac{2^{k-1}}{L}}. (3) Since the optimal worst-case success probability is upper bounded by the optimal average success probability, this also yields an upper bound on the worst-case success probability of (L,k) -QRACs. In addition, the following conjectured upper bound on the worst-case decoding success probability has been proposed [ 15 ] : P^{*}_{\rm Q}(L,k)\leq\frac{1}{2}+\frac{1}{2}\sqrt{\frac{k}{L}}\quad(\text{conjecture}). (4) Upper bounds for general d -level (L,k) -QRACs were proposed in [ 6 , Corollary 1] ; however, for the qubit case ( d=2 ), the bound in [ 15 ] is tighter. Although it is known that replacing classical message bits by qubits does not provide an asymptotic advantage in the sense that one cannot substantially reduce the message length k [ 3 , Theorem 1.2] , quantum advantage can be observed when focusing on the average success probability in the case k=1 [ 1 ] . The average decoding success probabilities of the (2,1) -RAC and (3,1) -RAC have also been discussed in the literature (see, e.g., [ 21 ] ). In [ 1 ] , an average-optimal (L,1) -RAC was constructed, and the following upper bound on the average decoding success probability was shown: \overline{P}_{\rm C}(L,1)\leq\frac{1}{2}+\frac{1}{2^{L}}\binom{L-1}{\lfloor\frac{L}{2}\rfloor}. (5) The above results summarize the current theoretical landscape on upper bounds for (L,k) -RACs and (L,k) -QRACs. On the other hand, explicit methods to build encoders and decoders for (Q)RACs have also been studied. In [ 11 ] , (L,2) -QRACs are constructed via a seesaw semidefinite programming (SDP) algorithm, i.e., an alternating SDP optimization over the quantum states and the POVMs. The same work also proposes an optimal (3,2) -QRAC in terms of both the average and worst-case decoding success probability, and further discussion of its structure is given in [ 23 ] . A general construction method for (L<2^{k},k) -RACs and (L<4^{k},k) -QRACs is discussed in [ 14 ] , which proposes the following form of encoder: \rho({\bf b})=\frac{1}{2^{k}}\mathbb{I}^{\otimes k}+\frac{1}{2^{k}\sqrt{(2^{k}-1)L}}\sum_{i\in[L]}(-1)^{b_{i}}\xi_{i}. (6) Here \xi_{i} are Pauli operators; for RACs one uses \xi_{i}\in\{\mathbb{I},\texttt{Z}\}^{\otimes k}\setminus\{\mathbb{I}^{\otimes k}\} , whereas for QRACs one uses \xi_{i}\in\{\mathbb{I},\texttt{X},\texttt{Y},\texttt{Z}\}^{\otimes k}\setminus\{\mathbb{I}^{\otimes k}\} , where X , Y , and Z are the Pauli matrices. The corresponding positive operator-valued measure (POVM) is proposed as E^{b_{i}}_{i}=\frac{1}{2}\mathbb{I}^{\otimes k}+\frac{(-1)^{b_{i}}}{2}\xi_{i}. (7) For the above (Q)RAC \big\{\{\rho({\bf b})\},\{E^{0}_{i},E^{1}_{i}\}\big\} , the decoding success probabilities satisfy \displaystyle{P^{*}_{\rm C}(L,k)=\overline{P}_{\rm C}(L,k)=P^{*}_{\rm Q}(L,k)=\overline{P}_{\rm Q}(L,k)} =\frac{1}{2}+\frac{1}{2}\sqrt{\frac{1}{(2^{k}-1)L}}. (8) While this value is significantly below the known upper bounds, at present no alternative constructive method is known that yields (L,k) -(Q)RACs for arbitrary L and k beyond the above approach. Very recently, a construction of an (L,L-1) -QRAC achieving the conjectured upper bound in Eq. ( 4 ) was proposed in [ 19 ] . However, for general (L,k) , an optimal construction of QRACs remains unknown, and it is also still open whether the conjectured upper bound in Eq. ( 4 ) holds in full generality. In summary, the current open questions on (Q)RACs can be stated

Read the complete text