Approaching the Quantum Singleton Bound
with Approximate Error Correction

Thiago Bergamaschi, Louis Golowich, Sam Gunn UC Berkeley. Email: [email protected].UC Berkeley. Email: [email protected]. Supported by an NSF Graduate Research Fellowship.UC Berkeley. Email: [email protected]. Supported by a Google PhD Fellowship.

Abstract

It is well known that no quantum error correcting code of rate $R$ can correct adversarial errors on more than a $(1-R)/4$ fraction of symbols. But what if we only require our codes to approximately recover the message?

In this work, we construct efficiently-decodable approximate quantum codes against adversarial error rates approaching the quantum Singleton bound of $(1-R)/2$ , for any constant rate $R$ . Specifically, for every $R\in(0,1)$ and $\gamma>0$ , we construct codes of rate $R$ , message length $k$ , and alphabet size $2^{O(1/\gamma^{5})}$ , that are efficiently decodable against a $(1-R-\gamma)/2$ fraction of adversarial errors and recover the message up to inverse-exponential error $2^{-\Omega(k)}$ .

At a technical level, we use classical robust secret sharing and quantum purity testing to reduce approximate quantum error correction to a suitable notion of quantum list decoding. We then instantiate our notion of quantum list decoding by (i) defining and constructing folded quantum Reed-Solomon codes, and (ii) applying a new, quantum version of distance amplification.

1 Introduction

There are several models of noise in quantum error correction. One of the weakest noise models is erasures, where some known subset of symbols are removed. The number of erasure errors that a code can tolerate is the distance of the code. At the other extreme there are adversarial errors, where an adversary is allowed to tamper arbitrarily with a subset of symbols (and the decoder doesn’t know which symbols were corrupted). The number of symbols that an adversary can be allowed to corrupt without sacrificing correctness of the decoded message is the decoding radius.

The quantum Singleton bound imposes an information-theoretic limit on the distance of a quantum code: No code of rate $R$ can correct from more than a $(1-R)/2$ fraction of erasures. But how far can we push the decoding radius? For the case of exact quantum error correction, it is a well-known consequence of the KL conditions [KL97] that any code of distance $d$ has decoding radius at most $d/2$ . Combined with the quantum Singleton bound, it follows that quantum codes cannot achieve decoding radius beyond a $(1-R)/4$ fraction of the block length.

However, in [CGS05] it was shown that, by relaxing the definition of quantum error correction to allow even exponentially-small error in the recovered state, one can design certain codes where the decoding radius essentially matches the quantum Singleton bound for very small (asymptotically decaying) rates. Unfortunately, that construction requires an exponentially large alphabet and is therefore unlikely to be useful for communicating over a noisy channel.

Still, the codes of [CGS05] indicate that the distance and the decoding radius might not be inherently far apart in approximate quantum error correction! This is in stark contrast to the classical setting, where it is impossible to build codes with decoding radius nearly matching the classical Singleton bound of $1-R$ for small rates¹¹1Indeed, given half of a codeword, an adversary could always substitute it with half of a fresh encoding of an arbitrary message. Therefore, decoding from adversarial errors up to the classical Singleton bound is impossible for $R<1/2$ .. Whether the quantum phenomenon was an artefact of the non-standard exponential alphabet used by [CGS05], or an exciting possibility for practical quantum error correcting codes, has essentially remained open.

In this work we construct the first efficiently-decodable approximate quantum error correcting codes over constant-sized alphabets with decoding radius approaching the quantum Singleton bound for all rates. Our codes have error that decays exponentially with the message size, and conclusively show that even a slight relaxation of standard quantum error correction permits the design of codes where the the distance and decoding radius are nearly identical.

1.1 Our Contributions

Main results.

Our main results are constructions of efficient approximate quantum error-correcting codes (AQECCs) approaching the quantum Singleton bound. We present two constructions, one in Corollary 4.8 and the other in Corollary 7.6, based on different approaches and with qualitatively slightly different guarantees. Either construction yields the following main result. We use the notation $[[n,k]]_{q}$ to refer to a quantum code which has block length $n$ , message length $k$ , and alphabet size (i.e., local dimension) $q$ .

Theorem 1.1 (Restatement of Corollary 4.8 and Corollary 7.6).

For any $\gamma>0$ and $0<R<1$ , there exists a family of approximate quantum $[[n,R\cdot n]]_{q}$ codes with constant alphabet size $q=q(\gamma)$ that correct errors acting on $(1-R-\gamma)\cdot n/2$ registers, up to a recovery error of $2^{-\Omega(n)}$ .

All of the codes we construct come with efficient algorithms for encoding and decoding. In Section 4 we present a general compiler that builds AQECCs from

•

quantum list-decodable codes,
•

purity testing codes, and
•

classical robust secret sharing schemes.

The purity testing codes of [BCG⁺02] and robust secret sharing schemes of [CDD⁺15] are sufficient for our purposes. Constructing good quantum list-decodable codes is the main technical part of this work. We define a quantum stabilizer code to be $(\tau,L)$ quantum list-decodable if each error syndrome is compatible with at most $L$ logically-equivalent Pauli errors of weight $\leq\tau n$ (Definition 3.2).

We construct CSS codes which are efficiently list-decodable up to the quantum Singleton bound by introducing folded quantum Reed-Solomon codes, a quantum version of the codes from [GR08].

Theorem 1.2 (Restatement of Theorem 3.8).

For any $\gamma>0$ and $0<R<1$ , there exists a family of quantum $[[n,R\cdot n]]_{q}$ stabilizer codes with alphabet size $q=n^{O(1/\gamma^{2})}$ which is $((1-R-\gamma)/2,n^{O(1/\gamma)})$ quantum list-decodable.

As in [GR08], the alphabet size of our folded codes scales with the block-length $n$ . To reduce the alphabet size to a constant, we introduce a quantum version of the expander-based distance amplification and alphabet reduction techniques of Alon, Edmonds, and Luby [AEL95]. This yields the following theorem.

Theorem 1.3 (Restatement of Theorem 6.1).

Together with our compiler, Theorem 1.3 allows us to obtain our main result Theorem 1.1.

Additional results.

We find our quantum version of distance amplification useful for three additional purposes. First, using recent constructions of good quantum LDPC codes [PK22, LZ22c, LZ22a, DHLV22, GPT22, LZ22b] we obtain quantum LDPC codes with distance approaching the quantum Singleton bound:

Theorem 1.4 (Restatement of Corollary 5.3).

For any $\gamma>0$ and $0<R<1$ , there exists a family of quantum LDPC $[[n,R\cdot n,(1-R-\gamma)\cdot n/2]]_{q}$ stabilizer codes with constant alphabet size $q=q(\gamma)$ .

Note that these codes are exact quantum error correcting codes, and are therefore only unique-decodable from errors on $(1-R-\gamma)/4$ fraction of registers.

Second, applying a more involved construction using AEL and quantum list decoding, we obtain the following LDPC version of Theorem 1.1, assuming access to a classical side-channel.

Theorem 1.5 (Restatement of Corollary 7.2).

For any $\gamma>0$ and $0<R<1$ , there exists a family of classical side-channel assisted approximate quantum LDPC $[[n,R\cdot n]]_{q}$ stabilizer codes with constant alphabet size $q=q(\gamma)$ that can correct errors acting on $(1-R-\gamma)\cdot n/2$ registers, up to a recovery error of $2^{-\Omega(n)}$ .

Third, we obtain alternative codes satisfying Theorem 1.1 in Corollary 7.6.

1.2 Technical Overview

We begin by defining AQECCs in Section 1.2.1. Then we present our definition of quantum list-decoding for stabilizer codes in Section 1.2.2, along with constructions in Section 1.2.3. In Section 1.2.4 we tie these ideas together to construct AQECCs from quantum list-decodable codes, purity testing codes, and robust secret sharing schemes.

We then turn to our quantum version of distance amplification in Section 1.2.5. Finally, we outline our use of these techniques to construct private LDPC codes in Section 1.2.6.

The discussion below assumes familiarity with basic notions of quantum error correction. The reader is referred to Section 2 or [Got97] for a review.

1.2.1 Approximate Quantum Error Correction

An approximate quantum error correcting code should encode message states into (possibly mixed) code-states, with the guarantee that the original messages are recoverable up to a high fidelity even when an adversary is allowed to tamper with a bounded number of registers. First, we define the syntax of a quantum code.

Definition 1.1.

An $[[n,k]]_{q}$ quantum code is a pair $(\mathsf{Enc},\mathsf{Dec})$ of quantum channels on qudits of local dimension $q$ such that

1.

$\mathsf{Enc}$ encodes a $k$ qudit message register $M$ into an $n$ qudit code-state register $C$ , and
2.

$\mathsf{Dec}$ decodes a received code-state register $\hat{C}$ into a $k$ qudit message register $\hat{M}$ .

The code is said to be efficient if $(\mathsf{Enc},\mathsf{Dec})$ can be implemented in polynomial time in $n$ . If the code-state register $C$ is defined on $n$ qudits, then the weight of an error channel acting on $C$ is the number of qudits of $C$ which the channel acts non-trivially on.

Definition 1.2 ([CGS05]).

A quantum code $(\mathsf{Enc},\mathsf{Dec})$ is said to be a $(\delta,\varepsilon)$ -AQECC (Approximate Quantum Error Correcting Code) if, for all adversarial channels $\mathcal{A}$ of weight $\delta\cdot n$ ,

\norm{\mathsf{Dec}\circ\mathcal{A}\circ\mathsf{Enc}-\mathbb{I}}_{\diamond}\leq\varepsilon.

We refer the reader to Section 2 for a review of distance measures between quantum states and channels.

While the ordinary quantum Singleton bound only applies to exact quantum error correcting codes, more robust versions for AQECCs also hold. Specifically, [MW22, Theorem 5] provides a general quantum Singleton bound for hybrid quantum/classical/entanglement-assisted codes with approximate or exact recovery.

Theorem 1.6 ([MW22]).

If a $(\delta,\varepsilon)$ -AQECC of local dimension $q$ has rate $R$ , then

\delta\leq\frac{1-R}{2}+O(\varepsilon\cdot c)

where $c=1+\log_{q}(1/\varepsilon)/n$ .

This bound also holds for AQECCs with side-information, or “private AQECCs” (Definition 1.5).

1.2.2 Defining Quantum List-Decodable Codes

Recall that stabilizer codes [Got97] are a subspace of $n$ -qudit states, defined as the joint eigenspace of a set of commuting operators called the stabilizer generators. Given a corrupted code-state, the syndrome measurement is the projective measurement of the eigenvalues of the stabilizer generators. The measurement outcome (a list of eigenvalues) is referred to as the syndrome, and is the quantum analogue of a classical parity check syndrome.

In classical coding theory, a code $C\subset\Sigma^{n}$ is said to be $(\tau,L)$ list-decodable [Woz58, Eli57] if there are at most $L$ codewords of $C$ in any hamming ball of radius $\tau\cdot n$ in $\Sigma^{n}$ . To understand our quantum analogue, observe that for linear codes this classical notion is exactly equivalent to requiring that there are at most $L$ errors of weight at most $\tau\cdot n$ consistent with each possible parity check syndrome.

Perhaps the most direct quantum translation would be the following: A stabilizer code $Q$ could be $(\tau,L)$ quantum list-decodable if for every possible syndrome $s$ , there are at most $L$ Pauli operators of weight at most $\tau\cdot n$ that are consistent with the syndrome $s$ . However, if the code has many low-weight stabilizers (such as concatenated codes) then the list of errors consistent with a given syndrome could contain exponentially many logically-equivalent Pauli operators. Since such logically-equivalent errors by definition have the same action on codewords, we instead use a slightly relaxed definition where we only count logically-distinct operators in the list.

Definition 1.3 (Restatement of Definition 3.2).

A stabilizer code $Q$ is $(\tau,L)$ quantum list-decodable (QLD) if for every possible syndrome $s$ , there are at most $L$ logically-distinct Pauli operators of weight at most $\tau\cdot n$ that are consistent with the syndrome $s$ .

Therefore, after measuring the syndrome, quantum list-decoding is the entirely classical task of computing the list of possible corrections for the given syndrome.

1.2.3 Constructions of Quantum List-Decodable Codes

Our main tool for designing these quantum list-decodable codes is a reduction to classical list-decoding via CSS codes.

Claim 1.7.

If $C_{1},C_{2}\subset(\mathbb{F}_{q}^{m})^{n}$ are two $\mathbb{F}_{q}$ -linear classical codes which are $(\tau,L)$ list-decodable and $C_{2}^{\perp}\subset C_{1}$ , then there exists a CSS code CSS $(C_{1},C_{2})$ which is $(\tau,L^{2})$ quantum list-decodable. Moreover, if the classical codes are efficiently list-decodable, then the CSS code is as well.

This follows from the fact that correcting errors on a code-state of a CSS code simply consists of correcting the $X$ and $Z$ errors.²²2Technically we consider generalized Paulis, the “shift” and “phase” operators. We refer the reader to Section 2 or [AK01] for a review of stabilizer codes over finite fields.

The central insight behind our quantum code construction — and later the quantum distance amplification in Section 1.2.5 — is that syntactic or physical operations on the registers of a quantum code are not only well-defined, but behave similarly to their classical counterparts. For instance, folding a quantum CSS code (i.e., bundling together $m$ consecutive qudits into a larger qudit) induces folded component classical codes:

Claim 1.8 (Informal statement of 3.7).

If $Q$ is the CSS code of two linear classical codes $C_{1},C_{2}\subset\mathbb{F}_{q}^{n}$ , then the $m$ -folded quantum code $Q^{(m)}$ is a CSS code of the two $\mathbb{F}_{q}$ -linear $m$ -folded classical codes $C_{1}^{(m)},C_{2}^{(m)}\subset(\mathbb{F}_{q}^{m})^{n/m}$ .

This follows from the fact that folding operation automatically bundles the qudits in both bases, so error correction in each basis can leverage folding. Instantiating 1.8 with the folded Reed-Solomon codes of [GR08], we obtain explicit quantum list-decodable codes tolerating errors up to the quantum Singleton bound:

Theorem 1.9 (Restatement of Theorem 3.8).

Unfortunately, these folded quantum codes have alphabet size $n^{O(1/\gamma^{2})}$ rather than constant. [GR08] reduce the alphabet size by showing that their codes can be used for the related task of list-recovery, and combining their ideas with the distance amplification and alphabet reduction techniques of [AEL95]. The main technical component of this work is to show that an analogous quantum list-recovery task can be used in combination with a quantum analog of the distance amplification techniques by [AEL95]. We outline quantum distance amplification in Section 1.2.5.

Using quantum distance amplification, we present a randomized construction of quantum stabilizer codes on constant sized alphabets, with list decoding radius approaching the quantum Singleton bound.

Theorem 1.10 (Restatement of Theorem 6.1).

For any $\gamma>0$ and $0<R<1$ , there exists a family of quantum $[[n,R\cdot n]]_{q}$ stabilizer codes with constant alphabet size $q=2^{O(1/\gamma^{5})}$ which is $((1-R-\gamma)/2,n^{O(1/\gamma^{3})})$ quantum list-decodable. Moreover, there exists an efficient randomized algorithm to construct a classical description of the stabilizers of the code, which succeeds with high probability.

1.2.4 Construction of AQECCs from Quantum List-Decodable Codes

Quantum list decoding enables us to find a short list of possible errors which match a syndrome measurement. If we had some way of tagging valid messages, then we could filter through the list for the true error and obtain unique decoding.

We find that purity testing codes (PTCs) [BCG⁺02] are well-suited for this task. A PTC is a collection $\{Q_{k}\}_{k\in K}$ of stabilizer codes which is able to faithfully detect a Pauli error with high probability over keys $k\leftarrow K$ . They were originally introduced to construct quantum authentication schemes, but it turns out that we do not need full quantum authentication for our purposes.

Definition 1.4 (Purity testing codes, [BCG⁺02]).

A stabilizer purity testing code with error $\varepsilon$ ( $\varepsilon$ -PTC) is a set of stabilizer codes $\{Q_{k}\}_{k\in K}$ such that, for all Pauli errors $E$ ,

\Pr_{k}\big{[}E\in N(Q_{k})\setminus S(Q_{k})]\leq\varepsilon

where $S(Q_{k})$ is the stabilizer group of $Q_{k}$ and $N(Q_{k})$ is the normalizer group.

We construct private AQECCs by first encoding the message in a PTC $Q_{k}$ , and subsequently encoding in a quantum list-decodable code $Q_{LD}$ . As long as the keys are kept secret from the channel, the probability that an undetectable error appears in the list is at most $\varepsilon\cdot L$ by a union bound. Therefore a recipient who knows $k$ can uniquely recover the message with probability $1-\varepsilon\cdot L$ .

Of course, this construction gives a collection of codes $\{Q_{LD}\circ Q_{k}\}_{k\in K}$ rather than a single code. Since the channel cannot be allowed to see the keys $k$ , we only obtain a relaxed version of AQECCs where the sender and receiver have shared private randomness (unknown to the error channel). We call such codes private AQECCs in analogy to the classical private codes of [Lan04, Gur03b].

Definition 1.5.

A set of quantum codes $\{(\mathsf{Enc}_{k},\mathsf{Dec}_{k})\}_{k\in K}$ is said to be a $(\delta,\varepsilon)$ private AQECC with keys $K$ if, for all adversarial channels $\mathcal{A}$ of weight $\delta\cdot n$ ,

\norm{\mathbb{E}_{k\leftarrow K}\left[\mathsf{Dec}_{k}\circ\mathcal{A}\circ\mathsf{Enc}_{k}\right]-\mathbb{I}}_{\diamond}\leq\varepsilon.

By using $k\leftarrow K$ as the shared private randomness, we obtain the following theorem.

Lemma 1.11 (Restatement of Lemma 4.1).

Let $\{Q_{k}\}$ be an $\varepsilon$ -PTC where each $Q_{k}$ is an $[[n_{PTC},m]]_{q}$ stabilizer code, and let $Q_{LD}$ be a $[[n,n_{PTC}]]_{q}$ stabilizer code which is $(\delta,L)$ quantum list-decodable. Then $Q_{LD}\circ Q_{k}$ is a $(\delta,2\cdot L\cdot\varepsilon)$ private AQECC.

In this construction, it becomes important that the adversary cannot choose the error according to the key $k$ . The local indistinguishability of $Q_{LD}$ protects against such attacks, by ensuring that the adversary’s view consisting of fewer than $\text{dist}(Q_{LD})$ components of a code-state of $Q_{LD}\circ Q_{k}$ is the same regardless of the value of $k$ .

To convert a private AQECC into an AQECC, we incorporate the classical key information into the quantum registers. The key tool for this conversion is a classical robust secret sharing schemes (RSSs) [CDD⁺99, CDF01, CDF⁺08, CDD⁺15]³³3Also known as an Error Tolerant Secret Sharing scheme (ETSS)., which ensures that the hidden secret key looks uniformly random to the adversary while still allowing the receiver to reconstruct the key with high probability. [CGS05] used a combination of classical secret sharing and classical authentication from [CDF01] to construct such an RSS. We need to be more careful with our choice of classical secret sharing scheme, in order to ensure that the resulting quantum code still lies roughly on the quantum Singleton bound and maintains constant alphabet. In Section 4, we use a more recent RSS construction of [CDD⁺15] to prove the following theorem.

Theorem 1.12 (Informal statement of Theorem 4.7).

For any $[[n,k]]_{q}$ code that is a $(\delta,\varepsilon)$ private AQECC with sufficiently short keys, there is a $[[n,(1-O\left(\frac{1}{\log(q)}\right))\cdot k]]_{O(q)}$ code that is a $(\delta,\varepsilon+2^{-\Omega(n)})$ AQECC.

1.2.5 Distance Amplification for Quantum Codes

In order to decrease the alphabet size of our quantum code constructions and improve on their encoding/decoding efficiency, we develop a quantum analog of the seminal distance amplification techniques for classical error correcting codes by Alon, Edmonds and Luby [AEL95]. Their ideas hinged on using code concatenation and a careful redistribution (or permutation) of the symbols of the code, in order define a new code with a larger distance and/or smaller alphabet (and slightly lower rate). These techniques have found extensive use in classical coding theory, such as the construction of linear time encodable/decodable codes [GI02], the construction of list-decodable codes from list-recoverable codes [GI03, GR08], high-rate locally testable codes [KMRZS15, GKO⁺18, HRZW19], and many other applications.

The simplest formulation of the quantum analog we study can be understood as physically permuting and re-grouping the qudits of a concatenated quantum code [KL96]⁴⁴4See Definition 2.5 for a review of quantum code concatenation.. Starting with an outer $[[n,k,n\cdot\Delta_{out}]]_{q^{m}}$ stabilizer code $Q_{out}$ , and an inner $[[n^{\prime},m,n^{\prime}\cdot\Delta_{in}]]_{q}$ stabilizer code $Q_{in}$ , their quantum code concatenation is the $[[n\cdot n^{\prime},k\cdot m]]_{q}$ stabilizer code $Q_{\diamond}=Q_{out}\diamond Q_{in}$ . Consider a physical depiction of $Q_{\diamond}$ as a $n\times n^{\prime}$ table of $q$ -ary qudits. The final step is to use an $n^{\prime}$ -biregular expander graph $G=(L\cup R,E)$ on two partitions of $|L|=|R|=n$ nodes, to redistribute the qudits of $Q_{\diamond}$ into another $[[n,km/n^{\prime}]]_{q^{n^{\prime}}}$ stabilizer code $Q_{G}$ . To do so, if the $i$ th edge incident to $u\in L$ equals the $j$ th edge incident to $v\in R$ , then the $i$ th $q$ -ary qudit of the $u$ th inner block of $Q_{\diamond}$ is placed into the $j$ th $q$ -ary qudit of the $v$ th inner block of $Q_{G}$ . In other words, the table associated to $Q_{\diamond}$ is permuted into another $n$ by $n^{\prime}$ table for $Q_{G}$ , and each of its rows represents a $q^{n^{\prime}}$ -ary qudit. Qualitatively, this qudit redistribution ensures that any $q^{n^{\prime}}$ -ary Pauli $E$ (represented as a tensor product of $q$ -ary Pauli’s) supported on roughly a $<\Delta_{in}/2$ fraction of the rows of $Q_{G}$ , after unpermuting $G$ , is then almost uniformly spread out among the inner blocks/rows of $Q_{\diamond}$ such that most inner blocks have less than $\Delta_{in}/2$ fraction of errors. If the fraction of the ‘high weight’ inner blocks is less than $\Delta_{out}/2$ , then $E$ is a perfectly correctable error for $Q_{G}$ , and thus $Q_{G}$ has relative distance roughly $\Delta_{in}$ .

Theorem 1.13 (Informal statement of Proposition 5.1).

If $G$ is an $\varepsilon$ -pseudorandom expander graph (Definition 5.1), then $Q_{G}$ has relative distance $\geq\Delta_{in}-2\cdot\varepsilon\cdot\sqrt{\Delta_{in}/\Delta_{out}}$ .

In Section 5 we argue that the insights from [AEL95] translate remarkably well into the quantum setting. We analogously adapt these ideas, and the intuition above to decrease the alphabet of our quantum codes, construct quantum list decodable codes from a suitable analog of quantum list recoverable codes, and to construct private AQECC’s which are LDPC and encodable/decodable in linear time.

1.2.6 Private LDPC AQECCs with Linear-Time Decoding

Recall that the construction of efficient private AQECCs described in Section 1.2.4 first constructs efficient quantum list-decodable codes using AEL amplification with inefficient but small quantum list-decodable inner codes, and then composes these AEL-amplified codes with PTCs to obtain the desired private AQECCs. Therefore while this construction provides a general recipe for AQECCs, as mentioned previously the outer code of the AEL concatenation must satisfy an appropriate form of quantum list-recoverability, which we only know how to achieve with folded quantum Reed-Solomon codes.

In Section 7, we present a construction of efficient private AQECCs that permits more flexibility in the code properties by combining the same ingredients described above in an alternative manner. Specifically, if we instead apply AEL amplification with a certain class of inefficient but small private AQEC inner codes, the outer code may be chosen to be any asymptotically good efficient quantum code $Q_{\text{out}}$ . The resulting construction will be an efficient private AQECC that inherents some of the properties of $Q_{\text{out}}$ , such as its locality and decoding time. Thus choosing the outer code from a family of good quantum LDPC codes [PK22, LZ22c, LZ22a, DHLV22, GPT22, LZ22b], we obtain the efficient private LDPC AQECCs of Theorem 1.5.

1.3 Related Work

The idea of using approximate quantum error correction to build better quantum codes goes back to [LNCY97], who construct a 4-qubit AQECC encoding one qubit that tolerates a specific noise model.

A more closely related result is that of [CGS05], who construct AQECCs with a decoding radius of $\lfloor(n-1)/2\rfloor$ for codes of block length $n$ . Their construction is based on a combination of quantum error correction, quantum message authentication, and classical secret sharing. However, the code in [CGS05] has asymptotically decaying rate, and is defined on qudits with exponentially large local dimension. To go beyond the exponential-alphabet regime we use quantum list decoding.

A related notion of quantum list decoding was introduced by [LS08], who show that random stabilizer codes on qubits are quantum list-decodable with high probability. They use these codes to construct private AQECCs on qubits with rates up to $1-H(\delta)-\delta\log 3$ (where $\delta\cdot n$ is the decoding radius).

Compared to this work, [LS08] have a slightly different definition of quantum list decoding and do not construct codes with efficient decoding procedures. In fact, we expect that an efficient decoding algorithm for random stabilizer codes should not exist. Moreover, their codes do not approach the quantum Singleton bound because they restrict to binary alphabets. While extending their results to larger (but still constant) alphabets would yield codes that do approach the quantum Singleton bound, the problem of efficient decoding would remain.

Several works have studied conditions in which approximate quantum error correction is possible [BK00, SW02, Dev05, KSW08, Bén09, NM10, MN12, BO10, HP17]. For instance, [SW02, KSW08, Bén09, BO10] were interested in characterizing when information can be sent over a noisy quantum channel, with or without prior knowledge of the input state and the noise model. [NM10, MN12] studied the efficacy and optimality of the transpose channel as a recovery map, when the noise process is known. [Dev05, HP17] studied applications of approximate quantum error correction to quantum and classical communication, including to the tasks of state merging, entanglement distillation, quantum identification and remote state preparation.

[BDH06] introduced the concept of an entanglement-assisted quantum error correcting code (EAQECC), when the sender and receiver have access to an unbounded supply of pre-shared EPR pairs. A number of results [LBW13, LB13, WHB11] studied properties of EAQECCs, and discussed their construction from classical linear codes. While no pure quantum code can bypass the quantum Singleton bound, quite remarkably, recently EAQECCs were shown to be able to transmit quantum information up to the classical Singleton bound [Gra20] in certain parameter regimes. [DS03, HW08, GHW22, MW22] proved Singleton bounds and other upper bounds on the capacity of entanglement-assisted and private quantum codes.

1.4 Discussion and Open Problems

The folded Reed-Solomon codes [GR08] are a family of deterministic, polynomial-time constructible classical codes which approach the information-theoretic list-decoding limit. Since their result, a number of (explicit) codes have improved on their alphabet and list sizes [Gur10, GX20, GRZ22], without the need of expander-based distance amplification [AEL95]. However, it seems unclear how to use these codes to design quantum codes, as their duals aren’t necessarily explicit, or they require pre-encoding with certain subspace-evasive sets [DL12, GXY17] to reduce their list sizes. We leave for future work the design of explicit quantum codes approaching the list-decoding capacity at small qudit local dimensions.

We note that the techniques in this work can be used to formalize a quantum analog of list-decoding from erasures, where the receiver is tasked with producing a list of correction operators to a reduced density matrix of some code-state. This task has been extensively studied in the classical setting [GI01, Gur03a, GI03, GI04, RZWZ20], where it is well known that random binary linear codes are efficiently erasure list-decodable even when all but a small fraction of symbols have been erased. One could ask an analogous question for quantum codes on qubits: For fixed rate $R$ , what is the maximum number of erasures for which one can still efficiently list-decode (or approximately unique-decode) the quantum state?

1.5 Organization

We organize the rest of this work as follows. In Section 2 we review the necessary background on quantum error correction. In Section 3 we present our definition of quantum list decoding and our results on list-decodable CSS codes, including our explicit construction of folded quantum Reed-Solomon codes. In Section 4 we show how to reduce approximate quantum error correction to quantum list decoding. In Section 5 we describe our quantum distance amplification and alphabet reduction techniques. We apply this AEL amplification in Section 6 to construct efficient quantum list-decodable codes approaching the quantum Singleton bound over constant alphabets. We apply AEL in an alternative manner in Section 7 to construct private LDPC AQECCs with linear-time decoders, which as a byproduct gives another construction of efficient AQECCs.

