# Spacetime codes of Clifford circuits

Nicolas Delfosse  Adam Paetznick

###### Abstract

We propose a scheme for detecting and correcting faults in any Clifford
circuit. The scheme is based on the observation that the set of all possible
outcome bit-strings of a Clifford circuit is a linear code, which we call the
“outcome code”. From the outcome code we construct a corresponding stabilizer
code, the “spacetime code”. Our construction extends the circuit-to-code
construction of Bacon, Flammia, Harrow and Shi [2], revisited recently by
Gottesman [16], to include intermediate and multi-qubit measurements. With
this correspondence, we reduce the problem of correcting faults in a circuit
to the well-studied problem of correcting errors in a stabilizer code. More
precisely, a most likely error decoder for the spacetime code can be
transformed into a most likely fault decoder for the circuit. We give
efficient algorithms to construct the outcome and spacetime codes. We also
identify conditions under which these codes are LDPC, and give an algorithm to
generate low-weight checks, which can then be combined with efficient LDPC
code decoders.

Several small quantum computing platforms are available today. However, the
high noise rate of quantum hardware is a major obstacle to the scalability of
these devices. Some form of quantum error correction is likely necessary in
order to achieve noise low enough for solving large-scale industrial problems.

The traditional solution to the noise problem is to execute quantum algorithms
on error-corrected qubits. First, choose a quantum error correction code to
encode each qubit. Second, design a syndrome extraction circuit for this code.
This quantum circuit is run regularly and returns a bit string, the so-called
syndrome, which is then used to identify errors. This code-centric approach
has limitations, however. For example, Floquet codes are not obtained through
this traditional solution and are instead defined directly by a circuit.

In this work, we take a circuit-centric approach. We describe a general method
for correcting faults in Clifford circuits. This methods applies not only to
syndrome extraction circuits of stabilizer codes and Floquet codes, but also
to general Clifford circuits that were not initially designed as a syndrome
extraction circuit. The basic idea is that these circuits can include some
other type of redundancy that can be exploited to correct circuit faults. Such
a circuit-centric approach was also considered previously in [2, 16, 13].
Clifford circuits are central for quantum computing because they implement
standard protocols such as quantum teleportation, preparation of Bell states
or error correction with stabilizer codes. Even though they are not universal
for quantum computing directly, universality can be achieved with Clifford
circuits by the injection of magic states [6].

We consider circuits made with unitary Clifford gates and Pauli measurements.
We allow all Pauli measurements, not just single-qubit measurements, and we
allow for internal measurements that can occur at any time step of the
circuit.

Collectively, the measurement outcomes of a circuit produce a classical bit-
string. Our basic idea is to correct circuit faults using redundancy in these
bit-strings. We prove that the set of possible outcome bit-strings of a
Clifford circuit is a linear code (up to relabeling the measurement outcomes);
see Theorem 1 and Corollary 2. We call this the “outcome code” of the circuit.
Moreover, we design an algorithm that returns a complete set of checks for the
outcome code; see Algorithm 1.

The “outcome code” can be used directly to detect and correct circuit faults.
Doing so, however, requires designing a decoder, generally a non-trivial task.
Instead of designing a new decoder that maps check values onto circuit faults,
we construct a stabilizer code associated with the circuit, the “spacetime
code”; see Theorem 2. Measuring the generators of the spacetime code provides
corresponding values of the checks of the outcome code. We show how to design
a circuit decoder that returns a most likely fault configuration using a most
likely error decoder for the spacetime stabilizer code; see Theorem 3.

The spacetime code defined in this paper is related to the circuit-to-code
construction of Bacon, Flammia, Harrow and Shi [2]. There, the authors
proposed a transformation of a restricted class of Clifford circuits with the
goal of building new subsystem codes. They considered a subclass of post-
selection circuits and computed the parameters of the resulting subsystem code
as a function of the input circuit. Recently, Gottesman extended this
formalism to circuits with Clifford unitaries and single-qubit preparation and
measurement [16].111The term _spacetime code_ follows terminology introduced
by [16]. The spacetime code we consider can be seen as the stabilizer code
associated with the subsystem code of [2, 16] after generalizing their
constructions to arbitrary Clifford circuits. The stabilizer generators of the
spacetime code we consider here coincide with “detectors” considered by [19],
where they were used to optimize surface codes for particular architecture
constraints.

Throughout, we provide new proofs of the properties of the spacetime code
based on the relation between the forward and the backward propagation of the
faults through the circuit. Namely, we prove that backward propagation is the
adjoint of forward propagation. This alternative approach unifies the
treatment of all Clifford circuits and sheds some light on the underlying
mathematical structure of the spacetime code. We believe that this relation
could also be relevant for other applications.

Equipped with the outcome code, one can build a scheme for the correction of
any small Clifford circuit using a lookup decoder. To push the range of
application further, we propose an algorithm to produce a set of low-weight
stabilizer generators for the spacetime code 3, resulting in a Low-Density
Parity-Check (LDPC) spacetime code for which efficient decoders exist [12, 21,
24, 8]. Starting from a local code in $D$ dimensions, that is, a code defined
by local stabilizer generators in a $D$-dimensional grid of qubits, our
algorithm produces local stabilizer generators in $D+1$ dimensions for which
topological decoders such as the Renormalization Group decoder [5] can be
used.

Our fault correction scheme applies to any Clifford circuit, but syndrome
extraction circuits are of special interest. The design of a quantum error
correction scheme is a non-trivial task which requires (i) a syndrome
extraction circuit, (ii) a syndrome map, (iii) a decoder. With our work, the
construction of the syndrome map and the decoder can be automated in some
cases. We do not provide a performance guarantee for the resulting scheme, and
we believe that some specialized schemes, highly optimized for a specific
circuit, are likely to perform better. The main advantage of our approach is
its flexibility. Our approach only requires the circuit to be given as an
input and it applies to codes implemented with Clifford operations or Pauli
measurements. This includes for instance CNOT-based surface codes [10, 11] or
color codes [4], Majorana-based surface codes [7] or Floquet codes [17] that
are implemented with only joint measurements.

This article is organized as follows. In order to motivate our results, we
start by describing an application of the outcome code and the spacetime code
in Section 1. Namely, we discuss the implementation of an automated scheme for
the correction of faults in Clifford circuits. The rest of the paper provides
a complete description of all the ingredients. Background material is
introduced in Section 2. Then, Section 3 proves some core technical results
and establishes the relation between the propagation and the backpropagation
operators. The outcome code is defined in Section 4 which also describes an
algorithm (Algorithm 1) to compute a complete set of checks for this code. The
spacetime code is introduced in Section 5 where we prove that a most-likely
error decoder for the spacetime code can be converted into a circuit decoder
that returns a most likely set of faults (Theorem 3). Section 6 provides an
algorithm (Algorithm 3) to generate low-weight generators for the spacetime
code.

Figure 1:  Construction of codes from a Clifford circuit. Given a Clifford
circuit as input, a modified stabilizer simulation, Algorithm 1, produces the
outcome code. The corresponding spacetime code can then be constructed by
accumulating measurement observables from the outcome code backward through
the circuit. See Section 5.1. Low-weight generators of the spacetime code are
obtained by sparsification with Algorithm 3. The dashed arrow indicates that
sparsification is not possible for all circuits. All constructions run in
polynomial time. The LDPC spacetime code can be decoded using any quantum LDPC
code decoder, thereby providing an automated and efficient means of correcting
faults given only the circuit as an input.

##  1 Applications of the outcome code and the spacetime code

In this section, we combine all the ingredients developed in this article to
describe a flexible scheme for the correction of faults in Clifford circuits.
The full protocol is illustrated in Figure 1. Detailed descriptions of all the
ingredients are provided in subsequent sections.

###  1.1 Standard design procedure for a quantum error correction scheme

To emphasize the advantage of our approach, we first review the general
approach to designing and simulating a quantum error correction scheme. For
simplicity, we focus on stabilizer codes and consider the standard circuit
noise model explained in Section 2.

To describe a complete quantum error correction scheme for a given stabilizer
code, we must design the following components:

  1. 1.

Syndrome extraction circuit: A quantum circuit that takes as input a noisy
encoded state and returns a bit string.

  2. 2.

Syndrome map: A classical procedure that takes as input the outcome of the
syndrome extraction circuit and returns bit string that we call the syndrome.

  3. 3.

Decoder: A classical procedure that takes as input the syndrome and that
returns a correction to apply to the encoded state.

These three components are non-trivial and tightly coupled, in general.
Designing a syndrome extraction circuit requires working within the
constraints of a specific architecture. See, for example, [7, 14, 23]. The
decoding problem is notoriously difficult [3, 18]. Some specific cases have
been worked out. For example, with the surface code, one can consider the
standard syndrome extraction circuit [11], a carefully chosen sequence of CNOT
gates and measurements of ancillary qubits. The syndrome of this circuit is
obtained by xor of consecutive outcomes for each ancilla. The syndrome is then
input to a surface code decoder such as a Minimum Weight Perfect Matching
decoder [10] or Union-Find decoder [9].

The effectiveness of the decoder depends tightly on the choice of syndrome
map. Indeed, the surface code decoders mentioned above may be ineffective for
other choices of syndromes. The syndrome map, in turn, depends on the details
of both the code and the circuit; see Floquet codes [17]. Any change to the
circuit or the code requires corresponding modification of the syndrome map.

###  1.2 Automated circuit-fault correction

Here, we propose a protocol described in Figure 1 for correcting faults that
requires only the Clifford circuit as an input, instead of the three
components required in the previous section. Consider a Clifford circuit
${\cal C}$ with $m$ measurements. The first step of the protocol is the
computation of a set of outcome checks
$u_{1},\dots,u_{r}\in\mathbb{Z}_{2}^{m}$ using Algorithm 1. In the absence of
faults, running the circuit ${\cal C}$ produces an outcome bit-string
$o\in\mathbb{Z}_{2}^{m}$ that satisfies $(o|u_{1})=\dots=(o|u_{r})=0$.
Therefore, one can use these values to detect and correct circuit faults.
Moreover, the set of outcome checks returned by Algorithm 1 is maximal. It
fully describes the set of possible outcomes for the circuit, which means that
we are using all the information available to detect and correct faults.

Given the outcome checks, we need to design a syndrome map and a decoder in
order to transform the check values $(o|u_{i})$ into a correction to apply to
the output state of the circuit. For small circuits, this can be done with the
syndrome map $o\mapsto\sigma$ where $\sigma_{i}=(o|u_{i})$ and a lookup
decoder. Naively, we can construct a lookup decoder for the circuit ${\cal C}$
using the outcome checks $u_{i}$ as follows. Loop over all the fault
configurations of the circuit with up to $M$ faults for some integer $M$. For
each fault configuration $F$, compute the syndrome value $\sigma$ and store a
configuration made with a minimum number of faults for each syndrome $\sigma$.

Lookup decoders are impractical for large codes. To make the decoding of large
circuit possible, we must restrict the set of schemes we consider because the
decoding problem for linear codes and stabilizer codes is generally
intractable [3, 18]. We focus on circuits that admit local redundancy in the
sense that the spacetime code of the circuit has many low-weight stabilizers.
This assumption is even more justified because the value of an outcome check
corresponding to a high-weight stabilizer in the spacetime code will be very
noisy and unreliable.

After computing the outcome checks $u_{1},\dots,u_{r}$ using Algorithm 1, we
compute the corresponding stabilizers
$\overleftarrow{F(u_{1})},\dots,\overleftarrow{F(u_{r})}$ defined in Eq. (20).
Then, we run Algorithm 3 to produce a set low-weight stabilizer generators for
the spacetime code. These generators define a new syndrome map whose
components are related to the check values $(o|u_{i})$ by a linear map. We are
now equipped with a set of low-weight generators and therefore one can use any
LDPC code decoder for this code. Existing LDPC decoder options include the
Union-Find decoder for local topological codes [9] or for LDPC codes [8].
Other decoding strategies can be used, such as the Renormalization Group
decoder [5] for topological codes or a Belief Propagation decoder for LDPC
codes [21, 24].

##  2 Background

###  2.1 Linear codes

A linear code with length $n$ is a $\mathbb{Z}_{2}$-linear subspace of
$\mathbb{Z}_{2}^{n}$. It encodes $k$ bits into $n$ bits where $k$ is the
dimension of the code. The dual code of a linear code $C$ with length $n$,
denoted $C^{\perp}$, is the set of vectors of $\mathbb{Z}_{2}^{n}$ that are
orthogonal with all the vectors of $C$. Orthogonality is with respect to the
binary inner product $(u|v)=\sum_{i=1}^{n}u_{i}v_{i}\pmod{2}.$

A linear code can be defined by providing a set of generators of the code or
by providing a set of generators of the dual code. Given a set of generators
of the dual code $u_{1},\dots,u_{r}\in\mathbb{Z}_{2}^{n}$, the code is the set
of vectors $v\in\mathbb{Z}_{2}^{n}$ that satisfy $(u_{i}|v)=0$ for all
$i=1,\dots,r$. We refer to the vectors $u_{i}$ as the “checks” of the code.

The syndrome map associated with the checks
$u_{1},\dots,u_{r}\in\mathbb{Z}_{2}^{n}$ is the map

$\displaystyle\sigma:\mathbb{Z}_{2}^{n}\longrightarrow\mathbb{Z}_{2}^{r}$ (1)

that sends a vector $v$ onto the vector $s$ whose $i$th component is
$s_{i}=(u_{i}|v)$. The vector $s$ is called the syndrome of $u$. The syndrome
can be used to correct some bit flips of the corresponding vector and to map
it back to the code space.

###  2.2 Stabilizer codes

A stabilizer code with length $n$ is defined by a set of commuting $n$-qubit
Pauli operators ${\cal S}$, that we call stabilizer generators, such that the
group $\langle{\cal S}\rangle$ they generate does not contain $-I$. We refer
to the group $\langle{\cal S}\rangle$ as the stabilizer group of the code and
a Pauli operator $P$ such that $\pm P\in\langle{\cal S}\rangle$ is called a
stabilizer.

The code space of a stabilizer code with length $n$ is the subspace of
$(\mathbb{C}_{2})^{\otimes n}$ that is invariant under the stabilizer
generators. If ${\cal S}$ contains $r$ independent operators, the code space
is a subspace of $(\mathbb{C}_{2})^{\otimes n}$ isomorphic with
$(\mathbb{C}_{2})^{\otimes n-r}$. We interpret this subspace as the encoding
of $k=n-r$ (logical) qubits into $n$ (physical) qubits.

Error correction with a stabilizer code is based on the measurement of a set
of stabilizer generators ${\cal S}=\\{S_{1},\dots,S_{r}\\}$. This produces an
outcome $\sigma\in\mathbb{Z}_{2}^{r}$ called the syndrome. Here the outcome
$\sigma_{i}$ corresponds to the eigenvalue $(-1)^{\sigma_{i}}$ for the $i$th
measured stabilizer generator. If the state of the system before syndrome
measurement is a code state suffering from Pauli error $E\in{\overline{\cal
P}}_{n}$, then the measurement returns a syndrome $\sigma$ such that
$\sigma_{i}=[E,S_{i}]$ where $[E,S_{i}]$ is 0 if $E$ and $S_{i}$ commute and 1
otherwise. In the absence of error, the syndrome is trivial. Therefore, a non-
trivial syndrome can be used to detect and correct errors on encoded states.

