arxiv: 2604.21274 · v1 · submitted 2026-04-23 · 🪐 quant-ph · cs.IT· math.IT

Recognition: unknown

Random Access Codes: Explicit Constructions, Optimality, and Classical-Quantum Gaps

Ruho Kondo , Yuki Sato , Hiroshi Yano , Yota Maeda , Kosuke Ito , Naoki Yamamoto

Authors on Pith no claims yet

Pith reviewed 2026-05-09 22:27 UTC · model grok-4.3

classification 🪐 quant-ph cs.ITmath.IT

keywords random access codesquantum random access codesexplicit constructionsoptimalityclassical-quantum gapaverage-case criterionworst-case criterion

0 comments

The pith

A framework reduces optimal random access code design to point selection, yielding explicit constructions that attain upper bounds for k equal to L minus one.

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

The paper develops a constructive approach to classical random access codes that encode an L-bit string into a k-bit message while allowing reliable recovery of any chosen bit. It shows that finding the best codes reduces to selecting 2^k points to minimize a distance-like cost, first in the binary hypercube for average-case performance and then in the unit hypercube for worst-case. This reduction produces explicit encoders and decoders for any L and k, with closed-form solutions when only one bit is discarded. The resulting classical codes reach the previously proven upper limits on success probability, and the same codes induce quantum random access codes that meet a conjectured bound. The work matters because it supplies concrete optimal objects where only abstract bounds existed before, clarifying how much information can be compressed while preserving random access.

Core claim

We develop a constructive framework for classical (L,k)-RACs under both average- and worst-case criteria. We show that optimal code design reduces to selecting 2^k points in {0,1}^L and [0,1]^L for the average- and worst-case criteria, respectively, so as to minimize a distance-like objective. This characterization yields explicit constructions for general (L,k). For k=L-1, we further obtain closed-form optimal encoders and decoders for both criteria, and show that the resulting classical (L,L-1)-RACs attain the corresponding proved upper bounds. We also show that these optimal classical codes induce (L,L-1)-QRACs that attain a conjectured upper bound on the decoding success probability.

What carries the argument

Reduction of optimal (L,k)-RAC design to selecting 2^k points that minimize a distance-like objective in the appropriate space.

Load-bearing premise

That the true optimum is always achieved by some selection of exactly 2^k points under the stated distance-like objective.

What would settle it

An explicit (L,L-1)-RAC encoder-decoder pair whose average or worst-case success probability exceeds that of the closed-form construction for any L greater than or equal to 3.

Figures

Figures reproduced from arXiv: 2604.21274 by Hiroshi Yano, Kosuke Ito, Naoki Yamamoto, Ruho Kondo, Yota Maeda, Yuki Sato.

**Figure 1.** Figure 1: Decoding success probability of RACs and QRACs for L ≤ 7 and k = 3. Conjectural upper bound of QRAC (Eq. (4)) is included. References [1] Wiesner, S. Conjugate coding. ACM Sigact News, 15 (1):78–88, 1983. doi: 10.1145/1008908.1008920. [2] Ambainis, A., Nayak, A., Ta-Shma, A. and Vazirani, U. Dense quantum coding and a lower bound for 1- way quantum automata. In Proceedings of the thirtyfirst annual ACM sy… view at source ↗

**Figure 2.** Figure 2: Achievable (conjecturally maximum) success probability of (L, L − 1)-RACs and (L, L − 1)-QRACs. Note that the maximum average success probability and the maximum worst case success probability are the same for (L, L − 1)-QRAC. For clarity, markers are shown only for L ≤ 10. [7] Sharma, M., Jin, Y., Lau, H.C. and Raymond, R. Quantum relaxation for solving multiple knapsack problems. In 2024 IEEE Internation… view at source ↗

read the original abstract

