# Improved performance of the Bacon-Shor code with Steane’s syndrome
extraction method

Guillermo Escobar-Arrieta  Escuela de Física, Universidad de Costa Rica, San
José 2060, Costa Rica  Escuela de Ingeniería Eléctrica, Universidad de Costa
Rica, San José 2060, Costa Rica<EMAIL_ADDRESS>Mauricio
Gutiérrez  Escuela de Química, Universidad de Costa Rica, San José 2060, Costa
Rica<EMAIL_ADDRESS>
###### Abstract

We compare Steane’s and Shor’s syndrome extraction methods on the Bacon-Shor
code. We propose a straightforward strategy based on post-selection to prepare
the logical $|0\rangle_{L}$ and $|+\rangle_{L}$ states of the Bacon-Shor code
by using flag-like qubits to verify their constituent Greenberger-Horne-
Zeilinger states. We perform stabilizer simulations with a depolarizing Pauli
error model and find that Steane’s method significantly outperforms Shor’s.
Not only does Steane’s method result in pseudo-thresholds that are about 1
order of magnitude higher than Shor’s, but also its advantage increases
monotonically as we go from a distance-3 to a distance-9 Bacon-Shor code. The
advantage of Steane’s method is the greatest in the regime where gate errors
dominate over measurement errors. Some of the circuit constructions we propose
for Steane’s method are not formally fault-tolerant, yet outperform the
formally fault-tolerant Shor’s protocols for experimentally relevant physical
error rates. This suggest that constructing formally fault-tolerant circuits
that maintain the full code distance is not strictly necessary to guarantee
the usefulness of a quantum error-correcting protocol. Despite relying on
post-selection, we find that our methods can be efficient. These protocols
would be naturally implementable on a platform with long-range qubit
interactions like trapped ions or neutral atoms.

##  1 Introduction

Quantum error correction (QEC) [1, 2, 3, 4, 5, 6] will be a crucial component
to construct a large-scale fault-tolerant quantum computer capable of solving
certain problems that are prohibitively costly on classical computers [7, 8,
9]. In order to build logical qubits with an error rate sufficiently low to
allow for the implementation of deep quantum circuits, quantum error-
correcting codes (QECC) will be employed. QECCs encode logical qubits in a
larger number of physical qubits. If the error rate affecting the physical
qubits is below the threshold of the particular QECC being employed, then an
arbitrarily low logical error rate can be obtained with only a polynomial
overhead in physical resources [10, 11, 12, 13, 14, 15, 16].

In stabilizer codes, the logical codespace is defined as the simultaneous
($+1$)-eigenspace of a set of independent, commuting Pauli operators known as
the stabilizer generators [4, 17, 18]. Errors are detected by extracting the
error syndrome, i.e., the eigenvalues of the stabilizer generators. After
decoding the error syndrome, a conditional correction is applied on the
logical qubits.

Since errors can occur on every qubit, the circuit constructions used to
extract the error syndrome need to be fault-tolerant. There are several
methods to achieve this. Shor’s syndrome extraction method (ShorSEM) employs
ancillary qubits to measure the stabilizer generators one by one. To guarantee
fault tolerance, harmful errors should not propagate from the ancillary qubits
to the data qubits. This can be achieved in a variety of ways. In the original
proposal [3, 19], each stabilizer generator would be measured with an
entangled cat state, either pre-verified or subsequently decoded to correct
correlated errors arising during its preparation [20, 21]. More recently, it
has been shown that a single ancilla qubit can be fault-tolerant if it is
coupled to extra flag qubits used to identify the harmful errors that have
propagated to the data qubits [22, 23]. Furthermore, for certain stabilizer
codes, single ancillary qubits without flag qubits are sufficient to measure
each stabilizer generator fault-tolerantly [24, 25, 26]. Finally, the
stabilizer generators need to be measured several times to guarantee that
readout errors or data errors that occur between stabilizer measurements do
not become fatal. Notable improvements on this considerable time overhead have
been designed since Shor’s original proposal [3], including adaptive [27, 28,
29] and single-shot [30, 31] methods.

For Calderbank-Shor-Steane (CSS) codes, an alternative scheme to ShorSEM is
Steane’s syndrome extraction method (SteaneSEM) [32]. In this scheme, an
ancillary logical $|0\rangle_{L}$ ($|+\rangle_{L}$) state is used to extract
the error syndrome associated with the X (Z) stabilizers by coupling it to the
data logical qubit by means of a logical CNOT, performing a logical
measurement in the X (Z) basis and finally classically error-correcting the
outcome. As long as the preparation of the ancillary logical states is fault-
tolerant, it is sufficient to perform this procedure only once since the
logical CNOT gate is transversal on CSS codes. SteaneSEM reduces the time
overhead of ShorSEM at the expense of the requirement of fault-tolerant
preparation of the logical $|0\rangle_{L}$ and $|+\rangle_{L}$ states. In
fact, rather than disparate schemes, these two methods can be regarded as
opposite ends of a family of circuit constructions that exchange the
complexity of the ancilla block for a reduction in the number of repetitions
necessary to guarantee fault tolerance [33, 34]. Recently, SteaneSEM has been
experimentally demonstrated in two different trapped-ion systems [35, 36]. In
a similar spirit to SteaneSEM, yet applicable to any stabilizer code, Knill’s
method employs an entangled logical state to extract all the error syndrome in
one step [37].

Two-dimensional Bacon-Shor (BS) codes [38, 1, 39] are a family of CSS codes
defined on a planar array. The logical subspace has dimension higher than 2
and thus contains several logical qubits, which can be seen as subsystems of
the codespace. Out of these subsystems, typically only one is chosen as the
working logical qubit and the rest are referred to as gauge (logical) qubits.
Crucially for this work, depending on the state of these gauge qubits, the
logical $|0\rangle_{L}$ and $|+\rangle_{L}$ states of a BS code can be
expressed as products of Greenberger-Horne-Zeilinger (GHZ) states. This vastly
simplifies the fault-tolerant preparation of the logical $|0\rangle_{L}$ and
$|+\rangle_{L}$ states and thus positions the BS code as a natural candidate
for SteaneSEM.

Here we study how to fault-tolerantly prepare logical $|0\rangle_{L}$ and
$|+\rangle_{L}$ states of the BS code by using extra qubits to verify its
constituent GHZ states and post-selecting them. We go up to distance-9. For BS
codes of distances 3 to 9, we compare the logical error rate for 1 QEC cycle
with ShorSEM and SteaneSEM. For the time decoding, we use a recently developed
adaptive decoder [29]. For the space decoding, we use a lookup table. Although
exponentially costly in the limit of large code distance, the lookup-table
decoder for the BS code is essentially the same as for a repetition code and,
therefore, does not scale as badly as for subspace codes.

We find that SteaneSEM outperforms ShorSEM for all distances greater than 3.
More importantly, the advantage of SteaneSEM over ShorSEM grows monotonically
with the distance and the pseudo-thresholds remain about 1 order of magnitude
higher for the former than the latter. We also find that the advantage of
SteaneSEM over ShorSEM is the highest when gate errors dominate over
measurement errors. Finally, we calculate the probability of the GHZ states
not passing the verification and find it to be very reasonable. The fact that
each GHZ state can be separately employed in SteaneSEM without the need to
simultaneously have all the constituent GHZ states of the logical state makes
this scheme very efficient despite its post-selective nature.

This paper is organized as follows. In Sections 2 and 3, we review SteaneSEM
and the BS code, respectively. Section 4 contains the relevant details of our
simulation scheme, including the noise model and the importance sampler we
employ. In Section 5, we summarize our main results. Finally, in Section 6, we
conclude and present some open questions and future directions.

##  2 Steane’s Syndrome Extraction Method (SteaneSEM)

SteaneSEM is a method to detect and correct errors than can be implemented on
any CSS code. The procedure is depicted in Figure 1.

$\Qcircuit@C=0.7em@R=.4em@!{\lstick{\ket{\psi}_{L}}&\targ\qw\ctrl{2}\qw\\\
\lstick{\ket{0}_{L}}\ctrl{-1}\measuretab{M_{x}}\\\
\lstick{\ket{+}_{L}}\targ\measuretab{M_{z}}\\\ }$ Figure 1: Circuit
representation of SteaneSEM used to correct for errors on a logical qubit in
an arbitrary state $|\psi\rangle_{L}$. Each CNOT in the circuit corresponds to
a logical CNOT composed of $n$ physical CNOTs for a CSS code with $n$ data
qubits. The ancillary logical qubit prepared in $|0\rangle_{L}$
($|+\rangle_{L}$) is used to correct Z(X) errors which propagate down from the
data logical qubit through the CNOTs. After coupling this ancillary logical
qubit to the data logical qubit, the former is measured in the X(Z) basis and
the outcome is processed with classical error correction. It is not necessary
to repeat the procedure in order to achieve fault tolerance as long as the
ancillary logical states are prepared in a fault tolerant way.

