Pith. sign in

REVIEW 4 minor 25 references

Binary quantum random access codes that store n bits in n-1 or n-2 qubits cannot beat average success probability 1/2 + 1/2 sqrt(m/n).

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-14 11:55 UTC pith:QLCXGGGP

load-bearing objection Clean proof that settles the exact optimal ASP for all binary (n,n-1) and (n,n-2) QRACs by combining Lin–de Wolf PGM reduction with a PSD parity argument and Nayak.

arxiv 2607.10414 v1 pith:QLCXGGGP submitted 2026-07-11 quant-ph cs.ITmath.IT

Optimal Average Success Probabilities of Binary (n,n-1) and (n,n-2) Quantum Random Access Codes via a Proof of the Corresponding Conjectured Bound

Shuo Tan , Syed A. Jafar This is my paper
classification quant-ph cs.ITmath.IT
keywords quantum random access codespretty good measurementaverage success probabilityHamming distancepositive-semidefinite channelNayak boundoptimal QRAC
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

A quantum random access code compresses an n-bit classical string into m qubits so that any single randomly chosen bit can still be recovered with high probability. A long-standing numerical conjecture said that the best average success probability is at most one-half plus half the square root of m over n. Matching constructions already achieve this number when m equals n-1 or n-2, so the only missing piece was a matching upper bound. This paper supplies that proof: every such code is at most as good as the constructions, fixing the exact optimal value. The argument works by turning local bit-wise recoveries into a global pretty-good measurement whose expected Hamming distance to the original string can be bounded both from above (via local success rates) and from below (via dimension and positive-semidefiniteness). The result therefore settles optimality for the two highest-rate regimes where constructions already saturate the conjectured formula.

Core claim

For every binary (n,m) quantum random access code with m equal to n-1 or n-2, the average success probability is at most 1/2 + 1/2 sqrt(m/n). Together with existing constructions that achieve the same number, this completely determines the optimal average success probability for both families.

What carries the argument

The full-string pretty-good measurement (PGM) induced by the code ensemble. Its coordinate-wise marginals recover the one-bit PGMs, so Renes’s refined bound converts average success probability into an upper estimate on expected Hamming distance; dimensional and positive-semidefinite constraints on the same PGM channel then give a matching lower estimate when m is n-1 or n-2.

Load-bearing premise

That the bit-wise reduction of the global pretty-good measurement is exactly the optimal one-bit pretty-good measurement for each coordinate, so local success rates control the expected Hamming distance.

What would settle it

Exhibit any (n,n-1) or (n,n-2) encoding ensemble whose average success probability (after optimal bit-wise decoding) strictly exceeds 1/2 + 1/2 sqrt(m/n), or show that the expected Hamming distance of its full-string PGM falls below the lower bound (n-m)/2 used in the proof.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Suzuki’s (n,n-1) construction is optimal for every n.
  • Akibue et al.’s (n,n-2) construction is optimal for every n.
  • The exact values P^{Q,avg,opt}_{n,n-1} = 1/2 + 1/2 sqrt((n-1)/n) and P^{Q,avg,opt}_{n,n-2} = 1/2 + 1/2 sqrt((n-2)/n) are now known.
  • The same dimensional-plus-PSD argument already yields a strictly tighter numerical upper bound for certain non-power-of-two dimensions (e.g., n=4, D=6).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same PGM-distance method may give non-trivial bounds for other sparse m (for instance m=n-3) once a sufficiently strong lower estimate on expected Hamming distance is available.
  • Because the three lemmas never require the Hilbert-space dimension to be a power of two, the technique applies directly to qudit random-access codes.
  • Tightness for intermediate dimensions is not automatic; the paper’s n=4, D=6 calculation already shows that naive logarithmic interpolation of the square-root formula can over-estimate the true optimum.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The manuscript proves that every binary (n,m) QRAC with m ∈ {n-1,n-2} satisfies P^C ≤ 1/2 + (1/2)√(m/n). Combined with the matching constructions of Suzuki (m=n-1) and Akibue et al. (m=n-2), this determines the exact optima P^{Q,avg,opt}_{n,n-1} and P^{Q,avg,opt}_{n,n-2}. The argument proceeds by relating average success probability to the expected Hamming distance Δ^{C,PGM} under the full-string pretty-good measurement: Lemma 1 upper-bounds Δ via Renes’s one-bit PGM inequality and Jensen; Lemmas 2–3 establish that the PGM channel matrix is PSD and therefore that the Hamming distance is not more likely to be odd than even; Nayak’s dimension bound then forces Δ ≥ (n-m)/2 for the two cases, which rearranges into the claimed inequality.

