Optimal Average Success Probabilities of Binary (n,n-1) and (n,n-2) Quantum Random Access Codes

arXiv:2607.10414 · quant-ph, cs.IT, math.IT · Submitted 2026-07-11 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: We're looking at the paper: "Optimal Average Success Probabilities of Binary (n,n-1) and (n,n-2) Quantum Random Access Codes".

Mira: Here's the gist of the paper. The gist This work settles whether the conjectured upper bound for average success probability holds for binary (n, n − 1) and (n, n − 2) quantum random access codes by proving it for these specific settings.

Kai: Quantum random access codes (QRACs) formalize the tradeoff between compressibility and retrievability of classical strings in a quantum setting.

Mira: A key performance metric is the optimal average probability of success, P Q,avg opt n,m.

Kai: This bound is particularly relevant for m ∈ QRAC Model The binary (n, m) QRAC C is specified as a tuple of an ensemble of quantum states and a binary decoding POVM.

Title and authors: Kai: So we’re looking at this paper titled Optimal Average Success Probabilities of Binary (n, n-one) and (n, n-two) Quantum Random Access Codes <ref:2607.10414#pg1,Optimal Average Success Probabilities of Binary (n, n-1) and (n, n>. What does that actually mean for us in the real world?

Mira: It means they're settling a question about the best average success probability for these specific types of quantum codes—the ones with m equal to n minus one or n minus two.

Lev: For me, it means this is about finding a concrete limit for how reliable we can be when we compress classical strings using quantum states like this.

Kai: Right, so they're not just guessing anymore; they're proving the upper bound that was already conjectured for these specific settings.

Mira: Exactly. They are determining precisely what the optimal average success probability is for those (n, n-one) and (n, n-two) codes <ref:2607.10414#pg1,n, n-1)$ and $(n, n-2>.

Lev: And that precision is important because we need to know where we stand when we try to build actual hardware for error correction later on.

The paper's summary: Kai: Okay, so what’s the core of this work? It seems they start by defining a binary (n, m) quantum random access code, which involves an ensemble of states and a decoding process.

Mira: They then introduce the optimal average success probability P Q, avg, opt n,m, which is defined as maximizing the product of the state's probability and a certain measurement outcome over all possible inputs.

Lev: From an engineering standpoint, that maximization part is what determines if a code is actually useful when you throw it on hardware.

Kai: The paper then uses a translation from local to global reconstruction via pretty good measurement, which helps them bound the expected Hamming distance between the original string X and its decoded version Y C, PGM.

Mira: They use Renes’s refined PGM bound on the one-bit PGM to show that the probability of getting a correct bit is at least (p C i) squared + (one - p C i) squared, where p C i is related to the code's probability <ref:2607.10414#pg1>.

Lev: That probabilistic step needs a lot of assumptions about how well we can measure the quantum state, which you have to trust when you build a real system.

Kai: And then they combine that with an optimization condition, where they take the maximum of p C i and one minus p C i, which leads them to the bound C, PGM 2n P C (one - P C) <ref:2607.10414#pg1>.

Mira: That final bound on the expected Hamming distance is what they derive, showing that it's at most two n times P C times one minus P C.

The paper's improvements: Kai: So what are the actual improvements the authors make in this paper? It seems to be about establishing a definitive proof for those bounds that were previously just conjectures.

Mira: They prove the conjectured upper bound holds for m in n-one n-two which is a big deal because it confirms the optimality of Suzuki’s (n, n-one) construction and Akibue et al <ref:2607.10414#pg1>.’s (n, n-two) construction <ref:2607.10414#pg1>.

Lev: Proving that the bound holds exactly for those two specific cases means that we can finally say something concrete about their performance without relying on just numerical examples.

Kai: The paper also establishes a lower bound for the expected Hamming distance, based on the full-string PGM, showing it's at least (n-m)/two when m is in those ranges <ref:2607.10414#pg1>.

Mira: Combining that upper and lower bound gives them C, PGM (n-m)/two which solidifies the result for the codes with m in n-one n-two <ref:2607.10414#pg1>.

Lev: For hardware design, that lower bound is crucial because it tells us the minimum level of error we can expect when running this compression scheme on actual physical devices.

