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

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.