Significance. Exact values of P^{Q,avg,opt}_{n,m} have been known only for a handful of small pairs. Establishing the conjectured bound for the two infinite families m=n-1 and m=n-2 therefore closes a natural open question and certifies the optimality of two recent constructions. The proof is short, elementary, and self-contained once the Lin–de Wolf coordinate-reduction fact and Nayak’s bound are granted; it also yields a modestly tighter estimate for certain non-power-of-two dimensions (the n=4, D=6 example). These features make the note a clean and useful contribution to the QRAC literature.

minor comments (4)
  1. The Discussion notes that none of the three lemmas require the ambient dimension to be a power of two, yet the main theorem is stated only for m qubits. A one-sentence remark clarifying that the same argument applies verbatim to any encoding dimension D with log2 D ∈ {n-1,n-2} would make the scope fully explicit.
  2. In the proof of Lemma 1 the passage from the coordinate-wise bounds to the averaged form (21) invokes Jensen on z(1-z). Adding the elementary observation that equality holds when all p_i^C are equal would make the tightness discussion cleaner.
  3. The citation to Lin & de Wolf (arXiv:2506.01903) is essential for the coordinate-reduction step. Because that work is still a preprint, a brief parenthetical restatement of the precise claim used (that the bit-wise marginal of the full-string PGM is the one-bit PGM) would improve self-containment.
  4. Typographical consistency: the abstract writes P^{Q,avg,opt}_{n,m} while the body occasionally drops the superscripts; a uniform macro would eliminate the minor visual discrepancy.

Circularity Check

0 steps flagged

No circularity: the upper bound is derived from first-principles lemmas on the full-string PGM channel (PSD Gram matrix, parity via sign character, Jensen on z(1-z)) plus external dimension and coordinate-reduction facts; matching constructions are cited only for equality, not inside the converse.

full rationale

The central claim (Theorem 1) is an upper bound P^C ≤ 1/2 + 1/2 sqrt(m/n) for every (n,m) QRAC with m ∈ {n-1,n-2}. It is obtained by combining three lemmas proved in full inside the manuscript (upper estimate on expected Hamming distance Δ via Renes one-bit PGM + Jensen; PSD of the PGM transition matrix as a Gram matrix; parity bound P[odd Hamming] ≤ 1/2 from the sign character) with two external, non-author facts (Lin–de Wolf coordinate reduction of the full-string PGM, and Nayak’s dimension bound P[Y=X] ≤ 2^{m-n}). No parameter is fitted to data, no quantity is defined in terms of the target success probability, and no uniqueness or ansatz is imported from the authors’ own prior work. The matching lower bounds that turn the inequality into an exact optimum are taken from independent constructions of Suzuki and of Akibue et al.; those citations appear only after the converse is complete and are not used inside it. The derivation is therefore self-contained against external benchmarks and exhibits none of the six circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

The derivation rests on three external theorems (Nayak dimension bound, Renes one-bit PGM inequality, Lin–de Wolf PGM reduction) together with elementary linear-algebra facts (Gram matrices are PSD, Jensen’s inequality for the concave function z(1-z)). No free parameters or newly postulated physical entities are introduced.

axioms (5)
  • domain assumption Nayak’s bound: any measurement of an m-qubit encoding of a uniform n-bit string recovers the whole string with probability at most 2^{m-n}.
    Invoked as Eq. (36) to lower-bound the expected Hamming distance for m = n-1 and m = n-2.
  • domain assumption Renes’s refined pretty-good-measurement success bound for binary ensembles: success probability of the one-bit PGM is at least p*^2 + (1-p*)^2.
    Used in the proof of Lemma 1 to convert coordinate-wise success probabilities into an upper bound on expected Hamming distance.
  • domain assumption Lin–de Wolf theorem: the bit-wise marginal of the full-string PGM is exactly the one-bit PGM for each coordinate.
    Cited at the beginning of Lemma 1; without it the Renes bound cannot be applied to the global measurement.
  • standard math A real Gram matrix formed by Hilbert–Schmidt inner products is positive semidefinite.
    Lemma 2; used to obtain the parity bound of Lemma 3.
  • standard math Jensen’s inequality for the concave function z(1-z) on [0,1].
    Applied in Eq. (21) of Lemma 1 to pass from coordinate-wise to average success probability.

pith-pipeline@v1.1.0-grok45 · 13361 in / 2515 out tokens · 34066 ms · 2026-07-14T11:55:17.652408+00:00 · methodology