In Appendix A we discuss the list decodability and other simple properties of random CSS codes, which follow easily from their classical counterparts. For completeness, in Appendix B we introduce a quantum notion of list recoverability and a “fully-quantum” proof of the construction of quantum list decodable codes on smaller alphabets from quantum list recoverable codes and distance amplification.

2 Preliminaries

2.1 Notation

Norms and Distances We use three notions of distance between quantum states and quantum channels. The trace distance $\|\rho-\sigma\|_{1}$ between two mixed states $\rho,\sigma\in\mathcal{D}(\mathcal{H})$ captures their distinguishability, and is defined in terms of the trace norm (or Shatten 1-norm) $\|M\|_{1}=\text{Tr}[\sqrt{M^{\dagger}M}]$ . The fidelity $F(\rho,\sigma)=\|\sqrt{\rho}\sqrt{\sigma}\|_{1}^{2}$ , and can be written simply as $\bra{\psi}\rho\ket{\psi}$ when $\sigma=\ket{\psi}\bra{\psi}$ is a pure state.

Finally, the diamond norm distance between two quantum channels $\mathcal{M},\mathcal{N}:\mathcal{L}(\mathcal{H}_{A})\rightarrow\mathcal{L}(\mathcal{H}_{B})$ , quantifies their distinguishability even in the presence of entanglement

\|\mathcal{N}-\mathcal{M}\|_{\diamond}=\sup_{n}\max_{\rho_{AE}}\|(\mathbb{I}_{n}\otimes\mathcal{N})(\rho_{AE})-(\mathbb{I}_{n}\otimes\mathcal{M})(\rho_{AE})\|_{1}

(1)

where $\rho_{AE}\in\mathcal{D}(\mathcal{H}_{A}\otimes\mathcal{H}_{E})$ .

Finite Fields Let $q=p^{m}$ be a power of a prime $p$ , and denote by $\mathbb{F}_{q}$ to be the Galois field of $p^{m}$ elements. We refer to the $\mathbb{F}_{p}$ functional $\text{tr}_{\mathbb{F}_{q}/\mathbb{F}_{p}}:\mathbb{F}_{q}\rightarrow\mathbb{F}_{p}$ as the trace function, where $\text{tr}_{\mathbb{F}_{q}/\mathbb{F}_{p}}(a)=\sum_{i=0}^{m-1}a^{p^{i}}$ . If $\alpha_{1},\cdots,\alpha_{m}$ is a basis of $\mathbb{F}_{q}$ over $\mathbb{F}_{p}$ , then one can express $a\in\mathbb{F}_{q}$ as $a=\sum_{i=1}^{m}a_{i}\alpha_{i}$ for $a_{i}\in\mathbb{F}_{p}$ . We refer to a pair of bases $\alpha=\alpha_{1},\cdots,\alpha_{m}$ , $\beta=\beta_{1}\cdots\beta_{m}$ of $\mathbb{F}_{q}$ as dual bases if $\text{tr}_{\mathbb{F}_{q}/\mathbb{F}_{p}}(\alpha_{i}\beta_{j})=\delta_{i,j}$ . If $a,b\in\mathbb{F}_{q}$ is expressed as $(a_{1},\cdots,a_{m})$ , $(b_{1},\cdots,b_{m})$ in the dual bases $\alpha,\beta$ respectively, then the inner product over the basis representation becomes the trace:

\big{\langle}a,b\big{\rangle}=\sum_{i=1}^{m}a_{i}b_{i}=\sum_{i,j=1}^{m}a_{i}b_{j}\text{tr}_{\mathbb{F}_{q}/\mathbb{F}_{p}}(\alpha_{i}\beta_{j})=\text{tr}_{\mathbb{F}_{q}/\mathbb{F}_{p}}(ab)

(2)

Error Basis To connect these notions to quantum codes, we define an explicit error basis for $q=p^{m}$ -ary quantum systems. Fix $\omega=e^{2\pi i/p}$ . Let $T,R$ be the ‘shift’ and ‘phase’ operators on $\mathbb{C}_{p}$ , defined by

T=\sum_{x\in\mathbb{F}_{p}}\ket{x}\bra{x+1}\text{ and }R=\sum_{x\in\mathbb{F}_{p}}\omega^{x}\ket{x}\bra{x}

(3)

The operators $T^{i}R^{j}$ , $i,j\in\mathbb{F}_{p}$ form the Weyl-Heisenberg operators, an orthonormal basis of operators over $\mathbb{C}_{p}$ . If $a,b\in\mathbb{F}_{q}$ , with representations $(a_{1},\cdots a_{m})$ , $(b_{1},\cdots b_{m})$ in the dual bases $\alpha,\beta$ respectively, then one can define an o.n. basis of operators over $\mathbb{C}_{q}$ :

E_{a,b}=X^{a}Z^{b}=\bigotimes_{i\in[m]}T^{a_{i}}R^{b_{i}}\text{ and thus }E_{a,b}E_{a^{\prime},b^{\prime}}=\omega^{\langle a,b^{\prime}\rangle-\langle a^{\prime},b\rangle}E_{a^{\prime},b^{\prime}}E_{a,b}.

(4)

Finally, if $\textbf{a}=(a^{(1)},a^{(2)}\cdots a^{(n)}),\textbf{b}=(b^{(1)},b^{(2)}\cdots b^{(n)})\in\mathbb{F}_{q}^{n}$ , then one can define operators acting on $\mathbb{C}_{q}^{\otimes n}$ via $E_{\textbf{a},\textbf{b}}=\otimes_{j\in[n]}E_{a^{(j)},b^{(j)}}$ . The error group $\mathcal{P}_{q}^{n}$ is the group generated by the $E_{\textbf{a},\textbf{b}}$ and the phase $\omega\cdot\mathbb{I}_{q^{n}\times q^{n}}$ . The weight $wt(E_{\textbf{a},\textbf{b}})$ is the number of locations $j\in[n]$ where either $a^{(j)},b^{(j)}$ are non-zero, and $\mathcal{P}_{q,\delta}^{n}\subset\mathcal{P}_{q}^{n}$ is the set of operators in the error group of weight less than $\delta\cdot n$ .

2.2 Quantum Error Correction

Definition 2.1 ([KL97]).

An $[[n,k,d]]_{q}$ QECC (quantum error correcting code) is a subspace $Q\subset(\mathbb{C}^{q})^{\otimes n}$ of dimension $q^{k}$ . Let $\Pi$ be the projection onto $Q$ . If for all operators $E$ of weight $\leq d$ , we have

\Pi E\Pi=\eta_{E}\Pi

(5)

where $\eta_{E}\in\mathbb{C}$ only depends on $E$ , then $Q$ is said to have distance $d$ .

Quantum stabilizer codes are a class of QECCs defined as the joint eigenspace of a set $S$ of commuting operators, the stabilizers. We discuss a presentation of stabilizer codes over finite fields by [AK01].

Definition 2.2 (Stabilizer Codes over Finite Fields, [AK01]).

Let $q=p^{m}$ be a prime power. Let the set of operators $\{S_{1},\cdots,S_{r}\}\subset\mathcal{P}_{q}^{n}$ generate a commutative subgroup $S$ of $\mathcal{P}_{q}^{n}$ . Then the subspace $Q\subset\mathbb{C}_{q}^{\otimes n}$ defined by

Q=\bigg{\{}|\psi\rangle\in\mathbb{C}_{q}^{\otimes n}:S_{i}\ket{\psi}=\ket{\psi}\text{ for all }i\in[r]\bigg{\}}

(6)

forms a $[[n,n-\frac{r}{m}]]_{q}$ QECC.

We refer to the stabilizer group of a code $Q$ as $S(Q)$ . Associated to a stabilizer group is the normalizer group $N(Q)$ , the set of operators in the error group $\mathcal{P}_{q}^{n}$ which commute with all the elements of $S(Q)$ . The elements of $N(Q)-S(Q)$ ⁵⁵5By which we mean the set difference, to distinguish from the quotient group. are the ‘undetectable errors’ on $Q$ , as they map code-states to distinct code-states, and the quotient group $N(Q)/S(Q)$ are the logical operators on $Q$ . The distance of $Q$ is the lowest weight of any operator in $N(Q)-S(Q)$ . The class of ‘detectable’ errors of $Q$ are the operators outside $N(Q)$ , which we detect by measuring the syndrome vector:

Definition 2.3.

For any operator $E\in\mathcal{P}_{q}^{n}$ , we refer to the syndrome $s_{E}=(s_{1},s_{2}\cdots,s_{r})\in\mathbb{F}_{p}^{r}$ of the operator $E$ on the stabilizer code $Q$ as the phases $s_{i}$ defined by $S_{i}E=\omega^{s_{i}}ES_{i}$ for $i\in[r]$ .

Note that if $E\in N(Q)$ , then the syndrome is 0, $s_{E}=0^{r}$ . Moreover, the syndrome is additive: if $E,E^{\prime}\in\mathcal{P}_{q}^{n}$ , then $s_{EE^{\prime}}=s_{E}+s_{E^{\prime}}$ , and $s_{E^{\dagger}}=-s_{E}\mod p$ .

We instantiate most of our constructions in this work using the CSS codes introduced by [CS96, Ste96], and their extensions to non-binary fields [KKKS06, RGB04, KW08].

Theorem 2.1 (Galois-qudit CSS codes).

Fix two linear classical codes $C_{1},C_{2}\subset\mathbb{F}_{q}^{n}$ of dimension $k$ , where $C_{2}^{\perp}\subset C_{1}$ and $C_{1},C_{2}$ both have distance at least $d$ . Let CSS $(C_{1},C_{2})\subset\mathbb{C}_{q}^{\otimes n}$ be the stabilizer code defined by the stabilizers $E_{\textbf{a},\textbf{b}}\in\mathcal{P}_{q}^{n}$ , $a\in(C_{2})^{\perp},b\in(C_{1})^{\perp}$ . Then CSS $(C_{1},C_{2})$ is a $[[n,2k-n,d]]_{q}$ QECC.

Moreover, the normalizer group of CSS $(C_{1},C_{2})$ are (up to a global phase) the operators $E_{\textbf{a},\textbf{b}}\in\mathcal{P}_{q}^{n}$ , $a\in C_{1},b\in C_{2}$ . While a seemingly minor modification, it will later be relevant to discuss CSS codes over vector spaces as well. As the authors haven’t found such a pre-existing definition in the literature, we discuss a short self-contained proof below, which follows immediately from the techniques by [AK01].

Theorem 2.2.

Fix two $\mathbb{F}_{q}$ -linear $[n,k]_{q^{m}}$ classical codes $C_{1},C_{2}\subset(\mathbb{F}_{q}^{m})^{n}$ of dimension $k$ , where $C_{2}^{\perp}\subset C_{1}$ and $C_{1},C_{2}$ both have distance at least $d$ . Let CSS $(C_{1},C_{2})\subset(\mathbb{C}_{q}^{\otimes m})^{\otimes n}$ be the stabilizer code defined by the stabilizers $E_{\textbf{a},\textbf{b}}\in\mathcal{P}_{q}^{n\cdot m}$ , $a\in(C_{2})^{\perp},b\in(C_{1})^{\perp}$ . Then CSS $(C_{1},C_{2})$ is a $[[n,2k-n,d]]_{q^{m}}$ QECC.

Proof.

We view the codewords of $a\in C_{1}^{\perp},b\in C_{2}^{\perp}$ as elements of $(\mathbb{F}_{q})^{n\cdot m}$ , and define the set of operators $E_{\textbf{a},\textbf{b}}\in\mathcal{P}_{q}^{n\cdot m}$ using the same expansion as the Galois-qudit construction. By design, these operators are commuting and thus define a stabilizer code $Q$ over $\mathbb{C}_{q}^{\otimes n\cdot m}$ , which we view as a code $Q^{\prime}$ over $(\mathbb{C}_{q}^{\otimes m})^{\otimes n}$ . ∎

2.3 Composition and Concatenation of Quantum Codes

If $Q$ is a $[[n,k]]_{q}$ stabilizer code, then let $\mathsf{Enc}_{Q}:\mathbb{C}_{q}^{\otimes k}\rightarrow\mathbb{C}_{q}^{\otimes n}$ be the isometry which encodes into $Q$ . Recall that $\mathsf{Enc}_{Q}$ is a Clifford circuit, such that if $X\in\mathcal{P}_{q}^{k}$ is a operator in the Pauli group on $k$ qudits, then we let

\bar{X}=\mathsf{Enc}_{Q}X\mathsf{Enc}_{Q}^{\dagger}\in\mathcal{P}_{q}^{n},

(7)

refer to the encoding of $X$ on $Q$ .

Definition 2.4.

Let $Q_{1}$ be an $[[n,m]]_{q}$ stabilizer code, and $Q_{2}$ an $[[m,k]]_{q}$ stabilizer code. Then the composition $Q_{\circ}=Q_{1}\circ Q_{2}$ of $Q_{1},Q_{2}$ is the $[[n,k]]_{q}$ stabilizer code defined by encoding any message $\ket{\psi}\in\mathbb{C}_{q}^{\otimes k}$ as

\mathsf{Enc}_{\circ}(\psi)=\mathsf{Enc}_{Q_{1}}(\mathsf{Enc}_{Q_{2}}(\ket{\psi}))

(8)

Since $Q_{1},Q_{2}$ are stabilizer codes, $Q_{\circ}$ can alternatively be characterized in terms of its stabilizers:

Fact 2.1.

If $\{S^{1}_{i}\}_{i\in[r_{1}]}\subset\mathcal{P}_{q}^{n}$ and $\{S^{2}_{j}\}_{j\in[r_{2}]}\subset\mathcal{P}_{q}^{m}$ are the stabilizer generators of $Q_{1},Q_{2}$ respectively, then the stabilizer generators of $Q_{\circ}$ are those of $Q_{1}$ together with those of $Q_{2}$ encoded into $Q_{1}$ :

\{S^{1}_{i}\}_{i\in[r_{1}]}\cup\{\bar{S}^{2}_{i}\}_{j\in[r_{2}]}=\{S^{1}_{i}\}_{i\in[r_{1}]}\cup\{\mathsf{Enc}_{Q}S^{2}_{j}\mathsf{Enc}_{Q}^{\dagger}\}_{j\in[r_{2}]}

(9)

The notion of concatenated (classical) codes was developed in a seminal work by Forney in 1966 [For09], and later introduced into a quantum setting by Knill and Laflamme [KL96] and Gottesman [Got97].

Definition 2.5.

Let $Q_{out}$ be an $[[n,k]]_{q^{m}}$ ‘outer’ stabilizer code, and $Q_{in}$ be a $[[n^{\prime},m]]_{q}$ ‘inner’ stabilizer code. Then the quantum code concatenation $Q_{out}\diamond Q_{in}$ is the $[[n\cdot n^{\prime},k\cdot m]]_{q}$ stabilizer code defined by encoding any message $\ket{\psi}\in\mathbb{C}_{q^{m}}^{\otimes k}$ as

\mathsf{Enc}_{\diamond}(\psi)=\bigg{(}\bigotimes_{i=1}^{n}\mathsf{Enc}_{in}\bigg{)}\mathsf{Enc}_{out}(\ket{\psi})

(10)

That is, each qudit of the outer code is encoded into the inner code. Much like the case of code composition, the stabilizer generators of a concatenated quantum code can be expressed in terms of the stabilizers of the inner code $Q_{in}$ , and the encoding of stabilizers of the outer code $Q_{out}$ .

Fact 2.2.

If $\{S^{out}_{i}\}_{i\in[r_{out}]}\subset\mathcal{P}_{q^{m}}^{n}$ and $\{S^{in}_{j}\}_{j\in[r_{in}]}\subset\mathcal{P}_{q}^{n^{\prime}}$ are the stabilizer generators of $Q_{out},Q_{in}$ respectively, then the stabilizer group of $Q_{\diamond}$ is generated by the following set of operators:

\bigg{\{}\big{(}\bigotimes_{i=1}^{n}\mathsf{Enc}_{in}\big{)}S^{out}_{j}\big{(}\bigotimes_{i=1}^{n}\mathsf{Enc}_{in}^{\dagger}\big{)}\bigg{\}}_{j\in[r_{out}]}\bigcup\bigg{\{}\big{(}S^{in}_{j}\big{)}_{i}\otimes\mathbb{I}^{\otimes[n]\setminus\{i\}}_{q^{n^{\prime}}}\bigg{\}}_{i\in[n],j\in[r_{in}]}\subset\mathcal{P}_{q}^{n\cdot n^{\prime}}

(11)

where the second set above corresponds to applying the $j$ th stabilizer of $S_{in}$ to the $i$ th inner block of the concatenated code.

CSS codes have a particular nicely behaved form of concatenation. Recall that concatenation requires specifying an encoding function for the inner code; we now describe how this can be done while preserving the CSS structure. Let $Q^{\text{out}}=\text{CSS}(C_{1}^{\text{out}},C_{2}^{\text{out}})$ and $Q^{\text{in}}=\text{CSS}(C_{1}^{\text{in}},C_{2}^{\text{in}})$ be $[[n_{\text{out}},k_{\text{out}}]]_{q_{\text{out}}}$ and $[[n_{\text{in}},k_{\text{in}}]]_{q_{\text{out}}}$ CSS codes respectively. Assume that $q_{\text{out}}=q_{\text{in}}^{k_{\text{in}}}$ , and that all four classical codes $C_{1}^{\text{out}},C_{2}^{\text{out}},C_{1}^{\text{in}},C_{2}^{\text{in}}$ are $\mathbb{F}_{q}$ -linear for some $q$ . Letting $q_{\text{in}}=q^{m}$ , so that $q_{\text{out}}=q^{mk_{\text{in}}}$ , then observe that $(\mathbb{F}_{q}^{mk_{\text{in}}},\mathbb{F}_{q}^{mk_{\text{in}}})$ and $(C_{1}^{\text{in}}/{C_{2}^{\text{in}}}^{\perp},C_{2}^{\text{in}}/{C_{1}^{\text{in}}}^{\perp})$ are both dual pairs of $mk_{\text{in}}$ -dimensional vector spaces over $\mathbb{F}_{q}$ . Thus there exists a pair of $\mathbb{F}_{q}$ -linear isomorphisms

(\mathsf{Enc}_{1}^{\text{in}}:\mathbb{F}_{q}^{mk_{\text{in}}}\rightarrow C_{1}^{\text{in}}/{C_{2}^{\text{in}}}^{\perp},\;\mathsf{Enc}_{2}^{\text{in}}:\mathbb{F}_{q}^{mk_{\text{in}}}\rightarrow C_{2}^{\text{in}}/{C_{1}^{\text{in}}}^{\perp})

that are duality-preserving in the sense that $\langle x,y\rangle=\langle\mathsf{Enc}_{1}^{\text{in}}(x),\mathsf{Enc}_{2}^{\text{in}}(y)\rangle$ for all $x,y$ .

Claim 2.3.

Let $Q^{\text{out}}=\text{CSS}(C_{1}^{\text{out}},C_{2}^{\text{out}})$ and $Q^{\text{in}}=\text{CSS}(C_{1}^{\text{in}},C_{2}^{\text{in}})$ be as above. Then there is a well defined $[[n_{\text{out}}n_{\text{in}},k_{\text{out}}k_{\text{in}}]]_{q_{\text{in}}}$ CSS concatenation given by

Q^{\text{out}}\diamond Q^{\text{in}}=\text{CSS}(C_{1}^{\text{out}}\diamond(C_{1}^{\text{in}}/{C_{2}^{\text{in}}}^{\perp}),\;C_{2}^{\text{out}}\diamond(C_{2}^{\text{in}}/{C_{1}^{\text{in}}}^{\perp})),

where $C_{1}^{\text{out}}\diamond(C_{1}^{\text{in}}/{C_{2}^{\text{in}}}^{\perp})$ is the union of all the cosets in $(\mathsf{Enc}_{1}^{\text{in}})^{\oplus n_{\text{out}}}(C_{1}^{\text{out}})\subseteq(C_{1}^{\text{in}})^{\oplus n_{\text{out}}}/({C_{2}^{\text{in}}}^{\perp})^{\oplus n_{\text{out}}}$ , and $C_{2}^{\text{out}}\diamond(C_{2}^{\text{in}}/{C_{1}^{\text{in}}}^{\perp})$ is the union of all the cosets in $(\mathsf{Enc}_{2}^{\text{in}})^{\oplus n_{\text{out}}}(C_{2}^{\text{out}})\subseteq(C_{2}^{\text{in}})^{\oplus n_{\text{out}}}/({C_{1}^{\text{in}}}^{\perp})^{\oplus n_{\text{out}}}$ .

Proof.

Let $C_{1}=C_{1}^{\text{out}}\diamond(C_{1}^{\text{in}}/{C_{2}^{\text{in}}}^{\perp})$ and $C_{2}=C_{2}^{\text{out}}\diamond(C_{2}^{\text{in}}/{C_{1}^{\text{in}}}^{\perp})$ . It suffices to show that

	$\displaystyle C_{1}^{\perp}$	$\displaystyle={C_{1}^{\text{out}}}^{\perp}\diamond(C_{2}^{\text{in}}/{C_{1}^{\text{in}}}^{\perp})$
	$\displaystyle C_{2}^{\perp}$	$\displaystyle={C_{2}^{\text{out}}}^{\perp}\diamond(C_{1}^{\text{in}}/{C_{2}^{\text{in}}}^{\perp}).$

We will show the first equality above; the proof of the second is analogous. By definition, if $c\in{C_{1}^{\text{out}}}^{\perp}\diamond(C_{2}^{\text{in}}/{C_{1}^{\text{in}}}^{\perp})$ , then for all $c^{\prime}\in C_{1}$ ,

\langle c^{\prime},c\rangle=\langle((\mathsf{Enc}_{1}^{\text{in}})^{-1})^{\oplus n_{\text{out}}}(c^{\prime}),((\mathsf{Enc}_{2}^{\text{in}})^{-1})^{\oplus n_{\text{out}}}(c)\rangle=0,

so $c\in C_{1}^{\perp}$ . For the converse, assume that $c\in C_{1}^{\perp}$ . Because $C_{1}\supseteq({C_{2}^{\text{in}}}^{\perp})^{\oplus n_{\text{out}}}$ , we must have $C_{1}^{\perp}\subseteq({C_{2}^{\text{in}}})^{\oplus n_{\text{out}}}$ . Thus $((\mathsf{Enc}_{2}^{\text{in}})^{-1})^{\oplus n_{\text{out}}}(c)$ is well defined, so for all $c^{\prime}\in C_{1}$ ,

\langle((\mathsf{Enc}_{1}^{\text{in}})^{-1})^{\oplus n_{\text{out}}}(c^{\prime}),((\mathsf{Enc}_{2}^{\text{in}})^{-1})^{\oplus n_{\text{out}}}(c)\rangle=\langle c^{\prime},c\rangle=0.

Therefore $c$ belongs to the (coset specified by the) encoding under $(\mathsf{Enc}_{2}^{\text{in}})^{\oplus n_{\text{out}}}$ of a vector that is orthogonal to all elements of $C_{1}$ , that is, $c\in(\mathsf{Enc}_{2}^{\text{in}})^{\oplus n_{\text{out}}}({C_{1}^{\text{out}}}^{\perp})={C_{1}^{\text{out}}}^{\perp}\diamond(C_{2}^{\text{in}}/{C_{1}^{\text{in}}}^{\perp})$ . ∎

3 Quantum List Decodable Codes

Let $Q$ be a stabilizer code of distance $d$ , defined with respect to a basis of operators on single-qudits $\mathcal{P}_{q}$ . Consider any adversarial quantum channel $\mathcal{A}$ acting on a (unknown) set of $\tau\cdot n$ qudits of a code-state $\ket{\psi}$ of $Q$ . If the support of the attack has size $\tau\cdot n<d$ , then, by measuring the syndrome of $Q$ , one collapses $\mathcal{A}(\psi)$ into a mixture of single errors in the basis:

\mathcal{A}(\psi)\rightarrow\sum_{s}\ket{s}\bra{s}\otimes\Pi_{s}\mathcal{A}(\psi)\Pi_{s}=\sum_{s}|c_{s}|^{2}\ket{s}\bra{s}\otimes\sigma_{s}\ket{\psi}\bra{\psi}\sigma_{s}^{\dagger}

(12)

Informally, this occurs since if any two distinct $n$ -qudit operators $\sigma,\sigma^{\prime}\in\mathcal{P}_{q}^{n}$ had the same small support $<d$ and the same syndrome, then their product $\sigma^{\dagger}\sigma^{\prime}$ must be a stabilizer of $Q$ . But if $\sigma^{\dagger}\sigma^{\prime}$ is a stabilizer, then $\sigma,\sigma^{\prime}$ corrupt code-states in essentially the same way: For any $\ket{\psi}\in Q$ , $\sigma\ket{\psi}=\eta\sigma^{\prime}\ket{\psi}$ for some phase $\eta\in\mathbb{C}$ .

In this fashion, to decode $\mathcal{A}(\psi)$ it suffices to identify $\sigma_{s}$ from the syndrome measurement $s$ . When the support of $\mathcal{A}$ is $\leq d/2$ , then there in fact exists a single $\sigma$ (up to a stabilizer of $Q$ ) which matches the syndrome, and one can unique-decode. When the support of $\mathcal{A}$ is larger, all bets are off: In this sense, the notion of list-decoding for stabilizer codes we consider is simply the number of operators which match the measured syndrome $s$ - and are all distinct up to a stabilizer of $Q$ .

Definition 3.1.

If $\mathcal{S}\subset\mathcal{P}_{q}^{n}$ is a stabilizer group, then any pair of operators $O,O^{\prime}\in\mathcal{P}_{q}^{n}$ is said to be $S$ -stabilizer equivalent if $O=O^{\prime}S$ for some $S\in\mathcal{S}$ , and stabilizer-distinct otherwise.

In other words, $O$ is in the coset $O^{\prime}\mathcal{S}$ . When the set of stabilizers is implicit, we simply refer to the pair of operators as ‘stabilizer-equivalent’ or ‘stabilizer-distinct’. We note that this relation defines equivalence classes over the Pauli group $\mathcal{P}_{q}^{n}$ , since if $A,B$ and $B,C$ are both stabilizer equivalent, then so are $A$ and $C$ . More importantly, if $Q$ is the quantum code stabilized by $\mathcal{S}$ , then stabilizer-equivalent operators acting on the code-space give rise to the same state:

O\ket{\psi}=O^{\prime}S\ket{\psi}=\eta_{S}O^{\prime}\ket{\psi},\text{ for all }\ket{\psi}\in Q,

(13)

where $\eta_{S}\in\mathbb{C}$ is some global phase. Moreover, given a description of the stabilizer generators and $O,O^{\prime}$ , one can test stabilizer-equivalence efficiently via row reduction.

Equipped with this notion, we discuss the following definition of list decoding for stabilizer codes. Conceptually, after measuring the syndrome of the quantum code, we consider enumerating all the operators $E_{1},E_{2}\cdots$ in a given class of errors $\mathcal{E}$ which agree with the syndrome measurement. However, note that many of these operators could be stabilizer-equivalent, corresponding essentially to the same state. The definition we study filters out this degeneracy, by considering the size of any list $\mathcal{L}_{s}$ of stabilizer-distinct operators which agrees with $s$ .

Definition 3.2.

Let $Q$ be an $[[n,k,d]]_{q}$ stabilizer QECC with stabilizer group $\mathcal{S}$ , and let $\mathcal{E}\subset\mathcal{P}_{q}^{n}$ be a set of errors. $Q$ is said to be $\ell$ -QLD (Quantum List Decodable) for $\mathcal{E}$ if, for every error $E\in\mathcal{E}$ , there exists at most $\ell$ stabilizer-distinct operators which agree with the syndrome $s$ of $E$ .

Of particular attention is the class of qudit Pauli errors $\mathcal{E}=\mathcal{P}_{q,\tau}^{n}$ of bounded weight $\tau\cdot n$ , and we refer to a quantum code as $(\tau,\ell)$ -QLD if it is an $\ell$ -QLD for $\mathcal{P}_{q,\tau}^{n}$ .

