# Long-range-enhanced surface codes

Yifan Hong<EMAIL_ADDRESS>Department of Physics, University of
Colorado, Boulder, CO 80309, USA  Center for Theory of Quantum Matter,
University of Colorado, Boulder, CO 80309, USA  Matteo Marinelli  Department
of Physics, University of Colorado, Boulder, CO 80309, USA  JILA and National
Institute of Standards and Technology, Boulder, CO 80309, USA  Adam M. Kaufman
Department of Physics, University of Colorado, Boulder, CO 80309, USA  JILA
and National Institute of Standards and Technology, Boulder, CO 80309, USA
Andrew Lucas<EMAIL_ADDRESS>Department of Physics, University of
Colorado, Boulder, CO 80309, USA  Center for Theory of Quantum Matter,
University of Colorado, Boulder, CO 80309, USA

###### Abstract

The surface code is a quantum error-correcting code for one logical qubit,
protected by spatially localized parity checks in two dimensions. Due to
fundamental constraints from spatial locality, storing more logical qubits
requires either sacrificing the robustness of the surface code against errors
or increasing the number of physical qubits. We bound the minimal number of
spatially non-local parity checks necessary to add logical qubits to a surface
code while maintaining, or improving, robustness to errors. We asymptotically
saturate this bound using a family of hypergraph product codes, interpolating
between the surface code and constant-rate low-density parity-check codes.
Fault-tolerant protocols for logical operations generalize naturally to these
longer-range codes, based on those from ordinary surface codes. We provide
near-term practical implementations of this code for hardware based on trapped
ions or neutral atoms in mobile optical tweezers. Long-range-enhanced surface
codes outperform conventional surface codes using hundreds of physical qubits,
and represent a practical strategy to enhance the robustness of logical qubits
to errors in near-term devices.

##  1 Introduction

Noise is inherent in quantum computers, and if ignored, will always destroy
any quantum computational advantage. With advances in quantum hardware
enabling controllable systems of hundreds of qubits, the use of quantum error
correction to prolong the lifetime of quantum information is becoming
feasible. At the hardware-theory interface, a key goal is to design optimal
codes that leverage specific hardware-level advantages, such as gate non-
locality, to mitigate the effect of key challenges, like the fidelity of few-
qubit gates, or the resources required to increase the number of qubits in the
system.

Quantum error correction is done by starting with a Hilbert space of $n$
_physical qubits_ , and identifying a subset $2^{k}<2^{n}$ of the possible
states within Hilbert space as encoding the wave function of $k$ _logical
qubits_. The smallest number of physical qubits on which a nontrivial logical
operation can act determines the code distance $d$, and such a code is often
abbreviated as $\llbracket n,k,d\rrbracket$. A practical set of codes are
_stabilizer codes_ Gottesman (1997) in which the logical codewords are the
simultaneous $+1$ eigenstates of a commuting set of Pauli operators called the
stabilizer group. A Calderbank-Shor-Steane (CSS) code Calderbank and Shor
(1996); Steane (1996) is a stabilizer code for which the generators of this
set are strictly products of Pauli $X$s or $Z$s.

An important example of a CSS code is the surface code Bravyi and Kitaev
(1998); Fowler  _et al._ (2012), a leading candidate for near-term
implementations of fault-tolerant quantum computation. It has local stabilizer
generators supported on a checkerboard-type lattice: see Fig. 1. Fault-
tolerant surface codes have been demonstrated with superconducting qubits AI
(2023), although the “break-even” point after which the logical bit is more
robust than an isolated physical qubit remains to be reached. For hardware
with highly biased noise (e.g. Pauli $Z$ error much more likely than Pauli $X$
error), elegant modifications of the surface code are known Ataides  _et al._
(2021). Due to the spatial locality of a surface code in two spatial
dimensions, it is highly desirable for experimentalists; nearly all platforms,
including atoms in optical tweezers Saffman  _et al._ (2010); Saffman (2016);
Kaufman and Ni (2021); Wu  _et al._ (2022); Cong  _et al._ (2022); Evered  _et
al._ (2023); Ma  _et al._ (2023), trapped ions Cirac and Zoller (1995);
Bruzewicz  _et al._ (2019); Kim  _et al._ (2010); Britton  _et al._ (2012);
Barreiro  _et al._ (2011), or superconducting qubits Martinis  _et al._
(2002); Nakamura  _et al._ (1997); Krantz  _et al._ (2019); Brooks  _et al._
(2013); Gu  _et al._ (2017), can realize geometrically local interactions in
two spatial dimensions. Unfortunately, quantum computation with $\sim 10^{3}$
logical qubits in a surface code architecture with typical error rates of
$\sim 10^{-3}$ may require an architecture with $\sim 10^{7}$ physical qubits
Fowler  _et al._ (2012), which could be prohibitively difficult to build in
the near term.

Figure 1: The 2D layout of a $\llbracket 41,1,5\rrbracket$ surface code. Black
dots and colored tiles represent physical qubits and stabilizer generators,
respectively. The string-like logical operators are shown.

An exciting alternative are quantum low-density parity-check (qLDPC) codes,
which can achieve $k\sim n$: the overhead for encoding logical information is
finite. At the same time, the stabilizers are few-body just like the surface
code (but not necessarily spatially local), meaning they can in principle be
measured efficiently using few-qubit operations. The first qLDPC construction
with a finite rate ($k\sim n$) and large distance ($d\sim\sqrt{n}$) was the
hypergraph product (HGP) Tillich and Zemor (2014); a series of improvements
Hastings  _et al._ (2021); Breuckmann and Eberhardt (2021); Panteleev and
Kalachev (2022a) eventually led to “good” codes with $k\sim d\sim n$ Panteleev
and Kalachev (2022b); Leverrier and Zémor (2022a); Dinur  _et al._ (2022).

Spatial locality constrains the implementation of qLDPC codes in quantum
hardware. Suppose that each physical qubit is arranged in a two-dimensional
grid, and qubits can only interact with other qubits a finite distance away.
Then one can prove Bravyi  _et al._ (2010) that $kd^{2}\lesssim n$: there is
an unavoidable tradeoff between robustness to error ($d$) and number of
logical qubits ($k$), given a fixed number of physical qubits ($n$).
Conversely, it is known Baspin and Krishna (2022) that to implement a qLDPC in
2D, at least $\sqrt{\frac{k}{n}}d$ interactions of range
$\sqrt{\frac{k}{\sqrt{n}}}$ are necessary. If we only ask for $d=\sqrt{n}$ as
in the surface code, the bounds of Baspin and Krishna (2022) alone admit the
prospect of $k\sim\sqrt{n}$ using interactions of $O(1)$ range. Since Bravyi
_et al._ (2010) proves that these finite-range interactions only allow
$k=O(1)$, the cost of nonlocality in qLDPC codes is even higher than implied
by Baspin and Krishna (2022). Further challenges to qLDPC implementation in 2D
were discussed in Delfosse  _et al._ (2021); Baspin  _et al._ (2023). It is
thus of crucial interest to know: how many non-local stabilizers are needed to
add logical qubits to a surface code, while keeping $k$ and $n$ fixed? If we
find a code that uses the least non-locality to add logical qubits to the
surface code, is it realizable in any near-term quantum hardware?

This paper answers these questions. We present _long-range-enhanced surface
codes_ (LRESCs): an interpolating family of hypergraph product codes that
bridges the surface code with constant-rate qLDPC codes. These codes: (_1_)
have (asymptotically) as few non-local stabilizers as possible, (_2_) maintain
the code distance $d$ of the surface code while adding logical qubits, i.e.
increasing $k$, (_3_) have lower logical failure rates compared to a surface
code in the single-shot regime, and (_4_) interface with existing algorithms
for fault-tolerant universal gate sets on surface codes. The simplest
realization of the LRESC has a “hierarchical” structure similar to a recent
construction Pattison  _et al._ (2023); however, unlike Pattison  _et al._
(2023), LRESCs are LDPC stabilizer codes, employing as little non-locality as
possible. Moreover, as we will explain, these codes are well suited for
implementation using multiple different architectures for quantum computation,
as the specific form of non-locality required by LRESCs is far more efficient
to implement than a generic qLDPC code.

##  2 The LRESC

###  2.1 Construction

We begin by summarizing intuitively the structure of LRESCs; technical details
are provided in appendices. Our construction consists of three parts,
visualized in Fig. 2.

Figure 2: The steps to construct a $\llbracket 52,4,4\rrbracket$ HGP code
based on a parent $[3(2),2,2(2)]$ concatenated code are illustrated. Double
and single circles represent inner logical bits and physical bits
respectively. Solid black dots represent physical qubits, and red (blue)
squares represent $X$ ($Z$) stabilizer checks. A chosen 1D embedding of the
classical Tanner graph localizes 2 out of the 3 original long-range edges. The
HGP construction transforms the product graph into a CSS Tanner graph. 20
long-range interactions (magenta curves) of range 4 are required for this
code. A $k=4$, $d=4$ surface code of the same layout will require $n\geq 100$
physical qubits.

(_1_) First, begin with a good classical LDPC (cLDPC) code Gallager (1962);
MacKay and Neal (1996), which uses $L_{0}$ classical bits to store $O(L_{0})$
logical bits (it is thus constant rate), with $\Theta(L_{0})$ distance. In
this paper, we will focus on relatively small code sizes where $L_{0}\sim
3-10$, both for pedagogy and near-term relevance. Note that this good cLDPC
code will require non-local parity checks between the classical bits to ensure
constant rate. Appendix A overviews classical codes.

(_2_) Next, we increase the number of classical bits: $L_{0}\rightarrow
cL_{0}=L$, while proportionally increasing the distance of the code to
$\Theta(L)$ and keeping the number of logical bits fixed as $O(L_{0})$. We can
do so by replacing the bits of our starting code with another classical code,
such as the repetition code, which stores a single logical bit in $c$ physical
bits, with codewords $0\rightarrow 0\cdots 0$ and $1\rightarrow 1\cdots 1$.
The repetition code has spatially local parity checks when bits are laid out
in one-dimension: the parity checks demand that the parity of two nearest-
neighbor bits agree. We thus build a _concatenated_ code by replacing the
cLDPC “physical bits” with repetition codes of length $c$. There is no code
with fewer non-local edges in one spatial dimension that has $O(L_{0})$
logical bits and $O(L)$ code distance (see Appendix A). Decoding this
classical code has a simple interpretation: we first decode each repetition
code, and then decode the size-$L_{0}$ LDPC using the state of each repetition
code as an effective “physical bit”.

(_3_) We now build a quantum code by taking the _hypergraph product_ (HGP) of
this classical concatenated code with itself. A formal definition of the HGP
is technical and relegated to Appendix B; Fig. 2 sketches the idea. We lay out
two copies of the classical code of length $L$ along the $x$ and $y$
directions in the plane. Based on the connections between checks and physical
bits of the classical code, we lay out physical qubits and $X$ and $Z$ type
stabilizers of the quantum code in two dimensions. Note that the hypergraph
product of two classical repetition codes is the quantum surface code. Since
our classical codes contain repetition code segments, our quantum code
consists of two-dimensional surface code patches. Long-range parity checks
from step (_1_) induce stabilizers that connect distant patches in the code,
while ensuring that each stabilizer itself has low-weight (is a product of
$O(1)$ $X$s or $Z$s).