A random access code (RAC) encodes an $L$-bit string into a $k$-bit $(L>k)$ message from which any designated source bit can be recovered with high probability. Its quantum counterpart, a quantum random access code (QRAC), replaces the $k$-bit message with $k$ qubits. While upper bounds on the decoding success probability have long been studied in both classical and quantum settings, explicit constructions of optimal codes are known only in special cases, even for classical RACs. In this paper, we develop a constructive framework for classical $(L,k)$-RACs under both average- and worst-case criteria. We show that optimal code design reduces to selecting $2^k$ points in $\{0,1\}^L$ and $[0,1]^L$ for the average- and worst-case criteria, respectively, so as to minimize a distance-like objective. This characterization yields explicit constructions for general $(L,k)$. For $k=L-1$, we further obtain closed-form optimal encoders and decoders for both criteria, and show that the resulting classical $(L,L-1)$-RACs attain the corresponding proved upper bounds. We also show that these optimal classical codes induce $(L,L-1)$-QRACs that attain a conjectured upper bound on the decoding success probability. Numerical optimization suggests little difference between RACs and QRACs in the average-case setting, but a potentially large classical-quantum gap in the worst-case nonasymptotic regime.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives explicit constructions for general (L,k) classical RACs via a geometric reduction to point selection, plus closed-form optimal codes for k=L-1 that hit the proved bounds and induce QRACs hitting a conjecture.

read the letter

This paper's main advance is explicit constructions for classical (L,k) random access codes that reach the known upper bounds when k equals L minus one, under both average- and worst-case decoding success. It also turns those codes into quantum versions that meet a conjectured quantum bound. The authors reduce the whole design task to choosing 2^k points in the hypercube or unit cube to minimize a distance objective, which then yields the general constructions and the closed forms for the special case. Numerical checks suggest the classical-quantum gap stays small on average but opens up more in the worst-case non-asymptotic regime. That geometric view is a useful way to see why the codes work and why the bounds are tight. Concrete encoders and decoders are the practical payoff here, since most prior work stopped at existence or asymptotics. The reduction step is the load-bearing part. If it truly shows that the point selection gives the absolute optimum rather than just a good feasible code, then the attainment claims hold. The abstract states they prove the reduction, so the paper presumably walks through the equivalence for both criteria. Still, that direction needs checking to confirm no hidden restrictions on the decoder. The quantum side remains a conjecture being attained rather than proved, and the gap observations rest on numerical optimization whose thoroughness would matter for the worst-case claims. This is for people working on quantum information primitives who need actual finite-size codes or want to quantify classical-quantum differences beyond asymptotics. A reader focused on explicit constructions or RAC applications will get direct value from the closed forms and the geometric characterization. It has enough new, verifiable results to deserve a serious referee.

Referee Report

2 major / 3 minor

Summary. The manuscript develops a constructive framework for classical (L,k)-random access codes (RACs) under both average- and worst-case decoding success criteria. It reduces optimal code design to the selection of 2^k points in {0,1}^L (average-case) or [0,1]^L (worst-case) that minimize a distance-like objective, yielding explicit constructions for general (L,k). For the special case k=L-1, closed-form optimal encoders and decoders are derived that attain the corresponding proved upper bounds; these classical codes are shown to induce (L,L-1)-QRACs attaining a conjectured quantum upper bound. Numerical optimization is used to compare RACs and QRACs, indicating small gaps in the average-case setting but potentially large classical-quantum gaps in the worst-case non-asymptotic regime.

Significance. If the central reduction is valid and the constructions attain the stated bounds, the work provides valuable explicit optimal RAC constructions beyond the limited special cases previously known. The closed-form solutions for k=L-1 and the induced QRACs attaining the conjectured bound are strong results that clarify the limits of both classical and quantum random access codes. The geometric characterization offers a reusable tool for further constructions, and the numerical exploration of gaps contributes to understanding when quantum encodings may offer advantages. Credit is due for the explicit, constructive nature of the results and the direct comparison to independently proved upper bounds.

major comments (2)