We denote by ${\cal P}_{n}$ the set of $n$-qubit Pauli operators and by
${\overline{\cal P}}_{n}$ its quotient by the phase operators $\\{\pm I,\pm
iI\\}$. In other words, in ${\overline{\cal P}}_{n}$ we consider Pauli
operators up to a phase. It is natural to consider Pauli errors up to a phase
because a global phase has no effect on quantum states. Given a probability
distribution over Pauli errors, a most likely error decoder (MLE decoder) is a
map $\mathbb{Z}_{2}^{r}\mapsto{\overline{\cal P}}_{n}$ that sends a syndrome
$\sigma$ to the Pauli $E$ with maximum probability among Pauli errors with
syndrome $\sigma$.

A logical operator is a Pauli operator that commutes with all stabilizer
generators of the code. A logical operator is non-trivial if it is not a
stabilizer. For any subset $A$ of ${\overline{\cal P}}_{n}$, we use the
notation

$\displaystyle A^{\perp}=\\{Q\in{\overline{\cal P}}_{n}\ |\ \forall P\in
A,[P,Q]=0\\}$ (2)

for the set of $n$-qubit Pauli operators that commute with all the elements of
$A$. If $\langle{\cal S}\rangle$ is a stabilizer group, then ${\cal
S}^{\perp}$ is the set of logical operators and ${\cal
S}^{\perp}\backslash\langle{\cal S}\rangle$ is the set of non-trivial logical
operators of the code.

###  2.3 Clifford circuits

We consider circuits composed of Clifford unitaries and Pauli measurements.
Qubit preparation of the state $|{0}\rangle$ can be emulated by measuring $Z$.
We assume that all the qubits are present at the beginning of the circuit and
no qubit can be added through the circuit. This is not a restriction because a
qubit can be reinitialized using a single qubit measurement as explained
above. We do not impose any restriction on the size of the support of allowed
operations, but our results also apply to circuits limited to single-qubit and
two-qubit gates or contexts in which connectivity is limited to nearest
neighbors, for example. Our results also hold for Clifford circuits with Pauli
fixes, but are not included here to keep the notation simple.

A Clifford circuit is a sequence of $s$ Clifford operations ${\cal
C}=(C_{1},\dots,C_{s})$ applied to $n$ qubits. Each operation $C_{i}$ is
applied at a given time step, denoted
$\operatorname{level}(C_{i})\in\\{1,2,\dots\\}$, that we call the level of the
operation. The depth of a circuit, denoted $\Delta({\cal C})$, is the maximum
level of its operations. To guarantee that they can be implemented
simultaneously, we require that two operations with the same level have
disjoint support. We assume that the circuit operations are given in
chronological order, that is $i\leq j$ implies
$\operatorname{level}(C_{i})\leq\operatorname{level}(C_{j})$.

We refer to the state of the $n$ qubits of the circuit before the first
circuit operation as the input state of the circuit and the final state of the
$n$ qubits is the output state of the circuit. We do not place any constraint
on the input state of the circuit.

Throughout, $m$ denotes the number of Pauli measurements in the circuit and we
denote by $S_{1},\dots,S_{m}$ the measured operators. For all $j=1,\dots,m$,
the level of the measurement $S_{j}$ is denoted $\ell_{j}$. By definition, we
have $0\leq m\leq s$, where $s$ is the number of operations of the circuit,
and each $\ell_{j}$ is an integer in the set $\\{1,\dots,\Delta({\cal C})\\}$.

###  2.4 Circuit faults

We consider a standard circuit noise model where each circuit operation
$C_{i}$ and each idle qubit is faulty with probability $p_{i}$. If a unitary
gate or an idle qubit is faulty, it is followed by a uniform random Pauli
error $E$ acting on its support. A faulty measurement is followed by a uniform
random Pauli error $E$ acting on its support combined with a flip of the
measurement outcome with probability 1/2.

Following [2], it is convenient to represent faults as Pauli operators acting
on half-integer time steps as shown in Fig. 2. A fault operator for a circuit
${\cal C}$ acting on $n$ qubits with depth $\Delta$ is a Pauli operator
$F\in{\overline{\cal P}}_{n(\Delta+1)}$ acting on $n(\Delta+1)$ qubits indexed
by pairs $(\ell+0.5,q)$ where $\ell\in\\{0,1,\dots,\Delta\\}$ represents a
level of the circuit and $q\in\\{1,\dots,n\\}$ corresponds to a qubit. We
include $\ell=0$ to represent faults on the input qubits of the circuit. The
component of $F$ on qubit $(\ell+0.5,q)$ is denoted
$F_{\ell+0.5,q}\in\\{I,X,Y,Z\\}$. It corresponds to the fault occurring right
after level $\ell$ on qubit $q$. We also use the notation $F_{\ell+0.5}$ for
the $n$-qubit Pauli operator $\otimes_{q=1}^{n}F_{\ell+0.5,q}$ which
represents the fault occurring right after the level $\ell$ of the circuit.

The flip of a measurement outcome can also be represented as a fault operator.
Let $P\in{\overline{\cal P}}_{n}$ be a measured Pauli operator and let
$Q\in{\overline{\cal P}}_{n}$ be a weight-one operator $Q$ that anti-commutes
with $P$. Then, the fault operator $F$ such that $F_{\ell-0.5}=Q$ and
$F_{\ell+0.5}=Q$ is a representation of the flip of the outcome of the
measurement of $P$ at level $\ell$.

We assume a noise model that describes the probability of each combination of
circuit faults. The corresponding probability distribution over the set of
fault operators is denoted by $\mathbb{P}_{\cal F}$.

###  2.5 Propagation of Pauli faults and cumulant

The effect of a set of faults on the outcomes of a circuit can be determined
by propagating the faults through the circuit as shown in Fig. 2.

(a)

(b)

Figure 2: A depth-three circuit with Pauli measurements and unitary Clifford
gates. Pauli faults are supported on the white circles. We show a fault
operator in (a) and its back-cumulant in (b) obtained by propagation of faults
backward. In this circuit, the third measurement is redundant and the three
measurement outcomes $o_{1},o_{2},o_{3}$ satisfy
$o_{1}+o_{2}+o_{3}=0\pmod{2}$. This defines a check of the outcome code. The
stabilizer generator of the spacetime code corresponding to this check is
obtained by the backward accumulation of the three measurements through the
circuit. This results in the weight-four Pauli operator shown in (b) supported
on the circles.

The basic idea of fault propagation is that a Pauli fault $P\in{\overline{\cal
P}}_{n}$ occurring before a unitary operation $U$ is equivalent to a fault
$UPU^{-1}$ after the operation $g$. We refer to $UPU^{-1}$ as the conjugation
of $P$ by $U$. In the case of a Pauli measurement, a fault propagates through
the corresponding projector unchanged, and it leads to a flip of the
measurement outcome if the Pauli fault preceding the measurement anti-commutes
with the measured operator.

The cumulant of a fault operator $F$ through a circuit ${\cal C}$ with depth
$\Delta$, is the fault operator denoted $\overrightarrow{F}$ obtained by the
following procedure.

  1. 1.

Initialize $\overrightarrow{F}$ as $\overrightarrow{F}=F$.

  2. 2.

For all levels $\ell=1,2,\dots,\Delta$ do:

    1. (a)

Let $E=\overrightarrow{F}_{\ell-0.5}$.

    2. (b)

Conjugate $E$ by the product of all unitary operations of ${\cal C}$ with
level $\ell$.

    3. (c)

Multiply $\overrightarrow{F}_{\ell+0.5}$ by $E$.

When propagating $\overrightarrow{F}_{\ell-0.5}$ through the operations with
level $\ell$, the order in which these operations are selected is not relevant
because they do not overlap.

The cumulant $\overrightarrow{F}$ is defined in such a way that the operator
$\overrightarrow{F}_{\ell+0.5}$ is the Pauli error resulting from the
combination of all the faults occurring during the first $\ell$ levels of the
circuit. The cumulant was introduced in [2] as the spackle operator.

###  2.6 Effect of circuit faults

Consider a depth-$\Delta$ Clifford circuit ${\cal C}$ acting on $n$ qubits.
Assume that the circuit contains $m$ Pauli measurements. The $m$ measured
operators are denoted by $S_{1},\dots,S_{m}$ and for all $j=1,\dots,m$ let
$\ell_{j}$ denote the level of the measurement of the operator $S_{j}$.

Executing the quantum circuit ${\cal C}$ produces two types of data:

  * •

the outcome bit-string $o\in\mathbb{Z}_{2}^{m}$ is the bit-string with $j$th
component corresponding to the outcome of measurement $S_{j}$ and

  * •

the output state $\rho_{o}$ is the state of the $n$ qubits of the system after
running the circuit.

The outcome bit-string is generally not deterministic. We denote by
$\mathbb{P}_{{\cal C},\rho}$ the outcome distribution of the circuit when the
input state of the circuit is $\rho$. Given input $\rho$, the circuit ${\cal
C}$ yields the outcome bit-string $o$ with probability $\mathbb{P}_{{\cal
C},\rho}(o)$. The output state $\rho_{o}$ generally depends on the outcome
bit-string $o$. A set of circuit faults represented by a fault operator
$F\in{\overline{\cal P}}_{n(\Delta+1)}$ can affect the outcome bit-string and
the output state of the circuit.

Our goal is to protect the outcome bit-string and the output state of the
circuit from the effect of faults occurring throughout the circuit. Faults are
represented by a fault operator $F\in{\overline{\cal P}}_{n(\Delta+1)}$. We
use the notation $\mathbb{P}_{{\cal C},\rho}^{(F)}$ for the outcome
distribution of the circuit ${\cal C}$ with input state $\rho$ and faults
corresponding to $F$. The corresponding output state is denoted by
$\rho_{o}^{(F)}$.

The impact of a fault $F$ on outcome $o_{j}$ is determined by the cumulant of
$F$ just prior to measurement $S_{j}$. If $\overrightarrow{F}_{\ell_{j}-0.5}$
anti-commutes with $S_{j}$, then the outcome is flipped. Likewise, the impact
on the output state $\rho_{o}$ is determined by the cumulant of $F$ at the end
of the circuit.

######  Proposition 1 (Effect of faults).

If $F\in{\overline{\cal P}}_{n(\Delta+1)}$ then, we have

  * •

$\mathbb{P}_{{\cal C},\rho}^{(F)}(o)=\mathbb{P}_{{\cal C},\rho}(o+f)$ where
$f=(f_{1},\dots,f_{m})\in\mathbb{Z}_{2}^{m}$ such that
$f_{j}=[\overrightarrow{F}_{\ell_{j}-0.5},S_{j}]$,

  * •

$\rho_{o}^{(F)}=E\rho_{o+f}E$ where $E=\overrightarrow{F}_{\Delta+0.5}$.

The pair $(f,E)$ associated with a fault operator $F$ is called the effect of
$F$ and is denoted $\operatorname{eff}(F)$. We say that $F$ flips the $j$-th
outcome of the circuit if $[\overrightarrow{F}_{\ell_{j}-0.5},S_{j}]=1$ and we
refer to the Pauli error $E=\overrightarrow{F}_{\Delta+0.5}$ as the residual
error of $F$.

###### Proof.

By definition of the cumulant $\overrightarrow{F}$, the accumulation of all
the circuit faults occurring before the measurement of $S_{j}$ is equivalent
to the Pauli error $\overrightarrow{F}_{\ell_{j}-0.5}$. As a result, an
outcome bit-string $o$ is mapped onto the vector $o+f$ given in the
proposition. When the vector $o$ is observed, the output state is the state
$E\rho_{o+f}E$ because $o$ was mapped onto $o+f$ and the accumulation of all
the circuit faults acts as an error $E=\overrightarrow{F}_{\Delta+0.5}$ on the
output state of the circuit. ∎

###  2.7 Correction of circuit faults with circuit decoders

For the circuit to be correct in the presence of faults, we must guarantee
that both the outcome bit-string and the output states can be recovered. An
error affecting the outcome bit-string can be just as harmful as an error on
the output state. For example, one can prepare a state $|{+}\rangle$ by
measuring $X$, which produces either $|{+}\rangle$ with outcome 0 or
$|{-}\rangle$ with outcome 1. To obtain the state $|{+}\rangle$, we apply $Z$
to the qubit when the outcome 1 is observed. An incorrect outcome in this
protocol directly translates into a qubit error.

The output of the circuit lives in a stabilizer code (which is a trivial code
for some circuits) and therefore it is sufficient to correct the residual
error up to a stabilizer of this code. Formally, define the output stabilizer
group of the circuit, denoted $\langle{\cal S}_{o}\rangle$, to be the
stabilizer group that keeps invariant all the possible output states
$\rho_{o}$ of the circuit corresponding to the outcome $o$ in the absence of
noise. For a fixed outcome $o$, we refer to an operator of $\langle{\cal
S}_{o}\rangle$ as an output stabilizer and the stabilizer code associated with
the stabilizer group generated by $\langle{\cal S}_{o}\rangle$ as the output
stabilizer code of the circuit. The output stabilizer group of a circuit can
be computed efficiently as in Algorithm 1 as originally proposed in [15, 1].

A circuit decoder for the circuit ${\cal C}$ is defined to be a map

$\displaystyle\mathbb{Z}_{2}^{m}$
$\displaystyle\longrightarrow\mathbb{Z}_{2}^{m}\times{\overline{\cal P}}_{n}$
$\displaystyle o$ $\displaystyle\longmapsto(\hat{f},\hat{E})$

that takes as an input an outcome bit-string $o$ and that returns an
estimation of the outcome flips $\hat{f}$ and an estimation of the residual
error $\hat{E}$.

Assume that the faults corresponding to $F\in{\overline{\cal
P}}_{n(\Delta+1)}$ occur, and let $(f,E)=\operatorname{eff}(F)$ be the effect
of $F$. The decoder is said to be successful if $\hat{f}=f$ and if the error
$\hat{E}E$ is correctable for the output stabilizer code. Here by correctable,
we mean correctable for the output stabilizer code equipped with a decoder and
a noiseless syndrome extraction circuit for the measurement of the stabilizer
generators. This notion of correctability depends on the decoder used for the
output code. Unless otherwise stated, we pick a minimum-weight error decoder
for the output code, that is a decoder returning a minimum weight Pauli error
for a given syndrome.

Denote by $\rho_{M}$ the density matrix of the maximally mixed state
$\rho_{M}=\left(\frac{I}{2}\right)^{\otimes n}$. A most likely fault operator
given an outcome bit-string $o\in\mathbb{Z}_{2}^{m}$ is defined to be a fault
operator $\hat{F}\in{\overline{\cal P}}_{n(\Delta+1)}$ that maximizes the
product

$\displaystyle Q_{\operatorname{MLF}}(\hat{F},o)=\mathbb{P}_{{\cal
C},\rho_{M}}^{(\hat{F})}(o)\mathbb{P}_{\cal F}(\hat{F})\cdot$ (3)

This definition is motivated by Bayes’ theorem, from which the probability of
a fault operator $\hat{F}$ given an outcome $o$ can be written as

