Curator's Take
AI Commentary
This article shows that the long‑standing conjecture limiting the success probability of quantum random access codes—often taken as a benchmark for how efficiently classical data can be packed into qubits—is false, because even simple classical RACs with private randomness already beat the proposed square‑root bound when recast as QRACs. By embedding those classical schemes into diagonal quantum encodings and invoking the Ambainis–Nayak–Ta‑Shma–Vazirani achievability theorem, the authors demonstrate violations across the entire interval between the conjectured limit and Nayak’s optimal bound, reshaping our understanding of fundamental compression trade‑offs. The result cautions against assuming universal QRAC limits and suggests that future performance guarantees will need to account for the spectral structure of decoding measurements rather than rely on coarse density‑operator arguments.
— Mark Eatherly
Summary
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.