WorksComputer Science
Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes
Abstract
Random access codes (RACs) encode a -ary input string into fewer -ary symbols while allowing any requested input symbol to be recovered with probability above the random-guessing value . 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 linear code with , together with an encoder based on its orthogonal-array property, yields an -RAC with worst-case decoding success probability 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 -ary Hamming codes and the trivial -RAC yields asymptotically good RAC families at every prescribed RAC rate . Numerical results demonstrate favorable finite-length performance of both constructions.
Introduction
A random access code (RAC) compresses an input string into a shorter message while allowing any designated input symbol to be decoded with probability strictly above random guessing. For binary classical RACs, Ambainis et al. [1] established an asymptotically tight tradeoff between the message rate and the decoding success probability, and the corresponding entropy converse extends to quantum messages [2]. Their achievability result, however, is non-constructive, relying on existence arguments for suitable codes and a probabilistic encoder. This motivates the study of explicit RAC constructions, particularly those admitting efficient encoding and decoding algorithms for practical implementations. Explicit classical and quantum RACs have been investigated for various finite parameters and particular parameter families, with results on their constructions, decoding performance, and optimality [3, 4, 5, 6, 7, 8, 9, 10, 11]. Recent work has also provided a geometric framework for explicit classical RAC constructions with general finite parameters [10], but no polynomial-time algorithm is known for the general construction. Although direct sums of fixed-size RACs trivially yield polynomial-time constructible families with nonvanishing compression and worst-case decoding advantage, developing efficient explicit constructions that accommodate general parameter choices while maintaining these properties remains a challenge.
In this work, we introduce asymptotically good RACs, whose compression fractions and worst-case decoding advantages over random guessing both remain bounded away from zero. By the Ambainis–Nayak–Ta-Shma–Vazirani (ANTV) converse, these conditions also keep the message rate bounded away from zero and the worst-case decoding success probability bounded away from one.
We give two approaches to constructing such families. First, building on the geometric connection between RACs and classical codes [10], we introduce an OA encoder based on the orthogonal-array property of linear codes. Using dual codes as RAC codebooks, we show that any asymptotically good family of linear codes yields an asymptotically good family of -. When the underlying codes and required operations are efficient, the resulting - are also efficient. As a concrete polynomial-time realization, we use concatenated codes with Garcia–Stichtenoth algebraic geometry outer codes [12].
Second, we consider a direct-sum strategy that constructs large RACs from smaller ones. Using - derived from -ary Hamming codes together with the trivial -RAC, we show that this strategy constructs asymptotically good RAC families at any prescribed rate.
Finally, we numerically examine the finite-length performance of both constructions. OA-RACs substantially outperform the Improved RAC construction [3] over much of the examined range, although they do not generally attain the optimum. For the direct-sum strategy, incorporating OA-RACs derived from additional linear-code families, including algebraic geometry codes, further improves the worst-case decoding success probability over a wide range of RAC rates.
Preliminaries
Our construction builds on the connection between RACs and linear codes established in [10]. We therefore first review RACs and the required facts on linear codes. Since our explicit construction of asymptotically good RACs uses asymptotically good concatenated codes with algebraic geometry (AG) outer codes, we also review the necessary background on AG codes and concatenated codes. Throughout the paper, for a positive integer , we write .
Random Access Codes
An RAC with input length , message length , and alphabet is called an -RAC. The encoder is a conditional distribution on messages given an input string . For a requested coordinate , the decoder is a conditional distribution on the reconstructed symbol given the message. The worst-case decoding success probability is
The random-guessing probability is .
For , the maximum worst-case decoding success probability admits the geometric formulation [10]
where is the Chebyshev distance. Thus, RAC construction can be viewed as a codebook-design problem over all subsets of cardinality . Importantly, this search space contains the family of all -dimensional binary linear codes , each of which also has exactly elements. The present work exploits this inclusion by restricting to linear codebooks and then importing structural results from classical coding theory.
Linear Codes
For a prime power , a subspace with is called an linear code. A matrix satisfying
is called a generator matrix of . The minimum distance is
An code with minimum distance is denoted by . The dual code is
and . We write when the underlying code is clear. The rate and relative minimum distance are
Using these notations, asymptotically good linear codes are defined as follows:
Definition 1 (Asymptotically good linear codes). A sequence of -ary linear codes with is called asymptotically good if
Algebraic Geometry Codes
Let be a nonsingular projective irreducible curve of genus over . For a divisor , define the Riemann–Roch space
Let be distinct -rational points disjoint from the support of , and set . The corresponding evaluation code is
If , the evaluation map is injective and
Consequently,
Thus, good asymptotic performance requires a large ratio of rational points to genus, .
Let denote the maximum possible number of -rational points on a genus- curve over . The Ihara constant is
The Drinfeld–Vlăduț bound gives , and equality is attained for square by GS towers [12]. Let with a prime power. Using the level index adopted here, one may select
rational evaluation points, while the genus is
For a one-point divisor with , the AG code satisfies
For a desired dimension , choosing yields a code of dimension at least ; a -dimensional subcode then preserves the distance guarantee
The method of Shum et al. [13] constructs generator matrices of these GS-tower AG codes in field operations for fixed . Moreover,
so the corresponding asymptotic distance guarantee is the Tsfasman–Vlăduț–Zink (TVZ) bound [14]
A Reed–Solomon (RS) code over is defined by evaluating polynomials of degree less than at distinct elements :
For $1 \le k \le n \le Q$, this yields an linear code. In particular, an RS code is an AG code on the projective line , which has genus zero, with the divisor .
Concatenated Codes
Let the outer and inner linear codes have parameters and , respectively. To map one outer symbol to one inner information vector, we impose
and fix an -linear vector-space isomorphism . The concatenated code then has parameters
Let and be the parameters and genus of level- GS outer code. For a fixed inner code concatenated with the level- GS outer code, the relative minimum distance satisfies
where is the relative minimum distance of the concatenated code with level- GS outer code, and , . Hence, if ,
In particular, the outer length can grow by increasing the GS tower level while the inner code and remain fixed. For an RS outer code,
However, an ordinary RS code satisfies . Thus, at fixed base alphabet , increasing the RS outer length eventually forces the inner dimension to grow as well. In the explicit finite-length construction considered in this paper, the resulting certified inner-code relative-distance guarantee decreases with this growth, and consequently the certified relative minimum-distance guarantee of the RS concatenated construction approaches zero for very large target lengths. For this reason, RS concatenation is used below as a finite-length baseline rather than as the mechanism for our asymptotically good RAC family. The GS tower avoids this obstruction at the level of the guarantee because can be achieved with a fixed inner code and fixed .
Construction of Asymptotically Good RACs
Linear RACs
Even after restricting (2) to , an optimal RAC need not in general be realized by a linear code [10]. Nevertheless, the family of linear codebooks is a particularly useful structured subclass because it exposes the full machinery of linear coding theory. Moreover, in the binary worst-case formulation, restricting to is equivalent to restricting the decoder to be deterministic [10]. Thus, after further restricting the codebook to a linear code, the remaining design choices are the linear code itself and the stochastic encoder used to select a codeword. The transmitted message is simply an index of the selected codeword. The resulting protocol has the form
To decode coordinate , the receiver outputs .
The discussion above is specific to the binary case. We extend this framework to the -ary setting and define a linear RAC as follows.
Definition 2 (Linear RAC). Fix a -dimensional -ary linear code and a one-to-one indexing map . Given , the encoder stochastically selects a codeword and sends its index . For a requested coordinate , the decoder outputs . We call this protocol a linear RAC.
This restriction is the key bridge used in the rest of the paper: properties of linear codes can now be translated directly into guarantees for RACs.
OA Encoder
An orthogonal array is an array over an alphabet of size such that, after selecting any columns, every possible -tuple appears exactly times. The integer is called the strength. If the codewords of an linear code are arranged as the rows of an array, Delsarte’s theorem [15] gives
Using this property of linear codes, we construct the following RAC encoder:
Theorem 3 (OA encoder). Let be a linear code with dual distance . Choose any integer satisfying . Given , choose a subset of size uniformly at random, then choose uniformly from
and transmit the index of . For every and every , the decoding success probability of -RAC is exactly
In particular, choosing gives
Proof. By (26), is an orthogonal array of strength at least . Because , every pattern on occurs equally often, so the conditional set is nonempty and uniform sampling is well defined. If , decoding is correct with probability 1. If , then , so the projection onto is uniform; conditioned on , the symbol is uniform on and is correct with probability . Averaging over gives (28).
We refer to an RAC incorporating this OA encoder as an -. The theorem also allows a certified lower bound and to be used in place of the exact dual distance as follows:
Corollary 4 (Finite-length transfer from linear codes to RACs). Let be a linear code, and suppose that a lower bound with is known. Take as the RAC codebook and apply the OA encoder of Theorem 3 with . Then the resulting -RAC has worst-case decoding success probability
Proof. Since , and . Hence satisfies the condition of Theorem 3, and the claim follows directly from (28).
This observation is important for polynomial-time construction because exact minimum-distance computation is intractable for general linear codes.
Beyond this computational advantage, the OA encoder also recovers RAC constructions that are optimal, either unconditionally or under the conjecture of [10], for certain parameter families.
Corollary 5 (Known optimal binary RAC families). For and , the OA encoder realizes both the worst-case-optimal -RAC and the conditionally worst-case-optimal -RAC identified in [10], where the latter optimality is conditional on the Conjecture 20 stated there.
Proof. The worst-case-optimal -RAC of [10] is realized by the binary simplex code . Its dual is the binary Hamming code, whose minimum distance is 3. Thus , and the OA encoder uses . With , Theorem 3 gives
which is exactly the worst-case optimum reported in [10].
For the family, the relevant codebook is the binary single-parity-check code . Its dual is the binary repetition code, whose minimum distance is . Hence , so the OA encoder uses and achieves
This is the success probability of the conditionally worst-case-optimal -RAC in [10].
A Concrete Example of the OA Encoder
As a concrete binary example, consider a linear code whose dual code is a code with generator matrix
Equivalently, is a parity-check matrix of the primal code . Its RREF is already
Using zero-based coordinate indices, the pivot columns are . After permuting columns so that the pivot columns appear first,
where
Collect the pivot coordinates of a codeword into
and the remaining free coordinates into
Then every codeword of is obtained by choosing and setting
The dual code generated by has minimum distance 5, so and Theorem 3 permits . Choose
The codeword coordinates 0, 3, and 4 must equal , , and , respectively, which gives
Simply fixing and sampling the remaining variables independently does not in general satisfy the two other constraints. Instead, we sample uniformly from the affine solution space.
For concreteness, take
After fixing , define
and
The remaining constraints are
The augmented matrix
is already in RREF. The pivot columns among the variables are and the free columns are . Writing and , one samples uniformly and then determines uniquely. For example, take
Then
so and
Together with , this gives
where over . The final codeword is
Because every assignment of the free variables determines exactly one solution, uniform sampling of the free variables gives a uniform sample from .
Asymptotically good RACs
For linear codes, asymptotic goodness requires both the code rate and the relative minimum distance to remain nonvanishing as the blocklength grows. For RACs, we instead consider the compression fraction and the decoding advantage . This motivates the following definition.
Definition 6 (Asymptotically good RACs). A sequence of -ary -RACs with is called asymptotically good if
and
By the ANTV converse, these two conditions also imply that the RAC rate is bounded away from zero and that the decoding success probability is bounded away from one, respectively.
For example, consider the known infinite family of -RACs [10]. Its compression fraction satisfies , whereas its worst-case decoding success probability is . Hence, , so this family is not asymptotically good. As another example, consider the infinite family of -RACs [10]. Its compression fraction is , while . Thus, this family is also not asymptotically good, because its compression fraction vanishes. These examples illustrate the two defining requirements separately. Moreover, the ANTV converse implies that a nonvanishing decoding advantage automatically keeps the RAC rate bounded away from zero, while a nonvanishing compression fraction automatically keeps the decoding success probability bounded away from one.
Definition 6 does not prescribe the asymptotic RAC rate. To distinguish asymptotically good families by their limiting rate, we introduce the following refinement.
Definition 7 (Asymptotically good RACs at rate ). Let . An asymptotically good sequence of -RACs is said to be asymptotically good at rate if
We next extend this notion from a single prescribed rate to all rates in by defining the following property of a class of RACs.
Definition 8 (Rate-universal asymptotic goodness). A class of -ary RACs is called rate-universally asymptotically good if, for every , contains a sequence of RACs that is asymptotically good at rate .
The next theorem states the general transfer principle from coding theory to RACs.
Theorem 9 (Asymptotically good codes induce asymptotically good RACs). Let be an asymptotically good family of -ary linear codes
For each , take the RAC codebook to be
and use the OA encoder with for all sufficiently large . Then the resulting -RAC family is asymptotically good.
Proof. Because is asymptotically good, . The Singleton bound gives , and therefore . Moreover, since is asymptotically good, . Thus the RAC message rate is bounded away from both zero and one. Moreover, . By Theorem 3, . Taking the lower limit gives . Hence the RAC family is asymptotically good.
Code Design
Theorem 9 reduces the construction of asymptotically good RACs to that of polynomial-time constructible asymptotically good linear-code families with efficiently available distance certificates. Thus, any explicit code family satisfying these requirements, such as Justesen-type codes, can in principle be used in our construction. Random linear codes, for example, attain the GV bound with high probability, but computing the exact minimum distance of a general binary linear code is NP-hard [16]. A randomly generated code therefore does not by itself provide the deterministic, efficiently available distance certificate required here.
In this work, we use concatenated codes with GS-tower AG codes as outer codes. This construction allows the inner code and the outer alphabet to remain fixed as the blocklength grows, while providing a convenient certified distance bound for finite-length analysis. We assume that the inner code is selected from a database of known linear codes for implementability.
For a GS-tower outer code, the concatenation condition must be compatible with the requirement that be a square. Thus either the inner dimension is even or the base alphabet is itself a square. For binary RACs, , so the inner dimension must be even. We assume that the inner code is selected from a database of known linear codes. The GS construction provides an explicit asymptotically good code family to which Theorem 9 can be applied.
Corollary 10 (GS-tower construction of asymptotically good RACs). Let be a fixed inner code with , and suppose that is a square. Fix . For each GS-tower level , choose an outer AG code of dimension satisfying . Then the resulting concatenated codes form an asymptotically good family of -ary linear codes. Consequently, the dual codebooks , together with the OA encoder, form an asymptotically good RACs.
Proof. The GS tower yields an asymptotically good family of AG codes over [12]. Since the inner code is fixed and has positive rate and relative minimum distance, the standard concatenated-code rate and distance bounds imply that is asymptotically good. The claim then follows from Theorem 9.
Throughout this paper, we refer to RACs constructed using GS-tower AG concatenated codes as base codes and equipped with the OA encoder as -RACs.
By contrast, the RS construction used in this paper is primarily a finite-length benchmark. Its certified distance lower bound is often strong at moderate lengths, but the RS length constraint forces the inner dimension to grow when the target concatenated length becomes very large. Under the explicit inner-code selection procedure used
Algorithm 1 Adjustment of code length and dimension by shortening and puncturing. Shortening applies shortening operations at coordinates that reduce the dimension by one, Puncturing applies dimension-preserving punctures, and ZeroPadding appends zero coordinates.
Input: Output: Modified generator matrix 1: 2: 3: if then 4: 5: else 6: 7: end if 8: return
here, this causes the certified relative minimum-distance guarantee to decrease toward zero. The numerical results in Section IV illustrate this behavior directly. We refer to these RACs as -RACs.
AG and RS concatenated codes constrain the achievable length and dimension. To obtain a desired linear code, we combine shortening and puncturing while preserving the certified minimum-distance lower bound as much as possible. Puncturing deletes one coordinate. If a nonpivot column of a systematic generator matrix is punctured, an code becomes an code without reducing dimension. Shortening at a coordinate on which the code is not identically zero yields an code. Thus, we first shorten until the desired dimension is reached, choosing coordinates that reduce the dimension by one at each step. If the resulting length is larger than desired, we puncture nonpivot coordinates; if it is smaller, we append zero coordinates. If an code is transformed into an code in this way, then
Asymptotic Performance of the AG/OA-RACs with Fixed Inner-Code Database
As discussed above, AG/OA-RACs are asymptotically good, whereas RS/OA-RACs are not when the inner codes are restricted to those in the fixed database. In what follows, we describe the asymptotic performance of the AG/OA-RACs with finite-length inner codes from the viewpoint of practical implementability.
Let the inner code be with parameters , , , and let the outer code be with parameters , , , and let and denote the -RAC rate and the rate of the concatenated base code, respectively.
Since the minimum distance of a concatenated code is at least , we use this value as in (30) to evaluate the worst-case decoding success probability. Accordingly, for fixed inner-code parameters , the asymptotic worst-case decoding success probability of the AG/OA-RAC is given by
Since the inner code is designed to be retrieved from a database, is finite. Thus, the maximum achievable minimum distance of the inner code for specified , , and satisfies , where denotes the finite-length GV bound. On the other hand, one advantage of AG concatenated codes is that their asymptotic performance can be evaluated even when the inner code is fixed. Hence, the outer-code length can be taken to infinity, i.e., . Consequently, the maximum achievable minimum distance of the outer code for specified , , and satisfies , where denotes the TVZ bound in (18). Note that must be even whenever is not a square, since must be a square. An upper bound on the worst-case decoding success probability can also be obtained by applying the MRRW bound [17] to the relative minimum distance of the concatenated code.
We set and . Then, the numerical calculation is performed as a function of and plotted against . Figure 1 shows the obtained bounds of worst-case decoding success probability of AG/OA-RAC, together with the ANTV upper bound, where denotes the inverse of the -ary entropy function on . This figure shows that, although the AG/OA-RAC does not attain the ANTV bound, its worst-case decoding success probability exceeds the random-guessing probability. Note that these asymptotic bounds allow the concatenated-code length to vary freely. If the concatenated-code length is instead fixed
Figure 1. Theoretical performance envelope for the asymptotic worst-case decoding success probability of AG/OA-RACs, derived using the finite-length linear GV lower bound for the inner codes with , the TVZ lower bound for the outer codes, and the MRRW upper bound for the concatenated codes. The actual asymptotic performance curve with lies within the shaded region. The ANTV upper bounds are shown for reference as dashed-line.
across all values of , the resulting constraints on the outer code generally prevent the achievable performance from reaching this asymptotic region. We illustrate this effect in Section IV.
Computational Complexity
We evaluate the theoretical computational costs of the five modules involved in the construction of the proposed RACs. The target is an -RAC. Throughout this subsection, each arithmetic operation over a fixed finite field is treated as having unit cost.
Parameter identification. Before constructing the concatenated codes, we first determine the parameters of the inner and outer codes. In the finite-length implementation considered in this work, the inner code is selected from a fixed database . The outer-code parameters are then chosen so that the resulting concatenated code matches the target length and dimension. Hence, for a fixed database, the parameter-identification cost is
with respect to the target blocklength over the range of parameters supported by .
Concatenated-code construction. For fixed , a generator matrix of the GS-tower AG outer code can be constructed using field operations by the method of [13]. On the other hand, an RS outer code can be constructed using field operations. In addition, expanding the outer-code generator matrix over the base field and composing it with the inner code requires, using ordinary matrix multiplication, field operations. Thus, the complexities of this module are
For the GS-tower AG construction, the inner code and hence are fixed while the tower level is allowed to grow. If the outer-code rate is bounded away from zero and one, then and . Consequently,
For the RS construction, Eq. (61) gives the arithmetic complexity for each feasible finite-length parameter set. However, an ordinary RS outer code must satisfy . Hence, with a fixed base alphabet and a fixed inner code, the outer length cannot grow without bound. More generally, if the inner-code database is fixed and finite, the set of reachable RS blocklengths is also bounded. Therefore, under the finite-length RS design considered in this work, we do not interpret Eq. (61) as an asymptotic complexity bound in . The RS construction is used only as a finite-length benchmark.
Code-size modification. Let the generator matrix before shortening and puncturing have size . To puncture coordinates without reducing the dimension, nonpivot coordinates must be identified, for which we first reduce the generator matrix to RREF. Using ordinary Gaussian elimination, this requires field operations. Once the pivot structure is known, shortening, puncturing, and zero padding can be performed by row and column operations requiring at most additional operations. Therefore,
If both and grow linearly with the target RAC length, this becomes
OA-sampler construction. The dominant one-time preprocessing step is reducing an parity-check matrix of the RAC codebook to RREF. With ordinary Gaussian elimination, this requires
field operations over .
OA sampling. The computational cost of OA sampling is dominated by the reduction of the augmented matrix in (46), which has at most rows and columns, to RREF. This requires
field operations. If the RAC rate is bounded away from zero and the relative dual distance is bounded away from zero, then and . Thus, the worst-case complexity of this module is
Combining these estimates, the overall worst-case complexity of the AG/OA-RAC construction along the GS-tower family considered in this work is
Therefore, the explicit AG/OA-RAC family can be constructed and implemented in polynomial time as a function of the target blocklength.
Direct-Sum Strategy
In this section, we consider a strategy that partitions both the input information and the message into multiple blocks. We refer to such an RAC as a direct-sum RAC (DS-RAC) and formally define it as follows.
Definition 11 (Direct-sum RAC (DS-RAC)). We denote a -ary -RAC with worst-case decoding success probability by an -RAC, and let denote a specific RAC protocol with these parameters. Let
be a dataset of available -ary RAC protocols. A direct-sum RAC (DS-RAC) is an RAC constructed by taking the direct sum of constituent RACs selected from , according to the following procedure.
Block selection: Select constituent RACs , , from , allowing repetitions, such that
Encoding: Partition the input into blocks of lengths , respectively. Independently encode each block using its corresponding constituent RAC to obtain a message of length . Concatenate the resulting messages and transmit the concatenated message.
Decoding: Given a requested coordinate , identify the block containing and recover the corresponding input symbol using the decoder of the -th constituent RAC.
Maximizing the worst-case decoding success probability of this protocol amounts to solving
For a fixed dataset , the above optimization problem can be reduced to a knapsack-type problem. Thus, an optimal solution can be obtained by dynamic programming with computational complexity
More specifically, an optimal partition can be found using the procedure described in Algorithm 2.
We now show that the direct-sum strategy yields rate-universally asymptotically good RACs through a simple construction.
Theorem 12 (Rate-universal asymptotic goodness of the direct-sum construction). The direct-sum strategy with the dataset of -ary Hamming/OA-RACs and the trivial -RAC is rate-universally asymptotically good.
Proof. Recall that -ary Hamming codes have parameters for . Hence, the parameters of the corresponding Hamming/OA-RACs are
Let
and set , corresponding to the trivial -RAC. Then decreases to as . Hence, for every , there exists such that
By taking direct sums of the -th and -st constituent RACs in suitable proportions, we can construct a sequence whose blocklength tends to infinity and whose rate converges to . Indeed, the rate of a direct sum consisting of copies of the -th RAC and copies of the -st RAC is , and these rates can be made arbitrarily close to any value in by varying . Since for , where , each such direct sum has worst-case decoding success probability . Choose a sequence of such direct sums so that
Since , we have
Moreover,
Thus, this sequence is asymptotically good at rate . Since was arbitrary, the DS-RAC with a dataset containing all -ary Hamming/OA-RACs and the trivial -RAC is rate-universally asymptotically good.
Finally, although it suffices for the dataset to contain Hamming/OA-RACs in order to construct rate-universally asymptotically good RACs via the direct-sum strategy, incorporating other RACs into the dataset can further improve the worst-case decoding success probability. We investigate this improvement in detail through numerical experiments in a later section.
Numerical Experiments
We perform three numerical experiments. First, we compare the proposed OA encoder with the optimal encoder for fixed linear RAC codebooks. Second, we compare the certified worst-case decoding success probabilities of AG/OA-RACs and RS/OA-RACs for a fixed inner-code database and concatenated-code length.
Performance of the OA Encoder
To evaluate the encoder itself independently of concatenated-code design, we consider binary linear RACs of input length . For each dimension , we enumerate linearly inequivalent binary linear codes of length 10 and identify the largest dual distance . Because the OA encoder depends only on the dual distance, its best performance within this ensemble is obtained from a codebook attaining . For comparison, we also obtain optimal encoders using the linear programming formulation of [10]. Specifically, we determine an optimal encoder for every inequivalent linear code of length 10 and, for each code dimension, select the code that maximizes the worst-case decoding success probability. Note, however, that this optimization is restricted to linear RACs, and the size of the resulting linear program grows exponentially with the parameters. We also compare with the general Improved RAC construction of [3]. For , its worst-case decoding success probability is
The known upper bound (ANTV U.B.) [1] is also included as a reference.
Figure 2 shows that the OA encoder does not attain the optimal encoder performance for most rates, but it substantially improves on the Improved RAC over much of the range in which the latter is applicable. Closing the gap between the optimal encoder and the OA-based encoder is left for future work.
Figure 2. Worst-case decoding success probability for binary -RACs. The OA encoder is evaluated using codebooks with the maximum dual distance for each , whereas the optimal encoder is obtained by optimizing over all inequivalent linear codes.
Certified Performance of Proposed RACs with Finite-Length Codes
In Section III-F, we derived upper and lower bounds on the asymptotic performance of AG/OA-RACs under a constraint on the inner-code length. Here, we evaluate the finite-length performance of AG/OA-RACs using a database
Algorithm 3 Parameter selection for an RS concatenated code.
Input:
Output: Best parameter set , or if no certified minimum-distance lower bound of at least 2 is found
for do
is an linear code
▷ Concatenation constraint
if then ▷ Ordinary RS length constraint
if then
if then
end if
end if
end if
end for
if then
return
else
return
end if
of linear codes with fixed concatenated code length. For comparison, we also evaluate the performance of RS/OA-RACs. The parameters of the outer and inner codes are selected according to Algorithms 3 and 4. For the inner-code database , we use linear codes of length from SageMath’s [18] best_linear_code_in_guava routine, together with their shortened and punctured variants using (57). If
Algorithm 4 Parameter selection for a GS-tower AG concatenated code.
Input:
Output: Best parameter set , or if no positive guarantee is found
for do
is an linear code
if is even or is square then ▷ Square-field constraint for the GS tower
the value in (14)
if then
if then
end if
end if
end if
end for
if then
return
else
return
end if
remains empty, none of the candidate inner/outer-code combinations considered by the corresponding algorithm yields a strictly positive certified minimum-distance lower bound after adjustment to the requested . In this case, we set the certified relative minimum-distance guarantee to zero. Note that in this experiment, we compute only the certified relative minimum distance of each resulting linear code and the corresponding worst-case decoding success probability of the RAC derived from this guarantee; the generator matrices themselves are not explicitly constructed. As reference benchmarks, we also include the GV and Zyablov bounds. The GV bound is a classical existence bound for linear codes, whereas the Zyablov bound gives an existence guarantee for concatenated codes.
Figures 3a and 3b show that, at , the RS construction provides a larger certified relative minimum distance over much of the rate range and approaches the GV benchmark relatively closely. Thus, at moderate block-lengths, RS/OA-RAC provides a better finite-length worst-case decoding success probability. Note that the observed oscillations arise from the code-size modification and are not artifacts of the implementation.
As shown in Figure 4, for very large concatenated-code lengths, ranging to , the envelope of the finite-length curves approaches the asymptotic bounds derived in Section tion III-F, although the individual curves do not. This distinction arises because each individual curve is evaluated at a fixed concatenated-code length, whereas taking the envelope over different values of effectively removes this constraint and thus recovers the setting underlying the asymptotic bounds. Since the total code length is naturally fixed when evaluating a RAC at finite length, this distinction should be kept in mind when interpreting the asymptotic performance of the proposed construction.
Figure 4. Simultaneous plot of the guaranteed worst-case decoding success probabilities for concatenated-code lengths ranging up to . The asymptotic achievable region for AG/OA-RACs derived in Section III-F is also shown. Different line colors correspond to different concatenated-code lengths.
Figure 3. Certified relative minimum-distance lower bounds and worst-case decoding success probabilities for RS and GS-tower AG concatenated codes. (a) Certified relative minimum-distance lower bounds as functions of the base-code rate, together with the GV and Zyablov bounds. (b) Worst-case decoding success probability as a function of the RAC rate for AG/OA-RAC and RS/OA-RAC, with the asymptotic bounds shown by the shaded region. For the AG constructions, the legends indicate the selected inner code and GS-tower level . For the RS construction at , the selected inner code varies across many rate intervals, so the individual inner-code parameters are omitted from the legend for readability.
Practical Performance of DS-RAC
We numerically evaluated the worst-case decoding success probability of DS-RACs. We fixed the input length to and considered message lengths . The RAC dataset used in the DS-RAC consisted of the following:
RACs constructed using OA encoders with Hamming codes, repetition codes, or RS codes as the base codes, with and . For , RS codes were excluded because they do not yield nontrivial RACs.
-AG/OA-RACs with and whose worst-case decoding success probability strictly exceeds .
Figure 5 shows that DS-RACs with Hamming/OA-RACs alone achieve a worst-case decoding success probability greater than over a wide range of RAC rates. For , the worst-case decoding success probability does not exceed at some rates. This does not contradict Theorem 12, since the theorem provides a guarantee only in the asymptotic limit .
Figure 5. Worst-case decoding success probability of (200, )-RACs constructed using the direct-sum strategy for (a) and (b) . The gray dotted curve represents the ANTV upper bound [1].
The figure also shows that successively incorporating RACs from other infinite families improves the worst-case decoding success probability. For , adding Repetition/OA-RACs to Hamming/OA-RACs already yields a substantial improvement at high RAC rates, whereas the additional improvement obtained by including AG/OA-RACs is relatively small around an RAC rate of 0.6. A similar trend is observed for . In this case, however, Reed–Solomon/OA-RACs substantially improve the worst-case decoding success probability for RAC rates of approximately 0.3–0.7, while AG/OA-RACs provide a substantial improvement for rates of approximately 0.2–0.3.
We note that the performance of the AG/OA-RACs was evaluated using a lower bound on the minimum distance. Therefore, a tighter lower bound, i.e., a larger value of supplied to the OA encoder, is expected to yield an even higher worst-case decoding success probability.
Conclusion
In this work, we introduced the notion of asymptotically good RACs, whose compression fractions and worst-case decoding advantages over random guessing both remain bounded away from zero.
As the first approach to constructing such RACs, we introduced an OA encoder based on the orthogonal-array property of linear codes. Using dual codes as RAC codebooks, we showed that asymptotically good linear codes yield asymptotically good OA-RACs. We further gave an explicit polynomial-time realization using concatenated codes with Garcia–Stichtenoth algebraic-geometry outer codes.
As the second approach, we proposed a direct-sum strategy that constructs large RACs, called DS-RACs, by combining smaller RACs. We showed that, with a dataset containing all -ary Hamming/OA-RACs and the trivial -RAC, this strategy constructs asymptotically good RAC families at any prescribed rate .
Our numerical results demonstrated the finite-length performance of both approaches. OA-RACs substantially outperform the Improved RAC construction [3] over much of the examined range, although they do not generally attain the optimum. For the direct-sum strategy, incorporating OA-RACs derived from additional linear-code families, including algebraic-geometry codes, further improves the worst-case decoding success probability over a wide range of RAC rates. Developing improved encoders, constructing explicit RAC families closer to the entropy-optimal rate–success tradeoff, and reducing the sampling complexity below the present cubic-time implementation are natural directions for future work.
ACKNOWLEDGMENT
The authors used ChatGPT (GPT-5.6 Sol, OpenAI) for brainstorming, checking mathematical expressions and derivations in Sections II–IV, and assistance with Python code development. All AI-assisted content and code were independently reviewed and verified by the authors, who take full responsibility for the final manuscript.
References
- [1]Ambainis, A., Nayak, A., Ta-Shma, A. and Vazirani, U. Dense quantum coding and a lower bound for 1-way quantum automata. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing (STOC ’99), pages 376–383, 1999. doi: 10.1145/301250.301347.DOI
- [2]Nayak, A. Optimal lower bounds for quantum automata and random access codes. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 369–376. IEEE, 1999. doi: 10.1109/SFFCS.1999.814608.
- [3]Liabøtrø, O. Improved classical and quantum random access codes. Physical Review A, 95(5):052315, 2017. doi: 10.1103/PhysRevA.95.052315.
- [4]Ambainis, A., Kravchenko, D., Sazim, S., Bae, J. and Rai, A. Quantum advantages in (n, d) ↦ 1 random access codes. New Journal of Physics, 26(12):123023, 2024. doi: 10.1088/1367-2630/ad9bdff.DOI
- [5]Tavakoli, A., Hameedi, A., Marques, B. and Bourennane, M. Quantum random access codes using single d-level systems. Physical Review Letters, 114(17):170502, 2015. doi: 10.1103/PhysRevLett.114.170502.DOI
- [6]Imamichi, T. and Raymond, R. Constructions of quantum random access codes. In Proceedings of the Asian Quantum Information Symposium (AQIS), 2018. URL https://research.ibm.com/publications/constructions-of-quantum-random-access-codes.
- [7]Teramoto, K., Raymond, R., Wakakuwa, E. and Imai, H. Quantum-relaxation based optimization algorithms: theoretical extensions. arXiv preprint arXiv:2302.09481, 2023. doi: 10.48550/arXiv.2302.09481.DOI
- [8]Suzuki, T. Analytical construction of (n, n - 1)-quantum random access codes saturating the conjectured bound. Physical Review A, 114(1):012441, 2026.DOI
- [9]Akibue, S., Raymond, R., Tamaki, S. and Teramoto, K. Measurement geometry for quantum random access codes: Beyond Nayak bound and toward optimality. arXiv preprint arXiv:2606.12700, 2026.arxiv.org/abs/2606.12700
- [10]Kondo, R., Sato, Y., Yano, H., Maeda, Y., Ito, K. and Yamamoto, N. Random access codes: Explicit constructions, optimality, and classical-quantum gaps. arXiv preprint arXiv:2604.21274, 2026. doi: 10.48550/arXiv.2604.21274.DOI
- [11]Tan, S. and Jafar, S.A. 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. arXiv preprint arXiv:2607.10414, 2026.arxiv.org/abs/2607.10414
- [12]Garcia, A. and Stichtenoth, H. A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound. Inventiones mathematicae, 121 (1):211–222, 1995.DOI
- [13]Shum, K.W., Aleshnikov, I., Kumar, P.V., Stichtenoth, H. and Deolalikar, V. A low-complexity algorithm for the construction of algebraic-geometric codes better than the Gilbert-Varshamov bound. IEEE Transactions on Information Theory, 47(6):2225–2241, 2001.DOI
- [14]Tsfasman, M.A., Vlăduț, S.G. and Zink, T. Modular curves, shimura curves, and goppa codes, better than varshamov-gilbert bound. Mathematische Nachrichten, 109(1):21–28, 1982.DOI
- [15]Delsarte, P. An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl., 10: vi+–97, 1973.
- [16]Vardy, A. The intractability of computing the minimum distance of a code. IEEE Transactions on Information Theory, 43(6):1757–1766, 1997.DOI
- [17]McEliece, R., Rodemich, E., Rumsey, H. and Welch, L. New upper bounds on the rate of a code via the Delsarte-Macwilliams inequalities. IEEE transactions on Information Theory, 23(2):157–166, 1977.DOI
- [18]The Sage Developers. Sagemath, the Sage Mathematics Software System, 2026. doi: 10.5281/zenodo.8042260. URL https://www.sagemath.org. Version 10.9.