$\displaystyle\mathbb{P}(\hat{F}|o)=\frac{\mathbb{P}_{{\cal
C},\rho_{M}}^{(\hat{F})}(o)\mathbb{P}_{\cal
F}(\hat{F})}{\sum_{\hat{F}\in{\overline{\cal
P}}_{n(\Delta+1)}}\mathbb{P}_{\cal F}(\hat{F})\mathbb{P}_{{\cal
C},\rho_{M}}^{(\hat{F})}(o)}$ (4)

where the input state of the circuit is chosen to be the maximally mixed state
$\rho_{M}$ because we do not want to assume a specific input state. For a
fixed circuit and a fixed outcome bit-string, this number is proportional with
$\mathbb{P}_{{\cal C},\rho_{M}}^{(\hat{F})}(o)\mathbb{P}_{\cal F}(\hat{F})$
because the denominator is independent of $\hat{F}$.

A circuit decoder that returns the effect of a most likely fault operator is
said to be a most likely fault decoder or MLF decoder.

##  3 Properties of the cumulant

This section introduces the main technical tools of this paper. In particular
we introduce the back-cumulant $\overleftarrow{F}$ obtained by propagating a
fault operator backward, and we show in Proposition 3 that the accumulator

$\displaystyle{\overline{\cal P}}_{n(\Delta+1)}$ $\displaystyle\longrightarrow
F\in{\overline{\cal P}}_{n(\Delta+1)}$ (5) $\displaystyle F$
$\displaystyle\longmapsto\overrightarrow{F}$ (6)

is the adjoint of the back-accumulator

$\displaystyle{\overline{\cal P}}_{n(\Delta+1)}$ $\displaystyle\longrightarrow
F\in{\overline{\cal P}}_{n(\Delta+1)}$ (7) $\displaystyle F$
$\displaystyle\longmapsto\overleftarrow{F}\cdot$ (8)

This relation allows us to replace the fault propagation by the
backpropagation of the measured operators and leads to the definition of
stabilizer generators of the spacetime code in Section 5.1.

###  3.1 Definition of the back-cumulant

The back-cumulant of a fault operator $F$, denoted $\overleftarrow{F}$, is
defined similarly to the cumulant with the following procedure.

  1. 1.

Initialize $\overleftarrow{F}$ as $\overleftarrow{F}=F$.

  2. 2.

For all levels $\ell=\Delta,\Delta-1,\dots,1$ do:

    1. (a)

Let $E=\overleftarrow{F}_{\ell+0.5}$.

    2. (b)

Conjugate $E$ by the inverse of the product of all unitary operations of
${\cal C}$ with level $\ell$.

    3. (c)

Multiply $\overleftarrow{F}$ by $E$.

Similar to the cumulant, the back-cumulant $\overleftarrow{F}$ is defined in
such a way that the operator $F_{\ell-0.5}$ is equivalent to the accumulation
(backward in time) of all the faults occurring during the levels
$\ell^{\prime}\geq\ell$ of the circuit.

###  3.2 Explicit cumulant and back-cumulant

The following proposition provides an explicit description of the cumulant and
back-cumulant of a fault operator.

######  Proposition 2 (Explicit cumulant and back-cumulant).

Let ${\cal C}$ be a Clifford circuit. Let $U_{\ell}$ be the product of all the
unitary operations of the circuit with level $\ell$ and let
$U_{i,j}=U_{j}U_{j-1}\dots U_{i+1}$ for $j\geq i$. If $F$ is a fault operator
then for all $\ell\in\\{0,1,\dots,\Delta\\}$, we have

$\displaystyle\overrightarrow{F}_{\ell+0.5}=\prod_{i=0}^{\ell}U_{i,\ell}F_{i+0.5}U_{i,\ell}^{-1}$
(9)

and

$\displaystyle\overleftarrow{F}_{\ell+0.5}=\prod_{j=\ell}^{\Delta}U_{\ell,j}^{-1}F_{j+0.5}U_{\ell,j}\cdot$
(10)

Here, we use the convention $U_{i,j}=I$ if $j\leq i$. When $j>i$, the
operation $U_{i,j}$ is defined in such a way that it maps the faults occurring
right after level $i$ onto equivalent faults occurring right after level $j$.

###### Proof.

The component $\overrightarrow{F}_{\ell+0.5}$ of $\overrightarrow{F}$ is
obtained by conjugating all the components $F_{i+0.5}$ of $F$ with $i\leq\ell$
through the level $i+1,i+2,\dots\ell$ of the circuit. This corresponds to the
conjugation by $U_{i,\ell}$, justifying the propagation formula.

To back-propagate $F_{j+0.5}$ from level $j+0.5$ to level $\ell+0.5$ with
$j\geq\ell$, we conjugate this operator by the inverse of the unitary
operations of the circuit at levels $\ell,\ell-1,\dots,j+1$ in that order.
This is equivalent to the conjugation by

$U_{j+1}^{-1}\dots U_{\ell-1}^{-1}U_{\ell}^{-1}$

which is equal to $U_{\ell,j}^{-1}$. ∎

The operators $U_{i,j}$ obey the relations

$\displaystyle U_{a,c}=U_{b,c}U_{a,b},$ (11) $\displaystyle
U_{b,c}^{-1}U_{a,c}=U_{a,b}$ (12)

and

$\displaystyle U_{a,b}U_{a,c}^{-1}=U_{b,c}^{-1}$ (13)

where $a,b,c$ are three integers such that $0\leq a\leq b\leq c\leq\Delta$.

######  Corollary 1.

The accumulator and the back-accumulator are automorphisms of the group
${\overline{\cal P}}_{n(\Delta+1)}$.

Thanks to this corollary, one can write

$\displaystyle\overrightarrow{FG}=\overrightarrow{F}\overrightarrow{G}$ (14)

and

$\displaystyle\overleftarrow{FG}=\overleftarrow{F}\overleftarrow{G}$ (15)

for all fault operators $F,G$.

###### Proof.

Based on Eq. (9), we see that

$\displaystyle\overrightarrow{FG}_{\ell+0.5}$
$\displaystyle=\prod_{i=0}^{\ell}U_{i,\ell}F_{i+0.5}G_{i+0.5}U_{i,\ell}^{-1}$
$\displaystyle=\prod_{i=0}^{\ell}U_{i,\ell}F_{i+0.5}U_{i,\ell}^{-1}U_{i,\ell}G_{i+0.5}G_{i+0.5}U_{i,\ell}^{-1}$
$\displaystyle=\prod_{i=0}^{\ell}U_{i,\ell}F_{i+0.5}U_{i,\ell}^{-1}\prod_{j=0}^{\ell}U_{j,\ell}G_{j+0.5}U_{j,\ell}^{-1}$
$\displaystyle=\overrightarrow{F}_{\ell+0.5}\overrightarrow{G}_{\ell+0.5}$

Therein, we can reorder the Pauli operators
$U_{i,\ell}F_{i+0.5}U_{i,\ell}^{-1}$ and $U_{j,\ell}G_{j+0.5}U_{j,\ell}^{-1}$
because we consider Pauli operators up to a phase. This proves that the
accumulator is a group morphism.

Therefore, the accumulator is a $\mathbb{Z}_{2}$-linear map over
${\overline{\cal P}}_{n(\Delta+1)}\simeq\mathbb{Z}_{2}^{2n(\Delta+1)}$. To
show that it is bijective, it suffices to see that its matrix is lower
triangular with the identity on the diagonal in the basis obtained by
concatenating Pauli operators acting on level $0,1,\dots,\Delta$.

One can show that the back-accumulator is a group automorphism with the same
technique. ∎

###  3.3 Basic properties of Pauli commutators

For two Pauli operators $P$ and $Q$, denote by $[P,Q]\in\mathbb{Z}_{2}$ the
commutator of $P$ and $Q$ which takes the value $0$ if $P$ and $Q$ commute and
takes the value 1 otherwise. We will use the following basic properties of the
commutator. Let $n,m$ be integers. For all Pauli operators
$P,Q\in{\overline{\cal P}}_{n}$, we have

$\displaystyle[P,Q]=[Q,P].$ (16)

For all Pauli operators $P,Q,R\in{\overline{\cal P}}_{n}$, we have

$\displaystyle[P,QR]=[P,Q]+[P,R]\pmod{2}.$ (17)

For all Pauli operators $P,Q\in{\overline{\cal P}}_{n}$ and
$P^{\prime},Q^{\prime}\in{\overline{\cal P}}_{m}$, we have

$\displaystyle[P\otimes P^{\prime},Q\otimes
Q^{\prime}]=[P,Q]+[P^{\prime},Q^{\prime}]\pmod{2}.$ (18)

For all Pauli operators $P,Q\in{\overline{\cal P}}_{n}$ and for all Clifford
unitary operations $U$, we have

$\displaystyle[P,Q]=[UPU^{-1},UQU^{-1}].$ (19)

###  3.4 Interplay between accumulation and commutation

Based on Proposition 1, to clarify the effect of faults on the outcomes of a
circuit, it is important to understand the interplay between fault propagation
and commutation; see definition of $f_{j}$. The following proposition is a key
technical result and is used many times in the rest of the paper. It proves
that the back-accumulator is the adjoint of the accumulator.

######  Proposition 3 (Adjoint of the accumulator).

For all fault operators $F,G$ of a circuit ${\cal C}$, we have

$[\overrightarrow{F},G]=[F,\overleftarrow{G}]\cdot$

###### Proof.

Because
$\overrightarrow{F}=\otimes_{\ell=0}^{\Delta}\overrightarrow{F}_{\ell+0.5}$
and $G=\otimes_{\ell=0}^{\Delta}G_{\ell+0.5}$, we can write

$\displaystyle[\overrightarrow{F},G]$
$\displaystyle=\sum_{\ell=0}^{\Delta}\left[\overrightarrow{F}_{\ell+0.5},G_{\ell+0.5}\right]$
Using Eq. (18)
$\displaystyle=\sum_{\ell=0}^{\Delta}\left[\prod_{i=0}^{\ell}\left(U_{i,\ell}F_{i+0.5}U_{i,\ell}^{-1}\right),G_{\ell+0.5}\right]$
Using Eq. (9)
$\displaystyle=\sum_{\ell=0}^{\Delta}\sum_{i=0}^{\ell}\left[U_{i,\ell}F_{i+0.5}U_{i,\ell}^{-1},G_{\ell+0.5}\right]$
Using Eq. (17)
$\displaystyle=\sum_{\ell=0}^{\Delta}\sum_{i=0}^{\ell}\left[F_{i+0.5},U_{i,\ell}^{-1}G_{\ell+0.5}U_{i,\ell}\right]$
Using Eq. (19)
$\displaystyle=\sum_{i=0}^{\Delta}\sum_{\ell=i}^{\Delta}\left[F_{i+0.5},U_{i,\ell}^{-1}G_{\ell+0.5}U_{i,\ell}\right]$
Interchanging the summation order
$\displaystyle=\sum_{i=0}^{\Delta}\left[F_{i+0.5},\prod_{\ell=i}^{\Delta}\left(U_{i,\ell}^{-1}G_{\ell+0.5}U_{i,\ell}\right)\right]$
Using Eq. (17)
$\displaystyle=\sum_{i=0}^{\Delta}\left[F_{i+0.5},\overleftarrow{G}_{i+0.5}\right]$
Using Eq. (10) $\displaystyle=[F,\overleftarrow{G}]$ $\displaystyle\text{Using
Eq.\leavevmode\nobreak\ \eqref{eq:commutator_tensor_product}}\cdot$

In the last equality we use the factorizations
$F=\otimes_{i=0}^{\Delta}F_{i+0.5}$ and
$\overleftarrow{G}=\otimes_{i=0}^{\Delta}\overleftarrow{G}_{i+0.5}$. ∎

##  4 The outcome code of a Clifford circuit

In this section, we show that the set of possible outcome bit-strings of a
Clifford circuit is almost linear code222By almost, we mean that it is not a
linear subspace but an affine subspace of $\mathbb{Z}_{2}^{m}$ for some
integer $m$. However, by changing the description of the circuit, one can make
it a proper linear code. and we propose an algorithm to efficiently compute a
set of checks for this code. Our algorithm is derived from the standard
stabilizer simulation algorithm of [15, 1]. In fact, removing steps 7 to 13 in
Algorithm 1, we recover a standard algorithm that computes the output
stabilizer group of a Clifford circuit. The outcome code can be used to detect
and correct faults in a Clifford circuit.

We consider a depth-$\Delta$ Clifford circuit ${\cal C}$ acting on $n$ qubits
containing $m$ measurements. We denote by $S_{j}$ the measured operators for
$j=1,\dots,m$ and by $\ell_{j}$ the level of the measurement of the operator
$S_{j}$.

In many cases, the outcomes observed through a circuit are not independent.
For instance, if a measurement is repeated twice in a row, we expect to obtain
the same outcome twice. The following theorem proves that the set of outcomes
of a Clifford circuit is an affine subspace. It is defined by a set of affine
checks of the form $\sum_{k\in K}o_{k}=0$ or 1.

######  Theorem 1 (Outcome code of a Clifford circuit).

The set of all possible outcome bit-strings for a Clifford circuit ${\cal C}$
with $m$ Pauli measurements is an affine subspace ${\cal O}({\cal C})$ of
$\mathbb{Z}_{2}^{m}$. Moreover a set of affine equations defining ${\cal
O}({\cal C})$ is computed by Algorithm 1.

input : A Clifford circuit ${\cal C}=(C_{1},\dots,C_{s})$ acting on $n$
qubits.

output : A set $R$ of checks for the circuit ${\cal C}$.

1

2Set $R=\\{\\}$ and ${\cal S}=\\{\\}$.

3 for  _all $i=1,\dots,s$_ do

4 if  _$C_{i}$ is a unitary gate_ then

5 for  _all $T$ in ${\cal S}$_ do

6 Replace $T$ by $C_{i}TC_{i}^{-1}$.

7

8

9 if  _$C_{i}$ is a measurement of a Pauli operator $S_{j}\in{\cal P}_{n}$._
then

10 if  _$\pm S_{j}\in\langle{\cal S}\rangle$_ then

11 Decompose $\pm S_{j}$ as a product of operators in ${\cal S}$.

12 Write this decomposition in the form $\pm S_{j}=\prod_{k\in K_{j}}S_{k}$.

13 if  _$+S_{j}\in\langle{\cal S}\rangle$_ then

14 Add the affine check $o_{j}+\sum_{k\in K_{j}}o_{k}=0$ to $R$.

15

16 if  _$-S_{j}\in\langle{\cal S}\rangle$_ then

17 Add the affine check $o_{j}+\sum_{k\in K_{j}}o_{k}=1$ to $R$.

18

19

20 else

21 if  _If there exists $T\in{\cal S}$ that anti-commutes with $S_{j}$_ then

22 for  _$T^{\prime}\in{\cal S}$ such that $T^{\prime}\neq T$_ do

23 if  _$T^{\prime}$ anti-commute with $S_{j}$_ then

24 Replace $T^{\prime}$ by $TT^{\prime}$ in ${\cal S}$.

25

26

27 Remove $T$ from ${\cal S}$.

28

29 Add $S_{j}$ to ${\cal S}$.

30

31

32

return $R$.

Algorithm 1 Outcome code of a Clifford circuit.

