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

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

REVIEW 2 major objections 3 minor 2 cited by

For the (2^k-1, k) family, an explicit quantum random access code exceeds the optimal classical worst-case success probability.

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

2026-05-21 00:00 UTC pith:GRNOVVE6

load-bearing objection This paper gives a geometric reduction that yields explicit optimal classical RACs for several families plus a concrete quantum advantage for the (2^k-1, k) case. the 2 major comments →

arxiv 2604.21274 v3 pith:GRNOVVE6 submitted 2026-04-23 quant-ph cs.ITmath.IT

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

Ruho Kondo , Yuki Sato , Hiroshi Yano , Yota Maeda , Kosuke Ito , Naoki Yamamoto This is my paper

classification quant-ph cs.ITmath.IT

keywords random access codesquantum random access codesclassical-quantum separationgeometric characterizationbinary linear codesworst-case optimalityaverage-case optimality

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.

This paper introduces a geometric characterization of optimal classical random access codes that map an L-bit string to a k-bit message. The average-case version reduces to choosing 2^k representative strings from {0,1}^L, while the worst-case version reduces to placing 2^k points in the unit hypercube [0,1]^L to minimize a distance-like objective. With this reduction in hand, the authors prove that a classical construction based on binary linear codes is worst-case optimal for the family where L equals 2^k minus one. They then exhibit an explicit quantum version whose worst-case success probability is strictly higher, establishing a separation. The same framework also yields average-optimal classical codes for the (L, L-1) family and quantum codes that meet a previously conjectured performance bound.

Core claim

The paper shows that worst-case optimality for classical (L,k)-RACs is equivalent to selecting 2^k points in [0,1]^L that minimize a distance-like objective. For the parameter family (2^k-1, k), this characterization proves the optimality of a classical construction derived from binary linear codes, while an explicit quantum random access code achieves a strictly higher worst-case success probability and thereby establishes a classical-quantum gap. For the family (L, L-1), the same viewpoint identifies an average-optimal classical construction and recovers explicit quantum constructions that attain a conjectured upper bound.

What carries the argument

Geometric reduction of the worst-case RAC problem to selecting 2^k points in [0,1]^L that minimize a distance-like objective.

Load-bearing premise

The average-case and worst-case success probabilities of random access codes are exactly captured by the stated geometric selections of representatives and points.

What would settle it

Direct numerical computation, for any small fixed k such as k=2, of the worst-case success probability achieved by the paper's explicit QRAC versus the minimum value of the distance-like objective over all choices of 2^k points in [0,1]^L.

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

If this is right

Several (L,k) families now possess provably optimal classical RAC constructions realized by standard binary linear codes.
The (2^k-1, k) family has a classical worst-case optimum that is strictly exceeded by the given explicit QRAC.
The (L, L-1) family admits a classical construction optimal under the average success criterion.
Explicit (L, L-1) QRACs are recovered that attain the value of a previously conjectured tight upper bound.

Where Pith is reading between the lines

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

The same geometric lens may be used to search for classical-quantum gaps in other parameter regimes or for approximate versions of the RAC task.
The reduction to a distance-minimization problem in the hypercube suggests possible links to classical coding theory questions about covering radii or constant-weight codes.
For concrete small values of k the separation can be checked by exhaustive search over the classical side, providing a direct test of the claimed gap.

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

This paper gives a geometric reduction that yields explicit optimal classical RACs for several families plus a concrete quantum advantage for the (2^k-1, k) case.

read the letter

The main takeaway is that this work supplies explicit classical constructions that hit optimality for multiple (L,k) families and proves a strict quantum-classical gap for the infinite family where L equals 2 to the k minus 1. They reduce the average-case problem to picking 2^k representatives inside the hypercube and the worst-case problem to minimizing a distance-like objective over 2^k points in the unit cube. Standard binary linear codes then serve as optimal constructions in many cases, which is a practical result. For the highlighted family they establish the classical optimum and give an explicit QRAC whose worst-case success probability is higher, which is the clearest new separation here. The same geometric lens also recovers explicit QRACs for the (L, L-1) family that reach a previously conjectured bound. This organizes scattered results and hands the community concrete benchmarks rather than just existence proofs. The soft spot is the conjecture required to claim worst-case optimality for the (L, L-1) family; that part remains conditional. The reduction to the continuous minimization also needs the full proof to confirm it is tight with actual deterministic encodings, since a strictly lower continuous value would leave a gap in the classical optimality claim. This is for quantum information researchers who work on random access codes and communication tasks. Readers who want explicit constructions and a verified separation will get direct use from the examples and the gap result. It deserves a serious referee to check the derivations and the conjecture. I would send it to peer review.

Referee Report

2 major / 3 minor

Summary. The manuscript develops a geometric characterization of classical (L,k)-random access codes under both average-case and worst-case success criteria. The average-case problem reduces to selecting 2^k representatives in {0,1}^L; the worst-case problem reduces to selecting 2^k points in [0,1]^L that minimize a distance-like objective. This framework is applied to prove worst-case optimality of classical constructions (realized by binary linear codes) for the family (2^k-1,k), to exhibit an explicit QRAC whose worst-case success probability strictly exceeds the classical optimum (establishing a separation), and to identify optimal classical constructions for (L,L-1) under the average criterion (and under the worst-case criterion assuming a stated conjecture). The same viewpoint recovers explicit (L,L-1)-QRACs attaining a previously conjectured upper bound.

Significance. If the central claims hold, the geometric reduction supplies a clean, unified method for proving optimality of RAC constructions and for certifying classical-quantum separations. The explicit separation for the infinite family (2^k-1,k) and the recovery of QRAC constructions matching a prior upper-bound conjecture are concrete advances. The connection to standard families of binary linear codes for optimal classical RACs is a further strength.

