Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.38429

Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes

Ruho Kondo, Yota Maeda

Published Oct 28, 2026• 0 citations
arXivHTMLPDF

Abstract

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\ge2$, together with an encoder based on its orthogonal-array property, yields an $(n,n-k)_q$-RAC with worst-case decoding success probability \[ p_{\rm wc}=\frac{1}{q}+\left(1-\frac{1}{q}\right)\frac{d-2}{n}. \] 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 $R_{\rm RAC}=(n-k)/n\in(0,1)$. Numerical results demonstrate favorable finite-length performance of both constructions.

DOI
10.48550/arxiv.2610.38429

Related papers

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

Ruho Kondo, Yuki Sato, Hiroshi Yano +3 more

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.

quant-pharXiv:2604.21274•Apr 24, 2026•4 citations

Biased random access codes

Gabriel Pereira Alves, N. Gigena, Jędrzej Kaniewski

A random access code (RAC) is a communication task in which the sender encodes a random message into a shorter one to be decoded by the receiver so that a randomly chosen character of the original message is recovered with some probability. Both the message and the character to be recovered are assumed to be uniformly distributed. In this paper, we extend this protocol by allowing more general distributions of these inputs, which alters the encoding and decoding strategies optimizing the protocol performance, with either classical or quantum resources. We approach the problem of optimizing the performance of these biased RACs with both numerical and analytical tools. On the numerical front, we present algorithms that allow a numerical evaluation of the optimal performance over both classical and quantum strategies and provide a Python package designed to implement them, called RAC-tools. We then use this numerical tool to investigate single-parameter families of biased RACs in the ${n}^{2}\ensuremath{\mapsto}1$ and ${2}^{d}\ensuremath{\mapsto}1$ scenarios. For RACs in the ${n}^{2}\ensuremath{\mapsto}1$ scenario, we derive a general upper bound for the cases in which the inputs are not correlated, which coincides with the quantum value for $n=2$ and in some cases for $n=3$. Moreover, it is shown that attaining this upper bound self-tests pairs or triples of rank-1 projective measurements, respectively. An analogous upper bound is derived for the value of RACs in the ${2}^{d}\ensuremath{\mapsto}1$ scenario, which is shown to be always attainable using mutually unbiased measurements if the distribution of input strings is unbiased.

arXiv:2302.08494•Physical Review A•Oct 13, 2023•7 citations

Improved classical and quantum random access codes

Ola Liabøtrø

A (quantum) random access code ((Q)RAC) is a scheme that encodes $n$ bits into $m$ (qu)bits such that any of the $n$ bits can be recovered with a worst case probability $p>\frac{1}{2}$. We generalize (Q)RACs to a scheme encoding $n$ $d$-levels into $m$ (quantum) $d$-levels such that any $d$-level can be recovered with the probability for every wrong outcome value being less than $\frac{1}{d}$. We construct explicit solutions for all $n\ensuremath{\le}\frac{{d}^{2m}\ensuremath{-}1}{d\ensuremath{-}1}$. For $d=2$, the constructions coincide with those previously known. We show that the (Q)RACs are $d$-parity oblivious, generalizing ordinary parity obliviousness. We further investigate optimization of the success probabilities. For $d=2$, we use the measure operators of the previously best-known solutions, but improve the encoding states to give a higher success probability. We conjecture that for maximal $(n={4}^{m}\ensuremath{-}1,m,p)$ QRACs, $p=\frac{1}{2}{1+{[{(\sqrt{3}+1)}^{m}\ensuremath{-}1]}^{\ensuremath{-}1}}$ is possible, and show that it is an upper bound for the measure operators that we use. We then compare $(n,m,{p}_{q})$ QRACs with classical $(n,2m,{p}_{c})$ RACs. We can always find ${p}_{q}\ensuremath{\ge}{p}_{c}$, but the classical code gives information about every input bit simultaneously, while the QRAC only gives information about a subset. For several different $(n,2,p)$ QRACs, we see the same trade-off, as the best $p$ values are obtained when the number of bits that can be obtained simultaneously is as small as possible. The trade-off is connected to parity obliviousness, since high certainty information about several bits can be used to calculate probabilities for parities of subsets.

arXiv:1607.02667•Physical Review A•May 8, 2017•22 citations

Erasure List-Decodable Codes From Random and Algebraic Geometry Codes