Except for steps $8-13$, Algorithm 1 matches the standard algorithm for
stabilizer simulation [15, 1]. The only difference is the action taken when a
measured Pauli operator $S_{j}$ is already an element of the stabilizer group
$\langle{\cal S}\rangle$. In that case, the usual action is to simply output
the measurement result $\pm 1$. Instead, we determine the decomposition of
$S_{j}$ as a product of existing elements of ${\cal S}$. The formula $\pm
S_{j}=\prod_{k\in K_{j}}S_{k}$ asserts that the outcome of measument $C_{j}$
_must_ match sum of outcomes from prior measurements $C_{k}$ the circuit. All
together, they form a check of the outcome code.

The decomposition (step 9) can be computed by a variation of Gauss-Jordan
elimination in which the elements of ${\cal S}$ are augmented to indicate the
indexes of their corresponding measurements. For a circuit with $n$ qubits and
$m$ measurements, the worst-case computational complexity of this step is
$O(n^{2}(n+m))$. Note also that this step can be combined with checking $\pm
S_{j}\in\langle{\cal S}\rangle$ (step 7), which also requires Gaussian
elimination.

The proof of Theorem 1 is derived from the following lemma which is similar to
Gottesman’s update rules [15].

######  Lemma 1 (Stabilizer update rules).

Let $|{\psi}\rangle$ be a state of a stabilizer code $C({\cal S})$ with length
$n$ and assume that the Pauli operator $M\in{\cal P}_{n}$ is measured with
outcome $o\in\\{-1,+1\\}$. Then, the following holds.

  1. 1.

If $\pm M\in\langle{\cal S}\rangle$, the outcome of the measurement of $M$ is
$\pm 1$ and the state of the system is unchanged after measurement.

  2. 2.

If $\pm M\notin\langle{\cal S}\rangle$ and $M$ commutes with all the elements
of ${\cal S}$. Denote ${\cal S}^{\prime}={\cal S}\cup\\{M\\}$.

     * •

For all outcomes $o\in\\{+1,-1\\}$ there exists a state of $C({\cal S})$ such
that the measurement of $M$ has outcome $o$ with non-zero probability.

     * •

For all states $|{\psi^{\prime}}\rangle$ in $C({\cal S}^{\prime})$ there
exists a state $|{\psi}\rangle\in C({\cal S})$ such that the measurement of
$M$ projects $|{\psi}\rangle$ onto $|{\psi^{\prime}}\rangle$ with non-zero
probability.

  3. 3.

If $\pm M\notin\langle{\cal S}\rangle$ and $M$ anti-commutes with an element
$S_{1}$ of $\langle{\cal S}\rangle$. Let $S_{1},S_{2},\dots,S_{r}$ be a
generating set for $\langle{\cal S}\rangle$ such that $S_{2},\dots,S_{r}$
commute with $M$. Denote ${\cal S}^{\prime}=\\{M,S_{2},\dots,S_{r}\\}$.

     * •

For all outcomes $o\in\\{+1,-1\\}$ there exists a state of $C({\cal S})$ such
that the measurement of $M$ has outcome $o$ with non-zero probability.

     * •

For all states $|{\psi^{\prime}}\rangle$ in $C({\cal S}^{\prime})$ there
exists a state $|{\psi}\rangle\in C({\cal S})$ such that the measurement of
$M$ projects $|{\psi}\rangle$ onto $|{\psi^{\prime}}\rangle$ with non-zero
probability.

###### Proof.

The first item is an immediate consequence of the postulates of quantum
mechanics.

Consider the second item. For the state
$|{\psi_{o}}\rangle=\frac{I+(-1)^{o}M}{2}|{\psi}\rangle$ where
$|{\psi}\rangle$ is a state of $C({\cal S})$, the outcome of the measurement
$M$ is $o$ with probability 1 proving the first part. Moreover, the
measurement of $M$ maps any state $|{\psi^{\prime}}\rangle$ of $C({\cal
S}^{\prime})$ onto itself with probability 1.

It remains to prove the third item. Consider a set of logical operators
$\bar{X}_{1},\bar{Z}_{1},\dots,\bar{X}_{k},\bar{Z}_{k}$ of the stabilizer code
$C({\cal S})$. Without loss of generality, we can assume that all these
logical operators commute with $M$. Otherwise, if a logical operator $L$ anti-
commutes with $M$, replace $L$ by $LS_{1}$ which is another representative of
the same logical operator. Therefore, the operators
$\bar{X}_{1},\bar{Z}_{1},\dots,\bar{X}_{k},\bar{Z}_{k}$ also form a basis of
logical operators for the code $C({\cal S}^{\prime})$.

Consider the logical state $|{\bar{x}}\rangle$ in the stabilizer code $C({\cal
S})$ where $x\in\mathbb{Z}_{2}^{k}$. It is the state of $C({\cal S})$ fixed by
the operators $(-1)^{x_{i}}\bar{Z}_{i}$. This state is mapped onto the logical
state $|{\bar{x}}\rangle$ of $C({\cal S}^{\prime})$ with probability $1/2$. To
see this, denote ${\cal S}_{x}={\cal
S}\cup\\{(-1)^{x_{1}}\bar{Z}_{1},\dots,(-1)^{x_{k}}\bar{Z}_{k}\\}$. Then,
$|{\bar{x}}\rangle\langle{\bar{x}}|=2^{-n}\sum_{S\in{\cal S}_{x}}S$ and the
measurement of $M$ produces the outcome $o$ with probability

$\displaystyle\operatorname{tr}\left(\frac{I+(-1)^{o}M}{2}|{\bar{x}}\rangle\langle{\bar{x}}|\right)=2^{-(n+1)}\left(\operatorname{tr}\sum_{S\in\langle{\cal
S}_{x}\rangle}S+(-1)^{o}\operatorname{tr}\sum_{S\in\langle{\cal
S}_{x}\rangle}MS\right)=1/2\cdot$

Indeed, the first sum is $\sum_{S\in\langle{\cal S}_{x}\rangle}S=2^{n}$
because all the Pauli operators are traceless except the identity which has
trace $2^{n}$. The second sum is trivial because $MS=\pm I$ would imply $\pm
M\notin{\cal S}_{x}$ which is impossible because $M$ anti-commute with ${\cal
S}_{x}$.

Therefore, we demonstrated the existence of a state $|{\bar{x}}\rangle$ of
$C({\cal S})$ which leads both measurement outcomes $o=0$ or $1$ with
probability $1/2$. Moreover, its image when the outcome is trivial is the
state $|{\bar{x}}\rangle$ of the code $C({\cal S}^{\prime})$. Therefore, we
can reach any of the basis state $|{\bar{x}}\rangle$ of $C({\cal S}^{\prime})$
from some state of $C({\cal S})$ by measuring $M$. By linearity of the
projection, this proves that one can reach any state of the code $C({\cal
S}^{\prime})$. ∎

###### Proof of Theorem 1.

Based on Lemma 1, the set of states that belong to the output of the
subcircuit $(C_{1},\dots,C_{i-1})$ is a stabilizer code. Moreover, a set of
stabilizer generators ${\cal S}_{i-1}$ for this code is computed by updating
the stabilizer generators of the circuit after each operation as in Algorithm
1.

If the operator $C_{i}$ is the measurement of an operator $S_{j}$ such that
neither $S_{j}$ nor $-S_{j}$ belong to the stabilizer group of the outcome of
the circuit $(C_{1},\dots,C_{i-1})$, then the outcome $o_{j}$ can be either 0
or 1. However, if $\pm S_{j}$ belongs to the stabilizer group, its outcome is
constrained and this defined a check of the affine code. This check is
computed in Algorithm 1. ∎

Without loss of generality, we can assume that the outcome code ${\cal
O}({\cal C})$ of a Clifford circuit not only an affine subspace but also a
proper $\mathbb{Z}_{2}$-linear code. Indeed, replacing the measured operator
$S_{j}$ by $-S_{j}$ for all the measurements such that $-S_{j}\in\langle{\cal
S}\rangle$ in Algorithm 1 makes all the checks linear without modifying the
output of the circuit. This leads to the following corollary.

######  Corollary 2 (Linearization of the outcome code).

Let ${\cal C}$ be a Clifford circuit and ${\cal C}^{\prime}$ the circuit
obtained by running Algorithm 1, replacing $S_{j}$ by $-S_{j}$ upon
encountering condition $-S_{j}\in\langle{\cal S}\rangle$. Then the outcome
code of ${\cal C}^{\prime}$ is a linear code.

For all remaining sections, we assume that the outcome code ${\cal O}({\cal
C})$ is linear. For obvious reasons, we may refer to a vector of ${\cal
O}({\cal C})^{\perp}$ as a check of the outcome code ${\cal O}({\cal C})$. The
outcome code can be immediately used to correct faults in a quantum circuit.
Indeed, if a fault configuration induces a flip of some of the circuit
outcomes, then it can be detected using the values of the checks of the
outcome code.

##  5 The spacetime code of a Clifford circuit

As a linear code, the outcome code provides natural means of detecting and
correcting errors in the classical bit-string of measurement outcomes of a
circuit. However, we also need to correct the output qubits of the circuit. In
order to correct qubit errors, we need a way of mapping syndromes of the
outcome code back on to corresponding qubit errors, i.e., a circuit decoder.
One way to build this map is to construct a lookup table by enumerating
combinations of faults recording their syndrome. But this approach scales
exponentially with circuit size, and so is feasible only for small circuits.

Instead, we might hope to leverage existing techniques for constructing
decoders for stabilizer codes. In this setting, we imagine that Pauli errors
can occur on qubits, but syndrome information is obtained perfectly. Contrast
this with the circuit setting in which errors can occur on any component,
including measurement outcomes.

In this section, we introduce a stabilizer code, the spacetime code,
associated with a Clifford circuit. We then show that the problem of
correcting faults in the circuit reduces to the problem of correcting Pauli
errors in this stabilizer code.

###  5.1 Definition of check operators

Here, we define the check operators that are the stabilizers of the spacetime
code.

It is convenient to introduce another notation from [2]. The fault operator
$F\in{\overline{\cal P}}_{n(\Delta+1)}$ obtained by placing a $n$-qubit Pauli
operator $P$ at level $\ell+0.5$ is denoted $\eta_{\ell+0.5}(P)$. By
definition, we have $F_{\ell+0.5}=P$ and $F_{\ell^{\prime}+0.5}=I$ for all
$\ell^{\prime}\neq\ell$.

For any vector $u\in{\cal O}({\cal C})^{\perp}$, define the check operator to
be the back-cumulant $\overleftarrow{F(u)}$ of the fault operator

$\displaystyle F(u)=\prod_{j=1}^{m}\eta_{\ell_{j}-0.5}(S_{j}^{u_{j}})$ (20)

Recall that $S_{1},\dots,S_{m}$ are the $m$ measured operators of the circuit
and $S_{j}$ is measured at level $\ell_{j}$. In other words, $F(u)$ is the
fault operator obtained by placing each measured operator $S_{j}$ with
$u_{j}=1$ at the level right before it is measured.

One may prefer to use a cumulant instead of a back-cumulant. Then, we can
define the check operators as $\overrightarrow{F^{\prime}(u)}$ where

$\displaystyle
F^{\prime}(u)=\prod_{j=1}^{m}\eta_{\ell_{j}+0.5}(S_{j}^{u_{j}})\cdot$ (21)

The definition is discussed in Appendix E where we prove that
$\overleftarrow{F(u)}=\overrightarrow{F^{\prime}(u)}$ for vectors $u$ of
${\cal O}({\cal C})^{\perp}$. We prefer using $\overleftarrow{F(u)}$ because
it makes some proofs more straightforward. What makes the back-accumulator
natural is the fact that it is the adjoint of the accumulator (Proposition 3).
Informally, this means that we can replace the propagation of faults by the
backpropagation of measurements. We will make this claim rigorous throughout
this section.

######  Proposition 4.

The map $u\mapsto\overleftarrow{F(u)}$ is an injective group morphism from
$\mathbb{Z}_{2}^{m}$ to ${\overline{\cal P}}_{n(\Delta+1)}$.

###### Proof.

For all $u,v\in\mathbb{Z}_{2}^{m}$, the operators $F(u)$ and $F(v)$ satisfy
$F(u)F(v)=F(u+v)$. Combined with Eq. (15), this leads to
$\overleftarrow{F(u)}\overleftarrow{F(v)}=\overleftarrow{F(u+v)}$ which proves
that $u\mapsto\overleftarrow{F(u)}$ is a group morphism. It is injective as
the composition of an injective map $u\mapsto{F(u)}$ and a bijection
$F\mapsto\overleftarrow{F}$ (Corollary 1). ∎

We will use extensively the relation
$\overleftarrow{F(u+v)}=\overleftarrow{F(u)}\overleftarrow{F(v)}$ which is a
consequence of Proposition 4.

###  5.2 The spacetime code

The following theorem proves that the check operators $\overleftarrow{F(u)}$
form a stabilizer group. We refer to the corresponding stabilizer code as the
spacetime code of the circuit, denoted ${\cal Q}({\cal C})$.

######  Theorem 2 (The spacetime code).

Let ${\cal C}$ be a Clifford circuit with depth $\Delta$. Then, the set of all
the check operators $\overleftarrow{F(u)}$ for $u\in{\cal O}({\cal
C})^{\perp}$ is a stabilizer group. Moreover, if the outcome code ${\cal
O}({\cal C})$ of the circuit has parameters $[m,k]$, the spacetime code of the
circuit ${\cal Q}({\cal C})$ has parameters $[[N,K]]$ with $N=n(\Delta+1)$ and
$K=N-(m-k)$.

###### Proof.

Based on Proposition 4, the set of operators of the form
$\overleftarrow{F(u)}$ with $u\in{\cal O}({\cal C})^{\perp}$ is a subgroup of
${\cal P}_{n(\Delta+1)}$. Proposition 9 proves that this subgroup is
commutative. Moreover, it cannot contain $-I$ because the map
$u\mapsto\overleftarrow{F(u)}$ with value in ${\overline{\cal
P}}_{n(\Delta+1)}$ is injective. Indeed, if there exists $u\neq 0$ such that
$\overleftarrow{F(u)}=-I$, then modulo a phase we have
$\overleftarrow{F(u)}=\overleftarrow{F(0)}$ which contradicts the injectivity.
Another consequence of the injectivity is that the rank of the image
stabilizer group is equal to the dimension of ${\cal O}({\cal C})^{\perp}$
which is $m-k$. This provides the stabilizer code parameters. ∎

###  5.3 Application to the correction of circuit faults

Here, we use the spacetime code to show that one can reduce the problem of
correcting circuit faults to the correction of Pauli errors in a stabilizer
code.

We consider a set of checks $u_{1},\dots,u_{r}$ for the outcome code ${\cal
O}({\cal C})$ of a Clifford circuit. The syndrome map associated with these
checks is denoted

$\sigma_{{\cal O}}:\mathbb{Z}_{2}^{m}\rightarrow\mathbb{Z}_{2}^{r}.$

Recall that the $i$th syndrome bit of a vector $v\in\mathbb{Z}_{2}^{m}$ is
$(u_{i}|v)$. We consider the spacetime code ${\cal Q}({\cal C})$ with
stabilizer generators
$\overleftarrow{F(u_{1})},\dots,\overleftarrow{F(u_{r})}$. The corresponding
syndrome map is denoted