major comments (2)

[Geometric characterization section] The section presenting the geometric characterization of the worst-case problem: the claimed exact equivalence between the max-min success probability over deterministic classical encodings and the continuous minimization of the distance-like objective over [0,1]^L must be shown to be tight; if the relaxation admits values unattainable by any function of the input bits, the optimality proof for the classical construction on (2^k-1,k) and the resulting separation would not be established.
[(L,L-1) optimality subsection] The subsection on the (L,L-1) family: worst-case optimality is asserted only under a stated conjecture; the manuscript should either prove the conjecture, supply supporting numerical evidence for small L, or clearly delineate which results remain conditional.

minor comments (3)

[Geometric characterization section] Clarify the precise definition of the distance-like objective (including any normalization) and verify that the decoder that achieves the minimum is explicitly constructible from the chosen points.
[QRAC construction for (2^k-1,k)] In the explicit QRAC construction for (2^k-1,k), state the worst-case success probability achieved and compare it numerically to the classical optimum for at least one small k (e.g., k=2 or 3).
[Related work and (L,L-1) QRAC] Ensure all references to prior RAC and QRAC literature are complete; the recovery of the (L,L-1)-QRAC should cite the original conjecture it matches.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and constructive comments. We address each major comment below and will update the manuscript to strengthen the presentation.

read point-by-point responses

Referee: [Geometric characterization section] The section presenting the geometric characterization of the worst-case problem: the claimed exact equivalence between the max-min success probability over deterministic classical encodings and the continuous minimization of the distance-like objective over [0,1]^L must be shown to be tight; if the relaxation admits values unattainable by any function of the input bits, the optimality proof for the classical construction on (2^k-1,k) and the resulting separation would not be established.

Authors: We thank the referee for highlighting the need to rigorously establish tightness. The geometric reduction in the manuscript interprets the worst-case objective as a continuous optimization over points in [0,1]^L, where each coordinate is the marginal probability of a 1 in that position under a (possibly randomized) encoding. Because the objective is a convex combination of success probabilities and the feasible set is the convex hull of the deterministic 0-1 encodings, the minimum is attained at a vertex. We will add an explicit lemma in the revised Section 3 proving that any interior point can be replaced by a convex combination of deterministic encodings without increasing the objective value, confirming that the continuous minimum equals the discrete maximum-minimum success probability. This closes the gap and validates both the optimality claim for (2^k-1,k) and the separation. revision: yes
Referee: [(L,L-1) optimality subsection] The subsection on the (L,L-1) family: worst-case optimality is asserted only under a stated conjecture; the manuscript should either prove the conjecture, supply supporting numerical evidence for small L, or clearly delineate which results remain conditional.

Authors: We agree that the worst-case optimality statement for the (L,L-1) family is conditional on the conjecture. In the revision we will (i) explicitly mark all claims that depend on the conjecture, (ii) add a short paragraph delineating the conditional results, and (iii) include numerical verification for L=3 to L=7 obtained by exhaustive enumeration of small encodings, showing that the conjectured construction matches the computed optimum in every checked case. While we do not prove the conjecture here, the added evidence and clearer delineation address the referee's concern without overstating the result. revision: yes

Circularity Check

0 steps flagged

No significant circularity; geometric reductions and code constructions are independent

full rationale

The paper derives its optimality claims from explicit geometric reductions of the average-case RAC to selecting 2^k representatives in {0,1}^L and the worst-case to minimizing a distance-like objective over 2^k points in [0,1]^L, then invokes standard infinite families of binary linear codes for constructions. The classical-quantum separation for (2^k-1,k) follows from proving the classical optimum via this framework and exhibiting an explicit QRAC exceeding it. No step reduces by definition to its inputs, no fitted parameters are relabeled as predictions, and no load-bearing premise rests solely on self-citation; the framework is self-contained against external coding-theory benchmarks. The stated conjecture for (L,L-1) is noted but does not collapse the central derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the validity of the stated geometric reductions from RAC success probabilities to point-selection problems in the hypercube and unit cube; these reductions are presented as equivalences but their justification is not visible in the abstract.

axioms (1)

domain assumption The average-case and worst-case success probabilities of an (L,k)-RAC are exactly captured by the minimum-distance objectives over representatives in {0,1}^L and [0,1]^L respectively.
This equivalence is invoked to reduce the optimality question to a geometric selection problem.

pith-pipeline@v0.9.0 · 5809 in / 1325 out tokens · 62935 ms · 2026-05-21T00:00:41.149988+00:00 · methodology

0 comments

read the original abstract

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 $2^k$ representatives in $\{0,1\}^L$, while the worst-case criterion is reduced to a minimax problem over $2^k$ 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 $(2^k-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.

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 ↗

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 5: maximum average decoding success probability = 1 - min_{S subset {0,1}^L, |S|=2^k} d→_Cham({0,1}^L, S; dH/L)
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 9: worst-case optimality via min directed Hausdorff distance over conv(S) subset [0,1]^L with d∞

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

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
quant-ph 2026-07 accept novelty 6.5

The optimal average success probability of binary (n,n-1) and (n,n-2) QRACs equals exactly 1/2 + 1/2 sqrt(m/n).
Decoder-Consistent Hamiltonians for POVM-Based Quantum Relaxations
quant-ph 2026-06 unverdicted novelty 6.0

Decoder-consistent Hamiltonians are defined via POVM pullback, revealing inconsistencies in standard QRAO for mixed-degree quadratics and yielding new MaxCut approximation guarantees.