The main challenge of SteaneSEM lies in the fault-tolerant preparation of the
logical $|0\rangle_{L}$ and $|+\rangle_{L}$ states that are needed to correct
for Z and X errors, respectively. In general, preparing a logical
$|0\rangle_{L}$ ($|+\rangle_{L}$) state of a CSS code requires a considerable
overhead. One can initialize the qubits in $|0\rangle^{\otimes n}$
($|+\rangle^{\otimes n}$), where $n$ is the total number of data qubits, and
then measure the X(Z) stabilizer generators to project the product state to
the codespace. However, to make this procedure fault-tolerant, the stabilizer
measurements need to be repeated, which essentially amounts to performing
ShorSEM. More efficient methods have been developed, which employ classical
error-correcting codes to aid in the detection of problematic errors [40, 41].
However, as we show in the next section, for the BS code, the fault-tolerant
logical state preparation can be even more straightforward.

When performing SteaneSEM, there are two mechanisms by which errors can
propagate from the ancillary to the data qubits: either directly or
indirectly. For the ancillary $|0\rangle_{L}$ ($|+\rangle_{L}$) state, X(Z)
errors can directly propagate through the logical CNOT to the data qubits. On
the other hand, while Z(X) errors will not propagate directly through the
logical CNOT, they will affect the measurements and will propagate indirectly
by giving rise to an incorrect syndrome and the application of the wrong
correction. Therefore, it is of critical importance to prepare the ancillary
logical states in a fault tolerant fashion.

##  3 The Bacon-Shor (BS) code

BS codes [38, 1, 39] are a family of CSS codes defined on a planar array of
$n$ physical data qubits. BS codes are subsystem codes [42, 43]. This implies
that the logical subspace has dimension higher than 2 and thus contains
several logical qubits, which can be seen as subsystems of the codespace. Out
of these subsystems, typically only one is chosen as the working logical
qubit.

For symmetric or square BS codes, there are $d^{2}$ physical data qubits,
where $d$ is the length of the side of the lattice and the distance of the
code. There are $(d-1)$ X stabilizer generators and $(d-1)$ Z stabilizer
generators, each of weight $2d$. X(Z) stabilizer generators correspond to
vertical (horizontal) rectangles. Because there are $d^{2}$ physical data
qubits but only $2(d-1)$ stabilizer generators, the total number of logical
qubits is $d^{2}-2(d-1)>1$. One of these has distance $d_{L}=d$ and is used as
the actual logical qubit. The rest correspond to encoded qubits of distance
$d_{G}<d$ that are not used to store information. They are referred to as
gauge qubits because they can be regarded as gauge degrees of freedom. The BS
code is an instance of the more general 2-D compass code family [44].

The BS code does not present a quantum error correction threshold as the
lattice size is increased [45]. However, if the code distance is increased by
concatenation, a threshold is obtained, albeit a small one [39]. More
importantly, under certain experimental conditions, simulations of the BS code
have revealed that it can achieve a comparable and even superior performance
to the more popular surface code [46]. Furthermore, it has been recently shown
that by employing a construction based on lattice surgery a threshold can be
obtained for the BS code [47].

The BS code has several very useful properties. Every stabilizer can be
measured fault-tolerantly with a single bare ancilla as long as one is careful
about the ordering of the entangling gates [26]. This property is very useful
for systems which allow for long-range entangling gates, like trapped ions
[48] and neutral atoms [49]. Alternatively, the stabilizers can also be
measured indirectly by measuring their constituent gauge operators (or some
combination of them) and calculating their total parity [39], which makes the
BS code amenable to be implemented on solid-state systems with only nearest-
neighboring interactions.

All logical Pauli gates, CNOTL, $H_{L}$, and $Y(\pi/2)_{L}$ can be implemented
transversally on the BS code. Universality can be achieved with either a
$T_{L}$ gate via magic state distillation [50] or a $CCZ_{L}$ gate by means of
pieceable fault tolerance [51, 52]. The BS code has been shown to be useful
against leakage errors [53] and amenable to be run with continuous
measurements [54]. The distance-2 and distance-3 square BS codes have been
experimentally implemented in trapped-ion systems [55, 48].

The gauge degrees of freedom of the BS code can be exploited to design very
simple fault tolerant procedures to prepare the logical $|0\rangle_{L}$ and
$|+\rangle_{L}$ states. In particular, for a square [[$d^{2},1,d$]] BS code,
the logical states can be expressed as:

$\displaystyle|0\rangle_{L}$
$\displaystyle=\frac{1}{\sqrt{2^{d}}}\left(|+\rangle^{\otimes
d}+|-\rangle^{\otimes d}\right)^{\otimes d}\quad\mbox{ along rows}$
$\displaystyle|+\rangle_{L}$
$\displaystyle=\frac{1}{\sqrt{2^{d}}}\left(|0\rangle^{\otimes
d}+|1\rangle^{\otimes d}\right)^{\otimes d}\quad\mbox{ along columns}$

That is, to prepare the logical $|0\rangle_{L}$ $\left(|+\rangle_{L}\right)$
state, we only need to prepare the GHZ state $\left(|+\rangle^{\otimes
d}+|-\rangle^{\otimes d}\right)/\sqrt{2}$ $\left(\left(|0\rangle^{\otimes
d}+|1\rangle^{\otimes d}\right)/\sqrt{2}\right)$ on each one of the $d$ rows
(columns) of the code. The preparation of GHZ states for QEC has been
experimentally demonstrated in trapped-ion systems [56]. Figure 2 illustrates
a possible circuit for the preparation of $\left(|0\rangle^{\otimes
5}+|1\rangle^{\otimes 5}\right)/\sqrt{2}$.

$\Qcircuit@C=0.7em@R=.4em@!{\lstick{\ket{0}}&\gate{H}\ctrl{1}\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\targ\ctrl{1}\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\targ\ctrl{1}\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\targ\ctrl{1}\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\targ\qw\\\ }$ Figure 2: Circuit that can be used
to prepare the GHZ state $\frac{1}{\sqrt{2}}\left(|0\rangle^{\otimes
5}+|1\rangle^{\otimes 5}\right)$. For the noise model employed in this paper,
this circuit is not fault-tolerant, since a weight-1 X error can propagate
through the CNOTs to form a weight-2 X error. Z errors are not problematic
since they propagate through the CNOTs to form an operator which is actually a
stabilizer of the GHZ state.

###  3.1 Fault-tolerant preparation of logical $|0\rangle_{L}$ and
$|+\rangle_{L}$ states on the [[25,1,5]] BS code (d=5)

Figure 3: The preparation of a 5-qubit GHZ state can be made fault-tolerant by
adding an extra verification qubit, which measures one of the Z stabilizers of
the GHZ state. In this case, the measured stabilizer is $Z_{2}Z_{4}$, but this
choice is not unique. Any stabilizer that detects a weight-2 X error caused by
a single-qubit X error works well. For example, for this circuit, $Z_{1}Z_{5}$
would also be a useful verification stabilizer. As with any verification
protocol, the final state might be discarded even in the absence of
problematic errors, for instance if an error occurs on the measurement. In the
case depicted, a problematic X error is successfully detected and the GHZ is
discarded and re-prepared.

The construction of a 3-qubit GHZ state of the form
$\frac{1}{\sqrt{2}}\left(|0\rangle^{\otimes 3}+|1\rangle^{\otimes 3}\right)$
is naturally fault-tolerant because its stabilizer generators are
$Z_{1}Z_{2},Z_{2}Z_{3},X_{1}X_{2}X_{3}$, which means that X and Z errors can
be at most of weight-1 up to a stabilizer. On the other hand, the analogous
5-qubit GHZ state, whose preparation is depicted in Figure 2 is stabilized by
$Z_{1}Z_{2}$, $Z_{2}Z_{3}$, $Z_{3}Z_{4}$, $Z_{4}Z_{5}$,
$X_{1}X_{2}X_{3}X_{4}X_{5}$. All Z errors are at most of weight-1 up to a
stabilizer, so they are not problematic but X errors can be of weight-1 or
weight-2. These are problematic because a single X error on the control qubit
of a CNOT can propagate to form a weight-2 X error.

As shown in Figure 3, this can be easily detected with an extra verification
qubit. If each one of the 5 GHZ states is verified by an extra qubit, then the
resulting BS logical state will be fault-tolerant and amenable to be used as
an ancilla in SteaneSEM. The procedure is straightforward and the only caveat
is that it requires post-selection and, therefore, midcircuit measurements. If
the verification is not passed, the GHZ state needs to be re-prepared.

###  3.2 Fault-tolerant preparation of logical $|0\rangle_{L}$ and
$|+\rangle_{L}$ states on the [[49,1,7]] BS code (d=7)

The preparation of 3-qubit GHZ states for the purpose of SteaneSEM on the
[[9,1,3]] BS code does not require a verification because, up to the
stabilizers of the GHZ state, all weight-1 errors propagate to form other
weight-1 errors. As shown in the previous subsection, for 5-qubit GHZ states,
some weight-1 errors can propagate to form problematic weight-2 errors.
Fortunately, these can be caught with a single verification qubit.

For the [[49,1,7]] code, in order to maintain the distance-7, the situation
becomes more complex: one needs to make sure that (1) no weight-1 error
propagates to form a problematic weight-2 or weight-3 error, and also that (2)
no weight-2 error propagates to form a problematic weight-3 error. Naively, by
extrapolating from the first two cases, one might believe that 2 verification
qubits are sufficient. However, this is not the case. We performed an
exhaustive search over all the possible circuits that emply 2 verification
qubits to measure weight-2 Z stabilizers and found none that satisfies
conditions (1) and (2). Figure 4 depicts an instance of a circuit with 2
verification qubits that does not satisfy the condition (2). The conditions
are not satisfied because our error model assumes that weight-2 errors can
occur after entangling gates with the same probability $p$ as weight-1 errors.
If weight-2 errors after entangling gates occurred with a probability
$O(p^{2})$, then 2 verification qubits would suffice. Therefore, when adapting
these ideas to experimental systems, it is crucial to consider the specific
noise model because the number of necessary verification qubits might depend
on it.