$\sigma_{{\cal Q}}:{\overline{\cal
P}}_{n(\Delta+1)}\longrightarrow\mathbb{Z}_{2}^{r}$

and the $i$th syndrome bit of a Pauli error $F\in{\overline{\cal
P}}_{n(\Delta+1)}$ is $[\overleftarrow{F(u_{i})},F]$.

An MLE decoder for the stabilizer code ${\cal Q}({\cal C})$ is a map

$D_{\cal Q}:\mathbb{Z}_{2}^{r}\longrightarrow{\overline{\cal
P}}_{n(\Delta+1)}$

that returns a most likely Pauli error given a syndrome $\sigma_{{\cal
Q}}(F)$. Here, we consider Pauli errors according to the distribution
$\mathbb{P}_{\cal F}$ of circuit faults.

Finally, recall that the effect of a fault operator $F$ in a circuit is
obtained from a map

$\operatorname{eff}:{\overline{\cal
P}}_{n(\Delta+1)}\longrightarrow\mathbb{Z}_{2}^{m}\times{\overline{\cal
P}}_{n}$

that maps a fault operator onto its corresponding outcome bit-string and the
output state.

######  Theorem 3 (Circuit decoder from stabilizer code decoder).

Let ${\cal C}$ be a Clifford circuit. If $D_{\cal Q}$ is a MLE decoder for
stabilizer code ${\cal Q}({\cal C})$, then $\operatorname{eff}\circ D_{\cal
Q}\circ\sigma_{{\cal O}}$ is a MLF circuit decoder for the circuit ${\cal C}$.

We first prove a lemma. Recall that $\rho_{M}$ denotes the $n$-qubit maximally
mixed state. The indicator function of a set $A$ is denoted $\delta_{A}$. It
takes the value $\delta_{A}(x)=1$ if $x\in A$ and 0 otherwise.

######  Lemma 2.

Let ${\cal C}$ be a Clifford circuit and let $F$ be a fault operator with
effect $\operatorname{eff}(F)=(f,E)$. If ${\cal O}({\cal C})$ is the outcome
code of ${\cal C}$, then we have

$\displaystyle\mathbb{P}_{{\cal
C},\rho_{M}}^{(F)}(o)=\frac{1}{2^{k}}\delta_{f+{\cal O}({\cal C})}(o)$ (22)

where $k=\dim{\cal O}({\cal C})$.

###### Proof.

Consider first the case of a trivial fault operators $F=I$. Then, we know from
Theorem 1 that the set of outcomes $o$ with non-zero probability is a subset
of the outcome code ${\cal O}({\cal C})$. The main difference with Theorem 1
is that we restrict the input state to be the maximally mixed state. The
unitary operations of the circuit preserve the maximally mixed states and
applying a Pauli measurement to the maximally mixed state returns a uniform
outcome and the post-measurement state is the maximally mixed state. This
proves that all outcome bit-strings of ${\cal O}({\cal C})$ can occur when the
input state of the circuit is fixed to be the maximally mixed state
$\rho_{M}$. Moreover, they occur with the same probability. This proves that

$\mathbb{P}_{{\cal C},\rho_{M}}^{(I)}(o)=\frac{1}{2^{k}}\delta_{{\cal O}({\cal
C})}(o)\cdot$

Injecting $F$ in the circuit shifts the outcome bit-string $o$ by $f$, which
leads to the shifted indicator function in the lemma. ∎

###### Proof of Theorem 3.

We need to prove that for all $o\in\mathbb{Z}_{2}^{m}$, the fault operator
$F=D_{\cal Q}\circ\sigma_{{\cal O}}(o)$ maximizes the function
$Q_{\operatorname{MLF}}(F,o)$ introduced in Eq. (3). First, denote
$(f,E)=\operatorname{eff}(F)$. Based on Lemma 2, we have

$\displaystyle Q_{\operatorname{MLF}}(F,o)=\frac{1}{2^{k}}\delta_{f+{\cal
O}({\cal C})}(o)\mathbb{P}_{\cal F}(F)$ (23)

which means that one can maximize $Q_{\operatorname{MLF}}(F,o)$ by selecting a
fault operator $F$ such that $o\in f+{\cal O}({\cal C})$ that has maximum
probability $\mathbb{P}_{\cal F}(F)$. The condition $o\in f+{\cal O}({\cal
C})$ is equivalent to $\sigma_{{\cal O}}(f)=\sigma_{{\cal O}}(o)$. Finally,
Lemma 4, we know that $\sigma_{{\cal O}}(f)=\sigma_{{\cal Q}}(F)$. Overall, we
showed that a MLF decoder for the circuit ${\cal C}$ is a circuit decoder that
returns the effect of a fault operator $F$ such that $\sigma_{{\cal
Q}}(F)=\sigma_{{\cal O}}(o)$ with maximum probability. Therefore the map
$\operatorname{eff}\circ D_{\cal Q}\circ\sigma_{{\cal O}}$ is a MLF decoder. ∎

###  5.4 Beyond MLF circuit decoders

A MLF decoder is sometimes good enough but it ignores the fact that two fault
operators may have the same effect and two residual errors that differ in an
output stabilizer can be considered equivalent.

In some cases one may prefer a most likely coset decoder (MLC decoder), which
is defined to be a circuit decoder that takes as an input an outcome bit-
string $o$ and returns a pair $(\hat{f},\hat{E})$ that maximizes the sum

$\displaystyle
Q_{\operatorname{MLC}}(\hat{f},\hat{E},o)=\sum_{E^{\prime}\in\hat{E}\langle{\cal
S}_{o}\rangle}\sum_{\begin{subarray}{c}\hat{F}\in{\overline{\cal
P}}_{n(\Delta+1)}\\\
\operatorname{eff}(\hat{F})=(\hat{f},E^{\prime})\end{subarray}}\mathbb{P}_{{\cal
C},\rho_{M}}^{(\hat{F})}(o)\mathbb{P}_{\cal F}(\hat{F})\cdot$ (24)

Wherein, $\hat{E}\langle{\cal S}_{o}\rangle$ denotes the coset of $\hat{E}$ in
the output stabilizer group. Based on Eq. (4), this sum is proportional with
the sum of the probabilities of all the fault operators that leads to an
effect $(\hat{f},E^{\prime})$ where the Pauli error $E^{\prime}$ is equivalent
to $\hat{E}$ up to a stabilizer of the output code.

One can design a MLC decoder using a subsystem version of the spacetime code
obtained by gauging logical operators which correspond to faults with trivial
effect. Namely, one can define a subsystem code from the union of two sets of
gauge operators: (i) the operators $G(P,\ell)$, defined by Eq. (25), for each
$\ell$ and for each $P$ that commutes with all the measurements at level
$\ell$ and (ii) the operators $\eta_{\ell_{j}-0.5}(S_{j})$ where $S_{j}$ is an
operator measured at level $\ell_{j}$. Then, the center of the gauge group is
the stabilizer group of the spacetime code. Equivalently, the subsystem
spacetime code can be seen as a variant of the stabilizer spacetime code
obtained by gauging the logical qubits corresponding to the operators
$G(P,\ell)$ such that $P$ commutes with all the measured operators at level
$\ell$. This subsystem code can be seen as a generalization of the circuit-to-
code construction proposed in [2]. Here we consider circuits including
intermediate measurements and multi-qubit measurement whereas [2] focuses on
post-selection circuits.

Then, one could design a a MLC decoder from a decoder for the subsystem
spacetime code that returns a most likely coset of the gauge group. We do not
expand on this strategy because designing a most likely coset for a subsystem
code is generally challenging. In what follows, we focus on the strategy
suggested by Theorem 3 and we use decoders for the stabilizer spacetime code.

##  6 LDPC spacetime code

To obtain a complete scheme for the correction of faults in a Clifford
circuit, we need to provide a decoder. However, decoding a general code is
quite difficult. Indeed, the maximum likelihood decoding problem is NP-hard
for linear codes [3] and $\\#$P-hard for stabilizer codes [18]. However, some
classes of codes such as LDPC codes, which are defined by low-weight checks,
admit an efficient decoder with good performance [12].

Here, we consider restrictions induced by a limited connectivity in the
quantum hardware implementing the circuit. This imposes constraints on the
spacetime code which, in some cases, make it easier to decode. Our basic idea
is to produce a set of low-weight stabilizer generators for the spacetime code
and to use an LDPC code decoder.

###  6.1 Qubit connectivity and LDPC spacetime codes

Because the back-cumulant can spread errors through the entire circuit, the
check operators $\overleftarrow{F(u)}$ are not expected to have low weight.
However, if the circuit connectivity is limited, then then back-cumulant does
not spread $F(u)$ as quickly. Below we identify sufficient conditions that
ensure that the spacetime code admit low-weight generators.

A family of stabilizer codes is said to be LDPC if each stabilizer group admit
generators acting on $O(1)$ qubits. A family of stabilizer codes is said to be
$D$-dimensional local if the $n$ qubits of the codes can be mapped onto the
vertices of a $D$-dimensional grid $\mathbb{Z}^{D}$ in such a way that the
stabilizer generators are all supported on a ball with radius $O(1)$ in the
grid. $D$-dimensional local codes are a subset of quantum LDPC codes.

The depth of an outcome bit-string $u\in\mathbb{Z}_{2}^{m}$, denoted
$\operatorname{depth}(u)$ is defined as

$\operatorname{depth}(u)=\max\\{\ell_{j}\ |\ u_{j}=1\\}-\min\\{\ell_{j}\ |\
u_{j}=1\\}+1\cdot$

Recall that $\ell_{j}$ is the level of the $j$ th measurement of the circuit.
The measurements indexed by $j$ satisfying $u_{j}=1$ are supported in a subset
of $\operatorname{depth}(u)$ consecutive levels of the circuit ${\cal C}$.

A family of circuits is said to be bounded if the outcomes codes of the
circuits admit a set of checks with weight $O(1)$ and depth $O(1)$.

######  Proposition 5 (LDPC spacetime codes).

Let $({\cal C}_{t})_{t\in\mathbb{N}}$ be a family of Clifford circuits. If the
family of circuits is bounded and if all circuit operations act on $O(1)$
qubits, then the spacetime codes of the circuits are LDPC.

###### Proof.

The stabilizer group of the spacetime code is generated by the check operators
$\overleftarrow{F(u_{i})}$ corresponding to the generators $u_{1},\dots,u_{r}$
of ${\cal O}({\cal C}_{t})^{\perp}$ with bounded depth. By Lemma 8, the
stabilizer generators $\overleftarrow{F(u_{i})}$ have support on $O(1)$
levels. Moreover, because the circuits are bounded, the weight of $F(u)$ is
bounded. Back-accumulating $F(u)$ through a circuit made with operations
acting on $O(1)$ qubits leads to a bounded weight operator
$\overleftarrow{F(u)}$. ∎

######  Proposition 6 ($(D+1)$-dimensional spacetime codes).

Let $({\cal C}_{t})_{t\in\mathbb{N}}$ be a family of Clifford circuits acting
on qubits placed on a $D$-dimensional grid $\mathbb{Z}^{D}$. If the family of
circuits is bounded and if all circuit operations act on qubits separated by a
distance $O(1)$, then the spacetime codes of the circuits are
$(D+1)$-dimensional local.

###### Proof.

By the same argument as in the proof of Proposition 5, the stabilizer
generators $\overleftarrow{F(u)}$ are obtained by back-accumulation of bounded
weight operators $F(u)$. Because the back-cumulant goes through local
operations in $D$ dimensions, this results in local generators in $(D+1)$
dimensions. ∎

###  6.2 Restriction of a stabilizer to a subset of qubits

To generate low-weight generators for a spacetime code, we will first consider
a simpler task. We are given a stabilizer group $\langle{\cal S}\rangle$ with
length $n$ and a subset $A\subset\\{1,\dots,n\\}$ of the qubits. Our objective
is to compute a generating set for the subgroup of operators $S\in\langle{\cal
S}\rangle$ whose support is included in $A$.

Let us first describe a naive solution. Assume that we are given a set of
stabilizer generators ${\cal S}=S_{1},\dots,S_{r}$. It suffices to solve the
linear system with the $n-|A|$ equations

$\prod_{i=1}^{r}(S_{i,j})^{\lambda_{i}}=I$

in the $r$ variables $\lambda_{1},\dots\lambda_{r}\in\mathbb{Z}_{2}$ where
$S_{i,j}\in{\overline{\cal P}}_{1}$ is the $j$th component of $S_{i}$ and $j$
varies over $\\{1,\dots,n\\}\backslash A$. Using Gaussian elimination, the
complexity of this approach is cubic in $n$.

This scaling may be too slow for large circuits. We can achieve a more
favorable complexity in the case of a small subset $A$ using the following
proposition. Before describing our solution, we need to introduce some
notations.

The restriction of a Pauli operator $P\in{\overline{\cal P}}_{n}$ to a subset
of qubits $A$ is the operator $P_{|A}$ obtained by setting all the components
of $P$ outside of $A$ to $I$. The restriction of a subgroup $G$ of
${\overline{\cal P}}_{n}$ to the subset $A$, denoted $G_{|A}$, is the set that
contains the restrictions of all the operators of $G$. For example, the set of
$n$-qubit Pauli operators supported on a subset $A$ of $\\{1,\dots,n\\}$ is
${\overline{\cal P}}_{n|A}$.

The following proposition yields a more efficient way to compute the
restriction of a stabilizer group to a small subset of qubits. Recall that we
use the notation $G^{\perp}$ for the set of Pauli operators that commutes with
the operators included in the subset $G$ of ${\overline{\cal P}}_{n}$. For a
stabilizer code ${\cal S}$, the set ${\cal S}^{\perp}$ is the set of logical
operators of the code.

######  Proposition 7 (Restricted stabilizer subgroup).

Let $\langle{\cal S}\rangle$ be a length-$n$ stabilizer code with stabilizer
generators ${\cal S}=\\{S_{1},\dots,S_{r}\\}$ and logical operators
$\bar{X}_{1},\bar{Z}_{1},\dots,\bar{X}_{k},\bar{Z}_{k}$. Let
$A\subset\\{1,\dots,n\\}$. A Pauli operator $P$ with support contained in $A$
is a stabilizer iff it commutes with the restricted operators
$S_{1|A},\dots,S_{r|A},\bar{X}_{1|A},\bar{Z}_{1|A},\dots,\bar{X}_{k|A},\bar{Z}_{k|A}$.

###### Proof.

A Pauli operator $P$ belongs to the stabilizer group $\langle{\cal S}\rangle$
iff it commutes with all the stabilizer generators and logical operators of
the code, that is iff $[P,L]=0$ for all $L\in{\cal S}^{\perp}$. The commutator
can be decomposed as a sum over $A$ and its complement $A^{C}$,

$[P,L]=[P,L_{|A}]+[P,L_{|A^{C}}].$

For a Pauli operator $P$ with support contained in $A$ we have
$[P,L_{|A^{C}}]=0$ and therefore $[P,L]=[P,L_{|A}].$ ∎