The immediate reason that this particular definition of list-decoding for quantum codes is useful is that the list $\mathcal{L}_{s}$ can be viewed as a list of “correction operators.” For instance, if $\ket{\psi}\in Q$ is a code state of an $\ell$ -QLD $Q$ , and an adversary corrupts it with an error $E\in\mathcal{E}$ of syndrome $s$ , let the list of operators $F_{1},\cdots,F_{\ell}\subset\mathcal{E}$ be those guaranteed by Definition 3.2. We note that by applying $F_{1}^{\dagger}$ on the corrupted code state $E\ket{\psi}$ , we return it to the code space $Q$ : $F_{1}^{\dagger}E\ket{\psi}\in Q$ . In fact, we can produce a next candidate code state by applying $(F_{2}^{\dagger}F_{1})F_{1}^{\dagger}E\ket{\psi}=F_{2}^{\dagger}E\ket{\psi}\in Q$ , and so on. Naturally, we won’t know which code state we are in, but by definition at least one correction $F_{i}^{\dagger}E\ket{\psi}\propto\ket{\psi}$ recovers the original state.

This description of list-decoding in terms of the syndrome measurements can alternatively be characterized through the normalizers and logical operators on the stabilizer code.

Claim 3.1.

If $Q$ is a stabilizer code with stabilizer group $S(Q)$ and normalizer group $N(Q)$ , then for any $E\in\mathcal{E}$ of syndrome $s$ , any list $\mathcal{L}_{s}$ of operators in $\mathcal{E}$ which agrees with $s$ satisfies

\mathcal{L}_{s}\subset\big{\{}EN:N\in N(Q)\}\cap\mathcal{E}

(14)

Proof.

If two operators $A,E$ have the same syndrome, then $A^{\dagger}E$ has null syndrome vector and thus $A^{\dagger}E\in N(Q)$ . In this manner, $A$ can be written as the product of $E$ and an element of the normalizer. ∎

While the characterization above is a structural constraint on the stabilizers and normalizers of the quantum error correcting code, perhaps its main advantage is that one can cast the list-decoding task as an entirely classical process, without any modification to the encoding of the quantum code. As we will see shortly, this description allows us to draw a connection between CSS codes which are QLD and classical codes which are (classically) LD. Beforehand, we need to describe what it means to efficiently list-decode these stabilizer codes.

We refer to an $[[n,k,d]]_{q}$ $\ell$ -QLD code $Q$ as efficiently list decodable for $\mathcal{E}$ if, given the syndrome $s$ , one can produce in time polynomial in $n,\log q,l$ a classical description of a list $\mathcal{L}_{s}\subset\mathcal{P}_{q}^{n}$ of $\leq\ell$ operators with the following stipulations: $\mathcal{L}_{s}$ contains only stabilizer distinct operators with syndrome $s$ ; and moreover, for each element of $\mathcal{E}$ of syndrome $s$ , there is an operator in $\mathcal{L}_{s}$ stabilizer-equivalent to it. That is, the list-decoding algorithm is allowed to output extraneous list elements that are not stabilizer-equivalent to any error in $\mathcal{E}$ , as long as they still act as corrections, and the overall list size is $\leq\ell$ . We emphasize that these “unpruned” lists arise because it can be intractable to determine if a given Pauli operator is stabilizer-equivalent to an element of $\mathcal{E}$ .

The main contribution of this section is a recipe to construct quantum list-decodable codes from classical list-decodable codes. For conciseness and to fit our applications, we present a discussion for CSS codes based on the Galois-qudit construction, which we review in Theorem 2.1.

Definition 3.3.

Given an $\mathbb{F}_{q}$ -linear classical code $C\subseteq(\mathbb{F}_{q}^{m})^{n}$ and a subcode $C^{\prime}\subseteq C$ , let the quotient $C/C^{\prime}$ be $(\tau,L)$ list-decodable if for every $x\in(\mathbb{F}_{q}^{m})^{n}$ , there exist at most $L$ cosets in $C/C^{\prime}$ that intersect the Hamming ball $B_{\tau n}(x)$ of radius $\tau n$ centered at $x$ .

We say that $C/C^{\prime}$ is efficiently $(\tau,L)$ list-decodable if there exists a $\poly(nm\log q)$ time algorithm that outputs a list consisting of a representative of each coset in $C/C^{\prime}$ that intersects $B_{\tau n}(x)$ .

By definition if $C$ is (efficiently) $(\tau,L)$ list-decodable then so is $C/C^{\prime}$ , as we may remove redundant list elements differing by an element of $C^{\prime}$ using row reduction.

Theorem 3.2.

Let $Q=\text{CSS}(C_{1},C_{2})$ be a CSS codes. If $C_{1}/C_{2}^{\perp}$ and $C_{2}/C_{1}^{\perp}$ are both (efficiently) $(\tau,L)$ list-decodable, then $Q$ is (efficiently) $(\tau,L^{2})$ list-decodable.

Proof.

Fix an error $E_{\textbf{a},\textbf{b}}$ on the CSS code, of syndrome $s=(s_{x},s_{z})$ . The normalizers of the CSS code are the operators $E_{\textbf{c}_{1},\textbf{c}_{2}}$ , $c_{1}\in C_{1},c_{2}\in C_{2}$ . Recall from the definition in Theorem 2.2 that we implicitly view $x\in(\mathbb{F}_{q}^{m})^{n}$ as an element $\textbf{x}\in\mathbb{F}_{q}^{nm}$ . From the previous claim, any list $\mathcal{L}_{s}$ is contained in the set of operators $F=E_{\textbf{a'},\textbf{b'}}$ where $a-a^{\prime}\in C_{1}$ and $b-b^{\prime}\in C_{2}$ . Furthermore, $E_{\textbf{a}^{\prime},\textbf{b}^{\prime}}$ and $E_{\textbf{a}^{\prime\prime},\textbf{b}^{\prime\prime}}$ are stabilizer equivalent if and only if $a^{\prime}-a^{\prime\prime}\in C_{2}^{\perp}$ and $b^{\prime}-b^{\prime\prime}\in C_{1}^{\perp}$ . Because $C_{1}/C_{2}^{\perp}$ is $(\tau,L)$ -LD, the number of cosets $a^{\prime}+C_{2}^{\perp}$ with $|a^{\prime}|\leq\tau\cdot n$ and $a-a^{\prime}\in C_{1}$ is $\leq L$ . Similarly, because $C_{2}/C_{1}^{\perp}$ is $(\tau,L)$ -LD, the number of cosets $b^{\prime}+C_{1}^{\perp}$ with $|b^{\prime}|\leq\tau\cdot n$ and $b-b^{\prime}\in C_{1}$ is $\leq L$ . It follows that the total number of pairs $(a^{\prime},b^{\prime})$ in the list is at most $\leq L^{2}$ .

It remains to be shown that efficiency of the classical list-decoding for $C_{1}/C_{2}^{\perp}$ and $C_{2}/C_{1}^{\perp}$ implies efficiency for the quantum list-decoding of $Q$ . Let $E^{\prime}=E_{e_{x},e_{z}}$ be any Pauli operator with the syndrome $s=(s_{x},s_{z})$ , so that $s_{x}$ and $s_{z}$ are the parity check syndromes of $e_{x}$ and $e_{z}$ for $C_{1}$ and $C_{2}$ respectively. One can find such a pair $e_{x},e_{z}\in(\mathbb{F}_{q}^{m})^{n}$ by finding any solution to the underlying linear system in polynomial time via Gaussian elimination (note that here, we don’t restrict $e_{x},e_{z}$ to be low weight). We call the classical list decoding algorithm for $C_{1}$ on $e_{x}$ , and for $C_{2}$ on $e_{z}$ , obtaining lists $a_{1}\cdots a_{L}$ and $b_{1}\cdots b_{L}\in(\mathbb{F}_{q}^{m})^{n}$ of classical errors of weight $\leq\tau n$ . We claim that any stabilizer distinct operator of weight $\leq\tau n$ that matches $s$ is stabilizer equivalent to an operator $E_{a_{i},b_{j}}$ , $i,j\in[L]$ , output by this algorithm. Indeed, for every operator $E_{a^{\prime},b^{\prime}}$ of weight $\leq\tau n$ and of syndrome $s$ , then $a^{\prime}$ and $b^{\prime}$ both have weight $\leq\tau n$ and have parity check syndromes $s_{x}$ and $s_{z}$ for $C_{1}$ and $C_{2}$ respectively, so by definition the list-decoding algorithm must output an operator that is stabilizer-equivalent to $E_{a^{\prime},b^{\prime}}$ . ∎

3.1 Explicit Constructions and Folded Quantum Codes

In this subsection we discuss explicit constructions of quantum list-decodable codes from classical list decodable codes, using Theorem 3.2. We use the well known classical Reed-Solomon codes, and the Folded Reed-Solomon codes from the breakthrough result of [GR08], to construct quantum codes which are efficiently list decodable up to the quantum Singleton bound (Theorem 3.8). While in principle we could approach the quantum Singleton bound using even random CSS codes, unfortunately these wouldn’t be explicit, nor efficiently decodable. Thus for conciseness, we dedicate Appendix A to a collection of their properties which we later use in our concatenated constructions. Before diving into the explicit constructions, let us briefly overview the necessary background on these classical codes and related quantum codes.

Definition 3.4 (Generalized Reed-Solomon Codes).

Let $q$ be a prime power. Fix $k<n<q$ , a primitive element $\gamma$ of $\mathbb{F}^{*}_{q}$ , and a set of ‘multipliers’ $U=(u_{0}\cdots u_{n-1})\subset\mathbb{F}^{*}_{q}$ . The degree $k-1$ GRS code is the set

GRS_{n,k,q}(\gamma,U)=\bigg{\{}(u_{0}f(1),\cdots,u_{n-1}f(\gamma^{n-1})):f\in\mathbb{F}_{q}[X]/(x^{k}-1)\bigg{\}}

(15)

Each codeword of a Reed-Solomon code corresponds to the evaluation of a distinct polynomial over $\mathbb{F}_{q}$ . The codewords of the Generalized RS code defined above, are RS codewords multiplied element-wise by scalars. The following properties don’t depend on the choice of primitive $\gamma$ or subset $U$ of $\mathbb{F}^{*}_{q}$ :

Fact 3.1.

$GRS_{n,k,q}(\gamma,U)$ is a $[n,k,n-k+1]_{q}$ code.

Fact 3.2.

The dual code $(GRS_{n,k,q}(\gamma,U))^{\perp}=GRS_{n,n-k,q}(\gamma,V)$ , for certain choice of multipliers $V$ . When $u_{i}=1,\forall i\in[n]$ , $V=\{1,\gamma,\cdots,\gamma^{n-1}\}$ .

Lemma 3.3 ([GS98]).

$GRS_{n,R\cdot n,q}(\gamma,U)$ is efficiently $(1-\sqrt{R}-\varepsilon,n^{O(1)})$ -LD.

The Quantum GRS codes, or Galois-qudit RS codes [ABO08, JX14], are quantum codes based on the Galois-Qudit CSS construction of the classical codes above. They are a class of quantum codes which meets the quantum Singleton bound, but at the cost of a large local qudit dimension:

Theorem 3.4 (Quantum GRS codes [LXW08]).

Fix a constant $R\in(0,1)$ . Let $C_{2}^{\perp}\subset C_{1}\subset\mathbb{F}_{q}^{n}$ be two GRS codes of block length $n<q$ and dimension $k_{2}=n(1-R)/2,k_{1}=n(1+R)/2$ respectively, with the same evaluation points $S=\{1,\gamma,\cdots,\gamma^{n-1}\}\subset\mathbb{F}_{q}$ . The Quantum GRS code $Q_{RS}=$ CSS $(C_{1},C_{2})$ is a $[[n,Rn,(1-R)/2\cdot n]]_{q}$ QECC.

One can interpret the QGRS encoding as a superposition of polynomial evaluations, where the high degree coefficients are defined by the message. By combining our insights in the previous section with the result by [GS98], we obtain a quantum adaptation of a well known family of classically list decodable codes:

Corollary 3.5.

The Quantum GRS codes of Theorem 3.4 of rate $R$ and block-length $n$ are $(1-\sqrt{\frac{1+R}{2}},n^{O(1)})$ -QLD. For small $R$ , this approaches radius $\approx.29-1.4\cdot R$ .

Proof.

Note that the classical codes $C_{1},C_{2}$ in Theorem 3.4 both have rate $R^{\prime}=(1+R)/2$ , and are efficiently LD up to a radius $1-\sqrt{R^{\prime}}$ [GS98]. Theorem 3.2 concludes the proof. ∎

In their seminal work Guruswami and Rudra [GR08] introduced Folded Reed-Solomon codes, which are efficiently list decodable up to almost the Singleton bound. Informally, they are defined by ‘bundling’ or ‘folding’ together groups of $m$ consecutive symbols of the RS code, into a symbol of a code on a larger alphabet.

Definition 3.5 ( $m$ -folded codes).

If $C\subset\mathbb{F}_{q}^{n}$ is an $[n,k]_{q}$ linear code, then the $m$ -folded code $C^{(m)}\subset(\mathbb{F}_{q}^{m})^{n/m}$ is an $[n/m,k/m]_{q^{m}}$ $\mathbb{F}_{q}$ -linear code defined by the codewords

C^{(m)}=\bigg{\{}(c_{1},\cdots,c_{m}),\cdots,(c_{n-m+1},\cdots,c_{n})):c=(c_{1},\cdots,c_{n})\in C\bigg{\}}

(16)

Indeed, note that the code itself hasn’t truly changed, we are simply viewing it as a code over a larger alphabet. Moreover, observe $(C^{(m)})^{\perp}=(C^{\perp})^{(m)}$ .

Definition 3.6 ( $m$ -folded Reed-Solomon codes [GR08]).

Fix a primitive element $\gamma$ of $\mathbb{F}^{*}_{q}$ , integers $n,m,k$ where $k<n\leq q-1$ and $m$ divides $n$ . The $m$ -folded RS code $FRS_{n,k,q}^{m}$ is an $[n/m,k/m,d/m]_{q^{m}}$ $\mathbb{F}_{q}$ -linear code defined over alphabet $\mathbb{F}_{q}^{m}$ which encodes a polynomial $f\in F_{q}[x]$ of degree $k-1$ as

\begin{pmatrix}\begin{bmatrix}f(1)\\ f(\gamma)\\ \vdots\\ f(\gamma^{m-1})\end{bmatrix},\begin{bmatrix}f(\gamma^{m})\\ f(\gamma^{m+1})\\ \vdots\\ f(\gamma^{2m-1})\end{bmatrix},\cdots,\begin{bmatrix}f(\gamma^{n-m})\\ f(\gamma^{n-m+1})\\ \vdots\\ f(\gamma^{n-1})\end{bmatrix}\end{pmatrix}

(17)

Theorem 3.6 ([GR08]).

For any $q>n$ , there exists a choice of $m=O(1/\gamma^{2})$ such that the $m$ -folded RS code of rate $R$ is efficiently $(1-R-\gamma,q^{O(1/\gamma)})$ -LD.

By multiplying element-wise the RS codes above by scalars $u_{i}\in\mathbb{F}_{q}^{*},i\in[n]$ , one defines Folded Generalized RS codes. Our starting point for efficiently list decodable quantum codes is an analogous bundling for the physical qudits of any stabilizer code.

Definition 3.7.

Let $S_{1},\cdots,S_{r}\in\mathcal{P}_{q}^{n}$ define a set of generators for an $[[n,k]]_{q}$ stabilizer code $Q\subset\mathbb{C}_{q}^{\otimes n}$ . Then the $m$ -folded quantum code $Q^{(m)}\subset(\mathbb{C}_{q}^{m})^{\otimes n/m}$ is the $[[n/m,k/m]]_{q^{m}}$ stabilizer code defined by the stabilizer generators $S^{(m)}_{1}\cdots S^{(m)}_{r}$ , where

S^{(m)}_{i}=\bigotimes_{j\in[n/m]}\big{(}\otimes_{l\in[m]}S_{i,j\cdot m+l}\big{)}

(18)

where each generator $S_{i}=\otimes_{j\in[n]}S_{ij}$ is expressed as a tensor product of operators acting on $\mathbb{C}_{q}$ .

Analogously to the classical construction, we are folding the physical qudits together, and we view the stabilizers as operators acting on a larger local dimension. We emphasize however that they are the same stabilizers, and the syndromes of operators acting on the code are measured in the same way as before. The key distinction is that now the notion of the ‘weight’ of an operator $E$ acting on $Q^{(m)}$ , is the number of distinct ‘bundles’ that $E$ acts non-trivially on. A simple claim allows us to use the list decoding algorithms of folded classical codes on folded quantum codes, when $Q$ is a CSS code.

Claim 3.7.

If $Q$ is the Galois-qudit CSS code of two linear classical codes $C_{1},C_{2}\subset\mathbb{F}_{q}^{n}$ , then $Q^{(m)}$ is the vector-space CSS code of the two $\mathbb{F}_{q}$ -linear folded classical codes $C_{1}^{(m)},C_{2}^{(m)}$ .

See the definitions in Theorem 2.1 and Theorem 2.2 for the distinctions between these CSS constructions.

Proof.

As defined in Theorem 2.2, the vector space CSS code of $C_{1}^{(m)},C_{2}^{(m)}$ is the subspace of $(\mathbb{C}_{q}^{\otimes m})^{\otimes n/m}$ stabilized by the operators $E_{\textbf{a},\textbf{b}}$ , where $a\in(C_{1}^{(m)})^{\perp},b\in(C_{2}^{(m)})^{\perp}\subset(\mathbb{F}_{q}^{m})^{n/m}$ are viewed as elements $\textbf{a},\textbf{b}$ of $\mathbb{F}_{q}^{n}$ . Since $a\in(C_{1}^{(m)})^{\perp}$ as an element of $\mathbb{F}_{q}^{n}$ is the ‘unfolded’ element $\textbf{a}\in C_{1}^{\perp}$ , we arrive at precisely the definition of $Q^{(m)}$ . ∎

Equipped with this notion of folding, we can now consider folding the Quantum GRS codes of Theorem 3.4.

Definition 3.8 (Folded Quantum Reed-Solomon Code).

For $0<R<1$ , fix a primitive element $\gamma\in\mathbb{F}_{q}^{*}$ and integer block length $n<q-1$ , and define integers dimension $d=n-(1+R)n/2$ and $m$ with $m|n$ . The $m$ -folded Quantum RS code is an $[[n/m,R\cdot n/m,d/m]]_{q^{m}}$ quantum error correcting code defined over qudits of local dimension $q^{m}$ , which encodes a computational basis state $|f\rangle$ , $f\in\mathbb{F}_{q}^{Rn}$ through the superposition $Enc(|f\rangle)=|\bar{f}\rangle$ :

\displaystyle\frac{1}{q^{d/2}}\sum_{deg(f^{\prime})\leq d}\bigg{|}\begin{bmatrix}(f+f^{\prime})(1)\\ (f+f^{\prime})(\gamma)\\ \vdots\\ (f+f^{\prime})(\gamma^{m-1})\end{bmatrix}\bigg{\rangle}\otimes\cdots\otimes\bigg{|}\begin{bmatrix}(f+f^{\prime})(\gamma^{n-m})\\ (f+f^{\prime})(\gamma^{n-m+1})\\ \vdots\\ (f+f^{\prime})(\gamma^{n-1})\end{bmatrix}\bigg{\rangle}

(19)

Where in the above $(f+f^{\prime})(x)$ corresponds to the evaluation at $x\in\mathbb{F}_{q}$ of the polynomial defined by $f^{\prime}$ as the low degree coefficients $<d$ , and $f$ as the high degree coefficients within $d$ and $d+R\cdot n$ . The bracket notation corresponds to the tensor product state in $\mathbb{C}_{q}^{\otimes m}$

\bigg{|}\begin{bmatrix}(f+f^{\prime})(1)\\ (f+f^{\prime})(\gamma)\\ \vdots\\ (f+f^{\prime})(\gamma^{m-1})\end{bmatrix}\bigg{\rangle}=\otimes_{i}^{m-1}\ket{(f+f^{\prime})(\gamma^{i})}

(20)

The main theorem of this section is that these $m$ -folded QRS codes are QLD up to essentially the distance of the quantum code.

Theorem 3.8.

The FQRS of Definition 3.8 is $(\frac{1-R}{2}-\gamma,q^{O(1/\gamma)})$ -QLD for a choice of $m=O(1/\gamma^{2})$ .

Proof.

From 3.7, we understand the FQRS codes as the vector space CSS codes (Theorem 2.2) of two classical folded GRS codes. These are classically $(\frac{1-R}{2}-\gamma,q^{O(1/\gamma)})$ -LD from Theorem 3.6, [GR08]. Finally, since the folded GRS codes are $\mathbb{F}_{q}$ -linear, from Theorem 3.2 we conclude the FQRS codes are $(\frac{1-R}{2}-\gamma,q^{O(1/\gamma)})$ -QLD as well. ∎

4 Approximate Quantum Error Correction

In this section we construct approximate quantum error correcting codes (AQECCs) that approach the quantum Singleton bound. In Section 4.1 we construct private AQECCs — which use a private classical side-channel — from quantum list decodable codes and purity testing codes. In Section 4.2 we show how to use a classical robust secret sharing scheme to remove the need for the classical side-channel, at the cost of slightly increasing the alphabet size.

4.1 Private AQEC from Quantum List Decoding and Purity Testing

Recall our definition of a private AQECC, where the sender and receiver have access to a private classical side-channel.

Definition 4.1 (Definition 1.5, restatement).

A set of pairs $\{(\mathsf{Enc}_{k},\mathsf{Dec}_{k})\}_{k\in K}$ of quantum channels is said to be a $(\delta,\varepsilon)$ -private AQECC with keys $K$ if for all adversarial channels $\mathcal{A}$ of weight $\delta\cdot n$ ,

\norm{\mathbb{E}_{k\leftarrow K}[\mathsf{Dec}_{k}\circ\mathcal{A}\circ\mathsf{Enc}_{k}]-\mathbb{I}}_{\diamond}\leq\varepsilon.

We now describe a construction of private AQECCs from list decodable quantum codes (QLDs) and purity testing codes (PTCs). Recall that a $(\delta,L)$ -QLD stabilizer code produces a list of possible corrections of size $L$ , given any codestate that has been adversarially corrupted on up to a $\delta$ fraction of symbols (see Definition 3.2). Roughly, an $\varepsilon$ -PTC detects any fixed Pauli error with probability $1-\varepsilon$ (see Definition 1.4).

Given an $[[n,n_{PTC}]]_{q}$ QLD $Q_{LD}$ and $[[n_{PTC},m]]_{q}$ PTC $\{Q_{k}\}$ , our private AQECC $\{Q_{LD}\circ Q_{k}\}$ is defined by channels $\mathsf{Enc}_{k}$ that encode a message state $\rho$ into $Q_{k}$ and then into $Q_{LD}$ :

\mathsf{Enc}_{k}(\rho)=\mathsf{Enc}_{Q_{LD}}\circ\mathsf{Enc}_{Q_{k}}(\rho).

(21)

To decode the quantum code composition $Q_{LD}\circ Q_{k}$ ⁶⁶6See Definition 2.4 and 2.2 for the properties of the composition of quanutm codes., we use Algorithm 1.

Input: A corrupted code-state

\mathcal{A}(\mathsf{Enc}_{k}(\rho))

1 Measure the syndromes

s_{QLD}

Q_{LD}

and

s_{PTC}

Q_{k}

;

2 Apply list decodability to

s_{QLD}

to obtain a list

E_{1},\dots,E_{L}

of potential errors;

3 Compute the

Q_{k}

-syndromes

s_{1},\dots,s_{L}

E_{1},\dots,E_{L}

, and choose any

i\in[L]

such that

s_{i}=s_{PTC}

;

4 Apply

(E_{i}\circ\mathsf{Enc}_{k})^{\dagger}

to the corrupted code-state and output the resulting message;

Algorithm 1

\mathsf{Dec}_{k}

for

Q_{LD}\circ Q_{k}

The main result of this subsection is the following lemma, which states that the composition above forms a private AQECC.

Lemma 4.1.

Let $\{Q_{k}\}$ be an $\varepsilon$ -PTC, where each $Q_{k}$ is an $[[n_{PTC},m]]_{q}$ stabilizer code, and let $Q_{LD}$ be a $[[n,n_{PTC},d]]_{q}$ stabilizer code which is $(\delta,L)$ -QLD and has distance $d>\delta\cdot n$ . Then $Q_{LD}\circ Q_{k}$ is an ensemble of $[[n,m]]_{q}$ stabilizer codes, and a $(\delta,2\cdot L\cdot\varepsilon)$ private AQECC.

We instantiate Lemma 4.1 with the family of $[[n,R\cdot n]]_{q}$ , $((1-R-\gamma)/2,n^{O_{\gamma}(1)})$ -QLD codes on alphabets of size $q=2^{\Theta(1/\gamma^{5})}$ guaranteed by Theorem 6.1 or Theorem B.7, together with a family of particularly randomness-efficient PTC’s from the work of [BCG⁺02].

Theorem 4.2 ([BCG⁺02]).

For every prime power $q$ and every $\lambda,n_{PTC}\in\mathbb{N}$ with $\lambda|n_{PTC}$ , there exists a stabilizer $\varepsilon$ -PTC $\{Q_{k}\}$ on qudits of local dimension $q$ and key size $\lambda\cdot\log q$ bits, encoding $n_{PTC}-\lambda$ qudits into $n_{PTC}$ qudits, where $\varepsilon\leq 2\cdot n_{PTC}\cdot q^{-\lambda}/\lambda$ .

With $\lambda=n/\log q$ and $n_{PTC}=(R+\gamma/2)\cdot n$ , we obtain:

Corollary 4.3.

For any $\gamma>0$ and $R\in(0,1)$ , there exists a family of $((1-R-\gamma)/2,2^{-\Omega(n)})$ private AQECCs of rate $R$ , block length $n$ , key size $n$ bits, and local dimension $2^{\Theta(1/\gamma^{5})}$ . Furthermore, there is an efficient randomized algorithm to construct these codes with failure probability $2^{-\Omega(n)}$ , as well as efficient encoding and decoding algorithms.

We leverage two key ideas to prove Lemma 4.1. First, recall the discussion in Section 3: If $Q_{LD}$ has distance $d$ , then the syndrome measurement in step 1 of Algorithm 1 of any adversarial channel $\mathcal{A}(\cdot)$ of support at most $\delta\cdot n<d$ collapses the corruption on the code state down to a single Pauli error $E$ . Moreover, the local indistinguishability of the stabilizer code guarantees that an adversary can’t learn any information about the secret key $k$ , and thus $E$ is independent of the random choice of $k$ . We formalize this idea in 4.1, and for conciseness, defer to C.2 in Appendix C a proof of a more general version even in the presence of adversaries with entangled side information.

Next, the list decodability of $Q_{LD}$ enables us to write down a short list $F_{1},\cdots,F_{L}$ of errors associated to the syndrome measurement $s_{QLD}$ of $E$ . We argue in 4.4 that if any candidate error $F_{i}$ has the same PTC syndrome as the syndrome measurement $s_{PTC}$ , then with high probability it exactly corrects the error $E$ . Finally, in 4.5 we tie these ideas together and conclude the proof of Lemma 4.1.

Fact 4.1.

Let $Q$ be be a $[[n,m,d]]_{q}$ stabilizer code. Let $\mathcal{A}$ be an arbitrary adversarial error channel acting on some subset $S\subseteq[n]$ of $|S|<d$ code components. For an arbitrary corrupted code state $\rho$ , let $s_{\rho}$ denote the random variable for the syndrome of $\rho$ . Then the distribution of $s_{\mathcal{A}(\psi)}$ is the same for all $\ket{\psi}\in Q$ .

In this manner, if we pre-encode a message $\psi$ with an ‘inner’ PTC code $Q_{k}$ (for a random choice of key $k$ ) before encoding it into a stabilizer code $Q_{LD}$ , then the syndrome measurement $s_{QLD}$ must be independent of $k$ .

4.4 below reasons that if an operator $E$ is an undetectable error of $Q_{LD}$ (i.e., $E\in N(Q_{LD})\setminus S(Q_{LD})$ ), then with high probability over the choice of $k$ , $E$ is not an undetectable error of the composition $Q_{LD}\circ Q_{k}$ . Later, we use this claim to show the PTC indeed eliminates all but one list element (up to stabilizer-equivalence) with high probability.

Claim 4.4.

Let $E\in\mathcal{P}_{q}^{n}$ satisfy $E\in N(Q_{LD})\setminus S(Q_{LD})$ . If $\{Q_{k}\}$ forms an $\varepsilon$ -PTC, then

\mathbb{P}_{k}\big{[}E\in N(Q_{LD}\circ Q_{k})\setminus S(Q_{LD}\circ Q_{k})\big{]}\leq\varepsilon

