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
2026-07-11 • Information Theory
Information Theory
AI summaryⓘ
The authors study a way to compress a long string of bits into fewer quantum bits that still lets you guess any bit from the original string with some success. They focus on codes that use just one or two fewer qubits than the original number of bits. Prior work suggested a limit on how well these codes can perform, which some specific constructions were known to reach. The authors prove that this limit is indeed the best possible for these cases, confirming that those constructions are strictly optimal. Their proof uses advanced quantum measurement techniques and mathematical constraints on quantum channels.
Quantum Random Access CodeQubitsQuantum CompressionPretty Good MeasurementPositive-Semidefinite ConstraintsQuantum ChannelOptimal Success ProbabilityLocal to Global ReconstructionQuantum Information Theory
Authors
Shuo Tan, Syed A. Jafar
Abstract
A binary $(n,m)$ quantum random access code (QRAC) compresses an $n$-bit classical string into an $m$-qubit quantum state, from which a decoder attempts to recover a randomly selected target bit. Of particular interest is the optimal average probability of success, $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}$, which is numerically conjectured to satisfy the bound $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\leq \frac{1}{2}+\frac{1}{2}\sqrt{\frac{m}{n}}$. Recent constructions of $(n,n-1)$ QRACs by Suzuki and $(n,n-2)$ QRACs by Akibue et al. meet this bound exactly, raising the question of their strict optimality. In this work, we settle this question by proving the conjectured upper bound for $m\in\{n-1,n-2\}$, thereby precisely determining $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-1}$ and $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-2}$. The proof utilizes a translation recently studied by Lin and de Wolf from local to global reconstruction via pretty good measurement, along with dimensional and positive-semidefinite constraints on an induced channel.