Based on Proposition 7, we design Algorithm 2 which returns a set of
generators for the restriction of a stabilizer group to a subset of qubits. If
each qubit is acted on by $O(1)$ stabilizer generators $S_{i}$ and $O(1)$
logical operators, the matrix ${\bf G}$ obtained at the end of line 2 has size
$O(|A|)\times O(|A|)$ and it can be constructed in $O(|A|^{2})$ bit
operations. Then, the most expensive subroutine of Algorithm 2 is the
transformation of the matrix ${\bf G}$ in reduced row echelon form which can
be done in $O(|A|^{3})$ bit operations using Gaussian elimination.

input : A set of stabilizer generators ${\cal S}=\\{S_{1},\dots,S_{r}\\}$ and
logical operators $\bar{X}_{1},\bar{Z}_{1},\dots,\bar{X}_{k},\bar{Z}_{k}$ for
a stabilizer code with length $n$.

output : A generating set for the restriction of $\langle{\cal S}\rangle$ to a
subset $A\subset\\{1,\dots,n\\}$.

1

2Construct a Pauli matrix ${\bf G}$ whose rows are the restricted operators of
the form
$S_{1|A},\dots,S_{r|A},X_{1|A},\bar{Z}_{1|A},\dots,\bar{X}_{k|A},\bar{Z}_{k|A}$.

3 Remove the rows supported on the complement $A^{C}$ of $A$ and the trivial
rows of ${\bf G}$.

4 Put ${\bf G}$ in reduced row echelon form (using Gaussian elimination).

5 Using the reduced row echelon form of ${\bf G}$, construct a Pauli matrix
${\bf H}$ whose rows satisfy $[{\bf H}_{i},{\bf G}_{j}]=\delta_{i,j}$.

6 Construct a Pauli matrix ${\bf S}^{\prime}$ whose rows are the $2|A|$
single-qubit operators $X_{i},Z_{i}$ for $i\in A$.

7 for  _each row ${\bf S}_{i}^{\prime}$ of ${\bf S}^{\prime}$_ do

8 for  _each row ${\bf H}_{j}$ of ${\bf H}$_ do

9 if  _$[{\bf S}_{i}^{\prime},{\bf G}_{j}]=1$_ then

10 Multiply ${\bf S}_{i}^{\prime}$ by ${\bf H}_{j}$.

11

12

return _the rows of ${\bf S}^{\prime}$._

Algorithm 2 Restricted Stabilizer group

###  6.3 Construction of low-weight generators for the spacetime code

To find a set of low-weight generators for a given stabilizer group, one could
apply Algorithm 2 to all subsets of $w$ qubits with $w=1,2,\dots$ until there
are enough generators to span the full stabilizer group. In this section, we
show that one can use some information about the structure of spacetime code
to help probe the right subsets of qubits and generate low-weight stabilizer
generators.

The spacetime graph of a circuit is a graph with vertex set
$V=\\{1,\dots,n\\}\times\\{0.5,1.5,\dots,\Delta-0.5\\}$ corresponding to the
qubits supporting the fault operators except the last level. The edges of the
spacetime graph are constructed by looping over all the operations of the
circuit and for each operation with level $\ell$ acting on qubits
$q_{i_{1}},\dots,q_{i_{t}}$, connecting together all the qubits of the form
$(q,\ell-0.5)$ or $(q,\ell^{\prime}+0.5)$. An operation acting on $w$ qubits
induces a clique with $2w$ vertices supported on level $\ell-0.5$ and
$\ell+0.5$. If the circuit is made with operations acting on at most $w$
qubits, the maximum degree of the spacetime graph is upper bounded by
$2(2w-1)$.

A stabilizer of a stabilizer code is said to be connected if its support is
connected in the spacetime graph. In Appendix F, we prove Proposition 12 that
the restriction of a stabilizer of the spacetime code to any connected
component of its support is a stabilizer. This proves that stabilizers of the
spacetime code can be decomposed as products of connected stabilizers. Instead
of running over all subsets of qubits, Algorithm 3 returns all the connected
stabilizers of a spacetime code by running over the neighborhoods of vertices
in the space time graph.

######  Proposition 8.

Let ${\cal C}$ be a Clifford circuit. Then Algorithm 3 returns all the
connected stabilizers of the space time code with weight up to $M$.

input : A Clifford circuit ${\cal C}$. An integer $M$.

output : A set containing all the connected stabilizers of the spacetime code
of ${\cal C}$ with weight $\leq M$.

1

2Set ${\cal S}_{M}=\\{\\}$.

3 Construct a set of generators $\\{u_{1},\dots,u_{r}\\}$ of the code ${\cal
O}({\cal C})^{\perp}$ using Algorithm 1.

4 Construct the set ${\cal S}$ of stabilizer generators
$S_{i}=\overleftarrow{F(u_{1})}$ of the spacetime code.

5 Construct a set of logical operators
$\bar{X}_{1},\bar{Z}_{1},\dots,\bar{X}_{K},\bar{Z}_{K}$ of the spacetime code.

6 Construct the spacetime graph $G=(V,E)$ of ${\cal C}$.

7 for  _all vertices $v\in V$_ do

8 Let $A$ be the set of vertices of $G$ at distance $\leq\lfloor M/2\rfloor$
from $v$.

9 Using Algorithm 2, compute a set ${\cal S}(A)$ of generators of
$\langle{\cal S}\rangle$ restricted to $A$.

10 for  _all vectors $F$ of $\langle{\cal S}(A)\rangle$ with weight $|F|\leq
M$_ do

11 Compute the connected components of the support of $F$.

12 If the support of $F$ has a single connected component, add $F$ to ${\cal
S}_{M}$.

13

14

return _${\cal S}_{M}$._

Algorithm 3 Low weight stabilizers of a spacetime code

In the case of a depth-$\Delta$ circuit acting on $n$ qubits with operations
acting on at most $w$ qubits, Algorithm 3 explores $n\Delta$ subsets $A$ of
qubits with size at most $|A|\leq 1+\sum_{i=1}^{\lfloor
M/2\rfloor}\delta(\delta-1)^{i-1}.$ where $\delta=2(2w-1)$ is the degree of
the spacetime graph.

The proof of Proposition 8 provided below relies on Proposition 12.

###### Proof.

Any connected stabilizer is supported on a connected subgraph of the spacetime
graph. As a result, any connected stabilizer with weight $\leq M$ is included
in a ball with radius $\lfloor M/2\rfloor$ of the spacetime. This guarantees
that it will be discovered by Algorithm 3. ∎

##  7 Conclusion

We proposed an efficient and versatile strategy for the correction of circuit
faults in Clifford circuits by reducing to error correction of a stabilizer
code. The main advantage of our approach is its flexibility. It applies to any
Clifford syndrome extraction circuit, including those of topological codes and
Floquet codes, and eliminates the tedious step of mapping circuit outcomes to
corresponding syndromes. It also applies to general Clifford circuits which
are not necessarily based on a quantum code.

Our scheme can be used to automatically generate low-weight checks in Clifford
circuits. Alternatively, it may be useful as a compilation tool for detecting
and removing redundancy in a Clifford circuit, thereby reducing circuit size.
Adapting Algorithm 1 for this task is immediate.

In the future, our scheme may be improved by designing a decoder that exploits
the equivalence between different fault configurations like in the work of
Pryadko [22]. Design of better decoders for quantum LDPC codes may also
improve our scheme.

Conceptually, our work emphasizes and formally captures a circuit-centric
approach of quantum error correction and fault tolerance. This circuit-centric
approach is central to Floquet codes [17] and has also lead to new ideas for
surface codes [19]. Our formalism could be used to take this approach further
by, for example, searching over the space of quantum codes and circuits. In
particular, machine learning techniques which were limited to Kitaev’s codes
in [20] could be expanded to a much broader range of codes and circuits.

## Acknowledgements

We would like to thank David Aasen, Michael Beverland, Jeongwan Haah, Vadym
Kliuchnikov and Marcus Silva for insightful discussions.

## References

  * [1] Scott Aaronson and Daniel Gottesman.  Improved simulation of stabilizer circuits.  Physical Review A, 70(5):052328, 2004.
  * [2] Dave Bacon, Steven T Flammia, Aram W Harrow, and Jonathan Shi.  Sparse quantum codes from quantum circuits.  In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 327–334, 2015.
  * [3] Elwyn Berlekamp, Robert McEliece, and Henk Van Tilborg.  On the inherent intractability of certain coding problems (corresp.).  IEEE Transactions on Information Theory, 24(3):384–386, 1978.
  * [4] Hector Bombin and Miguel Angel Martin-Delgado.  Topological quantum distillation.  Physical review letters, 97(18):180501, 2006.
  * [5] Sergey Bravyi and Jeongwan Haah.  Quantum self-correction in the 3d cubic code model.  Physical review letters, 111(20):200501, 2013.
  * [6] Sergey Bravyi and Alexei Kitaev.  Universal quantum computation with ideal clifford gates and noisy ancillas.  Physical Review A, 71(2):022316, 2005.
  * [7] Rui Chao, Michael E Beverland, Nicolas Delfosse, and Jeongwan Haah.  Optimization of the surface code design for majorana-based qubits.  Quantum, 4:352, 2020.
  * [8] Nicolas Delfosse, Vivien Londe, and Michael E Beverland.  Toward a union-find decoder for quantum ldpc codes.  IEEE Transactions on Information Theory, 2022.
  * [9] Nicolas Delfosse and Naomi H Nickerson.  Almost-linear time decoding algorithm for topological codes.  Quantum, 5:595, 2021.
  * [10] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill.  Topological quantum memory.  Journal of Mathematical Physics, 43(9):4452–4505, 2002.
  * [11] Austin G Fowler, Matteo Mariantoni, John M Martinis, and Andrew N Cleland.  Surface codes: Towards practical large-scale quantum computation.  Physical Review A, 86(3):032324, 2012.
  * [12] Robert Gallager.  Low-density parity-check codes.  IRE Transactions on information theory, 8(1):21–28, 1962.
  * [13] Craig Gidney.  Stim: a fast stabilizer circuit simulator.  Quantum, 5:497, 2021.
  * [14] Craig Gidney.  A pair measurement surface code on pentagons.  arXiv preprint arXiv:2206.12780, 2022.
  * [15] Daniel Gottesman.  The heisenberg representation of quantum computers.  arXiv preprint quant-ph/9807006, 1998.
  * [16] Daniel Gottesman.  Opportunities and challenges in fault-tolerant quantum computation, 2022\.
  * [17] Matthew B Hastings and Jeongwan Haah.  Dynamically generated logical qubits.  Quantum, 5:564, 2021.
  * [18] Pavithran Iyer and David Poulin.  Hardness of decoding quantum stabilizer codes.  IEEE Transactions on Information Theory, 61(9):5209–5223, 2015\.
  * [19] Matt McEwen, Dave Bacon, and Craig Gidney.  Relaxing hardware requirements for surface code circuits using time-dynamics.  arXiv preprint arXiv:2302.02192, 2023.
  * [20] Hendrik Poulsen Nautrup, Nicolas Delfosse, Vedran Dunjko, Hans J Briegel, and Nicolai Friis.  Optimizing quantum error correction codes with reinforcement learning.  Quantum, 3:215, 2019.
  * [21] Pavel Panteleev and Gleb Kalachev.  Degenerate quantum ldpc codes with good finite length performance.  Quantum, 5:585, 2021.
  * [22] Leonid P Pryadko.  On maximum-likelihood decoding with circuit-level errors.  Quantum, 4:304, 2020.
  * [23] Matthew J Reagor, Thomas C Bohdanowicz, David Rodriguez Perez, Eyob A Sete, and William J Zeng.  Hardware optimized parity check gates for superconducting surface codes.  arXiv preprint arXiv:2211.06382, 2022.
  * [24] Joschka Roffe, David R. White, Simon Burton, and Earl Campbell.  Decoding across the quantum low-density parity-check code landscape.  Physical Review Research, 2(4), Dec 2020.

##  Appendix A Outcomes of the check operators

This section relates the value of a check of the outcome code to the
measurement outcome of a check operator, justifying the definition of check
operators. The first lemma provides a description of the outcomes flipped by a
set of faults as a commutator of the corresponding fault operator.

######  Lemma 3 (Outcome flip).

Let $F$ be a fault operator. The faults corresponding to $F$ induce a flip of
the measurement of $S_{j}$ iff
$[\overrightarrow{F},\eta_{\ell_{j}-0.5}(S_{j})]=1$.

###### Proof.

Based on Proposition 1, the faults represented by $F$ induce a flip of the
outcome of $S_{j}$ iff $[\overrightarrow{F}_{\ell_{j}-0.5},S_{j}]=1$ and
because $\eta_{\ell_{j}-0.5}(S_{j})$ is trivial except at level
$\ell_{j}-0.5$, we have
$[\overrightarrow{F}_{\ell_{j}-0.5},S_{j}]=[\overrightarrow{F},\eta_{\ell_{j}-0.5}(S_{j})]$.
∎

The following Lemma shows that measurement of a check operator returns the
value of the corresponding check of the outcome code.

######  Lemma 4 (Check operator outcome).

Let $F$ be a fault operator. The faults corresponding to $F$ induce a flip of
an outcome check $u\in{\cal O}({\cal C})^{\perp}$ iff
$[F,\overleftarrow{F(u)}]=1$.

###### Proof.

By definition of $F(u)$, we have

$\displaystyle[F,\overleftarrow{F(u)}]$
$\displaystyle=[F,\overleftarrow{\prod_{j=1}^{m}\eta_{\ell_{j}-0.5}(S_{j}^{u_{j}})}]$

which leads to

$\displaystyle[F,\overleftarrow{F(u)}]$
$\displaystyle=[F,\prod_{j=1}^{m}\overleftarrow{\eta_{\ell_{j}-0.5}(S_{j}^{u_{j}})}]$
Using Eq. (15)
$\displaystyle=\sum_{j=1}^{m}[F,\overleftarrow{\eta_{\ell_{j}-0.5}(S_{j}^{u_{j}})}]$
Using Eq. (17)
$\displaystyle=\sum_{j=1}^{m}[\overrightarrow{F},\eta_{\ell_{j}-0.5}(S_{j}^{u_{j}})]$
By Proposition. 3

By Lemma. 3, this last sum coincides with the check $\sum_{j}u_{j}o_{j}$ of
the outcome code corresponding to the vector $u$. ∎

The next lemma states that an error $S_{j}$ right before or right after the
measurement of $S_{j}$ does not flip any of the check operator outcomes.

######  Lemma 5 (Stabilizer error).

For all $u\in{\cal O}({\cal C})^{\perp}$ and for all measured operators
$S_{j}$, we have $[{\eta_{\ell_{j}\pm 0.5}(S_{j})},\overleftarrow{F(u)}]=0.$

###### Proof.

Because $S_{j}$ belongs to the stabilizer group of the system right after
level $\ell_{j}$, the faults corresponding to ${\eta_{\ell_{j}+0.5}(S_{j})}$
do not flip any of the checks of the outcome code. Based on Lemma 4, this
leads to the lemma for the sign $\ell_{j}+0.5$. The same result holds for
$\ell_{j}-0.5$ because a fault $S_{j}$ after the measurement of $S_{j}$ is
equivalent to a fault $S_{j}$ before this measurement. ∎