These are the LRESCs. The total number of physical qubits is $n\sim L^{2}$,
the quantum code distance is $d\sim L$, and the number of logical qubits is
$k\sim L_{0}^{2}$. Alternatively, we have constructed a code with
$d\sim\sqrt{n}$, just like the surface code, but where we have added $k$
logical qubits at the cost of adding $\sim L\sqrt{k}$ long-range stabilizers.

###  2.2 Bounding nonlocality

There is no code that has parametrically fewer long-range stabilizers in 2D
than an LRESC, while maintaining the same code distance $d\sim\sqrt{n}$. To
see why, start with a code with no long-range stabilizers; the precise cutoff
for “long” is unimportant. Bravyi  _et al._ (2010) tells us that there is at
most a finite $k_{0}=O(1)$ number of logicals, such that
$k^{\vphantom{*}}_{0}d^{2}\leq Kn<(k^{\vphantom{*}}_{0}+\delta)d^{2}$ for
$K,\delta=O(1)$. To increase the number of logical qubits from
$k^{\vphantom{*}}_{0}$, we will need to add longer-range interactions: how
many are required? Suppose that by modifying $m-\tilde{k}$ of our local
stabilizers to be spatially non-local (but still low weight, i.e. few Paulis),
and removing $\tilde{k}$ stabilizers, we can add $\tilde{k}>\delta$ logical
qubits without sacrificing code distance $d$. To bound how small $m$ can be,
consider erasure errors on the $O(m)$ physical qubits contained in these long-
range stabilizers. By removing the erased qubits, we are left with a code
protected by local stabilizers, obeying the assumptions of Bravyi  _et al._
(2010), and has a distance of at least $d-m^{\prime}$, where
$m^{\prime}=O(m)$. Importantly, this residual code completely contains all the
logical information Bravyi and Terhal (2009). The bound of Bravyi  _et al._
(2010) implies that
$(k^{\vphantom{*}}_{0}+\tilde{k})(d-m^{\prime})^{2}<(k^{\vphantom{*}}_{0}+\delta)d^{2}$.
If $k^{\vphantom{*}}_{0}=O(1)$, we thus need $m\gtrsim d$. To add logical
qubits to a surface code, $\sqrt{n}\sim L$ long-range stabilizers are
required. The LRESC achieves this scaling, and is asymptotically as local as
possible for finite $k>k_{0}$.

###  2.3 Quantum error correction

Figure 3: QEC performance is numerically estimated using a single-stage BP+OSD
decoder for three surface codes with increasing distance as well as LRESCs
with increasing long-range connectivity (LRESCS 1, 2, 3 have parent codes
$[3(4),2,2(4)]$, $[6(2),2,4(2)]$, $[8(3),4,4(3)]$ respectively). Left: $\sim
10^{5}$ clean QEC cycles are averaged per data point. Right: $\sim 10^{4}$
samples of 100 noisy QEC cycles are averaged per data point. Uncertainties are
given by standard errors. A clean cycle is performed internally after each
noisy cycle to probe the residual errors. The break-even line is plotted in
dotted black. Note that to compare, e.g., the surface codes to LRESC 3, the
number of physical qubits should be multiplied by 16, as one would store 16
logical qubits in 16 decoupled surface codes (vs. 16 logical qubits in a
single LRESC).

Quantum error correction (QEC) for stabilizer codes is typically done by
extracting the eigenvalues of all stabilizers, which can be deduced by
measuring a set of generators called the check set; the outcomes of these
measurements comprise the error syndrome. Decoding then proceeds by finding a
suitable correction operator according to the syndrome. The combination of the
original error and the correction then either leaves the codespace unchanged
(success) or enacts an undesirable logical operation (fail).

We conduct numerical simulations of QEC, using both a code-capacity (clean
syndromes) and a phenomenological (noisy syndromes) noise model under a local,
stochastic depolarization channel (single-qubit $X$, $Y$ or $Z$ errors are
equally likely) with probability $p$: see Fig. 3. For the phenomenological
noise model we assume that syndromes with weight $w$ are incorrectly measured
with probability $wp$; this mimics the experimental way that such syndromes
are measured, as we will explain later. We implement a single-stage decoder
utilizing belief propagation with ordered-statistics Panteleev and Kalachev
(2021) post-processing (BP+OSD): the “min-sum” and “combination-sweep”
$(\lambda=20)$ variants of BP and OSD are used respectively Roffe (2022).
Syndrome errors are accounted for by adding an additional variable node for
each check node in the Tanner graph Kuo  _et al._ (2021); Higgott and
Breuckmann (2023). For the phenomenological model, 100 noisy QEC cycles are
performed, where a clean cycle is performed internally after each noisy cycle
to ensure that residual errors are successfully controlled. For the LRESCs, we
use parent codes (1) $[3(4),2,2(4)]$, (2) $[6(2),2,4(2)]$ and (3)
$[8(3),4,4(3)]$, where $[n^{\prime}(c),k^{\prime},d^{\prime}(c)]$ is short for
an outer $[n^{\prime},k^{\prime},d^{\prime}]$ code concatenated with an inner
$[c,1,c]$ repetition code. The LRESCs have parameters $\llbracket
244,4,8\rrbracket$, $\llbracket 244,4,8\rrbracket$ and $\llbracket
976,16,12\rrbracket$ respectively with common rate $k/n\approx 1.64\%$ (61
physical qubits per logical qubit). Each successive LRESC contains more long-
range interactions than the previous: see Table 1. The performance of the
single-stage BP+OSD decoder on these LRESCs is compared with those of
$d=5,7,9$ surface codes on a similar layout. We observe that the first two
LRESCs perform similarly to surface codes of similar distance under the code-
capacity model. For phenomenological noise however, the second LRESC performs
significantly better than the first. The third LRESC lowers the logical error
rate by another order of magnitude.

LRESC |  edges |  LR edges (embedded) |  LR ratio
---|---|---|---
$\llbracket 244,4,8\rrbracket$ | 924 | 60 (20) | 6.5% (2.2%)
$\llbracket 244,4,8\rrbracket$ | 1056 | 528 (176) | 50% (16.7%)
$\llbracket 976,16,12\rrbracket$ | 4224 | 1408 (704) |  33.3% (16.7%)
Table 1: The number of long-range interactions vs total number of pairwise
interactions are displayed for three LRESCs. Chosen embeddings of the Tanner
graphs lower the number of long-range interactions (in parentheses).

With an encoding rate of 61 physical qubits per logical qubit, the LRESCs
begin to significantly outperform the surface codes of similar rate. With
hundreds of physical qubits, an LRESC can reach the break-even point – where
the collective logical qubit is more stable than a single isolated qubit –
once one- and two-qubit operations are achieved with just above 99.9%
fidelity, which in many platforms is near-term Evered  _et al._ (2023); Ma
_et al._ (2023) or within reach Leu  _et al._ (2023); Ding  _et al._ (2023);
Zhang  _et al._ (2023).

A single-shot decoder is, of course, not the optimal decoder for the surface
code compared to one which utilizes the syndrome measurement histories of
previous rounds. Nonetheless, we use the same decoder for all codes in order
to benchmark the benefit of long-range interactions. We discuss possible
avenues for improved decoding in the outlook.

###  2.4 Logical operators

To understand why the LRESC not only stores more logicals, but also has
reduced logical error rates, we need to understand how LRESCs encode logical
qubits. As hinted at previously, since logical operators _locally_ look like
repetition codes in the concatenated cLDPC codes (Step 2 above), in the HGP,
logical operators _locally_ look like surface code logicals, which are strings
of Pauli $X$ or $Z$ stretching across a surface code patch. What differs from
the usual surface code is the global structure of the logical operator: i.e.
how strings in different patches are joined together. A sketch is shown in
Fig. 4, with technical details in Appendix C. In a nutshell: the simplest
logical operator in an LRESC corresponds to strings in $O(\sqrt{k})$ of the
surface code patches, corresponding to an analogous logical codeword of our
cLDPC from Step 1 above.

Figure 4: A 2D layout of a LRESC with an outer $[5,2,3]$ parent code is shown.
Smooth ($X$-type) and rough ($Z$-type) boundaries are located on the left
(thick red) and bottom sides (thick blue) of each patch respectively, with
long-range boundaries on the other (magenta) sides. Four logical operators
($X^{\vphantom{*}}_{1},Z^{\vphantom{*}}_{1},X^{\vphantom{*}}_{4},Z^{\vphantom{*}}_{4}$)
corresponding to two logical qubits are drawn (solid and dashed curves). A
$Z$-type stabilizer and an $X$-type error string also shown (dotted red and
blue).

We can intuitively understand why LRESCs are more effective at protecting
logical information by showing that no matter how a logical error forms via
local processes, during the formation of the error, we always violate more
check operators than in an ordinary surface code. Since more checks are
violated, we have more opportunities to catch the physical qubit errors before
they introduce a logical error. In the surface code, we can create a logical
error by introducing a physical error near one boundary and then causing a
cascade of additional errors on adjacent sites, i.e. growing a logical string
in Fig. 4. At any step during this process, for the ordinary surface code,
only one check is violated, meaning the error is almost undetected. In
condensed matter physics, we can interpret this as an _anyonic_ particle that
is free to diffuse around the system. In the LRESC, we can similarly grow an
error through a single patch; however, when the error hits the long-range
boundary, it will flip _multiple_ checks in adjacent patches (anyons are not
conserved across the long-range boundaries of the LRESC). The rules for anyon
splitting are discussed in Appendix C. Since the error must grow across
multiple patches to constitute a logical, we must inevitably flip more checks
during the formation of the logical error, implying that it is easier to
detect.

###  2.5 Logical gates

Implementing one- and two-qubit logical gates on an LRESC is (in principle)
quite simple. While it might be possible to directly apply logical operations
on the non-locally encoded qubits, e.g. using methods from Krishna and Poulin
(2021); Quintavalle  _et al._ (2022), we can also readily organize one of our
logical qubits into a contiguous surface-code patch (e.g. moving surface-code
patches in Fig. 4 so that a logical string becomes “continuous” and adjacent
to the global boundaries), through which it can be passed into a traditional
surface code via lattice surgery. Note that one will require surface code
patches of $O(n)$ physical qubits to implement logical gates on $O(1)$ logical
qubits, passed out of the LRESC. Once a logical is in an ordinary surface code
patch, standard methods Brown  _et al._ (2017) can then be used to apply all
logical Clifford operations in a fault tolerant way. This process can be
repeated to pass multiple qubits into surface code patches, onto which two-
qubit gates can be fault-tolerantly applied. To apply non-Clifford gates once
a qubit has been moved into the traditional surface code patch, magic state
distillation Knill (2004); Bravyi and Kitaev (2005) may be required, though
Bombin (2015); Kubica and Beverland (2015); Brown (2020) provide alternatives.

###  2.6 Weight balancing

There are two simple, but practical enhancements to the LRESC described thus
far by modifying the parent codes. In Step 2 of the LRESC construction, notice
that each “physical bit” of the cLDPC from Step 1 consists of a repetition
code, but we assigned all of the “long-range” parity checks to a single bit.
We can instead evenly distribute these parity checks to different bits inside
of the repetition code: see Fig. 5 – so long as $c$ is larger than the maximal
number of parity checks per bit of the cLDPC (Step 1), this will mean that
each physical bit is involved in at most one long-range parity check in Step
2.