(22)

Proof.

Since $E\in N(Q_{LD})\setminus S(Q_{LD})$ , $E$ is equivalent up to a stabilizer (of $Q_{LD}$ ) to some encoded operator $\bar{O}$ on $Q_{LD}$ . Let $O$ be the operator acting on the message space of $Q_{LD}$ corresponding to $\bar{O}$ . If we could prove that $\bar{O}\in N(Q_{LD}\circ Q_{k})\setminus S(Q_{LD}\circ Q_{k})$ iff $O\in N(Q_{k})\setminus S(Q_{k})$ , we would be done, as therefore since $O$ is fixed,

\mathbb{P}_{k}\big{[}E\in N(Q_{LD}\circ Q_{k})\setminus S(Q_{LD}\circ Q_{k})\big{]}=\mathbb{P}_{k}\big{[}O\in N(Q_{k})\setminus S(Q_{k})\big{]}\leq\varepsilon

(23)

by definition of the $\varepsilon$ -PTC. To prove our claim, we consider two cases on $O$ : If $O\in S(Q_{k})$ , then $\bar{O}\in S(Q_{LD}\circ Q_{k})$ is simply a stabilizer of the composed code. If $O\notin N(Q_{k})$ , then $O$ doesn’t commute with some stabilizer $S$ of $Q_{k}$ . That implies their encodings in the composed code $\bar{O}$ , $\bar{S}$ also don’t commute. Thus $\bar{O}\notin N(Q_{LD}\circ Q_{k})$ , and therefore $E\notin N(Q_{LD}\circ Q_{k})$ . We conclude $E\in N(Q_{LD}\circ Q_{k})\setminus S(Q_{LD}\circ Q_{k})$ iff $O\in N(Q_{k})\setminus S(Q_{k})$ as intended. ∎

Let us now tie these ideas together, and prove that Algorithm 1 approximately decodes the code composition. 4.5 below reasons that the density matrix produced at the end of the decoding Algorithm 1 has uniquely decoded the adversarial error with high probability over the random choice of key $k$ , and the outcome of the syndrome measurement.

Claim 4.5.

For any adversarial channel $\mathcal{A}$ acting on $|S|\leq\delta\cdot n<d$ code components, and any $Q_{LD}$ syndrome measurement $s=s_{QLD}$ , there exists a large subset of PTC keys $\text{Good}_{\mathcal{A},s}\subset K$ , $|\text{Good}_{\mathcal{A},s}|\geq|K|(1-L\cdot\varepsilon)$ , such that the density matrix describing the outcome of step 4 in Algorithm 1 in expectation over $k\in K$ can be written as

\rho_{4}=\bigg{(}\sum_{s,k\in\text{Good}_{\mathcal{A},s}}\frac{p_{\mathcal{A},s}}{|K|}\ket{k}\bra{k}\otimes\ket{s}\bra{s}\bigg{)}\otimes\rho+\sum_{s,k\in K\setminus\text{Good}_{\mathcal{A},s}}\frac{p_{\mathcal{A},s}}{|K|}\ket{k}\bra{k}\otimes\ket{s}\bra{s}\otimes\rho_{k,s}.

(24)

where $p_{\mathcal{A},s}$ denotes the probability of the syndrome measurement $s$ , and $\rho_{k,s}$ are arbitrary $m$ qudit density matrices. Thus, Algorithm 1 uniquely recovers the encoded state $\rho$ with probability (and fidelity) $\geq 1-L\cdot\varepsilon$ , and moreover $Q_{LD}\circ Q_{k}$ forms a $(\delta,2\varepsilon L)$ private AQECC.

Proof.

From 4.1, we know that the syndrome measurement of $Q_{LD}$ in step 1 of Algorithm 1 collapses the state into a mixture of single Pauli errors

\rho_{1}=\sum_{s_{QLD},k}\frac{p_{\mathcal{A},s}}{|K|}\ket{k}\bra{k}\otimes\ket{s_{QLD}}\bra{s_{QLD}}\otimes\sigma_{\mathcal{A},s_{QLD}}\mathsf{Enc}_{k}(\rho)\sigma_{\mathcal{A},s_{QLD}}^{\dagger}

(25)

where each Pauli $\sigma_{\mathcal{A},s}\in\mathcal{P}_{q}^{n}$ is a function only of $s=s_{QLD}$ and the support of $\mathcal{A}$ . Note that the syndrome measurement of $s_{PTC}$ does not further collapse the state.

Given $(s_{QLD},s_{PTC})$ , if $E_{1}\cdots E_{L}$ is the list of candidate corrections to $\sigma_{\mathcal{A},s_{QLD}}$ produced in step 3, then at least some $j\in[L]$ corrects $\sigma_{\mathcal{A},s_{QLD}}$ , i.e. $E_{j}^{\dagger}\sigma_{\mathcal{A},s_{QLD}}\in S(Q_{LD}\circ Q_{k})$ . Moreover, the decoding algorithm fails to produce $\rho$ if there exists some other $E_{i}$ of PTC syndrome $s_{PTC}$ which fails to correct $\sigma_{\mathcal{A},s_{QLD}}$ , i.e.

\exists i\in[L]\text{ s.t. }E_{i}^{\dagger}\sigma_{\mathcal{A},s_{QLD}}\in N(Q_{LD}\circ Q_{k})\setminus S(Q_{LD}\circ Q_{k})

(26)

From 4.4, the probability over $k$ this occurs is at most $L\cdot\varepsilon$ by a union bound. Thereby, for every $Q_{LD}$ syndrome measurement $s=s_{QLD}$ , there exists a subset of PTC keys $\text{Good}_{\mathcal{A},s}\subset K$ , $|\text{Good}_{\mathcal{A},s}|\geq|K|(1-L\cdot\varepsilon)$ where any $E_{j}$ in the list with PTC syndrome $s_{PTC}$ exactly recovers $\rho$ . If $k\in K\setminus\text{Good}_{\mathcal{A},s}$ , we have no guarantees on the returned state $\rho_{k,s}$ .

To conclude the proof, let us trace out the syndrome measurement and choice of key $k$ in $\rho_{4}$ . For any encoded state $\rho$ , $\text{Tr}_{s,k}[\rho_{4}]=\rho\cdot p_{success}+\rho_{fail}$ , where $p_{success}=\sum_{s}p_{\mathcal{A},s}\text{Good}_{\mathcal{A},s}/|K|\geq(1-L\cdot\varepsilon)$ and $\|\rho_{fail}\|_{1}=1-p_{success}\leq L\varepsilon$ . Thus,

\norm{\mathbb{E}_{k}[\mathsf{Dec}_{k}\circ\mathcal{A}\circ\mathsf{Enc}_{k}(\rho)]-\rho}_{1}\leq 2\cdot L\cdot\varepsilon.\qed

4.2 AQECC from Private AQEC and Robust Secret Sharing

Recall the definition of an AQECC.

Definition 4.2.

A pair $(\mathsf{Enc},\mathsf{Dec})$ of quantum channels is said to be a $(\delta,\varepsilon)$ -AQECC if, for all adversarial channels $\mathcal{A}$ of weight $\delta\cdot n$ ,

\norm{\mathsf{Dec}\circ\mathcal{A}\circ\mathsf{Enc}-\mathbb{I}}_{\diamond}\leq\varepsilon.

The following definition of robust secret sharing is taken from [CDD⁺15], except that we do not restrict to linear schemes and we do not include separate parameters for privacy and reconstructability. We also require the algorithms in the scheme to be efficient.

Definition 4.3 (Robust secret sharing).

For integers $n,s,d,$ and $a$ , an $[n,s]_{a}$ $(d,\varepsilon)$ -robust secret sharing scheme $\mathsf{RSS}$ consists of two efficient algorithms $\mathsf{RSS}.\mathsf{Share}$ and $\mathsf{RSS}.\mathsf{Reconstruct}$ . For every $r\in[a]^{s}$ , $\mathsf{RSS}.\mathsf{Share}(r)$ outputs a vector of shares $v\in[a]^{n}$ . We require the following two properties:

•

Privacy: For all $r,r^{\prime}\in[a]^{s}$ and every $A\subseteq[n]$ of size $\absolutevalue{A}\leq d$ , the restrictions $v_{A}$ and $v_{A}^{\prime}$ of $v=\mathsf{RSS}.\mathsf{Share}(r)$ and $v^{\prime}=\mathsf{RSS}.\mathsf{Share}(r^{\prime})$ to the coordinates in $A$ have the same probability distribution.
•

Reconstructability: For every $r\in[a]^{s}$ and every $A\subseteq[n]$ of size $\absolutevalue{A}\leq d$ , if $v=\mathsf{RSS}.\mathsf{Share}(r)$ and $\tilde{v}$ is such that $\tilde{v}_{\bar{A}}=v_{\bar{A}}$ and $\tilde{v}$ only depends on $v_{A}$ , then $\mathsf{RSS}.\mathsf{Reconstruct}(\tilde{v})=r$ except with probability $\varepsilon$ .

The following result is from [CDD⁺15], with the explicit choice of alphabet size $a$ from [GX14]. Concretely, we use the fact that $2^{1/\gamma}<a=2^{\tilde{O}(\gamma^{-2})}$ .

Theorem 4.6 ([CDD⁺15], Theorem 7).

For any $\gamma>0$ and $R\in(0,1)$ , there exists an efficient family of $[n,R\cdot n]_{a}$ $((1-R-\gamma)\cdot n/2,2^{-n})$ -robust secret sharing schemes $\{\mathsf{RSS}_{n}\}$ on shares of alphabet size $a=2^{\tilde{O}(\gamma^{-2})}$ .

Given any $[n,s]_{a}$ $(d,\varepsilon)$ -robust secret sharing scheme $\mathsf{RSS}$ , and a $[[n,k]]_{q}$ private $(d,\varepsilon^{\prime})$ -approximate quantum code $Q$ defined by $(\mathsf{Enc}_{r},\mathsf{Dec}_{r})_{r\in[a]^{s}}$ , we build an $(d,\varepsilon+\varepsilon^{\prime})$ -approximate $[[n,k]]_{q\cdot a}$ code $\hat{Q}$ by secret sharing the private keys $r$ with $\mathsf{RSS}$ and appending the shares to the symbols of $Q$ .

Formally, $\mathsf{Enc}$ for $\hat{Q}$ works as follows:

1.

Sample $r\leftarrow[a]^{s}$ .
2.

Apply $\mathsf{Enc}$ to $\rho$ , and call the resulting register $C=(C_{1},\dots,C_{n})$ .
3.

Compute $\mathsf{RSS}.\mathsf{Share}(r)$ , and store the (classical) result on register $S=(S_{1},\dots,S_{n})$ .
4.

Use $(C,S)$ as the codestate, where register $i\in[n]$ is the $a\cdot q$ -dimensional register $(C_{i},S_{i})$ .

To decode $\hat{Q}$ , we recover the private keys using the reconstruction algorithm of $\mathsf{RSS}$ and then apply the decoder for $Q$ to the $C$ register:

1.

Measure register $S$ and apply $\mathsf{RSS}.\mathsf{Reconstruct}$ to the result, obtaining $\tilde{r}$ .
2.

Apply $\mathsf{Dec}_{\tilde{r}}$ to $C$ , and output the resulting decoded message.

Theorem 4.7.

Given

1.

any $[n,s]_{a}$ $(d,\varepsilon)$ -robust secret sharing scheme $\mathsf{RSS}$ , and
2.

any $(d,\varepsilon^{\prime})$ -approximate private quantum $[[n,k]]_{q}$ code $Q$ with key space $[a]^{s}$ ,

the construction of $\hat{Q}$ above is an $(d,\varepsilon+\varepsilon^{\prime})$ -approximate $[[n,k\cdot\log(q)/\log(q\cdot a)]]_{q\cdot a}$ quantum code.

Proof.

Let $\rho$ be any message. Partition the registers of $\mathsf{Enc}(\rho)$ into $C_{A},C_{\bar{A}},S_{A},S_{\bar{A}}$ , where $C_{A},C_{\bar{A}}$ are the private AQECC part and $S_{A},S_{\bar{A}}$ are the RSS part, and the error channel acts only on $C_{A},S_{A}$ . Let $E$ denote the error channel. By the secrecy guarantee of the RSS against any subset of $d$ symbols, we have

	$\displaystyle\Tr_{S}\bigg{[}E\left(a^{-s}\sum_{r\in[a]^{s}}\mathsf{Enc}_{r}(\rho)_{C}\otimes\mathsf{RSS}.\mathsf{Share}(r)_{S}\right)\bigg{]}$
	$\displaystyle=\Tr_{S_{A}}\bigg{[}E\bigg{(}\Tr_{S_{\bar{A}}}a^{-s}\sum_{r\in[a]^{s}}\mathsf{Enc}_{r}(\rho)_{C}\otimes\mathsf{RSS}.\mathsf{Share}(r)_{S}\bigg{)}\bigg{]}$
	$\displaystyle=\Tr_{S_{A}}\bigg{[}E\bigg{(}\Tr_{S_{\bar{A}}}a^{-2s}\sum_{r\in[a]^{s},r^{\prime}\in[a]^{s}}\mathsf{Enc}_{r}(\rho)_{C}\otimes\mathsf{RSS}.\mathsf{Share}(r^{\prime})_{S}\bigg{)}\bigg{]}$
	$\displaystyle=\Tr_{S}\bigg{[}E\bigg{(}a^{-2s}\sum_{r\in[a]^{s},r^{\prime}\in[a]^{s}}\mathsf{Enc}_{r}(\rho)_{C}\otimes\mathsf{RSS}.\mathsf{Share}(r^{\prime})_{S}\bigg{)}\bigg{]}$

and thereby the adversary gains no information about the encryption key. By the recoverability guarantee of the RSS, $\mathsf{Dec}$ will use the correct private keys $r$ with probability $1-\varepsilon$ , so

	$\displaystyle\norm{\rho-\mathsf{Dec}\circ E\circ\mathsf{Enc}(\rho)}_{1}$	$\displaystyle=\norm{\rho-\mathsf{Dec}\circ E\left(\frac{1}{a^{s}}\sum_{r\in[a]^{s}}\mathsf{Enc}_{r}(\rho)\otimes\mathsf{RSS}.\mathsf{Share}(r)\right)}_{1}$
		$\displaystyle\leq\norm{\rho-\frac{1}{a^{s}}\sum_{r\in[a]^{s}}\mathsf{Dec}_{r}\circ\Tr_{S}\circ E(\mathsf{Enc}_{r}(\rho)\otimes\mathsf{RSS}.\mathsf{Share}(r))}_{1}+\varepsilon$
		$\displaystyle=\norm{\rho-\frac{1}{a^{s}}\sum_{r\in[a]^{s}}\mathsf{Dec}_{r}\circ\Tr_{S}\circ E\left(\mathsf{Enc}_{r}(\rho)\otimes\frac{1}{a^{s}}\sum_{r^{\prime}\in[a]^{s}}\mathsf{RSS}.\mathsf{Share}(r^{\prime})\right)}_{1}+\varepsilon$
		$\displaystyle\leq\varepsilon^{\prime}+\varepsilon.\qed$

Using the private AQECC of Corollary 4.3 and the robust secret sharing scheme of [CDD⁺15], we are able to instantiate Theorem 4.7 to obtain the following result.

Corollary 4.8.

For any constant $\gamma>0$ and $R\in(0,1)$ , there exists a family $\{Q_{n}\}$ of $((1-R-\gamma)/2,2^{-\Omega(n)})$ -approximate $[[n,R\cdot n]]_{q^{\prime}}$ quantum codes on alphabets of size $q^{\prime}=2^{O(1/\gamma^{5})}$ . Furthermore, there is an efficient randomized algorithm to construct these codes with failure probability $2^{-\Omega(n)}$ , as well as efficient encoding and decoding algorithms.

Proof.

By Corollary 4.3, for any fixed $R^{\prime},\gamma^{\prime}>0$ there exist $[[n,R^{\prime}\cdot n]]_{q}$ private $((1-R^{\prime}-\gamma^{\prime})/2,2^{-\Omega(n)})$ -approximate quantum error correcting codes with $n$ -bit keys and alphabet size $q=2^{\Theta(1/\gamma^{\prime 5})}$ , with the desired efficiency and construction guarantees. By Theorem 4.6, there exist $[n,r\cdot n]_{a}$ $((1-r-\gamma^{\prime\prime})\cdot n/2,2^{-n})$ -robust secret sharing schemes, for $a=2^{\tilde{O}(1/\gamma^{\prime\prime 2})}$ .

So long as the private AQECC key length is smaller than the secret size for the RSS scheme of Theorem 4.6, it can be secret shared into the RSS. This occurs if $n\leq n\cdot r\log a$ , i.e., $r\geq 1/\log a$ . From [GX14], we have $\log a\geq 1/\gamma^{\prime\prime}$ , and thus we pick $r=\gamma^{\prime\prime}$ . Theorem 4.7 then yields an AQECC with decoding radius $\frac{1}{2}\min\big{\{}(1-R^{\prime}-\gamma^{\prime}),(1-r-\gamma^{\prime\prime})\big{\}}$ , and its rate is

\frac{R^{\prime}\cdot n\log q}{n\cdot(\log q+\log a)}=\frac{\Theta(1/\gamma^{\prime 5})}{\Theta(1/\gamma^{\prime 5})+\tilde{O}(1/\gamma^{\prime\prime 2})}\cdot R^{\prime},

and it only remains to pick $\gamma^{\prime}$ . By inspection, there is a function $f(\gamma^{\prime\prime})=\tilde{O}(\gamma^{\prime\prime 3/5})$ such that whenever $\gamma^{\prime}\leq f(\gamma^{\prime\prime})$ , the rate above is at least $R^{\prime}\cdot(1-\gamma^{\prime\prime})$ . We can now divide into cases on $\gamma^{\prime\prime},f(\gamma^{\prime\prime})$ to determine the decoding radius. If $\gamma^{\prime\prime}<f(\gamma^{\prime\prime})$ , pick $\gamma^{\prime}=\gamma^{\prime\prime}$ , and if $\gamma^{\prime\prime}\geq f(\gamma^{\prime\prime})$ we pick $\gamma^{\prime}=f(\gamma^{\prime\prime})$ . In either case, the alphabet size is $q^{\prime}=q\cdot a=2^{O(1/\gamma^{\prime\prime 5})}$ , and the decoding radius is at least $\frac{1}{2}(1-\gamma^{\prime\prime}-\max\{R^{\prime},\gamma^{\prime\prime}\})$ .

To conclude, let us set $\gamma^{\prime\prime}=\gamma/4$ , and $R^{\prime}=R/(1-\gamma^{\prime\prime})$ . We may assume that $R^{\prime}\leq 1$ because $R\leq 1-\gamma=1-4\gamma^{\prime\prime}$ ; otherwise the decoding radius in the theorem statement is $0$ . The overall rate is then $R$ as intended. Since $\gamma^{\prime\prime}\leq 1/4$ , we have $R^{\prime}\leq R(1+2\gamma^{\prime\prime})\leq R+\gamma/2$ , and thus the resulting decoding radius is at least $(1-R-\gamma)/2$ . ∎

5 Distance Amplification and Alphabet Reduction for Quantum Codes

In this section, we describe how we apply Alon-Edmonds-Luby (AEL) distance amplification [AEL95] to quantum codes. This technique has seen extensive use in classical coding theory [GI01, GI02, GI03, GR08, HW18, KMRZS15, GKO⁺18, HRZW19], as it allows for amplifying the distance of a code while reducing alphabet size and preserving properties such as decodability and local testability and correctability.

To the best of our knowledge, AEL amplification has not previously been used in the quantum setting. However, as shown below, this technique translates almost flawlessly to quantum codes. This observation immediately yields some new results that will be discussed below, such as efficiently decodable quantum codes approaching the quantum Singleton bound over constant sized alphabets. In fact, such codes can be made LDPC using recent asymptotically good quantum LDPC constructions [PK22, LZ22c], some of which permit efficient decoding [LZ22a, DHLV22, GPT22, LZ22b].

Both of our constructions of AQECCs approaching the quantum Singleton bound apply the AEL construction. Specifically, we instantiate the AQECC construction described in Section 4 using quantum list-decodable codes approaching the quantum Singleton bound with constant alphabet size that we will construct in Section 6 by applying AEL to reduce the alphabet size of folded quantum Reed-Solomon codes. Then in Section 7, we provide another construction of AQECCs by applying AEL amplification directly with inner codes that are themselves appropriately chosen AQECCs.

At a high level, the AEL construction amplifies the distance of a code by concatenating with a small inner code of good distance, and then permuting the symbols of the concatenated code using an expander graph. If the outer code is chosen to have high rate and constant relative distance, then the resulting construction inherits the rate and distance of the inner code, up to a small loss. This procedure in fact works for arbitrary quantum codes; we do not even need to restrict attention to stabilizer codes below.

We first define the appropriate notion of expansion.

Definition 5.1.

An $r$ -regular bipartite graph $G=(L,R,E)$ with $|L|=|R|=n$ is said to be $\varepsilon$ -pseudorandom if it holds for every $S\subseteq L$ and $T\subseteq R$ that

\left||E(S,T)|-\frac{r|S||T|}{n}\right|\leq\varepsilon r\sqrt{|S||T|}.

By the well-known expander mixing lemma, the 2-lift of any $\lambda$ -spectral expander graph is $\lambda$ -pseudorandom. Thus in particular, the 2-lift of a $r$ -regular Ramanujan graph is $\varepsilon$ -pseudorandom for $\varepsilon=2\sqrt{r-1}/r$ . It follows that there exist explicit families of $r$ -regular $\varepsilon$ -pseudorandom graphs for all $r\geq 4/\varepsilon^{2}$ .

We now present the AEL construction in the quantum setting. We first present a basic version that amplifies distance without decreasing the alphabet size. We will then explain how the alphabet size can also be reduced. The analysis of the quantum version of the AEL construction in Proposition 5.1 and Proposition 5.4 below directly adapts the well-known analogous results for classical codes dating back to [AEL95]. However, to the best of our knowledge the application to the quantum setting is new, as are the corollaries below providing quantum codes approaching the quantum Singleton bound that are efficiently unique-decodable up to half their distance.

5.1 Distance Amplification without Alphabet Reduction

We first describe a simple version of AEL amplification that does not reduce alphabet size. Let $Q_{\text{out}}$ and $Q_{\text{in}}$ be $[[n_{\text{out}},k_{\text{out}},\Delta_{\text{out}}n_{\text{out}}]]_{q_{\text{out}}}$ and $[[n_{\text{in}},k_{\text{in}},\Delta_{\text{in}}n_{\text{in}}]]_{q_{\text{in}}}$ quantum codes respectively such that $q_{\text{out}}=q_{\text{in}}^{k_{\text{in}}}$ . Let $Q_{\diamond}=Q_{\text{out}}\diamond Q_{\text{in}}$ denote the $[[n_{\text{out}}n_{\text{in}},k_{\text{out}}k_{\text{in}}]]_{q_{\text{in}}}$ concatenated code. The key step is now to permute the components of $Q_{\diamond}$ according to the edges of an $n_{\text{in}}$ -regular bipartite expander, and to block the $n_{\text{out}}n_{\text{in}}$ $q_{\text{in}}$ -ary components into $n_{\text{out}}$ $q_{\text{in}}^{n_{\text{in}}}$ -ary components. Specifically, let $G=(L=[n_{\text{out}}],R=[n_{\text{out}}],E)$ be an $n_{\text{in}}$ -regular $\varepsilon_{0}$ -pseudorandom bipartite graph, and assume that the edges at each vertex have an arbitrary labeling by elements of $[n_{\text{in}}]$ . Let $\pi_{G}:[n_{\text{out}}]\times[n_{\text{in}}]\rightarrow[n_{\text{out}}]\times[n_{\text{in}}]$ be the permutation that maps $(i,j)\in[n_{\text{out}}]\times[n_{\text{in}}]$ to the unique pair $(i^{\prime},j^{\prime})$ such that the $j$ th outgoing edge in $G$ from vertex $i\in L$ lands on $i^{\prime}\in R$ , and $j^{\prime}$ is the label that vertex $i^{\prime}$ assigns to this edge $(i,i^{\prime})$ . Define $Q=\pi_{G}(Q_{\diamond})$ to be the $[[n_{\text{out}},R_{\text{in}}k_{\text{out}}]]_{q_{\text{in}}^{n_{\text{in}}}}$ code obtained by applying the permutation $\pi_{G}$ to the components of $Q_{\diamond}$ , and then regrouping each resulting block of $n_{\text{in}}$ components to a single $q_{\text{in}}^{n_{\text{in}}}$ -ary symbol. Observe that $Q$ has the same rate $R=R_{\diamond}=R_{\text{out}}R_{\text{in}}$ as $Q_{\diamond}$ .

Proposition 5.1.

The code $Q$ defined above has relative distance $\Delta\geq\Delta_{\text{in}}-2\varepsilon_{0}\sqrt{\Delta_{\text{in}}/\Delta_{\text{out}}}$ .

More generally, for every $0<\alpha_{\text{out}},\alpha_{\text{in}}<1$ , if a codeword of $Q$ experiences an error on $\alpha\leq\alpha_{\text{in}}-\varepsilon_{0}\sqrt{\alpha_{\text{in}}/\alpha_{\text{out}}}$ fraction of its ( $q_{\text{in}}^{n_{\text{in}}}$ -ary) components, then after applying $\pi_{G}^{-1}$ , fewer than $\alpha_{\text{out}}$ fraction of the resulting inner code blocks experience errors on at least $\alpha_{\text{in}}$ fraction of their ( $q_{\text{in}}$ -ary) components.

Proposition 5.1 follows directly from the following lemma, which captures the key property of the permutation $\pi_{G}$ .

Lemma 5.2.

Let $G=(L=[n_{\text{out}}],R=[n_{\text{out}}],E)$ be an $n_{\text{in}}$ -regular $\varepsilon_{0}$ -pseudorandom bipartite graph, and define $\pi_{G}:[n_{\text{out}}]\times[n_{\text{in}}]\rightarrow[n_{\text{out}}]\times[n_{\text{in}}]$ as above. Then for every $0<\alpha_{\text{out}},\alpha_{\text{in}}<1$ , and for every $T\subseteq R$ of size $|T|\leq(\alpha_{\text{in}}-\varepsilon_{0}\sqrt{\alpha_{\text{in}}/\alpha_{\text{out}}})\cdot n_{\text{out}}$ , there are fewer than $\alpha_{\text{out}}\cdot n_{\text{out}}$ vertices $i\in L$ for which

|\{j\in[n_{\text{in}}]:\pi_{G}(i,j)\in T\times[n_{\text{in}}]\}|\geq\alpha_{\text{in}}\cdot n_{\text{in}}.

(27)

Proof.

The proof is a direct application of the definition of $\varepsilon_{0}$ -pseudorandomness. Let $S\subseteq L$ be the set of vertices for which Equation 27 holds. Then by definition

\displaystyle|E(S,T)|

\displaystyle\geq|S|\cdot\alpha_{\text{in}}n_{\text{in}}.

Meanwhile by the $\varepsilon_{0}$ -pseudorandomness of $G$ ,

	$\displaystyle\|E(S,T)\|$	$\displaystyle\leq\frac{n_{\text{in}}\|S\|\|T\|}{n_{\text{out}}}+\varepsilon_{0}n_{\text{in}}\sqrt{\|S\|\|T\|}$
		$\displaystyle<\|S\|\cdot\alpha_{\text{in}}n_{\text{in}}-\|S\|\cdot\varepsilon_{0}n_{\text{in}}\sqrt{\frac{\alpha_{\text{in}}}{\alpha_{\text{out}}}}+\|S\|\cdot\varepsilon_{0}n_{\text{in}}\sqrt{\frac{\alpha_{\text{in}}}{\|S\|/n_{\text{out}}}}$

where the second inequality above applies the fact that $|T|\leq(\alpha_{\text{in}}-\varepsilon_{0}\sqrt{\alpha_{\text{in}}/\alpha_{\text{out}}})\cdot n_{\text{out}}$ . The above inequalities give a contradiction whenever $|S|/n_{\text{out}}\geq\alpha_{\text{out}}$ , so we must have $|S|/n_{\text{out}}<\alpha_{\text{out}}$ , as desired. ∎

