Classical codes violate the conjectured square-root bound for quantum random access codes

Kangqiao Liu

This paper shows that the conjectured square-root bound for quantum random access codes is false: classical random access codes with private randomness, embedded as QRACs with diagonal states and commuting measurements, violate it for every

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 · deepseek-v4-flash

2026-08-01 23:05 UTC pith:27OXZUD2

load-bearing objection A clean classical embedding refutes the square-root QRAC conjecture; the only real question is whether the cited ANTV theorem supports the exact worst-case finite-blocklength claim.

arxiv 2607.15617 v1 pith:27OXZUD2 submitted 2026-07-17 quant-ph cs.ITmath.IT

Classical codes violate the conjectured square-root bound for quantum random access codes

Kangqiao Liu This is my paper

classification quant-ph cs.ITmath.IT MSC 81P4594A17 PACS 03.67.Hk

keywords quantum random access codesclassical random access codesprivate randomnessworst-case success probabilitysquare-root boundentropy boundcommuting POVMslogarithmic qubit scaling

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.

The paper addresses whether every quantum random access code (QRAC)—a scheme compressing n bits into m qubits so that any one bit can be recovered—obeys the conjectured inequality p ≤ (1 + sqrt(m/n))/2, where p is the worst-case success probability. The author shows the conjecture is false for the general unrestricted model: classical random access codes with private randomness, which form a special subclass of QRACs, already violate it. The construction embeds such classical codes as QRACs with diagonal encoding states and commuting measurements, then uses the known achievability result that classical messages of length (1−h₂(p))n + O(log n) bits suffice. Because 1−h₂(p) is strictly less than (2p−1)², the embedded codes sit above the square-root curve. If correct, this refutes the conjecture and identifies the classical coding rate, not quantum effects, as the source of the separation.

Core claim

Within the general model of quantum random access codes—where n classical bits are encoded into m qubits and any one bit is recovered with worst-case success p—this paper proves the conjectured bound p ≤ (1+sqrt(m/n))/2 is violated by the classical sector. Specifically, for every fixed p in (1/2,1) and all sufficiently large n, there exist (n,m,p) QRACs with m/n < (2p−1)², obtained by embedding classical random access codes with private randomness and deterministic decoders into diagonal density operators and commuting projective measurements. A pure-state realization reproduces the same statistics. At fixed compression rate r = m/n, the achievable pairs fill the entire open interval between

What carries the argument

The load-bearing object is the embedding of a classical random access code into the QRAC formalism: message probabilities become diagonal entries of density matrices, decoder probabilities become diagonal POVM effects, and deterministic decoders become projective measurements. Proposition 2 identifies this diagonal sector exactly with QRACs whose decoding measurements commute. The driving identity is the strict gap 1−h₂(p) < (2p−1)² for p in (1/2,1); combined with the achievability result that (1−h₂(p))n + O(log n) classical message bits suffice, this places the embedded code's rate below ns², the threshold needed to violate the conjectured square-root expression.

Load-bearing premise

The central premise is the achievability theorem for classical random access codes with private randomness and deterministic decoders: worst-case success p using at most (1−h₂(p))n + O(log n) message bits. If that theorem fails for worst-case success (for instance if it only holds for average-case success), or if the covering-code construction sketched in Appendix A is not valid, the counterexamples collapse.

What would settle it

Check the claimed finite-blocklength example: the paper says a (4096, 858, 3/4) QRAC exists, which requires a classical RAC with 858-bit messages and worst-case success 3/4. An explicit construction or exhaustive search at this size either verifies or refutes Proposition 3; more generally, finding any p in (1/2,1) where no classical RAC with message length below n(2p−1)² exists at large n would falsify the paper's central claim.

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

If this is right

The conjectured square-root bound cannot hold for the unrestricted density-operator QRAC model; any valid general bound must allow at least the entropic curve as a boundary.
At every fixed compression rate r in (0,1), the entire open window between the square-root curve and the entropy curve is achievable for sufficiently large n.
The asymptotic worst-case boundary of the unrestricted QRAC model is the entropy bound, and it is reached by classical codes—quantum encodings are not required for the extremal rate.
The counterexamples are stable: small perturbations of states and decoding measurements preserve the violation, and noncommuting projective decoders exist arbitrarily close to the commuting ones.
With vanishing bias proportional to sqrt(log n/n) and a sufficiently large prefactor, only Θ(log n) qubits are needed to violate the bound, and this logarithmic scaling is order-optimal.