A Pauli error on the input state also keeps the check operator outcomes
trivial.

######  Lemma 6 (Input error).

For all $u\in{\cal O}({\cal C})^{\perp}$ and for all $P\in{\overline{\cal
P}}_{n}$, we have $[\eta_{0.5}(P),\overleftarrow{F(u)}]=0.$

###### Proof.

An fault $P$ on the input state of the circuit cannot flip the value of a
check because the outcome code ${\cal O}({\cal C})$ is the set of checks for
all possible input states. Based on Lemma 4, this implies
$[\eta_{0.5}(P),\overleftarrow{F(u)}]=0$ for all check $u$ of the outcome
code. ∎

##  Appendix B Commutation of the check operators

The goal of this section is to prove that check operators are pairwise
commuting. More precisely, we show by induction on $\ell$ that
$[\overleftarrow{F(u)}_{\ell+0.5},\overleftarrow{F(v)}_{\ell+0.5}]=0$ for all
$\ell$.

######  Proposition 9.

Let ${\cal C}$ be a Clifford circuit. For all $u,v\in{\cal O}({\cal
C})^{\perp}$, we have $[\overleftarrow{F(u)},\overleftarrow{F(v)}]=0.$

###### Proof.

Based on Eq. (18), we have

$\displaystyle[\overleftarrow{F(u)},\overleftarrow{F(v)}]=\sum_{\ell=0}^{\Delta}[\overleftarrow{F(u)}_{\ell+0.5},\overleftarrow{F(v)}_{\ell+0.5}]$

In the remainder of this proof, we demonstrate by induction on $\ell$ (in
decreasing order) that
$[\overleftarrow{F(u)}_{\ell+0.5},\overleftarrow{F(v)}_{\ell+0.5}]=0$ for all
$\ell$.

For $\ell=\Delta$, by definition we have
${F(u)_{\Delta+0.5}}={F(v)_{\Delta+0.5}}=I$ and therefore
$\overleftarrow{F(u)}_{\Delta+0.5}=\overleftarrow{F(v)}_{\Delta+0.5}=I$ which
yields
$[\overleftarrow{F(u)}_{\Delta+0.5},\overleftarrow{F(v)}_{\Delta+0.5}]=0.$

Assume now that
$[\overleftarrow{F(u)}_{\ell+1.5},\overleftarrow{F(v)}_{\ell+1.5}]=0$ and let
us prove that
$[\overleftarrow{F(u)}_{\ell+0.5},\overleftarrow{F(v)}_{\ell+0.5}]=0$. Using
Proposition 2 and Eq. (11), we find

$\displaystyle\overleftarrow{F(u)}_{\ell+0.5}$
$\displaystyle=\prod_{j=\ell}^{\Delta}U_{\ell,j}^{-1}F(u)_{j+0.5}U_{\ell,j}$
$\displaystyle=F(u)_{\ell+0.5}\prod_{j=\ell+1}^{\Delta}U_{\ell,j}^{-1}F(u)_{j+0.5}U_{\ell,j}$
$\displaystyle=F(u)_{\ell+0.5}\prod_{j=\ell+1}^{\Delta}\left(U_{\ell+1,j}U_{\ell,\ell+1}\right)^{-1}F(u)_{j+0.5}U_{\ell+1,j}U_{\ell,\ell+1}$
$\displaystyle=F(u)_{\ell+0.5}U_{\ell,\ell+1}^{-1}\left(\prod_{j=\ell+1}^{\Delta}U_{\ell+1,j}^{-1}F(u)_{j+0.5}U_{\ell+1,j}\right)U_{\ell,\ell+1}$
$\displaystyle=F(u)_{\ell+0.5}U_{\ell,\ell+1}^{-1}\overleftarrow{F(u)}_{\ell+1.5}U_{\ell,\ell+1}$

The same holds for $v$, that is $\overleftarrow{F(v)}_{\ell+0.5}\
=F(v)_{\ell+0.5}U_{\ell,\ell+1}^{-1}\overleftarrow{F(v)}_{\ell+1.5}U_{\ell,\ell+1}.$
Using these expressions for $\overleftarrow{F(u)}_{\ell+0.5}$ and
$\overleftarrow{F(v)}_{\ell+0.5}$ and applying Eq. (17), we obtain

$\displaystyle[\overleftarrow{F(u)}_{\ell+0.5},\overleftarrow{F(v)}_{\ell+0.5}]$
$\displaystyle=[F(u)_{\ell+0.5},F(v)_{\ell+0.5}]$
$\displaystyle\phantom{=}+[U_{\ell,\ell+1}^{-1}\overleftarrow{F(u)}_{\ell+1+0.5}U_{\ell,\ell+1},U_{\ell,\ell+1}^{-1}\overleftarrow{F(v)}_{\ell+1+0.5}U_{\ell,\ell+1}]$
$\displaystyle\phantom{=}+[F(u)_{\ell+0.5},U_{\ell,\ell+1}^{-1}\overleftarrow{F(v)}_{\ell+1+0.5}U_{\ell,\ell+1}]$
$\displaystyle\phantom{=}+[U_{\ell,\ell+1}^{-1}\overleftarrow{F(u)}_{\ell+1+0.5}U_{\ell,\ell+1},F(v)_{\ell+0.5}]\cdot$

Let us show that each of these four terms is trivial. The first one
$[F(u)_{\ell+0.5},F(v)_{\ell+0.5}]$ is trivial by definition of the $F(u)$ and
$F(v)$. Using Eq. (19) and the induction hypothesis, we get

$[U_{\ell,\ell+1}^{-1}\overleftarrow{F(u)}_{\ell+1.5}U_{\ell,\ell+1},U_{\ell,\ell+1}^{-1}\overleftarrow{F(v)}_{\ell+1.5}U_{\ell,\ell+1}]=[\overleftarrow{F(u)}_{\ell+1.5},\overleftarrow{F(v)}_{\ell+1.5}]=0$

proving that the second term is trivial. Because the operator
$U_{\ell,\ell+1}$ is the product of the unitary gates at level $\ell+1$ and
$F(u)_{\ell+0.5}$ and $F(v)_{\ell+0.5}$ corresponds to measurements at the
same level, the support of $U_{\ell,\ell+1}$ cannot overlap with the supports
of $F(u)_{\ell+0.5}$ and $F(v)_{\ell+0.5}$. As a result $U_{\ell,\ell+1}$ acts
trivially on $F(u)_{\ell+0.5}$ and $F(v)_{\ell+0.5}$. Therefore, we have

$\displaystyle[F(u)_{\ell+0.5},U_{\ell,\ell+1}^{-1}\overleftarrow{F(v)}_{\ell+1+0.5}U_{\ell,\ell+1}]$
$\displaystyle=[U_{\ell,\ell+1}F(u)_{\ell+0.5}U_{\ell,\ell+1}^{-1},\overleftarrow{F(v)}_{\ell+1.5}]$
$\displaystyle=[F(u)_{\ell+0.5},\overleftarrow{F(v)}_{\ell+1.5}]\cdot$

Therein, we used Eq. (19) in the first equality. To see that
$[F(u)_{\ell+0.5},\overleftarrow{F(v)}_{\ell+1.5}]=0$, write this commutator
as

$\displaystyle[F(u)_{\ell+0.5},\overleftarrow{F(v)}_{\ell+1.5}]$
$\displaystyle=[\eta_{\ell+1.5}(F(u)_{\ell+0.5}),\overleftarrow{F(v)}]\cdot$

and apply Lemma 5. We can apply this lemma because $F(u)_{\ell+0.5}$ is a
product of some measured operators $S_{j}$ with level $\ell_{j}=\ell+1$ in the
circuit. We proved that the third term is trivial. By symmetry, the fourth
term is trivial by the same argument. This proves that
$[\overleftarrow{F(u)}_{\ell+0.5},\overleftarrow{F(v)}_{\ell+0.5}]=0$
concluding the proof of the proposition. ∎

##  Appendix C Logical operators of the spacetime code

To describe the logical operators of the spacetime code, we introduce some
notation. For any $\ell=1,\dots,\Delta$ and for any $P\in{\overline{\cal
P}}_{n}$, define the fault operator $G(P,\ell)$ as

$\displaystyle
G(P,\ell)=\eta_{\ell-0.5}(P)\eta_{\ell+0.5}(U^{-1}_{\ell-1,\ell}PU_{\ell-1,\ell})\cdot$
(25)

These operators satisfy

$\displaystyle\overrightarrow{G(P,\ell)}=\eta_{\ell-0.5}(P)\cdot$ (26)

For any vector $v\in\mathbb{Z}_{2}^{m}$, define the fault operator $L(v)$ as

$\displaystyle L(v)=\prod_{j=1}^{m}G(P_{j},\ell_{j})^{v_{j}}$ (27)

where $\ell_{j}$ is the level of the $j$ th measured operator $S_{j}$ and
$P_{j}\in{\overline{\cal P}}_{n}$ is an arbitrary Pauli operator acting on the
support of $S_{j}$ that anti-commutes with $S_{j}$. Because $P_{j}$ is
included in the support of $S_{j}$ it commutes with all other measured
operators at level $\ell_{j}$.

######  Proposition 10.

Let ${\cal C}$ be a depth-$\Delta$ Clifford circuit acting on $n$ qubits. The
stabilizers and logical operators of the spacetime code are generated by the
following operators.

  * •

A set of operators $\eta_{\Delta+0.5}(P)$ where $P\in{\overline{\cal P}}_{n}$
runs over a basis of ${\overline{\cal P}}_{n}$.

  * •

A set of operators $G(P,\ell)$ for all $\ell=1,\dots,\Delta$ where
$P\in{\overline{\cal P}}_{n}$ runs over a basis of the space of Pauli
operators that commutes with all the measured operators at level $\ell$.

  * •

A set of operators $L(v)$ where $v\in\mathbb{Z}_{2}^{m}$ runs over a basis of
the space ${\cal O}({\cal C})$.

The following lemma is used in the proof of the proposition.

######  Lemma 7.

For all $u,v\in\mathbb{Z}_{2}^{m}$, we have
$[\overleftarrow{F(u)},L(v)]=(u|v).$

###### Proof.

$\displaystyle[\overleftarrow{F(u)},L(v)]$
$\displaystyle=[F(u),\overrightarrow{L(v)}]$ By Proposition 3
$\displaystyle=[F(u),\overrightarrow{\prod_{j=1}^{m}L(P_{j},\ell_{j})^{v_{j}}}]$
By definition of $L(v)$
$\displaystyle=[F(u),\prod_{j=1}^{m}\overrightarrow{G(P_{j},\ell_{j})^{v_{j}}}]$
By Eq. (14)
$\displaystyle=\sum_{j=1}^{m}v_{j}[F(u),\overrightarrow{G(P_{j},\ell_{j})}]$
By Eq. (17)
$\displaystyle=\sum_{j=1}^{m}v_{j}[F(u),\eta_{\ell_{j}-0.5}(P_{j})]$ By Eq.
(26) $\displaystyle=\sum_{j=1}^{m}v_{j}[F(u)_{\ell_{j}-0.5},P_{j}]$

By definition of $P_{i}$, we have $[F(u)_{\ell_{j}-0.5},P_{j}]=u_{j}$ which
yields $[\overleftarrow{F(u)},L(v)]=(u|v).$ ∎

###### Proof of Proposition 10.

First, let us prove that these three families of operators are logical
operators of the spacetime code, that is that they commute with all
stabilizers $\overleftarrow{F(u)}$ with $u\in{\cal O}({\cal C})^{\perp}$.

The operators of the form $\eta_{\Delta+0.5}(P)$ satisfy

$\displaystyle[\overleftarrow{F(u)},\eta_{\Delta+0.5}(P)]$
$\displaystyle=[F(u),\overrightarrow{\eta_{\Delta+0.5}(P)}]$
$\displaystyle=[F(u),\eta_{\Delta+0.5}(P)]$

which is trivial because $F(u)$ is trivial over level $\Delta+0.5$.

For the operators $G(P,\ell)$, we get

$[\overleftarrow{F(u)},G(P,\ell)]=[F(u),\overrightarrow{G(P,\ell)}]$

which is equal to $[F(u),\eta_{\ell-0.5}(P)]$ by Eq. 26. Because $P$ commute
with all the measured operators at level $\ell$, we get

$\displaystyle[\overleftarrow{F(u)},G(P,\ell)]$
$\displaystyle=[\eta_{\ell-0.5}(P),F(u)]$
$\displaystyle=[F(u)_{\ell-0.5},P]=0\cdot$

For the operators $L(v)$, based on Lemma 7 we have
$[\overleftarrow{F(u)},L(v)]=(u|v)$ and this inner product is trivial because
$v$ is in the code ${\cal O}({\cal C})$ and $u$ belongs to its dual.

To prove that these three families of operators generate all stabilizers and
logical operators, it is enough to show that the group they generate has rank
$2K+R$ where $K$ is the number of logical qubits of the stabilizer code and
$R$ is the rank of the stabilizer group. For the spacetime code, we know that
$K=n(\Delta+1)-r$ and $R=r$

Denote by $L_{1},L_{2},L_{3}$ the subgroups of ${\overline{\cal
P}}_{n}(\delta+1)$ generated by these three sets of operators. We have
$L_{1}\cap L_{2}=\\{I\\}$ because the operators of $L_{2}$ are supported on at
least two levels and $L_{1}$ has support on level $\Delta+0.5$. We also have
$L_{1}\cap L_{3}=\\{I\\}$ because the operators of $L_{1}$ cannot flip any
outcome and the only operator of $L_{3}$ that induces no outcome flip is $I$.
The same argument also shows that $L_{2}\cap L_{3}=\\{I\\}$. As a result, the
rank of the subgroup of ${\overline{\cal P}}_{n}(\delta+1)$ generated by all
the operators of $L_{1},L_{2}$ and $L_{3}$ is the sum of the ranks of the
three subgroups
$\operatorname{rank}(L_{1})+\operatorname{rank}(L_{2})+\operatorname{rank}(L_{3})$.

It is immediate to see that $\operatorname{rank}(L_{1})=2n$. For a circuit
without measurement the rank of $L_{2}$ is $2n\Delta$. The constraint
associated with the commutation with each measurement decreases the rank by
$1$, which yields $\operatorname{rank}(L_{2})=2n\Delta-m$ where $m$ is the
number of measurements of the circuit. Finally, the rank of $L_{3}$ is given
by the dimension of the outcome code, that is
$\operatorname{rank}(L_{3})=m-r$.

Putting things together this proves that these three sets of operators
generate a group with rank $2n(\Delta+1)-r$ which coincides with the value of
$2K+R$. This proves that this family of operators generate all stabilizer and
logical operators. ∎

##  Appendix D Levels supporting a check operator

In this section, we prove the support of a check operator of the spacetime
code is related to the support of the measurements involved in the
corresponding check of the outcome code.

######  Lemma 8.

Let $u\in{\cal O}({\cal C})^{\perp}$ be a non-zero vector. Denote by
$\ell_{u}$ (respectively $\ell_{u}^{\prime}$) the minimum (respectively
maximum) level of a measured operator $S_{j}$ with $u_{j}=1$. If
$\ell<\ell_{u}$ or $\ell\geq\ell_{u}^{\prime}$ then we have
$\overleftarrow{F(u)}_{\ell+0.5}=I.$

