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.
AI Summary
A binary $(n,m)$ quantum random access code encodes a uniformly random $n$-bit string into $m$ qubits and aims to recover a uniformly selected bit. This paper determines the optimal average success probability when only one or two qubits are saved: for $m\in\{n-1,n-2\}$, $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}=\tfrac12+\tfrac12\sqrt{m/n}$. The result establishes the optimality of existing constructions for both families.
The converse uses the full-string pretty good measurement (PGM), whose coordinate marginals coincide with the corresponding one-bit PGMs. A binary state-discrimination bound and Jensen’s inequality relate a code’s average success probability $P$ to the PGM’s expected Hamming distortion: $\Delta\leq \tfrac n2[1-(2P-1)^2]$. Conversely, the dimension bound on exact reconstruction gives $\Pr[Y=X]\leq 2^{m-n}$, implying $\Delta\geq 1/2$ for $m=n-1$. For $m=n-2$, the PGM transition matrix is shown to be a positive-semidefinite Gram matrix. Applying positivity to the parity vector gives $\Pr[\operatorname{dist}(X,Y)\text{ is odd}]\leq 1/2$; together with the exact-reconstruction bound, this yields $\Delta\geq1$. Combining these inequalities proves the claimed upper bounds, matched by the known constructions.
The exact characterization is restricted to these two high-rate families. The same square-root expression is not a universal upper bound: the paper notes that classical random access code counterexamples already rule out that broader conjecture. Limited extensions are referenced but not developed here.
Little sign of AI-generated text
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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 encodes a uniformly random n-bit string into m qubits and aims to recover a uniformly selected bit. This paper determines the optimal average success probability when only one or two qubits are saved: for m∈{n−1,n−2}, Pn,mQ,avg,opt=21+21m/n. The result establishes the optimality of existing constructions for both families.
The converse uses the full-string pretty good measurement (PGM), whose coordinate marginals coincide with the corresponding one-bit PGMs. A binary state-discrimination bound and Jensen’s inequality relate a code’s average success probability P to the PGM’s expected Hamming distortion: Δ≤2n[1−(2P−1)2]. Conversely, the dimension bound on exact reconstruction gives Pr[Y=X]≤2m−n, implying Δ≥1/2 for m=n−1. For m=n−2, the PGM transition matrix is shown to be a positive-semidefinite Gram matrix. Applying positivity to the parity vector gives Pr[dist(X,Y) is odd]≤1/2; together with the exact-reconstruction bound, this yields Δ≥1. Combining these inequalities proves the claimed upper bounds, matched by the known constructions.
The exact characterization is restricted to these two high-rate families. The same square-root expression is not a universal upper bound: the paper notes that classical random access code counterexamples already rule out that broader conjecture. Limited extensions are referenced but not developed here.
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 2k representatives in {0,1}L, while the worst-case criterion is reduced to a minimax problem over 2k 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 (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), 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.
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.
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.
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 (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.