Where Pith is reading between the lines

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

A likely consequence the paper leaves implicit: any future bound that hopes to exclude these counterexamples must either fix the dimension m or impose quantitative conditions on the decoding spectra—otherwise the classical rate alone forces the square-root bound to fail.
Because the violating codes are purely classical, device-independent or semi-device-independent conclusions drawn from QRAC success rates should account for private classical randomness as the possible source of apparent 'quantum' advantage.
A natural numerical test of the robustness claim: for small n, perturb a commuting realization within the operator-norm ball of Proposition 4 and verify the success gap persists while commutators become nonzero.
The rate-window mechanism may transfer to other information-theoretic tasks—such as parity-oblivious multiplexing or locally decodable codes—where a classical achievable rate can be embedded inside a quantum model.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

A clean classical embedding refutes the square-root QRAC conjecture; the only real question is whether the cited ANTV theorem supports the exact worst-case finite-blocklength claim.

read the letter

Short version: this paper kills the square-root conjecture for QRACs, provided the classical RAC achievability theorem of Ambainis et al. does what the paper says. I went through the main steps and they hold together. The diagonal embedding (Prop. 1) is correct, the commuting-POVM characterization (Prop. 2) is correct, and the entropy inequality 1-h2(p) < (2p-1)^2 is strict for every p in (1/2,1). Once you have classical RACs with message length (1-h2(p))n + O(log n) and worst-case success p, the violation follows by arithmetic. The rate-window corollary is a nice way to see the counterexamples fill the gap between the square-root curve and Nayak's curve.

The main soft spot is the reliance on the ANTV theorem. The paper cites it properly, and Appendix A sketches the finite-blocklength version, but the sketch is too compressed to verify independently. It mentions a covering-code index and n^3 permutation-mask pairs, then waves at a Chernoff bound and union bound to get a worst-case guarantee. A referee should check that the theorem really applies to this exact model: private randomness, deterministic decoders, worst-case success. If it only holds for average-case success or needs shared randomness, this construction collapses. I would want the appendix expanded before publication, but I would not call it a fatal flaw. The citation is to a standard published result, and the rest of the paper is transparent.

The finite-blocklength corollaries look right conditional on that theorem, and the logarithmic qubit scaling is a nice bonus. The robustness section is fine; the perturbation argument is standard.

Overall, this deserves a serious referee. The result is significant because a plausible conjecture has been refuted by a simple classical construction. I would accept it after the ANTV details are checked and the appendix is made self-contained enough for a skeptic. It will likely be cited as the definitive counterexample to the square-root bound, so the check is worth doing carefully.

Referee Report

0 major / 6 minor

Summary. The paper addresses the conjectured bound p ≤ (1+√(m/n))/2 for worst-case QRACs with density-operator encodings and arbitrary decoding POVMs. It shows that classical RACs with private randomness can be embedded as QRACs with diagonal encoding states and mutually commuting decoding POVMs (Prop. 1), and conversely that every QRAC with commuting POVMs is equivalent to such a classical RAC (Prop. 2). Combining the ANTV achievability theorem — classical RACs with private randomness, deterministic decoders, worst-case success p, and message length (1−h2(p))n+O(log n) — with the strict entropy gap 1−h2(p) < (2p−1)^2, the paper constructs, for every fixed p∈(1/2,1) and all sufficiently large n, QRACs that violate the conjectured bound. It also proves a rate-window statement (Cor. 2), finite-blocklength guarantees with explicit constants (Prop. 3), logarithmic-qubit codes for vanishing bias (Cor. 1), and robustness of the counterexamples under perturbations (Prop. 4).