Figure 4: Circuit to verify a 7-qubit GHZ with 2 verification qubits. For the
error model we employ, this circuit is formally not fault-tolerant. In this
case, an X error that occurs with probability $O(p^{2})$ can cause an
undetected weight-3 X error (The resulting weight-4 error is equivalent to a
weight-3 error up to the GHZ’s X stabilizer.). As shown in the Section 5, even
though this circuit is not formally fault-tolerant, it still performs better
than ShorSEM for $p>2\times 10^{-6}$. To guarantee formal fault tolerance, we
find that 3 verification qubits are needed.

For the error model employed in this paper, 3 verification qubits are
necessary to guarantee the fault-tolerant preparation of the 7-qubit GHZ
state. All 3 verification measurements need to return a $+1$ eigenvalue to
accept the GHZ state. If at least 1 of them returns a $-1$, the verification
is not passed and the GHZ state needs to be re-prepared. This was found by an
exhaustive search. Similarly, it was proven that the conditions (1) and (2)
are satisfied by exhaustively checking that all weight-1 and weight-2 errors
(more accurately all errors that occur with probability $O(p)$ and $O(p^{2})$)
that result in problematic higher-weight errors are effectively caught by at
least one verification qubit.

###  3.3 Maintaining the formal distance of the code is not strictly necessary
to suppress the logical error rate

One of the rules of thumb in the construction of fault-tolerant circuits for
QEC is that the code distance needs to be maintained. What’s the point of
using a distance-7 QEC code if a particular circuit construction is not immune
to some weight-3 errors, like the case of the [[49,1,7]] code with 7-qubit GHZ
states with 2 verification qubits? It seems like it should be a loss because
the leading order of the logical error rate would go from $p^{4}$ to $p^{3}$.

However, this argument is only valid in the limit of $p\to 0$. For higher $p$
values, the coefficients of the non-leading-order terms might play a very
significant role. In fact, as it is shown in the Section 5, for the [[49,1,7]]
BS code with SteaneSEM, employing 2 verification qubits outperforms ShorSEM
for an experimentally relevant interval of $p$ values ($p>2\times 10^{-6}$)
despite not being formally fault-tolerant. Furthermore, for $p>4\times
10^{-5}$, employing 2 and 3 verification qubits result in similar performances
(See Figure 6). Intuitively, this occurs because, with 2 verification qubits,
there are very few weight-3 errors that result in a logical error, so the
coefficient of the $p^{3}$ term is much smaller than the coefficient of the
$p^{4}$ term for the procedure with ShorSEM. The coefficients of the leading
orders of the polynomial expansions of the logical error rates are presented
in Table 1. These coefficients are not obtained by curve fitting, but rather
by employing an error subset sampler described in the Section 4. They are
exact up to the sampling error of the subsets.

###  3.4 Fault-tolerant preparation of logical $|0\rangle_{L}$ and
$|+\rangle_{L}$ states on the [[81,1,9]] BS code (d=9) and beyond

A $d$-qubit GHZ state ($(|0\rangle^{\otimes d}+|1\rangle^{\otimes
d})/\sqrt{2}$) can have at most $1$ Z error and $\lfloor(d-1)/2\rfloor$ X
errors, up to its stabilizers. Therefore, for errors of weight up to
$\lfloor(d-1)/2\rfloor$, no errors of higher weight will be formed by gate
propagation when creating the $d$-qubit GHZ states. We exhaustively searched
over all possible constructions involving $3$ and $4$ verification qubits and
we did not find a circuit that maintains the formal distance-9. However, the
performance is good compared to ShorSEM, as it is shown in the Section 5. All
the circuits we employed to verify the GHZ states are presented in Appendix B.
These circuits were found by an exhaustive search over all circuits that
measure weight-2 Z stabilizers of the GHZ states.

##  4 Simulation scheme

We use a simulation toolkit employed in previous papers [25, 57, 58, 59], with
CHP [60] as its core simulator. In order to compare SteaneSEM and ShorSEM on
the BS code, we simulate 1 QEC cycle. In both cases, we initialize the data
qubits in a perfect logical state, perform one of the syndrome extraction
methods, and apply the corresponding correction to the data qubits. Finally,
to account for only uncorrectable errors, we project the corrected state back
to the codespace. We count a logical error if the final projected state is
different from the initial state. We also determine if the working logical
qubit ends up being entangled with the gauge logical qubits. For the noise
model we employ, logical entanglement never occurs. We performed the
simulations with an initial logical $|0\rangle_{L}$ and $|+\rangle_{L}$. We
show the results for $|+\rangle_{L}$, but the results are practically the same
for both initial states.

For SteaneSEM, to calculate the logical error rate, we take into account only
the runs where all the GHZ verifications were passed. To perform the classical
error correction on the ancillary logical state outcomes, we employ a lookup
table. Despite its exponential scaling with the number of stabilizer
generators, the lookup table is very practical given the reduced number of
stabilizer generators of the BS code. For example, for the largest code we
analyze ($d=9$), the number of syndromes in each lookup table is only
$2^{9-1}=256$.

For ShorSEM, we employ a recently proposed adaptive scheme [29] for the time
decoding and the lookup tables for the space decoding. Following the formalism
introduced in [29], we performed both the weak and strong fault-tolerant
decoding schemes. We refer to [29] for a detailed explanation of the ideas
behind weak and strong fault tolerance.

###  4.1 Noise model

We employ a depolarizing Pauli noise model with no memory errors.
Specifically, we have the following noise processes:

  1. 1.

After every 1-qubit unitary gate: X, Y, or Z error, each with a probability of
$p/3$.

  2. 2.

After every 2-qubit unitary gate: one of the 15 possible Pauli errors (IX, IY,
…, ZZ), each with a probability of $p/15$.

  3. 3.

After every $|0\rangle$ state preparation: an X error with a probability of
$p$.

  4. 4.

After every measurement in the Z basis: a bit flip with a probability of $q$.
For most of the discussion, we set $p=q$ to simplify the visualization of the
results. At the end, we analyze the case where $p$ and $q$ are independent to
explore how each syndrome extraction method performs under different gate vs.
measurement noise strengths.

Despite being restricted to only Clifford gates and Pauli preparations and
measurements, error channels within the stabilizer formalism can be good
approximations to realistic non-Clifford noise processes [61, 62, 63, 64, 65].

###  4.2 Importance sampler

To expedite the simulation, we use an importance (subset) sampler previously
employed [25, 59]. Instead of traversing the whole circuit and adding an error
after each gate if a randomly generated real number between 0 and 1 is less
than the physical error probability $p$, our importance sampler divides the
error-configuration set into non-overlapping subsets according to the number
of errors or weight.

For a noise model with $n$ independent error parameters, we label each subset
with a vector $\vec{w}=(w_{1},w_{2},...,w_{n})$, where $w_{i}$ corresponds to
the number of errors associated with the parameter $i$. To estimate the
logical error rate, we (1) analytically calculate the total probability of
occurrence of each subset ($A_{\vec{w}}$) and (2) perform Monte Carlo sampling
on the error subsets with high probability of occurrence to obtain the logical
error rate for each subset $\left(p_{L}^{(\vec{w})}\right)$. We can then
compute lower and upper bounds to the logical error rate with the following
equations:

$p_{L}^{(lower)}=\sum_{\vec{w}=(0,0,...,0)}^{\vec{w}_{max}}A_{\vec{w}}\,p_{L}^{(\vec{w})}$
(1)
$p_{L}^{(upper)}=p_{L}^{(lower)}+\left(1-\sum_{\vec{w}=(0,0,...,0)}^{\vec{w}_{max}}A_{\vec{w}}\right)$
(2)

where $\vec{w}_{max}$ is the highest-weight subset that was sampled. The lower
(upper) bound assumes that all the subsets not sampled have a logical error
rate of 0(1). To calculate the upper bound we simply add to the lower bound
the total probability of occurrence of the unsampled subsets. For low physical
error rates, the two bounds typically overlap. They start to diverge as the
physical error rates increase.

The subset sampler has several very convenient features. First, it allows us
to efficiently obtain logical error rates at extremely low physical error
rates. In fact, it is most efficient at low physical error rates because the
number of subsets needed to be sampled is low. Secondly, once we sample the
relevant subsets, we can then generate the whole logical error rate curve (or
hyper-surface for a multi-parameter noise model) at once by simply re-
calculating the probabilities of occurrence of each subset, which is done
analytically. Finally, it allows us to compute the coefficients associated
with each term in the polynomial expansion of the logical error rate, which is
very useful to compare different QEC schemes. The method to compute the
polynomial coefficients is described in the Appendix A and the coefficients of
the leading order terms for all logical error rates are reported in Table 1.
We can even obtain the exact values of the leading polynomial coefficients by
exhaustively running all the error configurations of the relevant subsets, as
long as their cardinalities are not prohibitively high. Other importance
samplers have been previously applied to the simulation of QEC circuits [66,
67]. Recently, these ideas have been extended to develop a dynamical subset
sampling scheme [68].