The second modification is to introduce auxiliary bits into the parent codes
in order to reduce the weight of each long-range parity check. The parity-
check constraints of a classical code can be reformulated as a boolean
satisfiability problem (SAT). It is well known in computer science that any
SAT problem can be decomposed into conjunctions of smaller SATs of maximum
size three (3-SAT), with the potential of introducing some auxiliary bits.
Moreover, this SAT $\rightarrow$ 3-SAT decomposition can be performed in
polynomial time Karp (1972); for our linear constraints, this decomposition
takes a particularly simple form, see Fig. 5. When we apply this decomposition
to the parity checks of a classical code, we obtain new parity checks with
bounded weights $\leq 3$ acting on the combination of our original physical
bits and some new auxiliary bits. Importantly, the code distance remains
unchanged, though the relative distance may decrease by an $O(1)$ factor if
this method is applied to all checks. At the quantum level, this decomposition
bears resemblance to a measurement-only version of Shor’s cat-state syndrome
extraction circuit Shor (1997), where we have included the cat-state ancillas
and measured operators as auxiliary qubits and new stabilizer checks
respectively.

The modified parent codes will now have at most weight-3 parity checks with
each physical bit participating in at most one long-range interaction.
Furthermore, by arranging each long-range parity check to be adjacent to an
endpoint of a repetition-code segment, we can always localize at least one of
its long-range edges. In turn, the LRESCs will contain at most weight-6
stabilizer checks with each physical and ancilla qubit participating in at
most 4 long-range interactions. These two “weight-balancing” procedures are
particularly advantageous for experimental implementations, as we will
discuss.

Figure 5: The two different weight-balancing procedures are depicted. Top: a
$[5(2),2,3(2)]$ code is modified so that all physical bits participate in at
most one long-range parity check. Bottom: A weight-5 parity check is
decomposed into three weight-3 checks with two additional auxiliary bits (gray
circles).

##  3 Experimental implementations

Typically, experimental design of quantum hardware has been strongly limited
by the choice of QEC code and its resulting requirements on circuit
connectivity. LRESCs imply that one can exploit the tunable addition of non-
locality on top of the most local of codes, the surface code, once
improvements in physical error rates, or increases in physical qubit number,
have been exhausted. Such a theoretical advance offers a timely new tool for
improving the performance of state-of-the-art platforms, including super-
conducting qubits Martinis  _et al._ (2002); Nakamura  _et al._ (1997); Krantz
_et al._ (2019); Brooks  _et al._ (2013); Gu  _et al._ (2017), trapped-ions
Cirac and Zoller (1995); Bruzewicz  _et al._ (2019); Kim  _et al._ (2010);
Britton  _et al._ (2012); Barreiro  _et al._ (2011) and neutral-atom arrays
Saffman  _et al._ (2010); Saffman (2016); Kaufman and Ni (2021); Wu  _et al._
(2022); Cong  _et al._ (2022); Evered  _et al._ (2023); Ma  _et al._ (2023)
since, as we now explain, the specific type of non-locality needed for the
LRESC is relatively mild in multiple experimental platforms.

In superconducting circuits, novel circuit graphs have simulated many-body
physics in novel geometries Kollar  _et al._ (2019). To realize the LRESC, one
must use multiple planes of wiring Rosenberg  _et al._ (2017), and we expect
that this construction is doable for modest values of $k$ (i.e. not encoding
too many logical qubits). For devices with larger values of $k$, we can also
employ fault-tolerant quantum repeater networks Fowler  _et al._ (2010);
Rozpedek  _et al._ (2021) to teleport ancilla qubits down a strictly two-
dimensional architecture. The number of such quantum repeater rounds is
constrained by the requirement that we cannot pass two logical qubits “through
each other”. This latter construction is quite similar to the “hierarchical
codes” recently discussed in Pattison  _et al._ (2023).

###  3.1 Trapped ions

Figure 6: LRESC implementation using a trapped-ion Quantum Charge-Coupled
Device architecture. (a) A possible quantum processor is structured into
multiple unit cells, each representing a surface code tile (yellow tile in
Fig. 2). Each unit cell contains the necessary data qubits (black dots) and
measure qubits for parity checks (blue and red rims). Ions are transported
across different interaction regions (green-shaded areas) by precise control
of the voltage applied to the trap electrodes (yellow boxes) to perform the
necessary local operations. Each cell also contains additional ancilla qubits
(not shown) used for re-cooling operations after transport operations. Sparse
non-local operations required by LRESC are performed via long-range transport
of qubits across different cells (pink arrows). (b)-(c) two possible ways to
perform qubit permutation withing the QCCD architecture.

While a superconducting qubit based quantum computer may take advantage of
LRESCs or hierarchical codes, we believe that the LRESC is significantly more
optimized for alternative architectures. One such architecture is the Quantum
Charge-Coupled Device (QCCD) approach Kielpinski  _et al._ (2002) to quantum
computation with trapped ions. This architecture relies on a trap device
capable of confining multiple one-dimensional arrays of ions. Within these so-
called “ion crystals”, multi-qubit operations are achieved through laser- or
microwave-induced spin-motion couplings. To facilitate interactions between
ions initially residing in separate ion crystals, the architecture requires
real-time shuttling, splitting, and merging operations of ion crystals that
occur on faster timescales compared to the coherence time of the data qubits.
This dynamic control over system connectivity is made possible through precise
manipulation of electric fields that generate the trapping potentials.

The high operational fidelities (up to 99.9999% single-qubit fidelity Harty
_et al._ (2014) and 99.94% two-qubit fidelity Clark  _et al._ (2021)) allowed
fault-tolerant demonstrations of quantum error-correcting codes encoding a
single logical qubit in small-scale QCCD processors et al. (2022); Postler
_et al._ (2022). As systems with 100s of controllable qubits become available
in the near future it will be feasible to incorporate LRESCs in the QCCD
architecture. In particular, if state-of-the-art fidelities can be maintained
for a large-scale device, then LRESC 3 from Fig. 3 surpasses the break-even
point using 976 physical qubits, and a similar number of ancilla qubits,
assuming two-qubit fidelity from Clark  _et al._ (2021).

A possible implementation of LRESCs with trapped ions is shown in Fig. 6. The
envisioned architecture is structured into multiple unit cells, each
representing a surface code tile (yellow tile in Fig. 2). Within each unit
cell, multiple interaction regions are designed to facilitate parallel single-
and two-qubit gates. Every unit cell contains both the data qubits necessary
for surface code operations and the necessary ancilla ions. Data qubits are
transported between interaction regions to perform the necessary two-qubit
gates. During transport, unwanted motional excitations may arise due to
imperfect control of applied fields. To maintain high two-qubit fidelities,
ancilla ions are then used to sympathetic re-cool an ion crystal following a
transport operation. While qubits primarily move within a unit cell, an LRESC
requires sparse long-range operations. The architecture in Fig.6 efficiently
facilitates the parallel transport of multiple ions to different unit cells,
thus minimizing additional challenges associated with non-local operations.
The main complexity lies in the optimal scheduling of gates and the required
transport operations. The amount of ion transport can be significantly reduced
if the system allows manipulation of ion crystals with more than two data
qubits. Such a system not only would reduce scheduling complexity but is also
likely to reduce the unit cell’s size, as fewer interaction regions are
needed. Consequently, it would also decrease the overall execution time, since
the time required to transport and re-cool a crystal is generally longer than
those of two-qubit gates in medium size ion crystals Pino  _et al._ (2021); et
al. (2023). However, working with large ion crystals can add extra control
challenges. State-of-the-art two-qubit gates between ions in long ion chains
are generally slower than gates on two-qubit ion crystals and also yield lower
fidelities Landsman  _et al._ (2019); Wang  _et al._ (2020). Furthermore,
multi-qubit gates mediated by normal modes of motion cannot be easily executed
in parallel. Therefore, we speculate that a likely optimal architecture that
implements LRESCs will compromise the advantages offered by the QCCD
architecture and those offered by the manipulation of medium-size ion chains.

Depending on the details of the experimental apparatus (i.e. physical size of
the quantum processor, qubit coherence time, maximum achievable transport
speed and re-cooling times), long-range transport may cause an increased
physical error rate due to the finite qubit coherence time and the longer time
required for long-range ion shuttling. To mitigate this issue teleportation of
the qubit state can be employed to replace long-distance transport. This
approach requires generating entangled Bell pairs between two distant regions
of the quantum processor using schemes for remote entanglement generation
Monroe  _et al._ (2014); Stephenson  _et al._ (2020); Krutyanskiy  _et al._
(2019). This scheme would also be compatible with a modular ion-trap
architecture Monroe  _et al._ (2014) composed of multiple interlinked small
devices each with a limited number of qubits and correspondingly little
computational power Monroe  _et al._ (2014); Campbell (2007).

###  3.2 Neutral atom arrays

Perhaps the platform most likely to reap immediate benefits from LRESCs is
reconfigurable atom arrays manipulated with optical tweezers Saffman (2016);
Browaeys and Lahaye (2020); Kaufman and Ni (2021); Bluvstein  _et al._ (2022).
In particular, scaling to 100s of controllable qubits has already been
demonstrated Scholl  _et al._ (2021); Ebadi  _et al._ (2021); Young  _et al._
(2023), while scaling to 1000s is a near-term prospect Tao  _et al._ (2023);
two-qubit gate fidelities of $>98.5\%$ have been shown in multiple atomic
species, with the state-of-the-art performance at $99.5\%$ Ma  _et al._
(2023); Evered  _et al._ (2023). Accordingly, this platform lies within an
order of magnitude of the break-even point of an LRESC (see Fig. 3). As
important, the optical methods used for atomic reconfigurability enable
parallelism that is well-suited to the surface code and LRESCs Bluvstein  _et
al._ (2022); Wu  _et al._ (2022).

Fig. 7 illustrates a possible implementation of an LRESC using atom arrays. A
static array — formed with a spatial light modulator or optical lattice Scholl
_et al._ (2021); Ebadi  _et al._ (2021); Bluvstein  _et al._ (2022); Eckner
_et al._ (2023); Young  _et al._ (2023) — holds atomic data qubits. The
measure qubits that yield $X$ and $Z$ parity checks (blue and red rims) sit on
a grid of traps rotated 45 degrees from the $x$/$y$ axes. This array of traps
is formed with crossed acoustic-optic deflectors (AOD1-MQ, AOD2-MQ in Fig. 7b)
driven with a comb of radio-frequencies. This entire array can be moved by
adding an overall offset frequency to the comb of tones inside each deflector,
allowing any rigid array translation in the $x$-$y$ plane. Such moves are used
to bring all measure qubits into proximity with the appropriate neighbor, in
order to exploit short-range Rydberg-mediated interactions for a two-qubit
gate (orange-dashed lines) for parallelized two-qubit gates Bluvstein  _et
al._ (2022); Wu  _et al._ (2022). Due to the short distance scales and the use
of AODs, each stepwise move of the SC (top of Fig. 7) can be executed in
$\lesssim 10\mu$s.