To apply Lemma 5.2 to an AEL code $Q=\pi_{G}(Q_{\text{out}}\diamond Q_{\text{in}})$ , we will typically choose $\alpha_{\text{out}}$ and $\alpha_{\text{in}}$ to be the decoding radii of $Q_{\text{out}}$ and $Q_{\text{in}}$ respectively. Then if $Q$ experiences errors on $\alpha_{\text{in}}-\varepsilon_{0}\sqrt{\alpha_{\text{in}}/\alpha_{\text{out}}}$ fraction of its components, we may apply the natural decoding algorithm $\mathsf{Dec}_{Q_{\text{out}}}\circ\mathsf{Dec}_{Q_{\text{in}}}^{\otimes n_{\text{out}}}\circ\pi_{G}^{-1}$ , and Lemma 5.2 guarantees that fewer than $\alpha_{\text{out}}$ fraction of the inner decodings fail, so that the outer decoding will succeed. The following proof of Proposition 5.1 formalizes this idea for unique decoding for both the inner and outer codes. We will subsequently follow [GR08] in applying the same idea with list decoding for the inner code and list recovery for the outer code.

Proof of Proposition 5.1.

The second statement in the proposition is equivalent to Lemma 5.2, so we just need to show the first statement. For this purpose, it suffices to show that $Q$ can be decoded from errors acting on at most $\kappa=\Delta_{\text{in}}/2-\varepsilon_{0}\sqrt{\Delta_{\text{in}}/\Delta_{\text{out}}}$ fraction of the components. Assume some error acts on some subset $T\subseteq[n_{\text{out}}]$ of the code components with $|T|\leq\kappa n_{\text{out}}$ . Let $S\subseteq[n_{\text{out}}]$ be the set of blocks in $Q_{\diamond}=\pi_{G}^{-1}(Q)$ inside which at least $\Delta_{\text{in}}n_{\text{in}}/2$ of the qudits are mapped by $\pi_{G}$ to blocks in $T$ . Lemma 5.2 with $\alpha_{\text{in}}=\Delta_{\text{in}}/2$ and $\alpha_{\text{out}}=\Delta_{\text{out}}/2$ gives that $|S|<\Delta_{\text{out}}n_{\text{out}}/2$ , so the natural decoding algorithm $\mathsf{Dec}_{Q_{\text{out}}}\circ\mathsf{Dec}_{Q_{\text{in}}}^{\otimes n_{\text{out}}}\circ\pi_{G}^{-1}$ is guaranteed to successfully correct the error, as all inner decodings in blocks outside of $S$ must succeed. ∎

Below we show how applying AEL amplification to asymptotically good quantum LDPC codes with a constant sized random inner code yields efficiently decodable quantum LDPC codes approaching the quantum Singleton bound over constant sized alphabets. To the best of our knowledge, such a family of quantum codes was not previously known even without the LDPC requirement.

Corollary 5.3.

For every $\gamma>0$ and $0<R<1$ , there exists some $q=q(\gamma)$ such that there exists an explicit infinite family of quantum LDPC CSS codes of rate $R$ , relative distance $\Delta=(1-R-\gamma)/2$ , and alphabet size $q$ that are decodable in time $O_{\gamma}(n)$ up to errors on $\Delta/2$ fraction of the $n$ components.

Proof.

We may assume that $R<1-\gamma$ , as otherwise $\Delta\leq 0$ and the result holds trivially. We may also assume that $R\geq\gamma/2$ , as otherwise we may simply construct an AQECC of larger rate $\gamma/2$ using the argument below for updated parameters $R^{\prime}=\gamma/2$ and $\gamma^{\prime}=\gamma/2$ . By [PK22, LZ22c, LZ22a, DHLV22, GPT22, LZ22b], there exist explicit infinite families of $[[n_{\text{out}},k_{\text{out}}]]_{2}$ qLDPC CSS codes $Q_{\text{out}}$ of rate $1-\gamma/20$ over a binary alphabet that are decodable in linear time (for fixed $\gamma$ ) up to some constant fraction $\kappa=\kappa(\gamma)$ of errors. Here we do not need to let $\kappa$ or the decoding runtime depend directly on $R$ because $\gamma/2\leq R\leq 1-\gamma$ by assumption.

Futhermore, by A.2, there exist sufficiently large $q_{\text{in}}=q_{\text{in}}(\gamma)$ and $n_{0}=n_{0}(\gamma)$ such that for every $n_{\text{in}}\geq n_{0}$ , a random CSS code $Q_{\text{in}}$ of rate $R+\gamma/20$ , block length $n_{\text{in}}$ , and alphabet size $q_{\text{in}}$ will with positive probability have relative distance $\geq(1-R-\gamma/10)/2$ . Here we may assume that $q_{\text{in}}=2^{m}$ for some $m\in\mathbb{N}$ , so the classical codes making up the random CSS code are linear over $\mathbb{F}_{q_{\text{in}}}$ , and therefore are also $\mathbb{F}_{2}$ -linear.

Now set $\gamma_{0}=\gamma\sqrt{\kappa}/40$ , and set $n_{\text{in}}=\max\{n_{0},4/\gamma_{0}^{2}\}$ . Let $Q_{\diamond}=Q_{\text{out}}\diamond Q_{\text{in}}$ denote the concatenated code, where before concatenating we first block together groups of $mk_{\text{in}}$ qubits in $Q_{\text{out}}$ to obtain a code with the same rate and decoding radius over the alphabet $(\mathbb{F}_{2}^{m})^{k_{\text{in}}}$ . Finally, for some $n_{\text{in}}$ -regular $\gamma_{0}$ -pseudorandom bipartite graph $G$ , let $Q=\pi_{G}(Q_{\diamond})$ . Such a graph exists because $n_{\text{in}}\geq 4/\gamma_{0}^{2}$ by assumption.

Thus we have constructed an infinite family of quantum codes $Q$ of rate $(1-\gamma/20)(R+\gamma/20)\geq R$ over the alphabet $\mathbb{F}_{2}^{m}$ . By Proposition 5.1, these codes are decodable up to errors acting on $\Delta_{\text{in}}/2-2\gamma_{0}/\sqrt{\kappa}>(1-R-\gamma)/4$ fraction of the components. The proof of Proposition 5.1 in fact implies that the natural decoding algorithm $\mathsf{Dec}_{Q}=\mathsf{Dec}_{Q_{\text{out}}}\circ\mathsf{Dec}_{Q_{\text{in}}}^{\otimes n_{\text{out}}}\circ\pi_{G}^{-1}$ decodes up to this radius. For fixed $\gamma$ , this algorithm runs in time linear in the block length because $\mathsf{Dec}_{Q_{\text{out}}}$ by assumption runs in linear time, and $Q_{\text{in}}$ is a constant size CSS code and thus can be decoded in constant time via brute force. Also observe that for fixed $\gamma,R$ , then $Q_{\text{out}}$ is an explicit LDPC CSS code, and $Q_{\text{in}}$ is a constant sized CSS code that can be constructed in constant time via a brute force search. Thus $Q_{\diamond}$ and therefore $Q$ is an explicit quantum LDPC CSS code. ∎

5.2 Distance Amplification with Alphabet Reduction

We now show how the AEL construction can simultaneously amplify the distance and reduce the alphabet size of the outer code. Again let $Q_{\text{out}}$ and $Q_{\text{in}}$ be $[[n_{\text{out}},k_{\text{out}},\Delta_{\text{out}}n_{\text{out}}]]_{q_{\text{out}}}$ and $[[n_{\text{in}},k_{\text{in}},\Delta_{\text{in}}n_{\text{in}}]]_{q_{\text{in}}}$ quantum codes respectively such that $q_{\text{out}}=q_{\text{in}}^{k_{\text{in}}}$ . Let $Q_{\diamond}=Q_{\text{out}}\diamond Q_{\text{in}}$ denote the $[[n_{\text{out}}n_{\text{in}},k_{\text{out}}k_{\text{in}}]]_{q_{\text{in}}}$ concatenated code. As in Section 5.1, we will permute the components of $Q_{\diamond}$ according to an appropriate expander graph and reblock into larger symbols. However, we will now reblock into smaller symbols than before.

Specifically, for some $r\leq n_{\text{in}}$ , we partition the code components into groups of $r$ $q_{\text{in}}$ -ary symbols, each of which we block into a $q_{\text{in}}^{r}$ -ary symbol. To avoid rounding issues, for simplicity assume that $r$ divides $n_{\text{in}}$ , and let $b=n_{\text{in}}/r$ . Let $G=(L=[n_{\text{out}}b],R=[n_{\text{out}}b],E)$ be an $r$ -regular $\varepsilon_{0}$ -pseudorandom bipartite graph, and assume that the edges at each vertex have an arbitrary labeling by elements of $[r]$ . Similarly as in Section 5.1, let $\pi_{G}:[n_{\text{out}}b]\times[r]\rightarrow[n_{\text{out}}b]\times[r]$ be the permutation that maps $(i,j)\in[n_{\text{out}}b]\times[r]$ to the unique pair $(i^{\prime},j^{\prime})$ such that the $j$ th outgoing edge in $G$ from vertex $i\in L$ lands on $i^{\prime}\in R$ , and $j^{\prime}$ is the label that vertex $i^{\prime}$ assigns to this edge $(i,i^{\prime})$ . Define $Q=\pi_{G}(Q_{\diamond})$ to be the $[[n_{\text{out}}b,k_{\text{out}}k_{\text{in}}/b]]_{q_{\text{in}}^{r}}$ code obtained by applying the permutation $\pi_{G}$ to the components of $Q_{\diamond}$ , and then regrouping each consecutive block of $r$ $q_{\text{in}}$ -ary components into a single $q_{\text{in}}^{r}$ -ary component. As before, $Q$ has the same rate $R=R_{\diamond}=R_{\text{out}}R_{\text{in}}$ as $Q_{\diamond}$ . However, now the alphabet size $q_{\text{in}}^{r}$ of $Q$ does not depend on the inner code’s block length $n_{\text{in}}$ .

Proposition 5.4.

The code $Q$ defined above has relative distance $\Delta\geq\Delta_{\text{in}}-6(\varepsilon_{0}/2\cdot\sqrt{\Delta_{\text{in}}/\Delta_{\text{out}}})^{2/3}$ .

More generally, for every $0<\alpha_{\text{out}},\alpha_{\text{in}}<1$ , if a codeword of $Q$ experiences an error on $\alpha\leq\alpha_{\text{in}}-3(\varepsilon_{0}/2\cdot\sqrt{\alpha_{\text{in}}/\alpha_{\text{out}}})^{2/3}$ fraction of its ( $q_{\text{in}}^{r}$ -ary) components, then after applying $\pi_{G}^{-1}$ , fewer than $\alpha_{\text{out}}$ fraction of the resulting inner code blocks experience errors on at least $\alpha_{\text{in}}$ fraction of their ( $q_{\text{in}}$ -ary) components.

Proof.

We will prove the second statement in the proposition, as the first statement then follows by letting $\alpha_{\text{out}}=\Delta_{\text{out}}/2$ and $\alpha_{\text{in}}=\Delta_{\text{in}}/2$ analogously as in Proposition 5.1. Let $\varepsilon^{\prime}=(\varepsilon_{0}/2\cdot\sqrt{\alpha_{\text{in}}/\alpha_{\text{out}}})^{2/3}$ . Then $Q$ experiences an error on $\alpha\leq\alpha_{\text{in}}-\varepsilon^{\prime}-\varepsilon_{0}\sqrt{\alpha_{\text{in}}/\varepsilon^{\prime}\alpha_{\text{out}}}$ fraction of its components, so Lemma 5.2 implies that fewer than $\varepsilon^{\prime}\alpha_{\text{out}}$ fraction of the components of $\pi_{G}^{-1}(Q)$ (each of which is itself a length- $r$ block of $q_{\text{in}}$ -ary symbols) experience an error acting on at least $\alpha_{\text{in}}-\varepsilon^{\prime}$ fraction of its symbols. Now recall that each inner code block of $\pi_{G}^{-1}(Q)$ consists of $b$ of these length- $r$ blocks with $br=n_{\text{in}}$ . Thus for a given inner code block, if at most $\varepsilon^{\prime}$ fraction of the $b$ length- $r$ blocks experience an error acting on at least $(\alpha_{\text{in}}-\varepsilon^{\prime})r$ symbols, then the number of symbols in the entire inner block that experience an error is at most $\varepsilon^{\prime}br+(1-\varepsilon^{\prime})(\alpha_{\text{in}}-\varepsilon^{\prime})br<\alpha_{\text{in}}br$ . Thus an inner code block can only experience errors on $\geq\alpha_{\text{in}}$ fraction of its $n_{\text{in}}=br$ symbols if $>\varepsilon^{\prime}$ fraction of its length- $r$ blocks experience errors on at least $\alpha_{\text{in}}-\varepsilon^{\prime}$ fraction of their symbols. Therefore if at least $\alpha_{\text{out}}$ fraction of the inner code blocks experience errors on at least $\alpha_{\text{in}}$ fraction of their components, then more than $\varepsilon^{\prime}\alpha_{\text{out}}$ fraction of the length- $r$ blocks in the entire code $\pi_{G}^{-1}(Q)$ must experience errors on $\geq\alpha_{\text{in}}-\varepsilon^{\prime}$ fraction of their symbols. But as described above, Lemma 5.2 implies that this latter statement cannot occur, so fewer than $\alpha_{\text{out}}$ fraction of the inner code blocks can experience errors on at least $\alpha_{\text{in}}$ fraction of their components, as desired. ∎

We will typically apply Proposition 5.4 with an outer code of growing alphabet size $q_{\text{out}}=\poly(n_{\text{out}})$ , such as quantum Reed-Solomon or folded Reed-Solomon, and an inner code of fixed alphabet size $q_{\text{in}}=O(1)$ , such as a random CSS code.

6 Constant-Alphabet Quantum List Decodable Codes Near the Singleton Bound

In this section, we apply the AEL distance amplification and alphabet reduction construction described in Section 5 to the folded quantum Reed-Solomon codes described in Section 3.1. This construction is a quantum analogue of the classical construction of [GR08]. As in the classical case, the resulting quantum codes have constant alphabet size and are efficiently list-decodable with polynomial list size for a fraction of adversarial errors approaching the Singleton bound.

Theorem 6.1.

For every $\gamma>0$ and $0<R<1$ , there exists an infinite family of quantum CSS codes $Q$ of rate $R$ , relative distance at least $\delta=(1-R-\gamma)/2$ , and alphabet size $q=2^{O(1/\gamma^{5})}$ that are $(\delta,L=n^{O(1/\gamma^{3})})$ list-decodable in time $n^{O(1/\gamma^{4})}$ , where $n$ denotes the block length of $Q$ . Furthermore, there exists a randomized algorithm that constructs $Q$ in time $n^{O(1/\gamma^{4})}$ with failure probability $2^{-\Omega(n)}$ .

The proof of Theorem 6.1 concatenates a folded quantum Reed-Solomon outer code (see Section 3.1) with a list-decodable random CSS inner code and then reduces the alphabet size using AEL. To list-decode such a concatenation, we typically want to use a list-recoverable outer code as defined below.

Definition 6.1.

A code $C\subset\Sigma^{n}$ is $(\eta,\ell,L)$ -LR (list-recoverable) if $\forall S_{1}\cdots S_{n}\subset\Sigma$ , with $|S_{i}|\leq\ell$ ,

\bigg{|}\bigg{\{}c\in C:c_{i}\in S_{i}\text{ for at least }\eta\cdot n\text{ symbols }i\in[n]\bigg{\}}\bigg{|}\leq L

(28)

The following result of [GR08] shows that folded Reed-Solomon codes have this property.

Theorem 6.2 ([GR08]).

For every $0<R<1$ , and $\gamma>0$ , $\ell\geq 1$ , and $m\geq 1$ , the $m$ -folded Reed-Solomon codes over $\mathbb{F}_{q}$ of block length $N$ are

\left(\eta=R\cdot\left(1+\frac{s}{t}\right)\cdot\frac{m}{m-s+1}\cdot\left(\frac{\ell}{R}\right)^{1/(s+1)},\;\ell,\;L=(Nm)^{O(s)}\right)

list-recoverable in time $(Nm)^{O(s)}$ for all choices of integers $s\leq m$ and $t\geq 1$ satisfying $(s+t)(\ell/R)^{1/(s+1)}<q$ .

In Theorem 6.2, we will typically have $q$ growing with the block length $N$ while $s,t,\ell,R$ are fixed, so the condition that $(s+t)(\ell/R)^{1/(s+1)}<q$ trivially holds. Then for $\gamma>0$ and $\ell=O_{\gamma}(1)$ we may choose sufficiently large $s,t,m=O_{\gamma}(1)$ to obtain list-recovery up to a radius $\eta=R+O(\gamma)$ lying within $O(\gamma)$ of the Singleton bound.

Proof of Theorem 6.1.

The code $Q$ is an instantiation of the AEL construction described in Section 5.2 with the following parameters. Note that we may assume that $\gamma/2\leq R\leq 1-\gamma$ , as if $R<\gamma/2$ we may simply instead construct a code of greater rate $\gamma/2$ , and if $R>1-\gamma$ then the desired relative distance satisfies $\delta<0$ , which is trivially achievable. For completeness below we give explicit constants, which we do not attempt to optimize.

•

Let $Q_{\text{out}}^{0}$ be a $[[n_{0},k_{0}]]_{q_{0}}$ quantum Reed-Solomon code of rate $R_{\text{out}}=k_{0}/n_{0}=1-\gamma/20$ and relative distance $\delta_{\text{out}}=(1-R_{\text{out}})/2$ . We may assume that $n_{0}=\Theta(q_{0})$ , for instance by choosing $\mathbb{F}_{q_{0}}$ to be a field of characteristic $2$ so that we may take $q_{0}/2\leq n_{0}\leq q_{0}$ .
•
Set
- –
  
  $q_{\text{in}}=2^{200/\gamma}=2^{O(1/\gamma)}$
- –
  
  $\ell=q_{\text{in}}^{100/\gamma}=2^{O(1/\gamma^{2})}$
- –
  
  $s=100/\gamma\cdot\log(\ell/\gamma)=O(1/\gamma^{3})$
- –
  
  $m=100s/\gamma=O(1/\gamma^{4})$ .
Let $Q_{\text{out}}$ be the $[[n_{\text{out}},k_{\text{out}}]]_{q_{\text{out}}}$ code defined to be the $m$ -folding of $Q_{\text{out}}^{0}$ (see Section 3.1).
•

Let $Q_{\text{in}}$ be a $[[n_{\text{in}},k_{\text{in}}]]_{q_{\text{in}}}$ CSS code of rate $R_{\text{in}}=R+\gamma/20$ and dimension $k_{\text{in}}=\log_{q_{\text{in}}}q_{\text{out}}$ that has relative distance $\geq\delta_{\text{in}}=(1-R_{\text{in}}-\gamma/10)/2$ and consists of two classical $(\delta_{\text{in}},\ell)$ list-decodable codes, so that $Q_{\text{in}}$ $(\delta_{\text{in}},\ell^{2})$ list-decodable. By A.2, a random CSS code satisfies these properties with probability $1-q_{\text{in}}^{-\Omega(\gamma n)}$ .
•

Let $\gamma_{0}=\gamma^{2}/1000$ , $r=4/\gamma_{0}^{2}=O(1/\gamma^{4})$ , and let $G$ be an $r$ -regular $\gamma_{0}$ -pseudorandom bipartite graph.
•

As described in Section 5.2, let $Q_{\diamond}=Q_{\text{out}}\diamond Q_{\text{in}}$ , and let $Q=\pi_{G}(Q_{\diamond})$ be our final construction.

A direct application of Proposition 5.4 implies that $Q$ has relative distance $\geq\delta$ . We now show that $Q$ is efficiently $(\delta,L)$ list-decodable. For this purpose, observe that $Q_{\diamond}$ is the concatenation of the CSS codes $Q_{\text{out}}=\text{CSS}(C_{1}^{\text{out}},C_{2}^{\text{out}})$ and $Q_{\text{in}}=\text{CSS}(C_{1}^{\text{in}},C_{2}^{\text{in}})$ , and thus by 2.3,

Q=\text{CSS}\left(C_{1}=\pi_{G}(C_{1}^{\text{out}}\diamond(C_{1}^{\text{in}}/{C_{2}^{\text{in}}}^{\perp})),\;C_{2}=\pi_{G}(C_{2}^{\text{out}}\diamond(C_{2}^{\text{in}}/{C_{1}^{\text{in}}}^{\perp}))\right),

Therefore by Theorem 3.2, it suffices to show that $C_{1}/C_{2}^{\perp}$ and $C_{2}/C_{1}^{\perp}$ above are efficiently $(\delta,\sqrt{L})$ list-decodable in the sense of Definition 3.3. By symmetry of the construction, it suffices to consider $C_{1}/C_{2}^{\perp}$ , as $C_{2}/C_{1}^{\perp}$ is identical. Then our goal is to show that given a corrupted codeword $x$ of $C_{1}$ , there exists an efficient algorithm that outputs a list of size $\leq\sqrt{L}$ containing a representative of every coset in $C_{1}/C_{2}^{\perp}$ that intersects the Hamming ball $B_{\delta n}(x)$ of radius $\delta n$ centered at $x$ . Recall that then subtracting $x$ from each list element yields the desired list of stabilizer-distinct $X$ error operators for quantum list-decoding as stated in Definition 3.2; the $Z$ error operators are obtained by analogously list-decoding $C_{2}/C_{1}^{\perp}$ .

The desired list-decoding algorithm is as follows. Let $\alpha_{\text{in}}=\delta_{\text{in}}$ and $\alpha_{\text{out}}=\gamma/50$ . First, for each $i\in[n_{\text{out}}]$ , we apply a brute force search to compute the list $S_{i}\subseteq[q_{\text{out}}]=[q_{\text{in}}^{k_{\text{in}}}]\cong C_{1}^{\text{in}}/{C_{2}^{\text{in}}}^{\perp}$ of all inner code messages whose encodings differ from the $i$ th inner code block of $\pi_{G}^{-1}(x)$ in at most $\alpha_{\text{in}}$ -fraction of positions. Then we apply the list-recovery algorithm given by Theorem 6.1 to $S_{1},\dots,S_{n_{\text{out}}}$ , and output the (encodings into $C_{1}$ of the) returned list. Recall that when we re-encode the inner code, we apply the maps $\mathsf{Enc}_{1}^{\text{in}}$ and $\mathsf{Enc}_{2}^{\text{in}}$ described in Section 2.3 that send outer code symbols to cosets, and then we may select an arbitrary element from each coset.

The brute force searches over the inner code together take $O(n_{\text{out}}\cdot q_{\text{out}})\leq n^{O(m)}=n^{O(1/\gamma^{4})}$ time, and the outer list-recovery takes $(n_{\text{out}}m)^{O(s)}\leq n^{O(1/\gamma^{3})}$ time, so the overall runtime is $n^{O(1/\gamma^{4})}$ .

To show correctness, assume that $x$ is obtained by corrupting at most $\delta$ -fraction of the symbols in some codeword $c\in C_{1}$ . It suffices to show that the list returned by the above algorithm includes an element of the coset $c+C_{2}^{\perp}$ . By Proposition 5.4 and by the list-decodability of $C_{1}^{\text{in}}$ , at most $\alpha_{\text{out}}$ -fraction of the inner decodings return a list that does not contain the respective component of $c$ . Thus by Theorem 6.2, the final list returned by the algorithm will contain $c$ , up to addition by some element of $\pi_{G}(({C_{2}^{\text{in}}}^{\perp})^{\oplus n_{\text{out}}})\subseteq C_{2}^{\perp}$ from the re-encoding step described above. Also observe that by Theorem 6.2, the returned list will have size at most $(n_{\text{out}}m)^{O(s)}\leq n^{O(1/\gamma^{3})}$ .

It remains to be shown that $Q$ can be constructed in time $n^{O(1/\gamma^{4})}$ with failure probability $2^{-\Omega(n)}$ . The folded Reed-Solomon code is explicit, so the construction algorithm simply needs to find an appropriate inner CSS code $Q_{\text{in}}$ . By A.2, a random choice of $Q_{\text{in}}$ works with probability $>1/2$ , so trying $n$ random codes and checking the distance and list-decodability of each one by brute force gives the desired construction algorithm. ∎

7 AQEC without List Recovery

This section presents a construction of efficient AQECCs that avoid the need for list recovery. In fact, the only algorithmic ingredient this construction relies on is an efficient unique-decoder for an asymptotically good code, as the construction only performs list-decoding on a small inner code where a brute force search is sufficient.

The main idea of this construction is to concatenate an outer high-rate constant-distance unique-decodable QECC with an inner AQECC that permits exact unique decoding with high probability almost up to the Singleton bound. Specifically, for the inner code we use the concatenation of a quantum list-decodable code near the Singleton bound with a PTC, to ensure (inefficient) unique decodability near the Singleton bound with high probability for any fixed error. The inefficiency here is not a concern due to the small block length of the inner code. We then apply AEL distance amplification to boost the distance of the concatenated code almost to the Singleton bound.

We now show how to construct private AQECCs approaching the Singleton bound. Theorem 4.7 then gives the desired non-private AQECCs.

Theorem 7.1.

For any given $\gamma>0$ and $0<R<1$ , let $\delta_{\text{out}}>0$ be such that there is an infinite explicit family of stabilizer codes $Q_{0}$ of rate $1-\gamma/4$ and alphabet size $q_{0}$ that are unique-decodable from errors acting on $\delta_{\text{out}}$ fraction of the components in $f(n_{0}\log q_{0})$ time for some increasing function $f:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ , where $n_{0}$ denotes the block length.

Then there exists an infinite explicit family of private $((1-R-\gamma)/2,2^{-\Omega(\delta_{\text{out}}n)})$ -AQECCs $Q$ of rate $R$ , alphabet size $q=\max\{q_{0},2^{1/\gamma^{2}\delta_{\text{out}}}\}^{O(1/\gamma)}$ , private key length $O(\gamma^{2}\cdot n\log q)$ bits, and decoding time $f(n\log q)+O(nq^{2})$ , where $n$ denotes the block length.

Proof.

We may assume that $R\leq 1-\gamma$ , as otherwise the decoding radius in the theorem statement is $0$ . We may also assume that $R\geq\gamma/2$ , as otherwise we may simply construct an AQECC of larger rate $\gamma/2$ using the argument below for updated parameters $R^{\prime}=\gamma/2$ and $\gamma^{\prime}=\gamma/2$ ; such a change only affects the resulting code’s parameters by constant factors in the $R^{\prime}$ and $\gamma^{\prime}$ coefficients.

We construct $Q$ as follows. Below, we ignore rounding issues when choosing integer-valued parameters for ease of presentation; such rounding only affects the resulting bounds by constant factors. For completeness we give explicit constants, which we do not attempt to optimize.

•

Let $R_{\text{in}}=R+26\gamma/100$ , $\delta_{\text{in}}=1-R_{\text{in}}-\gamma/40$ $q_{\text{in}}=2^{100/\gamma}$ , $\ell=q_{\text{in}}^{400/\gamma}=2^{O(1/\gamma^{2})}$ $\gamma_{0}=\gamma\sqrt{\delta_{\text{out}}}/500$ , $n_{\text{in}}=\max\{(2/\gamma)\log q_{0}/\log q_{\text{in}},4/\gamma_{0}^{2}\}=\max\{\Theta(\log q_{0}),\Theta(1/\gamma^{2}\delta_{\text{out}})\}$ . Let $Q_{\text{in}}$ be an $[[n_{\text{in}},k_{\text{in}}]]_{q_{\text{in}}}$ CSS code of rate $R_{\text{in}}$ and relative distance $\geq\delta_{\text{in}}$ that is $(\delta_{\text{in}},\ell)$ quantum list-decodable. By A.2, a random CSS code satisfies these properties with probability $\geq 1-q_{\text{in}}^{-\Omega(\gamma n)}\geq 1/2$ . Such a code can be found via a brute force search in time $q_{\text{in}}^{O(n_{\text{in}}^{2})}=\max\{2^{O((\log q_{0})^{2}/\gamma)},2^{O(1/\gamma^{5}\delta_{\text{out}}^{2})}\}$ , which is constant with respect to $n$ .
•

Let $P_{\text{in}}=\{P_{\text{in}}^{\kappa}:\kappa\in K\}$ be a $\delta_{\text{out}}/10\ell$ -PTC of block length $n_{P}=k_{\text{in}}$ , rate $R_{P}\geq 1-\gamma/100$ , (so message length is $k_{P}=R_{P}n_{P}$ ), alphabet size $q_{\text{in}}$ , and private key set of size $|K|=q_{\text{in}}^{\lambda}$ for $\lambda=500(1/\gamma+\log(1/\delta_{\text{out}}))+(\gamma/100)\log n_{P}$ . Such a PTC was constructed by [BCG⁺02], as stated in Theorem 4.2.
•