In this work, we assume 3 independent error weights: the number of errors
after 1-qubit gates and state preparations ($w_{1}$), after 2-qubit gates
($w_{2}$), and after measurements ($w_{3}$). However, to simplify the
visualization of the results, we set all the physical error rates to be equal,
except in the final part of the paper where we let the measurement error rate
to be independent. We sample all error subsets up to total weight
$w_{tot}=w_{1}+w_{2}+w_{3}$ equal to 10. The number of samples taken for each
subset is $2\times 10^{4}$, except for crucial subsets with very a low logical
error rate, where we take $\max(2\times 10^{4},5\%$ of the subset’s
cardinality$)$.

##  5 Results

d Shor Steane Weak Strong v=0 v=1 v=2 v=3 v=4 3 $1.45\times 10^{2}p^{2}$
$3.88\times 10^{2}p^{2}$ $3.66\times 10^{2}p^{2}$ – – – – 5 $2.65\times
10^{5}p^{3}$ $2.13\times 10^{5}p^{3}$ $1.31\times 10^{5}p^{2}$ $4.56\times
10^{4}p^{3}$ – – – 7 $7.36\times 10^{8}p^{4}$ $3.42\times 10^{8}p^{4}$ – –
$1.31\times 10^{3}p^{3}$ + $6.32\times 10^{7}p^{4}$ $9.88\times 10^{7}p^{4}$ –
9 $1.45\times 10^{11}p^{5}$ $1.97\times 10^{12}p^{5}$ – – – $1.78\times
10^{5}p^{4}$ + $3.85\times 10^{10}p^{5}$ $2.26\times 10^{4}p^{4}$ +
$4.56\times 10^{10}p^{5}$

Table 1: Leading-order terms of the polynomial expansions of the logical error
rates for BS codes of distances 3, 5, 7, and 9 and various syndrome extraction
methods. For SteaneSEM, the number of qubits used for the GHZ verifications is
denoted by v. For each term, the coefficient is obtained with the subset
sampler and the method described in Appendix A. For both the strong and weak
StrongSEM, the leading orders are $p^{(d+1)/2}$, which implies that the full
code distance is maintained. For SteaneSEM, the full code distance is
maintained only for d=5 (v=1) and d=7 (v=3). For the other cases, the leading
order is reduced by 1. Nevertheless, as shown in Figure 6, except for the d=5
without verification, the SteaneSEM cases that have a decreased distance still
outperform full-distance ShorSEM for experimentally relevant physical error
rates $\left(p>\sim 10^{-6}\right)$. This illustrates that maintaining the
full distance is not strictly necessary to guarantee that a particular
protocol will be effective. Figure 5: Logical error rates for the BS code with
3 different decoding strategies: (1) weak ShorSEM adaptive decoder, (2) strong
ShorSEM adaptive decoder, and (3) SteaneSEM. For each decoding strategy, the
lowest and highest pseudo-thresholds are shown. Remarkably, the lowest
SteaneSEM pseudo-thresholds $\left(\sim 10^{-3}\right)$ are about 1 order of
magnitude higher than their ShorSEM counterparts $\left(\sim 10^{-4}\right)$.
For SteaneSEM, the number of verification qubits used for each GHZ state is
denoted by v. For some $d=9$ curves, we already observe, for high values of
$p$, a small divergence between the upper and lower bounds of the logical
error rate. This occurs because, for larger physical error rates, the
probability of occurrence of the high-weight subsets not sampled becomes
considerable.

Figure 5 shows the logical error rate for several distances of the BS code
with 3 different decoding strategies. For both the weak and strong ShorSEM,
the leading order of the polynomial expansion for each curve is $p^{(d+1)/2}$
(See Table 1), which implies that the full distance is maintained. However,
the pseudo-thresholds (intersections between curves) are rather low. An
interesting difference is observed between strong and weak ShorSEM. Whereas
the pseudo-thresholds decrease quickly for the strong decoder (from $2.0\times
10^{-3}$ to $2.0\times 10^{-4}$), they decrease much more slowly for the weak
decoder (from $5.8\times 10^{-4}$ to $4.4\times 10^{-4}$).

On the other hand, for SteaneSEM, the pseudo-thresholds remain high (from
$3.6\times 10^{-3}$ to $2.6\times 10^{-3}$), about 1 order of magnitude higher
than for the Shor methods. It remains an open question how fast the SteaneSEM
pseudo-thresholds will decrease for higher distances ($d>9$) and whether or
not a real threshold exists for the BS code if this syndrome extraction method
is employed. In any case, despite its great importance from a theoretical QEC
perspective, from a practical point of view the existence of a threshold is
not strictly necessary since the crucial goal of a QECC is to achieve a
sufficiently low logical error rate useful for algorithmic purposes.

Figure 6: Logical error rates for several distances (d) of the BS code. For
SteaneSEM, the number of verification qubits used for each GHZ state is
denoted by v. Except for the distance-5 with no verification qubits, all the
non fault-tolerant SteaneSEM circuit constructions outperform the fault-
tolerant ShorSEM protocols for experimentally relevant values of $p$. We only
include the results for weak ShorSEM. The results for strong ShorSEM are very
similar.

Figure 6 presents the logical error rates from a different perspective, which
lets us compare more easily the performance of the syndrome extraction methods
for distances 5, 7, and 9. For $d=5$, SteaneSEM with 1 verification qubit per
GHZ state (v=1) outperforms ShorSEM for every physical error rate. For low $p$
values, this can be explained by comparing the coefficients of the leading
orders in the polynomial expansions (See Table 1). For both ShorSEM and
SteaneSEM (v=1), the leading order is $p^{3}$, but the coefficient is almost 1
order of magnitude larger for both Shor methods than for SteaneSEM.

As a reference point, we also simulated the d=5 rotated surface code [24, 69,
70, 71] with the adaptive ShorSEM time decoder and a lookup-table space
decoder. As seen in Figure 6, its performance is slightly better than the BS
code with ShorSEM, but still worse than the BS code with SteaneSEM.

For d=7, SteaneSEM requires 3 verification qubits per GHZ state (v=3) to
maintain the full distance of the code. If only 2 verification qubits are
used, then some weight-3 error events can be uncorrectable. An example of such
an event would be a situation where first the 2 X errors depicted in Figure 4
occur during the preparation of one of the GHZ states. The resulting weight-3
X error on the GHZ state error would not directly propagate to the logical
data qubit because this GHZ state is a constituent of the logical
$|+\rangle_{L}$ state (See Figure 1). However, it would give rise to an
incorrect syndrome, so it propagates indirectly. If another X error occurs on
one of the data qubits not part of this wrong correction, then applying the
correction would result in an uncorrectable weight-4 X error. Therefore, this
is an error event that occurs with probability $O(p^{3})$, but that results in
an uncorrectable weight-4 error.

Despite being formally not fault-tolerant (its effective distance decreased
from 7 to 5), SteaneSEM with 2 verification qubits per GHZ still outperforms
both strong and weak ShorSEM for an experimentally relevant physical error
rate interval $\left(p>2\times 10^{-6}\right)$, as shown in Figure 6. As seen
in Table 1, the coefficient of the $p^{3}$ term for d=7 (v=2) SteaneSEM is
very small compared to the coefficients of the $p^{4}$ terms for both strong
and weak ShorSEM ($\sim 10^{3}$ vs. $\sim 10^{8}$). In other words, for d=7
(v=2) SteaneSEM, the number of uncorrectable error events that occur with
probability $O(p^{3})$ is so small that it is only for very low physical error
rates $\left(p<2\times 10^{-6}\right)$ that the leading-order comparison is an
appropriate analysis tool.

For d=7, if we use 3 verification qubits per GHZ state, then SteaneSEM
outperforms ShorSEM for every physical error rate. This agrees with the fact
that both d=7 (v=3) SteaneSEM and d=7 ShorSEM have the same leading order
($p^{4}$), but the former has a lower coefficient (See Table 1). Surprisingly,
for $p>4\times 10^{-5}$, the performance of SteaneSEM is about the same for
v=2 and v=3. This further strengthens the point that maintaining the full
distance of the code is not strictly necessary to guarantee the usefulness of
a particular QEC protocol.

For d=9, both v=3 and v=4 SteaneSEM have their effective distances decrease
from 9 to 7, as seen from the leading $p^{4}$ orders in Table 1. However, as
seen in Figure 6, for $p>4\times 10^{-7}$, both SteaneSEM constructions
outperform their ShorSEM counterparts, despite the latter ones maintaining the
full code distance (d=9). Similarly to the d=7 case, for an experimentally
relevant physical error rate interval $\left(p>10^{-5}\right)$, using 3 or 4
verification qubits per GHZ give essentially the same results.

###  5.1 Improvement rate of SteaneSEM vs. ShorSEM