The non-local gates that underlie LRESCs likewise can be implemented in a
straight-forward fashion, with one adjustment. A pair of crossed AODs (Fig.
7b), AOD1-NL and AOD2-NL, can be used for row translations along the $y$
direction (step 5 in Fig. 7a), as well as column translations along the $x$
direction (step 6). For the non-local gates, both measure and data qubits are
moved, which necessitates qubit transfers between different optical
potentials. Such methods have been demonstrated and can be done while
preserving coherence Trotzky  _et al._ (2008); Kaufman  _et al._ (2015), yet
come at the price of longer timescales ($\sim 100\mu\textrm{s}$) to mitigate
motional heating.

Figure 7: LRESC implementation on a neutral-atom-based processor using
Rydberg-mediated interactions. (a) Data qubits (black circles) and measure
qubits (blue and red rims) are initialized in a static ordered 2D array
generated by a spatial light modulator or optical lattice. Local parity checks
are performed with sequential two-qubit gates (orange-dashed lines) performed
on all measure/data qubits in parallel, where each measure qubit is
transported in close proximity with a neighbor qubit (step 1-4) using fast
crossed acousto-optic deflectors (AODs). Another pair of crossed AODs is used
to perform non-local operations by transporting data and measure qubits
between different locations of the quantum processor. (b) Two different pairs
of crossed AODs are used for short-range and long-range atom transport,
respectively labeled as MQ and NL. Arrows represent the transport direction
for a varying radio-frequency offset in each AOD.

In addition to allowing the core components of LRESCs, the atom array platform
is compatible with other more general needs of QEC. Initialization of the
qubit array into the set of optical potentials discussed can be accomplished
with atomic rearrangement Barredo  _et al._ (2016); Endres  _et al._ (2016);
Eckner  _et al._ (2023). Parity checks on the measure qubits will require mid-
circuit readout and reset. This can be done in-situ using qubit shelving
methods, as recently demonstrated for 171Yb or by using mixed atomic species
Singh  _et al._ (2023); Lis  _et al._ (2023); Norcia  _et al._ (2023) — this
circumvents the need for large moves and zoned read-out Pino  _et al._ (2021);
Bluvstein  _et al._ (2022). Lossless state detection of neutral atoms can be
slow (at best, a few milliseconds Lis  _et al._ (2023)); this timescale can be
improved using destructive state detection Ma  _et al._ (2023); Scholl  _et
al._ (2023), that is then paired with a qubit reservoir for rapid
replenishment Pause  _et al._ (2023); Norcia  _et al._ (2023). High fidelity
single- and two-qubit gates can be accomplished at low cross-talk with the
qubit separations illustrated, using a combination of tightly-focused and
laser beams and globally-addressing fields Xia  _et al._ (2015); Wang  _et
al._ (2016); Sheng  _et al._ (2018); Jenkins  _et al._ (2022); Ma  _et al._
(2022); Lis  _et al._ (2023); Evered  _et al._ (2023); Ma  _et al._ (2023).
Qubit loss — a prevalent error channel during two-qubit gates and measurement
— can be mitigated using syndrome extraction circuits and three-outcome
measurements Suchara  _et al._ (2015).

Finally, the weight-balancing procedures described earlier (Sec. 2.6), which
allow for reducing the number of qubits per check (and checks per qubit), are
relevant for the implementation of LRESCs in atom arrays. So long as each
qubit participates in at most 4 long-range interactions, a single physical
qubit will be involved in at most 8 rounds of row and column swaps – 4 local
and 4 non-local – to couple all corresponding physical and ancilla qubits
during syndrome extraction for one round of QEC. Using a single AOD each for
long-range row and column permutations, this may require $O(\sqrt{k})$
sequential swaps. These swaps could be further parallelized by carefully
arranging the long-range edges, or by adding additional AODs, though we leave
further optimization for future work.

##  4 Outlook

We have described the LRESC: a minimal generalization of the surface code
capable of encoding multiple logical qubits without sacrificing code distance.
The LRESC is well-suited for near-term hardware, where we anticipate that our
fault-tolerant code might be realizable within the next few years.

An immediate direction for future work is to design a better decoder for
LRESCs. Depending on qubit shuttling times, a more sophisticated two-stage
decoder could be designed as follows. (1) Perform multiple rounds of local
syndrome measurements in the surface code patches while waiting for the long-
range syndrome measurements to complete Berthusen and Gottesman (2023). (2)
Use one’s favorite standard decoder (e.g. MWPM Dennis  _et al._ (2002) or
Union-Find Delfosse and Nickerson (2021)) for the multi-round syndromes within
the surface-code patches and feed the output decisions into a single-stage
BP+OSD decoder for global decoding. In this manner, one can strike a balance
between the “fast” (but less robust) checks of the surface code and the
“slower” (but more robust) long-range checks. Another future direction is to
design fault-tolerant logical operations beyond what is known in the
literature. Perhaps our physics-inspired analysis of the LRESC can lead to
generalizations of the methods known for the surface code.

The construction of the LRESC also opens possible avenues to investigate new
quantum phases of matter. In particular, it suggests new “topological phases”
are enabled using only a small density of long-range interactions, and can
thus be investigated in experiment.

In the longer term, a large-scale LRESC in which $k\sim n$ may also be the
foundation for an autonomous self-correcting quantum memory. Indeed, our
proposed architecture may well represent a more convenient strategy for
passive error correction versus a four-dimensional toric code Dennis  _et al._
(2002). It may also be more amenable to single-shot error correction than
three-dimensional single-shot codes Héctor Bombín (2015); Kubica and Vasmer
(2022); Stahl (2023).

_Note Added._ — As we were preparing this manuscript, a preprint Xu  _et al._
(2023) appeared, which also describes how hypergraph product codes can be
realized efficiently in neutral atom arrays.

## Acknowledgements

We thank Evan Wickenden and Charles Stahl for useful discussions, and Jeff
Thompson for a careful reading of the manuscript. This work was supported by
the Office of Naval Research via Grant N00014-23-1-2533 (YH, AMK, AL), the
Alfred P. Sloan Foundation via Grant FG-2020-13795 (AL), NIST (AMK) and the
Swiss National Science Foundation under grant 211072 (MM).

##  Appendix A Classical LDPC codes

We begin by reviewing classical low-density parity-check (cLDPC) codes
Gallager (1962), which play an important role in our construction. A classical
linear code $\mathcal{C}$ is specified by a set of constraints called parity
checks and a set of codeword generators satisfying those constraints. The
state of the system can be represented as an element of $\mathbb{F}^{n}_{2}$,
where $\mathbb{F}^{\vphantom{*}}_{2}=\\{0,1\\}$, and in $\mathbb{F}_{2}$,
$1+1=0$. We often represent the parity checks as rows of an
$\mathbb{F}_{2}$-valued _parity-check matrix_ $H$ and logical codewords as
rows of a matrix $G$. The statement that the codewords satisfy the parity-
check constraints becomes $HG^{\mathsf{T}}=0$. The dual code
$\mathcal{C}^{\perp}$ is defined as the code where $G$ and $H$ are swapped. We
say a linear code is LDPC if its parity-check matrix $H$ is sparse: the number
of ones per row and column are bounded by a constant irrespective of $n$. The
code is useful if $G$ is not sparse: the code distance $d$ is the smallest
number of 1s in a codeword. We can represent any linear code as a bipartite
_Tanner graph_ , drawing an edge between a “variable node” $v$ and a “check
node” $c$ if the corresponding element of $H$ is non-zero: $H_{cv}=1$. The
Tanner graph of a repetition code is depicted in Fig. 8. All linear codes
satisfy the _Singleton bound_ :

$\displaystyle k\leq n-\lvert C\rvert$ (1)

where $C$ is a correctable region satisfying $\lvert C\rvert\geq d-1$.
Correctable here means that all codewords can be successfully recovered upon
erasure of $C$.

A code generated by a random sparse $H$ has $k\sim d\sim n$ with high
probability MacKay and Neal (1996); its corresponding Tanner graph is an
asymptotically good expander. However, if we arrange the variable nodes
locally in one dimension, such a code will necessarily involve checks $c$ that
are nonlocal. If we enforce geometric locality in $D$-dimensional Euclidean
space, then the code parameters must satisfy Bravyi  _et al._ (2010)

$\displaystyle kd^{1/D}\lesssim n\,.$ (2)

The sketch of the proof in $D=1$ is as follows. The idea is to partition the
1D chain into disjoint, correctable segments $C^{\vphantom{*}}_{i}$ of length
$\lvert C^{\vphantom{*}}_{i}\rvert\approx d$ where the separation between each
segment is large enough (say $r$) so that no parity check acts in more than
one segment: see Fig. 9. Since all the correctable segments do not share any
checks, their union is entirely correctable. The Singleton bound (1) then
imposes that $k\leq n-\lvert C\rvert=\lvert\bar{C}\rvert=O(rn/d)$, and we thus
arrive at (2) for $r=O(1)$ and $D=1$. Now suppose we add in $\ell$ long-range
connections to surpass (2). We can simplify avoid the long-range edges and
partition the rest of the chain as before, arriving at $\lvert
C\rvert\rightarrow\lvert C\rvert-O(\ell)$ and thus $k\rightarrow k+O(\ell)$.
Hence, the number of logical bits $k$ can scale at most linearly with the
number of long-range connections $\ell$.

Figure 8: The Tanner graph of a $n=6$ repetition code is illustrated. The
circles and squares represent nodes (bits) and factors (parity checks)
respectively. Figure 9: A 1D chain is partitioned into disconnected,
correctable segments (blue) of length $\approx d$ with separation $\approx r$.

We now saturate the asymptotic constraints above with a cLDPC of $d\sim n$,
$k$ logical bits, and $O(k)$ long-range checks. A
$[n^{\prime}c,k^{\prime},d^{\prime}c]$ code is produced from the concatenation
of an “outer” $[n^{\prime},k^{\prime},d^{\prime}]$ code with an “inner”
$[c,1,c]$ repetition code of variable length $c$ (denoted
$[n^{\prime}(c),k^{\prime},d^{\prime}(c)]$): see Step 1 of Fig. 2.
Concatenation means that we connect a single bit of each inner repetition code
to the parity checks of the outer $[n^{\prime},k^{\prime},d^{\prime}]$ code.
This concatenating procedure can also be interpreted as first cutting up a 1D
repetition code into disconnected segments and then reconnecting these
segments with long-range interactions. The only long-range checks come from
the outer code, and if it is a “good”
$[n^{\prime},k^{\prime},d^{\prime}]=[O(k^{\prime}),k^{\prime},\Theta(k^{\prime})]$
cLDPC code, the concatenated code has parameters
$[O(ck^{\prime}),k^{\prime},\Theta(ck^{\prime})]$ with $O(k^{\prime})$ long-
range connections, which is parametrically optimal. Since we are allowed to
attach the long-range edges to _any_ bits of the inner repetition codes, we
have some flexibility in designing the long-range couplings (recall Sec. 2.6).
This concatenation procedure can be considered as a “dual” variant to the
edge-augmentation construction of Roffe  _et al._ (2020): instead of having
the repetition codes live on the edges of a cLDPC code, we attach them to the
variable nodes themselves. For a cLDPC with average vertex degree $\bar{w}$,
the concatenated construction reduces the number of surface-code patches by a
factor of $\bar{w}^{2}$ compared to the approach in Roffe  _et al._ (2020). As
we will later see, the “hierarchical” structure of concatenated codes also
lends the dynamics to be factorized in a systematic manner: we can analyze the
dynamics within the inner and outer codes separately.

