Algorithmic Fault Tolerance for Fast Quantum Computing

Hengyun Zhou,1, 2, ∗ Chen Zhao,1, † Madelyn Cain,2 Dolev Bluvstein,2 Casey Duckering,1
Hong-Ye Hu,2 Sheng-Tao Wang,1 Aleksander Kubica,3, 4, 5 and Mikhail D. Lukin2, ‡
1
QuEra Computing Inc., 1284 Soldiers Field Road, Boston, MA, 02135, US
2
Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA
3
AWS Center for Quantum Computing, Pasadena, California 91125, USA
4
California Institute of Technology, Pasadena, California 91125, USA
5
Department of Applied Physics, Yale University, New Haven, Connecticut 06511, USA USA
Fast, reliable logical operations are essential for the realization of useful quantum computers [1–
3], as they are required to implement practical quantum algorithms at large scale. By redundantly
encoding logical qubits into many physical qubits and using syndrome measurements to detect and
subsequently correct errors, one can achieve very low logical error rates. However, for most practical
arXiv:2406.17653v1 [quant-ph] 25 Jun 2024

quantum error correcting (QEC) codes such as the surface code, it is generally believed that due
to syndrome extraction errors, multiple extraction rounds—on the order of the code distance d—
are required for fault-tolerant computation [4–14]. Here, we show that contrary to this common
belief, fault-tolerant logical operations can be performed with constant time overhead for a broad
class of QEC codes, including the surface code with magic state inputs and feed-forward operations,
to achieve “algorithmic fault tolerance”. Through the combination of transversal operations [7]
and novel strategies for correlated decoding [15], despite only having access to partial syndrome
information, we prove that the deviation from the ideal measurement result distribution can be made
exponentially small in the code distance. We supplement this proof with circuit-level simulations in
a range of relevant settings, demonstrating the fault tolerance and competitive performance of our
approach. Our work sheds new light on the theory of quantum fault tolerance, potentially reducing
the space-time cost of practical fault-tolerant quantum computation by orders of magnitude.

a Conventional fault tolerance b Algorithmic fault tolerance

Quantum computers have the potential to solve cer- Θ(1) SE rounds
Θ(d) SE rounds
tain computational problems much faster than their clas-

}
}
sical counterparts [1, 16]. Since most known applica-
tions require quantum computers with extremely low er-
ror rates, quantum error correction (QEC) and strate-
}
Logical
gies for fault-tolerant quantum computing (FTQC) are gate
necessary. These methods encode logical quantum infor-
mation into a QEC code involving many physical qubits, Independent decoding Correlated decoding
such that the lowest weight logical error has weight equal
to the code distance d and is therefore unlikely. FIG. 1. Algorithmic fault tolerance. (a) Conventional FT
analysis separately examines each gadget (red boxes) in the
Performing large-scale computation, however, comes circuit and ensures they are individually FT [4, 7, 31]. This
with significant overhead [2, 16]. By performing syn- requires Θ(d) syndrome extraction (SE) rounds to achieve
drome extraction (SE), one can reveal error information FT. (b) Algorithmic FT directly uses all accessible syndrome
and use a classical decoder to correct physical errors in information up to a logical measurement (blue box), and guar-
software and interpret logical measurement results. How- antees FT of the measurement result, even if the gadgets are
not individually FT and if future syndrome information is not
ever, in the presence of noisy syndrome measurements [4–
yet accessible (partial decoding). We realize algorithmic FT
7, 10], one typically requires a number of SE rounds through transversal operations, and only require a single SE
that scales linearly in d, i.e., Θ(d) [17] (see Fig. 1(a)). round per logical operation, thus allowing constant time im-
This is the case, for example, for the celebrated surface plementations of logical operations.
code [8–10], one of the leading candidates for practical
FTQC due to its simple 2D layout and competitive er-
ror thresholds. In typical compilations based on lattice native approaches introduce higher hardware complex-
surgery or braiding [11–14, 18], each logical operation re- ity [20, 22–24] or necessitate certain properties of the un-
quires Θ(d) SE rounds, thus incurring a space-time vol- derlying codes, such as the single shot QEC property [25–
ume per logical operation of Θ(d3 ). This reduces the 29], often incurring a trade-off between space and time
logical clock speed by a factor proportional to the code when executing logical operations [2, 16, 30].
distance, typically on the order of 10 –100 [14, 16]. The We introduce and develop a novel approach to FTQC
same considerations also apply when performing logical that we refer to as “algorithmic fault tolerance”, and
operations with many quantum low-density parity-check show that it can lead to a substantial reduction in space-
(QLDPC) codes [19, 20]. While there have been various time cost. We focus on transversal implementations of
efforts at addressing this challenge [5, 21], these alter- Clifford circuits [7, 32] with magic state inputs and feed-
 2

forward [33], thereby allowing universal quantum com- if the physical error rate p < pth under the basic model of
putation. Such transversal gate capabilities have already fault tolerance [5], then our protocol can perform constant
been demonstrated in multiple hardware platforms, such time logical operations, with only a single SE round per
as neutral atoms and trapped ions [34–36]. We show operation, while suppressing the total logical error rate as
that contrary to the common belief, for any Calderbank- PL = exp(−Θ(dn )).
Shor-Steane (CSS) QLDPC code [6, 37], these opera- The formal theorem statement and the corresponding
tions can be performed fault-tolerantly with only con- proof can be found in Supplementary Materials [41]. Our
stant time overhead per operation, provided that decod- analysis assumes the basic model of fault tolerance [5]. In
ing can be implemented efficiently. The key idea is to particular, we consider the local stochastic noise model,
consider the fault tolerance of the algorithm as a whole where we apply depolarizing errors on each data qubit
(Fig. 1(b)) [38–40]. We achieve this by performing corre- every SE round and measurement errors on each SE re-
lated decoding [15, 30, 36] despite only having access to sult, with a probability that decays exponentially in the
partial syndrome information, and ensuring consistency weight of the error event. This can be readily general-
in the presence of magic states and feed-forward via ad- ized to circuit-level noise by noting the bounded error
ditional operations in software. We verify such algorith- propagation for constant depth SE circuits in QLDPC
mic fault tolerance through a combination of proofs and codes. We also assume the most likely error (MLE) de-
circuit-level numerical simulations of our protocol, in- coder and fast classical computation (Methods). Finally,
cluding a simulation of state distillation factories [13, 33], we assume that all code patches are identical, and the
finding very little change to physical error thresholds. number of qubit locations within a code patch that any
Specializing to the surface code, our results reduce the given qubit can be coupled to via transversal gates is
per-operation time cost from Θ(d) to Θ(1), including for bounded by some constant t, in order to control error
Clifford operations used in magic state distillation. Note propagation.
that unlike methods that trade space for time, our tech- A key observation is that by considering the algorithm
niques represent a direct reduction in space-time volume, as a whole and leveraging the deterministic propagation
which is usually the ultimate quantity of interest. of errors through transversal Clifford circuits, one can
use the surrounding syndrome history to correct for noisy
measurements (Fig. 1(b)). This correlated decoding tech-
ALGORITHMIC FAULT TOLERANCE VIA nique has been shown to enable Θ(1) SE rounds for Clif-
TRANSVERSAL OPERATIONS ford circuits without feed-forward [15]. However, a key
component of many schemes for achieving universality is
We focus on transversal Clifford circuits with magic magic state teleportation, which crucially relies on the
state inputs, where Clifford operations are implemented ability to realize feed-forward operations.
with a depth-one quantum circuit (Methods). This is As illustrated by the example shown in Fig. 2(a), such
interleaved with SE rounds using ancilla qubits, which feed-forward operations require on-the-fly interpretation
reveal error information on the data qubits and enable of logical measurements, followed by a subsequent con-
error correction. In addition to transversal gates [7], we ditional gate, when only a subset of the logical qubits
refer to preparation of data qubits in |0⟩ followed by one have been measured. As we do not yet have future syn-
SE round as transversal state preparation, and Z ba- drome information on the unmeasured logical qubits, one
sis measurement of all data qubits as transversal mea- may be concerned that this can lead to an incorrect as-
surement. To achieve universality, we allow teleporting signment of logical measurement results. Indeed, prior
in low-noise magic states with feed-forward operations work analyzing circuits with magic states assumed that
based on past measurement results, and use the same at least d SE rounds separated state initialization and
Clifford operations above to prepare high quality magic measurements or out-going qubits [30, 42, 43]. As shown
states via magic state distillation [33]. We make use of in Fig. 2(b) for the Θ(1) SE round case, with new syn-
CSS QLDPC codes, where each data or ancilla qubit drome information, one may end up concluding a dif-
interacts with a constant number of other qubits, and ferent measurement result, which leads to an incorrect
each stabilizer generator consists of all X or all Z oper- feed-forward operation.
ators [6, 37]. Within this setting, our key result can be Surprisingly, we find that these inconsistencies can be
formulated as the following theorem: accounted for in classical processing, with a reinterpreta-
Theorem 1 (informal): Exponential error sup- tion of subsequent measurement results (Fig. 2(c), Pauli
pression for constant time transversal Clifford frame updates). The inconsistent measurement result
operations with any CSS QLDPC code. For a corresponds to an X operator applied right before the Z
transversal Clifford circuit with low-noise magic state measurement. Tracing back, we can find an X operator
inputs and feed-forward operations, that can be imple- on the |+⟩ initial state (Fig. 2(c)) which does not change
mented with a given CSS QLDPC code family Qd of grow- the logical state but propagates through to apply X on
ing code distance d, there exists a threshold pth , such that the logical measurement, together with some other logi-
 3

cal Pauli updates on the remaining logical qubits. These a Partial decoding Apply
MZ feed-forward
are stabilizers of the logical state, which leave the state
invariant. Indeed, the fact that this measurement result b Full decoding (step 1)
S MZ
can be affected by non-fault-tolerant state preparation X MZ M1=+1

implies that the measurement anti-commutes with the MZ Ma=-1

S MZ M2=-1
corresponding Pauli stabilizer, necessarily leading to a X

50/50 random outcome that is not changed by a logi- c Full decoding (step 2) MZ
Ma=+1
Inconsistent
cal flip. Products of individual measurements can have MZ M1=+1
feed-forward
nontrivial correlations only if they commute with all the X
S MZ M2=+1 Guarantee
Pauli stabilizers. Because they commute, however, they X
consistency
are also guaranteed to be insensitive to the state initial- MZ Ma=-1

ization errors.
Therefore, in the second step of our decoding proce- FIG. 2. Illustration of decoding strategy. (a) Logical
dure, we apply such Pauli operators on initial input states quantum circuit with measurement and feed-forward. All log-
until the measurement results are consistent with the pre- ical operations are transversal and interleaved with a single
vious commitments (Fig. 2(c)). Beyond this specific cir- SE round, instead of d SE rounds. We must decode and com-
cuit, the required pattern that leads to a consistent as- mit mid-circuit to a measurement result for the bottom qubit,
despite lacking complete syndrome information on the top two
signment can always be computed efficiently by solving a
qubits (partial decoding). (b) With the measurement result of
linear system of equations (Methods). In practice, sub- the bottom qubit, a feed-forward operation is applied, the re-
sets of measurements in which all measurement products maining circuit is executed, and decoding is performed again
are 50/50 random can be classically assigned in advance, on the whole circuit. The second decoding round may assign a
with the future measurements determined through the different result to the bottom qubit, causing an inconsistency
above procedure to ensure consistency. This also implies in feed-forward operations. (c) To guarantee consistency, we
that decoding of certain measurements can be delayed apply an X operator on the |+⟩ initial state of the middle
qubit, which acts trivially on |+⟩, but changes the interpreted
until joint products need to be determined, and some as-
logical measurement result Ma to be consistent with before.
signments can be performed deterministically in specific This also leads to a re-interpretation of the logical measure-
cases such as state distillation (Methods). ment result M2 .
Our protocol that leads to Theorem 1 thus consists
of two main steps: correlated decoding based on partial
syndrome information, and application of logical stabiliz- has probability ps/2 under the MLE decoder. Finally, we
ers to guarantee consistency between multiple decoding count the number of such connected clusters of size s,
rounds (Fig. 2). which scales as (ve)s , where e is the natural base and v
We now sketch the intuition behind our proof of The- is a constant upper-bounding the error connectivity for
orem 1. There are two types of logical errors that may a QLDPC code. The combined probability of an error
occur with our protocol. The first, a heralded inconsis- thus scales as
tency error, occurs when we are not able to find a set of √ Θ(d)
Perr ∝ ps/2 (2ve)s = (2ve p) →0 (1)
operators to apply that yield the same outcome as pre-
viously committed measurement results. The second, a when the physical error rate is sufficiently low
regular error, occurs when an erroneous logical operator p ≪ 1/(ve)2 (the factor of 2 comes from a combinatorial
is applied that results in a different measurement distri- sum), thereby establishing the existence of a threshold
bution. and exponential error suppression.
Because imperfect readout during transversal measure- Specializing to the surface code and utilizing the full
ments are equivalent to data qubit errors followed by per- transversal Clifford gate set accessible to the surface code
fect measurements, transversal measurements produce (Methods), an immediate corollary of our main theorem
reliable syndrome information. Intuitively, this prevents is a threshold result for performing constant time logical
individual errors from leading to high-weight corrections operations with an arbitrary transversal Clifford circuit.
on the logical qubits we measure, the main reason for This result supports universal quantum computing when
needing d SE rounds in typical FT state initialization pro- we allow magic state inputs prepared with sufficiently
tocols. At the same time, the use of correlated decoding, low noise.
together with the structured error propagation through Preparing high quality magic state inputs, in turn, can
transversal Clifford gates, allow us to propagate this syn- be performed simply with the same Clifford operations
drome information and correct relevant errors happen- and easy-to-prepare non-fault-tolerant magic states [44–
ing throughout the circuit. With these observations, we 46], a procedure known as magic state distillation [33]
prove that for either type of logical error to occur, the to- (see ED Fig. 3). We expect that the same algorithmic
tal Pauli weight s of physical error and subsequent correc- FT approach described above achieves a Θ(d) speed-up
tion in a connected cluster must satisfy s = Θ(d), which in distillation time as well. The distillation factory and
 4

a b a Distillation Factory
 
 †
c
|+ S

|+ H

First Both |+ H

MZ p step steps
MZ 0.16%  
0.25% 0 H
MZ ×8
0.40%

|+ H

c d  
Transversal Lattice surgery 0 H

X
Split
 
0 H
X
d
MZ  
0 H
MZ

MZ patch
GHZ X
prep.
MZ growth
preparation MZ
X
X
b
Z MZ Level 1
Z MZ
MZ
prep.
Z

=
FIG. 3. Numerical verification of fault tolerance.
(a) Simulation of circuit with repeated ZZ measurement (in-
set), where we commit mid-circuit to each measurement result Level 2
of the logical ancilla using only the syndrome information up prep.
Level 1
to that point. The total logical error rate as a function of = Distillation
circuit-level physical error rate p, for varying code distance d, Factory
shows clear threshold behavior. (b) Heralded error rate with
and without the second step of our decoding strategy, as a
function of code distance and for different physical error rates,
FIG. 4. |Y ⟩ state distillation factory. (a) Illustration of a
for the same circuit as (a). Only with both steps do we observe
|Y ⟩ state distillation factory based on the [[7,1,3]] Steane code,
exponential suppression of the logical error rate. (c) Com-
consisting of state initialization, layers of transversal CNOTs,
parison of two different methods for logical state preparation
followed by a teleported S gate. Each operation involves only
between three rotated surface codes and subsequent telepor-
a single SE round. Two of the CNOTs in the first layer act
tation, for fixed circuit noise p = 0.3%. We use transversal
trivially and can be omitted. (b) The |Y ⟩ resource state is
gates (left) and lattice surgery (right), in both cases with only
prepared via state injection at the first level, and via the first-
a single SE round. (d) With transversal gates, the error rate
level factory for the second level. (c) 1-level factory output
decreases exponentially with the code distance. With a single
state infidelity as a function of input state infidelity, for fixed
round of lattice surgery, the error rate instead increases lin-
circuit noise p = 0.1% and varying levels of artificially injected
early with code distance, as a single stabilizer measurement
Z errors. The ideal curve is calculated assuming the gate
error affects the logical ZZ measurement result.
operations in the factory are perfect. (d) Performance for one
and two rounds of distillation, showing good agreement with
the expected scaling.
main computation can then be combined by applying our
decoding approach to the joint system. In Methods and
Supplementary Information, we further describe an ex- it with existing methods. We consider various test cases
tension of our results to the case of single-shot code patch of our approach that also serve as key subroutines in
growth, relevant to practical distillation factories [47, 48]. large-scale algorithms.
Taken together, these results provide a theoretical foun- We first consider a simple circuit with intermediate log-
dation for our factor of Θ(d) improvement in logical clock ical measurements (inset of Fig. 3(a)). In this example,
speed compared to standard FT approaches for universal two logical qubits are transversally initialized in |+⟩, and
quantum computation. an ancilla logical qubit is used to measure the ZZ corre-
lation a total of eight times, before the two logical qubits
are transversally measured in the Z basis. While indi-
COMPETITIVE NUMERICAL PERFORMANCE vidual logical measurement results are random, a correct
realization of this circuit should yield the same result for
We now turn to circuit-level simulations of our protocol ZZ each time, which in turn should be consistent with
to numerically evaluate its performance [39], and contrast the final logical measurement results. We employ our al-
 5

gorithmic FT protocol to decode the circuit up to each to p = 0.1%, and vary the input infidelity Pin in Fig. 4(c).
logical measurement using only the syndrome informa- Examining the output |Y ⟩ of a one-level factory, we find
tion accessible at that point. We use the rotated surface that as the code distance is increased, the output logical
code, a circuit-level depolarizing noise model [15, 49], a error rate Pout approaches the fidelity expected for ideal
3 4
MLE decoder based on integer programming [15, 50], and Clifford logical gates in the factory Pout = 7Pin + O(Pin )
employ the two-step process described above (see Supple- (see Methods for the full expression), across the explored
mentary Information). fidelity regime.
Figure 3(a-b) show the results of numerical simula- Finally, we simulate the logical error rate for a two-
tions. We find that the total logical error rate, de- level |Y ⟩ state distillation factory, involving a total of 113
fined as the probability that a logical error of either logical qubits, where the output |Y ⟩ states of a d1 = 5
type mentioned above happened anywhere in the cir- factory is fed into a second factory with d2 = 9, with the
cuit, shows characteristic threshold behavior, with an es- distance chosen such that the logical error is dominated
timated threshold ≳ 0.85%. As an SE round involves four by the input state infidelity. As shown in Fig. 4(d), the
layers of CNOT gates, while the transversal CNOT only logical error rates at each level of the distillation proce-
involves a single layer, the effective error rate is domi- dure are consistent with that expected based on the ideal
nated by SE operations, hence it may be expected that factory formula (Methods), confirming that our approach
the threshold is close to the circuit-noise memory thresh- is FT. Since the state injection procedure is agnostic to
old. The number of SE rounds can be further optimized: the particular state that is injected, we expect that our
for example, in Ref. [15], performing one SE round ev- results will readily generalize to the setting of |T ⟩ magic
ery four gate layers minimized the space-time cost per state factories.
CNOT, suggesting that the practical improvement may
be ≳ 2d in some regimes [51]. In Fig. 3(b), we further
compare the scaling of heralded failure rates in the pres- DISCUSSION AND OUTLOOK
ence and absence of the second step of our decoding pro-
cedure, as a function of code distance d. We find that Transversal operations and correlated decoding were
this additional step is crucial to achieve exponential sup- recently found to be highly effective in experiments with
pression with the code distance. reconfigurable neutral atom arrays [36]. The principles
We now contrast our approach with lattice surgery in of algorithmic fault-tolerance described here are the core
a similar setting [11, 12, 18, 52]. We consider the logical underlying mechanisms of these observations, such as cor-
circuit in Fig. 3(c), where a GHZ state preparation circuit related decoding of a logical Bell state [36], and our re-
is followed by teleportation of the GHZ state to another sults here indicate that the same techniques allow for
set of logical qubits, and then measurement in the Z ba- Θ(d) time reduction for universal computation. While
sis [41]. Using transversal gates with only a single SE recent work has provided strong evidence that this re-
round during |+⟩ and |0⟩ state preparation, and decod- duction might be possible for circuits consisting purely
ing each logical measurement with only accessible infor- of Clifford gates and Pauli basis inputs [15], up to now
mation at that stage, we find that the logical error rate it has generally been believed that this conclusion does
decreases exponentially with the code distance, consis- not hold when performing universal quantum computa-
tent with our FT analysis. In contrast, state preparation tion [30, 42, 43], which crucially relies on the use of magic
based on a single round of lattice surgery [52], which in- states and feed-forward operations. The present work
volves performing syndrome extraction with a larger code not only demonstrates that this Θ(d) time cost reduction
patch and then splitting it into three individual logical is broadly applicable to universal quantum computing,
qubits, does not yield improved logical error rate as the but also provides a theoretical foundation for it through
code distance increases, as a single error can lead to in- mathematical fault tolerance proofs.
correct inference of the ZZ correlation of the GHZ state Although our analysis focused on the use of an MLE
(Supplementary Information). Unlike transversal mea- decoder, our numerical simulations suggest that algo-
surements, logical information here is contained in noisy rithms with polynomial runtime can still achieve a com-
stabilizer products, which require repetition to reliably petitive threshold [41], and the development of improved,
infer. parallel correlated decoders is an important area of fu-
Next, we simulate a state distillation factory. In order ture research (Methods). Taking into account the de-
to perform a classical simulation of a full factory, we fo- coding time overhead, we may eventually need to insert
cus on distillation of the |Y ⟩ = S|+⟩ state (Fig. 4(a)), more SE rounds to simplify decoding or wait for decoding
which allows the easy implementation of S gates in the completion [53], as is also needed for FT protocols that
surface code. Since this circuit has a similar structure to rely on single-shot quantum error correction [25]. In that
the practically relevant |T ⟩ magic state distillation fac- case, we still expect a significant practical saving over ex-
tories (Methods, ED Fig. 3), we expect them to have isting schemes. In light of recent experimental advances
similar performance. We fix the error rate of the circuit [36], a full compilation and evaluation of the space-time
 6

savings in parallel reconfigurable architectures such as

