††thanks: These authors contributed equally.††thanks: These authors
contributed equally.

# The Near-optimal Performance of Quantum Error Correction Codes

Guo Zheng<EMAIL_ADDRESS>Pritzker School of Molecular Engineering, The
University of Chicago, Chicago 60637, USA  Wenhao He  School of Physics,
Peking University, Beijing 100871, China  Center for Computational Science and
Engineering, Massachusetts Institute of Technology, Cambridge, MA 02139, USA
Gideon Lee  Pritzker School of Molecular Engineering, The University of
Chicago, Chicago 60637, USA  Liang Jiang<EMAIL_ADDRESS>Pritzker
School of Molecular Engineering, The University of Chicago, Chicago 60637, USA

###### Abstract

The Knill-Laflamme (KL) conditions distinguish perfect quantum error
correction codes, and it has played a critical role in the discovery of state-
of-the-art codes. However, the family of perfect codes is a very restrictive
one and does not necessarily contain the best-performing codes. Therefore, it
is desirable to develop a generalized and quantitative performance metric. In
this Letter, we derive the near-optimal channel fidelity, a concise and
optimization-free metric for arbitrary codes and noise. The metric provides a
narrow two-sided bound to the optimal code performance, and it can be
evaluated with exactly the same input required by the KL conditions. We
demonstrate the numerical advantage of the near-optimal channel fidelity
through multiple qubit code and oscillator code examples. Compared to
conventional optimization-based approaches, the reduced computational cost
enables us to simulate systems with previously inaccessible sizes, such as
oscillators encoding hundreds of average excitations. Moreover, we
analytically derive the near-optimal performance for the thermodynamic code
and the Gottesman-Kitaev-Preskill (GKP) code. In particular, the GKP code’s
performance under excitation loss improves monotonically with its energy and
converges to an asymptotic limit at infinite energy, which is distinct from
other oscillator codes.

††preprint: APS/123-QED

Introduction.—Quantum error correction (QEC) has central importance in scaling
up quantum devices. The seminal work [1] by Knill and Laflamme (KL) outlines
the necessary and sufficient conditions for perfect QEC. The KL conditions are
celebrated for their conciseness and computational efficiency. Practically,
they have guided the discoveries and analysis of many state-of-the-art qubit
codes [2, 3, 4] and oscillator codes [5, 6, 7, 8, 9].

The KL conditions deal with “perfect” error correction, in that they tell us
whether or not any given error is exactly correctable by a given code.
However, there are two issues with this: first, the set of correctable errors
may not correspond exactly to the errors that occur in real devices – one
often needs to approximate practical noise sources by considering a truncated
set of Kraus operators and/or through techniques such as Pauli Twirling [10,
11]. Furthermore, codes that “perfectly” correct leading order errors do not
necessarily outperform codes that “approximately” correct errors at all orders
[4, 12]. Therefore, it is critical to develop a concise and efficiently
computable metric (similar to the KL conditions) that quantifies the
capabilities of general codes. Such an extension uncovers the fundamental
limit set by the encoding and noise, which is a critical benchmark for code
designs.

One such widely accepted benchmark is the channel (or process) fidelity [13,
14, 15]111The channel fidelity is equivalent to the entanglement fidelity for
maximally entangled states. Under this metric, the optimal recovery can be
found through convex optimizations, which motivated works in optimization-
based QEC [13, 17, 18, 19, 12, 14, 20]. The optimal recovery fidelity can also
serve as a guide for encoding designs [21, 15, 12, 20]. However, these methods
have two drawbacks. Firstly, even if SDP algorithms are decently optimized,
they remain computationally expensive compared to optimization-free methods.
Consequently, past numerical works only work with small Hilbert space sizes,
such as systems with fewer than five qubits [22, 13, 23] or oscillators
containing at most ten average excitations [19, 12, 24]. Secondly, these
optimization techniques are inherently numerical. While powerful, they do not
yield analytical forms for many of the quantities we are interested in, eg.
the parametric dependence of the code performance.

Near-optimal recoveries [25, 26, 27, 28, 29, 30, 31] have the potential to
circumvent these limitations. These channels have constructive forms and solve
a relaxed optimization problem: their performances provide two-sided bounds on
the optimal fidelity. These channels have led to attempts to generalize the KL
conditions [31, 26, 32, 33], further leading to the development of codes like
the thermodynamic code [34, 35, 36]. However, the generalized conditions still
involve optimizations and/or the Bures metric, which are difficult to work
with analytically. The common solutions were to derive bounds on the scaling
of the near-optimal fidelity assuming large system sizes, which no longer
provides a two-sided bound on the optimal performance. Moreover, the
parametric dependence on other system parameters remains unknown.

In this Letter, we derive a concise and optimization-free performance metric,
the near-optimal channel fidelity. The metric is achievable by the transpose
channel [25], also known as the Petz channel [28, 27, 37], and provides a
narrow two-sided bound on the optimal fidelity. Importantly, the only input to
our expression is the QEC matrix, which is exactly what is required to verify
the KL conditions. Therefore, our result is a quantitative generalization of
the KL conditions for arbitrary codes and noise processes. We also develop a
perturbative expression, providing intuition on how are codes’ performances
connected to the structures of their error subspaces. More importantly, the
perturbative form enables us to derive analytical expressions for the near-
optimal fidelity. Taking multiple qubit codes as examples, we numerically
validate the proximity of the closed-form near-optimal expression and the
optimal fidelity obtained from convex optimizations. Furthermore, we
analytically compute the near-optimal fidelity for the thermodynamic code in
the thermodynamic limit, for which only a scaling with system size was known
in past works. After examining a few representative oscillator codes, we
provide rigorous insights on why certain codes’ performances under excitation
loss improve monotonically with increased energy, such as the Gottesman-
Kitaev-Preskill (GKP) code [5]. While past numerical simulations of the GKP
code were limited to a few average excitations, we extend our result to
hundreds of excitations. We also obtain GKP’s performance analytically,
parameterized by system parameters and loss rates. With the analytical
expression, we find the GKP’s performance admits an asymptotic limit at
infinite energy.

Background.—The Knill-Laflamme (KL) conditions [1] are the necessary and
sufficient conditions for perfect QEC codes. For completeness, we briefly
review the conditions here. In QEC settings, the logical information is
encoded through a code with $d$ logical codewords
$\mathinner{\left\\{\ket{\mu_{L}}\right\\}}$, which subsequently passes
through a noise channel $\mathcal{N}$ with Kraus form
$\mathinner{\left\\{\hat{N}_{i}\right\\}}$. The QEC matrix is defined as

$\displaystyle M_{[\mu l],[\nu
k]}=\bra{\mu_{L}}\hat{N}_{l}^{\dagger}\hat{N}_{k}\ket{\nu_{L}}$ (1)

in index notation. The KL conditions states that a code is a perfect error-
correcting code if and only if the QEC matrix can be written as
$M=I_{L}\otimes A$, with $I_{L}$ denoting a _logical_ $d$-dimensional identity
matrix.

The KL conditions assess codes with the assumption that any physical recovery
is allowed. Such an idea can be extended to general codes: the performance of
an encoding, $\mathcal{E}$, against certain noise, $\mathcal{N}$, is
determined by the performance of the optimal recovery,
$\mathcal{R}^{\text{opt}}$. To define optimality, in this work, we adopt the
metric of channel fidelity. For any quantum channel $\mathcal{Q}$, the channel
fidelity is defined as

$\displaystyle
F\left(\mathcal{Q}\right)\mathrel{\mathop{\ordinarycolon}}=\bra{\Phi}\mathcal{Q}\otimes\mathcal{I}_{R}\left(\ket{\Phi}\bra{\Phi}\right)\ket{\Phi},$
(2)

where $\ket{\Phi}$ is the purified maximally mixed state, and
$\mathcal{I}_{R}$ is the identity channel acting on the _reference_ ancillary
system. The optimal recovery, $\mathcal{R}^{\text{opt}}$, is defined as a
recovery that achieves the optimal fidelity

$\displaystyle
F^{\text{opt}}\mathrel{\mathop{\ordinarycolon}}=\max_{\mathcal{R}}F\left(\mathcal{R}\circ\mathcal{N}\circ\mathcal{E}\right)=F\left(\mathcal{R}^{\text{opt}}\circ\mathcal{N}\circ\mathcal{E}\right).$
(3)

For discussions below, we refer to the channel fidelity as fidelity for
simplicity. Our choice of metric is well-motivated by two important properties
of the channel fidelity. Firstly, the channel fidelity is directly connected
to other widely adopted metrics such as the average input-output fidelity [38,
39]. Secondly, the metric is linear in the Choi matrix of the recovery, which
causes the optimization to fall in the category of semidefinite programming
(SDP) [40], a subfield of convex optimization.

Main result.—Here we propose the near-optimal fidelity as a quantitative
metric that can be evaluated without optimization.

######  Theorem 1 (The near-optimal fidelity).

For a $d$-dimensional encoding, $\mathcal{E}$, and a noise channel,
$\mathcal{N}$, the near-optimal fidelity is

$\displaystyle\tilde{F}^{\text{opt}}=\frac{1}{d^{2}}\left\|\operatorname{Tr}_{L}\sqrt{M}\right\|_{F}^{2},$
(4)

where $M$ is the QEC matrix,
$\left(\operatorname{Tr}_{L}B\right)_{l,k}=\sum_{\mu}B_{[\mu l],[\mu k]}$
denotes the partial trace over the code space indices, and $||\cdot||_{F}$ is
the Frobenius norm. The near-optimal fidelity gives a two-sided bound on the
optimal fidelity as

$\displaystyle\frac{1}{2}\left(1-\tilde{F}^{\text{opt}}\right)\leq
1-F^{\text{opt}}\leq 1-\tilde{F}^{\text{opt}}.$ (5)

Worth noticing, the gap between the two-sided bound is proportional to the
optimal infidelity. Therefore, when the code performs well against the noise
channel, the near-optimal fidelity is a close approximation to the optimal
fidelity. Equally importantly, it is remarkable that Eq. (4) is only dependent
on the QEC matrix. Therefore, our metric requires exactly the same resources
as the KL conditions, but it provides a quantitative performance metric beyond
a binary Yes-or-No output. Moreover, our result can further extended to
general channel reversals [41, 42], subsystem codes [43], and mixed-state
codes [44]. Our result implies that the QEC matrix contains richer information
about the code and noise structure beyond the KL conditions. For example, one
can greatly reduce the complexity of optimization-based methods via adopting
the error subspaces as an efficient basis to describe the action of the noise
channel [40, 45, 46].

The near-optimal fidelity is achievable by the transpose channel [25, 26] by
construction, which is exactly where our expression inherits the two-sided
bound. While there are other channels possessing similar near-optimal
properties [29, 31], the transpose channel has the most concise fidelity
expression. The derivation of Eq. (4) is based on the observation that the QEC
matrix is the Gram matrix of the error subspaces. When the QEC matrix is
invertible, the error subspaces can be orthonormalized by the Gram matrix. In
such an orthonormal basis, the transpose channel is equivalent to a measure-
and-recover operation, which leads to the expression of Eq. (4). The
derivation can be generalized to scenarios of degenerate QEC matrix [40].