Conclusion: Kai: So to wrap up, what’s the big picture here? They’ve proven that for binary (n, n-one) and (n, n-two) QRACs, the upper bound they conjectured is achievable <ref:2607.10414#pg1,binary $(n, n-1)$ and $(n, n-2>.

Mira: This means P Q, avg, opt n,m is exactly one/two + one/two r m/n, which is the precise value for these specific code dimensions <ref:2607.10414#pg1>.

Lev: For hardware development, knowing this exact value of success probability helps us set realistic targets for what we can expect from a device implementing that kind of quantum compression.

Kai: It’s a confirmation that the theoretical limits we were aiming for in these specific settings are actually achievable with these known constructions.

Mira: So, the implication is that for any (n, m) QRAC with m in n-one n-two this bound holds true <ref:2607.10414#pg1>.

Lev: And remember that the authors also point out a limitation: they didn't prove it for arbitrary dimensions D=2m, so we can't just assume it works everywhere without further work <ref:2607.10414#pg2>.

University of California, Irvine

quant-ph, cs.IT, math.IT

Submitted: 2026-07-11

Updated: 2026-10-22

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 87/100

The gist: The gist This work settles whether the conjectured upper bound for average success probability holds for binary (n, n − 1) and (n, n − 2) quantum random access codes by proving it for these

Key concepts

Binary (n, m) QRAC: A quantum random access code formalizes how much classical information can be compressed into a quantum state while still allowing reliable retrieval. It involves an ensemble of quantum states and a binary decoding process. The goal is to maximize the average probability of successfully recovering the original string.
Optimal Average Success Probability (P_Q,avg_opt n,m): This metric represents the best possible average success rate achievable across all possible (n, m) QRACs. The paper proves that for specific cases like m=n-1 and m=n-2, this optimal probability is exactly 1/2 plus half the ratio of qubits to bits (m/n).
Full PGM Channel (T_C,PGM): This channel describes how a quantum state transforms into a classical output using Pretty Good Measurement (PGM). It allows researchers to translate the complex quantum process into a classical channel. This translation is used to bound the expected Hamming distance between the original string and its decoded version.
Hamming Distance Bound (Delta_C,PGM): The expected Hamming distance measures how many bits differ between the original transmitted string and the recovered string after decoding via PGM. The paper shows that this distance is bounded by 2n * P_C(1 - P_C), which helps quantify the error introduced by the measurement process.

Terminology

Decoder — 1× in this paper · explained in 2 episodes

Summary

The gist This work settles whether the conjectured upper bound for average success probability holds for binary (n, n − 1) and (n, n − 2) quantum random access codes by proving it for these specific settings.

Background

Quantum random access codes (QRACs) formalize the tradeoff between compressibility and retrievability of classical strings in a quantum setting. A key performance metric is the optimal average probability of success, P Q,avg opt n,m. This bound is particularly relevant for m ∈

QRAC Model

The binary (n, m) QRAC C is specified as a tuple of an ensemble of quantum states and a binary decoding POVM. The optimal average success probability for the entire class of (n, m) QRACs is defined as P Q,avg opt n,m:= max C P C(6) = max of rhoX,i>Mbi 1/n2 n X x∈0,1 n Xn i=1 TrrhoXMCxii>.

Full PGM and the Full PGM Channel

The full-string PGM is defined from the average state ρbarC as in [19] with uniform X as follows. This induces a classical channel T C,PGM xy with transition probabilities T C,PGM xy = P[Y C,PGM = y X = x] = Tr(ρ C xQ C y).

Upper Bound Derivation

The proof utilizes a converse that uses a translation from local to global reconstruction via pretty good measurement (PGM). The expected Hamming distance ∆C,PGM is bounded by ∆C,PGM ≤ n squared 1 − (2P C − 1) squared. By applying Renes’s refined PGM bound to the one-bit PGM, it is shown that P[Y C,PGM i = Xi] ≥ (p C∗ i) squared + (1 − p C∗ i) squared. Combining this with the optimization condition p C∗ i ≥ max of p C i, 1 − p C i ≥ 1/2 yields P[Y C,PGM i = Xi] ≥ (p C i) squared + (1 − p C i) squared. Summing over all bits leads to the bound ∆C,PGM ≤ 2n P C(1 − P C).