Significance. If correct, the paper refutes a conjecture that has served as a benchmark in recent QRAC literature and shows that, in the unrestricted density-operator model, the asymptotic worst-case boundary is the Nayak entropy curve rather than the square-root curve. The construction is parameter-free and explicit; the central argument is a clean rate comparison with no fitted parameters. The commuting-POVM characterization and the robustness analysis are valuable. The counterexamples are falsifiable and the proof is mostly transparent. The main weakness is that the finite-blocklength proof of the ANTV-based construction in Appendix A is compressed, but the asymptotic counterexamples rest on a cited theorem and the underlying covering-code/permutation argument is standard.

minor comments (6)

[Appendix A, proof of Prop. 3 and Eq. (6)] The sketch needs to be expanded. Specify the covering-code construction (radius, size bound), the distribution of the n^3 permutation-mask pairs, and the Chernoff bound with its deviation parameter. The sentence 'A Chernoff bound of e^{-2n} applies to each pair (x,i)' does not define the random variable; the worst-case-over-i property is exactly what needs to be established. This is important for the finite-blocklength claims and Corollary 1.
[Section III, Theorem 1] The paper should state ANTV Theorem 2.2 (and Theorem 5.2 of [3]) precisely, including the worst-case success guarantee and the origin of the O(log n) term, since the entire counterexample family reduces to this theorem. A paraphrase is insufficient for a reader to verify the central claim without going to the cited literature.
[Section II, Eq. (4)] The term 'private randomness' should be clarified: the randomness is in the encoder's stochastic map, and the decoder observes the sampled message; it is not shared randomness or randomness hidden from the decoder. The current wording could be misread as a shared-randomness model.
[Corollary 1] The numerical threshold 25.120896... follows from the constant 7 in Eq. (6). If the expanded proof changes that constant, the threshold and the statement 'C > 7/a' should be updated accordingly.
[Fig. 1 and Table I] Label the markers with the corresponding rate m/n or add a rate column to the table to make the placement in the (r,p) plane immediate. Currently the reader must compute m/n from the table.
[Abstract and full text] Some equations render with broken radicals (e.g., in the abstract and Eq. (13)); the final manuscript should use consistent formatting.

Circularity Check

0 steps flagged

No significant circularity: the central derivation relies on external achievability and converse results, not on the conjectured bound being tested.

full rationale

The paper's derivation chain is self-contained in the sense required by the circularity rules. The counterexample construction combines (i) a direct embedding of classical RACs into diagonal-state QRACs (Propositions 1 and 2), (ii) the external ANTV achievability theorem giving classical message length (1-h2(p))n + O(log n), and (iii) an independent entropy inequality 1-h2(p) < s^2 derived in Appendix A. No parameter is fitted to force the target violation; the conjectured square-root bound is never used as an input. The classical characterization in Proposition 2 is derived from simultaneous diagonalization, not assumed. The paper contains no load-bearing self-citation: the cited external results are prior literature by other authors or, where close in topic, are not used as the justification for the main construction. The only substantive concern raised by a skeptical reading is whether the finite-blocklength ANTV-style construction sketched in Appendix A rigorously delivers worst-case classical RACs with deterministic decoders; that is a question of correctness or completeness of an external benchmark, not a circularity. Accordingly, the appropriate score is 0.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The central argument depends on the ANTV achievability theorem (external prior literature) and on the binary-entropy inequality, which is proven in the appendix. Neither is fit to the target result. No free parameters or invented entities appear.

axioms (3)

domain assumption ANTV achievability theorem: classical RACs with private randomness, deterministic decoders, and worst-case success p exist with message length (1-h2(p))n + O(log n).
Invoked in Sec. III, Eq. (6) and Theorem 1. The counterexample family rests on this external theorem; the appendix only sketches the covering-code/permutation-mask proof.
standard math Binary entropy deficit inequality 1 - h2((1+s)/2) < s^2 for s in (0,1).
Derived in Appendix A using the series expansion; it creates the gap between the ANTV rate and the square-root rate, and is load-bearing for all counterexamples.
domain assumption Nayak's information-theoretic lower bound m >= (1-h2(p))n for QRACs.
Used in Sec. VII and Corollary 1 as the matching converse; identifies the upper endpoint of the rate window and the order-optimal logarithmic scaling claim.