Yang Ding, Lingfei Jin, Chaoping Xing

Erasure list decoding was introduced to correct a larger number of erasures by outputting a list of possible candidates. In this paper, we consider both random linear codes and algebraic geometry codes for list decoding from erasures. The contributions of this paper are twofold. First, for arbitrary 00 (R and ϵ are independent), we show that with high probability a q-ary random linear code of rate R is an erasure list-decodable code with constant list size qO(1/ϵ)that can correct a fraction 1 - R - ϵ of erasures, i.e., a random linear code achieves the information-theoretic optimal tradeoff between information rate and fraction of erasures. Second, we show that algebraic geometry codes are good erasure list-decodable codes. Precisely speaking, a q-ary algebraic geometry code of rate R from the Garcia-Stichtenoth tower can correct 1 - R - (1/√q - 1) + (1/q) - ϵ fraction of erasures with list size O(1/ϵ). This improves the Johnson bound for erasures applied to algebraic geometry codes. Furthermore, list decoding of these algebraic geometry codes can be implemented in polynomial time. Note that the code alphabet size q in this paper is constant and independent of ϵ.

arXiv:1401.2716•IEEE Transactions on Information Theory•Mar 31, 2014•5 citations

Quantum Random Access Codes encoding every possible number of bits into m qubits

Ola Liabøtrø

A (Quantum) Random Access Code ((Q)RAC) is a scheme that encodes $n$ bits into $m$ (qu)bits such that any of the $n$ bits can be recovered with a worst case probability $p>\frac{1}{2}$. Such a code is denoted by the triple $(n,m,p)$. It is known that $n<4^m$ for all QRACs and $n<2^m$ for classical RACs. These bounds are also known to be tight, as explicit constructions exist for $n=4^m-1$ and $n=2^m-1$ for quantum and classical codes respectively. We generalize (Q)RACs to a scheme encoding $n$ $d$-levels into $m$ (qu)-$d$-levels such that any $d$-level can be recovered with the probability for every wrong outcome value being less than $\frac{1}{d}$. We construct explicit solutions for all $n\leq \frac{d^{2m}-1}{d-1}$. For $d=2$, the constructions coincide with those previously known. We show that the (Q)RACs are $d$-parity-oblivious, generalizing ordinary parity-obliviousness. We further investigate optimization of the success probabilities. For $d=2$, we use the measure operators of the previously best known solutions, but improve the encoding states to give a higher success probability. We conjecture that for maximal $(n=4^m-1,m,p)$ QRACs, $p=\frac{1+\frac{1}{(\sqrt{3}+1)^m-1}}{2}$ is possible and show that it is an upper bound for the measure operators that we use. When we compare $(n,m,p_q)$ QRACs with classical $(n,2m,p_c)$ RACs, we can always find $p_q\geq p_c$, but the classical code gives information about every input bit simultaneously, while the QRAC only gives information about a subset. For several different $(n,2,p)$ QRACs, we see the same trade-off, as the best $p$ values are obtained when the number of bits that can be obtained simultaneously is as small as possible. The trade-off is connected to parity-obliviousness, since high certainty information about several bits can be used to calculate probabilities for parities of subsets.

•Jul 9, 2016•0 citations

Optimal Average Success Probabilities of Binary $(n,n-1)$ and $(n,n-2)$ Quantum Random Access Codes

Shuo Tan, Syed A. Jafar

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 was 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.