###### Proof.

By definition of $\ell_{u}^{\prime}$, for all $\ell\geq\ell_{u}^{\prime}$ the
component $F(u)_{\ell+0.5}$ is trivial. Applying Proposition 2, this shows
that $\overleftarrow{F(u)}_{\ell+0.5}$ is also trivial for all
$\ell\geq\ell_{u}^{\prime}$.

Assume now that $\ell=0$. We know from Lemma 6 that $\overleftarrow{F(u)}$
commutes with all fault operators $\eta_{0.5}(P)$ supported on level $0.5$.
Because $P$ can be any operator of ${\overline{\cal P}}_{n}$, this implies
$\overleftarrow{F(u)}_{0.5}=I$.

Consider now the case $\ell<\ell_{u}$ and let us prove that
$\overleftarrow{F(u)}_{\ell+0.5}=\overleftarrow{F(u)}_{0.5}$ which is the
identity. Applying Proposition 2, we find

$\displaystyle\overleftarrow{F(u)}_{0.5}=\prod_{j=\ell}^{\Delta}\left(U_{0,j}^{-1}F_{j+0.5}U_{0,j}\right)$

because for all $j<\ell$, we know that $F(u)_{j+0.5}=I$. Using Eq. (11), we
can write $U_{0,j}=U_{\ell,j}U_{0,\ell}$ for all $j\leq\ell$ which yields

$\displaystyle\overleftarrow{F(u)}_{0.5}$
$\displaystyle=\prod_{j=\ell}^{\Delta}\left((U_{\ell,j}U_{0,\ell})^{-1}F_{j+0.5}U_{\ell,j}U_{0,\ell}\right)$
$\displaystyle=U_{0,\ell}^{-1}\prod_{j=\ell}^{\Delta}\left(U_{\ell,j}^{-1}F_{j+0.5}U_{\ell,j}\right)U_{0,\ell}$
$\displaystyle=U_{0,\ell}^{-1}\overleftarrow{F(u)}_{\ell+0.5}U_{0,\ell}\cdot$

Because $\overleftarrow{F(u)}_{0.5}$ is trivial, this relation implies
$\overleftarrow{F(u)}_{\ell+0.5}=U_{0,\ell}\overleftarrow{F(u)}_{0.5}U_{0,\ell}^{-1}=I$.
∎

##  Appendix E Alternative definition of the check operators

One may prefer to use the cumulant obtained by propagating faults forward
instead of the back-cumulant obtained from the backward propagation of faults.
Here, we show that we can obtain the check operators by propagating forward
the fault operators ${F^{\prime}(u)}$ defined in Section 5.1.

######  Proposition 11.

If $u\in{\cal O}({\cal C})^{\perp}$, then, we have

$\displaystyle\overleftarrow{F(u)}=\overrightarrow{F^{\prime}(u)}\cdot$ (28)

Let us first prove a lemma.

######  Lemma 9.

Let $u\in\mathbb{Z}_{2}^{m}$. If $\overleftarrow{F(u)}_{0.5}=I$ then we have

$\displaystyle\overleftarrow{F(u)}=\overrightarrow{F^{\prime}(u)}\cdot$ (29)

###### Proof.

Let us prove by induction that we have the equality
$\overleftarrow{F(u)}_{\ell+0.5}=\overrightarrow{F^{\prime}(u)}_{\ell+0.5}$
for all level $\ell$.

For $\ell=0$, we have $\overleftarrow{F(u)}_{0.5}=I$ by assumption and by
definition of the cumulant we have $\overrightarrow{F^{\prime}(u)}_{0.5}=I$.

Assume that the result is true for level $\ell-1<\Delta$. Using Proposition 2,
we obtain

$\displaystyle\overrightarrow{F^{\prime}(u)}_{\ell+0.5}$
$\displaystyle=U_{\ell}\overrightarrow{F^{\prime}(u)}_{\ell-0.5}U_{\ell}^{-1}F^{\prime}(u)_{\ell+0.5}$
(30)

and

$\displaystyle\overleftarrow{F(u)}_{\ell-0.5}$
$\displaystyle=U_{\ell}^{-1}\overleftarrow{F(u)}_{\ell+0.5}U_{\ell}F(u)_{\ell-0.5}\cdot$
(31)

Using the induction hypothesis, we can replace
$\overrightarrow{F^{\prime}(u)}_{\ell-0.5}$ by
$\overleftarrow{F(u)}_{\ell-0.5}$ in Eq. (30) and we can use Eq. (31) for the
value of $\overleftarrow{F(u)}_{\ell-0.5}$. This leads to the equation

$\displaystyle\overrightarrow{F^{\prime}(u)}_{\ell+0.5}$
$\displaystyle=U_{\ell}\overleftarrow{F(u)}_{\ell-0.5}U_{\ell}^{-1}F^{\prime}(u)_{\ell+0.5}$
$\displaystyle=U_{\ell}U_{\ell}^{-1}\overleftarrow{F(u)}_{\ell+0.5}U_{\ell}F(u)_{\ell-0.5}U_{\ell}^{-1}F^{\prime}(u)_{\ell+0.5}$
$\displaystyle=\overleftarrow{F(u)}_{\ell+0.5}U_{\ell}F(u)_{\ell-0.5}U_{\ell}^{-1}F^{\prime}(u)_{\ell+0.5}$

By definition of $U_{\ell}$ acts trivially on $F(u)_{\ell-0.5}$ implying
$U_{\ell}F(u)_{\ell-0.5}U_{\ell}^{-1}=F(u)_{\ell-0.5}.$ Injecting this in the
previous equation produces

$\displaystyle\overrightarrow{F^{\prime}(u)}_{\ell+0.5}$
$\displaystyle=\overleftarrow{F(u)}_{\ell+0.5}F(u)_{\ell-0.5}F^{\prime}(u)_{\ell+0.5}$

which leads to
$\overrightarrow{F^{\prime}(u)}_{\ell+0.5}=\overleftarrow{F(u)}_{\ell+0.5}$
because $F(u)_{\ell-0.5}=F^{\prime}(u)_{\ell+0.5}$ by definition. ∎

###### Proof of Proposition 11.

By Lemma 6, we know that $\overleftarrow{F(u)}_{0.5}$ commutes with all Pauli
operators $P\in{\overline{\cal P}}_{n}$. The only Pauli operator that
satisfies this property is $\overleftarrow{F(u)}_{0.5}=I$. Therefore, the
operator $\overleftarrow{F(u)}$ satisfies the assumption of Lemma 9 which
proves the Proposition. ∎

##  Appendix F The connected components of a stabilizer of the spacetime code

The proof of proposition 8 relies on the following proposition. The proof of
this proposition relies on lemmas proven after the proposition.

######  Proposition 12.

Let $S$ be a stabilizer for a spacetime code. The restriction $S_{|\kappa}$ of
$S$ to a connected component $\kappa$ of the support of $S$ in the spacetime
graph is a stabilizer of the spacetime code.

###### Proof.

Based on lemma 10, the restriction $S_{|\kappa}$ can be written as
$\overleftarrow{F(v)}$ for some vector $v$. To show that this is a stabilizer
of the spacetime code, we must show that $v\in{\cal O}({\cal C})^{\perp}$.
Denote by $\ell_{v}^{\prime}$ the maximum level of a measured operator $S_{j}$
of the circuit such that $v_{j}=1$. The product of the measured operators
indexed by $v$ at level $\ell_{v}^{\prime}$ is $F(v)_{\ell_{v}^{\prime}-0.5}$.
By Lemma 11, this operator is equal to
$\overrightarrow{F^{\prime}(v)}_{\ell_{v}^{\prime}-0.5}$. This is a stabilizer
for the output of the circuit ${\cal C}[\ell_{v}^{\prime}-1]$ based on Lemma
12 (recall that ${\cal C}[\ell_{v}^{\prime}]$ is the subcircuit containing all
the operations of ${\cal C}$ with level $\leq\ell_{v}^{\prime}$). This implies
that, in the absence of circuit faults, the outcomes of the measurements of
the operators $S_{j}$ with $v_{j}=1$ have a fixed parity 0, which means that
$(o|v)=0$ for all $o\in{\cal O}({\cal C})$. This proves the proposition. ∎

######  Lemma 10.

Let ${\cal C}$ be a Clifford circuit with $m$ measurements. Let $S$ be a
stabilizer for the corresponding spacetime code. We can decompose $S$ as

$S=\prod_{i}\overleftarrow{F(u(i))}$

where $u(i)\in\mathbb{Z}_{2}^{m}$. Moreover, the support of the operators
$\overleftarrow{F(u(i))}$ have disjoint supports.

###### Proof.

We can decompose $S$ as

$S=\prod_{i}S_{|\kappa_{i}}$

where $\kappa_{1},\kappa_{2},\dots$ are the connected components of the
support of $S$ in the spacetime graph. By construction, the operators
$S_{|\kappa_{i}}$ have disjoint support.

Because it is a stabilizer, the operator $S$ is of the form
$\overleftarrow{F(u)}$ with $u\in{\cal O}({\cal C})^{\perp}$. Given a measured
operator $S_{j}$ of the circuit with level $\ell_{j}$, define $V(S_{j})$ to be
the set of vertices of spacetime graph of the form $(\ell_{j}\pm 0.5,q)$ where
$q$ is a qubit of the support of $S_{j}$. Define the vector
$u(i)\in\mathbb{Z}_{2}^{m}$ to be the restriction of $u$ to the set of
coordinates $j$ such that the circuit operation $V(S_{j})$ overlaps with
$\kappa_{i}$. Because it is a clique of the spacetime graph, a set $V(S_{j})$
can only overlap with a single connected component $\kappa_{i}$. Therefore,
$u$ can be decomposed as $u=\sum_{i}u(i)$ and the vectors $u(i)$ do not
overlap. Applying Proposition 4, this yields

$\overleftarrow{F(u)}=\prod_{i}\overleftarrow{F(u(i))}\cdot$

Now let us show that the support of $\overleftarrow{F(u(i))}$ is the component
$\kappa_{i}$. By definition of the back-cumulant, if a qubit $Q=(\ell+0.5,q)$
belongs to the support of $\overleftarrow{F(u(i))}$, there must exists a path
in this support that connects $Q$ to a set $V(S_{j})$ for some
$j\in\operatorname{supp}(u(i))$ (otherwise one cannot reach $Q$ by back-
propagating $F(u(i))$). By definition of the set $u(i)$, the proves that the
qubit $Q$ is part of the connected component $\kappa_{i}$. This shows that
$\operatorname{supp}(\overleftarrow{F(u(i))})=\kappa_{i}$ which implies
$\overleftarrow{F(u(i))}=S_{\kappa_{i}}$ and leads to the decomposition
claimed in the lemma. ∎

######  Lemma 11.

Let ${\cal C}$ be a Clifford circuit with depth $\Delta$ and with $m$
measurements. Let $v\in\mathbb{Z}_{2}^{m}$. If $\overleftarrow{F(v)}_{0.5}=I$,
then we have

$F(v)_{\ell_{v}^{\prime}-0.5}=\overrightarrow{F^{\prime}(v)}_{\ell_{v}^{\prime}-0.5}$

where $\ell_{v}^{\prime}$ is the maximum level of a measured operator $S_{j}$
with $v_{j}=1$.

###### Proof.

By definition, level $\ell_{v}^{\prime}-0.5$ is the largest non-trivial level
of $\overleftarrow{F(v)}$ and for this level we have

$\overleftarrow{F(v)}_{\ell_{v}^{\prime}-0.5}=F(v)_{\ell_{v}^{\prime}-0.5}.$

Combining this with Lemma 9 this proves result. ∎

In the following lemma ${\cal C}[\ell]$ denotes the subcircuit of ${\cal C}$
that contains all the operations of ${\cal C}$ with level $\leq\ell$.

######  Lemma 12.

Let ${\cal C}$ be a Clifford circuit with depth $\Delta$ and with $m$
measurements. Let $u\in{\cal O}({\cal C})^{\perp}$ and let
$v\in\mathbb{Z}_{2}^{m}$ such that $\overleftarrow{F(v)}$ is the restriction
of $\overleftarrow{F(u)}$ to one of a connected component of its support in
the spacetime graph. Then for all $\ell=1,\dots\Delta$, the operator
$\overrightarrow{F^{\prime}(v)}_{\ell+0.5}$ belongs to output stabilizer group
of the subcircuit ${\cal C}[\ell]$.

###### Proof.

Let us prove this result by induction on $\ell$.

For $\ell=1$, the result holds because the stabilizer group of the output of
the subcircuit ${\cal C}[1]$ is generated by the measured operators at level
$1$ and $\overrightarrow{F^{\prime}(v)}_{1.5}=F^{\prime}(v)_{1.5}$ is a
product of measured operators at level $1$.

Assume now that $\overrightarrow{F^{\prime}(v)}_{\ell-1+0.5}$ is a stabilizer
of the output state of the circuit ${\cal C}[\ell-1]$ and let us prove that
the result is true at level $\ell$.

The measurements performed at level $\ell$ do not affect the stabilizer
$\overrightarrow{F^{\prime}(v)}_{\ell-1+0.5}$ of the circuit because it
commutes with these measurements. Indeed, consider a measured operator $M$ of
the level $\ell$. From Lemma 5, we know that
$[\eta_{\ell-0.5}(M),\overleftarrow{F(u)}]=0$ because $\overleftarrow{F(u)}$
is a stabilizer of the spacetime code. This equation leads to
$[M,\overleftarrow{F(u)}_{\ell-0.5}]=0$ and
$[M,\overrightarrow{F^{\prime}(u)}_{\ell-0.5}]=0$ using Lemma 9. By definition
of the spacetime graph of the circuit, the operation $M$ can only overlap with
at most one of the connected component of the
$\overrightarrow{F^{\prime}(u)}$. Therefore, we also have
$[M,\overrightarrow{F^{\prime}(v)}_{\ell-0.5}]=0.$ This proves that the
stabilizer $\overrightarrow{F^{\prime}(v)}_{\ell-0.5}$ commutes with all the
operators measured at level $\ell$. As a result, it is still a stabilizer
after applying these measurements. Moreover, the measured operators are also
stabilizers.

Consider now the effect of the unitary operations. The unitary operations of
level $\ell$ induce a conjugation of the stabilizers by $U_{\ell}$ which is
the product of all unitary operations at level $\ell$. This maps the
stabilizer $\overrightarrow{F^{\prime}(v)}_{\ell-1+0.5}$ onto

$\displaystyle U_{\ell}\overrightarrow{F^{\prime}(v)}_{\ell-1+0.5}U_{\ell}$
$\displaystyle=\prod_{j=0}^{\ell-1}U_{j,\ell}F^{\prime}(v)_{j+0.5}U_{j,\ell}^{-1}\cdot$
(32)

Moreover, we know that $F^{\prime}(v)_{\ell+0.5}$ is a stabilizer because it
is a product of measured operators at level $\ell$. Multiplying the stabilizer
obtained Eq. (32) with $F^{\prime}(v)_{\ell+0.5}$ we get the stabilizer
$\overrightarrow{F^{\prime}(v)}_{\ell+0.5}$ for the output of the circuit
${\cal C}[\ell]$. ∎