pith-pipeline@v1.3.0-alltime-deepseek · 49 in / 54040 out tokens · 1373365 ms · 2026-08-01T23:05:06.002366+00:00 · methodology

0 comments

read the original abstract

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.

Figures

Figures reproduced from arXiv: 2607.15617 by Kangqiao Liu.

discussion (0)

Reference graph

Works this paper leans on

21 extracted references · 5 linked inside Pith

[1]

Wiesner, Conjugate coding, SIGACT News15, 78–88 (1983)

S. Wiesner, Conjugate coding, SIGACT News15, 78–88 (1983)

1983
[2]

Ambainis, A

A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani, Dense quantum coding and a lower bound for 1-way quantum automata, inProceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC ’99 (Association for Computing Machinery, New York, NY, USA,
[3]

Ambainis, A

A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani, Dense quantum coding and quantum finite automata, J. ACM49, 496–511 (2002)

2002
[4]

A. Nayak, Optimal lower bounds for quantum automata and random access codes, inProceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS ’99 (IEEE Computer Society, USA, 1999) p. 369

1999
[5]

Kerenidis and R

I. Kerenidis and R. de Wolf, Exponential lower bound for 2-query locally decodable codes via 15 a quantum argument, Journal of Computer and System Sciences69, 395 (2004), special Issue on STOC 2003

2004
[6]

Wehner, M

S. Wehner, M. Christandl, and A. C. Doherty, Lower bound on the dimension of a quantum system given measured data, Phys. Rev. A78, 062112 (2008)

2008
[7]

Gallego, N

R. Gallego, N. Brunner, C. Hadley, and A. Ac ´ ın, Device-independent tests of classical and quantum dimensions, Phys. Rev. Lett.105, 230501 (2010)

2010
[8]

Paw lowski and N

M. Paw lowski and N. Brunner, Semi-device-independent security of one-way quantum key distribution, Phys. Rev. A84, 010302(R) (2011)

2011
[9]

H.-W. Li, M. Paw lowski, Z.-Q. Yin, G.-C. Guo, and Z.-F. Han, Semi-device-independent randomness certification using n→ 1 quantum random access codes, Phys. Rev. A85, 052308 (2012)

2012
[10]

R. W. Spekkens, D. H. Buzacott, A. J. Keehn, B. Toner, and G. J. Pryde, Preparation contextuality powers parity-oblivious multiplexing, Phys. Rev. Lett.102, 010401 (2009)

2009
[11]

Manˇ cinska and S

L. Manˇ cinska and S. A. L. Storgaard, The geometry of bloch space in the context of quantum random access codes, Quantum Information Processing21, 143 (2022)

2022
[12]

Ambainis, D

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

Pith/arXiv arXiv 2009
[13]

Imamichi and R

T. Imamichi and R. Raymond, Constructions of quantum random access codes, inAsian Quantum Information Symposium (AQIS), Vol. 66 (2018)

2018
[14]

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

T. Suzuki, Analytical construction of ( n, n− 1)-quantum random access codes saturating the conjectured bound, Phys. Rev. A114, 012441 (2026)

2026
[15]

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
[16]

Kondo, Y

R. Kondo, Y. Sato, H. Yano, Y. Maeda, K. Ito, and N. Yamamoto, Random access codes: Explicit constructions, optimality, and classical-quantum gaps (2026), arXiv:2604.21274 [quant- ph]

Pith/arXiv arXiv 2026
[17]

Liabøtrø, Improved classical and quantum random access codes, Phys

O. Liabøtrø, Improved classical and quantum random access codes, Phys. Rev. A95, 052315 (2017)

2017
[18]

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]. 16

Pith/arXiv arXiv 2025
[19]

Carmeli, Claudio, Heinosaari, Teiko, and Toigo, Alessandro, Quantum random access codes and incompatibility of measurements, EPL130, 50001 (2020)

2020
[20]

Tan and S

S. Tan and S. A. Jafar, 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 (2026), arXiv:2607.10414 [quant-ph]

Pith/arXiv arXiv 2026
[21]

Farkas, N