Figure 7: Improvement rate of SteaneSEM over the weak ShorSEM for various
distances as a function of the physical error rate. The label v refers to the
number of qubits used for the verification of each GHZ state that forms the
logical ancillary $|0\rangle_{L}$ and $|+\rangle_{L}$ states. The improvement
rate increases monotonically with $d$, from $r\approx 0.4$ for $d=3$ (ShorSEM
$2.5$ times better than SteaneSEM), to $r\approx 20$ for $d=9$ (SteaneSEM $20$
times better than ShorSEM). SteaneSEM advantage is observed for $d=7($v$=2)$
and $d=9$, despite the fact that these protocols are not formally fault-
tolerant, while their ShorSEM counterparts are. Even for $d=5$ without
verification (v$=0$), SteaneSEM achieves a comparable performance to ShorSEM
for high physical error rates. For $d=7$ and $d=9$, the divergence between the
lower and upper bounds indicate that the probability of occurrence of the
high-weight subsets not sampled is considerable.

In order to further compare both syndrome extraction methods, we define the
improvement rate as the ratio of the logical error rate for ShorSEM over the
logical error rate of SteaneSEM:

$r=\frac{p_{L(ShorSEM)}}{p_{L(SteaneSEM)}}$

Figure 7 shows the improvement rate $r$ as function of the physical error rate
$p$. It increases with the code distance from less than $1$ for $d=3$ (a
disadvantage) to $\sim 2$ for $d=5$, $\sim 10$ for $d=7$, and $\sim 20$ for
$d=9$. The improvement rate does not depend too strongly on the physical error
rate for the $p$ interval considered, as seen in Figure 7.

The increasing improvement rate of SteaneSEM over ShorSEM has very important
practical consequences. Notice, for example, that for a physical error rate
$p=10^{-4}$, a distance-9 BS code with SteaneSEM would be enough to achieve a
logical error rate of $10^{-10}$, which is considered as the largest tolerable
error rate to achieve an algorithmic qubit capable of sustaining a deep and
useful quantum computation [72]. For ShorSEM, on the other hand, a distance-9
BS code would not be enough to achieve this logical error rate. It is an open
question whether this increasing improvement rate will be sustained for even
higher distances ($d>9$).

Figure 8: Improvement rate of SteaneSEM over the weak ShorSEM for the
distance-5 BS code. We define two independent noise parameters: $p$, which
quantifies the error rate of 1-qubit gates, 2-qubit gates, and state
preparations, and $q$, which quantifies the measurement error rate. The
improvement rate is the largest when gate errors dominate over measurement
errors ($p\gg q$), which corresponds to the lower right section of the heat
map. In the opposite regime ($p\ll q$), the improvement rate is less than 1,
which means that ShorSEM outperforms SteaneSEM. When $p=q$ (diagonal line),
the improvement rate is around 2.

Motivated by a recent paper [73], we now set the measurement error rate ($q$)
to be independent from the 1-qubit gate, 2-qubit gate, and state preparation
error rate ($p$). The resulting improvement rate is plotted as a heat map in
Figure 8. We find that the improvement rate has the highest values when gate
errors dominate over measurement errors ($p\gg q$). This is expected since the
number of entangling gates is considerably lower for SteaneSEM. However, when
measurement errors dominate over gate errors ($p\ll g$), the improvement rate
can be less than 1, which means that ShorSEM outperforms SteaneSEM. This is
also expected, since ShorSEM has less measurements than SteaneSEM. In Appendix
D, we present the total number of CNOT gates and measurements for the various
circuit constructions that we study in this paper.

###  5.2 Probability of not passing the GHZ state verification

Figure 9: Probability of discarding the GHZ state because of a failed
verification. The probability grows with increasing physical error rate, but
it remains within reasonable limits. The $5\%$ failure probability is shown as
a reference.

One possible drawback of the current proposal for SteaneSEM on the BS code is
that it relies on post-selection. If the GHZ state does not pass the
verification checks, it is discarded and re-prepared, which could potentially
result in a considerable time overhead in a system where the measurements and
state preparations are slow. However, a numerical calculation shows that this
is not as bad as it might seem. Figure 9 shows the probability that a single
$d$-qubit GHZ state does not pass the verification. The probability that the
verification is not passed increases with the code distance, but it is very
reasonable. As shown in Figure 9, for a physical error rate of $p=10^{-3}$,
all the verifications will be passed more than $95\%$ of the times.

To experimentally implement the SteaneSEM on the BS code, we envision a whole
section of the quantum computer dedicated to prepare and verify GHZ states
(GHZ state factory). Notice that to perform SteaneSEM on a distance-$d$ BS
code, it is possible to prepare each $d$-qubit GHZ state, entangle it to the
data qubits, and even measure it one at a time instead of waiting to
simultaneously have all the $d$ GHZ states that form the logical
$|0\rangle_{L}$ or $|+\rangle_{L}$.

##  6 Conclusions and Outlook

In this paper we have studied the performance of the BS code with two
different syndrome extraction methods: Shor’s and Steane’s. The fact that the
logical $|0\rangle_{L}$ and $|+\rangle_{L}$ states of the BS code can be
expressed as products of GHZ states positions this code as a natural candidate
for Steane’s syndrome extraction method.

We have shown that these logical BS states can be prepared in a
straightforward manner by verifying its constituent GHZ states and post-
selecting them. By using this post-selection GHZ preparation method we have
found that SteaneSEM significantly outperforms ShorSEM on the BS code.
Steane’s method results in pseudo-thresholds that are about 1 order of
magnitude higher $\left(\sim 10^{-3}\,\textrm{vs.}\,\sim 10^{-4}\right)$. We
have also found that the improvement rate of Steane’s method over Shor’s
increases monotonically with the code distance from Steane’s method being
disadvantageous for d=3 to being about 20 times better for d=9. When we let
the measurement error rate be independent from the gates and preparations
error rate, we find that Steane’s improvement is the greatest in the regime
where gate error dominate over measurement errors. This is consistent with the
fact that Steane’s method employs considerably less entangling gates than
Shor’s.

Some of the circuit constructions that we have found to prepare the logical
$|0\rangle_{L}$ and $|+\rangle_{L}$ states used in Steane’s method are not
strictly fault-tolerant, since their effective distance is reduced. However,
we found that for experimentally relevant physical error rates, even the non-
fault-tolerant Steane’s circuit constructions outperform their Shor’s
counterparts, despite the latter ones being formally fault-tolerant.
Furthermore, for these experimentally relevant physical error rates, Steane’s
non-fault-tolerant and fault-tolerant protocols have essentially the same
performance. From our perspective, this is one of the most important results
from this work, since it illustrates that maintaining the formal code distance
is not strictly necessary to guarantee the usefulness of a QEC protocol. It
also suggests that leading-order analysis might not be the most appropriate
tool when comparing QEC strategies under experimentally relevant physical
error rates.

Given that our state preparation methods post-selective, we also calculated
the probability that the GHZ verifications are not passed. We have found that,
for all code distances and experimentally relevant physical error rates, the
preparations fail less than $5\%$ of the times.

There are several questions that remain to be answered. First, the circuits
used to verify the GHZ states were found by a brute-force exhaustive search
over all possible weight-2 Z stabilizers. This strategy is not scalable to
higher distances. It would be interesting to apply the great body of work on
flag qubits [22, 23, 74] to develop a formal framework to construct GHZ-
verification circuits that employ the least number of extra qubits. It would
also be interesting to find circuits that do not rely on post-selection.

Finally, we also plan to study these protocols in the context of trapped ions
and neutral atoms with a realistic modeling of the noise and the possible
shuttling operations. In designing effective and useful fault-tolerant QEC
protocols, it will be crucial to take into account the detailed noise
processes and architectural constraints of the specific quantum computing
platforms where these protocols will be implemented.

##  7 Acknowlegments

The idea behind this paper originated while Mauricio Gutiérrez was visiting
the Duke Quantum Center. Mauricio Gutiérrez would like to thank Kenneth Brown
for hosting him and for his great warmth and hospitality. He would also like
to thank Shilin Huang, for the very fruitful discussions that gave rise to
this paper, and Theerapat Tansuwannont, for his explanations of the adaptive
time decoder for ShorSEM. The simulations were run on the computer cluster of
the Research Center for Materials Science and Engineering (CICIMA) of the
University of Costa Rica. The authors thank Federico Muñoz for his help in
setting up the simulations on the computer cluster. This work was partially
supported by the Research Office of the University of Costa Rica. Both authors
are grateful to the University of Costa Rica for its support.