Computationally, our approach has a drastically reduced cost compared to
optimization-based methods. In many cases, the QEC matrix can be analytically
computed. Otherwise, it is possible to efficiently compute the matrix
depending on the code and noise of interest. In such cases, suppose we are
considering $L$ number of noise Kraus operators, the cost of evaluating
$\tilde{F}^{\text{opt}}$ is $\mathcal{O}\left((dL)^{3}\right)$. As a
reference, the SDP for optimal recovery costs
$\tilde{\mathcal{O}}\left((dN)^{5.246}\right)$
[47]222$\tilde{\mathcal{O}}(g(n))$ is shortened for
$\mathcal{O}(g(n)\log^{k}g(n))$, where $N$ is the physical Hilbert space
dimension. For example, if we consider qubit codes, $N$ scales exponentially
with the number of qubits, $n$. However, it is sufficient numerically to
truncate the number of noise Kraus operators to a polynomial scaling,
$L\propto n^{r}$. In many cases, $r$ only depends on the target precision and
physical error rates.

While the exact form of the near-optimal fidelity, Eq. (4), is an elegant
expression, its advantage lies in its numerical complexity. The component of
matrix square root makes it cumbersome to obtain an analytical expression for
the near-optimal fidelity. Therefore, we develop the following corollary based
on a perturbative decomposition of the QEC matrix.

######  Corollary 1.

The noise channel’s Kraus representation can be chosen such that
$\frac{1}{d}\operatorname{Tr}_{L}M=D$, with $M$ being the QEC matrix and $D$
being a diagonal matrix. With the residual matrix $\Delta
M\mathrel{\mathop{\ordinarycolon}}=M-I_{L}\otimes D$, the near-optimal
infidelity has a perturbative expansion through

$\displaystyle 1-\tilde{F}^{\text{opt}}$ (6) $\displaystyle=$
$\displaystyle\frac{1}{d}\norm{f(D)\odot\Delta
M}_{F}^{2}+\mathcal{O}\left(\norm{f(D)\odot\Delta M}_{F}^{3}\right)$

where $f(D)_{[\mu l],[\nu k]}=\frac{1}{\sqrt{D_{ll}}+\sqrt{D_{kk}}}$ and the
Hadamard product $\left(A\odot B\right)_{ij}=A_{ij}B_{ij}$.

This corollary is proved with the Daleckii-Krein theorem of matrix square root
expansions [40, 49, 50]. Eq. (6) conveniently expresses the infidelity as a
function of $\Delta M$ and $D$ instead of the square root of $M$, thus making
it tangible to obtain analytical expressions. Physically,
$\frac{1}{d}I_{L}\otimes\operatorname{Tr}_{L}M$ and $\Delta M$ corresponds to
the correctable and uncorrectable QEC matrix respectively. In Corollary. 1, we
applied a unitary to diagonalize the correctable matrix. However, it is
generally nontrivial to analytically express the unitary. As a compromise, $D$
can be instead defined as the diagonal entries of the correctable matrix,
$\text{diag}(\frac{1}{d}\operatorname{Tr}_{L}M)=\text{diag}(D)$. Such a
truncation overestimates the error, but its effect is negligible as long as
the off-diagonal yet correctable elements are sufficiently small [40].

It is important to note that the infidelity includes contributions from the
uncorrectable matrix modulated by a function of the correctable matrix,
$f(D)$. Intuitively, while the overlaps between error subspaces lead to
uncorrectable errors, their effects are weighted by the probabilities of their
respective quantum trajectories, which are contained in $D$. Past works [12,
51, 52, 20, 53, 54] have proposed code performance estimators based on the QEC
matrix to perform efficient code optimizations. Nonetheless, they mostly only
took into account the uncorrectable matrix, $\Delta M$, or attempted to
consider the effects of $D$ in heuristic ways. As a comparison, Eq. (6)
suggests a combination of effects from $\Delta M$ and $D$ with guaranteed
performance.

A few observations can be drawn from Eq. (6). For example, for the near-
optimal and optimal fidelity, the error caused by the uncorrectable matrix is
suppressed quadratically. While the quadratic scaling was also observed in
Ref. [30], our result is not limited to one-parameter family of channels and
instead presents the full expression. Moreover, Eq. (6) has a noteworthy
property: if $\Delta M$ is traceless, the code is a perfect QEC code when the
perturbative form vanishes [40]. This is useful for applications that require
vanishing error probability, such as computing the achievable rates [55].

Figure 1: Comparison of near-optimal infidelity and optimal infidelity for
qubit codes $[[4,1,2]]$, $((5,6,2))$, and $[[7,1,3]]$ under amplitude-damping
noise. The black solid line (gray dashed line) represents the upper (lower)
bound on the optimal infidelity given by the near-optimal infidelity.

Examples.—In Fig. 1, we numerically validate the two-sided bound presented in
Eq. (5) for qubit codes under amplitude damping noise [40], which is a
practical but non-Pauli noise channel. We adopt the convention that
$[[n,k,d]]$ represents encoding $k$ logical qubits in $n$ physical qubits with
distance $d$, while for $((n,k,d))$, $k$ represents the logical dimension
instead. Even for well-studied codes like stabilizer codes, their optimal
decoders under non-Pauli noise are in general unknown. The shown qubit codes
include the classic $[[7,1,3]]$ stabilizer code [56] and approximate
$[[4,1,2]]$ [4] code. Another example is the $((5,6,2))$ code [57], which is a
qudit non-stabilizer code.

Figure 2: The near-optimal infidelity of the thermodynamic code with
$m_{0}=-\frac{d}{2}$ and $l=1$, i.e. single erasure error. The stars represent
the exact approach where the QEC matrix is numerically computed, and the
circles represent the perturbative expression given in Eq. (7).

The contributions of our expression lie not only in numerics but also in
analytical aspects. We take the thermodynamic code [34, 40] as an example. The
code has sparked interest because of its close connections with the Eigenstate
Thermalization Hypothesis [58], as well as being an instance of a covariant
code [35]. The code is characterized by the magnetization, $m_{0}$, and the
magnetization distance, $d$. When considering a constant number of erasure
errors and thermodynamic limit, the optimal infidelity was proven to scale as
$1-F^{\text{opt}}=\Theta(\frac{1}{N^{2}})$ [35], where $N$ is the number of
qubits. Beyond a scaling argument, our expression makes it possible to derive
the near-optimal infidelity analytically [40]. Take $m_{0}=-\frac{d}{2}$ as an
example, we have

$\displaystyle
1-\tilde{F}^{\text{opt}}=\frac{l}{16}\frac{d^{2}}{N^{2}}+\mathcal{O}\left(\frac{1}{N^{3}}\right).$
(7)

for $l$ erasure errors. The derivation of Eq. (7) with our formalism is
straightforward and can be easily extended to consider more erasure errors
[40]. The comparison of the perturbative and the exact forms of the near-
optimal infidelity is shown in Fig. 2, where it is clear they closely follow
each other. For the exact form, the QEC matrix is numerically computed, and
the simulation stops at 14 qubits because of the increased computational cost.
To compare, if we attempt to optimize for the optimal fidelity, it is only
possible for less than 5 qubits under the same time constraint.

Figure 3: The channel infidelity of square lattice GKP qubit code under loss.
The loss rate is $\gamma=0.1$. The blue dashed lines with (without) squares
represent the near-optimal infidelity upper (lower) bound given by the optimal
infidelity. The red triangles represent the exact form of the near-optimal
infidelity, where the QEC matrix is computed analytically. The green line is
the perturbative form, which has a closed-form analytical expression [59]. The
inset figure shows the optimal channel infidelity of GKP codes (square
lattice), cat codes (S=4), and binomial codes (S=1) [40].

Bosonic codes, or oscillator codes, are codes that encode a $d$-dimensional
logical space in the infinite-dimensional Hilbert space of oscillator(s). For
a bosonic code, the average excitation number,
$\bar{n}\mathrel{\mathop{\ordinarycolon}}=\Tr\left(\hat{n}\hat{P}_{L}\right)$,
affects code properties and is also a parameter of experimental interest. In
the inset plot of Fig. 3, we show the optimal performance of a few popular
bosonic codes under excitation loss [40], including the binomial code [8], the
cat code [7], and the GKP code [5]. An emerging feature is that for the
binomial and cat codes, their performance do not improve monotonically with
energy. On the contrary, the GKP code’s performance improves monotonically for
the range of $\bar{n}$ shown. Similar numerical observations were made in
previous works [12, 8], where heuristic explanations were given based on the
QEC matrix. Our expression Eq. (6) supports their arguments with rigor: like
perfect qubit codes, the cat code and binomial code perfectly correct no more
than $S$ excitation loss. Here, $S$ represents the fock basis spacing, which
can be understood as the distance against loss. However, they are completely
unprotected against more than $S$ loss, which is more likely to occur at
larger $\bar{n}$. Therefore, the infidelity is not suppressed with energy.

The critical difference of GKP codes is that while it generally cannot even
correct a single loss, the uncorrectable elements for all orders of loss are
suppressed by a factor of $e^{-\frac{\gamma}{\gamma+\frac{1}{\bar{n}}}}$ [12].
One open question was whether the suppression of the infidelity holds
asymptotically: optimizing for the optimal fidelity was only possible for
$\bar{n}\leq 10$ [12] because the Hilbert space size quickly becomes
unmanageable. The near-optimal fidelity solves the problem. Firstly, with the
QEC matrix being analytically computable, the only complexity cost for the
exact form in Eq. (4) is to compute the matrix square root. Thus, it is much
cheaper than SDP optimizations, and the numerical results can reach
$\bar{n}\sim 10^{2}$. Secondly, we can express the near-optimal performance
analytically with the perturbative form [59], which reveals the near-optimal
fidelity for arbitrarily large $\bar{n}$. In Fig. 3, we demonstrate the
results for a GKP square code under loss rate $\gamma=0.1$. At asymptotically
large $\bar{n}$, the perturbative expression converges as

$\displaystyle\lim_{\bar{n}\to\infty}1-\tilde{F}^{\text{opt}}=e^{-\frac{\pi}{2}\frac{1-\gamma}{\gamma}},$
(8)

which is approximately $7.2\times 10^{-7}$ for $\gamma=0.1$. As a comparison,
the best decoder with known performance at infinite energy is the
amplification decoder (AD) [12, 19]. For the same loss, AD gives a logical
error rate of $1-F^{\text{AD}}\approx
e^{-\frac{\pi}{8}\frac{1-\gamma}{\gamma}}=2.9\times 10^{-2}$. Therefore, while
the exceptionally low near-optimal fidelity highlights the promises of the GKP
code construction, its gap with the performance of the known decoders
emphasizes the potential gain in improving GKP decoders. Similar analysis can
be performed for general multi-mode GKP encodings [59].

Discussion.—We have derived the near-optimal channel fidelity as a
quantitative metric for arbitrary codes and noise channels. Our metric is
closely related to optimal code performances through narrow two-sided bounds.
Since the near-optimal fidelity only requires the QEC matrix as input, it
generalizes the KL conditions beyond distinguishing perfect QEC codes with the
same resource cost. To conclude, the proposed metric and its perturbative form
reduce computational costs for numerical simulations and enable us to obtain
analytical descriptions of code performances.

