# Approaching the Quantum Singleton Bound
with Approximate Error Correction

Thiago Bergamaschi, Louis Golowich, Sam Gunn UC Berkeley. Email:
<EMAIL_ADDRESS>Berkeley. Email<EMAIL_ADDRESS>Supported by
an NSF Graduate Research Fellowship.UC Berkeley. Email<EMAIL_ADDRESS>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.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Contributions
    2. 1.2 Technical Overview
    3. 1.3 Related Work
    4. 1.4 Discussion and Open Problems
    5. 1.5 Organization
  2. 2 Preliminaries
    1. 2.1 Notation
    2. 2.2 Quantum Error Correction
    3. 2.3 Composition and Concatenation of Quantum Codes
  3. 3 Quantum List Decodable Codes
    1. 3.1 Explicit Constructions and Folded Quantum Codes
  4. 4 Approximate Quantum Error Correction
    1. 4.1 Private AQEC from Quantum List Decoding and Purity Testing
    2. 4.2 AQECC from Private AQEC and Robust Secret Sharing
  5. 5 Distance Amplification and Alphabet Reduction for Quantum Codes
    1. 5.1 Distance Amplification without Alphabet Reduction
    2. 5.2 Distance Amplification with Alphabet Reduction
  6. 6 Constant-Alphabet Quantum List Decodable Codes Near the Singleton Bound
  7. 7 AQEC without List Recovery
  8. A Properties of Random CSS Codes
  9. B List-Recoverable Quantum Codes
    1. B.1 List Decodable Codes from List Recovery and Distance Amplification
  10. C Generalization of Lemma 4.1

##  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 rates111Indeed, 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).

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.

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

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

  2. 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.222Technically 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).

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.

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]333Also 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]444See 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)$ 555By 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}$666See 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}$ of $Q_{LD}$ and $s_{PTC}$ of $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}$ of $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. 1.

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

  2. 2.

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

  3. 3.

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

  4. 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. 1.

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

  2. 2.

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

######  Theorem 4.7.

Given

  1. 1.

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

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