## References

  * [1] Peter W. Shor.  “Scheme for reducing decoherence in quantum computer memory”.  Phys. Rev. A 52, R2493–R2496 (1995).
  * [2] Emanuel Knill and Raymond Laflamme.  “Theory of quantum error-correcting codes”.  Phys. Rev. A 55, 900–911 (1997).
  * [3] P.W. Shor.  “Fault-tolerant quantum computation”.  In Proceedings of 37th Conference on Foundations of Computer Science.  Pages 56–65.  (1996).
  * [4] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane.  “Quantum error correction and orthogonal geometry”.  Phys. Rev. Lett. 78, 405–408 (1997).
  * [5] A.Yu. Kitaev.  “Fault-tolerant quantum computation by anyons”.  Annals of Physics 303, 2–30 (2003).
  * [6] Barbara M. Terhal.  “Quantum error correction for quantum memories”.  Rev. Mod. Phys. 87, 307–346 (2015).
  * [7] Peter W. Shor.  “Algorithms for quantum computation: discrete logarithms and factoring”.  In Proceedings 35th Annual Symposium on Foundations of Computer Science.  Pages 124–134.  (1994).
  * [8] Seth Lloyd.  “Universal quantum simulators”.  Science 273, 1073–1078 (1996).
  * [9] Alán Aspuru-Guzik, Anthony D. Dutoi, Peter J. Love, and Martin Head-Gordon.  “Simulated quantum computation of molecular energies”.  Science 309, 1704–1707 (2005).
  * [10] Dorit Aharonov and Michael Ben-Or.  “Fault-tolerant quantum computation with constant error rate”.  SIAM Journal on Computing 38, 1207–1282 (2008).
  * [11] Emmanuel Knill, Raymond Laflamme, and Wojciech H. Zurek.  “Threshold accuracy for quantum computation” (1996).  url: https://arxiv.org/abs/quant-ph/9610011.
  * [12] John Preskill.  “Reliable quantum computers”.  Proc. R. Soc. Lond. A. 454, 385–410 (1998).
  * [13] Barbara M. Terhal and Guido Burkard.  “Fault-tolerant quantum computation for local non-markovian noise”.  Phys. Rev. A 71, 012336 (2005).
  * [14] Michael A. Nielsen and Christopher M. Dawson.  “Fault-tolerant quantum computation with cluster states”.  Phys. Rev. A 71, 042323 (2005).
  * [15] Panos Aliferis and Debbie W. Leung.  “Simple proof of fault tolerance in the graph-state model”.  Phys. Rev. A 73, 032308 (2006).
  * [16] Panos Aliferis, Daniel Gottesman, and John Preskill.  “Quantum accuracy threshold for concatenated distance-3 code”.  Quantum Info. Comput. 6, 97–165 (2006).
  * [17] A.R. Calderbank, E.M. Rains, P.M. Shor, and N.J.A. Sloane.  “Quantum error correction via codes over gf(4)”.  IEEE Transactions on Information Theory 44, 1369–1387 (1998).
  * [18] Daniel E. Gottesman.  “Stabilizer codes and quantum error correction”.  Phd thesis.  California Institute of Technology.  (1997).
  * [19] David P. DiVincenzo and Peter W. Shor.  “Fault-tolerant error correction with efficient quantum codes”.  Phys. Rev. Lett. 77, 3260–3263 (1996).
  * [20] David P. DiVincenzo and Panos Aliferis.  “Effective fault-tolerant quantum computation with slow measurements”.  Phys. Rev. Lett. 98, 020501 (2007).
  * [21] Theodore J. Yoder and Isaac H. Kim.  “The surface code with a twist”.  Quantum 1, 2 (2017).
  * [22] Rui Chao and Ben W. Reichardt.  “Quantum error correction with only two extra qubits”.  Phys. Rev. Lett. 121, 050502 (2018).
  * [23] Rui Chao and Ben W. Reichardt.  “Flag fault-tolerant error correction for any stabilizer code”.  PRX Quantum 1, 010302 (2020).
  * [24] Yu Tomita and Krysta M. Svore.  “Low-distance surface codes under realistic quantum noise”.  Phys. Rev. A 90, 062320 (2014).
  * [25] Muyuan Li, Mauricio Gutiérrez, Stanley E. David, Alonzo Hernandez, and Kenneth R. Brown.  “Fault tolerance with bare ancillary qubits for a [[7,1,3]] code”.  Phys. Rev. A 96, 032341 (2017).
  * [26] Muyuan Li, Daniel Miller, and Kenneth R. Brown.  “Direct measurement of bacon-shor code stabilizers”.  Phys. Rev. A 98, 050301 (2018).
  * [27] Christof Zalka.  “Threshold estimate for fault tolerant quantum computation” (1996).  url: https://arxiv.org/abs/quant-ph/9612028.
  * [28] Nicolas Delfosse and Ben W. Reichardt.  “Short shor-style syndrome sequences” (2020).  url: https://arxiv.org/abs/2008.05051.
  * [29] Theerapat Tansuwannont, Balint Pato, and Kenneth R. Brown.  “Adaptive syndrome measurements for Shor-style error correction”.  Quantum 7, 1075 (2023).
  * [30] Héctor Bombín.  “Single-shot fault-tolerant quantum error correction”.  Phys. Rev. X 5, 031043 (2015).
  * [31] Earl T Campbell.  “A theory of single-shot error correction for adversarial noise”.  Quantum Science and Technology 4, 025006 (2019).
  * [32] A. M. Steane.  “Active stabilization, quantum computation, and quantum state synthesis”.  Phys. Rev. Lett. 78, 2252–2255 (1997).
  * [33] Shilin Huang and Kenneth R. Brown.  “Constructions for measuring error syndromes in calderbank-shor-steane codes between shor and steane methods”.  Phys. Rev. A 104, 022429 (2021).
  * [34] Shilin Huang and Kenneth R. Brown.  “Between shor and steane: A unifying construction for measuring error syndromes”.  Phys. Rev. Lett. 127, 090505 (2021).
  * [35] Shilin Huang, Kenneth R. Brown, and Marko Cetina.  “Comparing shor and steane error correction using the bacon-shor code” (2023).  url: https://arxiv.org/abs/2312.10851.
  * [36] Lukas Postler, Friederike Butt, Ivan Pogorelov, Christian D. Marciniak, Sascha Heußen, Rainer Blatt, Philipp Schindler, Manuel Rispler, Markus Muller, and Thomas Monz.  “Demonstration of fault-tolerant steane quantum error correction” (2023).  url: https://arxiv.org/abs/2312.09745.
  * [37] E. Knill.  “Quantum computing with realistically noisy devices”.  Nature 434, 39–44 (2005).
  * [38] Dave Bacon.  “Operator quantum error-correcting subsystems for self-correcting quantum memories”.  Phys. Rev. A 73, 012340 (2006).
  * [39] Panos Aliferis and Andrew W. Cross.  “Subsystem fault tolerance with the bacon-shor code”.  Phys. Rev. Lett. 98, 220502 (2007).
  * [40] Ching-Yi Lai, Yi-Cong Zheng, and Todd A. Brun.  “Fault-tolerant preparation of stabilizer states for quantum calderbank-shor-steane codes by classical error-correcting codes”.  Phys. Rev. A 95, 032339 (2017).
  * [41] Yi-Cong Zheng, Ching-Yi Lai, and Todd A. Brun.  “Efficient preparation of large-block-code ancilla states for fault-tolerant quantum computation”.  Phys. Rev. A 97, 032331 (2018).
  * [42] David Kribs, Raymond Laflamme, and David Poulin.  “Unified and generalized approach to quantum error correction”.  Phys. Rev. Lett. 94, 180501 (2005).
  * [43] David Poulin.  “Stabilizer formalism for operator quantum error correction”.  Phys. Rev. Lett. 95, 230504 (2005).
  * [44] Muyuan Li, Daniel Miller, Michael Newman, Yukai Wu, and Kenneth R. Brown.  “2d compass codes”.  Phys. Rev. X 9, 021041 (2019).
  * [45] John Napp and John Preskill.  “Optimal bacon-shor codes”.  Quantum Inf. Comput.13 (2013).  url: https://arxiv.org/abs/1209.0794.
  * [46] Dripto M Debroy, Muyuan Li, Shilin Huang, and Kenneth R Brown.  “Logical performance of 9 qubit compass codes in ion traps with crosstalk errors”.  Quantum Science and Technology 5, 034002 (2020).
  * [47] Craig Gidney and Dave Bacon.  “Less bacon more threshold” (2023).
  * [48] Laird Egan, Dripto M. Debroy, Crystal Noel, Andrew Risinger, Daiwei Zhu, Debopriyo Biswas, Michael Newman, Muyuan Li, Kenneth R. Brown, Marko Cetina, and Christopher Monroe.  “Fault-tolerant control of an error-corrected qubit”.  Nature 598, 281–286 (2021).
  * [49] Dolev Bluvstein, Simon J. Evered, Alexandra A. Geim, Sophie H. Li, Hengyun Zhou, Tom Manovitz, Sepehr Ebadi, Madelyn Cain, Marcin Kalinowski, Dominik Hangleiter, J. Pablo Bonilla Ataides, Nishad Maskara, Iris Cong, Xun Gao, Pedro Sales Rodriguez, Thomas Karolyshyn, Giulia Semeghini, Michael J. Gullans, Markus Greiner, Vladan Vuletić, and Mikhail D. Lukin.  “Logical quantum processor based on reconfigurable atom arrays”.  Nature 626, 58–65 (2024).
  * [50] Sergey Bravyi and Alexei Kitaev.  “Universal quantum computation with ideal clifford gates and noisy ancillas”.  Phys. Rev. A 71, 022316 (2005).
  * [51] Theodore J. Yoder.  “Universal fault-tolerant quantum computation with bacon-shor codes” (2017).  url: https://arxiv.org/abs/1705.01686.
  * [52] Theodore J. Yoder, Ryuji Takagi, and Isaac L. Chuang.  “Universal fault-tolerant gates on concatenated stabilizer codes”.  Phys. Rev. X 6, 031039 (2016).
  * [53] Natalie C Brown, Michael Newman, and Kenneth R Brown.  “Handling leakage with subsystem codes”.  New Journal of Physics 21, 073055 (2019).
  * [54] Juan Atalaya, Alexander N. Korotkov, and K. Birgitta Whaley.  “Error-correcting bacon-shor code with continuous measurement of noncommuting operators”.  Phys. Rev. A 102, 022415 (2020).
  * [55] Norbert M Linke, Mauricio Gutierrez, Kevin A. Landsman, Caroline Figgatt, Shantanu Debnath, Kenneth R. Brown, and Christopher Monroe.  “Fault-tolerant quantum error detection”.  Science Advances 3, e1701074 (2017).
  * [56] Nhung H. Nguyen, Muyuan Li, Alaina M. Green, C. Huerta Alderete, Yingyue Zhu, Daiwei Zhu, Kenneth R. Brown, and Norbert M. Linke.  “Demonstration of shor encoding on a trapped-ion quantum computer”.  Phys. Rev. Appl. 16, 024057 (2021).
  * [57] Smitha Janardan, Yu Tomita, Mauricio Gutiérrez, and Kenneth R. Brown.  “Analytical error analysis of clifford gates by the fault-path tracer method”.  Quantum Inf. Process. 15, 3065–3079 (2016).
  * [58] Colin J Trout, Muyuan Li, Mauricio Gutiérrez, Yukai Wu, Sheng-Tao Wang, Luming Duan, and Kenneth R Brown.  “Simulating the performance of a distance-3 surface code in a linear ion trap”.  New Journal of Physics 20, 043038 (2018).
  * [59] M. Gutiérrez, M. Müller, and A. Bermúdez.  “Transversality and lattice surgery: Exploring realistic routes toward coupled logical qubits with trapped-ion quantum processors”.  Phys. Rev. A 99, 022330 (2019).
  * [60] Scott Aaronson and Daniel Gottesman.  “Improved simulation of stabilizer circuits”.  Phys. Rev. A 70, 052328 (2004).
  * [61] Easwar Magesan, Daniel Puzzuoli, Christopher E. Granade, and David G. Cory.  “Modeling quantum noise for efficient testing of fault-tolerant circuits”.  Phys. Rev. A 87, 012324 (2013).
  * [62] Mauricio Gutiérrez, Lukas Svec, Alexander Vargo, and Kenneth R. Brown.  “Approximation of realistic errors by clifford channels and pauli measurements”.  Phys. Rev. A 87, 030302 (2013).
  * [63] Daniel Puzzuoli, Christopher Granade, Holger Haas, Ben Criger, Easwar Magesan, and D. G. Cory.  “Tractable simulation of error correction with honest approximations to realistic fault models”.  Phys. Rev. A 89, 022306 (2014).
  * [64] Mauricio Gutiérrez and Kenneth R. Brown.  “Comparison of a quantum error-correction threshold for exact and approximate errors”.  Phys. Rev. A 91, 022335 (2015).
  * [65] Mauricio Gutiérrez, Conor Smith, Livia Lulushi, Smitha Janardan, and Kenneth R. Brown.  “Errors and pseudothresholds for incoherent and coherent noise”.  Phys. Rev. A 94, 042338 (2016).
  * [66] Sergey Bravyi and Alexander Vargo.  “Simulation of rare events in quantum error correction”.  Phys. Rev. A 88, 062308 (2013).
  * [67] Eren Guttentag, Andrew Nemec, and Kenneth R. Brown.  “Robust syndrome extraction via bch encoding” (2023).  url: https://arxiv.org/abs/2311.16044.
  * [68] Sascha Heußen, Don Winter, Manuel Rispler, and Markus Müller.  “Dynamical subset sampling of quantum error-correcting protocols”.  Phys. Rev. Res. 6, 013177 (2024).
  * [69] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill.  “Topological quantum memory”.  Journal of Mathematical Physics 43, 4452–4505 (2002).
  * [70] H. Bombin and M. A. Martin-Delgado.  “Optimal resources for topological two-dimensional stabilizer codes: Comparative study”.  Phys. Rev. A 76, 012305 (2007).
  * [71] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland.  “Surface codes: Towards practical large-scale quantum computation”.  Phys. Rev. A 86, 032324 (2012).
  * [72] Michael E. Beverland, Prakash Murali, Matthias Troyer, Krysta M. Svore, Torsten Hoefler, Vadym Kliuchnikov, Guang Hao Low, Mathias Soeken, Aarthi Sundaram, and Alexander Vaschillo.  “Assessing requirements to scale to practical quantum advantage” (2022).  arXiv:2211.07629.
  * [73] Weilei Zeng, Alexei Ashikhmin, Michael Woolls, and Leonid P. Pryadko.  “Quantum convolutional data-syndrome codes”.  In 2019 IEEE 20th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC).  Pages 1–5.  (2019).
  * [74] Christopher Chamberland and Michael E. Beverland.  “Flag fault-tolerant error correction with arbitrary distance codes”.  Quantum 2, 53 (2018).

