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:2601.19190 · Physical Review A

Analytical construction of $(n, n-1)$ quantum random access codes saturating the conjectured bound

Takayuki Suzuki

quant-phSubmitted Jan 27, 2026• Announced Jan 28, 2026• 0 citations
arXivHTMLPDF

Abstract

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, $\mathcal{P} = 1/2 + \sqrt{(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(\log n)$ 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.

DOI
10.1103/fcz5-2g3w

Related papers

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•0 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

Optimal 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.

quant-pharXiv:2607.10414•Jul 14, 2026•0 citations

Measurement Geometry for Quantum Random Access Codes: Beyond Nayak Bound and Toward Optimality

Seiseki Akibue, Rudy Raymond, Suguru Tamaki +1 more

Quantum random access codes (QRACs) ask how well N classical bits can be encoded into M qubits while allowing any single bit to be recovered. Although the Nayak bound remains the standard general upper bound on the decoding probability, numerical evidence suggests a stronger upper bound in the small-qubit regime. In this work, we formulate the optimal decoding probability in terms of decoding measurements, reformulating QRAC design as a spectral problem for noncommuting measurements. Using this formulation, we give an elementary proof of the Nayak bound by simplifying the Chernoff-bound argument. Moreover, we refine the argument to obtain upper bounds that improve over Nayak's bound in the entire finite-size regime. The equality conditions of our bounds justify defining mutually unbiased projector-valued measurements (MUPVMs), a generalization of mutually unbiased bases. We show that decoding measurement of any two-qubit QRAC attaining the conjectured bound must form MUPVMs. We also show that any MUPVM, assisted by one ancillary qubit, yields a QRAC with optimal N-scaling decoding probability. Finally, we propose a new MUPVM-based construction for the (M+2,M)-QRAC family attaining the conjectured bound.

quant-pharXiv:2606.12700•Jun 12, 2026•0 citations

Optimal Average Success Probabilities of Binary (n, n−1) and (n, n−2) Quantum Random AccessCodes

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,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.

•Oct 21, 2026•0 citations

High-dimensional multi-input quantum random access codes and mutually unbiased bases

Rui-Heng Miao, Zhao‐Di Liu, Yong-Nan Sun +3 more

Quantum random access codes (QRACs) provide a basic tool for demonstrating the advantages of quantum resources and protocols, which have a wide range of applications in quantum information processing tasks. However, the investigation and application of high-dimensional $(d)$ multi-input $(n)\phantom{\rule{4pt}{0ex}}{n}^{(d)}\ensuremath{\rightarrow}1$ QRACs are still lacking. Here, we present a general method to find the maximum success probability of ${n}^{(d)}\ensuremath{\rightarrow}1$ QRACs. In particular, we give the analytical solution for maximum success probability of ${3}^{(d)}\ensuremath{\rightarrow}1$ QRACs when measurement bases are mutually unbiased bases (MUBs). Based on the analytical solution, we show the relationship between MUBs and ${n}^{(d)}\ensuremath{\rightarrow}1$ QRACs. First, we provide a systematic method of searching for the operational inequivalence of MUBs (OI-MUBs) when the dimension $d$ is a prime power. Second, we theoretically prove that, surprisingly, the commonly used Galois MUBs are not the optimal measurement bases to obtain the maximum success probability of ${n}^{(d)}\ensuremath{\rightarrow}1$ QRACs, which indicates a breakthrough according to the traditional conjecture regarding the optimal measurement bases. Furthermore, based on high-fidelity high-dimensional quantum states of orbital angular momentum, we experimentally achieve two-input and three-input QRACs up to dimension 11. We experimentally confirm the OI-MUBs when $d=5$. Our results open alternative avenues for investigating the foundational properties of quantum mechanics and quantum network coding.

arXiv:2111.08890•Physical Review A•Oct 14, 2022•6 citations
Analytical construction of (n,n−1)(n, n-1)(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)(n, n-1)(n,n−1)-QRACs, which encode nnn bits of classical information into n−1n-1n−1 qubits, provides an ideal theoretical model for verifying quantum advantage in high-dimensional spaces; however, the analytical derivation of optimal codes for general nnn has remained an open problem. In this paper, we establish an analytical construction method for (n,n−1)(n, n-1)(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\mathcal{P} = 1/2 + \sqrt{(n-1)/n}/2P=1/2+(n−1)/n​/2, for all nnn. 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)O(n)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(log⁡n)O(\log n)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 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.
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.
Optimal Average Success Probabilities of Binary (n,n−1)(n,n-1)(n,n−1) and (n,n−2)(n,n-2)(n,n−2) Quantum Random Access Codes
A binary (n,m)(n,m)(n,m) quantum random access code (QRAC) compresses an nnn-bit classical string into an mmm-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,optP^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}Pn,mQ,avg,opt​, which was numerically conjectured to satisfy the bound Pn,mQ,avg,opt≤12+12mnP^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\leq \frac{1}{2}+\frac{1}{2}\sqrt{\frac{m}{n}}Pn,mQ,avg,opt​≤21​+21​nm​​. Recent constructions of (n,n−1)(n,n-1)(n,n−1) QRACs by Suzuki and (n,n−2)(n,n-2)(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}m\in\{n-1,n-2\}m∈{n−1,n−2}, thereby precisely determining Pn,n−1Q,avg,optP^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-1}Pn,n−1Q,avg,opt​ and Pn,n−2Q,avg,optP^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-2}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.
Quantum random access codes (QRACs) ask how well N classical bits can be encoded into M qubits while allowing any single bit to be recovered. Although the Nayak bound remains the standard general upper bound on the decoding probability, numerical evidence suggests a stronger upper bound in the small-qubit regime. In this work, we formulate the optimal decoding probability in terms of decoding measurements, reformulating QRAC design as a spectral problem for noncommuting measurements. Using this formulation, we give an elementary proof of the Nayak bound by simplifying the Chernoff-bound argument. Moreover, we refine the argument to obtain upper bounds that improve over Nayak's bound in the entire finite-size regime. The equality conditions of our bounds justify defining mutually unbiased projector-valued measurements (MUPVMs), a generalization of mutually unbiased bases. We show that decoding measurement of any two-qubit QRAC attaining the conjectured bound must form MUPVMs. We also show that any MUPVM, assisted by one ancillary qubit, yields a QRAC with optimal N-scaling decoding probability. Finally, we propose a new MUPVM-based construction for the (M+2,M)-QRAC family attaining the conjectured bound.
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.
Quantum random access codes (QRACs) provide a basic tool for demonstrating the advantages of quantum resources and protocols, which have a wide range of applications in quantum information processing tasks. However, the investigation and application of high-dimensional (d)(d)(d) multi-input $(n)\phantom{\rule{4pt}{0ex}}{n}^{(d)}\ensuremath{\rightarrow}1$ QRACs are still lacking. Here, we present a general method to find the maximum success probability of ${n}^{(d)}\ensuremath{\rightarrow}1$ QRACs. In particular, we give the analytical solution for maximum success probability of ${3}^{(d)}\ensuremath{\rightarrow}1$ QRACs when measurement bases are mutually unbiased bases (MUBs). Based on the analytical solution, we show the relationship between MUBs and ${n}^{(d)}\ensuremath{\rightarrow}1$ QRACs. First, we provide a systematic method of searching for the operational inequivalence of MUBs (OI-MUBs) when the dimension ddd is a prime power. Second, we theoretically prove that, surprisingly, the commonly used Galois MUBs are not the optimal measurement bases to obtain the maximum success probability of ${n}^{(d)}\ensuremath{\rightarrow}1$ QRACs, which indicates a breakthrough according to the traditional conjecture regarding the optimal measurement bases. Furthermore, based on high-fidelity high-dimensional quantum states of orbital angular momentum, we experimentally achieve two-input and three-input QRACs up to dimension 11. We experimentally confirm the OI-MUBs when d=5d=5d=5. Our results open alternative avenues for investigating the foundational properties of quantum mechanics and quantum network coding.