[framework section / reduction to point selection] The reduction of optimal (L,k)-RAC design to selecting 2^k points minimizing the distance-like objective (abstract and framework section): this equivalence is load-bearing for the claim that the k=L-1 constructions attain the proved upper bounds under both criteria. The manuscript must explicitly establish whether the minimization yields both optimal encoders and decoders (bidirectional equivalence) or only feasible codes under a restricted decoder form. If only one direction holds, the attainment statements for the closed-form solutions do not follow. Please supply the full derivation of the reduction, including how the decoder is recovered from the point selection, for both average- and worst-case objectives.
[quantum extensions / QRAC induction] Induction of (L,L-1)-QRACs from the optimal classical codes and attainment of the conjectured quantum bound (section on quantum extensions): the construction of the quantum encoding from the classical point selection must be specified, together with the argument that the resulting QRAC meets the conjectured bound. Since the bound is conjectured rather than proved, the manuscript should also discuss the status of the conjecture and any supporting evidence beyond the numerical checks.

minor comments (3)

[framework section] The distance-like objective function should be given an explicit equation number and definition at its first appearance, with clear notation distinguishing the average-case (binary) and worst-case (continuous) versions.
[numerical results] Numerical results on the classical-quantum gap (final section): add explicit references to the relevant figures or tables when stating that optimization 'suggests little difference' in average-case versus 'potentially large' gaps in worst-case; include error bars or optimization tolerances to support the non-asymptotic claims.
[introduction] Ensure all citations to prior upper-bound results (both proved and conjectured) are complete and correctly referenced in the introduction and comparison sections.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We address each major comment below. The requested derivations and clarifications will be incorporated into the revised manuscript.

read point-by-point responses

Referee: [framework section / reduction to point selection] The reduction of optimal (L,k)-RAC design to selecting 2^k points minimizing the distance-like objective (abstract and framework section): this equivalence is load-bearing for the claim that the k=L-1 constructions attain the proved upper bounds under both criteria. The manuscript must explicitly establish whether the minimization yields both optimal encoders and decoders (bidirectional equivalence) or only feasible codes under a restricted decoder form. If only one direction holds, the attainment statements for the closed-form solutions do not follow. Please supply the full derivation of the reduction, including how the decoder is recovered from the point selection, for both average- and worst-case objectives.

Authors: The equivalence is bidirectional. The minimization over the 2^k points directly yields the optimal encoder by assigning each of the 2^k possible messages to one point in the selected set. The decoder is recovered by, for each of the L query positions, selecting the bit value that minimizes the contribution to the objective (via nearest-neighbor assignment in the average-case or threshold comparison in the worst-case). We will insert a dedicated subsection deriving this equivalence in full for both criteria, including explicit formulas for recovering the decoder from the points. This establishes that the closed-form k=L-1 solutions attain the upper bounds. revision: yes
Referee: [quantum extensions / QRAC induction] Induction of (L,L-1)-QRACs from the optimal classical codes and attainment of the conjectured quantum bound (section on quantum extensions): the construction of the quantum encoding from the classical point selection must be specified, together with the argument that the resulting QRAC meets the conjectured bound. Since the bound is conjectured rather than proved, the manuscript should also discuss the status of the conjecture and any supporting evidence beyond the numerical checks.

Authors: The quantum encoding is obtained by mapping each optimal classical point (a vector in {0,1}^L or [0,1]^L) to a k-qubit state via a fixed embedding that preserves the distance-like objective (specifically, preparing a state whose measurement statistics reproduce the classical decoding probabilities). Because the classical code is optimal, this embedding yields a QRAC whose success probability equals the conjectured quantum upper bound. We will add an explicit description of the embedding and the equality argument. We will also expand the discussion to note that the conjecture remains open in general but is supported by the paper's numerical results for small L, consistency with known special cases, and independent lower-bound constructions in the literature. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivations rest on proved reductions and independent upper bounds

full rationale

The paper proves that optimal (L,k)-RAC design reduces to selecting 2^k points minimizing a distance-like objective (for both average- and worst-case criteria), derives explicit and closed-form constructions for k=L-1 directly from this characterization, and verifies that the resulting codes attain separately proved upper bounds. No step renames a fitted parameter as a prediction, imports uniqueness via self-citation chains, or defines a quantity in terms of the result it claims to derive. The QRAC constructions are induced from the classical ones and compared to a conjectured bound without creating a definitional loop. The overall chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard information-theoretic upper bounds from prior literature and a geometric reformulation of the code design problem; no new free parameters or invented entities are introduced beyond the standard formulation of RACs.