Our new approach opens doors to numerical benchmarking of large-sized codes
and oscillators encoding high-energy states. The benchmarking result can, in
turn, be used to optimize or guide the discovery of novel encoding and
efficient decoding for realistic noises. Moreover, it is critical to
understand the near-optimal performance of codes in asymptotic limits for many
concepts and settings in quantum information theory, such as the achievable
rate of a code family.

###### Acknowledgements.

We thank Victor Albert and Qian Xu for helpful discussions. We acknowledge
support from the ARO(W911NF-23-1-0077), ARO MURI (W911NF-21-1-0325), AFOSR
MURI (FA9550-19-1-0399, FA9550-21-1-0209), AFRL (FA8649-21-P-0781), DoE
Q-NEXT, NSF (OMA-1936118, ERC-1941583, OMA-2137642), NTT Research, and the
Packard Foundation (2020-71479). This material is based upon work partially
supported by the U.S. Department of Energy, Office of Science, National
Quantum Information Science Research Centers. The authors are also grateful
for the support of the University of Chicago Research Computing Center for
assistance with the numerical simulations carried out in this paper.

## References

  * Knill and Laflamme [1997] E. Knill and R. Laflamme, Phys. Rev. A 55, 900 (1997).
  * Bravyi and Kitaev [1998] S. B. Bravyi and A. Y. Kitaev, Quantum codes on a lattice with boundary (1998), arXiv:quant-ph/9811052 [quant-ph] .
  * Shor [1995] P. W. Shor, Phys. Rev. A 52, R2493 (1995).
  * Leung  _et al._ [1997] D. W. Leung, M. A. Nielsen, I. L. Chuang, and Y. Yamamoto, Phys. Rev. A 56, 2567 (1997).
  * Gottesman  _et al._ [2001] D. Gottesman, A. Kitaev, and J. Preskill, Phys. Rev. A 64, 012310 (2001).
  * Leghtas  _et al._ [2013] Z. Leghtas, G. Kirchmair, B. Vlastakis, R. J. Schoelkopf, M. H. Devoret, and M. Mirrahimi, Phys. Rev. Lett. 111, 120501 (2013).
  * Lescanne  _et al._ [2020] R. Lescanne, M. Villiers, T. Peronnin, A. Sarlette, M. Delbecq, B. Huard, T. Kontos, M. Mirrahimi, and Z. Leghtas, Nature Physics 16, 509 (2020).
  * Michael  _et al._ [2016] M. H. Michael, M. Silveri, R. T. Brierley, V. V. Albert, J. Salmilehto, L. Jiang, and S. M. Girvin, Phys. Rev. X 6, 031006 (2016).
  * Xu  _et al._ [2023a] Q. Xu, G. Zheng, Y.-X. Wang, P. Zoller, A. A. Clerk, and L. Jiang, npj Quantum Information 9, 78 (2023a).
  * Hashim  _et al._ [2021] A. Hashim, R. K. Naik, A. Morvan, J.-L. Ville, B. Mitchell, J. M. Kreikebaum, M. Davis, E. Smith, C. Iancu, K. P. O’Brien, I. Hincks, J. J. Wallman, J. Emerson, and I. Siddiqi, Phys. Rev. X 11, 041039 (2021).
  * Wallman and Emerson [2016] J. J. Wallman and J. Emerson, Phys. Rev. A 94, 052325 (2016).
  * Albert  _et al._ [2018] V. V. Albert, K. Noh, K. Duivenvoorden, D. J. Young, R. T. Brierley, P. Reinhold, C. Vuillot, L. Li, C. Shen, S. M. Girvin, B. M. Terhal, and L. Jiang, Phys. Rev. A 97, 032346 (2018).
  * Reimpell and Werner [2005] M. Reimpell and R. F. Werner, Phys. Rev. Lett. 94, 080501 (2005).
  * Fletcher  _et al._ [2007] A. S. Fletcher, P. W. Shor, and M. Z. Win, Phys. Rev. A 75, 012338 (2007).
  * Denys and Leverrier [2023] A. Denys and A. Leverrier, Quantum 7, 1032 (2023).
  * Note [1] The channel fidelity is equivalent to the entanglement fidelity for maximally entangled states.
  * Audenaert and De Moor [2002] K. Audenaert and B. De Moor, Phys. Rev. A 65, 030302 (2002).
  * Kosut and Lidar [2009] R. L. Kosut and D. A. Lidar, Quantum Information Processing 8, 443–459 (2009).
  * Noh  _et al._ [2019] K. Noh, V. V. Albert, and L. Jiang, IEEE Transactions on Information Theory 65, 2563 (2019).
  * Schlegel  _et al._ [2022] D. S. Schlegel, F. Minganti, and V. Savona, Phys. Rev. A 106, 022431 (2022).
  * Xu  _et al._ [2023b] Q. Xu, G. Zheng, Y.-X. Wang, P. Zoller, A. A. Clerk, and L. Jiang, npj Quantum Information 9, 78 (2023b).
  * Kosut  _et al._ [2008] R. L. Kosut, A. Shabani, and D. A. Lidar, Phys. Rev. Lett. 100, 020502 (2008).
  * Jayashankar  _et al._ [2020] A. Jayashankar, A. M. Babu, H. K. Ng, and P. Mandayam, Phys. Rev. A 101, 042307 (2020).
  * Leviant  _et al._ [2022] P. Leviant, Q. Xu, L. Jiang, and S. Rosenblum, Quantum 6, 821 (2022).
  * Barnum and Knill [2002] H. Barnum and E. Knill, Journal of Mathematical Physics 43, 2097 (2002).
  * Ng and Mandayam [2010] H. K. Ng and P. Mandayam, Phys. Rev. A 81, 062342 (2010).
  * Petz [1988] D. Petz, Quart. J. Math. Oxford Ser. 39, 97 (1988).
  * Wilde [2017] M. Wilde,  _Quantum Information Theory_ (Cambridge University Press, 2017).
  * Tyson [2010] J. Tyson, Journal of Mathematical Physics 51, 092204 (2010).
  * Bény [2011] C. Bény, Phys. Rev. Lett. 107, 080501 (2011).
  * Bény and Oreshkov [2010] C. Bény and O. Oreshkov, Phys. Rev. Lett. 104, 120501 (2010).
  * Mandayam and Ng [2012] P. Mandayam and H. K. Ng, Phys. Rev. A 86, 012335 (2012).
  * Junge  _et al._ [2018] M. Junge, R. Renner, D. Sutter, M. M. Wilde, and A. Winter, Annales Henri Poincaré 19, 2955–2978 (2018).
  * Brandão  _et al._ [2019] F. G. S. L. Brandão, E. Crosson, M. B. Şahinoğlu, and J. Bowen, Phys. Rev. Lett. 123, 110502 (2019).
  * Faist  _et al._ [2020] P. Faist, S. Nezami, V. V. Albert, G. Salton, F. Pastawski, P. Hayden, and J. Preskill, Phys. Rev. X 10, 041018 (2020).
  * Zhou  _et al._ [2021] S. Zhou, Z.-W. Liu, and L. Jiang, Quantum 5, 521 (2021).
  * Gilyén  _et al._ [2022] A. Gilyén, S. Lloyd, I. Marvian, Y. Quek, and M. M. Wilde, Phys. Rev. Lett. 128, 220502 (2022).
  * Horodecki  _et al._ [1999] M. Horodecki, P. Horodecki, and R. Horodecki, Phys. Rev. A 60, 1888 (1999).
  * Nielsen [2002] M. A. Nielsen, Physics Letters A 303, 249–252 (2002).
  * [40] See Supplemental Material for the formulation of optimization-based QEC, derivation of analytical results, and the definitions of noise channels and codes, which includes Ref. [60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70].
  * Berta and Tomamichel [2016] M. Berta and M. Tomamichel, IEEE Transactions on Information Theory 62, 1758 (2016).
  * Karimipour  _et al._ [2020] V. Karimipour, F. Benatti, and R. Floreanini, Phys. Rev. A 101, 032109 (2020).
  * Kribs  _et al._ [2005] D. Kribs, R. Laflamme, and D. Poulin, Phys. Rev. Lett. 94, 180501 (2005).
  * Koashi and Ueda [1999] M. Koashi and M. Ueda, Phys. Rev. Lett. 82, 2598 (1999).
  * Mohan  _et al._ [2023] A. Mohan, J. Sikora, and S. Upadhyay, (2023), arXiv:2312.04023 [quant-ph] .
  * Johnston  _et al._ [2023] N. Johnston, V. Russo, and J. Sikora, (2023), arXiv:2311.17047 [quant-ph] .
  * Jiang  _et al._ [2020] H. Jiang, T. Kathuria, Y. T. Lee, S. Padmanabhan, and Z. Song, in  _2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)_ (2020) pp. 910–918.
  * Note [2] $\tilde{\mathcal{O}}(g(n))$ is shortened for $\mathcal{O}(g(n)\log^{k}g(n))$.
  * Daletskii and Krein [1965] J. L. Daletskii and S. Krein, AMS Translations 2, (47)1 (1965).
  * Carlsson [2018] M. Carlsson, (2018), arXiv:1810.01464 [math.FA] .
  * Olle  _et al._ [2023] J. Olle, R. Zen, M. Puviani, and F. Marquardt, (2023), arXiv:2311.04750 [quant-ph] .
  * Zeng  _et al._ [2023] Y. Zeng, Z.-Y. Zhou, E. Rinaldi, C. Gneiting, and F. Nori, Phys. Rev. Lett. 131, 050601 (2023).
  * Korolev  _et al._ [2023] S. B. Korolev, E. N. Bashmakova, and T. Y. Golubeva, (2023), arXiv:2312.16000 [quant-ph] .
  * Cao  _et al._ [2022] C. Cao, C. Zhang, Z. Wu, M. Grassl, and B. Zeng, Quantum 6, 828 (2022).
  * Harrington and Preskill [2001] J. Harrington and J. Preskill, Phys. Rev. A 64, 062301 (2001).
  * Steane [1996] A. Steane, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 452, 2551–2577 (1996).
  * Rains  _et al._ [1997] E. M. Rains, R. H. Hardin, P. W. Shor, and N. J. A. Sloane, Phys. Rev. Lett. 79, 953 (1997).
  * Srednicki [1994] M. Srednicki, Phys. Rev. E 50, 888 (1994).
  * [59] G. Zheng, W. He, G. Lee, K. Noh, and L. Jiang, In preparation .
  * Caves [1999] C. M. Caves, Journal of Superconductivity 12, 707 (1999).
  * Nielsen and Chuang [2010] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ (Cambridge University Press, 2010).
  * Belavkin [1975] V. P. Belavkin, Radiotekhnika i Elektronika 20, 1177 (1975).
  * Kholevo [1979] A. S. Kholevo, Theory of Probability & Its Applications 23, 411 (1979), https://doi.org/10.1137/1123048 .
  * Hausladen and Wootters [1994] P. A. Hausladen and W. K. Wootters, Journal of Modern Optics 41, 2385 (1994).
  * Crooks [2008] G. E. Crooks, Phys. Rev. A 77, 034101 (2008).
  * Aw  _et al._ [2021] C. C. Aw, F. Buscemi, and V. Scarani, AVS Quantum Science 3, 045601 (2021).
  * Kwon and Kim [2019] H. Kwon and M. S. Kim, Phys. Rev. X 9, 031029 (2019).
  * Buscemi and Scarani [2021] F. Buscemi and V. Scarani, Phys. Rev. E 103, 052111 (2021).
  * Kwon  _et al._ [2022] H. Kwon, R. Mukherjee, and M. S. Kim, Phys. Rev. Lett. 128, 020403 (2022).
  * Biswas  _et al._ [2023] D. Biswas, G. M. Vaidya, and P. Mandayam, (2023), arXiv:2305.11093 [quant-ph] .