neutral atom arrays is an important next step. Finally,
it will be interesting to investigate how these results can ∗
These authors contributed equally; hyzhou@quera.com
be combined with recent progress toward constant-space- †
These authors contributed equally
overhead quantum computation [5, 20, 23, 27, 29, 54–56] ‡
lukin@physics.harvard.edu
or generalized to transversal non-Clifford gates [30, 57– [1] A. M. Dalzell, S. McArdle, M. Berta, P. Bienias, C.-
62], in order to further reduce the space-time volume of F. Chen, A. Gilyén, C. T. Hann, M. J. Kastoryano,
large-scale quantum computation. E. T. Khabiboulline, A. Kubica, G. Salton, S. Wang,
and F. G. S. L. Brandão, Quantum algorithms: A sur-
vey of applications and end-to-end complexities, arXiv
preprint arXiv:2310.03011 (2023).
[2] M. E. Beverland, P. Murali, M. Troyer, K. M. Svore,
AUTHOR CONTRIBUTIONS T. Hoeffler, V. Kliuchnikov, G. H. Low, M. Soeken,
A. Sundaram, and A. Vaschillo, Assessing requirements
to scale to practical quantum advantage, arXiv preprint
H.Z. formulated the decoding strategy and developed arXiv:2211.07629 10.48550/arxiv.2211.07629 (2022).
an initial proof sketch through discussions with C.Z., [3] R. Babbush, J. R. McClean, M. Newman, C. Gid-
M.C., D.B., C.D., S.-T.W., A.K., and M.D.L.. C.Z., ney, S. Boixo, and H. Neven, Focus beyond Quadratic
M.C., H.Z., and H.H. performed numerical simulations. Speedups for Error-Corrected Quantum Advantage,
H.Z., A.K., C.Z., M.C., and C.D. proved the fault toler- PRX Quantum 2, 010103 (2021).
ance of the scheme. All authors contributed to writing [4] D. Gottesman, An Introduction to Quantum Error
Correction and Fault-Tolerant Quantum Computation,
the manuscript. arXiv preprint arXiv:0904.2557 , 13 (2009).
[5] D. Gottesman, Fault-Tolerant Quantum Computation
with Constant Overhead, Quantum Information and
Computation 14, 1338 (2013).
ACKNOWLEDGEMENTS [6] A. M. Steane, Error Correcting Codes in Quantum The-
ory, Physical Review Letters 77, 793 (1996).
[7] P. W. Shor, Fault-tolerant quantum computation, arXiv
We acknowledge helpful discussions with G. Baranes, preprint arXiv:quant-ph/9605011 (1996).
P. Bonilla, E. Campbell, S. Evered, S. Geim, L. Jiang, [8] A. Y. Kitaev, Fault-tolerant quantum computation by
M. Kalinowski, A. Krishna, S. Li, D. Litinski, anyons, Annals of Physics 303, 2 (2003).
[9] S. B. Bravyi, A. Y. Kitaev, and L. D. Landau, Quan-
T. Manovitz, N. Maskara, Y. Wu, and Q. Xu. We tum codes on a lattice with boundary, arXiv preprint
would particularly like to thank C. Pattison for early dis- arXiv:quant-ph/9811052 (1998).
cussions and suggesting the simulation of the |Y ⟩ state [10] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill,
distillation factory, and J. Haah for stimulating discus- Topological quantum memory, Journal of Mathemati-
sions and deep insights. We acknowledge financial sup- cal Physics 43, 4452 (2002).
port from IARPA and the Army Research Office, un- [11] C. Horsman, A. G. Fowler, S. Devitt, and R. V. Me-
der the Entangled Logical Qubits program (Cooperative ter, Surface code quantum computing by lattice surgery,
New Journal of Physics 14, 123011 (2012).
Agreement Number W911NF-23-2-0219), the DARPA [12] D. Litinski, A Game of Surface Codes: Large-Scale
ONISQ program (grant number W911NF2010021), the Quantum Computing with Lattice Surgery, Quantum
DARPA IMPAQT program (grant number HR0011- 3, 128 (2019).
23-3-0012), the Center for Ultracold Atoms (a NSF [13] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N.
Physics Frontiers Center, PHY-1734011), the National Cleland, Surface codes: Towards practical large-scale
Science Foundation (grant number PHY-2012023 and quantum computation, Physical Review A 86, 032324
grant number CCF-2313084), the Army Research Office (2012).
[14] D. Litinski and N. Nickerson, Active volume: An ar-
MURI (grant number W911NF-20-1-0082), DOE/LBNL
chitecture for efficient fault-tolerant quantum comput-
(grant number DE-AC02-05CH11231). M.C. acknowl- ers with limited non-local connections, arXiv preprint
edges support from Department of Energy Computa- arXiv:2211.15465 (2022).
tional Science Graduate Fellowship under award num- [15] M. Cain, C. Zhao, H. Zhou, N. Meister, J. Pablo,
ber DE-SC0020347. D.B. acknowledges support from B. Ataides, A. Jaffe, D. Bluvstein, and M. D. Lukin,
the NSF Graduate Research Fellowship Program (grant Correlated decoding of logical algorithms with transver-
DGE1745303) and The Fannie and John Hertz Founda- sal gates, arXiv preprint arXiv:2403.03272 (2024).
[16] C. Gidney and M. Ekerå, How to factor 2048 bit RSA
tion. This research was developed with funding from the
integers in 8 hours using 20 million noisy qubits, Quan-
Defense Advanced Research Projects Agency (DARPA). tum 5, 1 (2019).
The views, opinions, and/or findings expressed are those [17] The notation g(x) = Θ(f (x)) indicates that two func-
of the author(s) and should not be interpreted as repre- tions f (x) and g(x) have the same asymptotic scaling
senting the official views or policies of the Department of with x, or more precisely, that there exists some con-
Defense or the U.S. Government. stants c1 and c2 such that c1 f (x) ≤ g(x) ≤ c2 f (x) for
 7

sufficiently large x. [35] C. Ryan-Anderson, N. C. Brown, M. S. Allman,

[18] A. G. Fowler and C. Gidney, Low overhead quan- B. Arkin, G. Asa-Attuah, C. Baldwin, J. Berg, J. G.
tum computation using lattice surgery, arXiv preprint Bohnet, S. Braxton, N. Burdick, J. P. Campora,
arXiv:1808.06709 10.48550/arxiv.1808.06709 (2018). A. Chernoguzov, J. Esposito, B. Evans, D. Francois,
[19] L. Z. Cohen, I. H. Kim, S. D. Bartlett, and B. J. J. P. Gaebler, T. M. Gatterman, J. Gerber, K. Gilmore,
Brown, Low-overhead fault-tolerant quantum comput- D. Gresh, A. Hall, A. Hankin, J. Hostetter, D. Luc-
ing using long-range connectivity, Science Advances 8, chetti, K. Mayer, J. Myers, B. Neyenhuis, J. Santi-
10.1126/sciadv.abn1717 (2022). ago, J. Sedlacek, T. Skripka, A. Slattery, R. P. Stutz,
[20] Q. Xu, J. P. Bonilla Ataides, C. A. Pattison, N. Raveen- J. Tait, R. Tobey, G. Vittorini, J. Walker, and D. Hayes,
dran, D. Bluvstein, J. Wurtz, B. Vasić, M. D. Lukin, Implementing Fault-tolerant Entangling Gates on the
L. Jiang, and H. Zhou, Constant-overhead fault-tolerant Five-qubit Code and the Color Code, arXiv preprint
quantum computation with reconfigurable atom arrays, arXiv:2208.01863 10.48550/arxiv.2208.01863 (2022).
Nature Physics 10.1038/s41567-024-02479-z (2024). [36] D. Bluvstein, S. J. Evered, A. A. Geim, S. H.
[21] H. Yamasaki and M. Koashi, Time-Efficient Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain,
Constant-Space-Overhead Fault-Tolerant Quan- M. Kalinowski, D. Hangleiter, J. P. Bonilla Ataides,
tum Computation, arXiv preprint arXiv:2207.08826 N. Maskara, I. Cong, X. Gao, P. Sales Ro-
10.48550/arxiv.2207.08826 (2022). driguez, T. Karolyshyn, G. Semeghini, M. J. Gullans,
[22] S. Bravyi, A. W. Cross, J. M. Gambetta, D. Maslov, M. Greiner, V. Vuletić, and M. D. Lukin, Logical quan-
P. Rall, and T. J. Yoder, High-threshold and low- tum processor based on reconfigurable atom arrays, Na-
overhead fault-tolerant quantum memory, Nature 627, ture 626, 58 (2024).
778 (2024). [37] A. R. Calderbank and P. W. Shor, Good quantum
[23] M. A. Tremblay, N. Delfosse, and M. E. Beverland, error-correcting codes exist, Physical Review A 54, 1098
Constant-Overhead Quantum Error Correction with (1996).
Thin Planar Connectivity, Physical Review Letters 129, [38] N. Delfosse and A. Paetznick, Spacetime codes of Clif-
050504 (2022). ford circuits, arXiv preprint arXiv:2304.05943 (2023).
[24] O. Higgott and N. P. Breuckmann, Constructions and [39] C. Gidney, Stim: a fast stabilizer circuit simulator,
performance of hyperbolic and semi-hyperbolic Floquet Quantum 5, 10.22331/q-2021-07-06-497 (2021).
codes, arXiv preprint arXiv:2308.03750 (2023). [40] D. Gottesman, Opportunities and Challenges in
[25] H. Bombı́n, Single-shot fault-tolerant quantum error Fault-Tolerant Quantum Computation, arXiv preprint
correction, Physical Review X 5, 031043 (2015). arXiv:2210.15844 10.48550/arxiv.2210.15844 (2022).
[26] E. T. Campbell, A theory of single-shot error correction [41] See Supplemental Material for more details.
for adversarial noise, Quantum Science and Technology [42] Z. Cai, A. Siegel, and S. Benjamin, Looped Pipelines
4, 025006 (2019). Enabling Effective 3D Qubit Lattices in a Strictly 2D
[27] O. Fawzi, A. Grospellier, and A. Leverrier, Constant Device, PRX Quantum 4, 020345 (2023).
overhead quantum fault-tolerance with quantum ex- [43] C. Duckering, J. M. Baker, D. I. Schuster, and F. T.
pander codes, Proceedings - Annual IEEE Symposium Chong, Virtualized Logical Qubits: A 2.5D Architecture
on Foundations of Computer Science, FOCS 2018- for Error-Corrected Quantum Computing, Proceedings
Octob, 743 (2018). of the Annual International Symposium on Microarchi-
[28] A. Kubica and M. Vasmer, Single-shot quantum error tecture, MICRO 2020-Octob, 173 (2020).
correction with the three-dimensional subsystem toric [44] Y. Li, A magic state’s fidelity can be superior to the
code, Nature Communications 2022 13:1 13, 1 (2022). operations that created it, New Journal of Physics 17,
[29] S. Gu, E. Tang, L. Caha, S. H. Choe, Z. He, and A. Ku- 023037 (2015).
bica, Single-shot decoding of good quantum LDPC [45] L. Lao and B. Criger, Magic state injection on the ro-
codes, arXiv preprint arXiv:2306.12470 (2023). tated surface code, ACM International Conference Pro-
[30] M. E. Beverland, A. Kubica, and K. M. Svore, Cost of ceeding Series , 113 (2022).
Universality: A Comparative Study of the Overhead of [46] C. Gidney, Cleaner magic states with hook injection,
State Distillation and Code Switching with Color Codes, arXiv preprint arXiv:2302.12292 (2023).
PRX Quantum 2, 020341 (2021). [47] D. Litinski, Magic State Distillation: Not as Costly as
[31] D. Aharonov and M. Ben-Or, Fault-Tolerant Quantum You Think, Quantum 3, 205 (2019).
Computation With Constant Error Rate, SIAM Journal [48] C. Gidney and A. G. Fowler, Efficient magic state fac-
on Computing 38, 1207 (1999). tories with a catalyzed |CCZ⟩ to 2|T ⟩ transformation,
[32] C. Wang, J. Harrington, and J. Preskill, Confinement- Quantum 3, 135 (2019).
Higgs transition in a disordered gauge theory and the [49] O. Higgott and N. P. Breuckmann, Improved Single-
accuracy threshold for quantum memory, Annals of Shot Decoding of Higher-Dimensional Hypergraph-
Physics 303, 31 (2003). Product Codes, PRX Quantum 4, 020332 (2023).
[33] S. Bravyi and A. Kitaev, Universal quantum computa- [50] Gurobi Optimization, LLC, Gurobi Optimizer Refer-
tion with ideal Clifford gates and noisy ancillas, Physical ence Manual (2023).
Review A 71, 022316 (2005). [51] Four transversal gates and one SE round require 8
[34] L. Postler, S. Heußen, I. Pogorelov, M. Rispler, T. Feld- CNOT gates in total, compared to 16d + 4 with d SE
ker, M. Meth, C. D. Marciniak, R. Stricker, M. Ring- rounds.
bauer, R. Blatt, P. Schindler, M. Müller, and T. Monz, [52] I. H. Kim, Y. H. Liu, S. Pallister, W. Pol, S. Roberts,
Demonstration of fault-tolerant universal quantum gate and E. Lee, Fault-tolerant resource estimate for quan-
operations, Nature 605, 675 (2022). tum chemical simulations: Case study on Li-ion bat-
tery electrolyte molecules, Physical Review Research 4,
 8

023019 (2022). 10.48550/arxiv.2303.04846 (2023).

[53] B. M. Terhal, Quantum error correction for quantum [72] O. Higgott, T. C. Bohdanowicz, A. Kubica, S. T. Flam-
memories, Reviews of Modern Physics 87, 307 (2015). mia, and E. T. Campbell, Improved Decoding of Circuit
[54] N. P. Breuckmann and J. N. Eberhardt, Quantum Noise and Fragile Boundaries of Tailored Surface Codes,
Low-Density Parity-Check Codes, PRX Quantum 2, Physical Review X 13, 031007 (2023).
10.1103/prxquantum.2.040101 (2021). [73] A. J. Landahl, J. T. Anderson, and P. R. Rice, Fault-
[55] J. P. Tillich and G. Zemor, Quantum LDPC codes with tolerant quantum computing with color codes, arXiv
positive rate and minimum distance proportional to the preprint arXiv:1108.5738 (2011).
square root of the blocklength, IEEE Transactions on [74] S. Bravyi and A. Cross, Doubled Color Codes, arXiv
Information Theory 60, 1193 (2014). preprint arXiv:1509.03239 10.48550/arxiv.1509.03239
[56] P. Panteleev and G. Kalachev, Asymptotically good (2015).
Quantum and locally testable classical LDPC codes, [75] D. Bacon, S. T. Flammia, A. W. Harrow, and J. Shi,
Proceedings of the Annual ACM Symposium on The- Sparse Quantum Codes from Quantum Circuits, Pro-
ory of Computing , 375 (2022). ceedings of the forty-seventh annual ACM symposium
[57] H. Bombı́n, Gauge color codes: optimal transversal on Theory of Computing , 327 (2014).
gates and gauge fixing in topological stabilizer codes, [76] P. Aliferis, D. Gottesman, and J. Preskill, Accuracy
New Journal of Physics 17, 083002 (2015). threshold for postselected quantum computation, Quan-
[58] A. Kubica, B. Yoshida, and F. Pastawski, Unfolding the tum Information and Computation 8, 181 (2007).
color code, New Journal of Physics 17, 083026 (2015). [77] A. A. Kovalev and L. P. Pryadko, Fault tolerance of
[59] M. Vasmer and D. E. Browne, Three-dimensional sur- quantum low-density parity check codes with sublinear
face codes: Transversal gates and fault-tolerant archi- distance scaling, Physical Review A - Atomic, Molecu-
tectures, Physical Review A 100, 012312 (2019). lar, and Optical Physics 87, 020304 (2013).
[60] B. J. Brown, A fault-tolerant non-Clifford gate for the [78] S. Bravyi, G. Smith, and J. A. Smolin, Trading classical
surface code in two dimensions, Science Advances 6, and quantum computational resources, Physical Review
4929 (2020). X 6, 021043 (2016).
[61] H. Bombin, Transversal gates and error propagation in [79] M. Yoganathan, R. Jozsa, and S. Strelchuk, Quan-
3D topological codes, arXiv preprint arXiv:1810.09575 tum advantage of unitary Clifford circuits with magic
(2018). state inputs, Proceedings of the Royal Society A:
[62] G. Zhu, S. Sikander, E. Portnoy, A. W. Cross, and B. J. Mathematical, Physical and Engineering Sciences 475,
Brown, Non-Clifford and parallelizable fault-tolerant 10.1098/rspa.2018.0427 (2018).
logical gates on constant and almost-constant rate ho- [80] C. Gidney, Halving the cost of quantum addition, Quan-
mological quantum LDPC codes via higher symmetries, tum 2, 74 (2018).
arXiv preprint arXiv:2310.16982 (2023). [81] S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P.
[63] M. A. Nielsen and I. L. Chuang, Quantum Computation Moulton, A new quantum ripple-carry addition circuit,
and Quantum Information: 10th Anniversary Edition arXiv preprint arXiv:quant-ph/0410184 (2004).
(Cambridge University Press, 2010) p. 676. [82] R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. Mc-
[64] C. A. Pattison, A. Krishna, and J. Preskill, Hierar- Clean, A. Paler, A. Fowler, and H. Neven, Encod-
chical memories: Simulating quantum LDPC codes ing Electronic Spectra in Quantum Circuits with Lin-
with local gates, arXiv preprint arXiv:2303.04798 ear T Complexity, Physical Review X 8, 10.1103/phys-
10.48550/arxiv.2303.04798 (2023). revx.8.041015 (2018).
[65] S. Bravyi, D. Gosset, R. König, and M. Tomamichel, [83] A. G. Fowler, Time-optimal quantum com-
Quantum advantage with noisy shallow circuits, Nature putation, arXiv preprint arXiv:1210.4626
Physics 2020 16:10 16, 1040 (2020). 10.48550/arxiv.1210.4626 (2012).
[66] B. Eastin and E. Knill, Restrictions on Transversal En- [84] E. Knill, Quantum Computing with Very Noisy Devices,
coded Quantum Gate Sets, Physical Review Letters Nature 434, 39 (2004).
102, 110502 (2009). [85] C. Gidney and A. G. Fowler, Flexible layout of sur-
[67] T. Jochym-O’Connor, A. Kubica, and T. J. Yoder, Dis- face code computations using AutoCCZ states, arXiv
jointness of Stabilizer Codes and Limitations on Fault- preprint arXiv:1905.08916 10.48550/arxiv.1905.08916
Tolerant Logical Gates, Physical Review X 8, 021047 (2019).
(2018). [86] S. Bravyi and J. Haah, Magic-state distillation with low
[68] J. E. Moussa, Transversal Clifford gates on folded overhead, Physical Review A - Atomic, Molecular, and
surface codes, Physical Review A 94, 10.1103/phys- Optical Physics 86, 052329 (2012).
reva.94.042316 (2016). [87] R. Acharya, I. Aleiner, R. Allen, T. I. Andersen,
[69] N. P. Breuckmann and S. Burton, Fold-Transversal M. Ansmann, F. Arute, K. Arya, A. Asfaw, J. Ata-
Clifford Gates for Quantum Codes, arXiv preprint laya, R. Babbush, D. Bacon, J. C. Bardin, J. Basso,
arXiv:2202.06647 (2022). A. Bengtsson, S. Boixo, G. Bortoli, A. Bourassa, J. Bo-
[70] A. O. Quintavalle, P. Webster, and M. Vasmer, Par- vaird, L. Brill, M. Broughton, B. B. Buckley, D. A.
titioning qubits in hypergraph product codes to im- Buell, T. Burger, B. Burkett, N. Bushnell, Y. Chen,
plement logical gates, arXiv preprint arXiv:2204.10812 Z. Chen, B. Chiaro, J. Cogan, R. Collins, P. Conner,
(2022). W. Courtney, A. L. Crook, B. Curtin, D. M. Debroy,
[71] H. Bombı́n, C. Dawson, Y.-H. Liu, N. Nicker- A. D. T. Barba, S. Demura, A. Dunsworth, D. Ep-
son, F. Pastawski, and S. Roberts, Modular de- pens, C. Erickson, L. Faoro, E. Farhi, R. Fatemi, L. F.
coding: parallelizable real-time decoding for quan- Burgos, E. Forati, A. G. Fowler, B. Foxen, W. Gi-
tum computers, arXiv preprint arXiv:2303.04846 ang, C. Gidney, D. Gilboa, M. Giustina, A. G. Dau,
 9

J. A. Gross, S. Habegger, M. C. Hamilton, M. P. computation, Ph.D. thesis, Sorbonne Université (2019).