axioms (1)

domain assumption Existence of proved upper bounds on decoding success probability for classical and quantum RACs
The paper states that the constructions attain these bounds, which are taken as given from earlier work.

pith-pipeline@v0.9.0 · 5585 in / 1281 out tokens · 31492 ms · 2026-05-09T22:27:09.476672+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

28 extracted references · 20 canonical work pages · 1 internal anchor

[1]

Optimal cloning of pure states

Wiesner, S. Conjugate coding. ACM Sigact News, 15 (1):78–88, 1983. doi: 10.1145/1008908.1008920

work page doi:10.1145/1008908.1008920 1983
[2]

and Vazirani, U

Ambainis, A., Nayak, A., Ta-Shma, A. and Vazirani, U. Dense quantum coding and a lower bound for 1- way quantum automata. In Proceedings of the thirty- first annual ACM symposium on Theory of computing, pages 376–383, 1999. doi: 10.1145/301250.301347

work page doi:10.1145/301250.301347 1999
[3]

Fuller, B. et al. Approximate solutions of combinatorial problems via quantum relaxations. IEEE Transactions on Quantum Engineering, 5:1–15, 2024. doi: 10.1109/ TQE.2024.3421294

work page arXiv 2024
[4]

Distribution of entanglement in two-dimensional square grid network,

Teramoto, K., Raymond, R. and Imai, H. The role of entanglement in quantum-relaxation based opti- mization algorithms. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 1, pages 543–553. IEEE, 2023. doi: 10.1109/QCE57702.2023.00068

work page doi:10.1109/qce57702.2023.00068 2023
[5]

Tamura, K. et al. Noise robustness of quantum relaxation for combinatorial optimization. IEEE Trans- actions on Quantum Engineering, 5:1–9, 2024. doi: 10.1109/TQE.2024.3439135

work page doi:10.1109/tqe.2024.3439135 2024
[6]

and Yamamoto, N

Kondo, R., Sato, Y., Raymond, R. and Yamamoto, N. Recursive quantum relaxation for combinatorial optimization problems. Quantum, 9:1594, 2025. doi: 10.22331/q-2025-01-15-1594. 13 101 102 103 Length of Original Bits L 0.5 0.6 0.7 0.8 0.9 1.0Maximum Success probability QRAC RAC (average) RAC (worst) Fig. 2. Achievable (conjecturally maximum) success probabi...

work page doi:10.22331/q-2025-01-15-1594 2025
[7]

Seitz, M

Sharma, M., Jin, Y., Lau, H.C. and Raymond, R. Quantum relaxation for solving multiple knapsack problems. In 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), vol- ume 1, pages 692–698. IEEE, 2024. doi: 10.1109/ QCE60285.2024.00086

work page arXiv 2024
[8]

and Pistoia, M

He, Z., Raymond, R., Shaydulin, R. and Pistoia, M. Non-variational quantum random access optimization with alternating operator ansatz. Scientific Reports, 15(1):29191, 2025. doi: 10.1038/s41598-025-13543-w

work page doi:10.1038/s41598-025-13543-w 2025
[9]

Feedback connections in quan- tum reservoir computing with mid-circuit measurements

Matsuyama, H. and Yamashiro, Y. Sampling-based quantum optimization algorithm with quantum relax- ation. In 2025 IEEE International Conference on Quan- tum Computing and Engineering (QCE), volume 01, pages 2323–2333, 2025. doi: 10.1109/QCE65121.2025. 00253

work page doi:10.1109/qce65121.2025 2025
[10]

and Ya- mashita, S

Iwama, K., Nishimura, H., Raymond, R. and Ya- mashita, S. Unbounded-error one-way classical and quantum communication complexity. In International Colloquium on Automata, Languages, and Program- ming, pages 110–121. Springer, 2007. doi: 10.1007/ 978-3-540-73420-8_12

2007
[11]

Optimal lower bounds for quantum automata and random access codes , Year =

Nayak, A. Optimal lower bounds for quantum au- tomata and random access codes. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 369–376. IEEE, 1999. doi: 10.1109/SFFCS.1999.814608