Let $q_{\text{out}}=q_{\text{in}}^{k_{P}}\geq q_{\text{in}}^{\gamma n_{\text{in}}/2}\geq q_{0}$ , and let $Q_{\text{out}}$ be the $[[n_{\text{out}},k_{\text{out}},\delta_{\text{out}}]]_{q_{\text{out}}}$ code of rate $R_{\text{out}}=1-\gamma/4$ obtained by reblocking (that is, folding) the code $Q_{0}$ defined in the theorem statement to increase the alphabet size from $q_{0}\leq q_{\text{out}}$ to $q_{\text{out}}$ .
•

Let $q=q_{\text{in}}^{n_{\text{in}}}$ , and for every $\vec{\kappa}\in K^{n}$ , define the $[[n,k]]_{q}$ code $Q_{\diamond}^{\vec{\kappa}}=\bigotimes_{i=1}^{n}(Q_{\text{in}}\circ P_{\text{in}}^{\kappa_{i}})\circ Q_{\text{out}}$ . That is, $Q_{\diamond}$ has encoding map $\mathsf{Enc}_{Q_{\diamond}^{\vec{\kappa}}}=\mathsf{Enc}_{Q_{\text{in}}}^{\otimes n}\circ\bigotimes_{i=1}^{n}\mathsf{Enc}_{P_{\text{in}}^{\kappa_{i}}}\circ\mathsf{Enc}_{Q_{\text{out}}}$ . Here $\mathsf{Enc}_{Q_{\diamond}^{\vec{\kappa}}}$ takes as input a message state and the classical private key $\vec{\kappa}$ , the latter of which consists of $n$ independent private keys for the $n$ respective calls to $\mathsf{Enc}_{P_{\text{in}}}$ .
•

Let $G$ be an $n_{\text{in}}$ -regular $\gamma_{0}$ -pseudorandom bipartite graph, and for $\vec{\kappa}\in K^{n}$ let $Q^{\vec{\kappa}}=\pi_{G}(Q_{\diamond}^{\vec{\kappa}})$ , where $\pi_{G}:[n]\times[n_{\text{in}}]\rightarrow[n]\times[n_{\text{in}}]$ is the permutation specified by $G$ as described in Section 5.1.

We now show that the private code $Q=\{Q^{\vec{\kappa}}:\vec{\kappa}\in K^{n}\}$ defined above has the desired properties. By definition, $Q$ has rate $R_{\text{out}}R_{P}R_{\text{in}}\geq R$ , alphabet size $q=2^{O(1/\gamma^{3}\delta_{\text{out}})}$ , and private key length $n\cdot\log(q_{\text{in}}^{\lambda})\leq O(n(1/\gamma)(1/\gamma+\log(1/\delta_{\text{out}})+\gamma\log n_{\text{in}}))\leq O(\gamma^{2}\cdot n\log q)$ , where this final inequality uses the fact that $\delta_{\text{out}}\leq\gamma/8$ by the quantum Singleton bound for $Q_{0}$ , and the fact that $q=q_{\text{in}}^{n_{\text{in}}}$ with $n_{\text{in}}\geq 4/\gamma_{0}^{2}=\Theta(1/\gamma^{2}\delta_{\text{out}})$ .

It remains to be shown that $Q$ has a decoding algorithm with the desired error and efficiency parameters. We define the following natural decoding algorithm $\mathsf{Dec}_{Q}^{\vec{\kappa}}$ . Let $\mathsf{Dec}_{\text{in}}^{\kappa}=\mathsf{Enc}_{Q_{\text{in}\circ P_{\text{in}}^{\kappa}}}^{\dagger}\circ\widetilde{\mathsf{Dec}}_{\text{in}}^{\kappa}$ be the brute force decoding algorithm for the composed stabilizer code $Q_{\text{in}}\circ P_{\text{in}}^{\kappa}$ . Here $\widetilde{\mathsf{Dec}}_{\text{in}}^{\kappa}$ first performs a syndrome measurement for $Q_{\text{in}}\circ P_{\text{in}}^{\kappa}$ and finds all stabilizer-distinct errors of weight $\leq\delta_{\text{in}}$ consistent with the syndrome. If there is a unique such error $E$ (up to multiplication by stabilizers), the algorithm applies $E^{\dagger}$ to the measured state to correct the error; otherwise, it fails and gives an arbitrary output. Let $\mathsf{Dec}_{Q_{\text{out}}}$ denote the unique-decoding algorithm for $Q_{\text{out}}$ provided by the theorem statement. Then we let $\mathsf{Dec}_{Q^{\vec{\kappa}}}=\mathsf{Dec}_{Q_{\text{out}}}\circ\bigotimes_{i=1}^{n}\mathsf{Dec}_{\text{in}}^{\kappa_{i}}\circ\pi_{G}^{-1}$ .

As $Q^{\vec{\kappa}}$ is the concatenation of stabilizer codes, the decoding algorithm described above can be implemented as a single syndrome measurement followed by a classical algorithm that computes a Pauli error, whose inverse can then be applied to the measured state to restore the initial code state with high probability. However, for the purpose of our analysis, it is helpful to assume that the inner code syndromes are measured before the outer code syndrome, as then we can apply Lemma 4.1 (and its composable generalization in Theorem C.1) to the inner codes.

Each of the inner decodings $\mathsf{Dec}_{\text{in}}^{\kappa_{i}}$ runs in time $O(q^{2})$ because the brute force search may simply iterate through all possible Pauli errors. Thus the overall runtime of $\mathsf{Dec}_{Q}$ is $f(n)+O(nq^{2})$ .

It remains to be shown that $Q$ is a private $(\delta,2^{-\Omega(\delta_{\text{out}}n)})$ -AQECC for $\delta=(1-R-\gamma)/2$ . For this purpose, we will show that for every error channel $\mathcal{A}$ acting on some subset $T\subseteq[n]$ of the code components with $|T|\leq\delta n$ , it holds with probability $2^{-\Omega(\delta_{\text{out}}n)}$ over the uniformly random choice of key $\vec{\kappa}\in K^{n}$ and over the randomness from measurements in the decoding algorithm that for every message $\ket{\phi}$ , we have

\mathsf{Dec}_{Q^{\vec{\kappa}}}(\mathcal{A}(\mathsf{Enc}_{Q^{\vec{\kappa}}}(\ket{\phi})))=\ket{\phi}.

(29)

As a point of notation, above we are viewing the channel $\mathsf{Dec}_{Q^{\vec{\kappa}}}\circ\mathcal{A}\circ\mathsf{Enc}_{Q^{\vec{\kappa}}}$ as a procedure that outputs a classical ensemble of pure quantum states. Thus in the notation of density matrices, we would equivalently like to show that

\mathsf{Dec}_{Q^{\vec{\kappa}}}\circ\mathcal{A}\circ\mathsf{Enc}_{Q^{\vec{\kappa}}}(\ket{\phi}\bra{\phi})=(1-p_{\text{bad}})\ket{\phi}\bra{\phi}+p_{\text{bad}}\rho_{\text{bad}}

for some $0\leq p_{\text{bad}}\leq 2^{-\Omega(\delta_{\text{out}}n)}$ and some density matrix $\rho_{\text{bad}}$ .

Note that we allow the message $\ket{\phi}$ to be an arbitrary pure state on the joint system consisting of the message register and an arbitrarily large side register, to which none of the encoding, decoding, or error channels have access. Allowing $\ket{\phi}$ to be entangled with a side register in this way implies that our proof gives the desired diamond norm bound in Definition 1.5. However, the side register effictively has no effect in the argument below, so we will not need to reference it further.

Letting $\ket{\psi}=\pi_{G}^{-1}\mathsf{Enc}_{Q^{\vec{\kappa}}}(\ket{\phi})$ and $\mathcal{A}_{G}=\pi_{G}^{-1}\mathcal{A}\pi_{G}$ , then (29) is equivalent to

\mathsf{Dec}_{Q_{\text{out}}}\left(\bigotimes_{i=1}^{n}\mathsf{Dec}_{\text{in}}^{\kappa_{i}}\right)\mathcal{A}_{G}(\ket{\psi})=\ket{\phi}.

Recall that we may decompose

\mathcal{A}_{G}(\ket{\psi})=\sum_{\nu}A_{\nu}\ket{\psi}\otimes\ket{\nu},

where $\nu$ ranges over a set of orthonormal environment states, and the $A_{\nu}$ are some operators such that $\sum_{\nu}A_{\nu}^{\dagger}A_{\nu}=I$ . Then it suffices to show for each $\nu$ , with probability $\geq 1-2^{-\Omega(\delta_{\text{out}}n)}$ we have

\mathsf{Dec}_{Q_{\text{out}}}\left(\bigotimes_{i=1}^{n}\mathsf{Dec}_{\text{in}}^{\kappa_{i}}\right)A_{\nu}\ket{\psi}=\ket{\phi}.

(30)

Define $S\subseteq[n]\times[n_{\text{in}}]$ by $S=\pi_{G}^{-1}(T\times[n_{\text{in}}])$ . Because $\delta_{\text{in}}-\gamma_{0}/\sqrt{\delta_{\text{out}}/100}<\delta$ , Lemma 5.2 implies that the set

S^{\prime}=\{i\in[n]:|S\cap(\{i\}\times[n_{\text{in}}])|\geq\delta_{\text{in}}\}.

has $|S^{\prime}|/n\leq\delta_{\text{out}}/100$ . That is, the $\geq 1-\delta_{\text{out}}/100$ fraction of inner blocks with $i\notin S^{\prime}$ have error rate from $\mathcal{A}_{G}$ below the list decoding radius $\delta_{\text{in}}$ of $Q_{\text{in}}$ .

Fix $\nu$ . Let $\mathcal{P}_{S}\subseteq\mathcal{P}_{q}^{n}$ denote the set of Paulis supported inside $S$ . Then we may decompose $A_{\nu}=\sum_{E\in\mathcal{P}_{S}}a_{E}E$ for some coefficeints $a_{e}$ .

As the left hand side of Equation 30 does not depend on the order in which the inner blocks are decoded, assume that we first sequentially apply $\widetilde{\mathsf{Dec}}_{\text{in}}^{\kappa_{i}}$ to the inner code blocks $i\notin S^{\prime}$ of $\mathcal{A}_{G}(\ket{\psi})$ . Then for a given such $i\notin S^{\prime}$ , $\widetilde{\mathsf{Dec}}_{\text{in}}^{\kappa_{i}}$ is applied to the $i$ th block of $\left(\bigotimes_{j\notin S^{\prime}:j<i}\widetilde{\mathsf{Dec}}_{\text{in}}^{\kappa_{j}}\right)A_{\nu}(\ket{\psi})$ . We may let

A_{\nu}^{(i)}\ket{\psi}=\left(\bigotimes_{j\notin S^{\prime}:j\leq i}\widetilde{\mathsf{Dec}}_{\text{in}}^{\kappa_{j}}\right)A_{\nu}(\ket{\psi})=\sum_{E\in\mathcal{P}_{S}}a_{E}^{(i)}E\ket{\psi}

for some coefficients $a_{E}^{(i)}$ , which are random variables depending on the choices of $\kappa_{j}$ as well as on the outcomes of measurements in $\widetilde{\mathsf{Dec}}_{\text{in}}^{\kappa_{j}}$ for $j\notin S^{\prime}$ with $j\leq i$ . Note that for a fixed $i$ , the random variables $a_{E}^{(i)}$ over $E\in\mathcal{P}_{S}$ may be correlated.

For every $i\notin S^{\prime}$ , since $\mathcal{A}_{G}$ and therefore $A_{\nu}$ acts on fewer than $\delta_{\text{in}}$ fraction of the components in block $i$ , local indistinguishability guarantees (C.2) that the distribution of the coefficients $a_{E}^{(i-1)}$ does not depend on the message encoded by $Q_{\text{in}}$ in block $i$ . Thus in particular, the distribution of $a_{E}^{(i-1)}$ does not depend on the choice of $\kappa_{i}\in K$ .

For an inner code block $i\in[n]$ , if $A_{\nu}^{(j)}=\sum_{E\in\mathcal{P}_{S}}a_{E}^{(j)}E$ is such that $a_{E}^{(j)}=0$ for every $E$ with $i$ th block $E_{i}$ not equal to the identity, we say that block $i$ is error-free in $A_{\nu}^{(j)}$ . Recall the definition of $\widetilde{\mathsf{Dec}}_{\text{in}}^{\kappa}$ in Algorithm 1. By Lemma 4.1 and its composable generalization in Theorem C.1, for each $i\notin S^{\prime}$ , conditioned on the values of $a_{E}^{(i-1)}$ , it holds with probability $\geq 1-\delta_{\text{out}}/10$ over the randomness in $\kappa_{i}$ and in the syndrome measurement that $\widetilde{\mathsf{Dec}}_{\text{in}}^{\kappa_{i}}$ successfully corrects the error on inner code block $i$ , meaning that block $i$ is error-free in $A_{\nu}^{(i)}$ . Furthermore, by Remark C.1, if block $i$ is error-free in $A_{\nu^{(i)}}$ , then block $i$ is error-free in $A_{\nu}^{(j)}$ for all $j\geq i$ , so that in particular block $i$ is error-free in $A_{\nu}^{(n)}$ . It follows that

	$\displaystyle\Pr[A_{\nu}^{(n)}\text{ has }\geq\delta_{\text{out}}n\text{ blocks }i\notin S^{\prime}\text{ that are not error-free}]$	$\displaystyle\leq\Pr[\operatorname{Bin}(n-\|S^{\prime}\|,\delta_{\text{out}}/10)+\|S^{\prime}\|\geq\delta_{\text{out}}n]$
		$\displaystyle\leq e^{-\delta_{\text{out}}n/2},$

where the final inequality above follows from the Chernoff bound. Thus because by definition $\ket{\psi}=(\bigotimes_{i=1}^{n}\mathsf{Enc}_{Q_{\text{in}}\circ P_{\text{in}}^{\kappa_{i}}})\mathsf{Enc}_{Q_{\text{out}}}\ket{\phi}$ , it follows that with probability $\geq 1-e^{-\delta_{\text{out}}n/2}$ , the state

\left(\bigotimes_{i=1}^{n}\mathsf{Dec}_{\text{in}}^{\kappa_{i}}\right)A_{\nu}\ket{\psi}=\left(\bigotimes_{i=1}^{n}\mathsf{Enc}_{Q_{\text{in}}\circ P_{\text{in}}^{\kappa_{i}}}^{\dagger}\right)\left(\bigotimes_{i\in S^{\prime}}\widetilde{\mathsf{Dec}}_{\text{in}}^{\kappa_{i}}\right)A_{\nu}^{(n)}\ket{\psi}

is equal to $A^{\prime}\mathsf{Enc}_{Q_{\text{out}}}\ket{\phi}$ for some operator $A^{\prime}$ that acts as the identity on $>1-\delta_{\text{out}}$ fraction of the components $i\in[n]$ . In this case we are guaranteed that $\mathsf{Dec}_{Q_{\text{out}}}A^{\prime}\mathsf{Enc}_{Q_{\text{out}}}\ket{\phi}=\ket{\phi}$ , so Equation 30 holds with probability $\geq 1-e^{-\delta_{\text{out}}n/2}$ , as desired.

∎

The following corollary instantiates Theorem 7.1 with two examples of suitable outer codes, namely distance-amplified concatenated Reed-Solomon codes and asymptotically good quantum LDPC codes.

Corollary 7.2.

For every $\gamma>0$ and $0<R<1$ , we have:

1.

There exists an infinite explicit family of private $((1-R-\gamma)/2,2^{-\Omega(\gamma n)})$ -AQECCs of rate $R$ , alphabet size $q=2^{O(\frac{1}{\gamma^{4}}\log\frac{1}{\gamma})}$ , block length $n\geq q$ , private key length $O(\gamma^{2}\cdot n\log q)$ bits, and decoding time $O(n\log q)^{3}$ .
2.

For sufficiently small $\delta_{\text{out}}=\delta_{\text{out}}(\gamma)>0$ , there exists an infinite explicit family of private LDPC $((1-R-\gamma)/2,2^{-\Omega(\delta_{\text{out}}n)})$ -AQECCs $Q$ of rate $R$ , alphabet size $q=2^{O(1/\gamma^{3}\delta_{\text{out}})}$ , private key length $O(\gamma^{2}\cdot n\log q)$ bits, and decoding time $O_{\gamma}(n)$ .

For the first item in Corollary 7.2, we will concatenate a Reed-Solomon outer code with an inner code from the ensemble of codes given below.

Lemma 7.3.

For a prime power $q$ and positive integers $r,s$ , let $C_{1},C_{2}\subseteq\mathbb{F}_{q^{r}}^{s}$ be $(s-1)$ -dimensional subspaces chosen uniformly at random subject to the constraint that $C_{1}^{\perp}\subseteq C_{2}$ . Let $Q=\text{CSS}_{\mathbb{F}_{q}}(C_{1},C_{2})$ be the CSS code of block length $n=rs$ , rate $R=1-2/s$ , and local dimension $\mathbb{F}_{q}$ obtained by associating $\mathbb{F}_{q^{r}}\cong\mathbb{F}_{q}^{r}$ . Then for every $\gamma>0$ , it holds with probability $\geq 1-2q^{-\gamma n}$ that $Q$ has relative distance at least $H_{q}^{-1}(1/s-\gamma)$ , where $H_{q}$ denotes the $q$ -ary entropy function.

Proof.

By definition for $i=1,2$ , the code $C_{i}$ contains any given $x\in\mathbb{F}_{q^{r}}^{s}\cong\mathbb{F}_{q}^{rs}$ with probability $(q^{r(s-1)}-1)/(q^{rs}-1)\leq q^{-r}$ . Therefore the chance that $C_{i}$ contains some $x$ of Hamming weight $\leq H_{q}^{-1}(1/s-\gamma)$ is at most $q^{-r}\cdot|B_{0}(H_{q}^{-1}(1/s-\gamma))|\leq q^{-r}\cdot q^{rs(1/s-\gamma)}=q^{-rs\gamma}$ . Union bounding over $i=1,2$ , it follows that both $C_{1},C_{2}$ , and therefore $Q$ , has relative distance at least $H_{q}^{-1}(1/s-\gamma)$ with probability $\geq 1-2q^{-rs\gamma}$ . ∎

The codes in Lemma 7.3 may be viewed as a quantum analogue of the Wozencraft ensemble, as they provide a derandomization of random CSS codes that still approach the quantum Singleton bound over large alphabets.

Lemma 7.4.

For every $\gamma>0$ , there exists an explicit infinite family of $[[n,k]]_{q}$ codes $Q$ of rate $R=k/n\geq 1-\gamma$ , local dimension $q=2^{O(\frac{1}{\gamma^{3}}\log\frac{1}{\gamma})}$ , and block length $n\geq q$ that are unique-decodable from errors acting on $\Omega(\gamma)$ fraction of the components in time $O(n\log q)^{3}$ .

Proof.

We construct $Q$ by applying the AEL construction in Proposition 5.4 to the concatenation of an outer Reed-Solomon code of rate $1-\gamma/2$ with an inner code of rate $1-\gamma/2$ from the ensemble in Lemma 7.3. Specifically, let $Q_{\text{in}}=\text{CSS}_{\mathbb{F}_{q_{\text{in}}}}(C_{1},C_{2})$ be a $[[n_{\text{in}},k_{\text{in}},\Delta_{\text{in}}n_{\text{in}}]]_{q_{\text{in}}}$ code from the ensemble in Lemma 7.3 of rate $R_{\text{in}}\geq 1-\gamma/2$ , local dimension $q_{\text{in}}=1/\gamma$ , and relative distance $\Delta_{\text{in}}\geq H_{q_{\text{in}}}^{-1}(\gamma/8)\geq\Omega(\gamma)$ . As described in Lemma 7.3, each of $C_{1},C_{2}$ is specified by a single parity check vector in $\mathbb{F}_{q_{\text{in}}^{r}}^{s}$ up to scalar multiplication by $\mathbb{F}_{q_{\text{in}}^{r}}$ . Therefore there are at most $2q_{\text{in}}^{k_{\text{in}}}$ possible choices for each of $C_{1},C_{2}$ , so there are at most $(2q_{\text{in}}^{k_{\text{in}}})^{2}$ possible choices for $Q$ . Computing the distance of each of $C_{1},C_{2}$ by brute force takes $O(q_{\text{in}}^{k_{\text{in}}})$ time, so a brute force search to find $Q_{\text{in}}$ takes $O(q_{\text{in}}^{3k_{\text{in}}})$ time.

Now let $Q_{\text{out}}$ be a $[[n_{\text{out}},k_{\text{out}}]]_{q_{\text{out}}}$ quantum Reed-Solomon code of rate $R_{\text{out}}=1-\gamma/2$ , and block length and local dimension $n_{\text{out}}=q_{\text{out}}=q_{\text{in}}^{k_{\text{in}}}$ . Then Proposition 5.4 implies that we may choose $\gamma_{0}=\Theta(\gamma^{3/2})$ , $r=4/\gamma_{0}^{2}$ , and $G$ an $r$ -regular $\gamma_{0}$ -pseudorandom bipartite graph such that the $[[n,k]]_{q}$ code $Q=\Pi_{G}(Q_{\text{out}}\circ Q_{\text{in}})$ has local dimension $q=q_{\text{in}}^{r}=2^{O(\frac{1}{\gamma^{3}}\log\frac{1}{\gamma})}$ and is decodable from adversarial errors acting on $\Omega(\gamma)$ fraction of the components. Furthermore, the decoding algorithm simply decodes the inner codes and then decodes the outer code. Brute force decoding in all inner code blocks takes time $O(n_{\text{out}})^{3}\leq O(n^{3})$ , and decoding the Reed-Solomon outer code can be done in time $O(n_{\text{out}}\log q_{\text{out}})^{3}\leq O(n\log q)^{3}$ . Thus the overall decoding algorithm takes $O(n\log q)^{3}$ time as desired.

Furthermore, $Q$ is explicit as we showed above that the inner code $Q_{\text{in}}$ can be constructed by a brute force search in time $O(q_{\text{out}}^{3})\leq O(n^{3})$ , and the quantum Reed-Solomon code $Q_{\text{out}}$ is explicit. ∎

Proof of Corollary 7.2.

1.

The result follows from Theorem 7.1 by letting $Q_{0}$ be a code of rate $1-\gamma/4$ and alphabet size $q_{0}=2^{O(\frac{1}{\gamma^{3}}\log\frac{1}{\gamma})}$ that is unique-decodable from errors acting on $\delta_{\text{out}}=\Omega(\gamma)$ fraction of the components in time $O(n_{0}\log q_{0})^{3}$ , as given in Lemma 7.4.
2.

The result follows form Theorem 7.1 by letting $Q_{0}$ be a family of asymptotically good quantum LDPC codes of local dimension $q_{0}=2$ that permits linear-time decoding. For instance, the codes of [PK22, LZ22c] have such a decoding algorithm [LZ22a].

∎

As described in Section 4.2, the private key of a private AQECC can be incorporated into the code using a classical robust secret sharing scheme. Specifically, Theorem 4.6 and Theorem 4.7 imply that the statement of Theorem 7.1 still holds when we remove the condition that the AQECC is private.

Corollary 7.5.

Define $\gamma,R,\delta_{\text{out}},Q_{0},f$ as in Theorem 7.1, and assume that $f(n)=\poly(n)$ so that $Q_{0}$ permits efficient decoding. Then there exists an infinite explicit family of $((1-R-\gamma)/2,2^{-\Omega(\delta_{\text{out}}n)})$ -AQECCs $Q$ of rate $R$ , alphabet size $q=\max\{q_{0},2^{1/\gamma^{2}\delta_{\text{out}}}\}^{O(1/\gamma)}$ that has efficient encoding and decoding algorithms.

Proof.

The result follows directly by applying the private AQECCs of Theorem 7.1 with the robust secret sharing schemes of Theorem 4.6 in Theorem 4.7. Specifically, as in the proof of Theorem 7.1, we may assume that $\gamma/2\leq R\leq 1-\gamma$ . Let $Q_{\text{priv}}$ be the private $((1-R_{\text{priv}}-\gamma_{\text{priv}})/2,2^{-\Omega(\delta_{\text{out}}n)})$ -AQECC from Theorem 7.1 of rate $R_{\text{priv}}=R+\gamma/2$ , block length $n$ , local dimension $q_{\text{priv}}=\max\{q_{0},2^{1/\gamma^{2}\delta_{\text{out}}}\}^{\Theta(1/\gamma)}$ , and with $\gamma_{\text{priv}}=c\gamma$ for a sufficiently small constant $0<c<1/2$ such that $Q_{\text{priv}}$ has private key length at most $\gamma^{2}/100\cdot n\log q_{\text{priv}}$ . Let $\mathsf{RSS}$ be the $((1-R_{\text{RSS}}-\gamma_{\text{RSS}})n/2,2^{-n})$ -robust secret sharing scheme from Theorem 4.6 of rate $R_{\text{RSS}}=\gamma/2$ , block length (number shares) $n$ , share size $a_{\text{RSS}}=q_{\text{priv}}^{\gamma/5}$ , and with $\gamma_{\text{RSS}}=\gamma/2$ . Note that we may choose $a_{\text{RSS}}=q_{\text{priv}}^{\gamma/5}$ because the quantum Singleton bound implies that $\delta_{\text{out}}\leq\gamma/8$ , so $q_{\text{priv}}\geq 2^{\Omega(1/\gamma^{4})}$ , and thus $q_{\text{priv}}^{\gamma/5}\geq 2^{\Omega(1/\gamma^{3})}\geq 2^{\tilde{O}(1/\gamma^{2})}$ is at least as large as the share size given by Theorem 4.6.

Then applying Theorem 4.7 with $Q_{\text{priv}}$ and $\mathsf{RSS}$ yields an AQECC $Q$ with the desired parameters. Specifically, because by construction the number of bits in the RSS message is $nR_{\text{RSS}}\log a_{\text{RSS}}=\gamma^{2}/10\cdot n\log q_{\text{priv}}$ , which is at least as large as the private key length of $Q_{\text{priv}}$ , we may indeed apply Theorem 4.7 to obtain a $((1-R-\gamma)/2,2^{-\Omega(\delta_{\text{out}}n)})$ -AQECC of rate $R_{\text{priv}}/(1+\gamma/5)\geq R$ and alphabet size $q=q_{\text{priv}}^{1+\gamma/5}\leq\max\{q_{0},2^{1/\gamma^{2}\delta_{\text{out}}}\}^{O(1/\gamma)}$ . ∎

Thus in particular we immediately obtain the following non-private analogue of Item 1 of Corollary 7.2, again by letting $Q_{0}$ be the code from Lemma 7.4.

Corollary 7.6.

For every $\gamma>0$ and $0<R<1$ , there exists an infinite explicit family of $((1-R-\gamma)/2,2^{-\Omega(\gamma n)})$ -AQECCs of rate $R$ , alphabet size $q=2^{O(\frac{1}{\gamma^{4}}\log\frac{1}{\gamma})}$ and block length $n\geq q$ that has efficient encoding and decoding algorithms.

Acknowledgements

We thank Venkatesan Guruswami, Andrea Coladangelo, Omar Alrabiah, Debbie Leung, James Bartusek and Umesh Vazirani for fruitful discussions. We also thank Fermi Ma, Markus Grassl, and Andreas Winter for helpful comments on earlier drafts of the paper.

TB and LG acknowledge support by the National Science Foundation Graduate Research Fellowship under Grant No. DGE 2146752.

References

