2026/04/23 by Ruho Kondo, Yuki Sato, Hiroshi Yano +3 · 1 citation
#quant-ph #cs.IT #math.IT
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 2k representatives in \0,1\L, while the worst-case criterion is reduced to a minimax problem over 2k 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 (2k-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.