Harrigan, S. D. Harrington, O. Higgott, J. Hilton, [99] X. Tan, F. Zhang, R. Chao, Y. Shi, and J. Chen,
M. Hoffmann, S. Hong, T. Huang, A. Huff, W. J. Hug- Scalable surface code decoders with paralleliza-
gins, L. B. Ioffe, S. V. Isakov, J. Iveland, E. Jeffrey, tion in time, arXiv preprint arXiv:2209.09219
Z. Jiang, C. Jones, P. Juhas, D. Kafri, K. Kechedzhi, 10.48550/arxiv.2209.09219 (2022).
J. Kelly, T. Khattar, M. Khezri, M. Kieferová, S. Kim, [100] L. Skoric, D. E. Browne, K. M. Barnes, N. I. Gillespie,
A. Kitaev, P. V. Klimov, A. R. Klots, A. N. Ko- and E. T. Campbell, Parallel window decoding enables
rotkov, F. Kostritsa, J. M. Kreikebaum, D. Landhuis, scalable fault tolerant quantum computation, arXiv
P. Laptev, K.-M. Lau, L. Laws, J. Lee, K. Lee, B. J. preprint arXiv:2209.08552 10.48550/arxiv.2209.08552
Lester, A. Lill, W. Liu, A. Locharla, E. Lucero, F. D. (2022).
Malone, J. Marshall, O. Martin, J. R. McClean, T. Mc- [101] D. Bluvstein, H. Levine, G. Semeghini, T. T. Wang,
court, M. McEwen, A. Megrant, B. M. Costa, X. Mi, S. Ebadi, M. Kalinowski, A. Keesling, N. Maskara,
K. C. Miao, M. Mohseni, S. Montazeri, A. Morvan, H. Pichler, M. Greiner, V. Vuletić, and M. D. Lukin,
E. Mount, W. Mruczkiewicz, O. Naaman, M. Neeley, A quantum processor based on coherent transport of
C. Neill, A. Nersisyan, H. Neven, M. Newman, J. H. entangled atom arrays, Nature 2022 604:7906 604, 451
Ng, A. Nguyen, M. Nguyen, M. Y. Niu, T. E. O’Brien, (2022).
A. Opremcak, J. Platt, A. Petukhov, R. Potter, L. P. [102] J. M. Pino, J. M. Dreiling, C. Figgatt, J. P. Gaebler,
Pryadko, C. Quintana, P. Roushan, N. C. Rubin, S. A. Moses, M. S. Allman, C. H. Baldwin, M. Foss-Feig,
N. Saei, D. Sank, K. Sankaragomathi, K. J. Satzinger, D. Hayes, K. Mayer, C. Ryan-Anderson, and B. Neyen-
H. F. Schurkus, C. Schuster, M. J. Shearn, A. Shorter, huis, Demonstration of the trapped-ion quantum CCD
V. Shvarts, J. Skruzny, V. Smelyanskiy, W. C. Smith, computer architecture, Nature 2021 592:7853 592, 209
G. Sterling, D. Strain, M. Szalay, A. Torres, G. Vidal, (2021).
B. Villalonga, C. V. Heidweiller, T. White, C. Xing, [103] S. Bartolucci, P. Birchall, D. Bonneau, H. Ca-
Z. J. Yao, P. Yeh, J. Yoo, G. Young, A. Zalcman, ble, M. Gimeno-Segovia, K. Kieling, N. Nickerson,
Y. Zhang, and N. Zhu, Suppressing quantum errors T. Rudolph, and C. Sparrow, Switch networks for pho-
by scaling a surface code logical qubit, arXiv preprint tonic fusion-based quantum computing, arXiv preprint
arXiv:2207.06431 10.48550/arxiv.2207.06431 (2022). arXiv:2109.13760 (2021).
[88] J. R. Wootton and D. Loss, High threshold error correc-
tion for the surface code, Physical Review Letters 109,
10.1103/PhysRevLett.109.160503 (2012).
[89] A. G. Fowler, Optimal complexity correction of cor-
related errors in the surface code, arXiv preprint
arXiv:1310.0863 (2013).
[90] N. Delfosse, V. Londe, and M. E. Beverland, Toward a
Union-Find Decoder for Quantum LDPC Codes, IEEE
Transactions on Information Theory 68, 3187 (2022).
[91] P. Panteleev and G. Kalachev, Degenerate Quantum
LDPC Codes With Good Finite Length Performance,
Quantum 5, 585 (2019).
[92] Y. Wu, L. Zhong, and S. Puri, Hypergraph Minimum-
Weight Parity Factor Decoder for QEC, in Bulletin of
the American Physical Society (American Physical So-
ciety, 2024).
[93] H. Bombı́n, Gauge Color Codes: Optimal Transver-
sal Gates and Gauge Fixing in Topological
Stabilizer Codes, New Journal of Physics 17,
10.48550/arxiv.1311.0879 (2013).
[94] N. Liyanage, Y. Wu, A. Deters, and L. Zhong, Scal-
able Quantum Error Correction for Surface Codes using
FPGA, Proceedings - 31st IEEE International Sympo-
sium on Field-Programmable Custom Computing Ma-
chines, FCCM 2023 , 217 (2023).
[95] T. Richardson and R. Urbanke, Modern coding theory
(Cambridge University Press, 2008).
[96] A. G. Fowler, Minimum weight perfect matching of
fault-tolerant topological quantum error correction in
average O(1) parallel time, Quantum Information and
Computation 15, 145 (2015).
[97] Y. Wu and L. Zhong, Fusion Blossom: Fast MWPM
Decoders for QEC, in Proceedings - 2023 IEEE Inter-
national Conference on Quantum Computing and Engi-
neering, QCE 2023 , Vol. 1 (2023) pp. 928–938.
[98] A. Grospellier, Constant time decoding of quantum ex-
pander codes and application to fault-tolerant quantum
 10

METHODS number of logical measurements performed throughout

C as M . The output of each execution of C is a bit
Background Concepts string ⃗bC ∈ ZM2 , sampled from a probability distribution
fC . This probability distribution fully characterizes the
output of the quantum computation.
In this section, we review some common concepts and
Local stochastic noise model. Our proof assumes
definitions used to establish the fault tolerance of our
the local stochastic noise model that is widely used in
scheme. We will focus on a high-level description here,
fault-tolerance analysis, see for example Ref. [5]. This
and defer the formal definitions to the supplementary in-
noise model allows for noise correlations, but requires
formation. Experienced QEC researchers may wish to
that the probability of any set of s errors is upper-
skip ahead to the key concepts section, where we dis-
bounded by ps , where p is a parameter characterizing
cuss a number of less commonly used concepts that are
the noise strength. We will use the local stochastic noise
key to our results.
model in Ref. [5, 20], where the noise is applied to data
We start by reviewing the ideal circuits we aim to per- qubits and the output syndrome bit. A basis of the errors
form, based on Clifford operations and magic state tele- is denoted as E and its size scales with the space-time vol-
portation. We then describe how to turn this into an ume of the circuit. For a QLDPC code (see below) and
error-corrected circuit. First, we define the local stochas- syndrome extraction circuit with bounded depth, this can
tic noise model that our proof assumes, which covers a be readily generalized to show a circuit-level threshold
wide range of realistic scenarios. We then describe the by using the fact that error propagation is bounded in a
quantum LDPC codes that we use to perform quantum constant depth circuit [5, 64, 65].
error correction and how to perform transversal logical Quantum LDPC Code. An [[n, k, d]] stabilizer
operations on them. A noisy transversal realization of quantum code Q is an (r, c)-LDPC (low-density parity
the ideal circuit is thus obtained by replacing each ideal check) code if each stabilizer generator has weight ≤ r
operation by the corresponding transversal gate, followed and each data qubit is involved in at most c stabilizer
by a single SE round. The error-corrected realization also generators. Here, n denotes the number of phyiscal data
determines how errors trigger syndromes, which is cap- qubits, k the number of encoded logical qubits, and d the
tured in the detector error model (decoding hypergraph). code distance. Here and below, we will use an overline to
Using the detector error model and observed syndromes, indicate logical operations and logical states, e.g. U and
we can infer a recovery operator which attempts to cor- |0⟩. Due to the random initial stabilizer projection, we
rect the actual errors.
also use the separate double-bar notation |0⟩ to denote
Together, these concepts establish the basic procedures the ideal logical code state with all stabilizers fixed to
that are typically used for quantum error correction and +1.
conventional FT analysis. However, in order to estab- A widely-used family of quantum LDPC codes is the
lish fault tolerance for our algorithmic FT protocol, we surface code, due to its 2D planar layout and high thresh-
need to introduce the additional notion of frame vari- old. The surface code, together with its X and Z stabiliz-
ables, which capture the randomness of initial stabilizer ers and logical operators, are illustrated in ED Fig. 1(a).
projections during state preparation, and we discuss how Transversal operations. Consider a fixed partition
to interpret logical measurement results in the presence of a code block, where each part contains at most t qubits.
of such degrees of freedom in the next section. We call a physical implementation U of a logical opera-
Ideal circuit C. We consider ideal circuits C in a tion U transversal with respect to this partition, if it
model of quantum computation consisting of Clifford op- exclusively couples qubits within the same part [66, 67].
erations and magic state inputs. C includes state prepa- We will also restrict our attention to the case where the
ration and measurement in the computational basis for logical operation, excluding SE rounds, has depth 1, mo-
any qubit, single-qubit I, Z, H, S gates, CN OT gates tivated by the fact that the elementary gates in the ideal
between any pair of qubits. This allows the implemen- circuit C have depth 1. We consider the same, fixed
tation of any Clifford unitary. C can also include condi- partition for all logical qubits throughout the algorithm.
tional operations of the above types, conditioned on pre- This definition includes common transversal gates such as
vious measurement results. Finally, C can also include CN OT on CSS codes, for the partition where each phys-
non-Clifford magic state inputs of the form |T ⟩ = T |+⟩ ical qubit is an individual part. For the surface code, we
inputs, where the T gate is a π/4 rotation around the Z can choose a partition of size at most two, which pairs to-
axis. This set of operations is known to be universal for gether qubits connected by a reflection. Common Clifford
quantum computation [63]. We require that all qubits operations are transversal with respect to this partition,
are measured by the end of the circuit. see ED Fig. 1(c-d): H can be implemented via a physical
Measurement distribution fC of ideal circuit C. H on each qubit, followed by a code patch reflection in a
Ultimately, we are only interested in the classical results single step. The S gate can be implemented via CZ on
that our quantum computation returns. Denote the total pairs of qubits connected by a reflection and S/S † along
 11

a ford gates, and non-Clifford gates are implemented via

magic state teleportation. The number of syndrome ex-
traction rounds can be further optimized in practice [15].
We denote the noiseless version of this circuit as C˜0 , and
the circuit with a given error realization e from the local
stochastic noise model as C˜e .
The surface code provides a concrete example of a code
that admits a transversal implementation of all transver-
sal Clifford operations mentioned above. Although we
use the surface code as a concrete instance that realizes
b c all required transversal gates, the transversal algorithmic
FT construction we propose works more generally. For a
specific quantum circuit, it may be possible to compile it
into, e.g. transversal CNOTs and fold-transversal gates
for multiple copies of other QLDPC codes [69, 70], where
our results also apply.
When considering magic state inputs, we assume that
the magic state is initialized in the desired state with all
stabilizer values fixed to +1, up to local stochastic noise
on each physical qubit of strength p. However, we also
generalize this in Theorem 3 below to the case where the
magic state input is at a smaller code distance, and show
Extended Data Fig. 1. (a) Illustration of the surface code. FT of single step patch growth, closely mirroring the sit-
White circles indicate data qubits. Orange (green) plaquettes
are Z (X) stabilizers. The logical Z (X) operator runs verti-
uation in practical multi-level magic state distillation fac-
cally (horizontally), and we choose our convention for fixing tories [47, 48]. Since magic states for the surface code are
Z (X) stabilizers to be performing a chain of X (Z) flips to typically prepared using magic state distillation, we ex-
the left (bottom) boundary, as illustrated by the red line. (b) pect that our methods allow single-shot logical operations
Illustration of transversal H gate, consisting of transversal H during these procedures as well, which consist of Clifford
gates followed by a reflection along the diagonal. Note that operations and noisy magic state inputs (see the follow-
this differs from the usual transversal H gate, which applies a ing section on State Distillation Factories). Therefore,
rotation in the second step. For the non-rotated surface code,
both choices map X (Z) stabilizers to Z (X) stabilizers and
compared to standard techniques such as lattice surgery,
hence are valid, but our choice leads to a smaller transversal we expect the transversal realization C to have a time
partition size for the full circuit. (c) Illustration of transver- cost that is a factor of Θ(d) smaller.
sal S gate, consisting of S and S † gates along the diagonal, Detector error model. To diagnose errors, we form
together with CZ gates between mirrored qubits. detectors (also known as checks), which are products of
stabilizer measurement outcomes that are deterministic
in the absence of errors. A basis of detectors is denoted
the diagonal [58, 68–70]. We also refer to the following as D. We denote the set of detectors that a given error
state preparation and measurement in the computational triggers as ∂e, which can be efficiently inferred [39]. In
basis as transversal, where |0⟩ state preparation involves other words, we have a linear map
preparing all physical qubits in |0⟩ and measuring all sta-
bilizers once, while measurement involves measuring all |E| |D|
∂ : Z2 → Z2 . (2)
physical qubits in the Z basis. Note that the |0⟩ state
preparation procedure does not prepare the actual code The error model, together with the pattern of detectors
state, but rather an equivalent version with random X a given set of errors triggers, forms a decoding hyper-
stabilizers, where information regarding the random sta- graph Γ, also known as a detector error model, see e.g.
bilizer initialization can be deduced later. Ref. [15, 38, 39, 71, 72]. The vertices of this graph are
Transversal realization C˜ of ideal circuit C. If the detectors, hyperedges are elementary errors, and a hyper-
set of operations involved in the ideal circuit (other than edge is connected to the detectors that the correspond-
magic state preparation, see below) admit a transver- ing error triggers. During a given execution of the noisy
sal implementation with the QEC code Q, then we can circuit, there will be some pattern of errors e that oc-
obtain a transversal error-corrected realization C˜ of the cur, giving some detection event ∂e. Since the circuit
ideal circuit C. C˜ is obtained from C by replacing each is adaptive based on past measurement results, the de-
operation by the corresponding transversal operation and tector error model must also be constructed adaptively
inserting only one round of syndrome extraction following to incorporate the conditional feed-forward operations.
each gate. Here, all transversal gate operations are Clif- More specifically, the decoding hypergraph Γ|j for the
 12

jth logical measurement in a given run is constructed af- variable, which allows us to ensure consistency between
ter committing to the previous j − 1 logical measurement multiple rounds of decoding. These understandings lead
results, and similarly for other objects. us to propose the decoding strategy shown in Fig. 2, and
To analyze error clusters, we also introduce the related will be crucial to our FT proofs below.
notion of the syndrome adjacency graph Ξ [5]. In this Frame variables g. When performing transversal
hypergraph, vertices are elementary fault locations, and state initialization, all physical qubits are prepared in
hyperedges are detectors connecting the fault locations |0⟩, and stabilizers are measured with an ancilla. The
they flip. outcome of the X stabilizers will thus be random. Fol-
Inferred recovery operator κ. Given the detection lowing the approach taken in Ref. [39], this randomness
events and the detector error model, we can perform de- can be captured by additional Z operators acting at ini-
|E| tialization. Concretely, for each data qubit i, we add Zi
coding to identify a recovery operator κ ∈ Z2 which trig-
gers the same detector pattern ∂κ = ∂e. Our proof makes to a basis of frame operators G if it is not equivalent to
use of the most-likely-error (MLE) decoder [15, 73, 74], any combination of operators in G up to stabilizers. The
which returns the most probable error event κ with the state after random stabilizer projection is equivalent to
same detector pattern ∂κ = ∂e. We will refer to the com- starting with the ideal code state |0⟩ and applying a set
bination f = e ⊕ κ as the “fault configuration”, where ⊕ of Z operators; in other words, |0⟩ = g|0⟩. We refer to
denotes addition modulo 2. By linearity, the fault con- these operators as frame operators, as they describe the
figuration e ⊕ κ will not trigger any detectors, effective code space (“reference frame”) with random sta-
bilizers that we projected into, and help interpret logical
∂(e ⊕ κ) = 0. (3) measurement results. The set of Z operators that pro-
duces a given pattern of initial stabilizer values can be
Forward-propagated error P (e). A Pauli error E efficiently determined by solving a linear system of equa-
occurring before a unitary U is equivalent to an error tions. We choose a basis G for these operators, as defined
U EU † occurring after the unitary. For a set of errors e, above, and denote with g both the Pauli operator corre-
we can forward-propagate it through the circuit until it sponding to a frame variable as well as the binary vector
reaches measurements. We denote the final operator the describing it:
errors transform into as P (e), and denote its restriction
|G|
onto the jth logical measurement as P (e)|j . This is re- g ∈ Z2 , |G| = B(n − rZ ), (4)
lated to the cumulant defined in Ref. [38] and the spackle
operator in Ref. [75]. where B is the number of code blocks used, n is the num-
ber of data qubits per block and rZ is the number of in-
dependent Z stabilizer generators per block. In the pres-
Key Concepts ence of noise, we can imagine first performing the ran-
dom stabilizer projection perfectly, and then performing
We now introduce a few concepts that are less com- a noisy measurement of the syndromes via ancillae and
monly discussed in the literature, but are important for recording the results. Although this does not allow the
our analysis. We start by describing the randomness as- reliable inference of frame variables, we will show that the
sociated with transversal state initialization and stabi- transversal measurement provides enough information to
lizer projections. To do so, we introduce frame variables infer the relevant degrees of freedom for interpreting log-
g. To capture the random reference frame corresponding ical measurement results.
to random initialization of stabilizer values upon projec- Frame logical variables gl . A special subset of frame
tion, we introduce frame stabilizer variables gs . These variables are frame logical variables
correspond to certain Pauli Z operators that flip a sub- gl ∈ ZBk
2 , (5)
set of X stabilizers, and we call both these operators and
the binary vector that describes them as frame variables, which are combinations of the Z operators that form a
where the meaning should be clear from context. The logical Z operator of the code block, and therefore act
Pauli logical initial state, e.g. |0⟩, also has a logical sta- trivially on the code state |0⟩. Here, B is the number
bilizer Z, which we describe with frame logical variables of code blocks and k is the number of logical qubits per
gl . Applying frame logical variables on the initial state block. While they do not change the initialized physical
does not change the logical state, since we are applying state, nor do they flip any stabilizers, different choices
a logical stabilizer, but this does change the interpreta- of the frame logical variables when decoding will lead
tion of a given logical measurement shot. To interpret to different interpretations of the logical measurement
logical measurement results, we must perform a frame result, as we explain next.
repair operation that returns all stabilizers to +1, mir- Frame stabilizer variables gs . We refer to frame
roring the error recovery inference. However, there can variables that are not frame logical variables as frame sta-
be some degree of freedom in choosing the frame logical bilizer variables. These variables will flip the randomly
 13

a Errors and frame flips b Error Recovery c Frame repair d Frame logical flip

2
3

Time Time Time Time

Extended Data Fig. 2. Illustration of error recovery and frame repair procedures. We illustrate the procedure for
the surface code, where a cross-sectional view with one spatial axis and one time axis is shown. We only illustrate X errors
and Z stabilizer measurement errors, which are relevant to interpreting the Z measurement. X errors can terminate on orange
boundaries, but cannot terminate on cyan boundaries. The transversal CN OT copies X errors from the top to the bottom,
resulting in a branching point (black cross) and an error cluster spanning both code blocks. (a) Error chains and frame flips.
Chains of X-type errors (orange lines) lead to syndromes (end points) or terminate on appropriate boundaries. A line segment
in the vertical direction is a data qubit X error, while a line segment in the horizontal direction is a measurement error. Note
that the X-type error cannot terminate on the transversal Z measurement boundary. The random stabilizer initialization leads
to a frame configuration on the logical |+⟩ initialization, as illustrated by the blue line and the flipped Z stabilizer (blue point).
This is similar to the frame stabilizer operator gs illustrated in ED Fig. 1(a). (b) We first infer an error recovery operator, which
has the same boundary as the error chain. Together, the error and recovery operator form the fault configuration, which triggers
no detectors. We illustrate a few examples (orange lines) that do not lead to a logical error: (1) the fault configuration forms a
closed loop and is equivalent to applying a stabilizer; (2) the fault configuration terminates on an initialization boundary; (3)
the fault configuration terminates on a future time boundary (unmeasured logical qubit), but the forward-propagated errors
onto the measured logical qubit are equivalent to a stabilizer. A logical error can only happen when the fault configuration spans
across two opposing spatial boundaries (red line), which requires an error of weight Θ(d). (c,d) The frame repair operation
returns the logical qubit to the code space with all stabilizers +1, corresponding to cancelling any residual flipped stabilizers
on the initialization boundary. Note that the error recovery process may also lead to a change that needs to be accounted
for by frame repair. An example choice of frame repair is shown in (c), which applies an overall X operator on the logical
measurement result. Alternatively, a different choice of frame repair shown in (d), related to the previous one by a frame logical
flip, results in identity operation on the logical measurement result.

initialized stabilizer values. An example is shown in ED during initialization, and the repair operation should be
Fig. 1(a), in which a chain of Z errors connecting to the viewed as being applied on the corresponding initial-
bottom boundary flips a single stabilizer. ization boundary as well. In other words, we require
Interpreting logical measurement outcomes in (e ⊕ κ) ⊕ (g ⊕ λ) to act as a stabilizer or logical opera-
the presence of frame variables. We now describe tor, such that the stabilizer values are the same as the
how to interpret logical measurement results in the pres- ideal code state |0⟩. We will refer to the combination
ence of randomly initialized frame variables. h = g ⊕ λ as the “frame configuration”. Following this
First, in the presence of noise, we apply the decoding step, all frame stabilizer variables gs have been deter-
procedure and obtain an error recovery operator κ such mined, but we still have freedom to choose our frame
that ∂(κ ⊕ e) = 0. Note that κ ⊕ e may have some non- logical variables gl .
trivial projection onto the initialization boundary, such Finally, we evaluate the product of Pauli operators to
as string 2 that terminates on the |+⟩ boundary in ED determine the logical measurement result. Denote the
Fig. 2(b). This projection can modify the effective frame, raw logical observable inferred from the bit strings as
and must be taken into account when returning things to M
the code space. L(z) = zi , (7)
Next, we perform an analogous procedure to error re- zi ∈L

covery for the frame variables. Specifically, we perform and the corrected logical observable after applying the
a frame repair operation error recovery operation κ and frame repair operation λ
|G| as
λ ∈ Z2 (6)
Lc (z, κ, λ) = L(z) ⊕ F (κ) ⊕ F (λ), (8)
to return to the code space with all stabilizers set to
+1. This corresponds to an inference of what the ref- where F (κ), F (λ) indicates the parity flip of the logical
erence frame was after the random stabilizer projection observable due to the operator κ, λ.
 14