[ABO08] Dorit Aharonov and Michael Ben-Or. Fault-tolerant quantum computation with constant error rate. SIAM J. Comput., 38:1207–1282, 2008.
[AEL95] N. Alon, J. Edmonds, and M. Luby. Linear time erasure codes with nearly optimal recovery. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, FOCS ’95, page 512, USA, 1995. IEEE Computer Society.
[AG06] Andris Ambainis and Daniel Gottesman. The minimum distance problem for two-way entanglement purification. IEEE Transactions on Information Theory, 52:748–753, 2006.
[AK01] Alexei E. Ashikhmin and Emanuel Knill. Nonbinary quantum stabilizer codes. IEEE Trans. Inf. Theory, 47:3065–3072, 2001.
[Aud06] Koenraad MR Audenaert. A sharp fannes-type inequality for the von Neumann entropy. arXiv preprint quant-ph/0610146, 2006.
[BCG⁺02] Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam Smith, and Alain Tapp. Authentication of quantum messages. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 449–458. IEEE, 2002.
[BDH06] Todd A. Brun, Igor Devetak, and Min-Hsiu Hsieh. Correcting quantum errors with entanglement. Science, 314:436 – 439, 2006.
[Bén09] Cédric Bény. Conditions for the approximate correction of algebras. In TCQ, 2009.
[BK00] Howard Barnum and Emanuel Knill. Reversing quantum dynamics with near-optimal quantum and classical fidelity. Journal of Mathematical Physics, 43:2097–2106, 2000.
[BKN00] Howard Barnum, Emanuel Knill, and Michael A. Nielsen. On quantum fidelities and channel capacities. IEEE Trans. Inf. Theory, 46:1317–1329, 2000.
[BO10] Cédric Bény and Ognyan Oreshkov. General conditions for approximate quantum error correction and near-optimal recovery channels. Physical review letters, 104(12):120501, 2010.
[CDD⁺99] Ronald Cramer, Ivan Damgård, Stefan Dziembowski, Martin Hirt, and Tal Rabin. Efficient multiparty computations secure against an adaptive adversary. In EUROCRYPT, 1999.
[CDD⁺15] Ronald Cramer, Ivan Bjerre Damgård, Nico Döttling, Serge Fehr, and Gabriele Spini. Linear secret sharing schemes from error correcting codes and universal hash functions. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part II, volume 9057 of Lecture Notes in Computer Science, pages 313–336. Springer, 2015. doi:10.1007/978-3-662-46803-6\_11.
[CDF01] Ronald Cramer, Ivan Damgård, and Serge Fehr. On the cost of reconstructing a secret, or VSS with optimal reconstruction phase. In CRYPTO, 2001.
[CDF⁺08] Ronald Cramer, Yevgeniy Dodis, Serge Fehr, Carles Padró, and Daniel Wichs. Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors. In EUROCRYPT, 2008.
[CGL99] Richard Cleve, Daniel Gottesman, and Hoi-Kwong Lo. How to share a quantum secret. Physical Review Letters, 83:648–651, 1999.
[CGS05] Claude Crépeau, Daniel Gottesman, and Adam Smith. Approximate quantum error-correcting codes and secret sharing schemes. In Proceedings of the 24th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT’05, page 285–301, Berlin, Heidelberg, 2005. Springer-Verlag. doi:10.1007/11426639_17.
[CS96] Calderbank and Shor. Good quantum error-correcting codes exist. Physical review. A, Atomic, molecular, and optical physics, 54 2:1098–1105, 1996.
[Dev05] Igor Devetak. The private classical capacity and quantum capacity of a quantum channel. IEEE Transactions on Information Theory, 51:44–55, 2005.
[DHLV22] Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, and Thomas Vidick. Good quantum LDPC codes with linear time decoders. arXiv preprint arXiv:2206.07750, 2022.
[DJX14] Yang Ding, Lingfei Jin, and Chaoping Xing. Erasure list-decodable codes from random and algebraic geometry codes. IEEE Transactions on Information Theory, 60:3889–3894, 2014.
[DL12] Zeev Dvir and Shachar Lovett. Subspace evasive sets. Electron. Colloquium Comput. Complex., TR11, 2012.
[DS03] Igor Devetak and Peter W. Shor. The capacity of a quantum channel for simultaneous transmission of classical and quantum information. Communications in Mathematical Physics, 256:287–303, 2003.
[Eli57] Peter Elias. List decoding for noisy channels. In Technical Report 335. Research Laboratory of Electronics, MIT, 1957.
[For09] G. David Forney. Concatenated codes. Scholarpedia, 4:8374, 2009.
[GHW22] Markus Grassl, Felix Huber, and Andreas Winter. Entropic proofs of Singleton bounds for quantum error-correcting codes. IEEE Transactions on Information Theory, 2022.
[GI01] Venkatesan Guruswami and Piotr Indyk. Expander-based constructions of efficiently decodable codes. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 658–667. IEEE, 2001.
[GI02] Venkatesan Guruswami and Piotr Indyk. Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. In STOC ’02, 2002.
[GI03] Venkatesan Guruswami and Piotr Indyk. Linear time encodable and list decodable codes. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 126–135, 2003.
[GI04] Venkatesan Guruswami and Piotr Indyk. Linear-time list decoding in error-free settings: (extended abstract). In ICALP, 2004.
[GKO⁺18] Sivakanth Gopi, Swastik Kopparty, Rafael Oliveira, Noga Ron-Zewi, and Shubhangi Saraf. Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound. IEEE Transactions on Information Theory, 64(8):5813–5831, 2018.
[Got97] Daniel Gottesman. Stabilizer codes and quantum error correction. arXiv: Quantum Physics, 1997.
[GPT22] Shouzhen Gu, Christopher A Pattison, and Eugene Tang. An efficient decoder for a linear distance quantum LDPC code. arXiv preprint arXiv:2206.06557, 2022.
[GR08] Venkatesan Guruswami and Atri Rudra. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Transactions on Information Theory, 54:135–150, 2008.
[Gra20] Markus Grassl. Entanglement-assisted quantum communication beating the quantum Singleton bound. ArXiv, abs/2007.01249, 2020.
[GRZ22] Zeyu Guo and Noga Ron-Zewi. Efficient list-decoding with constant alphabet and list sizes. IEEE Transactions on Information Theory, 68:1663–1682, 2022.
[GS98] Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraic-geometric codes. Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), pages 28–37, 1998.
[Gur01] Venkatesan Guruswami. List decoding of error correcting codes. PhD thesis, Massachusetts Institute of Technology, 2001.
[Gur03a] Venkatesan Guruswami. List decoding from erasures: bounds and code constructions. 18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings., 49:2826–2833, 2003.
[Gur03b] Venkatesan Guruswami. List decoding with side information. 18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings., pages 300–309, 2003.
[Gur10] Venkatesan Guruswami. Cyclotomic function fields, Artin–Frobenius automorphisms, and list error correction with optimal rate. Algebra & Number Theory, 4:433–463, 2010.
[GW13] Venkatesan Guruswami and Carol Wang. Linear-algebraic list decoding for variants of Reed-Solomon codes. IEEE Transactions on Information Theory, 59(6):3257–3268, 2013.
[GX14] Venkatesan Guruswami and Chaoping Xing. Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets. Electron. Colloquium Comput. Complex., TR13, 2014.
[GX20] Venkatesan Guruswami and Chaoping Xing. Optimal rate list decoding over bounded alphabets using algebraic-geometric codes. ACM Journal of the ACM (JACM), 69:1 – 48, 2020.
[GXY17] Venkatesan Guruswami, Chaoping Xing, and Chen Yuan. Subspace designs based on algebraic function fields, 2017. URL: https://arxiv.org/abs/1704.05992, doi:10.48550/ARXIV.1704.05992.
[HP17] Patrick M. Hayden and Geoffrey Penington. Approximate quantum error correction revisited: introducing the alpha-bit. Communications in Mathematical Physics, 374:369–432, 2017.
[HRZW19] Brett Hemenway, Noga Ron-Zewi, and Mary Wootters. Local list recovery of high-rate tensor codes and applications. SIAM Journal on Computing, 49(4):FOCS17–157, 2019.
[HW08] Min-Hsiu Hsieh and Mark M. Wilde. Entanglement-assisted communication of classical and quantum information. IEEE Transactions on Information Theory, 56:4682–4704, 2008.
[HW18] Brett Hemenway and Mary Wootters. Linear-time list recovery of high-rate expander codes. Information and Computation, 261:202–218, 2018.
[JX14] Lingfei Jin and Chaoping Xing. A construction of new quantum MDS codes. IEEE Transactions on Information Theory, 60:2921–2925, 2014.
[KKKS06] Avanti Ketkar, Andreas Klappenecker, Santosh Kumar, and Pradeep Kiran Sarvepalli. Nonbinary stabilizer codes over finite fields. IEEE Transactions on Information Theory, 52:4892–4914, 2006.
[KL96] Emanuel Knill and Raymond Laflamme. Concatenated quantum codes. arXiv: Quantum Physics, 1996.
[KL97] Emanuel Knill and Raymond Laflamme. Theory of quantum error-correcting codes. Physical Review A, 55:900–911, 1997.
[KMRZS15] Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, 2015.
[KRRZ⁺19] Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, and Shashwat Silas. On list recovery of high-rate tensor codes. IEEE Transactions on Information Theory, 67:296–316, 2019.
[KSW08] Dennis Kretschmann, Dirk Schlingemann, and Reinhard F. Werner. The information-disturbance tradeoff and the continuity of Stinespring’s representation. IEEE Transactions on Information Theory, 54:1708–1717, 2008.
[KW08] Jon-Lark Kim and Judy L. Walker. Nonbinary quantum error-correcting codes from algebraic curves. Discret. Math., 308:3115–3124, 2008.
[Lan04] M. Langberg. Private codes or succinct random codes that are (almost) perfect. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 325–334, 2004. doi:10.1109/FOCS.2004.51.
[LB13] C. Lai and Todd A. Brun. Entanglement increases the error-correcting ability of quantum error-correcting codes. Physical Review A, 88:012320, 2013.
[LBW13] C. Lai, Todd A. Brun, and Mark M. Wilde. Duality in entanglement-assisted quantum error correction. IEEE Transactions on Information Theory, 59:4020–4024, 2013.
[LNCY97] Debbie W Leung, Michael A Nielsen, Isaac L Chuang, and Yoshihisa Yamamoto. Approximate quantum error correction can lead to better codes. Physical Review A, 56(4):2567, 1997.
[LS08] D. Leung and G. Smith. Communicating over adversarial quantum channels using quantum list codes. IEEE Trans. Inf. Theor., 54(2):883–887, feb 2008. URL: https://arxiv.org/pdf/quant-ph/0605086.pdf, doi:10.1109/TIT.2007.913433.
[LXW08] Zhuo Li, Lijuan Xing, and Xinmei Wang. Quantum generalized Reed-Solomon codes: unified framework for quantum MDS codes. ArXiv, abs/0812.4514, 2008.
[LZ22a] Anthony Leverrier and Gilles Zémor. Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes. arXiv preprint arXiv:2206.07571, 2022.
[LZ22b] Anthony Leverrier and Gilles Zémor. A parallel decoder for good quantum LDPC codes. arXiv preprint arXiv:2208.05537, 2022.
[LZ22c] Anthony Leverrier and Gilles Zémor. Quantum Tanner codes. arXiv preprint arXiv:2202.13641, 2022.
[MN12] Prabha Mandayam and Hui Khoon Ng. Towards a unified framework for approximate quantum error correction. Phys. Rev. A, 86:012335, Jul 2012. URL: https://link.aps.org/doi/10.1103/PhysRevA.86.012335, doi:10.1103/PhysRevA.86.012335.
[MW22] Manideep Mamindlapally and Andreas J. Winter. Singleton bounds for entanglement-assisted classical and quantum error correcting codes. 2022 IEEE International Symposium on Information Theory (ISIT), pages 85–90, 2022.
[NM10] Hui Khoon Ng and Prabha Mandayam. Simple approach to approximate quantum error correction based on the transpose channel. Phys. Rev. A, 81:062342, Jun 2010. URL: https://link.aps.org/doi/10.1103/PhysRevA.81.062342, doi:10.1103/PhysRevA.81.062342.
[PK22] Pavel Panteleev and Gleb Kalachev. Asymptotically good quantum and locally testable classical LDPC codes. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 375–388, 2022.
[RGB04] Martin Rötteler, Markus Grassl, and Thomas Beth. On quantum MDS codes. International Symposium onInformation Theory, 2004. ISIT 2004. Proceedings., pages 356–356, 2004.
[RSTW78] I Reed, R Scholtz, Treiu-Kien Truong, and L Welch. The fast decoding of Reed-Solomon codes using Fermat theoretic transforms and continued fractions. IEEE Transactions on Information Theory, 24(1):100–106, 1978.
[Rud07] Atri Rudra. List decoding and property testing of error correcting codes. PhD thesis, University of Washington, 2007.
[RZWZ20] Noga Ron-Zewi, Mary Wootters, and Gilles Zémor. Linear-time erasure list-decoding of expander codes, 2020. URL: https://arxiv.org/abs/2002.08579, doi:10.48550/ARXIV.2002.08579.
[Ste96] Steane. Simple quantum error-correcting codes. Physical review. A, Atomic, molecular, and optical physics, 54 6:4741–4751, 1996.
[Sud00] Madhu Sudan. List decoding: algorithms and applications. In SIGA, 2000.
[SW02] Benjamin Schumacher and Michael D. Westmoreland. Approximate quantum error correction. Quantum Inf. Process., 1(1-2):5–12, 2002. doi:10.1023/A\%3A1019653202562.
[Wer98] R. F. Werner. Optimal cloning of pure states. Phys. Rev. A, 58:1827–1832, Sep 1998. URL: https://link.aps.org/doi/10.1103/PhysRevA.58.1827, doi:10.1103/PhysRevA.58.1827.
[WHB11] Mark M. Wilde, Min-Hsiu Hsieh, and Zunaira Babar. Entanglement-assisted quantum turbo codes. IEEE Transactions on Information Theory, 60:1203–1222, 2011.
[Woz58] J. M. Wozencraft. List decoding. Quarterly Progress Report, Research Laboratory of Electronics, MIT, page 48:90–95, 1958.
[Yam06] Tomoyuki Yamakami. Quantum list decoding of classical block codes of polynomially small rate from quantumly corrupted codewords. Balt. J. Mod. Comput., 4, 2006.

Appendix A Properties of Random CSS Codes

In this section, we briefly discuss the list decodability and other properties of random CSS codes, which we apply in for the construction of concatenated codes. These properties follow from straightforward applications of their well known classical counterparts, and so for conciseness we simply refer to the necessary statements. That is, we construct random CSS codes from correlated random classical linear codes. Therefore, by a union bound, any property that holds with high probability for these classical codes also holds with high probability for the CSS code.

We generate a random $[[n,k]]_{q}$ CSS code as follows. First, sample $k_{1}=(n+k)/2$ random linearly independent vectors $g_{1},\cdots g_{k_{1}}$ in $\mathbb{F}_{q}^{n}$ . Let $G_{1}=(g_{1}\cdots g_{k_{1}})\in\mathbb{F}_{q}^{n\times k_{1}}$ be the matrix defined by the sampled vectors and $G_{2}=(g_{1}\cdots g_{k_{2}})$ to be the first $k_{2}=n-k_{1}$ columns of $G_{1}$ . We define $C_{1}$ to be the classical linear code defined by using $G_{1}$ as a generator matrix, and $C_{2}$ to be the classical linear code defined by using $G_{2}^{T}$ as the parity check matrix, such that $C_{2}^{\perp}\subset C_{1}$ by construction. We now consider the random Galois-Qudit CSS code $Q_{R}=$ CSS $(C_{1},C_{2})$ , where $R$ is the rate $k/n$ .

First, by assumption with high probability both $G_{2},G_{1}$ are full rank. Thereby, we have $C_{2},C_{1}$ are $[n,k_{1}]_{q}$ classical codes, and CSS $(C_{1},C_{2})$ is a $[[n,k]]_{q}$ QECC. A standard exercise in coding theory is to prove random generator matrices (and parity check matrices) of $k$ columns (resp. $n-k$ rows) have distances approaching the Gilbert-Varshamov bound of $n\cdot H_{q}^{-1}(1-\frac{k}{n})$ with exponentially high probability, where $H_{q}$ denotes the $q$ -ary entropy function. A similar statement also holds for list-decodability, as shown in [Gur01, Theorem 5.3] and stated below.

Lemma A.1 (Well known).

Let $C\subseteq\mathbb{F}_{q}^{n}$ be a random classical linear code of rate $R$ . Then for every $0<\delta<H_{q}^{-1}(1-R)$ ,

•

$C$ has relative distance $\geq\delta$ with probability $\geq 1-q^{-n(1-R-H_{q}(\delta))}$
•

For every $\ell\geq 1$ , $C$ is $(\delta,\ell)$ list-decodable with probability $\geq 1-q^{n(1-\log_{q}(\ell+1)(1-R-H_{q}(\delta)))}$ .

In particular, Lemma A.1 implies that given $\varepsilon>0$ , we can choose $q=2^{O(1/\varepsilon)}$ , $\delta=1-R-O(\varepsilon)$ , and $\ell=q^{O(1/\varepsilon)}=2^{O(1/\varepsilon^{2})}$ , and the random linear code $C$ will be $(\delta,\ell)$ list-decodable and have relative distance $\geq\delta$ with probability $\geq 1-q^{-\Omega(\varepsilon n)}$ . Union bounding over the two classical codes making up a random CSS code, Lemma A.1 and Theorem 3.2 immediately imply the following.

Claim A.2.

Let $Q$ be a random CSS code of rate $R$ and block length $n$ over $\mathbb{F}_{q}$ . Then for every $0<\delta<H_{q}^{-1}((1-R)/2)$ ,

•

$Q$ has relative distance $\geq\delta$ with probability $\geq 1-2\cdot q^{-n((1-R)/2-H_{q}(\delta))}$
•

For every $\ell\geq 1$ , $Q$ is $(\delta,\ell)$ list-decodable with probability $\geq 1-2\cdot q^{n(1-\log_{q}(\sqrt{\ell})((1-R)/2-H_{q}(\delta)))}$ .

Similarly as in the classical case, given $\varepsilon>0$ , we can choose $q=2^{O(1/\varepsilon)}$ , $\delta=(1-R-O(\varepsilon))/2$ , and $\ell=q^{O(1/\varepsilon)}=2^{O(1/\varepsilon^{2})}$ , and the random CSS code $Q$ will be $(\delta,\ell)$ list-decodable and have relative distance $\geq\delta$ with probability $\geq 1-q^{-\Omega(\varepsilon n)}$ .

Appendix B List-Recoverable Quantum Codes

In this section, we discuss a quantum analog of a certain extension to list-decoding, the problem of list-recovery. While, at a high level, list-decoding requests the codewords of a certain code $C$ around a given point, the problem of list-recovery requests the codewords $c\in C$ whose individual symbols $c_{1},c_{2}...c_{n}$ come from a small set of ‘candidate’ symbols:

Definition B.1.

A code $C\subset\Sigma^{n}$ is $(\eta,l,L)$ -LR (list-recoverable) if $\forall S_{1}\cdots S_{n}\subset\Sigma$ , with $|S_{i}|\leq l$ ,

\bigg{|}\bigg{\{}c\in C:c_{i}\in S_{i}\text{ for at least }\eta\cdot n\text{ symbols }i\in[n]\bigg{\}}\bigg{|}\leq L

(31)

This would suggest that once one fixes sets of candidate symbols $S_{1}\cdots S_{n}$ , there aren’t many codewords $c\in C$ which agree with the subsets $S_{i}\subset\Sigma$ at most $i$ . We emphasize that the special case $(\eta,1,L)$ -LR is equivalent to $(1-\eta,L)$ -LD. This is since if $C$ is $(\eta,1,L)$ -LR, for any vector $y\in\Sigma^{n}$ , one can pick $S_{i}=\{y_{i}\}$ (such that $|S_{i}|=1$ ) and the number of codewords $c\in C$ which agree with $y$ on at least $\eta$ locations is the number of codewords in a ball of radius $1-\eta$ around $y$ . Finally, $C$ is said to be efficiently list-recoverable if there exists an efficient algorithm to find these codewords.

Below, we discuss an analogous notion of list recoverability for the normalizer group of a stabilizer QECC. Informally, it corresponds to enumerating the logical operators of the quantum code whose single-qudit components are selected from candidate lists $\mathcal{E}_{i}\subset\mathcal{P}_{q}$ of single-qudit operators.

Definition B.2.

A $[[n,k]]_{q}$ stabilizer code $Q$ with stabilizer group $\mathcal{S}(Q)$ is $(\eta,l,L)$ -QLR (Quantum List Recoverable) if, for all subsets $\mathcal{E}_{1},\cdots,\mathcal{E}_{n}\subset\mathcal{P}_{q}$ of single-qudit operators with $|\mathcal{E}_{i}|\leq l$ , any list $L(\{\mathcal{E}\})$ of logically-distinct operators in the normalizer group $N(Q)$ where

L(\{\mathcal{E}\})=\bigg{\{}A=\otimes_{i}A_{i}\in N(Q):A_{i}\in\mathcal{E}_{i}\text{ for at least }\eta\cdot n\text{ symbols }i\bigg{\}},

(32)

has size bounded by $|L(\{\mathcal{E}\})|\leq L$ .

This means that there don’t exist many logical operators which match the $\mathcal{E}_{i}$ at most locations $i\in[n]$ . We expect this to naturally reduces to the QLD definition when $l=1$ . Indeed,

Claim B.1.

If a stabilizer QECC $Q$ is $(\eta,1,L)$ -QLR, then it is $(1-\eta,L)$ -QLD.

Proof.

Fix $E\in\mathcal{P}_{q}^{n}$ . Recall the set of operators $F\in\mathcal{P}_{q}^{n}$ such that $F^{\dagger}E\in N(Q)$ is a logical operator, is equivalent to the set $EA^{\dagger}$ for $A\in N(Q)$ . Thus $F$ has weight $\leq\delta\cdot n$ if $A_{i}=E_{i}$ for at least $1-\delta$ locations. Let $\mathcal{E}_{i}=\{E_{i}\}$ . Since $Q$ is $(\eta,1,L)$ -QLR, there are at most $L$ such choices of $A$ . ∎

We note that the characterization above of quantum list-recovery can be cast in terms of an analogous classical question about syndromes of the stabilizer code.

Claim B.2.

Let $Q$ be $(\eta,l,L)$ -QLR, let $E\in\mathcal{P}_{q}^{n}$ be any error on $Q$ of syndrome $s$ , and consider any set of subsets $\mathcal{E}_{1},\cdots,\mathcal{E}_{n}\subset\mathcal{P}_{q}$ of single-qudit operators with $|\mathcal{E}_{i}|\leq l$ . Then any set $\mathcal{L}_{s}(\{\mathcal{E}\})\subset\mathcal{P}_{q}^{n}$ of logically-distinct operators of syndrome $s$ and which agree with the $\mathcal{E}_{i}$ on at least $\eta\cdot n$ qudits $i$ , has size bounded by $|\mathcal{L}_{s}(\{\mathcal{E}\})|\leq L$ .

Proof.

Given any such set $\mathcal{L}_{s}(\{\mathcal{E}\})$ , consider the set $\mathcal{L}=\big{\{}E^{\dagger}F:\text{ for }F\in\mathcal{L}_{s}(\{\mathcal{E}\})\big{\}}$ defined by shifting the elements of the former by $E$ . Also, for each $i\in[n]$ , ‘shift’ each list of single qudit operators $\mathcal{E}_{i}^{\prime}=(E^{\dagger})_{i}\mathcal{E}_{i}$ by $E_{i}^{\dagger}$ . Note that $|\mathcal{E}_{i}^{\prime}|\leq l$ , and $|\mathcal{L}_{s}(\{\mathcal{E}\})|=|\mathcal{L}|$ . Since each $F\in\mathcal{L}_{s}(\{\mathcal{E}\})$ has the same syndrome as $E$ , $E^{\dagger}F\in N(Q)$ and thus the elements of $\mathcal{L}$ are logically-distinct operators in $N(Q)$ . Moreover, $(E^{\dagger}F)_{i}\in\mathcal{E}_{i}^{\prime}$ for most $i$ . By the definition of QLR, we must have $|\mathcal{L}|\leq L$ , which concludes the proof. ∎

Much like the case for quantum list decoding, we show that one can devise quantum codes with good list recovery properties from the CSS construction of two classically list recoverable codes.

Claim B.3.

If $C_{1},C_{2}\subset(\mathbb{F}_{q}^{m})^{n}$ are two $\mathbb{F}_{q}$ -linear classical codes with $C_{2}^{\perp}\subset C_{1}$ and $C_{1},C_{2}$ are $(\eta,l,L)$ -LR, then the Galois-qudit CSS $(C_{1},C_{2})$ is $(\eta,l,L^{2})$ -QLR.

Proof.

The elements in the normalizer of CSS $(C_{1},C_{2})$ are the operators $E_{\textbf{a},\textbf{b}}$ , $a\in C_{1},b\in C_{2}$ . Now, fix arbitrary sets $\mathcal{E}_{1},\cdots,\mathcal{E}_{n}\subset\mathcal{P}_{q}^{m}$ of size $\leq l$ . We can write each single qudit operator $E_{ij}$ in the $i$ th set $\mathcal{E}_{i}=\{E_{ij}\}_{j\in[l]}$ into a Pauli basis: $E_{ij}=E_{a_{ij},b_{ij}},a_{ij},b_{ij}\in(\mathbb{F}_{q}^{m})$ . We can thereby define sets of ‘X’ symbols $S^{X}_{i}=\{a_{ij}\}_{j\in[l]}$ , and ‘Z’ symbols $S^{Z}_{i}=\{b_{ij}\}_{j\in[l]}$ , for each location $i$ .

If $A=E_{\textbf{a},\textbf{b}}\in N(S)$ , and $A_{i}\in\mathcal{E}_{i}$ for most $i$ , then we have that $a_{i}\in S^{X}_{i}$ and $b_{i}\in S^{Z}_{i}$ for most $i$ . However, $a\in C_{1}$ is $(\eta,l,L)$ -LR, so there exist at most $L$ such valid codewords of $C_{1}$ . Analogously, there exist at most $L$ valid choices of $b\in C_{2}$ . The set of of valid elements $A\in N(S)$ is at most the number of pairs of valid elements. ∎

By casting this notion of list recovery as a classical problem, we inherit the efficiency of classical list decoding algorithms.

Claim B.4.

If $C_{1},C_{2}\subset(\mathbb{F}_{q}^{m})^{n}$ with $C_{2}^{\perp}\subset C_{1}$ are efficiently $(\eta,l,L)$ -LR, then given any syndrome $s$ of the quantum code $Q=$ CSS $(C_{1},C_{2})$ and subsets $\mathcal{E}_{1},\cdots,\mathcal{E}_{n}\subset\mathcal{P}_{q}$ of single-qudit operators with $|\mathcal{E}_{i}|\leq l$ , there exists a polynomial time classical algorithm to find a list of logically-distinct operators $F$ of syndrome $s$ and $F_{i}\in\mathcal{E}_{i}$ for at least $\eta\cdot n$ symbols $i\in[n]$ .

Proof.

If $s=s_{x},s_{z}$ are the syndrome measurements of the X and Z checks, respectively, then let $E^{\prime}=E_{e_{x},e_{z}}$ be any Pauli operator with the same syndrome. Given the sets of single qudit operators $\mathcal{E}_{i}=\{E_{a_{ij},b_{ij}}\}_{j\in[l]}$ , then consider the sets of $q$ -ary symbols

S^{X}_{i}=\{(e_{x})_{i}+a_{ij}\}_{j\in[l]}\text{ and }S^{Z}_{i}=\{(e_{z})_{i}+b_{ij}\}_{j\in[l]}\text{ for }i\in[n]

(33)

We call the classical list decoding algorithm for $C_{1}$ on the $S^{X}_{1},S^{X}_{2}\cdots$ and $C_{2}$ on the $S^{Z}_{i}$ , obtaining lists of codewords $(c_{1,1},c_{1,2}\cdots c_{1,L})\subset C_{1}$ and $(c_{2,1},c_{2,2}\cdots c_{2,L})\subset C_{2}$ respectively. We note that each ‘correction’ $c_{1,k}-e_{x}$ , for $k\in[L]$ , defines a Pauli operator $X^{e_{x}-c_{1,k}}$ with the same syndrome as $e_{x}$ . Moreover, $(e_{x}-c_{1,k})_{i}$ agrees with $\{a_{ij}\}_{l\in[n]}$ in at least $\eta\cdot n$ locations $i$ . Thus a subset of the $L^{2}$ operators $E_{\textbf{e}_{x}-\textbf{c}_{1,k},\textbf{e}_{z}-\textbf{c}_{2,k^{\prime}}},k,k^{\prime}\in[L]$ satisfy the claim. ∎

By combining the above with known results on the list-recoverability of folded Reed-Solomon codes (the below is a corollary of Theorem 6.2 of [GR08] stated previously),

Theorem B.5 ([GR08]).

For every integer $l$ , rates $R\in(0,1)$ , $\gamma\in(0,R)$ , and prime $p$ , there exists $m$ -folded RS codes (Definition 3.6) over fields of characteristic $p$ of rate $R$ and block length $n$ which are $(R+\gamma,l,L)$ -LR, where $m=O(\frac{\log l}{(1-R)\gamma^{2}})$ , $L=O(n/\gamma^{2})^{O(\gamma^{-1}\log l/R)}$ , and alphabet size $(n/\gamma^{2})^{O(m)}$ .