##  Appendix B Hypergraph product codes

Using an $\mathbb{F}^{2n}_{2}$ representation for Paulis, the stabilizer
checks of a CSS code can be represented by the parity-check matrix

$\displaystyle H=\begin{pmatrix}H^{\vphantom{*}}_{X}&0\\\
0&H^{\vphantom{*}}_{Z}\end{pmatrix}$ (3)

where commutativity requires $H^{\vphantom{*}}_{Z}H^{\mathsf{T}}_{X}=0$. We
use the hypergraph product (HGP) construction Tillich and Zemor (2014) to
produce a quantum CSS code from two classical linear codes. Specifically,
suppose we have two classical codes with parameters
$[n^{\vphantom{*}}_{1},k^{\vphantom{*}}_{1},d^{\vphantom{*}}_{1}]$,
$[n^{\vphantom{*}}_{2},k^{\vphantom{*}}_{2},d^{\vphantom{*}}_{2}]$ and parity-
check matrices $H^{\vphantom{*}}_{1}$, $H^{\vphantom{*}}_{2}$ respectively.
The associated HGP code has parity-check matrices defined as

$\displaystyle H^{\vphantom{*}}_{X}$
$\displaystyle=(H^{\vphantom{*}}_{1}\otimes\mathds{1}\;\;|\;\;\mathds{1}\otimes
H^{\mathsf{T}}_{2})$ (4a) $\displaystyle H^{\vphantom{*}}_{Z}$
$\displaystyle=(\mathds{1}\otimes
H^{\vphantom{*}}_{2}\;\;|\;\;H^{\mathsf{T}}_{1}\otimes\mathds{1})\,.$ (4b)

By construction, the orthogonality constraint
$H^{\vphantom{*}}_{Z}H^{\mathsf{T}}_{X}=0$ is automatically satisfied. If
$H^{\vphantom{*}}_{1}$ and $H^{\vphantom{*}}_{2}$ have full rank (no redundant
parity checks), then the HGP code has parameters $\llbracket
O(n^{\vphantom{*}}_{1}n^{\vphantom{*}}_{2}),k^{\vphantom{*}}_{1}k^{\vphantom{*}}_{2},\min(d^{\vphantom{*}}_{1},d^{\vphantom{*}}_{2})\rrbracket$.
Geometrically, the Tanner graph of the HGP code takes the form of a graph
product between those of the two classical parent codes. Given two graphs
$\mathcal{G}^{\vphantom{*}}_{1}=(V^{\vphantom{*}}_{1},E^{\vphantom{*}}_{1})$
and
$\mathcal{G}^{\vphantom{*}}_{2}=(V^{\vphantom{*}}_{2},E^{\vphantom{*}}_{2})$,
the product graph
$\mathcal{G}^{\vphantom{*}}_{1}\times\mathcal{G}^{\vphantom{*}}_{2}$ is a
graph with vertices labeled by pairs $(x,y)$ where $x\in V^{\vphantom{*}}_{1}$
and $y\in V^{\vphantom{*}}_{2}$. Two vertices $(x,y)$,
$(x^{\prime},y^{\prime})$ are connected by an edge if either $x=x^{\prime}$
and $\\{y,y^{\prime}\\}\in E^{\vphantom{*}}_{2}$ or $y=y^{\prime}$ and
$\\{x,x^{\prime}\\}\in E^{\vphantom{*}}_{1}$. The steps to convert this
product graph into a CSS Tanner graph are:

  1. 1.

If the vertex of the product graph is of the form (node, node) or (factor,
factor), then that vertex becomes a node representing a physical qubit.

  2. 2.

If the vertex of the product graph is of the form (node, factor), then that
vertex becomes a factor representing an $X$ stabilizer.

  3. 3.

If the vertex of the product graph is of the form (factor, node), then that
vertex becomes a factor representing a $Z$ stabilizer.

Importantly, if the two parent codes are LDPC, then so is the resultant HGP
code. If the two parent codes can be locally embedded in
$D^{\vphantom{*}}_{1}$ and $D^{\vphantom{*}}_{2}$ spatial dimensions, then the
HGP code can in $D^{\vphantom{*}}_{1}+D^{\vphantom{*}}_{2}$ dimensions. The
surface code is the HGP of two 1D repetition codes.

The LRESC is simply the HGP of the classical concatenated code defined earlier
with itself. Its parameters are $\llbracket O(c^{2}k^{\prime 2}),k^{\prime
2},\Theta(ck^{\prime})\rrbracket$ with $O(ck^{\prime 2})$ long-range
interactions. Denoting $L\equiv ck^{\prime}$ and $k\equiv k^{\prime 2}$, the
code parameters simplify as $\llbracket O(L^{2}),k,\Theta(L)\rrbracket$ with
$O\left(L\sqrt{k}\right)$ long-range interactions. For $k\ll n$, the 2D layout
of this HGP code can be understood as patches of surface code of length
$O(c)$, whose boundaries are connected by long-range stabilizers: see Fig. 2.
The graph product structure arranges these long-range interactions as parallel
row and column couplings.

In the surface code, the quantum Tanner transformation Leverrier and Zémor
(2022b); Leverrier (2022) can reduce $n$ to roughly $\approx n/2$ while
maintaining the same distance, producing the so-called “rotated surface code”
with parameters $\llbracket L^{2},1,L\rrbracket$. The idea is to multiply
adjacent checks of the same type in order to produce new checks which commute
when restricted to a sublattice; the complementary sublattice can then be
discarded: see Fig. 10. The Tanner transform of a LRESC will unfortunately
introduce a “diagonal” interaction for every long-range 4-cycle in the
original Tanner graph. If the parent code has $O(k^{\prime})$ long-range
edges, then the HGP code will contain $O(k^{\prime 2})=O(k)$ additional
“diagonal” interactions in a 2D layout. For small platforms, the factor of 2
reduction in overhead may still be advantageous despite the increase in
routing complexity.

Figure 10: The transformation of a $\llbracket 52,4,4\rrbracket$ HGP code into
a $\llbracket 36,4,4\rrbracket$ quantum Tanner code is shown. Solid black dots
represent physical qubits, and red (blue) squares represent $X$ ($Z$) checks.
21 long-range interactions (magenta curves) are required. A $k=4$, $d=4$
surface code of the same layout will require $n\geq 64$ physical qubits.

##  Appendix C Long-range boundaries and confinement

In this section, we characterize the structure of logical operators in LRESCs
using concepts from condensed-matter physics. We show how anyon transport
properties in the LRESC are related to domain-wall dynamics in the classical
parent codes. Finally, we describe how the long-range boundaries in an LRESC
can lead to anyon confinement and improved single-shot decoding.

###  C.1 Logical operators and boundary dynamics

Interpreting the parity checks of the 1D repetition code (Fig. 8) as energetic
terms in a Hamiltonian, we arrive at the 1D Ising model. A local bit flip in
the 1D Ising model creates a pair of domain walls separating 1s and 0s. When
these domain walls move via additional bit flips, the number of violated
checks remains constant, and we say that the domain walls are “deconfined”.
These domain walls can then travel to opposite endpoints of the chain,
flipping all physical bits in the process. Thus, a logical error in the 1D
repetition code can be enacted with local processes while violating only
$O(1)$ checks.

The concatenated codes mentioned earlier consist of an outer
$[n^{\prime},k^{\prime},d^{\prime}]$ code and an inner repetition code. We now
describe how the structure of the outer code dictates the dynamics of
propagating domain walls. As a concrete example, suppose our outer code was a
$[5,2,3]$ code with

$\displaystyle H=\begin{pmatrix}1&1&0&1&0\\\ 0&1&0&0&1\\\
0&0&1&1&0\end{pmatrix}\quad,\quad G=\left(\begin{array}[]{cc|ccc}1&0&1&1&0\\\
0&1&1&1&1\end{array}\right)$ (7)

where we have expressed $G$ in reduced row echelon (standard) form. Domain
walls can freely propagate within each inner repetition code. However, upon
hitting the long-range boundaries, these domain walls will excite the long-
range checks of the outer cLDPC code: see Fig. 11. Satisfying the long-range
checks requires locally exciting domain walls on other repetition code
segments according to the codewords generated by $G$. When a domain wall
reaches a long-range check, we examine the codewords which contain a 1 at the
position of its corresponding repetition-code segment. The other 1s in the
codeword label the other segments which can spawn the additional domain walls,
thereby satisfying all long-range parity checks. The minimum number of
additional domain walls is $d^{\prime}-1$, where $d^{\prime}$ is the distance
of the outer code.

Figure 11: The classical dynamics of long-range boundaries is depicted for a
$[5(c),2,3(c)]$ concatenated code. A domain-wall excitation (star) is created
in an inner repetition code and is transported across to the long-range
boundaries (magenta lines). Left: Upon reaching this boundary, the long-range
checks of the outer code will be violated (red squares). Right: Additional
$d^{\prime}-1=2$ excitations must appear amongst the other connected surface-
code patches in order to complete a logical operation (codeword 11001).

The HGP will produce two types of horizontal and vertical long-range
boundaries: an $X$-type and a $Z$-type. For every long-range edge connecting a
node and a check, the graph product will produce a long-range edge connecting
a (node, node) $\rightarrow$ qubit to a (check, node) $\rightarrow$ $Z$-check
or a (node, check) $\rightarrow$ $X$-check to a (check, check) $\rightarrow$
qubit. We denote an excitation of a $X$($Z$)-check as a $e$ ($m$) anyon. Using
these conventions, we can now analyze anyon transport through the long-range
boundaries. Suppose we try and move an $e$ particle through an $X$-type long-
range boundary (by growing its “error” string of $Z$s). The combination of the
original and newly emerging strings must overlap on an even number of sites
with each long-range $X$-check. This constraint is satisfied precisely by the
codewords generated by $G$. If the code distance of the outer code is
$d^{\prime}$, then the $e$ must split into at least $d^{\prime}-1$ additional
$e$ particles. Now if we try to move an $e$ particle through a $Z$-type long-
range boundary, we can simply multiply the error string by long-range
$Z$-checks, which will extend the support of this error to additional surface-
code patches given by $H$. Growing the error strings in these other patches
will create additional $e$ particles. The rules for $m$ particle follow
analogously by switching the roles of $X$ and $Z$. For each surface-code patch
labeled $(x,y)$ with the origin at the upper-left, we can arrange the rough
($e$ absorbing), smooth ($m$ absorbing) and long-range boundaries as depicted
in Fig. 12. Rough boundaries are present at the bottom and smooth boundaries
on the left. The top and right boundaries are the long-range boundaries. The
anyon transport rules through the long-range boundaries can now be summarized
as

  * •

$e$ anyons tunnel through horizontal (vertical) boundaries according to $G$
($H$).

  * •

$m$ anyons tunnel through horizontal (vertical) boundaries according to $H$
($G$).

So the tunneling of $e$ ($m$) anyons through horizontal (vertical) boundaries
are analogous to that of domain walls in the classical parent code: the
codewords generated by $G$ label the $y$ ($x$) coordinates of surface-code
patches where additional anyons can appear. The tunneling rules in the other
directions are analogous but using the dual codewords generated by $H$.
Because $e$ and $m$ anyons behave differently through long-range boundaries
($G\neq H$ in general), we have lost the usual $e\leftrightarrow m$ duality
that is present in the ordinary surface code. However, if we use a _self-dual_
code where $G\simeq H$ (e.g. $[8,4,4]$ extended Hamming), then this duality is
restored.