##  Appendix A Calculating the Polynomial Expansion Coefficients

To calculate the coefficients of the logical error rate polynomial expansion
we can expand Equation 1 to get a function of the physical error rates and
then add all the coefficients corresponding to the term we wish to find. For
the cases presented in this paper, the error subsets have only three indices.
If all errors occur with the same probability $p$, $A_{\vec{w}}$ is given by
Equation 3.

$\displaystyle A_{\vec{w}}$
$\displaystyle=\binom{n_{1}}{w_{1}}\binom{n_{2}}{w_{2}}\binom{n_{3}}{w_{3}}p^{w_{tot}}(1-p)^{n_{tot}-w_{tot}}$
$\displaystyle=\sum_{r=0}^{n_{tot}-w_{tot}}(-1)^{r}\binom{n_{1}}{w_{1}}\binom{n_{2}}{w_{2}}\binom{n_{3}}{w_{3}}\binom{n_{tot}-w_{tot}}{r}p^{w_{tot}+r}$
(3)

where $n_{1}$ is the number of 1-qubit gates and state preparations, $n_{2}$
is the number of 2-qubit gates, and $n_{3}$ is the number of measurements in
the circuit; $w_{1}$ is the number of errors after 1-qubit gates and state
preparations, $w_{2}$ is the number of errors after 2-qubit gates, and $w_{3}$
is the number of errors after measurements for the particular error subset
$A_{\vec{w}}$; $n_{tot}=n_{1}+n_{2}+n_{3}$ and $w_{tot}=w_{1}+w_{2}+w_{3}$.
Substituting Equation 3 into Equation 1 we get Equation 4.

$p_{L}^{(lower)}=\sum_{\vec{w}=(0,0,...,0)}^{\vec{w}_{max}}\sum_{r=0}^{n_{tot}-w_{tot}}(-1)^{r}\binom{n_{1}}{w_{1}}\binom{n_{2}}{w_{2}}\binom{n_{3}}{w_{3}}\binom{n_{tot}-w_{tot}}{r}p^{w_{tot}+r}\,p_{L}^{(\vec{w})}$
(4)

Then we can get the coefficient $c_{l}$ of the term $p^{l}$ by adding the
coefficients of all the terms that satisfy $w_{tot}+r=l$, as shown equation 5

$\displaystyle c_{l}$ $\displaystyle=\sum_{\begin{subarray}{c}r=0\\\
w_{tot}+r=l\end{subarray}}^{n_{tot}-w_{tot}}(-1)^{r}p_{L}^{(\vec{w})}\binom{n_{1}}{w_{1}}\binom{n_{2}}{w_{2}}\binom{n_{3}}{w_{3}}\binom{n_{tot}-w_{tot}}{r}$
(5)

##  Appendix B GHZ Preparation Circuits

The circuits used to prepare the GHZ states are shown in figures 10, 11, 12,
13 and 14. The circuit used to perform ShorSEM for a distance-3 BS code is
shown in Figure 15.