We arrive at an exact analog:

Corollary B.6.

For every integer $l$ , rates $R\in(0,1)$ , $\gamma\in(0,R)$ , and prime $p$ , there exists $m$ -folded QRS codes (Definition 3.8) over fields of characteristic $p$ of rate $R$ and block length $n$ which are $(\frac{1+R}{2}+\gamma,l,L)$ -QLR, where $m=O(\frac{\log l}{(1-R)\gamma^{2}})$ , $L=O(n/\gamma^{2})^{O(\gamma^{-1}\log l)}$ , and local dimension $(n/\gamma^{2})^{O(m)}$ .

B.1 List Decodable Codes from List Recovery and Distance Amplification

In this section, we discuss an application of a classical technique to devise codes over smaller alphabets with better list-decoding properties, using the distance amplification techniques in [AEL95]. To do so, we discuss a quantum adaptation of the approach in [GR08], who concatenated Folded RS codes with list decodable inner codes, to reduce the large alphabet size of the RS construction, and approach list decoding capacity on constant size alphabets (with efficient decoding). The theorem below is the main result of this section, on the construction of list decodable quantum codes up to the Singleton bound from the concatenation and distance amplification of list recoverable and list decodable quantum codes.

Theorem B.7.

Fix $R,\gamma>0$ . There exists a $[[N,RN,\geq N\cdot(1-R-\gamma)/2]]_{d}$ stabilizer code $Q$ which is $((1-R-\gamma)/2,N^{1/\gamma^{O(1)}})$ -QLD on local dimension $d=2^{O(1/\gamma^{5})}$ . Moreover, $Q$ can be list-decoded efficiently.

B.1.1 The Construction

We build the quantum code in the theorem above using the concatenation $Q_{\diamond}=Q_{out}\diamond Q_{in}$ of two stabilizer codes $Q_{out},Q_{in}$ . Informally, the ‘outer’ quantum code $Q_{out}$ is chosen to be a high rate, large alphabet, quantum list recoverable code, of size $n$ and local dimension $q^{m}$ . In particular, a $[[n,(1-4\gamma)n]]_{q^{m}}$ QECC which is $(1-\gamma,l,L)$ -QLR. In turn, the ‘inner’ code $Q_{in}$ has rate $R$ near the target rate and is near list decoding capacity, i.e. with decoding radius approaching the quantum singleton bound, $(1-R)/2$ . Formally, $Q_{in}$ is a $[[n^{\prime},m]]_{q}$ QECC and $((1-R)/2-4\cdot\gamma,l)$ -QLD, where $m=n^{\prime}(R+5\gamma)$ . Their concatenation $Q_{\diamond}=Q_{out}\diamond Q_{in}$ is a code on $nn^{\prime}$ qudits of local dimension $q$ and rate $(R+5\gamma)(1-4\gamma)\geq R$

To conclude the construction, the physical qudits of the resulting concatenated code are permuted and re-grouped, using the AEL alphabet-reducing distance amplification techniques discussed in Section 5. Intuitively, as before this permutation is used to ‘spread out’ errors on the inner code, such that any error on the final code doesn’t corrupt most inner blocks beyond repair. Formally, we pick an $\gamma_{0}$ -pseudorandom $D$ -biregular bipartite graph $G$ , with $\gamma_{0}=\gamma^{2}$ and degree $D=10/\gamma_{0}^{2}=\text{poly}(1/\gamma)$ , and use it to define a permutation $\pi_{G}$ . The final code is defined by $\pi_{G}(Q_{\diamond})$ , and is defined on qudits of local dimension $q^{D}$ .

B.1.2 Analysis

We present a lemma on the distance amplification of generic list recoverable and list decodable quantum codes, and then instantiate the lemma with a particular choice of quantum codes $Q_{out},Q_{in}$ to prove Theorem B.7.

Lemma B.8.

Fix $R$ and sufficiently small $\gamma>0$ . Let $Q_{out}$ be a $[[n,(1-4\gamma)n]]_{q^{m}}$ QECC and $(1-\gamma,l,L)$ -QLR, $Q_{in}$ be a $[[n^{\prime},m=n^{\prime}(R+5\gamma)]]_{q}$ QECC and $((1-R)/2-4\gamma,l)$ -QLD, and $G$ be a $\gamma^{2}$ -pseudorandom bipartite expander graph of size $N=nn^{\prime}/D$ and degree $D=O(1/\gamma^{4})$ . Then $\pi_{G}(Q_{out}\diamond Q_{in})$ is $((1-R)/2-8\cdot\gamma,L)$ -QLD.

If $E_{G}=\pi_{G}(E)\in(\mathcal{P}_{q}^{D})^{nn^{\prime}/D}$ is an operator on the code $\pi_{G}(Q_{\diamond})$ , then we refer to $\pi_{G}^{-1}(E_{G})=E\in(\mathcal{P}_{q}^{n^{\prime}})^{n}$ as the ‘unpermuted’ operator $E$ acting on the concatenated code $Q_{\diamond}$ . We emphasize here that we restrict our attention to a basis of operators which factorizes as a tensor product of operators on the individual qudits of local dimension $q$ . Since $Q_{\diamond}$ is a concatenated code, recall that its syndrome measurement corresponds to the syndromes of the inner codes, as well as the syndrome measurement of the encoding of the stabilizers of the outer code, see 2.2.

To prove the lemma above, it suffices to show that there aren’t many low weight, logically-distinct, operators $F_{G}$ on $\pi_{G}(Q_{\diamond})$ , which agree with both of the syndrome measurements. To do so, we divide the proof into two key steps. First, we measure the syndrome of the inner blocks, and argue that their list-decodability and the expansion of $G$ produces small lists of candidate ‘correction’ operators acting on the inner blocks. Then, we measure the syndrome of the outer code, and use its list-recoverability to infer that there can’t be many global operators matching the elements of these inner-block lists.

Claim B.9.

Let $s_{1}\cdots s_{n}$ be any syndrome measurements of the $n$ inner code blocks, and let each $\mathcal{L}_{s_{i}}$ , for $i\in[n]$ , correspond to a list of operators on $Q_{in}$ of relative weight $\leq(1-R)/2-4\cdot\gamma$ which match $s_{i}$ and are all distinct up to a stabilizer of $Q_{in}$ . Let $O_{G}=\pi_{G}(O)$ be any operator of relative weight $\leq(1-R)/2-8\gamma$ on $\pi_{G}(Q_{\diamond})$ , where $O=\otimes_{i}O_{i}\in(\mathcal{P}_{q}^{n^{\prime}})^{n}$ , and $O_{i}\in\mathcal{P}_{q}^{n^{\prime}}$ is supported on the $i$ th inner block. Then, if $O$ has syndrome $s_{i}$ on the $i$ th block for $i\in[n]$ ,

O_{i}\text{ is stabilizer equivalent to some element of }\mathcal{L}_{s_{i}}\text{ for }\geq 1-\gamma\text{ inner blocks }i\in[n]

(34)

Proof.

Let $O_{G}=\pi_{G}(O)$ be any operator of relative weight $\leq(1-R)/2-8\cdot\gamma$ on $\pi_{G}(Q_{\diamond})$ . From Proposition 5.4, the expansion of $G$ tells us that at least $\geq 1-\gamma$ inner blocks have wt $(O_{i})\leq n^{\prime}\cdot((1-R)/2-4\cdot\gamma)$ . We refer to these inner blocks as ‘Good’ blocks. Via the list decodability of $Q_{in}$ , if $i$ is Good, then $O_{i}$ is equivalent up to a stabilizer of $Q_{in}$ , to some element of $\mathcal{L}_{s_{i}}$ . Moreover, $|\mathcal{L}_{s_{i}}|\leq l$ . ∎

Now, let us measure the syndrome $s^{out}$ of the outer code, by means of the encoded stabilizers of $Q_{out}$ . Please refer to 2.2 for a description of the stabilizers of concatenated codes. From B.9 it suffices to argue that there aren’t many operators $O$ on the concatenated code with outer syndrome $s^{out}$ and where $O_{i}\in\mathcal{L}_{s_{i}}$ for most $i$ . This resembles a statement about list-recoverability, but about operators on the concatenated code, not the outer code. The claim below formalizes how to reduce that statement to the list recoverability of the outer code.

Claim B.10.

There are at most $L$ operators $E\in(\mathcal{P}_{q}^{n^{\prime}})^{n}$ which are distinct up to a stabilizer of the concatenated code $Q_{out}\diamond Q_{in}$ and have outer syndrome $s^{out}$ , inner syndromes $s_{1}\cdots s_{n}$ , where $E_{G}=\pi_{G}(E)$ is an operator on the distance amplified code of relative weight $\leq(1-R-16\cdot\gamma)/2$ .

As an immediate corollary of the above, we recover Lemma B.8.

Corollary B.11.

$\pi_{G}(Q_{\diamond})$ is $((1-R-O(\gamma))/2,L)$ -QLD.

Proof of B.10.

The proof proceeds by using the elements of the lists $\mathcal{L}_{s_{i}}$ to construct operators acting on each symbol of the outer code, for which we then invoke list-recoverability. Consider, WLOG, the first element $F_{1}^{i}\in\mathcal{P}_{q}^{n^{\prime}}$ in the list $\mathcal{L}_{s_{i}}$ of the $i$ th inner block. For each $i\in[n]$ , we construct a list of inner code normalizers

L_{i}=\big{\{}(F_{1}^{i})^{\dagger}F_{j}^{i}\in N(Q_{in}):F_{j}^{i}\in\mathcal{L}_{s_{i}},j\in[l]\big{\}}

(35)

Note that each element of $L_{i}$ is $S(Q_{in})$ -logically-equivalent to a logical operator $\bar{X}_{ij}\in N(Q_{in})/S(Q_{in})$ , defined by quotienting out the stabilizer group of $Q_{in}$ . Thus, one can derive from $L_{i}$ a list of operators $\mathcal{E}_{i}\subset\mathcal{P}_{q^{m}}$ acting on the $i$ th qudit of the outer code:

\mathcal{E}_{i}=\bigg{\{}X_{ij}=\mathsf{Enc}_{in}^{\dagger}\bar{X}_{ij}\mathsf{Enc}_{in}\in\mathcal{P}_{q^{m}}:\bar{X}_{ij}\text{ stabilizer equivalent to some element of }L_{i}\bigg{\}}

(36)

Note that $|\mathcal{L}_{s_{i}}|\leq l\Rightarrow|\mathcal{E}_{i}|\leq l$ , and that the identity operator is in $\mathcal{E}_{i}$ (since it was in $L_{i}$ as well). Let $s_{1}^{out}$ denote the syndrome of the operator $F_{1}=\otimes_{i}^{n}F_{1}^{i}$ on the encoded stabilizers of the outer code. Now, we invoke the list recoverability of the outer code to find a list $\mathcal{L}_{out}\subset\mathcal{P}_{q^{m}}^{n}$ of at most $L$ $S(Q_{out})$ -logically-distinct operators $E=\otimes E_{i}$ acting on the outer code where $E_{i}\in\mathcal{E}_{i}$ for $\geq 1-\gamma$ qudits $i\in[n]$ , and $E$ has syndrome $s^{out}-s^{out}_{1}$ . Each element of $\mathcal{L}_{out}$ can now be represented as an operator acting on the concatenated code, by re-encoding into $Q_{in}$ , and to conclude we shift back the rotation by $F_{1}=\otimes_{i}^{n}F_{1}^{i}$ :

\mathcal{L}_{s^{out},s^{in}}=\big{\{}F_{1}\big{(}\otimes_{i}^{n}\mathsf{Enc}_{in}\big{)}X\big{(}\otimes_{i}^{n}\mathsf{Enc}_{in}^{\dagger}\big{)}:X\in\mathcal{L}_{out}\big{\}}

(37)

To conclude the proof, we argue correctness of the produced list. It suffices to prove that any operator $O$ with bounded weight on the distance-amplified code with syndromes $s^{out},s^{in}=s_{1}\cdots s_{n}$ is $S(Q_{\diamond})$ -stabilizer equivalent to an element of $\mathcal{L}_{s^{out},s^{in}}$ . For the purposes of contradiction, assume otherwise and let one such operator be $O=\otimes O_{i}$ on $Q_{\diamond}$ . By construction, $F_{1}^{\dagger}O$ has syndrome 0 on all inner code blocks, since $(F_{1}^{i})^{\dagger}O_{i}\in N(Q_{in})$ , and thereby $F_{1}^{\dagger}O$ is $S(Q_{\diamond})$ -stabilizer equivalent to some encoded operator $(\otimes_{i}^{n}\mathsf{Enc}_{in})X(\otimes_{i}^{n}\mathsf{Enc}_{in}^{\dagger})$ , for $X\in\mathcal{P}_{q^{m}}^{n}$ . Moreover, $X_{i}\in\mathcal{E}_{i}$ for at least $1-\gamma$ locations $i$ , and the outer code syndrome of $X$ is the same as that of $F_{1}^{\dagger}O$ . Since the outer code syndrome of $F_{1}^{\dagger}O$ is precisely $s_{out}-s_{1}^{out}$ , $X$ must be $S(Q_{out})$ -logically-equivalent to some element returned by the list recovery, concluding the proof. ∎

To conclude this section, we make an explicit choice of codes and parameters. Let $q=2^{\Theta(1/\gamma)}$ , and pick $Q_{in}$ to be a random $q$ -ary CSS code of rate $R+5\gamma$ which is $((1-R)/2-4\gamma,q^{\Theta(1/\gamma)})$ -QLD, see A.2. By picking $l=q^{\Theta(1/\gamma)}$ in Theorem 3.8, we let $Q_{out}$ be the $m$ -Folded Quantum RS code of Definition 3.8 of rate $1-4\gamma$ , and blocklength $n$ , folding parameter $m=\Theta(\frac{1}{\gamma^{4}}\log q)=\Theta(\frac{1}{\gamma^{5}})$ , which is $(1-\gamma,q^{O(1/\gamma)},n^{O(\log(1/\gamma)/\gamma^{3})})$ -QLR. Naturally $Q_{out},Q_{in}$ are defined over a field of the same characteristic, and we let the alphabet size of $Q_{out}$ be any composite $Q=q^{m\cdot x}$ where $x=\Theta(\log n)$ , such that the block-length of $Q_{in}$ is $\Theta(m\log n)$ . The resulting alphabet size is $q^{D}=2^{\Theta(1/\gamma^{5})}$ , and list size $n^{O(\log(1/\gamma)/\gamma^{3})}$ . We list decode the resulting code by brute force decoding the inner codes in time $N\cdot q^{O(m\log N)}=N^{O(\frac{1}{\gamma^{5}})}$ , and list recover $Q_{out}$ in time $N^{O_{\gamma}(1)}$ , resulting in an efficient decoding.

Appendix C Generalization of Lemma 4.1

In this section we prove a particular parallel composability property of the private AQECCs of Lemma 4.1 presented in Section 5. For simplicity, we simply discuss the main modifications from Lemma 4.1. We later apply this composability to study the concatenation of AQECCs.

In our proof of Lemma 4.1, we actually showed the slightly stronger statement that $Q_{LD}\circ Q_{k}$ uniquely decodes an arbitrary adversarial error with high probability over the choice of private key $k$ . In this section, we show that this stronger property continues to hold when the adversary is allowed access to a side-register entangled with the encoded message.

Consider the following setting, where Alice and Eve hold a bipartite quantum state $\ket{\psi}_{AE}$ , and Alice desires to send the $A$ register to a third party, Bob. To do so, Alice has access to an adversarial quantum communication channel $\mathcal{A}_{SE}$ , where Eve can adversarially tamper with up to a $\delta$ fraction $S$ of the registers of the sent message, in addition to their half $E$ of $\psi_{AE}$ . Before doing so, Alice picks a random key $k\in K$ , and encodes her half of the state using the private AQECC $(\mathsf{Enc}_{k})_{A\rightarrow Q}$ , and then sends her half over the channel. After receiving the corrupted code-state (and with knowledge of $k$ ), Bob attempts to decode using the channel $\mathsf{Dec}_{k}$ defined in Algorithm 1. The density matrix $\rho^{k}_{BE}$ produced by Bob can be written as

\rho^{k}_{BE}=\big{(}(\mathsf{Dec}_{k})_{Q\rightarrow B}\otimes\mathbb{I}_{E}\big{)}\circ\big{(}\mathbb{I}_{Q\setminus S}\otimes\mathcal{A}_{SE}\big{)}\circ\big{(}(\mathsf{Enc}_{k})_{A\rightarrow Q}\otimes\mathbb{I}_{E}\big{)}(\psi_{AE})

(38)

Theorem C.1 below is a generalization of 4.5, which states that with high probability over the choice of $k$ (and the syndrome measurement outcomes), the quantum state $\rho_{BE}^{k}$ Bob recovers is simply as if Eve had corrupted their register $E$ without touching the $A$ register at all: i.e. $\rho_{BE}^{k}\approx(\mathbb{I}_{A}\otimes\mathcal{A}_{E})(\psi)_{AE}$ , for some CP operator $\mathcal{A}_{E}$ acting only on $E$ .

Theorem C.1.

Let $(\mathsf{Enc}_{k},\mathsf{Dec}_{k})$ be the private $(\delta,\varepsilon^{\prime})$ -AQECC of Lemma 4.1, defined via the composition of a $[[n,m,d\geq\delta n]]$ $(\delta,L)$ -QLD code $Q_{LD}$ and an $\varepsilon$ -PTC $\{Q_{k}\}$ with keys $K$ . Let $\ket{\psi}_{AE}$ be a bipartite quantum state, and for $k\in K$ let $|\psi_{k}\rangle_{QE}=(\mathbb{I}_{E}\otimes(\mathsf{Enc}_{k})_{A\rightarrow Q})\ket{\psi}_{AE}$ be the encoding of the $A$ half of $\psi_{AE}$ into the AQECC. If $\mathbb{I}_{Q\setminus S}\otimes\mathcal{A}_{SB}$ is an arbitrary CP error operator supported on $B$ and a set $S\subset Q$ of at most $\delta\cdot n$ code registers, then for a random choice of $k$ the decoding algorithm $\mathsf{Dec}_{k}$ of Algorithm 1 produces the density matrix

\sum_{s}\sum_{k\in\text{Good}_{\mathcal{A},s}}\frac{p_{\mathcal{A},s}}{|K|}\ket{k}\bra{k}\otimes\ket{s}\bra{s}\otimes(\mathbb{I}_{A}\otimes\mathcal{A}_{E}^{s})(\psi_{AE})+\sum_{s}\sum_{k\in K\setminus\text{Good}_{\mathcal{A},s}}\frac{p_{\mathcal{A},s}}{|K|}\ket{k}\bra{k}\otimes\ket{s}\bra{s}\otimes(\rho_{k,s})_{BE}

(39)

That is, for each syndrome $s$ of the stabilizer code $Q_{LD}$ , $s$ is measured with probability $p_{\mathcal{A},s}$ , $\mathcal{A}_{E}^{s}$ is a CP operator acting only on the register $E$ , $(\rho_{k,s})_{BE}$ are generic bipartite PSD matrices, and $\text{Good}_{s}\subset K$ is a large subset of the PTC keys of size $\geq|K|(1-L\cdot\varepsilon)$ .

In other words, even if the adversary can corrupt a sideregister $E$ entangled with the message, with probability at least $(1-L\cdot\varepsilon)$ Bob recovers the $A$ half of the original bipartite state $\psi_{AE}$ uncorrupted.

Remark C.1.

We remark that the proof of Theorem C.1 below holds even if the state $\ket{\psi}$ is entangled with a third environment register to which none of the encoder, decoder, or error operators have access.

To prove the theorem above, we present a generalization of 4.1 and the intuition in Section 3. Qualititatively, it formalizes that the local indistinguishability of the stabilizer code ensures Eve learns nothing about the private encryption key $k$ , even if Eve has prior entanglement with the message. Thus, if Bob performs a syndrome measurement upon receiving the corrupted codestate, he will collapse the state into a mixture of Pauli errors acting on his half of the state, and generic operators acting on Eve’s half. Together with 4.4 and 4.5, C.2 below directly implies Theorem C.1.

Claim C.2.

Let $Q$ be be a $[[n,m,d]]_{q}$ stabilizer code, let $\ket{\psi}_{AE}$ be any bipartite quantum state, and let $|\tilde{\psi}\rangle_{QE}=(\mathbb{I}_{E}\otimes\mathsf{Enc}_{A\rightarrow Q})\ket{\psi}_{AE}$ be the encoding of half of $\ket{\psi}_{AE}$ into the code $Q$ . If $\mathbb{I}_{Q\setminus S}\otimes\mathcal{A}_{SE}$ is an arbitrary CP error operator supported on $E$ and a set $S\subset Q$ of fewer than $d$ code registers, then the syndrome measurement $(M_{Q}\otimes\mathbb{I}_{E})$ collapses the corrupted state into the mixture

(M_{Q}\otimes\mathbb{I}_{E})\circ(\mathbb{I}_{Q\setminus S}\otimes\mathcal{A}_{SE})(\tilde{\psi}_{QE})=\sum_{s}p_{\mathcal{A},s}\ket{s}\bra{s}\otimes(\mathbb{I}_{Q\setminus S}\otimes(\sigma_{\mathcal{A},s})_{S}\otimes\mathcal{A}^{s}_{E})(\tilde{\psi}_{QE}),

(40)

That is, the syndrome $s$ is measured with probability $p_{\mathcal{A},s}$ and the resulting state is collapsed a single Pauli error $\sigma_{\mathcal{A},s}$ on the code $Q$ , and a CP operator $\mathcal{A}^{s}_{E}$ supported only on the non-encoded half $E$ .

If $\mathcal{A}_{SE}$ is CPTP, then $\sum_{s}p_{\mathcal{A},s}=1$ . We emphasize that the distribution over syndrome measurements, $\{p_{\mathcal{A},s}\}$ , doesn’t depend on the encoded half $A$ of $\ket{\psi}_{AE}$ , only on the choice of error operator $\mathcal{A}$ and $\rho_{E}=\text{Tr}_{E}[\psi_{AE}]$ .

Proof.

Consider a decomposition of the CP map $\mathcal{A}=\mathcal{A}_{SE}$ into Krauss operators $\{A_{\nu}\}$ . Let us further decompose each operator $A_{\nu}=\sum_{\sigma=\sigma_{S}\otimes\sigma_{E}}c^{\nu}_{\sigma}\cdot\sigma_{S}\otimes\sigma_{E}$ into a Pauli basis. The POVM $(\mathbb{I}_{E}\otimes M_{Q})$ is comprised of projectors $\Pi_{s}$ for each syndrome $s$ , which we observe to collapse $A_{\nu}$ into Pauli’s on $S\subset Q$ of syndrome $s$ :

\bigg{(}\mathbb{I}_{E}\otimes(\Pi_{s})_{Q}\bigg{)}(\mathbb{I}_{Q\setminus S}\otimes A_{\nu})|\tilde{\psi}\rangle_{QE}=\sum_{\sigma_{S}\text{ of syndrome }s}\sum_{\sigma_{E}}c^{\nu}_{\sigma_{S},\sigma_{E}}\sigma_{S}\otimes\sigma_{E}|\tilde{\psi}\rangle_{QE}

(41)

However, each $\sigma_{S}$ in the sum above is supported on $|S|\leq d$ and they all have the same syndrome $s$ , and thereby must all be stabilizer-equivalent to an operator $\sigma_{\mathcal{A},s}$ supported on $S$ . One can thereby re-arrange the above

=(\sigma_{\mathcal{A},s})_{S}\otimes\sum_{\sigma_{E}}a^{s,\nu}_{\sigma_{E}}\sigma_{E}|\tilde{\psi}\rangle_{QE}=(\sigma_{\mathcal{A},s})_{S}\otimes(A_{s,\nu})|\tilde{\psi}\rangle_{QE},\text{ where }a^{s,\nu}_{\sigma_{E}}=\sum_{\sigma_{S}\text{ of syndrome }s}c^{\nu}_{\sigma_{S},\sigma_{E}}

(42)

To conclude, we denote as $p_{\mathcal{A},s}=\sum_{\nu}\langle\tilde{\psi}|\mathbb{I}\otimes\mathcal{A}_{s,\nu}^{\dagger}\mathcal{A}_{s,\nu}|\tilde{\psi}\rangle_{QE}=\sum_{\nu}\sum_{\sigma_{E},\sigma^{\prime}_{E}}(a^{s,\nu}_{\sigma_{E}})^{*}a^{s,\nu}_{\sigma^{\prime}_{E}}\langle\tilde{\psi}|\mathbb{I}\otimes\sigma_{E}^{\dagger}\sigma^{\prime}_{E}|\tilde{\psi}\rangle_{QE}=\sum_{\nu}\sum_{\sigma_{E},\sigma^{\prime}_{E}}(a^{s,\nu}_{\sigma_{E}})^{*}a^{s,\nu}_{\sigma^{\prime}_{E}}\cdot\text{Tr}[\sigma_{E}^{\dagger}\sigma^{\prime}_{E}\rho_{E}]$ , which is only a function of $\rho_{E}$ and $\mathcal{A}$ .

∎

Approaching the Quantum Singleton Bound with Approximate Error Correction

Abstract

1 Introduction

1.1 Our Contributions

Main results.

Theorem 1.1 (Restatement of Corollary 4.8 and Corollary 7.6).

Theorem 1.2 (Restatement of Theorem 3.8).

Theorem 1.3 (Restatement of Theorem 6.1).

Additional results.

Theorem 1.4 (Restatement of Corollary 5.3).

Theorem 1.5 (Restatement of Corollary 7.2).

1.2 Technical Overview

1.2.1 Approximate Quantum Error Correction

Definition 1.1.

Definition 1.2 ([CGS05]).

Theorem 1.6 ([MW22]).

1.2.2 Defining Quantum List-Decodable Codes

Definition 1.3 (Restatement of Definition 3.2).

1.2.3 Constructions of Quantum List-Decodable Codes

Claim 1.7.

Claim 1.8 (Informal statement of 3.7).

Theorem 1.9 (Restatement of Theorem 3.8).

Theorem 1.10 (Restatement of Theorem 6.1).

1.2.4 Construction of AQECCs from Quantum List-Decodable Codes

Definition 1.4 (Purity testing codes, [BCG+02]).

Definition 1.5.

Lemma 1.11 (Restatement of Lemma 4.1).

Theorem 1.12 (Informal statement of Theorem 4.7).

1.2.5 Distance Amplification for Quantum Codes

Theorem 1.13 (Informal statement of Proposition 5.1).

1.2.6 Private LDPC AQECCs with Linear-Time Decoding

1.3 Related Work

1.4 Discussion and Open Problems

1.5 Organization

2 Preliminaries

2.1 Notation

2.2 Quantum Error Correction

Definition 2.1 ([KL97]).

Definition 2.2 (Stabilizer Codes over Finite Fields, [AK01]).

Definition 2.3.

Theorem 2.1 (Galois-qudit CSS codes).

Theorem 2.2.

Proof.

2.3 Composition and Concatenation of Quantum Codes

Definition 2.4.

Fact 2.1.

Definition 2.5.

Fact 2.2.

Claim 2.3.

Proof.

3 Quantum List Decodable Codes

Definition 3.1.

Definition 3.2.

Claim 3.1.

Proof.

Definition 3.3.

Theorem 3.2.

Proof.

3.1 Explicit Constructions and Folded Quantum Codes

Definition 3.4 (Generalized Reed-Solomon Codes).

Fact 3.1.

Fact 3.2.

Lemma 3.3 ([GS98]).

Theorem 3.4 (Quantum GRS codes [LXW08]).

Corollary 3.5.

Proof.

Definition 3.5 (mm-folded codes).

Definition 3.6 (mm-folded Reed-Solomon codes [GR08]).

Theorem 3.6 ([GR08]).

Definition 3.7.

Claim 3.7.

Proof.

Definition 3.8 (Folded Quantum Reed-Solomon Code).

Theorem 3.8.

Proof.

4 Approximate Quantum Error Correction

4.1 Private AQEC from Quantum List Decoding and Purity Testing

Definition 4.1 (Definition 1.5, restatement).

Lemma 4.1.

Theorem 4.2 ([BCG+02]).

Approaching the Quantum Singleton Bound
with Approximate Error Correction

Definition 1.4 (Purity testing codes, [BCG⁺02]).

Definition 3.5 ( $m$ -folded codes).

Definition 3.6 ( $m$ -folded Reed-Solomon codes [GR08]).

Theorem 4.2 ([BCG⁺02]).

Theorem 4.6 ([CDD⁺15], Theorem 7).