quant-pharXiv:2607.10414•Jul 14, 2026•3 citations
Random access codes (RACs) encode a qqq-ary input string into fewer qqq-ary symbols while allowing any requested input symbol to be recovered with probability above the random-guessing value 1/q1/q1/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[n,k,d]_q[n,k,d]q​ linear code with d≥2d\ge2d≥2, together with an encoder based on its orthogonal-array property, yields an (n,n−k)q(n,n-k)_q(n,n−k)q​-RAC with worst-case decoding success probability [ p_{\rm wc}=\frac{1}{q}+\left(1-\frac{1}{q}\right)\frac{d-2}{n}. ] 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 qqq-ary Hamming codes and the trivial (1,1)q(1,1)_q(1,1)q​-RAC yields asymptotically good RAC families at every prescribed RAC rate RRAC=(n−k)/n∈(0,1)R_{\rm RAC}=(n-k)/n\in(0,1)RRAC​=(n−k)/n∈(0,1). Numerical results demonstrate favorable finite-length performance of both constructions.
A random access code (RAC) encodes an LLL-bit string into a kkk-bit message, L>kL>kL>k, so that any requested bit can be recovered with high probability; a quantum RAC (QRAC) uses kkk qubits instead. We give a geometric characterization of optimal classical (L,k)(L,k)(L,k)-RACs under average and worst-case decoding criteria. The average criterion is reduced to choosing 2k2^k2k representatives in {0,1}L\{0,1\}^L{0,1}L, while the worst-case criterion is reduced to a minimax problem over 2k2^k2k points in [0,1]L[0,1]^L[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>1L>1L>1, we construct a (L,1)(L,1)(L,1)-QRAC whose average decoding success probability strictly exceeds the optimal classical value. Second, for the family (2k−1,k)(2^k-1,k)(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)(L,L-1)(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)(L,L-1)(L,L−1)-QRACs attaining a previously conjectured upper-bound value.
A random access code (RAC) is a communication task in which the sender encodes a random message into a shorter one to be decoded by the receiver so that a randomly chosen character of the original message is recovered with some probability. Both the message and the character to be recovered are assumed to be uniformly distributed. In this paper, we extend this protocol by allowing more general distributions of these inputs, which alters the encoding and decoding strategies optimizing the protocol performance, with either classical or quantum resources. We approach the problem of optimizing the performance of these biased RACs with both numerical and analytical tools. On the numerical front, we present algorithms that allow a numerical evaluation of the optimal performance over both classical and quantum strategies and provide a Python package designed to implement them, called RAC-tools. We then use this numerical tool to investigate single-parameter families of biased RACs in the ${n}^{2}\ensuremath{\mapsto}1$ and ${2}^{d}\ensuremath{\mapsto}1$ scenarios. For RACs in the ${n}^{2}\ensuremath{\mapsto}1$ scenario, we derive a general upper bound for the cases in which the inputs are not correlated, which coincides with the quantum value for n=2n=2n=2 and in some cases for n=3n=3n=3. Moreover, it is shown that attaining this upper bound self-tests pairs or triples of rank-1 projective measurements, respectively. An analogous upper bound is derived for the value of RACs in the ${2}^{d}\ensuremath{\mapsto}1$ scenario, which is shown to be always attainable using mutually unbiased measurements if the distribution of input strings is unbiased.
A (quantum) random access code ((Q)RAC) is a scheme that encodes nnn bits into mmm (qu)bits such that any of the nnn bits can be recovered with a worst case probability p>12p>\frac{1}{2}p>21​. We generalize (Q)RACs to a scheme encoding nnn ddd-levels into mmm (quantum) ddd-levels such that any ddd-level can be recovered with the probability for every wrong outcome value being less than 1d\frac{1}{d}d1​. We construct explicit solutions for all $n\ensuremath{\le}\frac{{d}^{2m}\ensuremath{-}1}{d\ensuremath{-}1}$. For d=2d=2d=2, the constructions coincide with those previously known. We show that the (Q)RACs are ddd-parity oblivious, generalizing ordinary parity obliviousness. We further investigate optimization of the success probabilities. For d=2d=2d=2, we use the measure operators of the previously best-known solutions, but improve the encoding states to give a higher success probability. We conjecture that for maximal $(n={4}^{m}\ensuremath{-}1,m,p)$ QRACs, $p=\frac{1}{2}{1+{[{(\sqrt{3}+1)}^{m}\ensuremath{-}1]}^{\ensuremath{-}1}}$ is possible, and show that it is an upper bound for the measure operators that we use. We then compare (n,m,pq)(n,m,{p}_{q})(n,m,pq​) QRACs with classical (n,2m,pc)(n,2m,{p}_{c})(n,2m,pc​) RACs. We can always find ${p}_{q}\ensuremath{\ge}{p}_{c}$, but the classical code gives information about every input bit simultaneously, while the QRAC only gives information about a subset. For several different (n,2,p)(n,2,p)(n,2,p) QRACs, we see the same trade-off, as the best ppp values are obtained when the number of bits that can be obtained simultaneously is as small as possible. The trade-off is connected to parity obliviousness, since high certainty information about several bits can be used to calculate probabilities for parities of subsets.
Erasure list decoding was introduced to correct a larger number of erasures by outputting a list of possible candidates. In this paper, we consider both random linear codes and algebraic geometry codes for list decoding from erasures. The contributions of this paper are twofold. First, for arbitrary 00 (R and ϵ are independent), we show that with high probability a q-ary random linear code of rate R is an erasure list-decodable code with constant list size qO(1/ϵ)that can correct a fraction 1 - R - ϵ of erasures, i.e., a random linear code achieves the information-theoretic optimal tradeoff between information rate and fraction of erasures. Second, we show that algebraic geometry codes are good erasure list-decodable codes. Precisely speaking, a q-ary algebraic geometry code of rate R from the Garcia-Stichtenoth tower can correct 1 - R - (1/√q - 1) + (1/q) - ϵ fraction of erasures with list size O(1/ϵ). This improves the Johnson bound for erasures applied to algebraic geometry codes. Furthermore, list decoding of these algebraic geometry codes can be implemented in polynomial time. Note that the code alphabet size q in this paper is constant and independent of ϵ.
A (Quantum) Random Access Code ((Q)RAC) is a scheme that encodes nnn bits into mmm (qu)bits such that any of the nnn bits can be recovered with a worst case probability p>12p>\frac{1}{2}p>21​. Such a code is denoted by the triple (n,m,p)(n,m,p)(n,m,p). It is known that n<4mn<4^mn<4m for all QRACs and n<2mn<2^mn<2m for classical RACs. These bounds are also known to be tight, as explicit constructions exist for n=4m−1n=4^m-1n=4m−1 and n=2m−1n=2^m-1n=2m−1 for quantum and classical codes respectively. We generalize (Q)RACs to a scheme encoding nnn ddd-levels into mmm (qu)-ddd-levels such that any ddd-level can be recovered with the probability for every wrong outcome value being less than 1d\frac{1}{d}d1​. We construct explicit solutions for all n≤d2m−1d−1n\leq \frac{d^{2m}-1}{d-1}n≤d−1d2m−1​. For d=2d=2d=2, the constructions coincide with those previously known. We show that the (Q)RACs are ddd-parity-oblivious, generalizing ordinary parity-obliviousness. We further investigate optimization of the success probabilities. For d=2d=2d=2, we use the measure operators of the previously best known solutions, but improve the encoding states to give a higher success probability. We conjecture that for maximal (n=4m−1,m,p)(n=4^m-1,m,p)(n=4m−1,m,p) QRACs, p=1+1(3+1)m−12p=\frac{1+\frac{1}{(\sqrt{3}+1)^m-1}}{2}p=21+(3​+1)m−11​​ is possible and show that it is an upper bound for the measure operators that we use. When we compare (n,m,pq)(n,m,p_q)(n,m,pq​) QRACs with classical (n,2m,pc)(n,2m,p_c)(n,2m,pc​) RACs, we can always find pq≥pcp_q\geq p_cpq​≥pc​, but the classical code gives information about every input bit simultaneously, while the QRAC only gives information about a subset. For several different (n,2,p)(n,2,p)(n,2,p) QRACs, we see the same trade-off, as the best ppp values are obtained when the number of bits that can be obtained simultaneously is as small as possible. The trade-off is connected to parity-obliviousness, since high certainty information about several bits can be used to calculate probabilities for parities of subsets.
Optimal Average Success Probabilities of Binary (n,n−1)(n,n-1)(n,n−1) and (n,n−2)(n,n-2)(n,n−2) Quantum Random Access Codes
A binary (n,m)(n,m)(n,m) quantum random access code (QRAC) compresses an nnn-bit classical string into an mmm-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, Pn,mQ,avg,optP^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}Pn,mQ,avg,opt​, which was numerically conjectured to satisfy the bound Pn,mQ,avg,opt≤12+12mnP^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\leq \frac{1}{2}+\frac{1}{2}\sqrt{\frac{m}{n}}Pn,mQ,avg,opt​≤21​+21​nm​​. Recent constructions of (n,n−1)(n,n-1)(n,n−1) QRACs by Suzuki and (n,n−2)(n,n-2)(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∈{n−1,n−2}m\in\{n-1,n-2\}m∈{n−1,n−2}, thereby precisely determining Pn,n−1Q,avg,optP^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-1}Pn,n−1Q,avg,opt​ and Pn,n−2Q,avg,optP^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-2}Pn,n−2Q,avg,opt​. 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.