$\Qcircuit@C=0.01em@R=0.01em@!{\lstick{\ket{0}}&\gate{H}\ctrl{1}\qw\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\targ\ctrl{1}\qw\qw\ctrl{4}\qw\qw\\\
\lstick{\ket{0}}\qw\qw\targ\ctrl{1}\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\targ\ctrl{1}\qw\ctrl{2}\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\targ\qw\qw\qw\\\
\lstick{\ket{0}}\targ\targ\measuretab{M_{z}}\\\ }$ Figure 10: Circuit used to
prepare a distance-5 GHZ state with 1 verification. This circuit is formally
fault-tolerant.
$\Qcircuit@C=0.01em@R=0.01em@!{\lstick{\ket{0}}&\gate{H}\ctrl{1}\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\targ\ctrl{1}\qw\qw\qw\qw\ctrl{6}\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\targ\ctrl{1}\qw\qw\qw\qw\qw\ctrl{6}\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\targ\ctrl{1}\qw\qw\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\targ\ctrl{1}\qw\qw\ctrl{3}\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\qw\targ\ctrl{1}\qw\qw\qw\ctrl{3}\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\qw\qw\targ\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\targ\targ\qw\qw\measuretab{M_{z}}\\\
\lstick{\ket{0}}\qw\qw\targ\targ\measuretab{M_{z}}\\\ }$ Figure 11: Circuit
used to prepare a distance-7 GHZ state with 2 verifications. This circuit is
formally not fault-tolerant.
$\Qcircuit@C=0.01em@R=0.01em@!{\lstick{\ket{0}}&\gate{H}\ctrl{1}\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\targ\ctrl{1}\qw\qw\qw\qw\ctrl{6}\qw\ctrl{7}\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\targ\ctrl{1}\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\targ\ctrl{1}\qw\qw\qw\qw\qw\qw\ctrl{6}\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\targ\ctrl{1}\qw\qw\ctrl{3}\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\qw\targ\ctrl{1}\qw\qw\qw\ctrl{3}\qw\ctrl{4}\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\qw\qw\targ\qw\qw\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\targ\targ\qw\qw\qw\qw\measuretab{M_{z}}\\\
\lstick{\ket{0}}\qw\qw\targ\targ\qw\qw\measuretab{M_{z}}\\\
\lstick{\ket{0}}\qw\qw\qw\qw\targ\targ\measuretab{M_{z}}\\\ }$ Figure 12:
Circuit used to prepare a distance-7 GHZ state with 3 verifications. This
circuit is formally fault-tolerant.
$\Qcircuit@C=0.01em@R=0.01em@!{\lstick{\ket{0}}&\gate{H}\ctrl{1}\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\targ\ctrl{1}\qw\qw\qw\qw\qw\qw\ctrl{8}\qw\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\targ\ctrl{1}\qw\qw\qw\qw\qw\qw\qw\ctrl{8}\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\targ\ctrl{1}\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\targ\ctrl{1}\qw\qw\qw\qw\qw\qw\qw\ctrl{7}\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\qw\targ\ctrl{1}\qw\qw\qw\qw\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\qw\qw\targ\ctrl{1}\qw\qw\ctrl{3}\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\qw\qw\qw\targ\ctrl{1}\qw\qw\qw\ctrl{3}\qw\ctrl{4}\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\qw\qw\qw\qw\targ\qw\qw\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\targ\targ\qw\qw\qw\qw\measuretab{M_{z}}\\\
\lstick{\ket{0}}\qw\qw\targ\targ\qw\qw\measuretab{M_{z}}\\\
\lstick{\ket{0}}\qw\qw\qw\qw\targ\targ\measuretab{M_{z}}\\\ }$ Figure 13:
Circuit used to prepare a distance-9 GHZ state with 3 verifications. This
circuit is formally not fault-tolerant.
$\Qcircuit@C=0.01em@R=0.01em@!{\lstick{\ket{0}}&\gate{H}\ctrl{1}\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\targ\ctrl{1}\qw\qw\qw\qw\qw\qw\ctrl{8}\qw\qw\qw\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\targ\ctrl{1}\qw\qw\qw\qw\qw\qw\qw\ctrl{8}\qw\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\targ\ctrl{1}\qw\qw\qw\qw\qw\qw\qw\qw\ctrl{8}\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\targ\ctrl{1}\qw\qw\qw\qw\ctrl{5}\qw\qw\qw\qw\ctrl{8}\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\qw\targ\ctrl{1}\qw\qw\qw\qw\qw\qw\qw\ctrl{6}\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\qw\qw\targ\ctrl{1}\qw\qw\qw\qw\qw\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\qw\qw\qw\targ\ctrl{1}\qw\qw\qw\ctrl{3}\qw\qw\qw\ctrl{5}\qw\\\
\lstick{\ket{0}}\qw\qw\qw\qw\qw\qw\qw\qw\targ\qw\qw\qw\qw\qw\qw\qw\qw\qw\\\
\lstick{\ket{0}}\targ\targ\qw\qw\qw\qw\qw\qw\measuretab{M_{z}}\\\
\lstick{\ket{0}}\qw\qw\targ\targ\qw\qw\qw\qw\measuretab{M_{z}}\\\
\lstick{\ket{0}}\qw\qw\qw\qw\targ\targ\qw\qw\measuretab{M_{z}}\\\
\lstick{\ket{0}}\qw\qw\qw\qw\qw\qw\targ\targ\measuretab{M_{z}}\\\ }$ Figure
14: Circuit used to prepare a distance-9 GHZ state with 4 verifications. This
circuit is formally not fault-tolerant. Figure 15: Circuit used to extract the
X-stabilizer syndromes using ShorSEM for a distance-3 Bacon-Shor code. We used
an analogous circuit to extract the syndromes for higher distances.

##  Appendix C Lookup tables

For the space decoding of the BS code we used lookup tables. For distances 3
and 5 the lookup tables used are shown in Table 2 and Table 3 respectively.
The lookup tables for distances 7 and 9 are analogous. They correspond to the
lookup tables of a repetition code. For each distance $d$, the X (Z)
stabilizers correspond to weight-$2d$ vertical (horizontal) rectangles.

$S_{X,1}$ | $S_{X,2}$ | Correction
---|---|---
0 | 0 | $I$
0 | 1 | $Z_{3}$
1 | 0 | $Z_{1}$
1 | 1 | $Z_{2}$
(a) X stabilizers to correct Z errors.

$S_{Z,1}$ | $S_{Z,2}$ | Correction
---|---|---
0 | 0 | $I$
0 | 1 | $X_{7}$
1 | 0 | $X_{1}$
1 | 1 | $X_{4}$
(b) Z stabilizers to correct X errors.

Table 2: Lookup tables for the distance-3 BS code.
$S_{X,1}=X_{1}X_{2}X_{4}X_{5}X_{7}X_{8}$,
$S_{X,2}=X_{2}X_{3}X_{5}X_{6}X_{8}X_{9}$,
$S_{Z,1}=Z_{1}Z_{2}Z_{3}Z_{4}Z_{5}Z_{6}$,
$S_{Z,2}=Z_{4}Z_{5}Z_{6}Z_{7}Z_{8}Z_{9}$.

$S_{X,1}$ | $S_{X,2}$ | $S_{X,3}$ | $S_{X,4}$ | Correction
---|---|---|---|---
0 | 0 | 0 | 0 | $I$
0 | 0 | 0 | 1 | $Z_{5}$
0 | 0 | 1 | 0 | $Z_{4}Z_{5}$
0 | 0 | 1 | 1 | $Z_{4}$
0 | 1 | 0 | 0 | $Z_{1}Z_{2}$
0 | 1 | 0 | 1 | $Z_{3}Z_{4}$
0 | 1 | 1 | 0 | $Z_{3}$
0 | 1 | 1 | 1 | $Z_{3}Z_{5}$
1 | 0 | 0 | 0 | $Z_{1}$
1 | 0 | 0 | 1 | $Z_{1}Z_{5}$
1 | 0 | 1 | 0 | $Z_{2}Z_{3}$
1 | 0 | 1 | 1 | $Z_{1}Z_{4}$
1 | 1 | 0 | 0 | $Z_{2}$
1 | 1 | 0 | 1 | $Z_{2}Z_{5}$
1 | 1 | 1 | 0 | $Z_{1}Z_{3}$
1 | 1 | 1 | 1 | $Z_{2}Z_{4}$
(a) X stabilizers to correct Z errors.

$S_{Z,1}$ | $S_{Z,2}$ | $S_{Z,3}$ | $S_{Z,4}$ | Correction
---|---|---|---|---
0 | 0 | 0 | 0 | $I$
0 | 0 | 0 | 1 | $X_{21}$
0 | 0 | 1 | 0 | $X_{16}X_{21}$
0 | 0 | 1 | 1 | $X_{16}$
0 | 1 | 0 | 0 | $X_{1}X_{6}$
0 | 1 | 0 | 1 | $X_{11}X_{16}$
0 | 1 | 1 | 0 | $X_{11}$
0 | 1 | 1 | 1 | $X_{11}X_{21}$
1 | 0 | 0 | 0 | $X_{1}$
1 | 0 | 0 | 1 | $X_{1}X_{21}$
1 | 0 | 1 | 0 | $X_{6}X_{11}$
1 | 0 | 1 | 1 | $X_{1}X_{16}$
1 | 1 | 0 | 0 | $X_{6}$
1 | 1 | 0 | 1 | $X_{6}X_{21}$
1 | 1 | 1 | 0 | $X_{1}X_{11}$
1 | 1 | 1 | 1 | $X_{6}X_{16}$
(b) Z stabilizers to correct X errors.

Table 3: Lookup tables for distance-5 BS code. The stabilizers are analogous
to the distance-3 stabilizers: weight-$10$ vertical (horizontal) rectangles
for the X(Z) stabilizers.

##  Appendix D Number of gates for the various circuit constructions

To calculate the total number of gates, for SteaneSEM, we assume that the GHZ
verifications are done only once. Since ShorSEM is adaptive, we do not know a
priori how many rounds of stabilizer measurements will be run. The number of
gates we report correspond to the maximal number of stabilizer rounds, which
are given in [29].

d | Steane | Shor
---|---|---
v=0 | v=1 | v=2 | v=3 | v=4 | weak | strong
3 | 30 | – | – | – | – | 48 | 72
5 | 90 | 110 | – | – | – | 320 | 400
7 | – | – | 238 | 266 | – | 1176 | 1344
9 | – | – | – | 414 | 450 | 2880 | 3168
Table 4: Total number of CNOT gates for the various protocols that we study in this paper. d | Steane | Shor
---|---|---
v=0 | v=1 | v=2 | v=3 | v=4 | weak | strong
3 | 18 | – | – | – | – | 8 | 12
5 | 50 | 60 | – | – | – | 32 | 40
7 | – | – | 126 | 140 | – | 84 | 96
9 | – | – | – | 216 | 234 | 160 | 176
Table 5: Total number of measurements for the various protocols that we study
in this paper.