Random access codes (RACs) encode a
q-ary input string into fewer
q-ary symbols while allowing any requested input symbol to be recovered with probability above the random-guessing value
1/q. However, it remains unclear what asymptotic guarantees on compression and recovery probability should be required of RACs. We address this question by introducing the notion of asymptotically good RACs and give two polynomial-time constructions. First, an
[n,k,d]q linear code with
d≥2, together with an encoder based on its orthogonal-array property, yields an
(n,n−k)q-RAC with worst-case decoding success probability
pwc=q1+(1−q1)nd−2. These OA-RACs are asymptotically good whenever the underlying linear codes are, and Garcia--Stichtenoth algebraic-geometry codes give a concrete polynomial-time realization. Second, a direct-sum strategy using OA-RACs derived from
q-ary Hamming codes and the trivial
(1,1)q-RAC yields asymptotically good RAC families at every prescribed RAC rate
RRAC=(n−k)/n∈(0,1). Numerical results demonstrate favorable finite-length performance of both constructions.
We show that for any
R,ε>0 and any prime
p≥2, there exists an infinite family of
p-ary quantum low-density parity-check (QLDPC) codes, rate
R, checks of weight
Oε(1), and normalized distance at least
δGV(p,R)−ε. Here,
δGV(p,R) denotes the quantum Gilbert-Varshamov (GV) bound for
p-ary stabilizer codes.
In fact, we construct an ensemble of such QLDPC codes, such that a random code from this ensemble is close to the GV bound with high probability. Moreover, this ensemble matches the performance of random stabilizer codes on several quantum channels. Specifically, it approaches the quantum capacity of the erasure channel and the hashing bound for memoryless Pauli channels, including the depolarizing channel.
A significant challenge in working with QLDPC codes is that they are necessarily \emph{degenerate}, i.e., contain many low-weight stabilizers. A key contribution of our work is a construction of QLDPC codes with quantitative control on their degeneracy. These codes are obtained by combining known constructions of asymptotically good QLDPC codes with the expander-based distance amplification procedure of Alon, Edmonds, and Luby [FOCS'95].
Our random ensemble is constructed by starting with these low-degeneracy QLDPC codes near the quantum Singleton bound and concatenating each coordinate with a random inner code. This can be viewed as a quantum analogue of Thommesen's construction, and as an LDPC version of a result of Ouyang, with an appropriately designed outer code.