In the noiseless case, the raw logical measurement re- 2. We obtain perfect syndrome information on the log-
sult is equivalent to the ideal measurement result that ical qubits via transversal measurements, which we
one would obtain if one had perfectly prepared the ideal then combine with correlated decoding to handle
code state |0⟩, up to the application of F (g ⊕ λ) on the errors throughout the circuit and guarantee that
initial state. However, g ⊕ λ consists of physical Z oper- any logical error must be caused by a high-weight
ations only and commutes with all stabilizers, so it must physical error cluster.
act as a combination of Z stabilizers and logical Z opera-
3. By counting the number of such high-weight er-
tor on |0⟩. Therefore, it does not change the distribution ror clusters, we show that when the physical er-
of measurement results, although it can change the inter- ror probability is sufficiently low, the growth in
pretation of individual shots. The procedure in the noisy the number of error clusters as the distance in-
case can be reduced to the noiseless case after applying creases is slower than the decay of probability of
the MLE recovery operator κ, with a suitable modifica- high-weight clusters, thereby establishing an error
tion to the repair operation λ to account for fault config- threshold and exponential sub-threshold error sup-
urations that terminate on initialization boundaries and pression.
therefore forward-propagated to flip some stabilizers on
the relevant logical measurement (ED Fig. 2(c)). We now explain a set of useful lemmas that lead to our
Decoding strategy. A key component of our FT main theorem.
construction is the decoding strategy. In our setting with Frame variables g do not affect the logical mea-
transversal Clifford gates only, classical decoding only be- surement distribution. We show that the choice of
comes necessary when we need to interpret logical mea- frame variables g does not affect the logical measure-
surement results. We sort the set of logical measurements ment distribution fC̃ . Intuitively, this is because different
into an ordering {L̄1 , L̄2 , L̄3 , ..., L̄M } based on the time choices of frame variables are equivalent up to the appli-
they occur, and then decode and commit to their results cation of Z̄ logicals on |0⟩, which does not affect the log-
in this order. ical measurement distribution. Indeed, as long as we are
For the jth logical measurement L̄j , we first apply the able to keep track of which subspace of random stabilizer
most-likely-error (MLE) decoder to the available detec- values we are in, achieved via the transversal measure-
tor data D|j and the detector error model Γ|j , where |j ment, the measurement result distribution should not be
denotes that this information is restricted to information affected.
up to the jth logical measurement. Note that since we fC = fC̃0 . In other words, the noiseless transversal
allow feed-forward operations, the decoding hypergraph realization C˜0 produces the same distribution of logical
may differ in each repetition of the circuit (shot). After bit strings as the ideal quantum circuit C. This can be
this first step, we will have obtained an inferred recovery seen from the previous statement by choosing all frame
operator κ, similar to standard decoding approaches. variables to be zero and invoking standard definitions of
The second step is to apply frame logical variables gl logical qubits and operations.
such that previously-committed logical measurement re- Transversal gates limit error propagation. One
sults retain the same measurement result. It may not be major advantage of transversal gates is that they limit
clear a priori that this is always possible, but we prove error propagation [4, 7], thereby limiting the effect any
that below a certain error threshold pth , the probability given physical error event can have on any logical qubit.
of a failure decays to zero exponentially in the code dis- With the bounded cumulative partition size t defined
tance. This guarantees that we are always consistently above, one can readily show that any error e acting on
assigning the same results to the same measurement in at most k qubits can cause at most tk errors on a given
each round of decoding. The assignment of frame logical logical qubit, when propagated to a logical measurement
variables can be solved efficiently using a linear system P (e)|j .
of equations. Effect of low-weight faults on code space. Con-
sider the syndrome adjacency graph Ξ|j , which is the
line graph of the detector error model Γ|j corresponding
Proof Sketch to the first j logical measurements, and any fault con-
figuration f |j = (e ⊕ κ)|j . We show that if the largest
In this section, we provide a sketch of our FT proof, weight of any connected cluster of f |j is less than d/t,
using the concepts introduced above. Our reasoning fol- then there exists a choice of frame repair operator λ̂j ,
lows three main steps: such that the forward propagation of fault configuration
and frame configuration
1. We show that the transversal realization reproduces
the logical measurement result distribution of the P (e|j ⊕ κ|j ) ⊕ P (g|j ⊕ λ̂j ) (9)
ideal circuit, regardless of the reference frame we
initially projected into. acts trivially on the first j logical measurements.
 15

The intuition for this statement is illustrated in ED error yet, as the outcome is still random. In this case,
Fig. 2. Suppose without loss of generality that the logi- it is only when the joint distribution with other logical
cal measurement we are examining is in the Z basis, then measurements is modified that we say a logical error has
we only need to examine errors that forward-propagate to occurred. When analyzing a new measurement result
X errors. By definition, the fault configuration e ⊕ κ and with some previously committed results, we analyze the
frame configuration g⊕λ should return things to the code distribution conditional on these previously committed
space and not trigger any detectors, implying that the results.
X basis component of P (e ⊕ κ ⊕ g ⊕ λ) = P (f ⊕ h) is a Second, there may be a heralded logical error, in which
product of X stabilizers and logical operators. Consider no valid choice of frame repair operation λ exists in the
each connected component fi of f |j , then by transver- second step of our decoding strategy. More specifically,
sality (previous lemma) and wt(fi ) < d/t, we have there is no λ that makes all logical measurement results
wt(P (fi )) < d. identical to their previously-committed values.
Case 1: If fi does not connect to a Pauli initialization
We show that when the largest weight of any con-
boundary (fault configurations 1 and 3 in ED Fig. 2(b)),
nected cluster in the fault configuration is less than d/t,
then it is also a connected component of f ⊕ h, since the
neither type of logical error can occur. The absence of
frame configuration lives on the initialization boundary.
unheralded logical errors can be readily seen from the
Since P (fi ) has weight less than d, it must be a stabilizer
above characterization of the effect of low-weight faults
and therefore acts trivially on the logical measurement
on the code space. To study heralded errors, we make
under consideration.
slight modifications to analyze the consistency of mul-
Note that because magic states are provided with
tiple rounds of decoding, and find that heralded errors
known stabilizer values up to local stochastic noise, con-
require one of the two rounds of decoding that cannot be
nected components of the fault configuration cannot ter-
consistently assigned to have a fault configuration with
minate on them without triggering detectors. The same
weight ≥ d/t, thereby leading to the desired result.
also holds for measurement boundaries or boundaries in
which the initialization stabilizer propagates to commute Counting lemma. The counting lemma is a useful
with the final measurement. Only when the initialization fact that bounds the number of connected clusters of a
stabilizer propagates to anti-commute can we connect to given size within a graph, with many previous uses in
the boundary, as described in case 2, but this also then the QEC context [5, 25, 28, 76, 77]. It shows that for a
implies that the measurement is 50/50 random and can graph with bounded vertex degree v and n vertices, as is
be made consistent using our methods. the case for the syndrome adjacency graph Ξ of qLDPC
Case 2: Now suppose fi connects to an initialization codes, the total number of clusters of size s is at most
boundary (fault configuration 2 in ED Fig. 2(b)) and n(ve)s−1 . This bounds the number of large connected
its connected component P (fi ⊕ hi ) acts as a nontrivial clusters. When the error rate is low enough, the growth
logical operator L, flipping the logical measurement. In of the “entropy” factor associated with the number of
this case, we can choose a different frame repair operator clusters will be slower than the growth of the “energy”
such that P (λ̂) = P (λ)⊕L, which does not flip the logical penalty associated with the probability, and thus the log-
measurement. In ED Fig. 2(c,d), we can intuitively think ical error rate will exponentially decrease as the system
of this as changing whether the frame repair connects in size is increased, allowing us to prove the existence of a
the middle or to the two boundaries. In one of these threshold and exponential sub-threshold suppression.
two cases, the total effect of the fault configuration and Theorem 1: Threshold theorem for transversal
frame configuration is trivial on the logical measurements realization C˜ with any CSS QLDPC code, with re-
of interest (ED Fig. 2(d) in this case). liable magic state inputs and feed-forward. With
Thus, we see that when the fault configuration only the preceding lemmas, we can prove the existence of a
involves connected clusters of limited size, its effect on the threshold under the local stochastic noise model. Us-
logical measurement results is very limited. This leads to ing the counting lemma, we can constrain the number of
a key technical lemma that lower bounds the number of connected clusters Ns of a given size s on the syndrome
faults required for a logical error to occur. adjacency graph Ξ. For a connected cluster of size s,
Logical errors must be composed of at least d/t MLE decoding implies that at least s/2 errors must have
faults. Due to the decoding strategy we employ, there occurred, which has bounded probability scaling as ps/2
are two types of logical errors we must account for. under the local stochastic noise model. Our characteriza-
First, we may have a logical error in the usual sense, tion of logical errors implies that a logical error can only
where the distribution of measurement results differs occur when s ≥ d/t. For each round of logical measure-
from the ideal quantum circuit fC̃ ̸= fC . It is impor- ments, the probability of a logical error is then bounded
tant to note here, however, that this deviation is in the by a geometric series summation over cluster sizes s, with
distribution sense. Thus, if a measurement outcome that an entropy factor from cluster number counting and an
was 50/50 random was flipped, it does not cause a logical energy factor from the exponentially decreasing proba-
 16

bility of each error event: Single-shot code patch growth. To further extend
the applicability of our results, we also analyze a set-
∞
X ting in which reliable magic states are provided at a code
Perr ∝ M Ns 2s ps/2
distance d1 smaller than the full distance d of the main
s= dt
computation. This is relevant, for example, to multi-
 d/2t
√ d/t p stage magic state distillation procedures that are com-
∝ (2ve p) = , (10) monly employed to improve the quality of noisy injected
1/(2ve)2
magic state inputs. Lower levels of magic state distilla-
where v is a bound on the vertex degree of the syndrome tion are typically performed at a reduced code distance,
adjacency graph and is dependent on the degrees r and due to the less stringent error rate requirements, before
c of the QLDPC code. When the error probability p they are grown into larger distance for further distilla-
in the local stochastic noise model is sufficiently small, tion, as is the case in Fig. 4.
the latter factor outweighs the former, and the logical By analyzing which stabilizers are deterministic dur-
error rate decays exponential to zero as the code distance ing the code patch growth process, we find that a strip of
increases, with an exponent pd/2t . We can then take width d1 has deterministic values. A fault configuration
the union bound over rounds of logical measurements to that causes a logical error must span across this region,
bound the total logical error probability. and thus have weight at least d1 . Therefore, in this case
While our theorem assumes reliable magic state inputs we still have fault tolerance and exponential error sup-
with local stochastic data qubit noise only, we expect our pression, but with an effective distance now modified to
results to readily generalize to magic state distillation scale as d1 instead of d, set by the smaller patch size of
factories (see next section and discussion in main text), the magic state input as expected.
thereby enabling a Θ(d) saving for universal quantum
computing.
State Distillation Factories
Note that to prove a threshold theorem for FT simu-
lating the ideal circuit C, we need a family of codes {Q}
with growing size that provide a transversal realization In this section, we provide more details on state distil-
of C. For general high-rate QLDPC codes, this may be lation factories. First, we derive the output fidelity of the
challenging, as the set of transversal gates is highly con- |Y ⟩ state distillation factory described in the main text,
strained [69, 70]. However, we will now show that the as a function of input |Y ⟩ state fidelity and assuming
surface code provides the required code family. ideal Clifford operations within the factory. Second, we
Theorem 2: Fault tolerance for arbitrary Clif- illustrate the 15-to-1 |T ⟩ magic state distillation factory
ford circuits with reliable magic state inputs and and comment on a few simplifications that our decoding
feed-forward, using a transversal realization with strategy enables in executing this factory.
the surface code. We can further specialize the pre- The |Y ⟩ state distillation factory described in the main
ceding results to the case of the surface code. With the text prepares a Bell pair between a single logical qubit
transversal gate implementations of H, S and CN OT , we and seven logical qubits further encoded into the [[7, 1, 3]]
can implement arbitrary Clifford operations with cumu- Steane code. Applying a transversal S gate on the Steane
lative partition size t = 2. Note that with more detailed code then leads to a S gate on the output logical qubit
analysis of the error events and gate design, it may be due to the Bell pair. Error detection on the Steane code
possible to recover the full code distance d (instead of further allows one to distill a higher-fidelity logical state.
the d/2 proven here), which we leave for future work. For this distillation factory, we can directly count the er-
Our threshold and error suppression results are indepen- ror cases for the magic state input that lead to a logical
dent of the circuits implemented, e.g. whether the cir- error, conditional on post-selection results. For example,
cuit has a large depth or width. The resulting logical there are seven logical Z representatives of weight three
error rate scales linearly with the circuit space-time vol- and one logical representative of weight seven, and the
ume and number of logical measurements, and is expo- application of a logical representative leads to an unde-
nentially suppressed in the code distance, similar to the tectable error. Counting all possible combinations, we
usual threshold theorems. arrive at the following formula for noisy magic state in-
A straight-forward application of the previous theo- puts and ideal Clifford operations
rem shows the existence of a threshold and exponential 7Pin3
(1 − Pin )4 + Pin
7

sub-threshold error suppression. Importantly, the surface Pout = 3 (1 − P )4 + 7P 4 (1 − P )3 + P 7

(1 − Pin )7 + 7Pin in in in in
code provides all elementary Clifford operations, thereby 3
≈ 7Pin , (11)
giving a concrete code family for the FT simulation of
any ideal circuit C, as long as we are provided with the where Pout is the output logical error rate and Pin is the
appropriate magic state inputs, which can in turn be ob- input logical error rate. For our numerical simulations,
tained in the same way via magic state distillation. we artificially inject Z errors for the input state.
 17

In ED Fig. 3, we illustrate the 15-to-1 |T ⟩ state distil-  

 †
|+ T
lation factory, which takes 15 noisy |T ⟩ states and distills
Prep
  Patch
a single high quality |T ⟩ state. As described in Ref. [33], T Growth

X
assuming ideal Clifford operations, the rejection proba- |+ S H

bility scales linearly with the input infidelity, while the Prep
 
T
Patch
Growth
output logical error rate scales with the cube of the input
|+ S H
infidelity. The |T ⟩ factory bears a lot of similarities with
Prep
the |S⟩ factory in the main text: In both cases, we start  
T
Patch
Growth

with Pauli basis states, apply parallel layers of CNOT  

0 S H

gates, and then perform resource state teleportation us- Prep

 
T
Patch
Growth
ing a CNOT. The resource states at the lowest level can
|+
be prepared using state injection, which is agnostic to S H

the precise quantum state being injected and therefore Prep

 
T
Patch
Growth

should apply equally to a |S⟩ and |T ⟩ state, while the  

0 S H

resource states at the higher levels are obtained by lower Prep

  Patch
T
levels of the same distillation factory. The main differ-  
Growth

0
ence is that because the feed-forward operation is now a S H

Clifford instead of a Pauli, the feed-forward gate must be Prep

 
T
Patch
Growth

executed in hardware, rather than just kept track of in  

0 S H

software. Prep Patch

 
T Growth

When performing magic state distillation and teleport- |+ S H

ing the magic state into the main computation, the first Prep
  Patch
T
step of our protocol requires correlated decoding of the Growth

 
0
distillation factory and main computation together. It S H

will be interesting to formally extend our threshold anal- Prep

 
T
Patch
Growth

ysis to incorporate noisy magic state injection and state  

0 S H
distillation procedures. As low-weight logical errors are Prep
  Patch
localized around the state injection sites, we expect com- T Growth

 
mon arguments regarding the error scaling of distillation 0 S H

factories to hold, as is also supported by our numerical Prep

 
T
Patch
Growth

results. We leave a detailed proof of this to future work.  

0 S H
In practice, to reduce the decoding cost, one can also in-
Prep
  Patch
sert Θ(d) SE rounds on the single output logical qubit T Growth

 
of the factory, in order to separate the system into mod- 0 S H

ular blocks [71]. Since we only need to insert the Θ(d) Prep
 
T
Patch
Growth
SE rounds on a single logical qubit, while a two-level  
0 S H
distillation factory typically involves hundreds of logical
Prep
qubits [47, 48], we expect that this will only cause a slight  
T
Patch
Growth

increase in the total distillation cost.  

0 S H

Using our decoding strategy, it is possible to reduce

the number of feed-forward operations that need to be Extended Data Fig. 3. Illustration of a 15-to-1 |T ⟩ magic
executed. As illustrated in ED Fig. 3, we can apply an state distillation factory, adapted from Ref. [30]. The green
X operator on the |+⟩ logical initial states, which is a log- lines illustrate the application of a logical stabilizer, which
ical stabilizer of the resulting quantum state. Applying allows re-interpretation of measurement results and changes
which feed-forwards should be performed.
this operator flips the interpreted results of some subset
of logical measurements. Thus, we can always choose to
not apply a feed-forward S on the first |T ⟩ teleportation,
but instead change what feed-forward operations are ap- control parallelism [36].
plied on the remaining |T ⟩ teleportations. There are 15 Finally, we also comment on the relation of our re-
|T ⟩ teleportations to be implemented and 5 |+⟩ logical sults to other computational models that make use of
state initialization locations. Therefore, we expect that magic state inputs and Clifford operations. In particu-
at most 10 feed-forward operations need to be applied. lar, Pauli-based computation [78, 79] has been shown to
Using these techniques, the logical qubit locations where provide a weak simulation of universal quantum circuits
the feed-forward operations need to be applied may also using only magic state inputs, apparently removing the
be adjusted, which may be beneficial for the purpose of need of |0⟩ and |+⟩ logical states altogether, and clari-
 18