Lower Bound Derivation and Main Result

The second lemma establishes that the matrix of transition probabilities for the channel T C,PGM is positive-semidefinite. Lemma 3 bounds the probability that the Hamming distance between X and Y C,PGM is odd to P[dH(X, Y C,PGM) is odd] ≤ 1/2. This leads to the bound ∆C,PGM ≥ (n − m)/2 in both cases for m ∈

Conclusion

The main result proves that for m ∈

Corollary 1 states that P Q,avg opt n,m = 1/2 + 1/2 r m/n. This is achieved because the upper bound holds for Suzuki’s (n, n − 1) construction and Akibue et al.’s (n, n − 2) construction. The exact values of P Q,avg opt n,m for m ∈

This work determines the precise values of the optimal average success probability for the classes of binary (n, n − 1) and (n, n − 2) QRACs by proving that the numerically conjectured upper bound holds for these specific settings.

Discussion

The discussion notes that while focusing on dimensions D = 2m for integer m, none of the three lemmas require D to be a power of 2. An example with n = 4 and D = 6 shows that direct logarithmic interpolation is not always tight.

Acknowledgements

The authors acknowledge the use of OpenAI’s ChatGPT (GPT-5.5) as a research assistant during the discovery of the results presented in this work. The content is independently verified, revised, and approved by the authors who take full responsibility for the manuscript.

References

[1] A. S. Holevo, Probl. Inf. Transm. 9, 177 (1973)

[2] A Ambainis, A Nayak, A Ta-Shma, and U Vazirani in Proc 31st Annu ACM Symp Theory Comput STOC (ACM 1999) pp 376–383

[3] H Klauck in Proc 32nd Annu ACM Symp Theory Comput STOC (ACM 2000) pp 644–651

[4] S Aaronson in Proc 19th IEEE Annu Conf Comput Complexity CCC (IEEE 2004) pp 320–332 arXiv:quant-ph/0402095

[5] M Hayashi, K Iwama, H Nishimura, R Raymond, and S Yamashita in Annual Symposium Theoretical Aspects Computer Science (Springer 2007) pp 610–621

[6] I Kerenidis and R de Wolf in J Comput Syst Sci 69, 395 (2004)

[7] S Wehner and R de Wolf in Automata Languages and Programming ICALP Lecture Notes in Computer Science Vol 3580 (Springer 2005) pp 1424–1436 arXiv:quant-ph/0403140

[8] N Brunner, M Navascués, and T Vértesi Phys Rev Lett 110, 150501 (2013)

[9] M Pawłowski and N Brunner Phys Rev A 84, 010302 (2011)

[10] H-W Li, Z-Q Yin, Y-C Wu, X-B Zou, S Wang, W Chen, G-C Guo, and Z-F Han Phys Rev A 84 034301 (2011)

[11] H-W Li, M Pawłowski, Z-Q Yin, G-C Guo, and Z-F Han Phys Rev A 85 052308 (2012)

[12] A Tavakoli, A Hameedi, B Marques, and M Bourennane Phys Rev Lett 114, 170502 arXiv:1504.

Improvements for AI systems

Precise characterization of optimal average success probability for (n, n-1) and (n, n-2) quantum random access codes allows for designing communication protocols that maximize data recovery reliability while adhering to a proven fundamental limit.
AI systems can be improved by designing quantum communication protocols where the optimal average success probability is exactly 1/2 plus half the ratio of qubits to bits, specifically for codes with m = n-1 or m = n-2.
A quantum receiver can utilize the full PGM output to bound the expected Hamming distance between a transmitted classical string and its decoded version by showing that Delta C PGM is bounded by 2n PC (1 - PC).
Quantum networks can be engineered with self-testing capabilities because the proof shows that for every (n, m) QRAC C with m in the specified range, P C is bounded as P C <= 1/2 + 1/2 r m n.
The optimal average success probability for binary (n, n-1) and (n, n-2) QRACs is exactly determined as 1/2 plus half the ratio of qubits to bits when m in these settings, which is crucial for optimizing quantum data compression schemes.