Figure 12: Some logical (left diagram) and stabilizer (right diagram)
operators are depicted for a LRESC with a parent $[5,2,3]$ outer code (7). (a)
The $X^{\vphantom{*}}_{1}$ and $Z^{\vphantom{*}}_{1}$ logical operators are
constructed using the codeword $10110\in G$. (b) The $X^{\vphantom{*}}_{4}$
and $Z^{\vphantom{*}}_{4}$ logical operators are constructed using the
codeword $01111\in G$. (c) A $Z$-type stabilizer is constructed using
$x:11010\in H$ and $y:10110\in G$. (d) An $X$-type stabilizer is constructed
using $x:10110\in G$ and $y:00110\in H$. (e) An $X$-type stabilizer is
constructed from a “contractible loop” through the long-range boundaries
according to $y:01001\in H$. Logical operators may be deformed through the
long-range boundaries by multiplying appropriate stabilizers.

We can use the above tunneling rules to construct our logical operators. We
choose the standard form of $G$ ($\mathds{1}^{\vphantom{*}}_{k^{\prime}}$ on
the left) as a canonical basis for our logical operators like in (7). Starting
on each surface-code patch $(1\leq x\leq k^{\prime},1\leq y\leq k^{\prime})$
in the upper-left corner, the $X$($Z$)-type logical operators are horizontal
(vertical) lines spanning the surface-code patches given by the $x$($y$)-th
row of $G$ with the other coordinate fixed. The $X$($Z$)-type logical strings
can be interpreted as dragging a single $m$ ($e$) from a smooth (rough)
boundary where they are condensed, transporting it to the long-range boundary
on the opposite side, and then transporting all tunneled anyons across the new
surface-code patches and absorbing them at opposing smooth (rough) boundaries.
Using this procedure, we successfully construct $X$ and $Z$ logical operators
for all $k=k^{\prime 2}$ logical qubits. Since $G$ is in standard form, these
logical operators only intersect once inside the patches in the upper-left
$k^{\prime}\times k^{\prime}$ corner.

###  C.2 Anyon confinement and single-shot decoding

The presence of syndrome measurement errors is detrimental for surface code
decoding, often lowering the error threshold by an order of magnitude. The
intuitive reason is that error strings are only detectable at their endpoints,
and so if both endpoints have a syndrome measurement error, then that string
becomes undetectable. The usual scheme to account for syndrome measurement
errors is to perform multiple rounds of syndrome measurements and use the
global space-time history for decoding. However, the number of measurement
rounds per QEC cycle will scale with the system size Dennis  _et al._ (2002).
If a decoder is able to account for these measurement errors with a only a
small overhead, then we say this decoder is capable of _single-shot_
correction. For stabilizer codes, the relation between confinement and single-
shot ability has been well established Héctor Bombín (2015); Quintavalle  _et
al._ (2021). Confinement implies that enacting a logical operation via local
moves will necessarily violate an increasing amount of stabilizers, and so
even if a few measurements are faulty, there still exists a sufficient number
of violated stabilizers to undo most of the error such that any residual error
remains controlled over subsequent QEC cycles.

The Tanner graph of a good cLDPC code is a (bipartite) expander graph.
Expander graphs have the property that the boundary of a subset of vertices
scales proportionally to the size of the subset. In particular, for a graph
$G=(V,E)$, one can define the (outer) _expansion profile_

$\displaystyle h^{\vphantom{*}}_{G}(r)\equiv\min_{\lvert S\rvert\leq
r}\frac{\lvert\partial^{\vphantom{*}}_{+}S\rvert}{\lvert S\rvert}\,,$ (8)

where $\partial^{\vphantom{*}}_{+}S$ denotes the outer boundary of $S\subset
V$, defined as the set of vertices outside of $S$ with an edge connecting to a
vertex in $S$. There is a small tweak in the definition for bipartite graphs,
but the general idea is the same. On a Tanner graph, the boundary of a subset
of nodes is related to the number of violated parity checks for an error
supported on that subset. An expander graph is formally a graph where
$h^{\vphantom{*}}_{G}(r)=O(1)$ for $r<d\sim n$, so effecting a logical error
via local bit flips, or equivalently moving a domain wall, will necessarily
violate a growing number of checks in the process. Interpreting the parity
checks as a classical Hamiltonian, we can reformulate the previous statement
as the existence of macroscopic energy barriers between different ground
states.

For the LRESCs, as we increase the number of long-range connections in the
parent code, we allow outer codes with larger $n^{\prime}$. If these outer
codes are good cLDPC codes, whose Tanner graphs are good expanders, then the
LRESCs will contain more anyon confinement which should lead to better single-
shot performance, as suggested in Fig. 3. Specifically, for a parent
$[O(ck^{\prime}),k^{\prime},\Theta(ck^{\prime})]$ code, the syndrome weight
$\lvert\mathbf{s}\rvert$ for an error $\mathbf{e}$ grows as
$\lvert\mathbf{s}\rvert\sim\lvert\mathbf{e}\rvert/c\sim\lvert\mathbf{e}\rvert\cdot\ell/n$
for $\lvert\mathbf{e}\rvert\lesssim d\sim n$ (up to stabilizer equivalence),
where $\ell\sim k^{\prime}$ is the number of long-range interactions. If the
number of long-range interactions in the parent code increases with the system
size as $\ell\sim n^{b}$ for some $b>0$, then the corresponding LRESC
satisfies the “good” confinement definition of Quintavalle  _et al._ (2021)
and thus has a provable single-shot (sustainable) threshold under adversarial
noise. A threshold under local stochastic noise has been proven for $b=1$
($c=O(1)$ limit of a LRESC), but it remains an open problem as to whether this
threshold exists for $b<1$, though numerical evidence suggests an affirmative
for certain families of 3D homological product codes Quintavalle  _et al._
(2021). (We also see no physical reason why local stochastic noise would be
more dangerous than adversarial noise!) Because LRESCs can systematically vary
their density of long-range interactions, they provide tunable qLDPC codes to
numerically benchmark sustainable thresholds for $0<b<1$.