fying the importance of |T ⟩ state preparation in partic- the 15-to-1 distillation factory), followed by application
ular. However, this model relies on the logical measure- of non-Clifford rotations [13, 30, 33, 86]. The non-Clifford
ments being non-destructive, and continues to use a given rotations are often implemented via noisy magic states
logical qubit after measurement, which is not possible and gate teleportation, which therefore require logical
for transversal measurements on logical qubits without measurements. If the Clifford circuit depth has to be at
Pauli basis initialization. Thus, in an error-corrected im- least d to maintain FT, as is assumed in e.g. Ref. [42], the
plementation, Pauli basis initialization is still necessary, time cost of the magic state factory will be much larger
and the use of our FT framework is necessary to achieve than the case in which we can execute the circuit fault-
low time overhead. This comparison to other computa- tolerantly in constant depth, as we demonstrate here.
tional models highlights the generality of the algorithmic
fault-tolerance framework, and indicates that universally
across these various computational models, such tech- Decoding Complexity
niques allow a Θ(d) saving.
In this section, we discuss the decoding complexity of
our FT construction, and highlight important directions
Importance of Shallow Depth Algorithmic Gadgets of future research. While a detailed analysis and high-
performance implementation of large-scale decoding is
In this section, we discuss the importance of shallow- beyond the scope of this work, this will be important for
depth algorithmic gadgets in many practical compilations the large-scale practical realization of our scheme and to
of quantum algorithms. This highlights the need for FT maximize the savings in space-time cost. We therefore
strategies that do not require a Θ(d) separation between sketch some key considerations and highlight important
initialization and measurement, as we developed in the avenues of research that can address the decoding prob-
main text. lem. We emphasize that much of our discussion is not
In general, circuit components that involve an ancilla specific to our FT strategy, and may also apply to other
logical qubit often have a shallow depth between initial- hypergraph decoding problems and existing discussions
ization and measurement, whether this ancilla is used for of single-shot QEC [25] (Supplementary Information).
algorithmic reasons or compilation reasons. For instance, Compared with usual decoding problems, there are two
temporary ancilla registers are used in algorithmic gad- main aspects that may increase the complexity in our set-
gets such as adders [80, 81] or quantum read-only memo- ting. First, the decoding problem is now by necessity a
ries [82], where the bottom rail of a ripple carry structure hypergraph decoding problem, involving hyperedges con-
is initialized, two or three operations are performed on necting more than two vertices, which are not decompos-
it, and then the ancilla qubit is measured. A useful tech- able into existing weight-two edges [15]. Second, the size
nique for performing multiple circuit operations in par- of the relevant decoding problem (decoding volume) may
allel is time-optimal quantum computation [14, 16, 83], be much larger, as one needs to jointly decode many logi-
which is also related to gate teleportation [63] and Knill cal qubits, in the worst-case reaching the scale of the full
error correction [84]. In this case, a pair of logical qubits system.
are initialized in a Bell state. One qubit is then sent The hypergraph decoding problem has been stud-
as the input into a circuit fragment A, while the other ied in a variety of different settings [15, 87–90], and
qubit executes a Bell basis measurement with the output heuristic decoders appear to handle this fairly well in
of another circuit fragment B. The combined circuit is the low error rate regime in practice. For example,
equivalent to the sequential execution of B and A. This polynomial-time decoders such as belief propagation +
allows the two circuit fragments to be executed in par- ordered statistic decoding (BPOSD) [91], hypergraph
allel, despite them originally being sequential, thereby union find (HUF) [15, 90], and minimum-weight parity
reducing the total circuit depth and idling volume. How- factor (MWPF) [92] have been shown to result in compet-
ever, to fully capitalize on this advantage, it is desirable itive thresholds. Decoding on hypergraphs is also often
to only have a constant number of SE rounds separating required for high-rate QLDPC codes, or to appropriately
the Bell state initialization and Bell basis measurement, handle error correlations. Therefore, we expect that hy-
in order to minimize the extra circuit volume incurred pergraph decoding does not pose any serious challenge in
by the space-time trade-off. Thus, a depth O(1) sepa- practice.
ration between state initialization and measurement is There are several ways in which the increased decoding
again highly desirable. volume can be dealt with. First, error inferences that
Another common situation in which there is a low- are sufficiently far Ω(d) away from measurements or out-
depth separation between initialization and measurement going qubits can be committed to without affecting the
is magic state distillation [33] and auto-corrected magic logical error rate [71]. This reduces the relevant decoding
state teleportation [85]. Many magic state factories in- volume. Moreover, for underlying codes with the single-
volve a constant-depth Clifford circuit (e.g. depth 4 for shot QEC property [25], it may be possible to further
 19

reduce this depth. to solve very few of them. In both algorithmic FT and
Second, extra QEC rounds can also be inserted to re- conventional FT, we expect the total amount of classical
duce the relevant decoding volume and give more time decoding resources to scale with the number of logical
for the classical decoder to keep up with the quantum qubits. When decomposing correlated decoding into in-
computer and avoid the backlog problem [53]. Asymp- dividual cluster decoding problems, we therefore expect
totically, this may be necessary for both our scheme and the aggregate classical decoding resources required for
for computation schemes based on single-shot quantum our protocol to still remain competitive with conventional
error correction [25, 93], unless O(1)-time classical de- approaches.
Hardware Considerations
coding is possible. In both cases, the time cost will grow
from Θ(1) to Θ(d/C), where the improvement factor C
over conventional schemes with d SE rounds can be made In this section, we briefly comment on the hardware
arbitrarily large as the classical computation is sped up. requirements to implement our scheme. It is worth em-
phasizing that these requirements may be relaxed with
Third, we expect algorithms based on cluster growth future improvements to our construction.
(HUF and MWPF) and belief propagation to be readily Our algorithmic FT protocol makes important use
amenable to parallelization across multiple cores [94–97], of transversal gate operations between multiple logical
with the decoding problems merging only when an error qubits. As such, a direct implementation likely requires
cluster spans multiple decoding cores. As an error clus- two key ingredients: long-range connectivity and recon-
ter of size Θ(d) is exponentially unlikely, we expect it to figurability. Long-range connectivity is used to entan-
be unlikely for many decoding problems to have to be gle physical qubits that are located at matching posi-
merged together. Indeed, fast parallel decoders for the tions in large code patches, which are otherwise spatially-
surface code [96, 97] and QLDPC codes [98] have been separated. Reconfigurability is useful because a given
argued to achieve average runtime O(1) per SE round, al- logical qubit may perform transversal gates with many
though they still have an O(d) or O(log d) latency. There- other logical qubits throughout its lifetime, such that a
fore, although the original decoding problem is not mod- high cumulative connectivity degree is required, or multi-
ular (input-level modularity) [71, 99, 100], in practice ple swaps and routing must be used. Given that common
we may expect the decoder to naturally split things into routing techniques based on lattice surgery incur a Θ(d)
modular error clusters (decoder-level modularity). time cost, it is desirable to perform direct connections
Finally, there are many additional optimizations that via reconfigurable qubit interactions.
can be applied in practice. Because the decoding prob- These considerations make dynamically-reconfigurable
lems have substantial overlap, it may be possible to make hardware platforms such as atomic systems [35, 36, 101,
partial use of past decoding results, particularly when us- 102] particularly appealing. In particular, neutral atom
ing clustering decoders. The decoding and cluster growth arrays have demonstrated hundreds of transversal gate
process can also be initiated with partial syndrome in- operations on tens of logical qubits, making use of the
formation and continuously updated as more informa- flexible connectivity afforded by atom moving [36]. In
tion becomes available. Decoding problems with specific comparison, while systems with connections based on
structure, such as circuit fragments in which the flow of fixed wiring can support long-range connectivity and
CNOTs are directional (ED Fig. 3), may also benefit from switching [22, 103], transversal connections between mul-
specialized decoders [30]. We also note that although the tiple logical qubits likely increases the cumulative qubit
relevant decoding hypergraph for any given measurement degree which may significantly increase the hardware
is now larger, for a given rate of syndrome extraction on complexity. From a clock speed perspective, for typi-
the hardware, the amount of incoming data is compa- cal assumed code distances of d ∼ 30, our techniques
rable to the usual FT setting. Although the individual correspond to a 10 –100× speed-up by using transversal
correlated decoding problem is larger, we will only need operations in a reconfigurable architecture.
 Supplementary Information: Transversal Algorithmic Fault Tolerance for Fast
Quantum Computing
Hengyun Zhou,1, 2, ∗ Chen Zhao,1, † Madelyn Cain,2 Dolev Bluvstein,2 Casey Duckering,1
Hong-Ye Hu,2 Shengtao Wang,1 Aleksander Kubica,3, 4, 5 and Mikhail D. Lukin2, ‡
1
QuEra Computing Inc., 1284 Soldiers Field Road, Boston, MA, 02135, US
2
Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA
3
AWS Center for Quantum Computing, Pasadena, California 91125, USA
4
California Institute of Technology, Pasadena, California 91125, USA
5
Department of Applied Physics, Yale University, New Haven, Connecticut 06511, USA USA

I. SUMMARY OF NOTATION 8. Feed-forward Clifford operations of the above types.

arXiv:2406.17653v1 [quant-ph] 25 Jun 2024

Conditional on certain qubit measurement results,

To facilitate reading the rest of the supplementary in- perform some combination of the preceding opera-
formation, we summarize our notation in Tab. I. tions on the remaining qubits.

9. Qubit initialization in the magic state |T ⟩ = T |+⟩.

II. DETAILED DESCRIPTION OF PROTOCOL
Note that to simplify the construction of an error-
corrected version of these circuits, we have compiled the
In this section, we provide detailed descriptions of our Clifford circuit into a particular set of operations. X or
protocol and key related concepts, further elaborating on Y basis operations can be obtained from the Z basis via
the “key concepts” section from Methods. H and/or S gates.

II.1. Ideal Quantum Circuits

II.2. Noise Models

First, let us describe our protocol for turning a target In practice, quantum circuits will experience noise. For
quantum circuit into a fault-tolerant circuit. We assume our theoretical analysis, we adopt the local stochastic
that the circuit is specified in a computational model with noise model as a simplified description of actual noise
Pauli basis state preparation and measurement, single- channels [1]. Consider a set of possible elementary er-
and two-qubit Clifford gate operations, and |T ⟩ = T |+⟩ rors (faults) E, and denote a given error realization by
magic state inputs. |E|
the vector e ∈ Z2 , where the ith entry of the vector is
Definition 1 (Ideal quantum circuit). Define C, an ideal equal to one if and only if the ith error in E occurred.
Clifford quantum circuit with magic state inputs and feed- The local stochastic noise model satisfies the following
forward operations (henceforth ideal quantum circuit), to property: the probability that an error e of weight s oc-
be a quantum circuit that consists of layers of the follow- curs is at most ps , where p is the error rate. For the
ing operations: set of possible elementary errors, we choose the follow-
ing data-syndrome error set [1]: data qubits experience
1. Qubit initialization in state |0⟩. error rate p per initialization, syndrome extraction, and
measurement, and the syndrome bit readout experiences
2. Single-qubit Z gates.
error rate p. Following Ref. [1], we do not add extra er-
3. Single-qubit H gates. rors for transversal gates themselves but only the round
of syndrome extraction that follow them. Incorporating
4. Single-qubit S gates. gate errors just corresponds to a rescaling of the error
rate. While this error model is simplified compared to
5. CN OT gate between any pair of qubits. experimental noise models, threshold proofs for the for-
6. Identity gate, if no other operation is specified on a mer can be readily generalized to the latter by choos-
given qubit. ing a different set of elementary errors and noting that
syndrome extraction circuits for QLDPC codes typically
7. Measurement of a subset of qubits in the Z basis. have bounded depth, and therefore error propagation is
also bounded. The change in error model only results
in a quantitative modification of the threshold, without
changing the overall conclusions. Thus, we use the sim-
∗ These authors contributed equally; hyzhou@quera.com plified local stochastic noise model for our proofs, and
† These authors contributed equally more detailed circuit-level noise models (Sec. VII) for nu-
‡ lukin@physics.harvard.edu merical simulations.
 2

C Ideal Clifford quantum circuit with magic state inputs and feed-forward operations
|0⟩ Logical |0⟩ initial state prepared via random stabilizer projections
|0⟩ Ideal logical |0⟩ code state, with all stabilizers fixed to +1
CN OT Logical CNOT operation
CN OT Physical CNOT operation
M Number of ideal (logical) measurements performed in the ideal (logical) circuit
T Number of gate operation layers
B Maximal number of code blocks at any given time
q Number of logical qubit initializations performed in the Pauli basis
⃗bC ∈ ZM2 Logical bit string sampled from circuit C
⃗bj Vector formed by the first j logical measurement results of a given shot
fC ∈ (ZM 2 → R) Distribution of logical bit strings sampled from circuit C
p Parameter characterizing the noise strength
pth Error threshold
Q Quantum code
r Upper bound on stabilizer weight
c Upper bound on number of stabilizers each qubit is involved in
t Maximal number of qubits within a code block connected by transversal gates
s Size of connected cluster in the decoding hypergraph
v Maximal degree of a node in a hypergraph
d Code distance
C˜ Transversal realization of ideal circuit C
C˜e Transversal realization of ideal circuit C with error realization e
C˜0 Transversal realization of ideal circuit C with no errors
Object for the circuit up to the jth logical measurement, e.g. C| ˜ j denotes
|j
the transversal realization of the ideal circuit up to the jth logical measurement
E Set of elementary errors (faults)
|E|
e ∈ Z2 A given error realization
D Set of detectors
|D|
∂e ∈ Z2 Set of detectors a given error e triggers
Γ Hypergraph corresponding to the detector error model
Ξ Line graph of Γ, also known as syndrome adjacency graph in Ref. [1]
|E|
κ ∈ Z2 Recovery returned by the most likely error decoder
G Set of frame variables, corresponding to distinct patterns of Z operators applied on the |0⟩ initial state
|G|
g ∈ Z2 A given realization of frame variables
gl Frame logical variable, i.e. a frame variable that commutes with all stabilizers
Λ Matrix describing how frame logical variables flip logical measurement results
λ An inferred assignment of frame variables that returns the code to the codespace with all stabilizers equal to +1
f =e⊕κ Fault configuration, formed from the mod 2 addition of errors and error recovery operators
h=g⊕λ Frame configuration, formed from the mod 2 addition of frame variables and inferred frame repair operators
P (e) Forward propagation of operator e through the Clifford circuit to logical measurements
z Physical measurement results that a logical measurement corresponds to
Physical measurement results that would have occurred
zi
if no errors happened after the initial random stabilizer projections
Lj j-th logical operator
L(z) Logical measurement result inferred from the physical measurement results z
F (e), F (g) Change in the logical measurement result due to error or frame operators
Lc (z, κ, λ) Corrected logical measurement result after applying the inferred recovery operator κ and frame operator λ

TABLE I. Summary of conventions employed in this paper. For the error and frame variables, we use the same notation for
both the binary variables and the Pauli operators they correspond to, where the meaning should be clear based on the context.
An overline distinguishes operations and variables at the logical level from the corresponding ones at the physical level.

To capture the effect of a given set of errors on logi- forward in time through the circuit. Note that syndrome
cal measurements, we also define the forward-propagated measurement errors do not directly act on a physical data
error P (e). An error E on some data qubits occurring qubit, and therefore are not propagated forward. For a
before a unitary U is equivalent to U EU † occurring af- set of errors e, we can keep propagating the error for-
ter the unitary. We can thus propagate any error event ward until it reaches either a logical measurement or a
 3

future time boundary. We denote the resulting operator in |0⟩, followed by one syndrome extraction (SE)
as P (e), and its restriction onto the jth logical measure- round.
ment as P (e)|j .
2. Single-qubit Pauli gates do not lead to any physical
action, but are tracked in the logical Pauli frame.
II.3. Error-Corrected Quantum Circuits
3. Clifford gate operations are performed via transver-
sal gate operations, including transversal CNOT
We now describe how to realize the ideal quantum cir- gates between blocks and fold-transversal gates
cuit in this noisy setting, using logical qubits and quan- within each block [16–19], followed by one SE
tum error correction. We consider CSS stabilizer quan- round.
tum codes Q, encoding k logical qubits into n physical
data qubits, with code distance d, denoted by the nota- 4. Qubit measurement in the Z basis is replaced by
tion [[n, k, d]]. We restrict our attention to quantum low- measuring all data qubits in a code block in the Z
density parity check (QLDPC) codes, where each sta- basis.
bilizer generator has weight ≤ r and each data qubit
is involved in ≤ c stabilizer generators. QLDPC codes 5. Feed-forward operations and magic state teleporta-
have the nice property that the resulting syndrome ad- tion are executed in the same way as the ideal cir-
jacency graph (see following discussion) has bounded de- cuit, based on the decoded logical measurement re-
gree, thereby causing fault configurations to form small sults.
connected clusters that are more easily corrected. There
are many QLDPC code constructions, including surface 6. Magic states are assumed to be provided with all
codes [2, 3], color codes [4], and various high-rate con- stabilizers fixed to +1, followed by local stochastic
structions based on products and/or polynomials [5–13]. data qubit noise of strength p.
We only consider the case where all code blocks belong The magic states are assumed to be prepared via some
to the same code family, instead of the more general case separate procedure in this formulation. In practice, as
where different codes may be mixed and matched. Apart they are often obtained via magic state distillation [20]
from Theorem 13, we will focus on the case where all involving Clifford circuits and noisy state injection, we
code blocks have the same size. expect that our conclusions can be readily generalized to
Our analysis focuses on transversal operations, which include these procedures as well.
have well-behaved error propagation. Transversal gates A simple example of a transversal realization of a cir-
are defined relative to a partition of the code blocks [14, cuit is the preparation and measurement of correlations
15]. We choose the same, fixed partition for all code of a Bell pair. Using the transversal CNOT for CSS
blocks, and use the parameter t to denote the maximal codes, we can implement this using two blocks of any
size of any part within a code block. We call a physi- CSS QLDPC code, where only one logical qubit in each
cal implementation U of a logical operation U transver- block is used to create the Bell pair. This then enables
sal with respect to this partition, if it exclusively cou- implementing the target circuit with a family of codes
ples qubits within the same part (see Methods and be- with growing distance, allowing us to use the threshold
low for specific examples in state preparation and mea- theorem below and achieve exponential error suppression
surements, as well as gate operations). We will also fo- for the given circuit.
cus only on transversal operations consisting of depth- Note that for a general CSS QLDPC code family, the
one quantum circuits (excluding SE rounds), which cover above prescription may only allow the implementation of
most common transversal Clifford gates. The advantage a subset of ideal quantum circuits. For a quantum code
of transversal gates is that the spread of errors is con- encoding many logical qubits, all logical qubits within
strained to be within each partition. a given code block must be initialized and measured in
We now consider how a given ideal circuit C can be the same basis. Moreover, transversal gate operations
implemented using error-correcting codes and transversal for this code may only be able to implement a subset of
operations, subject to the local stochastic noise model Clifford gates [18].
described above. However, using the surface code, which has a transver-
Definition 2 (Transversal realization C˜ of ideal circuit sal implementation of the whole Clifford group, we can
C). Consider an ideal quantum circuit C, and a QEC obtain a transversal realization C˜ of any ideal circuit C.
code Q with some set of transversal operations. If there The same conclusion also applies to other codes with
exists a sequence of transversal operations of Q, such that transversal Clifford operations, such as the 2D color code.
the logical operations implement the ideal quantum circuit We now review the definition of the surface code. We
on some of the logical qubits, then we call the following focus on the non-rotated surface code for our proof, due
circuit a transversal realization C˜ of the ideal circuit C: to the relative simplicity of gate implementations, but
we expect the conclusions to readily apply to other vari-
1. Qubit initialization in the Z basis is replaced by ations as well. We illustrate the non-rotated surface
initialization of all physical qubits in a code block code in Fig. 1. The distance d surface code consists of
 4

a 4. Single-qubit S gates are replaced by a fold-

transversal S gate [16, 17], in which physical S,
S † gates are applied in an alternating fashion on
qubits on the diagonal, and CZ gates are applied
on pairs of qubits that are matched together when
(0,3)
folding across a diagonal (Fig. 1(c)). This is fol-
lowed by one SE round.
(0,2) 5. CN OT gates are replaced by transversal CN OT s
between pairs of logical qubits, followed by one SE
(0,0) (2,0) round.
b c
6. Identity gates are replaced by one SE round.
7. Measurements in the Z basis are replaced by a
transversal measurement of all corresponding phys-
ical qubits in the Z basis.
8. Feedforward Clifford operations are executed in the
same way as above, based on the decoded logical
measurement results.
9. Magic states are assumed to be provided with all
stabilizers fixed to +1, followed by local stochastic
FIG. 1. (a) Illustration of the non-rotated surface code. data qubit noise of strength p.
White circles indicate data qubits. Orange (green) plaque-
ttes are Z (X) stabilizers. The logical Z (X) operator runs
Here, all logical qubits (code blocks) are non-rotated sur-
vertically (horizontally), and we choose our convention for face codes of the same code distance d.
fixing Z (X) stabilizers to be performing a chain of X (Z) The syndrome measurement for the surface code can
flips to the left (bottom) boundary, as illustrated by the red
be performed simultaneously in both bases [3]. When
line. We refer to the rows (columns) that have data qubits on
the outer edge as major rows(columns). We have also labeled
initializing the logical qubit, the values in one basis are
the qubit coordinate system convention. (b) Illustration of already deterministic, and therefore we only need to mea-
transversal H gate, consisting of physical H gates followed sure the complementary basis. However, for simplicity of
by a reflection along the diagonal. We choose to perform a analysis, we include both bases here.
reflection instead of rotation to limit the transversal partition Each logical operation is followed by one SE round in
size to two. (c) Illustration of transversal S gate, consisting our construction. This is primarily for simplicity of our
of S and S † gates along the diagonal, together with CZ gates analysis, and the number of rounds should be optimized
between mirrored qubits. in practice depending on the given target circuit and tar-
get logical error rate, possibly even performing multiple
gate operations before one SE round [21]. Notice also
n = d2 + (d − 1)2 data qubits and n − 1 stabilizers. The that we never perform d SE rounds following any given
logical operators X and Z are shown in Fig. 1 as well. operation.
We can now obtain a transversal realization of any
ideal quantum circuit described in Def. 1.
Definition 3 (Surface code transversal realization). II.4. Error Correction and Decoding
Given an ideal quantum circuit C with magic state in-
puts and feed-forward operations (Def. 1), we define its Having specified the error-corrected quantum circuit,
surface code transversal realization C˜ of distance d by re- let us now describe how we handle errors and interpret
placing each of the operations as follows: logical measurement results. To start with, we consider
the standard decoding approach, in which a detector er-
1. Qubit initialization in the Z basis is replaced by ini- ror model (decoding hypergraph) is constructed, and a
tialization of physical data qubits in |0⟩, followed by recovery operator κ is identified that reproduces the ob-
one SE round. served syndrome patterns.
|E|
2. Single-qubit Z gates do not lead to any physical ac- As above, consider a given error realization e ∈ Z2 ,
tion, but are tracked in the logical Pauli frame. where the ith entry of the vector is one iff the ith error in
E occurred. We will also use the same notation to denote
3. Single-qubit H gates are replaced by a transversal the Pauli operator the error realization corresponds to,
H gate, in which we apply an H gate on each phys- where the meaning should be clear from the context. In
ical qubit of the code block, followed by a reflection the absence of errors, certain products of stabilizer mea-
across the diagonal, and one SE round (Fig. 1(b)). surement outcomes are deterministic. For example, with
 5

an idling logical qubit, the product of successive stabilizer ing the measurement results of the corresponding data
outcomes is deterministic in the absence of errors. We de- qubits, and do not assign X stabilizer values since they
note these deterministic products as detectors (checks), are unknown when performing a transversal Z measure-
and a generating set of detectors is denoted as D. In ment. The detectors can now be constructed for each of
the presence of an error e, some set of detectors will be the logical operations as follows:
triggered, which we denote as ∂e. We can construct the
detector error model (decoding hypergraph) Γ, in which 1. For an identity gate on logical qubit i before SE
vertices are detectors, and (hyper)edges are error events. round r, the detector is
This also motivates the boundary operator notation ∂, as
the boundary of the hyperedges are the detector nodes. S(i, r − 1, x, y, B)S(i, r, x, y, B).
To analyze error clusters, we also introduce the related
notion of the syndrome adjacency graph Ξ [1]. In this 2. For a H gate on logical qubit i before SE round r,
hypergraph, vertices are elementary fault locations, and the detectors are
hyperedges are detectors connecting the fault locations
they flip. S(i, r − 1, x, y, X)S(i, r, y, x, Z),
Due to the feed-forward operations, the circuit must S(i, r − 1, x, y, Z)S(i, r, y, x, X).
be constructed in a sequential manner, where the actual
In other words, we compare against the stabilizer
circuit to be executed only becomes available after in-
after mirroring across the diagonal.
terpreting and committing to past measurement results.
Generically, the circuit C|˜ j for the jth logical measure- 3. For a transversal CN OT from logical qubit i to
ment is only constructed after interpreting the first j − 1 logical qubit j, before SE round r, the detectors
logical measurements, and performing any requisite feed- are
forward operations. It also varies between different shots
of executing the logical algorithm, due to randomness in S(j, r − 1, x, y, X)S(j, r, x, y, X),
the measurement results. Similarly, we construct a de- S(i, r − 1, x, y, Z)S(i, r, x, y, Z),
coding problem Γ|j for each shot based on the circuit and S(i, r − 1, x, y, X)S(j, r − 1, x, y, X)S(i, r, x, y, X),
errors that occur up to the jth logical measurement. In
the following, we will use Γ|j to determine the jth logical S(i, r − 1, x, y, Z)S(j, r − 1, x, y, Z)S(j, r, x, y, Z).
measurement. We also ensure that the assigned measure-
ment results for the first j − 1 logical measurements are See also Ref. [21]. The transversal CN OT prop-
consistent with the feed-forwards and circuits chosen, as agates X errors from control to target, and Z er-
discussed below. rors from target to control, thereby leading to the
higher-weight detectors.
Let us now discuss the concrete construction of de-
tectors for the surface code. The construction can be 4. For a S gate on logical qubit i before SE round r,
readily extended to the case of general LDPC codes. the detectors are
We construct detectors in a time-local fashion, using the
fact that logical gate operations are interspersed with SE S(i, r − 1, x, y, Z)S(i, r, x, y, Z),
rounds. To describe the detectors, we label the syndrome S(i, r − 1, x, y, X)S(i, r − 1, y, x, Z)S(i, r, x, y, X).
extraction result with the logical qubit index i, syndrome
round index r, location within code block (x, y), and basis This bears some similarity to the CN OT gate, but
B = X or Z. Our physical qubit location coordinate sys- couples the X and Z components of the decoding
tem starts from the bottom left, with the bottom left data problem together rather than that of two logical
qubit having the label (0, 0). We place data qubits at co- qubits.
ordinates (x, y) with x+y ≡ 0 mod 2, e.g. the next data
qubit to the right is at coordinate (2, 0) (Fig. 1(a)). Sta- Given the detector error model and a detector shot
bilizers are placed at the center of the corresponding pla- ∂e, a decoder returns a recovery operator κ, such that
quette. With this convention, we can label the measure- ∂κ = ∂e. The total action of error and recovery is then
ment result of the bottom left Z stabilizer of logical qubit given by f = e ⊕ κ, where addition is understood to
1, in round 3, as S(i = 1, r = 3, x = 1, y = 0, B = Z). be mod 2. In slight abuse of terminology, we will refer
The first stabilizer measurement round is labeled round to this joint action as the fault configuration. By lin-
1. For initialization in the Z basis, we set the round 0 earity, we have that ∂(κ ⊕ e) = 0. For the purposes of
Z stabilizer values to be +1, since they are initialized our discussion, we will make use of the most likely er-
with a deterministic eigenvalue, and construct a detec- ror (MLE) decoder, also known as the minimum weight
tor comparing the round 1 Z stabilizer value with this. decoder. The MLE decoder returns the most likely er-
|E|
Meanwhile, the X stabilizer values are random and hence ror κ ∈ Z2 that is consistent with the observed detec-
there is no detector comparing the first X stabilizer value tors. Note that this decoder solves the most likely error
to previous results. For measurements in the Z basis, we problem instead of the maximum likelihood problem, i.e.
construct a final round Z stabilizer value by multiply- it does not consider the entropy factor associated with
 6

the number of cosets. Additionally, for generic decod- surement results that they might flip, for each circuit C| ˜ j,
ing problems, identifying the most likely error may be j×qj
we introduce a matrix Λ ∈ Z2 , where qj is the num-
computationally challenging, although efficient heuristics ber of logical initializations in the Pauli basis (thereby
exist (see Decoding Complexity, Methods). producing qj frame logical operators), and j is the num-
ber of logical measurements that have been performed up
to this point. Note that if more than one logical qubit
II.5. Logical Qubit Initialization and Frame is encoded in each code block, there will be as many Z
Variables frame logical operators as there are logical qubits. For
a given circuit C|˜ j , Λ can be efficiently constructed by
We now introduce some useful concepts to describe the propagating the frame logical operators until they reach
randomness associated with measurement-based logical the logical measurements, using standard techniques for
qubit initialization, and clarify how to interpret random propagating Pauli operators through Clifford circuits.
logical measurement outcomes. As a concrete example, let us define a basis of frame
Due to the random initial projection when measuring operators for the surface code (Fig. 1). As mentioned
X stabilizers during |0⟩ initialization, the physical state above, we will choose X to be the product of X opera-
is not initially in the code space, where all stabilizers tors on the top row, and Z to be the product of Z op-
should have eigenvalue +1. To describe this, we adapt erators on the rightmost column. We choose the frame
and formalize a concept introduced and implemented in logical operator to be the Z logical operator representa-
Stim [22]. There, to capture the randomness introduced tive above. For each X stabilizer s, we choose a frame
when measuring a physical qubit initialized in |0⟩ in the operator gs consisting of a string of Z operators along
X basis, a Z operator on that site is multiplied into the column that the X stabilizer is located in, starting
the state with 50% probability. Starting from a refer- from the bottom data qubit of the stabilizer and ending
ence sample of measurement results, the full measure- at the bottom boundary (see red line in Fig. 1(a)). By
ment result distribution can then be obtained by con- definition, gs will only flip the single stabilizer s, while all
sidering the distribution over these random Z operators other stabilizers and logical operators remain unchanged.
and error events. We refer to these Z operators that Together, these form a basis G of frame operators for the
act on the initialization boundary as “frame operators” surface code. While any equivalent choice of logical qubit
(Z operator acting on each physical qubit of the initial and frame operators is valid (Lemma 4), we choose this
logical qubit), and variables describing them as “frame particular convention so that fixing the stabilizer values
variables”, where the name is meant to indicate that they will not change the logical qubit readout result.
describe the reference frame of random stabilizer initial-
ization, and the reference frame in which we will interpret
our logical measurement results. II.6. Interpreting Logical Measurement Results
Formally, consider a |0⟩ logical qubit initialization. For
each data qubit in the code block, associate a Z operator. With these concepts in hand, we now consider how
Some of these Z operators will have inter-dependencies logical measurement results are interpreted, particularly
due to Z stabilizer constraints. Therefore, we can con- in the case where the logical measurement results are
struct a basis G of frame operators as follows: For each random. The majority of error correction analyses and
data qubit i, we add Zi to G if it is not equivalent to any simulations focus on the case of a deterministic observ-
combination of operators in G up to stabilizers. For an able, as they provide a simple characterization of logical
[[n, k, d]] quantum code with rZ independent Z stabilizer error rates. However, the case of non-deterministic ob-
generators, we have |G| = n − rZ . We use g to denote servables is equally important, and the interpretation of
both a product of frame operators taken from G and a them can be more intricate.
|G|
binary vector g ∈ Z2 describing it. To start with, let us describe the logical qubit initial-
Some of the frame operators will flip X stabilizers, and ization procedure in terms of frame variables. To initial-
correspond to different effective code spaces (reference ize a logical qubit in |0⟩, we start with all physical qubits
frames) that we may project into during the initial ran- in |0⟩, and perform a single SE round. This projects
dom stabilizer measurement results. We denote these by the X stabilizers to take on random values. The quan-
gs , and refer to them as frame stabilizer operators. There tum state can be described in terms of frame variables as
are also frame operators gl that do not flip any X stabiliz- |0⟩ = g|0⟩, where |0⟩ is the ideal |0⟩ logical state with all
ers, instead corresponding to a logical Z operator of the stabilizers fixed to +1, and g is some appropriate frame
code block. We refer to them as frame logical operators. variable. Intuitively, we start from |0⟩ and flip certain X
While applying these frame logical operators does not stabilizers to reach the actual state |0⟩. Similar to the
change the initial physical state |0⟩, it does lead to dif- error variable e, the frame variable g will not be directly
ferent interpretations of the logical measurement result accessible to us, and must be inferred from our observa-
without changing the measurement distribution, a fact tions.
that is crucial for our construction. To capture the rela- We will now describe the procedure of interpreting the
tion between frame logical operators gl and logical mea- logical measurement outcome of a noisy error-corrected
 7

quantum circuit in three steps. described by the frame operator g, and our frame repair
First, we apply the standard decoding procedure in operation λ may differ from g. Define a fixed transversal
Sec. II.4 to obtain an inferred error recovery operator κ, Clifford circuit with magic state inputs C˜f ix by taking a
such that ∂(e ⊕ κ) = 0. This ensures that the result- ˜ fixing the first j −1 logical mea-
transversal realization C,
ing frame configuration f = e ⊕ κ does not trigger any surement results and their resulting feed-forward opera-
detectors. tions, and considering the quantum circuit up to the jth
Next, we perform the analogous procedure to error re- logical measurement, thereby obtaining a non-adaptive
covery for the frame variables, which we refer to as a quantum circuit C˜f ix . We can then show the following
|G|
frame repair operation λ ∈ Z2 . Whereas error recovery lemma:
aims to ensure that no detectors are triggered in the bulk
of the quantum circuit, frame repair aims to ensure that Lemma 4 (Frame variables do not affect measurement
we return to the ideal code space with all stabilizers set distribution). Consider a fixed transversal Clifford cir-
to +1 when interpreting a logical measurement. There- cuit with magic state inputs C˜f ix and a fixed, arbitrary
fore, we choose λ, such that the combined effect of error fault configuration f = e ⊕ κ such that ∂f = 0. Then for
|G|
operator e, recovery operator κ, frame operator g and any choice of frame configuration h = g ⊕ λ ∈ Z2 , the
frame repair operator λ does not violate any stabilizers. corrected logical observable Lc has the same measurement
In other words, (e ⊕ κ) ⊕ (g ⊕ λ) should act as a sta- distribution regardless of the choice of h.
bilizer or logical operator. We refer to the combination
h = g ⊕ λ as the “frame configuration”, again mirroring Consider the difference in the corrected logical observ-
the notation for faults. able between h = g ⊕ λ and h0 = I. By construction, the
Finally, we evaluate the logical observable after apply- combination h = g ⊕ λ must return the logical qubit to
ing the above corrections. Denote the raw logical observ- the codespace. h must thus commute with all X stabiliz-
able inferred from the bit strings as ers, and as h is composed of Z operators, it can therefore
M only be a combination of Z stabilizers and Z logical op-
L(z) = zi . erators. By definition, h is applied on the ideal logical
zi ∈L initial state |0⟩, so we conclude that h acts as a logical Z
operator on |0⟩, i.e. the corrected logical observable has
The raw logical observable already incorporates the ef- the same measurement distribution for h and h0 .
fect of e and g, which physically occurred. To obtain the Intuitively, this is because what random stabilizer pat-
corrected logical observable, we propagate the effects of tern we projected into should not affect the logical mea-
the error recovery operation κ and frame repair operation surement results. It is important to emphasize that this
λ to the measured logical qubit. Recalling that P (κ)|j statement only applies to the distribution of measure-
denotes the forward propagation of operator κ to the jth ment results: for any given shot, different choices of frame
logical measurement L, we can define the parity flip of variables may still lead to different interpretations, a fea-
the logical observable due to κ: ture that we will make use of in our decoding strategy.
(   Note that this lemma is formulated in the case of a
0, P (κ)|j , L = 0, fixed circuit, which will not generally be the case in the
F (κ) =   (1)
1, P (κ)|j , L ̸= 0, presence of feed-forward operations. In the latter case,
we can still make use of this lemma as follows: con-
where the bracket indicates taking the commutator. The sider the full conditional circuit C˜cond , the fixed circuit
corrected logical observable is then given by corresponding to the given branch of conditional opera-
tions C˜f ix , as well as their corresponding ideal versions
Lc (z, κ, λ) = L(z) ⊕ F (κ) ⊕ F (λ). (2)
Ccond and Cf ix . Lemma 4 shows that for a noiseless cir-
Now let us consider how the error recovery and frame cuit, the measurement distribution of the ideal and error-
repair procedures affect the logical measurement result. corrected circuits are identical, fC̃f ix = fCf ix , regardless
First, consider the case when the inference repro- of the frame variables. This immediately implies that
duces the error and frame operators applied exactly, i.e. the marginal distribution conditioned on some fixed set
(e ⊕ κ) ⊕ (g ⊕ λ) is the identity operator. In this case, of previous measurement results are identical. On the
the circuit and quantum state are equivalent to preparing other hand, conditioned on the fixed set of previous mea-
ideal code states with all stabilizers set to +1, executing surement results, the fixed and conditional circuits are
the logical circuit, and performing logical measurements. identical, i.e. fC̃cond = fC̃f ix , fCcond = fCf ix . This implies
As everything is ideal and all stabilizers are +1 through- that fC̃cond = fCcond . Thus, Lemma 4 can be readily ap-
out, standard arguments show that the logical quantum plied to the setting with feed-forward operations as well.
circuit C˜ executes the ideal quantum circuit C correctly Finally, we briefly comment on the case with noisy
and reproduces the same distribution of logical bit strings operations, with more details provided in the proofs in
fC̃ = fC . the next section. In this case, we first apply the error
Next, consider the case where no errors were applied, recovery operator κ, which handles any detectors in the
but we still have the initial random stabilizer projection bulk. As some error clusters may have terminated on
 8

the initialization boundary, the total effect of e ⊕ κ may where the outer subscript denotes taking the first
lead to both logical errors and a change in the reference j − 1 components of the vector, and ⃗bj−1 are the
frame. We therefore make corresponding modifications first j − 1 logical measurement results that we have
to the frame repair operation λ as well, before applying already committed to. If there is a solution gl , ap-
the preceding arguments. ply the frame logical operators gl and update the
(1)
logical measurement result ⃗bj = ⃗bj ⊕ Λgl , commit-
ting to the jth measurement result (this guarantees
II.7. Decoding Strategy
consistency with the first j − 1 logical measurement
results). If not, a heralded failure has occurred and
In this section, we provide a description of our full we abort the execution.
decoding strategy, which includes decoding errors, infer-
ring frame variables, and interpreting logical measure- Notice that each time we perform partial decoding,
ment results. As described in the main text, the key we only commit to the logical measurement result, with-
idea is to perform correlated decoding across the logical out committing to the corrections and reference frame
algorithm, thereby utilizing all relevant syndrome infor- throughout. In other words, we only commit to the min-
mation. However, we may need to apply additional frame imal amount of information necessary to determine the
operators in order to ensure that the executed quantum feed-forward operations. We leave possible relaxations of
circuit feed-forward is consistent with past logical mea- this, where more pieces of information are fixed, to future
surement results. work.
When executing transversal Clifford quantum circuits, In this definition, we processed the logical measure-
decoding and performing recovery operations are only ment results and feedforward one by one. The technique,
necessary when interpreting logical measurement results however, also readily applies to the case where we in-
(i.e. the classical outputs of the quantum computa- stead partition the logical measurements based on lay-
tion), which can lead to different executed circuits due ers of Clifford feedforward operations, resulting in fewer
to feed-forward operations. To capture this dependency, rounds of decoding.
we sort the set of logical measurements into an ordering To show that this decoding strategy has a high prob-
{L̄1 , L̄2 , L̄3 , ..., L̄M } based on the time they occur and ability of success, we need to show two things: first, the
conditional dependencies. We require that for any pair probability of a heralded error should be low; second,
i < j, the logical measurement result L̄i must not de- the probability of a regular logical error should be low,
pend on the subsequent logical measurement result L̄j . such that the measurement distribution should be close
If multiple measurements occur simultaneously, then we in total variation distance (TVD) to the measurement
can place them in any order, since there are no direct distribution of the ideal circuit. We will now prove these
inter-dependencies. statements.
We can now recursively define our decoding strategy.
For each logical measurement L̄j , we assume that the
previous logical measurement results {L̄1 , ..., L̄j−1 } have III. PROOF OF FAULT TOLERANCE
been decoded and interpreted, and we have committed to
these previous results in order to perform any necessary
III.1. Characterizing the Effect of Errors
feed-forward operations.
Definition 5 (Decoding strategy). For the jth logical We start by examining how physical errors propagate
measurement, we perform two steps to decode and inter- under transversal gate operations. Transversality guar-
pret the measurement result: antees that a given error cannot cause too many errors
1. Partial decoding (correlated decoding): Based on a given code block when propagated to the qubit mea-
˜ j up to the jth logical mea-
on the current circuit C| surements.
surement (including the applied feed-forward opera-
Lemma 6 (Transversal gates limit error propagation).
tions), construct the detector error model Γ|j . Ap-
Consider a transversal realization C˜ of an ideal circuit,
ply the MLE decoder to Γ|j and the available de-
with maximal size t of the fixed transversal partition.
tector data D|j to identify and apply (in the Pauli
Then any fault configuration f , when forward propagated
frame) an inferred error recovery operator κ. From
(1) P (f ) to any logical measurement, has support on at most
this, obtain logical measurement values ⃗bj for the t|f | data qubits, where |f | is the weight of the fault con-
first j logical measurements, where the superscript figuration f .
(1) denotes the first step of decoding.
2. Consistency check: Solve the linear equation This lemma is a straightforward consequence of the
over Z2 definition of transversal gates. By construction, each in-
  dividual error can only spread to at most t qubits within
(1)
(Λgl )1,...,j−1 = ⃗bj ⊕ ⃗bj−1 , (3) each code block, and therefore P (f ) has support on at
1,...,j−1 most t|f | data qubits on each code block.
 9

For our data-syndrome noise model, in which errors and combine the frame configurations
occur on data qubits between SE rounds and on the syn- !
drome value itself, we do not need to consider error prop- M
agation due to the syndrome extraction procedure itself. λ̂ = g ⊕ (λ̂i ⊕ g) . (5)
For practical SE circuits, for QLDPC codes with bounded i

syndrome extraction circuit depth, this only produces a

constant factor difference due to the bounded error prop- Since each component P (fi ⊕ (λ̂i ⊕ g)) has trivial logical
agation and doesn’t change our qualitative conclusions. action on the measurement results, by linearity, so does
As discussed above, for the special case of the non- the combined effect P (f ⊕ (g ⊕ λ̂)).
rotated surface code and the set of transversal operations Case 1: First, we consider the case where fi is not con-
that we consider, we have t = 2. Intuitively, an error can nected to any detectors that involve an initial syndrome
only affect the given qubit and the qubit that it is paired measurement during |0⟩ state initialization. Intuitively,
with via a reflection across the diagonal (Fig. 1). this is the case where fi is not connected to the initializa-
We now introduce a technical lemma characterizing the tion boundary. In this case, if we choose λ̂i = g, then the
effect of the fault configuration and frame configuration combined action of fault configuration and frame config-
after applying decoding and error correction. Here and uration is P (fi ) ⊕ P (g ⊕ λ̂i ) = P (fi ). Since ∂fi = 0 and
below, we will use the notation with a hat λ̂ to indicate a fi is not connected to an initialization boundary, P (fi )
frame repair operator that leads to trivial logical action must be a product of X stabilizers and X logical oper-
on the logical measurements of interest for the given shot, ators. Since wt(P (fi )) < d, it cannot be a logical X
and that without a hat λ to indicate any other frame operator that changes the Z measurement result. There-
repair operator, e.g. those determined from consistency fore, it does not flip the logical measurement result.
checks. Case 2: Now consider the case where fi is connected to
a |0⟩ initialization boundary. Let λi be the frame repair
Lemma 7 (Correction on codespace for low weight operation we choose, and let hi = g⊕λi . If P (fi ⊕hi ) does
faults). Consider the jth logical measurement and the as- not flip the logical measurement result, then we have al-
sociated syndrome adjacency graph Ξ|j in a given execu- ready satisfied our requirements, and we can set λ̂i = λi .
˜ Consider any fault
tion of the transversal realization C. Otherwise, suppose P (fi ⊕hi ) = L, where L is some non-
configuration f = e ⊕ κ in Ξ|j , where the largest weight trivial logical operator. Since wt(P (fi )) < d, the logical
of any connected cluster of error vertices is less than d/t. operator must have some contribution from the frame
configuration hi located on the initialization boundary.
Then there exists a choice of frame repair operator λ̂, Similar to Eq. (3), we can thus find a frame logical op-
such that the combined effect of fault configuration and erator gl to apply on the initialization boundary, such
frame configuration P (e ⊕ κ) ⊕ P (g ⊕ λ̂) does not flip the that P (gl ) = L. Choosing λ̂i = λi ⊕ gl then implies that
results of any of the j logical measurements.
P (fi ⊕ (g ⊕ λ̂i )) cancels the application of L on the logi-
As we described in Def. 2, measurements are performed cal measurement, such that λ̂i acts trivially on the logical
in the Z basis (X basis measurements can be performed measurements.
by an H gate followed by a Z measurement). To show Combining the fault configurations and frame config-
that no logical measurement result is flipped, i.e. the urations as in Eqs. (4,5), the frame configuration λ̂ will
combined effect is trivial, we need to show that for the be such that the combined effect of fault configuration
Z measurements we perform, P (f ) ⊕ P (g ⊕ λ̂) acts as and frame configuration does not flip any of the j logical
a combination of stabilizers and the logical Z operator, measurements.
which will not change the logical measurement result. When considering clusters connected to initialization
Here, f = e ⊕ κ as before. boundaries, we only need to consider those connected to
We will analyze each connected cluster fi of f sepa- Pauli basis initialization boundaries and not |T ⟩ magic
rately. Because the different clusters are disjoint, ∂f = 0 state inputs. This is because per Def. 2, the magic states
implies that ∂fi = 0. As P (f ) is linear in the input are provided with known stabilizer values up to local
error, we can analyze the effect of each connected com- stochastic noise. As the stabilizer values are known with
ponent independently. By Lemma 6 and the condition confidence, detectors can be constructed in both bases to
that wt(fi ) < d/t for all i, we have that wt(P (fi )) < d. detect and correct any errors nearby. In other words, un-
like |0⟩ initialization, errors cannot terminate on magic
We now show that ∂fi = 0 and wt(P (fi )) < d implies
state inputs without being detectable.
that there exists a choice of frame repair operator λ̂i , Lemma 7 only requires such a frame repair operation
such that P (fi ) ⊕ P (g ⊕ λ̂i ) acts trivially on the logical to exist, but does not require us to explicitly apply it. We
measurements. If this is the case, then we can combine simply use its existence to guarantee consistency between
the fault configurations multiple rounds of decoding. The reason that finding
M this particular frame repair operation is not important is
f= fi , (4) that per Lemma 4, this choice does not affect the logical
i measurement distribution. Our decoding strategy only
 10

a Errors and frame flips b Error Recovery c Frame repair d Frame logical flip

2
3

Time Time Time Time

FIG. 2. Illustration of error recovery and frame repair procedures. We illustrate the procedure for the surface code,
where a cross-sectional view with one spatial axis and one time axis is shown. We only illustrate X errors and Z stabilizer
measurement errors, which are relevant to interpreting the Z measurement. X errors can terminate on orange boundaries,
but cannot terminate on cyan boundaries. The transversal CN OT copies X errors from the top to the bottom, resulting in
a branching point (black cross) and an error cluster spanning both code blocks. (a) Error chains and frame flips. Chains of
X-type errors (orange lines) lead to syndromes (end points) or terminate on appropriate boundaries. A line segment in the
vertical direction is a data qubit X error, while a line segment in the horizontal direction is a measurement error. Note that
the X-type error cannot terminate on the transversal Z measurement boundary. The random stabilizer initialization leads to
a frame configuration on the logical |+⟩ initialization, as illustrated by the blue line and the flipped Z stabilizer (blue point).
This is similar to the frame stabilizer operator gs illustrated in Fig. 1(a). (b) We first infer an error recovery operator, which has
the same boundary as the error chain. Together, the error and recovery operator form the fault configuration, which triggers
no detectors. We illustrate a few examples (orange lines) that do not lead to a logical error: (1) the fault configuration forms a
closed loop and is equivalent to applying a stabilizer; (2) the fault configuration terminates on an initialization boundary; (3)
the fault configuration terminates on a future time boundary (unmeasured logical qubit), but the forward-propagated errors
onto the measured logical qubit are equivalent to a stabilizer. A logical error can only happen when the fault configuration spans
across two opposing spatial boundaries (red line), which requires an error of weight Θ(d). (c,d) The frame repair operation
returns the logical qubit to the code space with all stabilizers +1, corresponding to cancelling any residual flipped stabilizers
on the initialization boundary. Note that the error recovery process may also lead to a change that needs to be accounted
for by frame repair. An example choice of frame repair is shown in (c), which applies an overall X operator on the logical
measurement result. Alternatively, a different choice of frame repair shown in (d), related to the previous one by a frame logical
flip, results in identity operation on the logical measurement result.

requires us to find frame repair operations that guaran- logical operator and thereby acts trivially on the logical
tee consistency between multiple rounds of decoding of measurement, as required by Lemma 7.
the same logical measurement in a given shot, without
requiring the logical action for a given shot to be trivial.
Let us briefly illustrate this lemma in the case of the III.2. Characterizing Logical Errors
surface code. In Fig. 2(a), we illustrate an instance of
physical errors e (orange lines) and initial random frame It is important to note that we are only guaranteed
projection g (blue line). The error recovery and frame to not flip the logical qubits that we have performed a
repair procedures are illustrated in Fig. 2(b,c), cancel- measurement on, and only in the basis that we measured.
ing any bulk detectors and returning the stabilizers to There could be residual errors on the remaining qubits,
the +1 subspace, respectively. We illustrate different or a Z flip on a logical qubit measured in the Z basis.
types of clusters that can appear in Fig. 2(b): case 1 in However, the former will get fixed in later rounds of de-
Lemma 7 is illustrated with the orange lines labeled 1 and coding, so long as we can maintain consistency on the
3, while case 2 is illustrated by the orange line labeled 2. logical measurement results, while the latter does not in-
For case 1, the frame configuration acts trivially when fluence any measurement results. Thus, they should not
forward-propagated to the logical measurement, auto- cause any effects on the logical measurement distribution.
matically satisfying our requirements. For case 2, the We formalize this idea in the following key lemma, which
frame configuration flips some stabilizers, which we take characterizes the structure of logical errors. It shows that
into account in the frame repair stage (Fig. 2(c)). After small clusters of errors cannot give rise to logical errors
the error recovery and frame repair stage, it is possible on logical qubits that have been measured.
that an overall X operator is applied at initialization,
which propagates through the CNOT to flip the logical Lemma 8 (Logical errors must be composed of at least
measurement result. However, one can choose an alter- d/t faults). Consider the jth logical measurement and
native frame configuration (Fig. 2(d)), which negates the the associated syndrome adjacency graph Ξ|j in a given
 11

˜ Consider any
execution of the transversal realization C. hence frame configuration ĥ|j−1 = g ⊕ λ̂|j−1 , such that
fault configuration f = e ⊕ κ in Ξ|j , where the largest P (f |j−1 ) ⊕ P (ĥ|j−1 ) acts trivially on the first j − 1 log-
weight of any connected cluster of error vertices is less ical measurement results. Similarly for the jth logical
than d/t. measurement, there exists λ̂|j and ĥ|j = g ⊕ λ̂|j , such
Then there exists a choice of frame repair operator λj , that P (f |j ) ⊕ P (ĥ|j ) acts trivially for the first j logical
such that measurement results.
1. The first j − 1 measurement results are consistent The actual frame configuration we chose for decoding
with the previous rounds of decoding, if the previous the first j−1 measurements, h|j−1 , may differ from ĥ|j−1 ,
rounds of decoding also satisfy the same conditions as we needed to maintain consistency with previously
above. committed measurements. This may lead to different
measurement outcomes for this specific shot (note that
2. The distribution of the jth measurement, condi- the distribution still remains the same). For joint decod-
tioned on the outcome of the first j − 1 measure- ing of the first j measurements, let us therefore choose
ment results from the previous round of decoding, the following inferred frame assignment
is identical to the ideal distribution.
λ|j = ĥ|j−1 ⊕ h|j−1 ⊕ λ̂|j . (6)
Recall our notation convention, where λ̂ indicates a
frame repair operator that has trivial action for the given With this assignment and by linearity, the action on the
shot, and λ is the frame repair operator that we ap- codespace is
ply based on consistency conditions. In other words,
P (f ) ⊕ P (ĥ) has trivial logical action when the latter P (f |j ) ⊕ P (ĥ|j−1 ) ⊕ P (h|j−1 ) ⊕ P (ĥ|j )
h i h i
term ĥ = g ⊕ λ̂ has a hat. = P (f |j ) ⊕ P (ĥ|j ) ⊕ P (ĥ|j−1 ) ⊕ P (h|j−1 ) . (7)
Let us start by proving property 2. The proof here
is similar to our discussion following Lemma 4. Condi- P (f |j ) ⊕ P (ĥ|j ) has trivial logical action by construc-
tioned on the outcome of the first j − 1 measurement tion (the hat is present), so the combined action is
results, the circuit up to the jth measurement is now a
identical to that of P (ĥ|j−1 ) ⊕ P (h|j−1 ). Similarly,
deterministic circuit C˜f ix , and we can construct a given
syndrome adjacency graph Ξ|j . By Lemma 7, there ex- P (f |j−1 ) ⊕ P (ĥ|j−1 ) has trivial logical action by con-
struction, so on the first j − 1 measurements, we have
ists a choice of frame repair operator λ̂ that produces
that
the same measurement distribution as the corresponding
fixed ideal circuit Cf ix , i.e. fC̃f ix = fCf ix . In particu- P (ĥ|j−1 ) ⊕ P (h|j−1 )
lar, conditioned on the first j − 1 measurement results,
it also reproduces the marginal distribution of the jth =[P (f |j−1 ) ⊕ P (ĥ|j−1 )] ⊕ [P (f |j−1 ) ⊕ P (h|j−1 )]
measurement result. =P (f |j−1 ) ⊕ P (h|j−1 ), (8)
Conditioned on the first j −1 measurement results, the
fixed circuit Cf ix and adaptive circuit C are identical and which is exactly the same as the final logical action for
have the same marginal distribution for the jth logical the decoding problem of the first j − 1th measurements.
measurement, for both the ideal and error-corrected case, Therefore, for this choice of λ|j , the first j − 1 measure-
i.e. fC = fCf ix , and fC̃ = fC̃f ix for a fixed frame repair ment results are consistent with the previous round of
decoding, proving property 1.
operator. Therefore, with frame repair operator λ̂, the
marginal distribution of the jth logical measurement for
the fixed circuit C˜f ix matches that of the ideal circuit III.3. Threshold Theorem
C. By Lemma 4, different choices of frame configuration
give rise to the same measurement distribution for a fixed
Using the preceding characterization of errors, we
circuit. In particular, if we can show the existence of a
prove our main result in this section, the existence of
frame repair operator λj that satisfies property 1, then
a threshold below which logical errors are exponentially
it will have the same marginal measurement distribution
suppressed in the code distance.
for the jth measurement under C˜f ix . Conditioned on
First, we reproduce a lemma that bounds the number
the previous j − 1 measurement results, this is the same
˜ thereby of connected clusters of a given size, a core component
as the marginal measurement distribution for C,
of a number of fault-tolerance proofs [1, 23–26]. We will
completing the proof of property 2.
make use of the presentation from Ref. [1], specializing
Let us now prove property 1. By our assumption,
to the case where the specific set is a single vertex, as is
the decoding problems of both the first j − 1 measure-
needed for the main theorem.
ment results and the first j measurement results also
satisfy the condition that the fault configuration has Lemma 9 (Counting lemma on vertices, Lemma 5 of
largest weight of any connected cluster less than d/t. By [23]). Consider a specific vertex α in a graph for which
Lemma 7, there exists a frame repair operation λ̂|j−1 and every vertex has degree at most v. Let Nv (s, α) be
 12

the number of connected sets containing α and a to- Suppose a given fault configuration involves s faults.
tal of s vertices (i.e. s − 1 vertices beyond α). Then As we are using the MLE decoder, this implies that the
Nv (s, α) ≤ (ve)s−1 , with e the usual base of the natural error e must involve at least ⌈s/2⌉ faults. Since each fault
logarithm. has probability at most p, the probability that this fault
configuration appears is at most
Using the counting lemma, we can now complete the
  " s  #
proof of our main theorem. Xs X s
s i
p ≤ ps/2 = 2s ps/2 . (11)
Theorem 10 (Fault tolerance of decoding strategy in i i
i=⌈s/2⌉ i=0
Def. 5). Consider a transversal realization C˜ of an ideal
quantum circuit C (Def. 2), subject to the local stochastic For each logical measurement, by Lemma 8, the fault
noise model with probability p, with the circuit involving configuration must involve a connected cluster of at least
at most B code blocks of an [[n, k, d]] CSS (r, c)-LDPC d/t faults. Therefore, applying Lemma 9 to Ξ consisting
quantum code family, T layers of operations, with a single of Nf vertices, the number of connected clusters Ns of
SE round following each operation, and M logical mea- size s is upper bounded by the sum of clusters which
surements. Then there exists a threshold p0 , such that for contain any given vertex:
p < 121
144 p0 , the probability Perr of either heralded errors
or regular logical errors for the entire circuit, when us- Ns ≤ Nf (ve)s−1 . (12)
d
ing the decoding strategy in Def. 5, is at most C(p/p0 ) 2t .
Here, d is the code distance, t is the maximal part size in By Lemma 8, if none of the first j rounds of decod-
1 M BT (4n−k) ing involve a connected cluster of size at least d/t, then
the transversal partition, p0 = (96ecr) 2, C = 4ecr .
the decoding strategy (Def. 5) will not output FAIL, and
First, let us count the number of possible fault loca- the output measurement distribution of the first j mea-
tions under our local stochastic error model. There are surement results will be the same as the ideal distribu-
nB physical qubits, each of which experiences at most 3 tion. Since there are M measurements in total, taking
types of errors (X, Y, Z), leading to 3nBT possible data the union bound, the total probability Perr of outputting
qubit fault locations. Each logical qubit has n − k inde- FAIL or having a logical error is at most
pendent stabilizer generators that we measure, so there ∞
X
are (n−k)B possible stabilizer measurement errors. Since Perr ≤ M Ns 2s ps/2
there are T layers of operations, the number of fault lo-
s=d/t
cations in the circuit is at most ∞
X √
Nf ≤ 3nBT + (n − k)BT = (4n − k)BT. (9) ≤M Nf (ve)s−1 (2 p)s
s=d/t
By definition, this is also the number of vertices in the √
M Nf (2ve p)d/t
syndrome adjacency graph Ξ. = √
Next, let us bound the number of neighboring vertices ve 1 − 2ve p
for any vertex in Ξ. By definition, the stabilizer weight √
M BT (4n − k) (96ecr p)d/t
is upper bounded by r ≥ 1, while the number of stabiliz- ≤ √
48ecr 1 − 96ecr p
ers each qubit is involved in is upper bounded by c ≥ 1.  d/2t
Therefore, each data qubit error can cause an error on at M BT (4n − k) p
≤ √ (13)
most c stabilizers. Since we focus on depth-one transver- 48ecr(1 − 96ecr p) 1/(96ecr)2
sal operations, each stabilizer is involved in at most four
detectors (at most 2 in the past and 2 in the future due The threshold is thus given by p0 = 1/(96ecr)2 , but
to the branching detectors for CNOTs). Therefore, each because the summation still goes to infinity exactly at
data qubit error is connected to at most 4c edges. Each the threshold, we choose to work below a slightly smaller
measurement error affects a single stabilizer, which is in- value than the threshold in order to have a finite con-
volved in at most four detectors, so the number of edges stant prefactor. The prefactor can be tuned if one con-
it is connected to is also upper bounded by 4c. Each strains the range of error rates p differently. Choosing
detector consists of at most three stabilizers for a depth- p < (11/12)2 p0 , we have
one transversal operation, each of which is connected to  d/2t
at most r qubits, where each qubit has at most three p
types of elementary errors under a depolarizing channel. Perr ≤C , (14)
p0
Together with the three measurement errors on the sta-
bilizers, each hyperedge is connected to at most 9r + 3 where
error types. Putting this together, the number of neigh- 1
boring vertices for any vertex in Ξ is upper bounded by p0 = , (15)
the constant (96ecr)2
M BT (4n − k)
v ≤ 4c(9r + 3) ≤ 48cr. (10) C= . (16)
4ecr
 13

This theorem demonstrates that below a certain physi-

cal error threshold, the logical error rate is exponentially
suppressed in the code distance. Thus, despite never re-
Deterministic
quiring d rounds of syndrome measurement anywhere in X stabilizers
the circuit, we can still maintain fault-tolerance. As is
the case with threshold proofs, many of the bounds here
are loose and the actual threshold will be much higher, as
we demonstrated numerically. While we assumed magic
state inputs with known stabilizer values for this theo-
rem, we expect that the same techniques, when applied
jointly to magic state distillation and the main computa-
tion, will still yield a Θ(d) saving, as discussed in Meth-
ods. Deterministic
Z stabilizers
The logical error rate of our protocol scales linearly
with the space-time volume of the original circuit. As
only a single SE round follows each operation, another FIG. 3. Illustration of logical qubit growth process for the
potential benefit of our approach is that there are fewer surface code. The initial d1 = 3 logical qubit, located on the
top right, is grown into a larger logical qubit with d = 5 by
potential error locations, which may lead to a more fa-
initializing the qubits in the top left in |+⟩ and the bottom
vorable constant factor for the logical error rate. This right in |0⟩. The strips indicated in red have deterministic
can partially offset any reduction in the threshold, which stabilizer values, which leads to a lower bound on the weight
our numerics find to be rather minimal. of an undetectable logical error.
We can directly apply this theorem to the case of the
surface code, plugging in the specific constants. This
leads to the following theorem: to the full distance d in a single EC round. We will
show that despite growing the patch in a single step,
Theorem 11 (Fault tolerance for any ideal quantum cir- the information provided by transversal measurements
cuit with magic state inputs). Consider a surface code still allows us to maintain a code distance of d1 . Our
transversal realization C˜ of an ideal quantum circuit C discussion focuses on the surface code case, although it
(Def. 3), subject to the local stochastic noise model with is likely that this can be extended to other scenarios.
probability p, with the circuit involving at most B code
Definition 12 (Single-shot patch growth). Given an
blocks of a [[d2 + (d − 1)2 , 1, d]] non-rotated surface code,
ideal quantum circuit C with magic state inputs and feed-
T layers of operations, with a single SE round follow-
forward operations (Def. 1), we define its surface code
ing each operation, and M logical measurements. Then
transversal realization with reduced magic state inputs
there exists a threshold p0 , such that for p < 121 144 p0 , the Cm , with distances (d, d1 ), as the surface code transversal
probability Perr of either heralded errors or regular logi-
realization of distance d defined in Def. 3, together with
cal errors for the entire circuit, when using the decoding
d the following operations:
strategy in Def. 5, is at most C(p/p0 ) 4 . Here, d is the
1 M BT d2 1. Initialization of some sets of logical qubits of dis-
code distance, p0 = (1536e) 2, C = 8e .
tance d1 ≤ d in state |T ⟩ = T |+⟩, and with all
For the non-rotated surface code, we have n = d2 + stabilizer values fixed to +1, up to local stochastic
(d − 1)2 ≤ 2d2 , r = c = 4, t = 2. t = 2 comes from the noise on each physical qubit of strength p.
fold-transversal S gate, leading to a d/4 scaling exponent, 2. Logical qubit block growth [27, 28] from distance d1
but this can likely be improved with more careful error to d, by performing the initialization in the pattern
analysis. Plugging this into Eqs. (15,16), we have shown in Fig. 3 and performing one SE round.
1 1 We now extend our key lemma characterizing the
p0 = = (17) corrections on measurements for low weight errors,
(96ecr)2 (1536e)2
Lemma 7, to this setting with magic state inputs of dis-
M BT (4n − k) 8d2 M BT M BT d2
C= ≤ = . (18) tance d1 . Here, we use the same decoding strategy de-
4ecr 64e 8e fined in Def. 5. The statement and proof is essentially
the same as before, except the distance d is replaced by
d1 ≤ d, the size of the magic state input. This still goes
beyond previous work, as the code deformation is per-
III.4. Single-Shot Patch Growth formed in a single round rather than over d rounds.
Lemma 13 (Correction on codespace for low weight
We now extend our results to the case where the magic faults, with patch growth). Consider the jth logical mea-
state input has a smaller code distance d1 that is grown surement and the associated syndrome adjacency graph
 14

Ξ|j in a given execution of the transversal realization with

reduced magic state inputs C˜m . Consider any fault con-
figuration f = e ⊕ κ in Ξ|j , where the largest weight of
any connected cluster of error vertices is less than d1 /t.
Then there exists a choice of frame repair operator λ̂,
such that the combined effect of fault configuration and
|ψ⟩L
frame configuration P (e ⊕ κ) ⊕ P (g ⊕ λ̂) does not flip the
results of any of the j logical measurements.

The proof is analogous to that of Lemma 7. The only

modification is that there are additional frame variables
on the logical qubits with magic state input, correspond-
ing to the randomly initialized stabilizers during patch
growth, but these do not have an associated frame log- |+⟩
ical variable, as the magic state can be in an arbitrary
input state. MZZ
The frame variables that these randomly initialized |+⟩
stabilizers correspond to are spatially localized. There- MZZ
fore, in the basis of Z stabilizers/X errors that is rele-
|+⟩
vant to our initialization and measurement, they can only
produce operations away from the deterministic region, MZZ
and cover d − d1 rows. Meanwhile, all Z stabilizers in |+⟩
the region highlighted in red in Fig. 3 are determinis- MZZ
tic, and a chain of errors that spans this region, in or-
der to produce a logical error, must have weight at least |+⟩
d1 . By Lemma 6, each fault throughout the circuit can
propagate to at most t errors on the final measurement.
Therefore, any fault configuration of weight d1 /t must
have trivial logical action on the measured logical qubits. FIG. 4. Repetition code example. The bottom logical qubit is
prepared via a single round of stabilizer measurements, and
then executes a transversal CNOT on the top logical qubit
Using this lemma, we can generalize the rest of our |ψ⟩L . Although the state preparation of the bottom logical
results to prove an analogous fault tolerance theorem, qubit is not fault-tolerant in the conventional sense, we are
with the distance replaced by the reduced distance of the still able to reproduce the logical measurement statistics of
magic state input. Moreover, examining the logical er- an ideal circuit with high probability as the distance d → ∞.
ror events of weight d1 suggest that they are localized
near the small patch input, so most of the circuit is still
protected with the full code distance d. We leave a de- cause we have not gained sufficient confidence about the
tailed analysis of these low weight errors, in the context ZZ stabilizer values from the single faulty measurement,
of magic state factories and error suppression scaling, to and therefore may incorrectly pair up excitations, poten-
future work. Such an analysis would establish a complete tially causing a larger string of X errors. Importantly,
fault tolerance theorem for universal quantum comput- however, it is not yet necessary to fix the stabilizer val-
ing, with noisy magic states directly as input. ues back to the code space, as we have not yet performed
a logical measurement. The transversal logical measure-
ment later on will help us avoid harmful long X error
IV. EXAMPLE: REPETITION CODE strings due to its reliable syndrome information.
We then perform a transversal CNOT, with the second
We now consider a simple illustrative example of the logical qubit as control and first logical qubit as target.
fault-tolerance approach. For illustration purposes, we Following this, we measure the first logical qubit in the Z
will focus on a repetition code example [29], although basis. With Pauli feedforward, this circuit can teleport
the lessons readily generalize to the surface code. the unknown state |ψ⟩ to the second logical qubit.
Consider two repetition code logical qubits. The first is At this point, we may naively be concerned about
prepared in an unknown logical quantum state |ψ⟩, while the correctness of the first measurement result, since the
the second logical qubit is prepared in a single-shot man- string of X errors can lead to a probability linear in the
ner in the |+⟩ state, by preparing all physical qubits in physical error rate p of flipping this measurement result.
|+⟩ and measuring neighboring ZZ stabilizers once. At However, the situation is a bit more subtle: when defining
this stage, the physical state of the second logical qubit is correctness of a quantum computer execution in a model
in fact a mixture of product states [30] if we try to directly of classical inputs and outputs, what we really care about
fix the stabilizer values back to the code space. This is be- is that the ideal measurement distribution is reproduced,
 15

rather than a given shot being interpreted in a particular anti-commute with some Pauli initialization are random,
way. In the circuit that we are executing here, the logi- and therefore their distribution does not get affected by
cal CNOT propagates the randomness to the first logical logical flips. Products that commute with all Pauli ini-
qubit, and thus the measurement result will be a 50/50 tializations, on the other hand, are insensitive to the large
random number. By itself, flipping the logical readout error string due to the commutation, and therefore are
result therefore does not change the measurement distri- not affected either. Because Pauli initializations propa-
bution of the first logical qubit measurement, and so in a gate to Pauli products through the Clifford circuit, and
sense, the long X error string does not yet cause a logi- all logical measurements are in the Pauli basis, the two
cal error at this stage. More broadly, consider any logical must either commute or anti-commute.
measurement where we may be worried about large er- When we now measure the second logical qubit, in our
ror strings from some Pauli initialization. In order for decoding strategy, we will re-decode the existing portion
the error string to have an effect, the initialized Pauli of our circuit. This may cause a different assignment of
stabilizer, upon propagating through the Clifford circuit, the first logical measurement result. However, we can ap-
must anti-commute with the logical measurement. This, ply an X operation at initialization on the second logical
however, implies that the measurement result was ran- qubit, which doesn’t change the |+⟩ state. Propagat-
dom, so a flip of the measurement result does not change ing this X flip through, this will flip both logical mea-
the measurement distribution. surement results, flipping the first measurement back to
Although the measurement distribution for the first being consistent with the previous measurement, while
logical qubit is unchanged, this does not yet mean the also flipping the second measurement result. We thus in-
whole circuit is executed correctly: we still need to guar- terpret the second measurement result as having taken
antee that the joint distribution between all logical mea- the flipped value, so that we maintain consistency with
surements is the same as the ideal circuit. To under- the first measurement. With this method, our theorem
stand this, we need to provide more specification on our shows that the measurement distribution of the noisy cir-
unknown state |ψ⟩. In particular, we need to specify cuit can be made arbitrarily close to the ideal circuit, as
whether we have already prepared it in a fault-tolerant the code distance is increased.
fashion, such that the residual noise on it is local stochas-
tic, or whether some of the stabilizers have not yet been
fault-tolerantly assigned.
V. EXAMPLE: NON-CLIFFORD OPERATIONS
First, consider the former case, where we have already
fault-tolerantly prepared the unknown magic state |ψ⟩
through some method. For the surface code, this may In this section, we discuss the example in Fig. 2 of
come from another circuit that involved e.g. magic state main text in more detail, where we perform |T ⟩ state
distillation. The transversal measurement of the first log- teleportation and feed-forward operations.
ical qubit reveals information about the product of sta- Again, one might be worried about making an incorrect
bilizers at the same location on the two logical qubits, commitment to the measurement result used for telepor-
up to local stochastic errors, since we directly measure tation, since a non-trivial feed-forward S gate has been
the physical qubits and therefore errors can be regarded applied (Fig. 2(b) of main text). However, as illustrated
as data errors rather than syndrome errors. Since we in Fig. 2(c) and discussed throughout our paper, applying
know the stabilizers of the first logical qubit with only an X on the |+⟩ initial state does not change the state.
local stochastic errors, we have also effectively made in- Propagating this through, we find that the combination
ferences about the stabilizer initialization values of the of an X operator on the bottom qubit and a Y on the
second logical qubit. middle qubit also stabilizes the state. Thus, if we infer a
In the second case where the first logical qubit also has different logical measurement result for the bottom qubit
unknown stabilizer initialization values, its preparation later on, we can flip it back to our originally-committed
must trace back to some Pauli basis input state. For ex- result, as long as we also apply a Y to the middle qubit.
ample, consider the case where the first logical qubit was Another possible concern is how a logical measurement
also initialized in a single step in |+⟩. The transversal result that, due to a magic state input, is no longer de-
logical measurement still reveals information about the terministic or 50/50 random would be affected by the
product of stabilizers, but now we no longer learn the ini- non-fault-tolerant Pauli basis initialization. However, as
tialization values of each of the stabilizers. Fortunately, discussed in the previous section, a logical measurement
this is not a concern, as only the product of stabilizers is that can be affected by the large error string originat-
relevant to interpreting the logical measurement result. ing from a Pauli basis initialization must by necessity,
Later logical measurements will give us additional infor- also anti-commute with the initial logical stabilizer, en-
mation that will allow us to learn the individual values suring that it will be a 50/50 random variable. This is
of stabilizers when they are necessary. Indeed, we can indeed the case for the circuit illustrated in Fig. 2 of the
extend the intuition of anti-commutation between logi- main text. Otherwise, the relevant basis has determin-
cal measurements and logical Pauli stabilizers discussed istic stabilizers to begin with on all input logical qubits,
above. Products of multiple logical measurements that and errors can be appropriately detected and corrected.
 16

VI. ANALYSIS OF SINGLE-ROUND LATTICE is contained in noisy syndrome measurements for lattice
SURGERY surgery, thereby necessitating repetition before one can
gain confidence about the results.
In this section, we analyze single-round lattice surgery
in more detail, and explain why unlike the transversal
case, it is not fault-tolerant. We note that our example VII. DETAILS OF NUMERICAL SIMULATIONS
is very similar to the one discussed in Appendix D of
Ref. [31]. Our analysis indicates that the scheme pro- Here we describe the numerical simulations conducted
posed there is not fault-tolerant, although suitable modi- to evaluate the performance of our decoding strategy. To
fications based on transversal algorithmic fault tolerance simulate a logical circuit, we first generate a description
should be able to recover most of their conclusions. of the physical circuit and noise model using Stim [22],
We analyze a variant of the circuit shown in Fig. 3 of an open-source Clifford simulation package. From this
the main text. Here, instead of preparing the bottom description, we specify the detectors and logical observ-
three qubits in |0⟩, we prepare them in some arbitrary ables of the circuit. Because in practice Stim requires log-
quantum state |ψ⟩, with known stabilizer values up to ical observables to be deterministic under noiseless exec-
local stochastic noise. This closely mirrors the typical tution, we label non-deterministic logical observables as
situation in a deep circuit. We perform a transversal gauge detectors, whose ideal measurement outcome can
CNOT from the GHZ state to three qubits initialized in be non-deterministic. We then use Stim to Monte-Carlo
|ψ⟩, and then measure the original GHZ qubits in the sample the detectors and logical observables over differ-
X basis. With a Z feed-forward on each qubit, the cor- ent physical noise realizations. Each sample is decoded
relations of the GHZ state are now imprinted onto the using our decoding strategy, with each logical measure-
bottom 3 qubits. However, with state preparation based ment interpreted using only the partial syndrome infor-
on lattice surgery, knowledge of the specific GHZ state mation up to that point, and a logical error is observed if
we prepare relies on obtaining the product of values of either a heralded inconsistency or a regular logical error
Z stabilizers of the larger surface code patch, along the occured. The logical error rate for a given circuit is com-
seams between the different logical qubits. More specifi- puted from the mean over many Monte-Carlo samples,
cally, labeling the logical qubits with 1 to 3 from top to and the error bars correspond to the Clopper-Pearson
bottom, the correlator Z 1 Z 2 is initialized to a random confidence interval based on a Beta distribution with a
value when we perform the initial random projection of significance level of 0.05.
the larger surface code. In the absence of errors, this cor- We specify the physical operations used to generate
relator will be equal to the product of Z stabilizers along the rotated surface code logical operations following Def-
the corresponding boundary. However, a single measure- inition 3. In addition to these operations, we also allow
ment error can cause us to misinterpret Z 1 Z 2 , and we physical measurements and initialization in the X basis
have no way of obtaining and correcting this error later (rather than using a H operation plus measurement or
on. Therefore, in the case of single-shot lattice surgery, initialization in the Z basis). We perform a SE round by
a single physical error can lead to a logical error. Note using a sequence of four physical CNOTs to map each
that we measure the GHZ state in the X basis, so that stabilizer value to an ancilla qubit, using the gate or-
it is not possible to deduce Z 1 Z 2 directly through the dering described in Ref. [32]. Because our main result
logical measurements. enables O(1) rounds of SE between transversal CNOTs,
We can contrast this with our transversal algorithmic we have flexibility in where SE is performed within the
fault tolerance construction. In this case, even if later circuit. In Figs. 3(a-b) and Fig. 4(c-d), for example, we
decoding steps assign a different logical measurement re- perform one SE round after each transversal CNOT on
sult to the ancilla qubit, we can apply a frame logical the logical qubits involved in the gate. In contrast, no
variable to obtain the same result as our previous com- intermediate SE rounds are performed in Fig. 3(d).
mitment. The transversal measurement also ensures that We add noise to each physical operation using a circuit-
no harmful error events can terminate on the measure- level noise model similar to Ref. [33]. Concretely, for a
ment time boundary, and therefore there are no time-like chosen physical error rate p, we add a depolarizing chan-
errors that flip the logical measurement result, as occurs nel with probability p to each physical operation. We
in the case of lattice surgery. Thus, single-shot logical apply a two-qubit depolarizing channel after each entan-
operations are fault-tolerant in the transversal scheme, gling gate, a single-qubit depolarizing channel after each
but not in the case of lattice surgery. single-qubit gate and initialization, and a single-qubit de-
A key distinction between our transversal construction polarizing channel before each measurement. In contrast
and lattice surgery is thus how the logical information is to Ref. [33], we do not apply noise to idling qubits during
measured. For transversal gates, we always directly ac- measurement and initialization. However, we do apply a
cess the logical information through transversal measure- single-qubit depolarizing channel to idling qubits during
ments, in the process obtaining the relevant information gate operations.
to process and correct errors and interpret logical mea- For the |Y ⟩ state distillation factory simulations in
surements correctly. In contrast, the logical information Fig. 4 of the main text, we perform state injection from
 17

the corner qubit at distance d0 = 3 (Fig. 4b), following (a) (b)

the procedure described in Ref. [28]. More precisely, we
perform two rounds of SE during the first phase of state

Logical error rate

injection, growing the patch size from one to d0 , and post-
select on having consistent stabilizer values between the
two rounds as well as the correct stabilizer value for the
deterministically-initialized stabilizers. Then we perform
the single step patch growth from distance d0 to d1 . In
order to probe the performance of the state distillation
factory without prohibitive sampling costs, we add ex-
tra Z errors with probability pZ on the injected physical
qubit to increase the error rate. The output state in-
fidelity is probed by performing a noiseless S rotation
via S gate teleportation with a noiseless-injected ancilla FIG. 5. Numerical results for decoding repeated Bell pair
patch and performing an X basis measurement. measurements with the belief-HUF and MLE decoders. (a)
For the single-level distillation factory simulations, we The total logical error rate decreases with the code distance
set d0 = 3 and vary d1 in the set {3, 5, 7, 9}. Each data at p = 0.56% for belief-HUF and at 0.85% for MLE (top); the
point in Fig. 4(c) represents 105 samples after post- same trend at p = 0.1% (bottom). (b) The total logical error
selection during the state injection step. After gener- rate as a function of the physical error rate for belief-HUF
and MLE.
ating a sample of measurement results that succeeded in
all state injection checks, we first partially decode the
logical Z basis measurements on all injected qubits and
logical X basis measurements on the remaining qubits
other than the output qubit to filter out factory failures.
Then, we decode all qubits to estimate the output in-
fidelity of the |Y ⟩ state. For the two-level distillation scribed as follows. We generate the partial decoding
factory simulation, the input states of the second-level hypergraph Γ|j as well as its decomposed version Γ′ |j
factory are the output states from the first-level factories at each partial decoding step j. Here, Γ′ |j , which con-
followed by a single step patch growth from distance d1 tains essential hyperedges only, can be generated by set-
to d2 . We set d0 = 3, d1 = 5, and d2 = 9. To decode the ting decompose errors = True in Stim from Γ|j [22].
two-level factory efficiently in practice, we first sample Given a sampled detector configuration, we first perform
measurement results for the entire circuit. We then de- bp rounds = 5 rounds of belief propagation to update the
code each level-1 factory and discard runs in which any posterior probabilities of error mechanisms for Γ|j and
of the physical state injections or level-1 factories failed, transfer these probabilities into Γ′ |j . Finally, we apply
in order to reduce the computational cost. For instances a hypergraph union-find decoder on Γ′ |j with the hyper-
where all level-1 factories succeeded, we perform corre- parameter weight exponent = 0 to obtain the decoded
lated decoding on the entire level-2 factory, with the out- logical observables [21].
put |Y ⟩ state rotation and measurement, to determine
the output and estimate the logical error rate. Assuming Fig. 3a in the main text presents the total logical er-
pZ = 10% and p = 0.1%, we obtain 99620000 raw shots ror rate PL , which is the probability of either a heralded
in total, of which 312825 shots passed all factory checks, error or a regular logical error occurring, as a function
and 3 logical errors were observed. of the physical error rate p, using the MLE decoder. In
As the state injection protocol itself is noisy, the infi- Fig. 5(b), we show the corresponding results for belief-
delity of the injected logical state pinj is greater than pZ . HUF as well. These simulations imply the presence of
In order to estimate the infidelity of the input logical |Y ⟩ a threshold when using the belief-HUF decoder in prac-
state, we simulate the state injection protocol itself by in- tice. As the total logical error rates approach their up-
jecting a |Y ⟩ state, followed by a perfect S gate and an X per bounds at physical error rates near the thresholds,
basis measurement described above. All input infidelities we cannot precisely estimate the threshold by fitting
in Fig. 4(c-d) refer to pinj instead of pZ . the universal scaling hypothesis. Nevertheless, we can
Finally, our main Theorem assumes that partial de- still estimate a lower bound of the belief-HUF and MLE
coding is performed using the MLE decoder, which in thresholds by identifying the highest physical error rate
practice may have a runtime that grows exponentially at which PL monotonically decreases as d increases, as
with the size of the decoding problem. However, in shown in Fig. 5(a). We estimate that the threshold for
practice we find that our decoding strategy still yields the MLE decoder is ≳ 0.85% and for the belief-HUF de-
a threshold with belief propagation augmented hyper- coder is ≳ 0.56%, consistent with previous simulation
graph union find (belief-HUF), an efficient decoder which results [21]. We expect future optimizations of the de-
runs in polynomial time [21, 34]. The detailed im- coder to further improve the performance and bring it
plementation of belief-HUF for partial decoding is de- closer to the MLE decoder.
 18

VIII. COMPARISON WITH EXISTING rection gadgets, rather than the complete end-to-end al-
APPROACHES TO SINGLE-SHOT QUANTUM gorithmic context. This is in contrast to our FT strategy,
ERROR CORRECTION which uses all accessible information throughout the al-
gorithm, and analyzes the fault tolerance of logical opera-
In this section, we contrast our approach with exist- tions. Our scheme thus has much more forgiving require-
ing approaches to single-shot quantum error correction. ments on the code properties, and can serve as a drop-in
We highlight the crucial distinction between single-shot replacement to existing compilation schemes with an im-
quantum error correction, which analyzes an error cor- mediate space-time overhead reduction.
rection gadget individually, and single-shot logical oper-
ations, which applies also to logical operations and ana-
lyzes fault tolerance as a whole.
The concept of single-shot quantum error correction
was originally proposed by Bombin [24]. Here, redundan-
cies are present in the syndrome extraction results, allow-
ing one to robustly infer the actual stabilizer values up to
small residual errors, in a fashion similar to classical error
correction on the syndrome readings. These ideas were
later extended to certain families of quantum low-density
parity-check (qLDPC) codes [35–38], where expansion
and the so-called confinement property lead to single-
shot QEC for quantum memories. In this case, however,
there are usually no stabilizer redundancies, and so the
randomly initialized stabilizer values cannot be reliably
inferred in the conventional FT strategies. Here, one only
guarantees that the output error after a round of error
correction is controlled if both the input error and added
noise are controlled, and one may still require d rounds
of repetition to learn the initialized values of the stabi-
lizers with sufficient confidence for the individual state
preparation gadget.
When considering a full-fledged FTQC, the time cost
may be modified, and logical operations are often no
longer single-shot. As mentioned above, state initializa-
tion for LDPC codes using conventional FT construc-
tions may require d rounds of repetition, as the values
of randomly initialized stabilizers need to be learned re-
liably. Moreover, the most general methods for perform-
ing logical operations on LDPC codes make use of lat-
tice surgery, which also requires d rounds of syndrome
extraction to maintain FT [39, 40], similar to the lattice
surgery example for the surface code we analyzed. There-
fore, logical gates typically require order of d time cost.
The same consideration also applies to other constant-
space-overhead schemes, such as those based on code
concatenation [41]. Many logical operations can be im-
plemented in 3D codes in a single-shot fashion, but the
space usage scales as d3 , effectively corresponding to a
space-time trade-off when compared to the conventional
surface code scheme and not leading to a clear advan-
tage [42]. As such, while there are multiple approaches
with potential promise to produce lower space-time over-
head when implementing a generic quantum circuit, to
the best of our knowledge, further research is required to
show an end-to-end space-time overhead reduction when
compared to the standard surface code schemes based on
lattice surgery.
In conclusion, single-shot QEC focuses on the fault-
tolerance and error-reducing effect of individual error cor-
 19

[1] D. Gottesman, Fault-Tolerant Quantum Computation tioning qubits in hypergraph product codes to implement
with Constant Overhead, Quantum Information and logical gates, arXiv preprint arXiv:2204.10812 (2022).
Computation 14, 1338 (2013). [20] S. Bravyi and A. Kitaev, Universal quantum computa-
[2] A. Kitaev, Unpaired Majorana Fermions in Quan- tion with ideal Clifford gates and noisy ancillas, Physical
tum Wires, arXiv preprint arXiv:cond-mat/0010440 Review A 71, 022316 (2005).
10.1070/1063-7869/44/10S/S29 (2000). [21] M. Cain, C. Zhao, H. Zhou, N. Meister, J. Pablo,
[3] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. B. Ataides, A. Jaffe, D. Bluvstein, and M. D. Lukin, Cor-
Cleland, Surface codes: Towards practical large-scale related decoding of logical algorithms with transversal
quantum computation, Physical Review A 86, 032324 gates, arXiv preprint arXiv:2403.03272 (2024).
(2012). [22] C. Gidney, Stim: a fast stabilizer circuit simulator, Quan-
[4] H. Bombin and M. A. Martin-Delgado, Topological quan- tum 5, 10.22331/q-2021-07-06-497 (2021).
tum distillation, Physical Review Letters 97, 180501 [23] P. Aliferis, D. Gottesman, and J. Preskill, Accuracy
(2006). threshold for postselected quantum computation, Quan-
[5] J. P. Tillich and G. Zemor, Quantum LDPC codes with tum Information and Computation 8, 181 (2007).
positive rate and minimum distance proportional to the [24] H. Bombı́n, Single-shot fault-tolerant quantum error cor-
square root of the blocklength, IEEE Transactions on rection, Physical Review X 5, 031043 (2015).
Information Theory 60, 1193 (2014). [25] A. A. Kovalev and L. P. Pryadko, Fault tolerance of quan-
[6] N. P. Breuckmann and J. N. Eberhardt, Quantum tum low-density parity check codes with sublinear dis-
Low-Density Parity-Check Codes, PRX Quantum 2, tance scaling, Physical Review A - Atomic, Molecular,
10.1103/prxquantum.2.040101 (2021). and Optical Physics 87, 020304 (2013).
[7] S. Bravyi and M. B. Hastings, Homological [26] A. Kubica and M. Vasmer, Single-shot quantum error
Product Codes, arXiv preprint arXiv:1311.0885 correction with the three-dimensional subsystem toric
10.48550/arxiv.1311.0885 (2013). code, Nature Communications 2022 13:1 13, 1 (2022).
[8] M. B. Hastings, J. Haah, and R. O’Donnell, Fiber bundle [27] Y. Li, A magic state’s fidelity can be superior to the
codes: Breaking the n1/2polylog(n) barrier for Quantum operations that created it, New Journal of Physics 17,
LDPC codes, in Proceedings of the Annual ACM Sympo- 023037 (2015).
sium on Theory of Computing (2021) pp. 1276–1288. [28] L. Lao and B. Criger, Magic state injection on the rotated
[9] N. P. Breuckmann and J. N. Eberhardt, Balanced Prod- surface code, ACM International Conference Proceeding
uct Quantum Codes, IEEE Transactions on Information Series , 113 (2022).
Theory 67, 6653 (2020). [29] J. Haah, What is Your Logical Qubit, in Simon’s Insti-
[10] P. Panteleev and G. Kalachev, Quantum LDPC Codes tute Workshop on Advances in Quantum Coding Theory
with Almost Linear Minimum Distance, IEEE Transac- (Simons Institute for the Theory of Computing, 2024).
tions on Information Theory 68, 213 (2022). [30] M. B. Hastings, Topological order at nonzero tempera-
[11] P. Panteleev and G. Kalachev, Asymptotically good ture, Physical Review Letters 107, 210501 (2011).
Quantum and locally testable classical LDPC codes, Pro- [31] I. H. Kim, Y. H. Liu, S. Pallister, W. Pol, S. Roberts,
ceedings of the Annual ACM Symposium on Theory of and E. Lee, Fault-tolerant resource estimate for quantum
Computing , 375 (2022). chemical simulations: Case study on Li-ion battery elec-
[12] A. A. Kovalev and L. P. Pryadko, Quantum ”hyperbicy- trolyte molecules, Physical Review Research 4, 023019
cle” low-density parity check codes with finite rate, Phys- (2022).
ical Review A - Atomic, Molecular, and Optical Physics [32] R. Acharya, I. Aleiner, R. Allen, T. I. Andersen, M. Ans-
88, 10.1103/PhysRevA.88.012311 (2012). mann, F. Arute, K. Arya, A. Asfaw, J. Atalaya, R. Bab-
[13] S. Bravyi, A. W. Cross, J. M. Gambetta, D. Maslov, bush, D. Bacon, J. C. Bardin, J. Basso, A. Bengts-
P. Rall, and T. J. Yoder, High-threshold and low- son, S. Boixo, G. Bortoli, A. Bourassa, J. Bovaird,
overhead fault-tolerant quantum memory, Nature 627, L. Brill, M. Broughton, B. B. Buckley, D. A. Buell,
778 (2024). T. Burger, B. Burkett, N. Bushnell, Y. Chen, Z. Chen,
[14] B. Eastin and E. Knill, Restrictions on Transversal En- B. Chiaro, J. Cogan, R. Collins, P. Conner, W. Court-
coded Quantum Gate Sets, Physical Review Letters 102, ney, A. L. Crook, B. Curtin, D. M. Debroy, A. D. T.
110502 (2009). Barba, S. Demura, A. Dunsworth, D. Eppens, C. Er-
[15] T. Jochym-O’Connor, A. Kubica, and T. J. Yoder, Dis- ickson, L. Faoro, E. Farhi, R. Fatemi, L. F. Burgos,
jointness of Stabilizer Codes and Limitations on Fault- E. Forati, A. G. Fowler, B. Foxen, W. Giang, C. Gid-
Tolerant Logical Gates, Physical Review X 8, 021047 ney, D. Gilboa, M. Giustina, A. G. Dau, J. A. Gross,
(2018). S. Habegger, M. C. Hamilton, M. P. Harrigan, S. D. Har-
[16] A. Kubica, B. Yoshida, and F. Pastawski, Unfolding the rington, O. Higgott, J. Hilton, M. Hoffmann, S. Hong,
color code, New Journal of Physics 17, 083026 (2015). T. Huang, A. Huff, W. J. Huggins, L. B. Ioffe, S. V.
[17] J. E. Moussa, Transversal Clifford gates on folded Isakov, J. Iveland, E. Jeffrey, Z. Jiang, C. Jones, P. Juhas,
surface codes, Physical Review A 94, 10.1103/phys- D. Kafri, K. Kechedzhi, J. Kelly, T. Khattar, M. Khezri,
reva.94.042316 (2016). M. Kieferová, S. Kim, A. Kitaev, P. V. Klimov, A. R.
[18] N. P. Breuckmann and S. Burton, Fold-Transversal Klots, A. N. Korotkov, F. Kostritsa, J. M. Kreikebaum,
Clifford Gates for Quantum Codes, arXiv preprint D. Landhuis, P. Laptev, K.-M. Lau, L. Laws, J. Lee,
arXiv:2202.06647 (2022). K. Lee, B. J. Lester, A. Lill, W. Liu, A. Locharla,
[19] A. O. Quintavalle, P. Webster, and M. Vasmer, Parti- E. Lucero, F. D. Malone, J. Marshall, O. Martin, J. R.
 20

McClean, T. Mccourt, M. McEwen, A. Megrant, B. M. for adversarial noise, Quantum Science and Technology
Costa, X. Mi, K. C. Miao, M. Mohseni, S. Montazeri, 4, 025006 (2019).
A. Morvan, E. Mount, W. Mruczkiewicz, O. Naaman, [37] O. Fawzi, A. Grospellier, and A. Leverrier, Constant
M. Neeley, C. Neill, A. Nersisyan, H. Neven, M. New- overhead quantum fault-tolerance with quantum ex-
man, J. H. Ng, A. Nguyen, M. Nguyen, M. Y. Niu, T. E. pander codes, Proceedings - Annual IEEE Symposium on
O’Brien, A. Opremcak, J. Platt, A. Petukhov, R. Potter, Foundations of Computer Science, FOCS 2018-Octob,
L. P. Pryadko, C. Quintana, P. Roushan, N. C. Rubin, 743 (2018).
N. Saei, D. Sank, K. Sankaragomathi, K. J. Satzinger, [38] S. Gu, E. Tang, L. Caha, S. H. Choe, Z. He, and A. Ku-
H. F. Schurkus, C. Schuster, M. J. Shearn, A. Shorter, bica, Single-shot decoding of good quantum LDPC codes,
V. Shvarts, J. Skruzny, V. Smelyanskiy, W. C. Smith, arXiv preprint arXiv:2306.12470 (2023).
G. Sterling, D. Strain, M. Szalay, A. Torres, G. Vidal, [39] L. Z. Cohen, I. H. Kim, S. D. Bartlett, and B. J. Brown,
B. Villalonga, C. V. Heidweiller, T. White, C. Xing, Z. J. Low-overhead fault-tolerant quantum computing using
Yao, P. Yeh, J. Yoo, G. Young, A. Zalcman, Y. Zhang, long-range connectivity, Science Advances 8, 10.1126/sci-
and N. Zhu, Suppressing quantum errors by scaling a sur- adv.abn1717 (2022).
face code logical qubit, arXiv preprint arXiv:2207.06431 [40] Q. Xu, J. P. Bonilla Ataides, C. A. Pattison, N. Raveen-
10.48550/arxiv.2207.06431 (2022). dran, D. Bluvstein, J. Wurtz, B. Vasić, M. D. Lukin,
[33] O. Higgott, T. C. Bohdanowicz, A. Kubica, S. T. Flam- L. Jiang, and H. Zhou, Constant-overhead fault-tolerant
mia, and E. T. Campbell, Improved Decoding of Circuit quantum computation with reconfigurable atom arrays,
Noise and Fragile Boundaries of Tailored Surface Codes, Nature Physics 10.1038/s41567-024-02479-z (2024).
Physical Review X 13, 031007 (2023). [41] H. Yamasaki and M. Koashi, Time-Efficient
[34] N. Delfosse, V. Londe, and M. E. Beverland, Toward a Constant-Space-Overhead Fault-Tolerant Quan-
Union-Find Decoder for Quantum LDPC Codes, IEEE tum Computation, arXiv preprint arXiv:2207.08826
Transactions on Information Theory 68, 3187 (2022). 10.48550/arxiv.2207.08826 (2022).
[35] A. O. Quintavalle, M. Vasmer, J. Roffe, and [42] M. E. Beverland, A. Kubica, and K. M. Svore, Cost of
E. T. Campbell, Single-shot error correction of three- Universality: A Comparative Study of the Overhead of
dimensional homological product codes, PRX Quantum State Distillation and Code Switching with Color Codes,
2, 10.1103/prxquantum.2.020340 (2020). PRX Quantum 2, 020341 (2021).
[36] E. T. Campbell, A theory of single-shot error correction