0 comments
read the original abstract

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

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 12 linked inside Pith

  1. [1]

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

    1973

  2. [2]

    Ambainis, A

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

    1999

  3. [3]

    Klauck, inProc

    H. Klauck, inProc. 32nd Annu. ACM Symp. Theory Comput. (STOC)(ACM, 2000) pp. 644–651

    2000

  4. [4]

    Aaronson, inProc

    S. Aaronson, inProc. 19th IEEE Annu. Conf. Com- put. Complexity (CCC)(IEEE, 2004) pp. 320–332, arXiv:quant-ph/0402095

    Pith/arXiv arXiv 2004

  5. [5]

    Hayashi, K

    M. Hayashi, K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita, inAnnual Symposium on Theoretical As- pects of Computer Science(Springer, 2007) pp. 610–621

    2007

  6. [6]

    Kerenidis and R

    I. Kerenidis and R. de Wolf, J. Comput. Syst. Sci.69, 395 (2004)

    2004

  7. [7]

    Wehner and R

    S. Wehner and R. de Wolf, inAutomata, Languages and Programming (ICALP), Lecture Notes in Com- puter Science, Vol. 3580 (Springer, 2005) pp. 1424–1436, arXiv:quant-ph/0403140

    Pith/arXiv arXiv 2005

  8. [8]

    Brunner, M

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

    2013

  9. [9]

    Pawłowski and N

    M. Pawłowski and N. Brunner, Phys. Rev. A84, 010302 (2011)

    2011

  10. [10]

    Li, Z.-Q

    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. A84, 034301 (2011)

    2011

  11. [11]

    H.-W. Li, M. Pawłowski, Z.-Q. Yin, G.-C. Guo, and Z.-F. Han, Phys. Rev. A85, 052308 (2012)

    2012

  12. [12]

    A.Tavakoli, A.Hameedi, B.Marques,andM.Bourennane, Phys. Rev. Lett.114, 170502 (2015), arXiv:1504.08105 [quant-ph]. 5

    Pith/arXiv arXiv 2015

  13. [13]

    Farkas and J

    M. Farkas and J. Kaniewski, Phys. Rev. A99, 032316 (2019), arXiv:1803.00363 [quant-ph]

    Pith/arXiv arXiv 2019

  14. [14]

    Nayak, inProc

    A. Nayak, inProc. 40th Annu. Symp. Found. Comput. Sci. (FOCS)(IEEE, 1999) pp. 369–376

    1999

  15. [15]

    Ambainis, D

    A. Ambainis, D. Leung, L. Mančinska, and M. Ozols, Quantum random access codes with shared randomness (2008), arXiv:0810.2937 [quant-ph]

    Pith/arXiv arXiv 2008

  16. [16]

    Imamichi and R

    T. Imamichi and R. Raymond, inProc. 18th Asian Quan- tum Inf. Sci. Conf. (AQIS)(2018)

    2018

  17. [17]

    Mančinska and S

    L. Mančinska and S. A. L. Storgaard, Quantum Inf. Pro- cess.21, 143 (2022), arXiv:2106.00155 [quant-ph]

    Pith/arXiv arXiv 2022

  18. [18]

    Farkas, N

    M. Farkas, N. Miklin, and A. Tavakoli, Quantum9, 1643 (2025), arXiv:2312.14142 [quant-ph]

    Pith/arXiv arXiv 2025

  19. [19]

    Lin and R

    H.-H. Lin and R. de Wolf, Getting almost all the bits from a quantum random access code (2025), arXiv:2506.01903 [quant-ph]

    Pith/arXiv arXiv 2025

  20. [20]

    Suzuki, Analytical construction of(n, n− 1)-quantum random access codes saturating the conjectured bound (2026), accepted in Phys

    T. Suzuki, Analytical construction of(n, n− 1)-quantum random access codes saturating the conjectured bound (2026), accepted in Phys. Rev. A, doi:10.1103/fcz5-2g3w, arXiv:2601.19190 [quant-ph]

    Pith/arXiv arXiv doi:10.1103/fcz5-2g3w 2026

  21. [21]

    Akibue, R

    S. Akibue, R. Raymond, S. Tamaki, and K. Teramoto, Measurement geometry for quantum random access codes: Beyond Nayak bound and toward optimality (2026), arXiv:2606.12700 [quant-ph]

    Pith/arXiv arXiv 2026

  22. [22]

    Kondo, Y

    R. Kondo, Y. Sato, H. Yano, Y. Maeda, K. Ito, and N. Yamamoto, arXiv preprint arXiv:2604.21274 (2026)

    Pith/arXiv arXiv 2026

  23. [23]

    Hausladen and W

    P. Hausladen and W. K. Wootters, J. Mod. Opt.41, 2385 (1994)

    1994

  24. [24]

    Hausladen, R

    P. Hausladen, R. Jozsa, B. Schumacher, M. Westmoreland, and W. K. Wootters, Phys. Rev. A54, 1869 (1996)

    1996

  25. [25]

    J. M. Renes, Phys. Rev. A96, 042328 (2017), arXiv:1707.01114 [quant-ph]

    Pith/arXiv arXiv 2017