## References

  * Gottesman (1997) Daniel Gottesman, “Stabilizer codes and quantum error correction,” (1997), arXiv:quant-ph/9705052 [quant-ph] .
  * Calderbank and Shor (1996) A. R. Calderbank and Peter W. Shor, “Good quantum error-correcting codes exist,” Physical Review A 54, 1098–1105 (1996).
  * Steane (1996) Andrew Steane, “Multiple-particle interference and quantum error correction,” Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 452, 2551–2577 (1996).
  * Bravyi and Kitaev (1998) S. B. Bravyi and A. Yu. Kitaev, “Quantum codes on a lattice with boundary,” (1998), arXiv:quant-ph/9811052 [quant-ph] .
  * Fowler  _et al._ (2012) Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland, “Surface codes: Towards practical large-scale quantum computation,” Physical Review A 86 (2012), 10.1103/physreva.86.032324.
  * AI (2023) Google Quantum AI, “Suppressing quantum errors by scaling a surface code logical qubit,” Nature 614, 676–681 (2023).
  * Ataides  _et al._ (2021) J. Pablo Bonilla Ataides, David K. Tuckett, Stephen D. Bartlett, Steven T. Flammia, and Benjamin J. Brown, “The XZZX surface code,” Nature Communications 12 (2021), 10.1038/s41467-021-22274-1.
  * Saffman  _et al._ (2010) M. Saffman, T. G. Walker, and K. Mølmer, “Quantum information with Rydberg atoms,” Rev. Mod. Phys. 82, 2313–2363 (2010).
  * Saffman (2016) M Saffman, “Quantum computing with atomic qubits and rydberg interactions: progress and challenges,” Journal of Physics B: Atomic, Molecular and Optical Physics 49, 202001 (2016).
  * Kaufman and Ni (2021) Adam M Kaufman and Kang-Kuen Ni, “Quantum science with optical tweezer arrays of ultracold atoms and molecules,” Nature Physics 17, 1324–1333 (2021).
  * Wu  _et al._ (2022) Yue Wu, Shimon Kolkowitz, Shruti Puri, and Jeff D Thompson, “Erasure conversion for fault-tolerant quantum computing in alkaline earth rydberg atom arrays,” Nature communications 13, 4657 (2022).
  * Cong  _et al._ (2022) Iris Cong, Harry Levine, Alexander Keesling, Dolev Bluvstein, Sheng-Tao Wang, and Mikhail D Lukin, “Hardware-efficient, fault-tolerant quantum computation with rydberg atoms,” Physical Review X 12, 021049 (2022).
  * Evered  _et al._ (2023) Simon J Evered, Dolev Bluvstein, Marcin Kalinowski, Sepehr Ebadi, Tom Manovitz, Hengyun Zhou, Sophie H Li, Alexandra A Geim, Tout T Wang, Nishad Maskara, _et al._ , “High-fidelity parallel entangling gates on a neutral atom quantum computer,” arXiv preprint arXiv:2304.05420 (2023).
  * Ma  _et al._ (2023) Shuo Ma, Genyue Liu, Pai Peng, Bichen Zhang, Sven Jandura, Jahan Claes, Alex P Burgers, Guido Pupillo, Shruti Puri, and Jeff D Thompson, “High-fidelity gates with mid-circuit erasure conversion in a metastable neutral atom qubit,” arXiv preprint arXiv:2305.05493 (2023).
  * Cirac and Zoller (1995) J. I. Cirac and P. Zoller, “Quantum computations with cold trapped ions,” Phys. Rev. Lett. 74, 4091–4094 (1995).
  * Bruzewicz  _et al._ (2019) Colin D. Bruzewicz, John Chiaverini, Robert McConnell, and Jeremy M. Sage, “Trapped-ion quantum computing: Progress and challenges,” Applied Physics Reviews 6, 021314 (2019).
  * Kim  _et al._ (2010) Kihwan Kim, M-S Chang, Simcha Korenblit, R. Islam, E Edwards, J Freericks, G-D Lin, L-M Duan, and C Monroe, “Quantum simulation of frustrated ising spins with trapped ions,” Nature 465, 590–3 (2010).
  * Britton  _et al._ (2012) Joseph W. Britton, Brian C. Sawyer, Adam C. Keith, C.-C. Joseph Wang, James K. Freericks, Hermann Uys, Michael J. Biercuk, and John J. Bollinger, “Engineered two-dimensional ising interactions in a trapped-ion quantum simulator with hundreds of spins,” Nature 484, 489–492 (2012).
  * Barreiro  _et al._ (2011) Julio T. Barreiro, Markus Müller, Philipp Schindler, Daniel Nigg, Thomas Monz, Michael Chwalla, Markus Hennrich, Christian F. Roos, Peter Zoller, and Rainer Blatt, “An open-system quantum simulator with trapped ions,” Nature 470, 486–491 (2011).
  * Martinis  _et al._ (2002) John M. Martinis, S. Nam, J. Aumentado, and C. Urbina, “Rabi oscillations in a large josephson-junction qubit,” Phys. Rev. Lett. 89, 117901 (2002).
  * Nakamura  _et al._ (1997) Y. Nakamura, C. D. Chen, and J. S. Tsai, “Spectroscopy of energy-level splitting between two macroscopic quantum states of charge coherently superposed by josephson coupling,” Phys. Rev. Lett. 79, 2328–2331 (1997).
  * Krantz  _et al._ (2019) P. Krantz, M. Kjaergaard, F. Yan, T. P. Orlando, S. Gustavsson, and W. D. Oliver, “A quantum engineer's guide to superconducting qubits,” Applied Physics Reviews 6, 021318 (2019).
  * Brooks  _et al._ (2013) Peter Brooks, Alexei Kitaev, and John Preskill, “Protected gates for superconducting qubits,” Physical Review A 87 (2013), 10.1103/physreva.87.052306.
  * Gu  _et al._ (2017) Xiu Gu, Anton Frisk Kockum, Adam Miranowicz, Yu xi Liu, and Franco Nori, “Microwave photonics with superconducting quantum circuits,” Physics Reports 718-719, 1–102 (2017).
  * Tillich and Zemor (2014) Jean-Pierre Tillich and Gilles Zemor, “Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength,” IEEE Transactions on Information Theory 60, 1193–1202 (2014).
  * Hastings  _et al._ (2021) Matthew B. Hastings, Jeongwan Haah, and Ryan O’Donnell, “Fiber bundle codes: Breaking the $\sqrt{n}$ polylog($n$) barrier for quantum ldpc codes,” in  _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_, STOC 2021 (Association for Computing Machinery, New York, NY, USA, 2021) p. 1276–1288.
  * Breuckmann and Eberhardt (2021) Nikolas P. Breuckmann and Jens N. Eberhardt, “Balanced product quantum codes,” IEEE Transactions on Information Theory 67, 6653–6674 (2021).
  * Panteleev and Kalachev (2022a) Pavel Panteleev and Gleb Kalachev, “Quantum ldpc codes with almost linear minimum distance,” IEEE Transactions on Information Theory 68, 213–229 (2022a).
  * Panteleev and Kalachev (2022b) Pavel Panteleev and Gleb Kalachev, “Asymptotically good quantum and locally testable classical ldpc codes,” in  _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_, STOC 2022 (Association for Computing Machinery, New York, NY, USA, 2022) p. 375–388.
  * Leverrier and Zémor (2022a) Anthony Leverrier and Gilles Zémor, “Quantum tanner codes,” (2022a), arXiv:2202.13641 [quant-ph] .
  * Dinur  _et al._ (2022) Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, and Thomas Vidick, “Good quantum ldpc codes with linear time decoders,” (2022), arXiv:2206.07750 [quant-ph] .
  * Bravyi  _et al._ (2010) Sergey Bravyi, David Poulin, and Barbara Terhal, “Tradeoffs for reliable quantum information storage in 2d systems,” Physical Review Letters 104 (2010), 10.1103/physrevlett.104.050503.
  * Baspin and Krishna (2022) Nouédyn Baspin and Anirudh Krishna, “Quantifying nonlocality: How outperforming local quantum codes is expensive,” Physical Review Letters 129 (2022), 10.1103/physrevlett.129.050505.
  * Delfosse  _et al._ (2021) Nicolas Delfosse, Michael E. Beverland, and Maxime A. Tremblay, “Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum ldpc codes,” (2021), arXiv:2109.14599 [quant-ph] .
  * Baspin  _et al._ (2023) Nouédyn Baspin, Venkatesan Guruswami, Anirudh Krishna, and Ray Li, “Improved rate-distance trade-offs for quantum codes with restricted connectivity,” (2023), arXiv:2307.03283 [quant-ph] .
  * Pattison  _et al._ (2023) Christopher A. Pattison, Anirudh Krishna, and John Preskill, “Hierarchical memories: Simulating quantum ldpc codes with local gates,” (2023), arXiv:2303.04798 [quant-ph] .
  * Gallager (1962) R. Gallager, “Low-density parity-check codes,” IRE Transactions on Information Theory 8, 21–28 (1962).
  * MacKay and Neal (1996) D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes,” Electronics Letters 32, 1645 (1996).
  * Bravyi and Terhal (2009) Sergey Bravyi and Barbara Terhal, “A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes,” New Journal of Physics 11, 043029 (2009).
  * Panteleev and Kalachev (2021) Pavel Panteleev and Gleb Kalachev, “Degenerate quantum LDPC codes with good finite length performance,” Quantum 5, 585 (2021).
  * Roffe (2022) Joschka Roffe, “LDPC: Python tools for low density parity check codes,”  (2022).
  * Kuo  _et al._ (2021) Kao-Yueh Kuo, I-Chun Chern, and Ching-Yi Lai, “Decoding of quantum data-syndrome codes via belief propagation,” in  _2021 IEEE International Symposium on Information Theory (ISIT)_ (IEEE, 2021).
  * Higgott and Breuckmann (2023) Oscar Higgott and Nikolas P. Breuckmann, “Improved single-shot decoding of higher-dimensional hypergraph-product codes,” PRX Quantum 4, 020332 (2023).
  * Leu  _et al._ (2023) AD Leu, MF Gely, MA Weber, MC Smith, DP Nadlinger, and DM Lucas, “Fast, high-fidelity addressed single-qubit gates using efficient composite pulse sequences,” arXiv preprint arXiv:2305.06725 (2023).
  * Ding  _et al._ (2023) Leon Ding, Max Hays, Youngkyu Sung, Bharath Kannan, Junyoung An, Agustin Di Paolo, Amir H Karamlou, Thomas M Hazard, Kate Azar, David K Kim, _et al._ , “High-fidelity, frequency-flexible two-qubit fluxonium gates with a transmon coupler,” arXiv preprint arXiv:2304.06087 (2023).
  * Zhang  _et al._ (2023) Helin Zhang, Chunyang Ding, DK Weiss, Ziwen Huang, Yuwei Ma, Charles Guinn, Sara Sussman, Sai Pavan Chitta, Danyang Chen, Andrew A Houck, _et al._ , “Tunable inductive coupler for high fidelity gates between fluxonium qubits,” arXiv preprint arXiv:2309.05720 (2023).
  * Krishna and Poulin (2021) Anirudh Krishna and David Poulin, “Fault-tolerant gates on hypergraph product codes,” Phys. Rev. X 11, 011023 (2021).
  * Quintavalle  _et al._ (2022) Armanda O. Quintavalle, Paul Webster, and Michael Vasmer, “Partitioning qubits in hypergraph product codes to implement logical gates,” (2022), arXiv:2204.10812 [quant-ph] .
  * Brown  _et al._ (2017) Benjamin J. Brown, Katharina Laubscher, Markus S. Kesselring, and James R. Wootton, “Poking holes and cutting corners to achieve clifford gates with the surface code,” Physical Review X 7 (2017), 10.1103/physrevx.7.021029.
  * Knill (2004) E. Knill, “Fault-tolerant postselected quantum computation: Schemes,” (2004), arXiv:quant-ph/0402171 [quant-ph] .
  * Bravyi and Kitaev (2005) Sergey Bravyi and Alexei Kitaev, “Universal quantum computation with ideal clifford gates and noisy ancillas,” Physical Review A 71 (2005), 10.1103/physreva.71.022316.
  * Bombin (2015) H. Bombin, “Gauge color codes: Optimal transversal gates and gauge fixing in topological stabilizer codes,” (2015), arXiv:1311.0879 [quant-ph] .
  * Kubica and Beverland (2015) Aleksander Kubica and Michael E. Beverland, “Universal transversal gates with color codes: A simplified approach,” Phys. Rev. A 91, 032330 (2015).
  * Brown (2020) Benjamin J. Brown, “A fault-tolerant non-clifford gate for the surface code in two dimensions,” Science Advances 6 (2020), 10.1126/sciadv.aay4929.
  * Karp (1972) Richard Karp, “Reducibility among combinatorial problems,” (1972) pp. 85–103.
  * Shor (1997) Peter W. Shor, “Fault-tolerant quantum computation,” (1997), arXiv:quant-ph/9605011 [quant-ph] .
  * Kollar  _et al._ (2019) Alicia J. Kollar, Mattias Fitzpatrick, and Andrew A. Houck, “Hyperbolic lattices in circuit quantum electrodynamics,” Nature 571, 45–50 (2019).
  * Rosenberg  _et al._ (2017) D. Rosenberg, D. Kim, R. Das, D. Yost, S. Gustavsson, D. Hover, P. Krantz, A. Melville, L. Racz, G. O. Samach, S. J. Weber, F. Yan, J. L. Yoder, A. J. Kerman, and W. D. Oliver, “3d integrated superconducting qubits,” npj Quantum Information 3 (2017).
  * Fowler  _et al._ (2010) Austin G. Fowler, David S. Wang, Charles D. Hill, Thaddeus D. Ladd, Rodney Van Meter, and Lloyd C. L. Hollenberg, “Surface code quantum communication,” Physical Review Letters 104 (2010), 10.1103/physrevlett.104.180503.
  * Rozpedek  _et al._ (2021) Filip Rozpedek, Kyungjoo Noh, Qian Xu, Saikat Guha, and Liang Jiang, “Quantum repeaters based on concatenated bosonic and discrete-variable quantum codes,” npj Quantum Information 7 (2021), 10.1038/s41534-021-00438-7.
  * Kielpinski  _et al._ (2002) D. Kielpinski, C. Monroe, and D. J. Wineland, “Architecture for a large-scale ion-trap quantum computer,” Nature 417, 709–711 (2002).
  * Harty  _et al._ (2014) T. P. Harty, D. T. C. Allcock, C. J. Ballance, L. Guidoni, H. A. Janacek, N. M. Linke, D. N. Stacey, and D. M. Lucas, “High-fidelity preparation, gates, memory, and readout of a trapped-ion quantum bit,” Phys. Rev. Lett. 113, 220501 (2014).
  * Clark  _et al._ (2021) Craig R. Clark, Holly N. Tinkey, Brian C. Sawyer, Adam M. Meier, Karl A. Burkhardt, Christopher M. Seck, Christopher M. Shappert, Nicholas D. Guise, Curtis E. Volin, Spencer D. Fallek, Harley T. Hayden, Wade G. Rellergert, and Kenton R. Brown, “High-fidelity bell-state preparation with ${}^{40}{\mathrm{ca}}^{+}$ optical qubits,” Phys. Rev. Lett. 127, 130505 (2021).
  * et al. (2022) C. Ryan-Anderson et al., “Implementing fault-tolerant entangling gates on the five-qubit code and the color code,” (2022), arXiv:2208.01863 [quant-ph] .
  * Postler  _et al._ (2022) Lukas Postler, Sascha Heu$\beta$en, Ivan Pogorelov, Manuel Rispler, Thomas Feldker, Michael Meth, Christian D. Marciniak, Roman Stricker, Martin Ringbauer, Rainer Blatt, Philipp Schindler, Markus Müller, and Thomas Monz, “Demonstration of fault-tolerant universal quantum gate operations,” Nature 605, 675–680 (2022).
  * Pino  _et al._ (2021) J. M. Pino, J. M. Dreiling, C. Figgatt, J. P. Gaebler, S. A. Moses, M. S. Allman, C. H. Baldwin, M. Foss-Feig, D. Hayes, K. Mayer, C. Ryan-Anderson, and B. Neyenhuis, “Demonstration of the trapped-ion quantum CCD computer architecture,” Nature 592, 209–213 (2021).
  * et al. (2023) S. A. Moses et al., “A race track trapped-ion quantum processor,” (2023), arXiv:2305.03828 [quant-ph] .
  * Landsman  _et al._ (2019) K. A. Landsman, Y. Wu, P. H. Leung, D. Zhu, N. M. Linke, K. R. Brown, L. Duan, and C. Monroe, “Two-qubit entangling gates within arbitrarily long chains of trapped ions,” Phys. Rev. A 100, 022332 (2019).
  * Wang  _et al._ (2020) Ye Wang, Stephen Crain, Chao Fang, Bichen Zhang, Shilin Huang, Qiyao Liang, Pak Hong Leung, Kenneth R. Brown, and Jungsang Kim, “High-fidelity two-qubit gates using a microelectromechanical-system-based beam steering system for individual qubit addressing,” Phys. Rev. Lett. 125, 150505 (2020).
  * Monroe  _et al._ (2014) C. Monroe, R. Raussendorf, A. Ruthven, K. R. Brown, P. Maunz, L.-M. Duan, and J. Kim, “Large-scale modular quantum-computer architecture with atomic memory and photonic interconnects,” Phys. Rev. A 89, 022317 (2014).
  * Stephenson  _et al._ (2020) L. J. Stephenson, D. P. Nadlinger, B. C. Nichol, S. An, P. Drmota, T. G. Ballance, K. Thirumalai, J. F. Goodwin, D. M. Lucas, and C. J. Ballance, “High-rate, high-fidelity entanglement of qubits across an elementary quantum network,” Phys. Rev. Lett. 124, 110501 (2020).
  * Krutyanskiy  _et al._ (2019) V. Krutyanskiy, M. Meraner, J. Schupp, V. Krcmarsky, H. Hainzer, and B. P. Lanyon, “Light-matter entanglement over 50 km of optical fibre,” npj Quantum Information 5 (2019), 10.1038/s41534-019-0186-3.
  * Campbell (2007) Earl T. Campbell, “Distributed quantum-information processing with minimal local resources,” Phys. Rev. A 76, 040302 (2007).
  * Browaeys and Lahaye (2020) Antoine Browaeys and Thierry Lahaye, “Many-body physics with individually controlled Rydberg atoms,” Nature Physics 16, 132–142 (2020).
  * Bluvstein  _et al._ (2022) Dolev Bluvstein, Harry Levine, Giulia Semeghini, Tout T Wang, Sepehr Ebadi, Marcin Kalinowski, Alexander Keesling, Nishad Maskara, Hannes Pichler, Markus Greiner, _et al._ , “A quantum processor based on coherent transport of entangled atom arrays,” Nature 604, 451–456 (2022).
  * Scholl  _et al._ (2021) Pascal Scholl, Michael Schuler, Hannah J Williams, Alexander A Eberharter, Daniel Barredo, Kai-Niklas Schymik, Vincent Lienhard, Louis-Paul Henry, Thomas C Lang, Thierry Lahaye, _et al._ , “Quantum simulation of 2d antiferromagnets with hundreds of rydberg atoms,” Nature 595, 233–238 (2021).
  * Ebadi  _et al._ (2021) Sepehr Ebadi, Tout T Wang, Harry Levine, Alexander Keesling, Giulia Semeghini, Ahmed Omran, Dolev Bluvstein, Rhine Samajdar, Hannes Pichler, Wen Wei Ho, _et al._ , “Quantum phases of matter on a 256-atom programmable quantum simulator,” Nature 595, 227–232 (2021).
  * Young  _et al._ (2023) Aaron W Young, Shawn Geller, William J Eckner, Nathan Schine, Scott Glancy, Emanuel Knill, and Adam M Kaufman, “An atomic boson sampler,” arXiv preprint arXiv:2307.06936 (2023).
  * Tao  _et al._ (2023) Renhao Tao, Maximilian Ammenwerth, Flavien Gyger, Immanuel Bloch, and Johannes Zeiher, “High-fidelity detection of large-scale atom arrays in an optical lattice,” arXiv preprint arXiv:2309.04717 (2023).
  * Eckner  _et al._ (2023) William J Eckner, Nelson Darkwah Oppong, Alec Cao, Aaron W Young, William R Milner, John M Robinson, Jun Ye, and Adam M Kaufman, “Realizing spin squeezing with rydberg interactions in an optical clock,” Nature , 1–6 (2023).
  * Trotzky  _et al._ (2008) Stefan Trotzky, Patrick Cheinet, S Folling, Michael Feld, Ute Schnorrberger, Ana Maria Rey, Anatoli Polkovnikov, Eugene A Demler, Mikhail D Lukin, and Immanuel Bloch, “Time-resolved observation and control of superexchange interactions with ultracold atoms in optical lattices,” Science 319, 295–299 (2008).
  * Kaufman  _et al._ (2015) AM Kaufman, BJ Lester, M Foss-Feig, ML Wall, AM Rey, and CA Regal, “Entangling two transportable neutral atoms via local spin exchange,” Nature 527, 208–211 (2015).
  * Barredo  _et al._ (2016) Daniel Barredo, Sylvain De Léséleuc, Vincent Lienhard, Thierry Lahaye, and Antoine Browaeys, “An atom-by-atom assembler of defect-free arbitrary two-dimensional atomic arrays,” Science 354, 1021–1023 (2016).
  * Endres  _et al._ (2016) Manuel Endres, Hannes Bernien, Alexander Keesling, Harry Levine, Eric R Anschuetz, Alexandre Krajenbrink, Crystal Senko, Vladan Vuletic, Markus Greiner, and Mikhail D Lukin, “Atom-by-atom assembly of defect-free one-dimensional cold atom arrays,” Science 354, 1024–1027 (2016).
  * Singh  _et al._ (2023) K Singh, CE Bradley, S Anand, V Ramesh, R White, and H Bernien, “Mid-circuit correction of correlated phase errors using an array of spectator qubits,” Science 380, 1265–1269 (2023).
  * Lis  _et al._ (2023) Joanna W Lis, Aruku Senoo, William F McGrew, Felix Rönchen, Alec Jenkins, and Adam M Kaufman, “Mid-circuit operations using the omg-architecture in neutral atom arrays,” arXiv preprint arXiv:2305.19266 (2023).
  * Norcia  _et al._ (2023) MA Norcia, WB Cairncross, K Barnes, P Battaglino, A Brown, MO Brown, K Cassella, C-A Chen, R Coxe, D Crow, _et al._ , “Mid-circuit qubit measurement and rearrangement in a 137 yb atomic array,” arXiv preprint arXiv:2305.19119 (2023).
  * Scholl  _et al._ (2023) Pascal Scholl, Adam L Shaw, Richard Bing-Shiun Tsai, Ran Finkelstein, Joonhee Choi, and Manuel Endres, “Erasure conversion in a high-fidelity rydberg quantum simulator,” arXiv preprint arXiv:2305.03406 (2023).
  * Pause  _et al._ (2023) Lars Pause, Tilman Preuschoff, Dominik Schäffner, Malte Schlosser, and Gerhard Birkl, “Reservoir-based deterministic loading of single-atom tweezer arrays,” Physical Review Research 5, L032009 (2023).
  * Xia  _et al._ (2015) T Xia, M Lichtman, K Maller, AW Carr, MJ Piotrowicz, L Isenhower, and M Saffman, “Randomized benchmarking of single-qubit gates in a 2d array of neutral-atom qubits,” Physical review letters 114, 100503 (2015).
  * Wang  _et al._ (2016) Yang Wang, Aishwarya Kumar, Tsung-Yao Wu, and David S Weiss, “Single-qubit gates based on targeted phase shifts in a 3d neutral atom array,” Science 352, 1562–1565 (2016).
  * Sheng  _et al._ (2018) Cheng Sheng, Xiaodong He, Peng Xu, Ruijun Guo, Kunpeng Wang, Zongyuan Xiong, Min Liu, Jin Wang, and Mingsheng Zhan, “High-fidelity single-qubit gates on neutral atoms in a two-dimensional magic-intensity optical dipole trap array,” Physical review letters 121, 240501 (2018).
  * Jenkins  _et al._ (2022) Alec Jenkins, Joanna W Lis, Aruku Senoo, William F McGrew, and Adam M Kaufman, “Ytterbium nuclear-spin qubits in an optical tweezer array,” Physical Review X 12, 021027 (2022).
  * Ma  _et al._ (2022) Shuo Ma, Alex P Burgers, Genyue Liu, Jack Wilson, Bichen Zhang, and Jeff D Thompson, “Universal gate operations on nuclear spin qubits in an optical tweezer array of yb 171 atoms,” Physical Review X 12, 021028 (2022).
  * Suchara  _et al._ (2015) Martin Suchara, Andrew W Cross, and Jay M Gambetta, “Leakage suppression in the toric code,” in  _2015 IEEE International Symposium on Information Theory (ISIT)_ (IEEE, 2015) pp. 1119–1123.
  * Berthusen and Gottesman (2023) Noah Berthusen and Daniel Gottesman, “Partial Syndrome Measurement for Hypergraph Product Codes,” (2023), arXiv:2306.17122 [quant-ph] .
  * Dennis  _et al._ (2002) Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill, “Topological quantum memory,” Journal of Mathematical Physics 43, 4452–4505 (2002).
  * Delfosse and Nickerson (2021) Nicolas Delfosse and Naomi H. Nickerson, “Almost-linear time decoding algorithm for topological codes,” Quantum 5, 595 (2021).
  * Héctor Bombín (2015) Héctor Bombín, “Single-shot fault-tolerant quantum error correction,” Physical Review X 5 (2015), 10.1103/physrevx.5.031043.
  * Kubica and Vasmer (2022) Aleksander Kubica and Michael Vasmer, “Single-shot quantum error correction with the three-dimensional subsystem toric code,” Nature Communications 13 (2022), 10.1038/s41467-022-33923-4.
  * Stahl (2023) Charles Stahl, “Single-shot quantum error correction in intertwined toric codes,” (2023), arXiv:2307.08118 [quant-ph] .
  * Xu  _et al._ (2023) Qian Xu, J. Pablo Bonilla Ataides, Christopher A. Pattison, Nithin Raveendran, Dolev Bluvstein, Jonathan Wurtz, Bane Vasic, Mikhail D. Lukin, Liang Jiang, and Hengyun Zhou, “Constant-overhead fault-tolerant quantum computation with reconfigurable atom arrays,” (2023), arXiv:2308.08648 [quant-ph] .
  * Roffe  _et al._ (2020) Joschka Roffe, David R. White, Simon Burton, and Earl Campbell, “Decoding across the quantum low-density parity-check code landscape,” Physical Review Research 2 (2020), 10.1103/physrevresearch.2.043423.
  * Leverrier and Zémor (2022b) Anthony Leverrier and Gilles Zémor, “Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes,” (2022b), arXiv:2206.07571 [quant-ph] .
  * Leverrier (2022) Anthony Leverrier, “Mapping the toric code to the rotated toric code,” https://github.com/errorcorrectionzoo/eczoo_data/files/9210173/rotated.pdf (2022).
  * Quintavalle  _et al._ (2021) Armanda O. Quintavalle, Michael Vasmer, Joschka Roffe, and Earl T. Campbell, “Single-shot error correction of three-dimensional homological product codes,” PRX Quantum 2 (2021), 10.1103/prxquantum.2.020340.