Supplemental Material: ”The near-optimal performance of quantum error
correction codes”

##  I Convex optimization for recovery

The problem setup for channel reversal is that we want to revert a general
channel
$\mathcal{A}\mathrel{\mathop{\ordinarycolon}}\mathcal{B}\left(\mathcal{H}_{d}\right)\to\mathcal{B}\left(\mathcal{H}_{n}\right)$
with a physical recovery,
$\mathcal{R}\mathrel{\mathop{\ordinarycolon}}\mathcal{B}\left(\mathcal{H}_{n}\right)\to\mathcal{B}\left(\mathcal{H}_{d}\right)$.
Then, we would want to minimize the distance between the composed channel,
$\mathcal{R}\circ\mathcal{A}$, and the identity channel. One of the distance
metrics is the channel fidelity. For a quantum channel
$\mathcal{Q}\mathrel{\mathop{\ordinarycolon}}\mathcal{B}\left(\mathcal{H}_{d}\right)\to\mathcal{B}\left(\mathcal{H}_{d}\right)$
with an operator sum representation,
$\mathcal{Q}\left(\rho\right)=\sum_{i}Q_{i}\rho Q_{i}^{\dagger}$, the channel
fidelity is defined as

$\displaystyle F\left(\mathcal{Q}\right)$
$\displaystyle\mathrel{\mathop{\ordinarycolon}}=$
$\displaystyle\bra{\Phi}\mathcal{Q}\otimes\mathcal{I}_{R}\left(\ket{\Phi}\bra{\Phi}\right)\ket{\Phi}$
(S1) $\displaystyle=$
$\displaystyle\frac{1}{d^{2}}\sum_{i}\absolutevalue{\text{Tr}\hat{Q}_{i}}^{2}$
(S2) $\displaystyle=$ $\displaystyle\frac{1}{d^{2}}\text{Tr}X_{\mathcal{Q}}$
(S3)

where $\ket{\Phi}$ is the purified maximally mixed state, $\mathcal{I}_{R}$ is
the identity channel acting on the _reference_ ancillary system, $d$ is the
input and output Hilbert space size, and $X_{\mathcal{Q}}$ is the
superoperator form [60] (also known as the matrix representation [61]) of
$\mathcal{Q}$. If $\mathcal{Q}=\mathcal{R}\circ\mathcal{A}$, a nice property
of the channel fidelity is that it can be expressed as a linear function of
the Choi matrix form of $\mathcal{R}$:

$\displaystyle F\left(\mathcal{R}\circ\mathcal{A}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{d^{2}}\text{Tr}\left(X_{\mathcal{R}}X_{\mathcal{A}}\right)=\frac{1}{d^{2}}\text{Tr}\left(C_{\mathcal{R}}\tilde{C}_{\mathcal{A}}\right)$
(S4)

where the Choi matrix $C_{\mathcal{M}}$ of any channel $\mathcal{M}$ is
defined to have an index form of
$\left(C_{\mathcal{M}}\right)_{[\mu\rho],[\nu\sigma]}=\bra{\rho}\mathcal{M}\left(\ket{\mu}\bra{\nu}\right)\ket{\sigma}$.
We also define the linear map
$\left(\tilde{C}_{\mathcal{M}}\right)_{[\mu\rho],[\nu\sigma]}=\left(C_{\mathcal{M}}\right)_{[\sigma\nu],[\rho\mu]}$
to make the linear dependence of $F$ on $C_{\mathcal{R}}$ more apparent.
Moreover, the constraints on the recovery channel being physical, i.e. a
completely positive trace-preserving map, can also be expressed through linear
functions of $C_{\mathcal{R}}$. As a result, we can formulate the channel
reversal problem as a convex optimization problem. The optimal recovery
$\mathcal{R}^{\text{opt}}$ and its performance can be found through

$\displaystyle\max_{C_{\mathcal{R}}}$
$\displaystyle\Tr\left\\{C_{\mathcal{R}}\tilde{C}_{\mathcal{A}}\right\\},$
(S5) s.t. $\displaystyle C_{\mathcal{R}}\succeq
0,\Tr_{\mathcal{H}_{n}}C_{\mathcal{R}}=I_{d}$ (S6)

which is a semidefinite program (SDP). Here, the partial trace notation
$\Tr_{\mathcal{H}_{n}}$ denotes tracing out the indices of the input system,
and $I_{d}$ is a $d\times d$ identity matrix. The first condition ensures the
recovery to be a completely positive map, while the second represents the
constraint of trace-preserving maps.

In the context of quantum error correction (QEC), the target channel to be
reverted is composed of the noise channel and the encoding channel,
$\mathcal{A}=\mathcal{N}\circ\mathcal{E}$. The scenario considered by the
original Knill-Laflamme conditions is the special case of pure state
encodings, where $\mathcal{E}$ is an isometry. The optimization result
specifies the optimal recovery and the optimal channel fidelity,
$F^{\text{opt}}=F\left(\mathcal{R}^{\text{opt}}\circ\mathcal{N}\circ\mathcal{E}\right)$.
Similarly, we can utilize the permutation invariant property of the trace and
similarly optimize the encoding. Since we optimize for the Choi matrix of the
recovery and/or encoding, the computational complexity is a high-order
polynomial or even exponential function of the system size.

Worth noticing, the Fock state basis may not be the most efficient basis for
representing the Choi matrix and, more generally, the code after noise. We can
learn from the transpose channel form and devise better forms to drastically
reduce the complexity required. Some recent works on antidistinguishability
[46] and quantum state discrimination [45] adopted similar ideas to improve
their SDP forms, and the improvement can be also extended to QEC.

##  II Transpose channel

The transpose channel (TC) [25, 26] is a member of the near-optimal channel
family. It has close connections with pretty good measurements [62, 63, 64]
and has applications in quantum information theory [65], quantum
thermodynamics [66, 67, 68], and many others. There is also active effort in
devising implementation schemes [37, 69, 70]. While there exist other recovery
channels with similar two-sided bounds as the transpose channel, such as the
quadratic recovery [29], the near-optimal expression we obtained from the
transpose channel is the most concise and informative by far.

The transpose channel, or other near-optimal channels, has a critical
property: its fidelity gives a two-sided bound of the optimal recovery
fidelity. In particular, for the transpose channel, it can be shown to bound
the optimal fidelity as $\left(F^{\text{opt}}\right)^{2}\leq
F(\mathcal{R}^{\text{TC}}\circ\mathcal{N}\circ\mathcal{E})\leq F^{\text{opt}}$
[25]. As a corrollary, we have

$\displaystyle\frac{1}{2}\left(1-F(\mathcal{R}^{\text{TC}}\circ\mathcal{N}\circ\mathcal{E})\right)\leq
1-F^{\text{opt}}\leq
1-F(\mathcal{R}^{\text{TC}}\circ\mathcal{N}\circ\mathcal{E}).$ (S7)

Since the goal is to find and benchmark good codes, we are mostly only
interested in codes that perform well against the noise channels of interest.
In these scenarios, the bound given by the TC channel is quite a tight bound
on the optimal recovery. Therefore, the transpose channel provides a
constructive channel that solves the slightly relaxed convex optimization
problem.

For a given logical code space projector $\hat{P}_{L}$ and noise channel
$\mathcal{N}\sim\mathinner{\left\\{\hat{N}_{i}\right\\}}$, the transpose
channel admits a Kraus operator representation of
$\mathcal{R}^{\text{TC}}\sim\mathinner{\left\\{\hat{R}_{i}^{\text{TC}}\right\\}}$,
where
$\hat{R}^{\text{TC}}_{i}\mathrel{\mathop{\ordinarycolon}}=\hat{P}_{L}\hat{N}_{i}^{\dagger}\mathcal{N}\left(\hat{P}_{L}\right)^{-\frac{1}{2}}$
for $i=0,\dots,L-1$. Here, we define $\hat{P}_{L}$ to be the projector onto
the logical code space. The inverse of $\mathcal{N}\left(\hat{P}\right)$ is
defined on its support, which is spanned by the error subspaces. For a high-
level understanding, the channel is a generalized version of the QEC recovery
procedure from KL conditions: $\mathcal{A}\left(\hat{P}\right)^{-\frac{1}{2}}$
performs measurements that project the state into carefully chosen subspaces,
and $\hat{P}\hat{N}_{i}^{\dagger}$ rotates them back into the corresponding
logical space. More rigorously, we can derive the following lemma.

######  Lemma 1.

Given noise channel $\mathcal{N}\sim\mathinner{\left\\{\hat{N}_{i}\right\\}}$
and logical codewords $\ket{\mu_{L}}$, the form of the transpose channel Kraus
operators is equivalent to

$\displaystyle\hat{R}_{l}^{\text{TC}}=\sum_{\mu,\nu,k}\left(M^{-\frac{1}{2}}\right)_{[\mu
l],[\nu k]}|\mu_{L}\rangle\left\langle\nu_{L}\right|\hat{N}_{k}^{\dagger}$
(S8)

where the inverse represents matrix pseudoinverse and the QEC matrix $M_{[\mu
l],[\nu
k]}\mathrel{\mathop{\ordinarycolon}}=\left\langle\mu_{L}\left|\hat{N}_{l}^{\dagger}\hat{N}_{k}\right|\nu_{L}\right\rangle$.

###### Proof.

The error subspace basis is defined by the set
$\mathinner{\left\\{\hat{N}_{l}\ket{\mu_{L}}\right\\}}$. It is worth noting
that this basis set is neither necessarily linear independent nor necessarily
complete on the Hilbert space. However, it provides us the sufficient basis to
express $\mathcal{N}\left(\hat{P}_{L}\right)^{-\frac{1}{2}}$ and consequently
$\hat{R}_{l}^{\text{TC}}$. To start with, we can write a projection operator
on this subspace

$\displaystyle\hat{P}_{N}=\sum_{l,k,\mu,\nu}\left(M^{-1}\right)_{[\mu l],[\nu
k]}\hat{N}_{l}|\mu\rangle\left\langle\nu\right|\hat{N}_{k}^{\dagger},$ (S9)

where $M^{-1}$ is the pseudoinverse of $M$. The projector expression can be
verified through checking that its matrix element $M_{[\mu l],[\nu
k]}=\left\langle\mu_{L}\left|\hat{N}_{l}^{\dagger}\hat{P}_{N}\hat{N}_{k}\right|\nu_{L}\right\rangle$
behaves as a projection operator.

Notice that
$\mathcal{N}\left(\hat{P}_{L}\right)=\sum_{l,\mu}\hat{N}_{l}\ket{\mu_{L}}\bra{\mu_{L}}\hat{N}_{l}^{\dagger}$.
We can then derive representation of
$\mathcal{N}\left(\hat{P}_{L}\right)^{-\frac{1}{2}}$ in the error subspace
basis as

$\displaystyle\mathcal{N}\left(\hat{P}_{L}\right)^{-\frac{1}{2}}=\sum_{l,k,\mu,\nu}\left(M^{-\frac{3}{2}}\right)_{[\mu
l],[\nu
k]}\hat{N}_{l}|\mu_{L}\rangle\left\langle\nu_{L}\right|\hat{N}_{k}^{\dagger}.$
(S10)

We can either derive step-by-step or straightforwardly verify from the
definition of $\mathcal{N}\left(\hat{P}_{L}\right)^{-\frac{1}{2}}$:

$\displaystyle\mathcal{N}\left(\hat{P}_{L}\right)^{-\frac{1}{2}}\mathcal{N}\left(\hat{P}_{L}\right)\mathcal{N}\left(\hat{P}_{L}\right)^{-\frac{1}{2}}=\hat{P}_{N}.$
(S11)

With the expression presented in Eq. (S10), the transpose channel Kraus can be
written in the form of

$\displaystyle\hat{R}^{\text{TC}}_{l}$
$\displaystyle\mathrel{\mathop{\ordinarycolon}}=$
$\displaystyle\hat{P}_{L}\hat{N}_{l}^{\dagger}\mathcal{N}\left(\hat{P}_{L}\right)^{-\frac{1}{2}}$
(S12) $\displaystyle=$
$\displaystyle\sum_{\mu}\ket{\mu_{L}}\bra{\mu_{L}}\hat{N}_{l}^{\dagger}\sum_{p,k,\eta,\nu}\left(M^{-\frac{3}{2}}\right)_{[\eta
p],[\nu
k]}\hat{N}_{p}|\eta_{L}\rangle\left\langle\nu_{L}\right|\hat{N}_{k}^{\dagger}$
(S13) $\displaystyle=$
$\displaystyle\sum_{\mu,\nu,k}\left(M^{-\frac{1}{2}}\right)_{[\mu l],[\nu
k]}|\mu_{L}\rangle\left\langle\nu_{L}\right|\hat{N}_{k}^{\dagger}.$ (S14)

∎

Although we assume isometry encoding for simplicity, it is straightforward to
extend our result to the context of general channel reversal problems. For
example, for mixed-state encodings, we can combine the encoding channel with
the noise channel and revert the composed channel. For other codes like
subsystem codes, the transpose channel is also valid following, for example,
Ref. [32].

While Eq. (S8) is useful for our proof of the near-optimal fidelity
expression, it is not so intuitive. We can arrive at a more intuitive
expression by defining a set of new basis

$\displaystyle\ket{\psi_{i}}\mathrel{\mathop{\ordinarycolon}}=\sum_{[\nu
k]}\left(M^{-\frac{1}{2}}\right)^{\ast}_{i,[\nu k]}\hat{N}_{k}\ket{\nu_{L}},$
(S15)

which is not necessarily a set of orthonormal basis. In fact, since $M$ is a
Hermitian matrix, we can check that
$\langle\phi_{j}|\phi_{i}\rangle=M^{-\frac{1}{2}}_{j,[\mu
l]}\left(M^{-\frac{1}{2}}\right)^{\ast}_{i,[\nu
k]}\bra{\mu}\hat{N}_{l}^{\dagger}\hat{N}_{k}\ket{\nu}=\left(M^{-1/2}MM^{-1/2}\right)_{j,i}$,
which only guarantees orthonormality of the basis if $M$ is full rank. The
transpose channel Kraus operators can be conveniently expressed as

$\displaystyle\hat{R}_{l}^{\text{TC}}=\sum_{\mu}\ket{\mu_{L}}\langle\psi_{[\mu
l]}|.$ (S16)

This form of the transpose channel Kraus operators can be interpreted as
following: for each logical codeword $\ket{\mu_{L}}$ and noise Kraus operator
with label $l$, the physical operation of the transpose channel is to measure
the projector $|\psi_{[\mu l]}\rangle\langle\psi_{[\mu l]}|$ and perform a
rotation back to the logical codeword $\ket{\mu_{L}}$ accordingly.

##  III Derivation of the near-optimal fidelity expression

With Lemma. 1, we arrive at our main result, Theorem 1 in the main text.

######  Theorem.

For a $d$-dimensional encoding, $\mathcal{E}$, and noise channel
$\mathcal{N}$, the near-optimal fidelity is defined as

$\displaystyle\tilde{F}^{\text{opt}}=\frac{1}{d^{2}}\left\|\operatorname{Tr}_{L}\sqrt{M}\right\|_{F}^{2},$
(S17)

where $M$ is the QEC matrix,
$\left(\operatorname{Tr}_{L}B\right)_{l,k}=\sum_{\mu}B_{[\mu l],[\mu k]}$
denotes the partial trace over the code space indices, and $||\cdot||_{F}$ is
the Frobenius norm. The near-optimal fidelity gives a two-sided bound on the
optimal fidelity as

$\displaystyle\frac{1}{2}\left(1-\tilde{F}^{\text{opt}}\right)\leq
1-F^{\text{opt}}\leq 1-\tilde{F}^{\text{opt}}.$ (S18)

###### Proof.

The near-optimal fidelity is defined as the fidelity achieved by the transpose
channel recovery,
$\tilde{F}^{\text{opt}}\mathrel{\mathop{\ordinarycolon}}=F\left(\mathcal{R}^{\text{TC}}\circ\mathcal{N}\circ\mathcal{E}\right)$.
Substituting Lemma 1 into Eq. (S2), we have

$\displaystyle\tilde{F}^{\text{opt}}$ $\displaystyle=$
$\displaystyle\frac{1}{d^{2}}\sum_{i,j}\left|\operatorname{Tr}\left(\hat{R}^{\text{TC}}_{i}\hat{N}_{j}\right)\right|^{2}$
(S19) $\displaystyle=$
$\displaystyle\frac{1}{d^{2}}\sum_{i,j}\left|\operatorname{Tr}\left(\sum_{\mu,\nu,k}\left(M^{-\frac{1}{2}}\right)_{[\mu
i],[\nu
k]}|\mu_{L}\rangle\left\langle\nu_{L}\right|\hat{N}_{k}^{\dagger}\hat{N}_{j}\right)\right|^{2}$
(S20) $\displaystyle=$
$\displaystyle\frac{1}{d^{2}}\sum_{i,j}\left|\sum_{\mu}\left(M^{\frac{1}{2}}\right)_{[\mu
i],[\mu j]}\right|^{2}$ (S21) $\displaystyle=$
$\displaystyle\frac{1}{d^{2}}\left\|\text{Tr}_{L}\sqrt{M}\right\|_{F}^{2}$
(S22)

where we have used the cyclicity of trace and the definition of the Frobenius
norm
$||B||_{F}\mathrel{\mathop{\ordinarycolon}}=\sum_{i,j}\absolutevalue{B_{i,j}}^{2}$

∎

In some cases, we might also be dealing with non-orthonormal codewords. As an
example, finite-energy GKP codes generally have non-orthonormal codewords.
When we want to obtain a valid near-optimal fidelity for the orthonormalized
codewords, it is convenient to have the following corollary.

######  Corollary 2.

For any non-orthonormal codeword with overlap matrix

$\displaystyle
m_{\mu,\nu}\mathrel{\mathop{\ordinarycolon}}=\bra{\mu_{L}}\ket{\nu_{L}},$
(S23)

the near-optimal fidelity in Theorem 1 has the form of

$\displaystyle\tilde{F}^{\text{opt}}=\frac{1}{d^{2}}\left\|\operatorname{Tr}_{L}\sqrt{(m^{-1}\otimes
I_{l})M}\right\|_{F}^{2},$ (S24)

where $I_{l}$ is a $l\times l$ identity matrix, and $l$ is the number of Kraus
operators of the noise channel $\mathcal{N}$.

###### Proof.

Assume that with the, not necessarily orthonormal, original codewords
$\ket{\mu_{L}}$, we obtain the QEC matrix $M$. Moreover, we can always find a
matrix $A$, such that $AA^{\dagger}=m^{-1}\otimes I_{l}$. Consequently,
$A^{\dagger}(m\otimes I_{l})A=I$ and orthonormalizes the codewords. The QEC
matrix obtained from the orthonormalized codewords, $M^{\prime}$, is related
to the original QEC matrix via $M^{\prime}=A^{\dagger}MA$. Therefore, based on
Theorem 1, we have

$\displaystyle\tilde{F}^{\text{opt}}$
$\displaystyle=\frac{1}{d^{2}}\left\|\operatorname{Tr}_{L}\sqrt{M^{\prime}}\right\|_{F}^{2}.$
(S25)

Because of the tensor product structure of $m\otimes I_{l}$, we can write
$A=B\otimes I_{l}$ and still utilize the cyclicity of the partial trace:

$\displaystyle\operatorname{Tr}_{L}\sqrt{M^{\prime}}=\operatorname{Tr}_{L}A\sqrt{M^{\prime}}A^{-1}=\operatorname{Tr}_{L}\sqrt{AM^{\prime}A^{-1}}=\operatorname{Tr}_{L}\sqrt{AA^{\dagger}M}=\operatorname{Tr}_{L}\sqrt{(m^{-1}\otimes
I_{l})M}.$ (S26)

Substituting Eq. (S26) into Eq. (S25), we conclude the proof.

∎

##  IV Derivation of the perturbative form of the near-optimal fidelity and
its properties

Here we attempt to prove Corollary. 1, which is a perturbative expansion of
Theorem 1. Such a perturbative expansion can lead to fruitful analytical
results, as we have demonstrated for the thermodynamic code and the GKP code
in the main text.

######  Corollary.

With a suitable choice of unitary gauge, there exists a decomposition of the
QEC matrix $M$ such that $D=\frac{1}{d}\operatorname{Tr}_{L}M$ is diagonal.
With the residual matrix $\Delta
M\mathrel{\mathop{\ordinarycolon}}=M-I_{L}\otimes D$, the near-optimal
infidelity has a perturbative expansion through

$\displaystyle 1-\tilde{F}^{\text{opt}}=\frac{1}{d}\norm{f(D)\odot\Delta
M}_{F}^{2}+\mathcal{O}\left(\norm{f(D)\odot\Delta M}_{F}^{3}\right)$ (S27)

where we define $f(D)_{[\mu l],[\nu k]}=\frac{1}{\sqrt{D_{ll}}+\sqrt{D_{kk}}}$
and the Hadamard product to be $\left(A\odot B\right)_{ij}=A_{ij}B_{ij}$.

###### Proof.

Given the decomposition $M=I_{L}\otimes D+\Delta M$, where matrix $D$ is
diagonal and $D\succ 0$ (since we can truncate the $M$ matrix and discard the
channel subspaces which vanish, $D_{ii}=0$). If we treat $\Delta M$ as a
perturbation, we can perturbatively expand the matrix square root such that

$\displaystyle\sqrt{M}$ $\displaystyle=$ $\displaystyle
I_{L}\otimes\sqrt{D}+f(D)\odot\Delta M-f(D)\odot\left(f(D)\odot\Delta
M\right)^{2}+\mathcal{O}\left(\norm{f(D)\odot\Delta M}_{F}^{3}\right).$ (S28)

This is a second-order expansion from the Daleckii-Krein theorem [49, 50],
where more general matrix functions were treated. Notice that $\text{Tr}D=1$
and $\text{Tr}\Delta M=0$. We can then derive that

$\displaystyle 1-\tilde{F}^{\text{opt}}$
$\displaystyle=1-\frac{1}{d^{2}}\left\|\operatorname{Tr}_{L}\sqrt{M}\right\|_{F}^{2}$
(S29)
$\displaystyle=1-\text{Tr}D+\Tr\left(\frac{1}{d}\Tr_{L}\left(f(D)\odot\Delta
M\right)^{2}\right)+\mathcal{O}\left(\norm{f(D)\odot\Delta M}_{F}^{3}\right)$
(S30) $\displaystyle=\frac{1}{d}\norm{f(D)\odot\Delta
M}_{F}^{2}+\mathcal{O}\left(\norm{f(D)\odot\Delta M}_{F}^{3}\right)$ (S31)

Here, in the big-$\mathcal{O}$ notation, we omit factors of $d$ by assuming it
is a constant.

∎

As mentioned in the main text, we can choose to determine $D$ not through
performing a unitary rotation but instead truncating the off-diagonal terms in
$\frac{1}{d}\operatorname{Tr}_{L}M$. Such a choice can be more convenient when
the analytical expression for the unitary rotation is unknown. In this
scenario, we end up with $\text{Tr}\Delta M\neq 0$ and $\Tr D\neq 1$.
Physically, we are distributing some of the correctable parts into the
uncorrectable off-diagonal part of the QEC matrix, thus overestimating the
near-optimal channel infidelity. The perturbative form is modified to be

$\displaystyle 1-\tilde{F}^{\text{opt}}=\frac{1}{d}\norm{f(D)\odot\Delta
M}_{F}^{2}-\left(\Tr_{L}f(D)\odot\Delta
M\right)^{2}+\mathcal{O}\left(\norm{f(D)\odot\Delta M}_{F}^{3}\right).$ (S32)

Therefore, with such a choice of $D$, the resulting infidelity is a good
approximation as long as
$\norm{f(D)\odot\left(\frac{1}{d}\operatorname{Tr}_{L}M-D\right)}_{F}^{2}\ll\frac{1}{d}\norm{f(D)\odot\Delta
M}_{F}^{2}$. Moreover, if higher precision is required, it is certainly
possible to have higher orders of perturbative expressions through the
definition of Fretchet derivatives or through solving the iterative relations
order-by-order.

For a more intuitive understanding of the perturbative form, we can rewrite it
as

$\displaystyle 1-F^{\text{opt}}=\frac{1}{d}\left(\sum_{[\mu l]\neq[\nu
k]}\frac{p_{[\mu l]}p_{[\nu
k]}}{\left(\sqrt{\bar{p}_{l}}+\sqrt{\bar{p}_{k}}\right)^{2}}\Tr{\hat{P}_{[\mu
l]}\hat{P}_{[\nu k]}}+\sum_{[\mu l]}\frac{\left(p_{[\mu
l]}-\bar{p}_{l}\right)^{2}}{4\bar{p}_{l}}\right)+\mathcal{O}\left(\norm{f(D)\odot\Delta
M}_{F}^{3}\right).$ (S33)

Here, we define the error subspace projectors as $\hat{P}_{[\mu
l]}\mathrel{\mathop{\ordinarycolon}}=\frac{\hat{N}_{l}\ket{\mu_{L}}\bra{\mu_{L}}\hat{N}_{l}^{\dagger}}{p_{[\mu
l]}}$, where $p_{[\mu
l]}\mathrel{\mathop{\ordinarycolon}}=\bra{\mu}\hat{N}_{l}^{\dagger}\hat{N}_{l}\ket{\mu}$
and represents the probability of measuring $\ket{\mu,l}$ if we initialize in
$\ket{\mu}$. The probability of measuring noise Kraus operator $l$ is
$\bar{p}_{l}=\frac{1}{d}\sum_{\mu=0}^{d-1}p_{[\mu l]}$. In the expression, the
second term contains the errors from different logical codewords reacting
differently to the same noise Kraus operator, which leaks information to the
environment. The first term includes logical flip errors (reverting to a
different logical state) and dephasing errors (reverting to the same logical
state but with an incorrect phase).

Moreover, the perturbative form possesses a special property when it vanishes:

######  Corollary 3.

As $\frac{1}{d}\norm{f(D)\odot\Delta M}_{F}^{2}\to 0$, the near-optimal
fidelity

$\displaystyle\tilde{F}^{\text{opt}}\to\Tr{D}.$ (S34)

###### Proof.

Here, we define
$\Delta\mathrel{\mathop{\ordinarycolon}}=\frac{1}{d}\absolutevalue{\norm{\Tr_{L}\sqrt{M}}_{F}-\norm{\Tr_{L}\sqrt{I_{\mu}\otimes
D}}_{F}}$, and we show that $\Delta$ vanishes when the perturbative expression
vanishes, i.e. $\frac{1}{d}\norm{f(D)\odot\Delta M}_{F}^{2}\to 0$. First,
notice some matrix identities

$\displaystyle\Delta$ $\displaystyle\leq$
$\displaystyle\frac{1}{d}\norm{\Tr_{L}\sqrt{M}-\Tr_{L}\sqrt{I_{L}\otimes
D}}_{F}$ (S35) $\displaystyle\leq$
$\displaystyle\frac{1}{\sqrt{d}}\norm{\sqrt{M}-\sqrt{I_{L}\otimes D}}_{F}$
(S36) $\displaystyle\leq$
$\displaystyle\norm{\sqrt{\frac{M}{d}}-\sqrt{\frac{I_{L}\otimes D}{d}}}_{F}$
(S37)

The first inequality applies Von Neumann’s trace inequality to obtain that for
any two Hermitian matrices $A,B\succeq 0$,
$\norm{A-B}_{F}\geq\norm{A}_{F}-\norm{B}_{F}$. In the second inequality, we
proceeded by decomposing any matrix $X=\sum_{i}Y_{i}\otimes\sigma_{i}$, where
$\sigma_{i}$ are the Gell-mann matrices, and show that
$\norm{X}_{F}\geq\frac{1}{\sqrt{d}}\norm{\Tr_{L}X}_{F}$, where $d$ is the
logical dimension. Notice that from the definition of Fretchet derivatives and
the Daleckii-Krein theorem,

$\displaystyle\sqrt{M}=\sqrt{I_{L}\otimes D}+f(D)\odot\Delta M+o(\Delta M).$
(S38)

Since $D\succ 0$ and $\Tr{D}\leq 1$, $\norm{f(D)\odot\frac{\Delta
M}{\sqrt{d}}}_{F}\to 0$ implies that $\norm{\frac{\Delta M}{\sqrt{d}}}_{F}\to
0$. Thus,

$\displaystyle\lim_{\frac{\Delta M}{\sqrt{d}}\to 0}\Delta$ $\displaystyle\leq$
$\displaystyle\lim_{\frac{\Delta M}{\sqrt{d}}\to
0}\norm{f(\frac{D}{d})\odot\frac{\Delta M}{d}+o(\frac{\Delta M}{d})}_{F}$
(S39) $\displaystyle=$ $\displaystyle\norm{f(D)\odot\frac{\Delta
M}{\sqrt{d}}}_{F}$ (S40) $\displaystyle=$ $\displaystyle 0$ (S41)

where the last equality holds by assumption. Therefore, in the limit of
$\frac{1}{d}\norm{f(D)\odot\Delta M}_{F}^{2}\to 0$,

$\displaystyle\tilde{F}^{\text{opt}}=\frac{1}{d^{2}}\left\|\operatorname{Tr}_{L}\sqrt{M}\right\|_{F}^{2}=\frac{1}{d^{2}}\left\|\operatorname{Tr}_{L}\sqrt{I_{L}\otimes
D}\right\|_{F}^{2}=\Tr D.$ (S42)

∎

A special case is when $D$ contains all the correctable elements, i.e.
$\text{Tr}D=1$, where both the near-optimal and the optimal fidelity will be
unity.

##  V Definitions and notations for examples of applications

###  V.1 Noise models

Here we define the noise models that appeared in the examples we provided in
the main text. The single qubit amplitude damping noise is defined as
$\mathcal{N}(\hat{\rho})=\hat{K}_{0}\hat{\rho}\hat{K}_{0}^{\dagger}+\hat{K}_{1}\hat{\rho}\hat{K}_{1}^{\dagger}$,
where

$\hat{K}_{0}=\ket{0}\bra{0}+\sqrt{1-p}\ket{0}\bra{0},\hat{K}_{1}=\sqrt{p}\ket{0}\bra{1},$
(S43)

with $p$ being the damping probability. The amplitude damping noise is a non-
Pauli noise, and it is unclear how to optimally decode it for, for example,
stabilizer codes. Therefore, a common choice is to perform Pauli Twirling to
convert it into a Pauli channel. A channel is a Pauli channel if it has the
form of

$\mathcal{N}(\hat{\rho})=\left(1-p_{X}-p_{Y}-p_{Z}\right)\hat{\rho}+p_{X}\hat{X}\hat{\rho}\hat{X}+p_{Y}\hat{Y}\hat{\rho}\hat{Y}+p_{Z}\hat{Z}\hat{\rho}\hat{Z}.$
(S44)

The depolarizing noise channel with error probability $p$ has
$p_{X}=p_{Y}=p_{Z}=p$.

For codes encoded in an oscillator, the excitation loss noise channel, also
known as the pure loss channel, has the form of
$\mathcal{N}(\hat{\rho})=\sum_{i=0}^{\infty}\hat{N}_{l}\hat{\rho}\hat{N}_{l}^{\dagger}$,
where

$\hat{N}_{l}=\left(\frac{\gamma}{1-\gamma}\right)^{l/2}\frac{\hat{a}^{l}}{\sqrt{l!}}\left(1-\gamma\right)^{\hat{n}/2},$
(S45)

and $\hat{n}=\hat{a}^{\dagger}\hat{a}$ is the number operator. Here, $\gamma$
is the loss parameter.

###  V.2 Code definitions

For the standard qubit codes, we refer interested readers to the original
references [56, 4, 4, 57]. We focus on the definitions for the bosonic codes,
which largely follow the definitions in Ref. [12].

Cat codes are characterized by the coherent state amplitude, $\alpha$, and the
loss spacing, $S$, which is also known as the number of legs. The codewords
are defined as

$\displaystyle\ket{0_{L}}$ $\displaystyle\propto\hat{\Pi}_{0}\ket{\alpha}$
(S46) $\displaystyle\ket{1_{L}}$
$\displaystyle\propto\hat{\Pi}_{S+1}\ket{\alpha},$

where we omit the normalization factors for simplicity. Here,
$\hat{\Pi}_{0}=\sum_{n=0}^{\infty}|2n(S+1)\rangle\langle 2n(S+1)|$ and
$\hat{\Pi}_{S+1}=\sum_{n=0}^{\infty}|(2n+1)(S+1)\rangle\langle(2n+1)(S+1)|$
are projectors onto Fock states that are $0$ and $S+1$ mod $2(S+1)$
respectively. In the special case of $S=0$, they are the even and odd parity
space projectors. Notice that since the codewords’ support in the Fock basis
has a spacing of $S+1$, the error subspace is orthogonal and perfectly
correctable as long as we consider less than $S+1$ excitation loss.
Nevertheless, it is unnecessary to have a complete separation in terms of
their Fock state support: two states supported in the same generalized parity
space can still be orthogonal. For example, the recently discovered squeezed
cat code. [21] explores such a property. The squeezed cat code has its
codewords living in the even and odd parity spaces, i.e. $S=0$ in the
convention of cat codes. However, in the limit of infinite squeezing, the code
can still correct single excitation loss because of the orthogonality
mentioned.

Binomial codes are characterized by the loss spacing, $S$, and the dephasing
spacing, $N$. The codewords are defined as

$\displaystyle\ket{0_{L}}$
$\displaystyle=\frac{1}{\sqrt{2^{N+1}}}\sum_{m=0}^{N+1}\sqrt{{N+1\choose
m}}\ket{(S+1)m}$ (S47) $\displaystyle\ket{1_{L}}$
$\displaystyle=\frac{1}{\sqrt{2^{N+1}}}\sum_{m=0}^{N+1}\left(-1\right)^{m}\sqrt{{N+1\choose
m}}\ket{(S+1)m}.$

It is clear that if we switch the basis to $\ket{\pm_{L}}$, the binomial code
is protected by the Fock state subspace spacing very similar to the cat code.
Therefore, it possesses the same property that it can perfectly correct less
than $S+1$ excitation loss.

The ideal GKP, which has infinite energy is defined on top of a symplective
lattice. In the main text, we gave the square lattice as an example. In the
position basis, we have that

$\displaystyle\ket{0_{L}}$
$\displaystyle\propto\sum_{n\in\mathbb{Z}}\ket{2n\sqrt{\pi}}_{x}$ (S48)
$\displaystyle\ket{1_{L}}$
$\displaystyle\propto\sum_{n\in\mathbb{Z}}\ket{(2n+1)\sqrt{\pi}}_{x}.$

Since these codewords are not physical, we apply a Gaussian envelope. We
define the finite-energy GKP codes as

$\ket{\mu^{\Delta}_{L}}\propto e^{-\Delta^{2}\hat{n}}\ket{\mu_{L}}$ (S49)

where we omit the normalization factor. For GKP codes encoding two logical
dimensions, the codewords live in the even parity subspace. Therefore, they
are perfect codes against a single excitation loss, but for more loss, they
are approximate codes. For general lattices and logical dimensions, the
separation in parity does not necessarily hold.

##  VI Thermodynamic code and derivations

###  VI.1 Code definition

Thermodynamic codes were first proposed in Ref. [34], where it was observed
that the Eigenstate Thermalization Hypothesis automatically yielded
approximate error correction codes in the bulk of the spectrum. We focus here
on the simplest thermodynamic code, which can be seen as either an ETH code
with respect to the one local Hamiltonian $\sum_{i}(I-\sigma_{z}^{i})$, or a
ground state encoding in the ferromagnetic Heisenberg model. The code words on
$N$ modes, for $m=0,1,...,N$ are

$|h_{m}^{N}\rangle=\genfrac{(}{)}{0.0pt}{0}{N}{N/2+m/2}^{-1/2}\sum_{\mathbf{s}\mathrel{\mathop{\ordinarycolon}}\sum_{j}s_{j}=m}|\mathbf{s}\rangle_{N},$
(S50)

where $s_{j}=\pm 1$.

We focus on a logical qubit with $k=2$. To define a logical qubit, we pick
some $d<N,m_{0}<N-d$ and take

$\displaystyle|0_{L}\rangle$ $\displaystyle=|h_{m_{0}}^{N}\rangle,$ (S51)
$\displaystyle|1_{L}\rangle$ $\displaystyle=|h_{m_{0}+d}^{N}\rangle,$

where $d$ is the distance of the code.

###  VI.2 One erasure

We first work out the case of a single erasure. The error channel can be
written with Kraus operators

$\displaystyle K_{0}$ $\displaystyle=\sqrt{1-p}I,$ (S52) $\displaystyle K_{1}$
$\displaystyle=\sqrt{p}|\Omega\rangle\langle-1|,$ $\displaystyle K_{2}$
$\displaystyle=\sqrt{p}|\Omega\rangle\langle 1|,$

where $p$ is the probability of erasure, and $|\Omega\rangle$ is some external
state, orthonormal to $|1\rangle,|-1\rangle$, representing an erased qubit.
Since the codewords are permutation invariant, without loss of generality, we
can set the error-prone qubit to be the first qubit. Then the above Kraus
operators are only supported on the first qubit, with identity on the rest of
the system. We want to calculate the relevant QEC matrix.

First, note that if we simply pick $d>2$ we will have
$M_{l,\mu,l^{\prime},\nu}\propto\delta_{\mu,\nu}\delta_{l,l^{\prime}}$ such
that

$M=\sum_{l,\mu}c_{\mu,l}|l\rangle\langle l|\otimes|\mu\rangle\langle\mu|.$
(S53)

Then, for this problem, Eq. (S17) simplifies to

$1-\tilde{F}^{\text{opt}}=1-\frac{1}{4}\sum_{l}\left(\sum_{\mu}\sqrt{c_{\mu,l}}\right)^{2}.$
(S54)

We simply have to calculate $c_{\mu,l}$, which are defined by

$\langle\mu_{L}|K_{l}^{{\dagger}}K_{l}|\mu_{L}\rangle.$ (S55)

For $l=0$ this is simply $1-p$. Suppose $\mu_{L}$ has magnetization $m$. Then
$K_{1}$ increases the magnetization by $1$, so that this simply counts the
number of states on $N-1$ qubits with magnetization $m+1$. Similarly, $K_{2}$
decreases the magnetization by $1$. Then we have

$\displaystyle\langle
h_{m}^{N}|K_{1}^{{\dagger}}K_{1}|h_{m}^{N}\rangle=p\frac{{N-1\choose(N+m)/2}}{{N\choose(N+m)/2}}=\frac{p}{2}(1-m/N),\qquad$
$\displaystyle\langle
h_{m}^{N}|K_{2}^{{\dagger}}K_{2}|h_{m}^{N}\rangle=p\frac{{N-1\choose(N+m-2)/2}}{{N\choose(N+m)/2}}=\frac{p}{2}(1+m/N)$
(S56)

Specializing to the chosen codewords,

$\displaystyle\sum_{l}\left(\sum_{\mu}\sqrt{c_{\mu,l}}\right)^{2}$
$\displaystyle=\sum_{l=0}^{2}\left(\sqrt{\langle
h_{m_{0}}^{N}|K_{l}^{{\dagger}}K_{l}|h_{m_{0}}^{N}\rangle}+\sqrt{\langle
h_{m_{0}+d}^{N}|K_{l}^{{\dagger}}K_{l}|h_{m_{0}+d}^{N}\rangle}\right)^{2}$
(S57)
$\displaystyle=4(1-p)+\frac{p}{2}\left(\sqrt{1-\frac{m_{0}}{N}}+\sqrt{1-\frac{m_{0}+d}{N}}\right)^{2}+\frac{p}{2}\left(\sqrt{1+\frac{m_{0}}{N}}+\sqrt{1+\frac{m_{0}+d}{N}}\right)^{2}$
$\displaystyle=4(1-p)+2p+p\sqrt{1-\frac{m_{0}}{N}}\sqrt{1-\frac{m_{0}+d}{N}}+p\sqrt{1+\frac{m_{0}}{N}}\sqrt{1+\frac{m_{0}+d}{N}}$

The most straightforward way to pick two states in the middle of the spectrum
is to take $m_{0}=-d/2$. We can treat $x\equiv d/N$ as a small parameter in
the thermodynamic limit. The exact expression is

$1-\tilde{F}^{\text{opt}}=\frac{1}{2}p(1-\sqrt{1-x^{2}/4}).$ (S58)

For small $x$, we get

$1-\tilde{F}^{\text{opt}}=\frac{1}{16}px^{2}=\frac{1}{16}p\frac{d^{2}}{N^{2}}$
(S59)

which has the expected $1/N^{2}$ scaling [35]. At first glance, a strange
property of this scaling is that infidelity increases with distance. We can
understand this as follows: once $d>2$, the QEC matrix becomes diagonal. Then,
infidelity is given by how close the diagonal elements are to each other. The
smaller $d$ is, the closer the codewords are to each other, such that the
diagonal elements become more similar. Another way to think about this is that
now $d$ controls how far from the exact middle of the spectrum we are.

###  VI.3 Two erasures

We now fix two qubits $i,j$ where erasures occur. Again, without loss of
generality, we can simply think of these as the first two qubits. If we pick
$d>4$, the QEC matrix will be diagonal along the codewords – however, it will
not be diagonal along the Kraus operators. We can index Kraus operators by
$(\alpha,\beta)$, and write

$\displaystyle M$
$\displaystyle=\sum_{\mu}\sum_{\alpha,\beta,\alpha^{\prime},\beta^{\prime}}c_{\mu,(\alpha,\beta),(\alpha^{\prime},\beta^{\prime})}|\alpha,\beta\rangle\langle\alpha^{\prime},\beta^{\prime}|\otimes|\mu\rangle\langle\mu|$
(S60)

This is certainly diagonal for the case where there is only an error on one
qubit, as we know from studying one erasure, so

$\displaystyle M=$
$\displaystyle\sum_{\mu}c_{\mu,(0,0),(0,0)}|0,0\rangle\langle
0,0|\otimes|\mu\rangle\langle\mu|$ (S61)
$\displaystyle+\sum_{\mu}\sum_{\alpha\neq
0}c_{\mu,(\alpha,0),(\alpha,0)}\left(|\alpha,0\rangle\langle\alpha,0|+|0,\alpha\rangle\langle
0,\alpha|\right)\otimes|\mu\rangle\langle\mu|$
$\displaystyle+\sum_{\mu}\sum_{\alpha\neq 0,\beta\neq 0,\alpha^{\prime}\neq
0,\beta^{\prime}\neq
0}c_{\mu,(\alpha,\beta),(\alpha^{\prime},\beta^{\prime})}|\alpha,\beta\rangle\langle\alpha^{\prime},\beta^{\prime}|\otimes|\mu\rangle\langle\mu|,$

where the first row corresponds to no error, the second row to one error, and
the last row to two errors. The one error elements can be read off using the
results of the previous section:
$c_{\mu,(0,0),(0,0)}=(1-p)^{2},c_{\mu,(1,0),(1,0)}=\frac{1}{2}p(1-p)(1-m_{0}/N),c_{\mu,(2,0),(2,0)}=\frac{1}{2}p(1-p)(1+m_{0}/N)$.

Now, let’s consider the two error parts of the QEC matrix (i.e. both
$\alpha,\beta$ non-zero). First, note that if $\alpha=\beta$, then we must
have $\alpha^{\prime}=\beta^{\prime}=\alpha=\beta$ for the matrix element to
be nonzero. The reason for this is that we are either taking away two
excitations, or adding two excitations, so in order to have a non-zero inner
product, we must do the same to the other side. With that, we have

$\begin{aligned} M_{\rm 2err}^{(\mu)}&=\begin{pmatrix}c_{\mu,(1,1),(1,1)}&0\\\
0&c_{\mu,(2,2),(2,2)}\end{pmatrix}\oplus\begin{pmatrix}c_{\mu,(1,2),(1,2)}&c_{\mu,(1,2),(2,1)}\\\
c_{\mu,(2,1),(1,2)}&c_{\mu,(2,1),(2,1)}\\\ \end{pmatrix}\end{aligned},$ (S62)

so thankfully, we only have the one $2\times 2$ matrix to diagonalize. The
diagonal part has elements,

$\displaystyle c_{\mu,(1,1),(1,1)}$ $\displaystyle=\langle
h_{m}^{N}|K_{1}^{\otimes 2{\dagger}}K_{1}^{\otimes
2}|h_{m}^{N}\rangle=p^{2}{N\choose(N+m)/2}^{-1}{N-2\choose(N+m)/2}=p^{2}\left(\frac{(N-m)^{2}}{4N(N-1)}-\frac{N-m}{2N(N-1)}\right),$
(S63) $\displaystyle c_{\mu,(2,2),(2,2)}$ $\displaystyle=\langle
h_{m}^{N}|K_{2}^{\otimes 2{\dagger}}K_{2}^{\otimes
2}|h_{m}^{N}\rangle=p^{2}{N\choose(N+m)/2}^{-1}{N-2\choose(N+m-4)/2}=p^{2}\left(\frac{(N+m)^{2}}{4N(N-1)}-\frac{N+m}{2N(N-1)}\right).$

Now for the non-diagonal part. It is straightforward to see that all the
elements are the same, which we will denote

$M_{12}=\begin{pmatrix}c_{\mu,(1,2),(1,2)}&c_{\mu,(1,2),(2,1)}\\\
c_{\mu,(2,1),(1,2)}&c_{\mu,(2,1),(2,1)}\\\ \end{pmatrix}\equiv
c_{\mu,\times}\begin{pmatrix}1&1\\\
1&1\end{pmatrix}\rightarrow\sqrt{M_{12}}=\sqrt{\frac{c_{\mu,\times}}{2}}\begin{pmatrix}1&1\\\
1&1\end{pmatrix}$ (S64)

Since errors of the form $(1,2)$ do not change the magnetization, we can
calculate $c_{\mu,\times}$ as follows:

$\displaystyle c_{\mu,\times}$ $\displaystyle=\langle
h_{m}^{N}|(K_{1}^{{\dagger}}\otimes K_{2}^{{\dagger}})(K_{1}\otimes
K_{2})|h_{m}^{N}\rangle=p^{2}{N\choose(N+m)/2}^{-1}{N-2\choose(N+m-2)/2}=p^{2}\frac{N^{2}-m^{2}}{4N(N-1)}$
(S65)

With that we can now calculate the infidelity. Denoting the diagonal and non
diagonal parts of $M$ by $M_{1},M_{2}$ so that $M=M_{1}\oplus M_{2}$ and

$\displaystyle M_{1}=$
$\displaystyle\sum_{\mu}c_{\mu,(0,0),(0,0)}|0,0\rangle\langle
0,0|\otimes|\mu\rangle\langle\mu|$ (S66)
$\displaystyle+\sum_{\mu}\sum_{\alpha\neq
0}c_{\mu,(\alpha,0),(\alpha,0)}\left(|\alpha,0\rangle\langle\alpha,0|+|0,\alpha\rangle\langle
0,\alpha|\right)\otimes|\mu\rangle\langle\mu|$
$\displaystyle+\sum_{\mu}\sum_{\alpha=\beta\neq
0}c_{\mu,(\alpha,\alpha),(\alpha,\alpha)}|\alpha,\alpha\rangle\langle\alpha,\alpha|\otimes|\mu\rangle\langle\mu|,$
$\displaystyle M_{2}=$
$\displaystyle\oplus_{\mu}c_{\mu,\times}\begin{pmatrix}1&1\\\
1&1\end{pmatrix},$

one can plug and chug to obtain,

$\displaystyle({\rm Tr}_{\mu}\sqrt{M})^{2}=$ $\displaystyle({\rm
Tr}_{\mu}\sqrt{M_{1}})^{2}+({\rm Tr}_{\mu}\sqrt{M_{2}})^{2}$ (S67)
$\displaystyle\|({\rm Tr}_{\mu}\sqrt{M_{1}})\|^{2}=$
$\displaystyle\left(\sum_{\mu}\sqrt{c_{\mu,(0,0),(0,0)}}\right)^{2}+2\sum_{\alpha=1,2}\left(\sum_{\mu}\sqrt{c_{\mu,(\alpha,0),(\alpha,0)}}\right)^{2}+\sum_{\alpha=1,2}\left(\sum_{\mu}\sqrt{c_{\mu,(\alpha,\alpha),(\alpha,\alpha)}}\right)^{2}$
$\displaystyle\|{\rm Tr}_{\mu}\sqrt{M_{2}}\|^{2}=$ $\displaystyle
2\left(\sum_{\mu}\sqrt{c_{\mu,\times}}\right)^{2}$

Finally, the fidelity will be

$\tilde{F}^{\text{opt}}=(1-p)^{2}+\frac{1}{2}\sum_{\alpha=1,2}\left(\sum_{\mu}\sqrt{c_{\mu,(\alpha,0),(\alpha,0)}}\right)^{2}+\frac{1}{4}\sum_{\alpha=1,2}\left(\sum_{\mu}\sqrt{c_{\mu,(\alpha,\alpha),(\alpha,\alpha)}}\right)^{2}+\frac{1}{2}\left(\sum_{\mu}\sqrt{c_{\mu,\times}}\right)^{2}.$
(S68)

We can now set $m_{0}=-d/2,m_{1}=d/2$ as usual, and obtain exact expressions.
The full expression however, is long and tedious, so we take the limit $N\gg
1,d/N\ll 1$ in turn, and obtain

$1-\tilde{F}^{\text{opt}}=\left(\frac{1}{2}p-\frac{3}{8}p^{2}\right)\frac{d^{2}}{N^{2}}+O\left(\frac{d^{2}}{N^{3}}\right).$
(S69)

Note that in the $1$ erasure case, we could have taken $m\sim O(N)$ and still
obtained the $d^{2}/N^{2}$ scaling. However, here we cannot – if we take
$m_{0}=(N-d)/2$ for instance, it turns out there will remain uncorrectable
errors even in the thermodynamic limit.

###  VI.4 Constant number of erasures under sufficiently large distance

Now we consider the case where there are $l$ erasures for an instance of a
thermodynamic code with distance $d>l$. Again, WLOG we place these errors on
the first $l$ qubits. The matrix elements we have to calculate all have the
form

$\displaystyle c_{\mu}^{(l_{1})}$ $\displaystyle=p^{l}(1-p)^{N-l}\langle
h_{m_{\mu}}^{N}|\left(K_{1}^{\otimes l_{1}}\otimes K_{2}^{\otimes
l-l_{1}}\otimes K_{0}^{\otimes N-l}\right)^{{\dagger}}\left(K_{1}^{\otimes
l_{1}}\otimes K_{2}^{\otimes l-l_{1}}\otimes K_{0}^{\otimes
N-l}\right)|h_{m_{\mu}}^{N}\rangle$ (S70)
$\displaystyle=p^{l}(1-p)^{N-l}{N\choose(N+m_{\mu})/2}^{-1}{N-l\choose((N+m_{\mu})/2-(l-l_{1})},$

where the second factor counts the number of states on $N-l$ qubits with
magnetization $m_{\mu}-l+2l_{1}$. Here, $m_{\mu}$ is the magnetization of the
codeword $|\mu_{L}\rangle$. We will set $p=1$, since we are interested in what
happens if these $l$ qubits were deterministically erased. We will assume that
$m_{\mu}\ll N$, in which case we can expand the above in powers of $m_{\mu}/N$
as follows:

$\displaystyle c_{\mu}^{(l_{1})}$
$\displaystyle\simeq\frac{1}{N^{l}}\left(\frac{N+m_{\mu}}{2}\right)^{l-l_{1}}\left(\frac{N-m_{\mu}}{2}\right)^{l_{1}}$
(S71)
$\displaystyle=\frac{1}{2^{l}}\left(1+\frac{m_{\mu}}{N}\right)^{l-l_{1}}\left(1-\frac{m_{\mu}}{N}\right)^{l_{1}}$
$\displaystyle\simeq\frac{1}{2^{l}}\left(1+(l-2l_{1})\frac{m_{\mu}}{N}+\frac{1}{2}(l^{2}+4l_{1}^{2}-4ll_{1}-l)\frac{m_{\mu}^{2}}{N^{2}}\right)+O\left(\frac{1}{N^{3}}\right).$

where we have obtained the first approximate equality by only keeping track of
terms with $N,m_{\mu}$.

Now, any permutation of $l_{1}$ $K_{1}$’s and $l-l_{1}$ $K_{2}$’s on the first
$l$ qubits will give the same overlap (and any other configuration of Kraus
operators will give $0$ overlap), so the above gives a block of the QEC matrix
of size ${l\choose l_{1}}$ by ${l\choose l_{1}}$, with every matrix element
being the same number above. Let us denote a matrix of ones of size $d\times
d$ by $O_{1}^{d}$. The full QEC matrix then takes the form

$M=\bigoplus_{\mu=0,1}\bigoplus_{l_{1}=0}^{l}c_{\mu}^{(l_{1})}O_{1}^{{l\choose
l_{1}}},$ (S72)

such that

$\displaystyle\widetilde{F}^{\rm opt}=\frac{1}{4}\|{\rm
Tr}_{\mu}\sqrt{M}\|^{2}_{F}$ $\displaystyle=\frac{1}{4}\sum_{l_{1}=0}^{l}{\rm
Tr}\left(\sum_{\mu}\sqrt{c_{\mu}^{(l_{1})}O_{1}^{{l\choose
l_{1}}}}\right)^{2}$ (S73)
$\displaystyle=\frac{1}{4}\sum_{l_{1}=0}^{l}{l\choose
l_{1}}\left(\sum_{\mu}\sqrt{c_{\mu}^{(l_{1})}}\right)^{2}.$

The exact expression can now be easily evaluated numerically, or we can
continue with our expansion in terms of $d/N$ as before. Setting $m_{\mu}=\pm
d/2,x=d/N$, and using the approximate form in Eq. (S70), we have

$\left(\sum_{\mu}\sqrt{c_{\mu}^{(l_{1})}}\right)^{2}\simeq\frac{4}{2^{l}}\left(1+\frac{1}{16}\left(-2l+l^{2}-4ll_{1}+4l_{1}^{2}\right)x^{2}\right)$
(S74)

To evaluate the prefactor of $x^{2}$, we note that
$\sum_{l_{1}=0}^{l}{l\choose l_{1}}=2^{l},\sum_{l_{1}=0}^{l}{l\choose
l_{1}}l_{1}=2^{l-1}l,\sum_{l_{1}=0}^{l}{l\choose
l_{1}}l_{1}^{2}=2^{l-2}l(l-1)$. This leads us to the simple final expression,

$\displaystyle 1-\widetilde{F}^{\rm
opt}=\frac{l}{16}x^{2}+O\left(\frac{1}{N^{3}}\right)=\frac{l}{16}\frac{d^{2}}{N^{2}}+O\left(\frac{1}{N^{3}}\right).$
(S75)

Note that the above equation is only valid when we keep $l$ constant and take
$N$ to be large, but will not hold if we allow $l$ to scale with $N$. Eq.
(S75) matches with the single and two erasure error expressions by setting
$l=1,2$ and unit erasure probability $p=1$.