M. Farkas, N. Miklin, and A. Tavakoli, Simple and general bounds on quantum random access codes, Quantum9, 1643 (2025). 17

2025

[1] [1]

Wiesner, Conjugate coding, SIGACT News15, 78–88 (1983)

S. Wiesner, Conjugate coding, SIGACT News15, 78–88 (1983)

1983

[2] [2]

Ambainis, A

A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani, Dense quantum coding and a lower bound for 1-way quantum automata, inProceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC ’99 (Association for Computing Machinery, New York, NY, USA,

[3] [3]

Ambainis, A

A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani, Dense quantum coding and quantum finite automata, J. ACM49, 496–511 (2002)

2002

[4] [4]

A. Nayak, Optimal lower bounds for quantum automata and random access codes, inProceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS ’99 (IEEE Computer Society, USA, 1999) p. 369

1999

[5] [5]

Kerenidis and R

I. Kerenidis and R. de Wolf, Exponential lower bound for 2-query locally decodable codes via 15 a quantum argument, Journal of Computer and System Sciences69, 395 (2004), special Issue on STOC 2003

2004

[6] [6]

Wehner, M

S. Wehner, M. Christandl, and A. C. Doherty, Lower bound on the dimension of a quantum system given measured data, Phys. Rev. A78, 062112 (2008)

2008

[7] [7]

Gallego, N

R. Gallego, N. Brunner, C. Hadley, and A. Ac ´ ın, Device-independent tests of classical and quantum dimensions, Phys. Rev. Lett.105, 230501 (2010)

2010

[8] [8]

Paw lowski and N

M. Paw lowski and N. Brunner, Semi-device-independent security of one-way quantum key distribution, Phys. Rev. A84, 010302(R) (2011)

2011

[9] [9]

H.-W. Li, M. Paw lowski, Z.-Q. Yin, G.-C. Guo, and Z.-F. Han, Semi-device-independent randomness certification using n→ 1 quantum random access codes, Phys. Rev. A85, 052308 (2012)

2012

[10] [10]

R. W. Spekkens, D. H. Buzacott, A. J. Keehn, B. Toner, and G. J. Pryde, Preparation contextuality powers parity-oblivious multiplexing, Phys. Rev. Lett.102, 010401 (2009)

2009

[11] [11]

Manˇ cinska and S

L. Manˇ cinska and S. A. L. Storgaard, The geometry of bloch space in the context of quantum random access codes, Quantum Information Processing21, 143 (2022)

2022

[12] [12]

Ambainis, D

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

Pith/arXiv arXiv 2009

[13] [13]

Imamichi and R

T. Imamichi and R. Raymond, Constructions of quantum random access codes, inAsian Quantum Information Symposium (AQIS), Vol. 66 (2018)

2018

[14] [14]

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

T. Suzuki, Analytical construction of ( n, n− 1)-quantum random access codes saturating the conjectured bound, Phys. Rev. A114, 012441 (2026)

2026

[15] [15]

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

[16] [16]

Kondo, Y

R. Kondo, Y. Sato, H. Yano, Y. Maeda, K. Ito, and N. Yamamoto, Random access codes: Explicit constructions, optimality, and classical-quantum gaps (2026), arXiv:2604.21274 [quant- ph]

Pith/arXiv arXiv 2026

[17] [17]

Liabøtrø, Improved classical and quantum random access codes, Phys

O. Liabøtrø, Improved classical and quantum random access codes, Phys. Rev. A95, 052315 (2017)

2017

[18] [18]

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]. 16

Pith/arXiv arXiv 2025

[19] [19]

Carmeli, Claudio, Heinosaari, Teiko, and Toigo, Alessandro, Quantum random access codes and incompatibility of measurements, EPL130, 50001 (2020)

2020

[20] [20]

Tan and S

S. Tan and S. A. Jafar, 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 (2026), arXiv:2607.10414 [quant-ph]

Pith/arXiv arXiv 2026

[21] [21]

Farkas, N

M. Farkas, N. Miklin, and A. Tavakoli, Simple and general bounds on quantum random access codes, Quantum9, 1643 (2025). 17

2025