work page doi:10.1109/sffcs.1999.814608 1999
[12]

and Storgaard, S.A

Mančinska, L. and Storgaard, S.A. The geometry of bloch space in the context of quantum random access codes. Quantum Information Processing, 21(4):143,
[13]

doi: 10.1007/s11128-022-03470-4

work page doi:10.1007/s11128-022-03470-4
[14]

and Tavakoli, A

Farkas, M., Miklin, N. and Tavakoli, A. Sim- ple and general bounds on quantum random access codes. Quantum, 9:1643, 2025. doi: 10.22331/ q-2025-02-25-1643

2025
[15]

and Rai, A

Ambainis, A., Kravchenko, D., Sazim, S., Bae, J. and Rai, A. Quantum advantages in (n, d) 7! 1 random access codes. New Journal of Physics, 26(12):123023,
[16]

doi: 10.1088/1367-2630/ad9bdf

work page doi:10.1088/1367-2630/ad9bdf
[17]

and Bouren- nane, M

Tavakoli, A., Hameedi, A., Marques, B. and Bouren- nane, M. Quantum random access codes using single d- level systems. Physical review letters, 114(17):170502,
[18]

doi: 10.1103/PhysRevLett.114.170502

work page doi:10.1103/physrevlett.114.170502
[19]

and Raymond, R

Imamichi, T. and Raymond, R. Constructions of quantum random access codes. In Proceedings of the Asian Quantum Information Symposium (AQIS),
[20]

URL https://research.ibm.com/publications/ constructions-of-quantum-random-access-codes
[21]

and Imai, H

Teramoto, K., Raymond, R., Wakakuwa, E. and Imai, H. Quantum-relaxation based optimization algorithms: theoretical extensions. arXiv preprint arXiv:2302.09481, 2023. doi: 10.48550/arXiv.2302. 09481

work page internal anchor Pith review doi:10.48550/arxiv.2302 2023
[22]

Improved classical and quantum random access codes

Liabøtrø, O. Improved classical and quantum random access codes. Physical Review A, 95(5):052315, 2017. doi: 10.1103/PhysRevA.95.052315

work page doi:10.1103/physreva.95.052315 2017
[23]

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

Suzuki, T. Analytical construction of (n, n 1) quan- tum random access codes saturating the conjectured bound. arXiv preprint arXiv:2601.19190, 2026. doi: https://doi.org/10.48550/arXiv.2601.19190

work page doi:10.48550/arxiv.2601.19190 2026
[24]

and Wolf, H.C

Barrow, H.G., Tenenbaum, J.M., Bolles, R.C. and Wolf, H.C. Parametric correspondence and chamfer matching: Two new techniques for image matching. In Proceedings of the 5th International Joint Conference on Artificial Intelligence (IJCAI), pages 659–663, 1977. doi: 10.5555/1622943.1622971

work page doi:10.5555/1622943.1622971 1977
[25]

and Jain, A.K

Dubuisson, M.P. and Jain, A.K. A modified haus- dorff distance for object matching. In Proceedings of 12th international conference on pattern recogni- tion, volume 1, pages 566–568. IEEE, 1994. doi: 10.1109/ICPR.1994.576361

work page doi:10.1109/icpr.1994.576361 1994
[26]

Quantum Random Access Codes with Shared Randomness

Ambainis, A., Leung, D., Mancinska, L. and Ozols, M. Quantum random access codes with shared ran- domness. arXiv preprint arXiv:0810.2937, 2008. doi: 10.48550/arXiv.0810.2937

work page Pith review doi:10.48550/arxiv.0810.2937 2008
[27]

Grundzüge der Mengenlehre

Hausdorff, F. Grundzüge der Mengenlehre. Göschens Lehrbücherei/Gruppe I: Reine und Angewandte Math- ematik Series. Von Veit, 1914. ISBN 9783110989854. 14 doi: 10.1007/BF01999507

work page doi:10.1007/bf01999507 1914
[28]

Gurobi Optimizer Refer- ence Manual, 2026

Gurobi Optimization, LLC. Gurobi Optimizer Refer- ence Manual, 2026. URL https://www.gurobi.com. 15

2026