# Fault-tolerant transformations of spacetime codes

Arthur Pesah, Austin K. Daniel, Ilan Tzitrin, Michael Vasmer

► To cite this version:

Arthur Pesah, Austin K. Daniel, Ilan Tzitrin, Michael Vasmer. Fault-tolerant transformations of spacetime codes. 2026. hal-05425964

HAL Id: hal-05425964

https://hal.science/hal-05425964v1

Preprint submitted on 20 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Fault-tolerant transformations of spacetime codes

Arthur Pesah¹,², Austin K. Daniel¹, Ilan Tzitrin¹, and Michael Vasmer¹,³,⁴,⁵

¹Xanadu Quantum Technologies Inc., Toronto, Ontario, M5G 2C8, Canada

²University College London, Gower Street, London WC1E 6BT, United Kingdom

³Inria Paris, 48 rue Barrault, Paris 75013, France

⁴Institute for Quantum Computing, Waterloo, Ontario, N2L 3G1, Canada

⁵Perimeter Institute for Theoretical Physics, Waterloo, Ontario, N2L 2Y5, Canada

Recent advances in quantum error-correction (QEC) have shown that it is often beneficial to understand fault-tolerance as a dynamical process—a circuit with redundant measurements that help correct errors—rather than as a static code equipped with a syndrome extraction circuit. Spacetime codes have emerged as a natural framework to understand error correction at the circuit level while leveraging the traditional QEC toolbox. Here, we introduce a framework based on chain complexes and chain maps to model spacetime codes and transformations between them. We show that stabilizer codes, quantum circuits, and decoding problems can all be described using chain complexes, and that the equivalence of two spacetime codes can be characterized by specific maps between chain complexes, the *fault-tolerant maps*, that preserve the number of encoded qubits, fault distance, and minimum-weight decoding problem. As an application of this framework, we extend the foliated cluster state construction from stabilizer codes to any spacetime code, showing that any Clifford circuit can be transformed into a measurement-based protocol with the same fault-tolerant properties. To this protocol, we associate a chain complex which encodes the underlying decoding problem, generalizing previous cluster state complex constructions. Our method enables the construction of cluster states from non-CSS, subsystem, and Floquet codes, as well as from logical Clifford operations on a given code.

## Contents

<table><tr><td><b>1 Introduction</b></td><td><b>2</b></td></tr><tr><td>1.1 Motivation</td><td>2</td></tr><tr><td>1.2 Main results</td><td>4</td></tr><tr><td>1.3 Reader's guide</td><td>5</td></tr><tr><td><b>2 Quantum error correction from chain complexes</b></td><td><b>6</b></td></tr><tr><td>2.1 Notation</td><td>6</td></tr><tr><td>2.2 Homological quantum error correction</td><td>6</td></tr><tr><td>2.3 Graphical representation of a chain complex</td><td>10</td></tr></table>
<table><tbody><tr><td>2.4 Fault-tolerant maps</td><td>11</td></tr><tr><td>2.5 Rule A</td><td>13</td></tr><tr><td>2.6 Rule B</td><td>19</td></tr><tr><td><b>3</b> Spacetime codes</td><td><b>22</b></td></tr><tr><td>3.1 Outcome code</td><td>22</td></tr><tr><td>3.2 Detectors of the spacetime code</td><td>23</td></tr><tr><td>3.3 Spacetime subsystem code</td><td>26</td></tr><tr><td>3.4 Stabilizers of the spacetime subsystem code</td><td>27</td></tr><tr><td>3.5 Logical operators of the spacetime subsystem code</td><td>29</td></tr><tr><td>3.6 Relationship to other frameworks</td><td>31</td></tr><tr><td><b>4</b> Fault-tolerant measurement-based quantum computing</td><td><b>33</b></td></tr><tr><td>4.1 Measurement-based quantum computing</td><td>34</td></tr><tr><td>4.2 Spacetime code of an MBQC circuit</td><td>36</td></tr><tr><td>4.3 Cluster state complex</td><td>38</td></tr><tr><td><b>5</b> Cluster state complex from a Clifford circuit</td><td><b>46</b></td></tr><tr><td>5.1 General lemmas</td><td>48</td></tr><tr><td>5.2 Compilation of the circuit into H, HS and CZ networks</td><td>51</td></tr><tr><td>5.3 Measurement-based H and HS gates</td><td>53</td></tr><tr><td>5.4 Merge of CZ networks</td><td>55</td></tr><tr><td>5.5 Example: transversal logical gate</td><td>64</td></tr><tr><td><b>6</b> Cluster state complex from a stabilizer code</td><td><b>69</b></td></tr><tr><td>6.1 CSS stabilizer codes</td><td>69</td></tr><tr><td>6.2 General stabilizer codes</td><td>77</td></tr><tr><td><b>7</b> Cluster state complex from a dynamical code</td><td><b>84</b></td></tr><tr><td><b>8</b> Discussion</td><td><b>95</b></td></tr></tbody></table>

# 1 Introduction

## 1.1 Motivation

Fault-tolerant quantum computing architectures have traditionally been designed in a “static” code-centric approach. In this paradigm, constructing a code, building syndrome extraction circuits, and performing logical operations are treated as separate processes. However, recent advances have shown that it is often beneficial to take a more circuit-centric approach to quantum error correction. For instance, Floquet codes [1–4] have a stabilizer group that evolves through a sequence of non-commuting measurements, making a dynamical description essential. The order of measurements influences both the fault-tolerant properties of the circuit and the logical operation being applied [5]. Similarly, the precise scheduling of gauge measurements of a subsystem code [6–8] can have an impact on the performance of the code [9–12]. Finally, the tools and frameworks developed for analyzing error-correcting circuits have already had a large impact in the field: they have helped design better circuit-level
decoders [13], more efficient syndrome extraction circuits [14–16], and noise reduction methods with less overhead than traditional quantum error-correction [17]. They have also provided new insights into the study of problematic “hook errors” [18].

Several frameworks have been proposed to formally study fault-tolerant circuits. The first, originally proposed by Bacon et al. [19] and more recently revived by Pryadko [20] and Gottesman [21], associates a spacetime subsystem code with any Clifford circuit. In this code, each physical qubit corresponds to a spacetime location in the circuit. Gauge operators are defined for each gate, measurement, and input stabilizer, and represent trivial circuit errors. The stabilizers of this subsystem code are then associated either with redundancies between measurements—often referred to as detectors [22]—or with measurements that become redundant when additional ones are introduced at the beginning or end of the circuit (which can be viewed as incomplete detectors). Given a circuit noise model, the maximum-likelihood decoding problem can also be expressed in terms of this subsystem code [20]. In a related framework proposed by Delfosse and Paetznick [23], spacetime codes are modeled as stabilizer codes, with only the full detectors as stabilizers. Overall, viewing a fault-tolerant circuit as a spacetime code allows to understand the fault-tolerant properties of the circuit in terms of the properties of the code, such as the number of encoded qubits throughout the computation, the fault distance of the circuit (the minimal number of physical errors that leads to a logical error on the output), and the circuit-level decoding problem.

A natural next step in understanding spacetime codes is determining when two are equiv-
alent. In the realm of static codes, studying code equivalence has led to valuable insights. For
instance, defining two code families as equivalent if they are related by a geometrically-local
Clifford unitary operator, it has been shown that *D*-dimensional color codes are equivalent
to *D* copies of the toric code [24–27]. This insight has enabled the construction of color code
decoders based on toric code decoders [28, 29]. More general classifications of quantum code
equivalence classes have recently been developed [30, 31]. Establishing a notion of equivalence
in the context of error-correcting circuits is particularly valuable, as compiling a fault-tolerant
process depends on the hardware architecture: different quantum devices have distinct gate
sets, connectivity constraints, and noise models. Finding a device-tailored compilation that
preserves fault tolerance is therefore a crucial challenge.

As a simple example to understand this, let us consider the **SWAP** gate and its compilation
into three **CNOT** gates:

<figure><img src="image_2.png" /></figure>

While the circuit on the left propagates any single-qubit *X* or *Z* error into a single-qubit
error on the other qubit, the circuit on the right can propagate single-qubit errors occurring
in between the **CNOT** gates into two-qubit errors. If a **SWAP** gate is therefore present in a
fault-tolerant circuit, compiling it into **CNOTs** can lead to a reduction in the fault distance
compared to directly exchanging the qubits. On the other hand, we might want to consider
the two circuits below as equivalent:

<figure><img src="image_3.png" /></figure>

where $M_{XX}$ and represents a two-qubit $XX$ measurements. Indeed, while adding Hadamard gates might increase the probability of errors in between the two measurements, it does not fundamentally change the decoding problem or fault distance of the circuit.

An example of recent progress in understanding equivalent compilations of fault-tolerant processes relates to the problem of “Floquetifying” codes [3, 32–35]. This problem can be formulated as follows: given a family of stabilizer codes, find a sequence of two-qubit measurements such that the resulting Floquet code maintains the same fault-tolerant properties as the original code family. Most progress towards this goal has been made by formulating the problem in ZX-calculus [36, 37] and deriving local diagrammatic rewrite rules that preserve the local structure of detectors and the logical channel action. More recently, Ref. [34] has demonstrated the existence of ZX rewrite rules that preserve the fault distance of the circuit. ZX-calculus has also enabled distance-preserving compilations of surface code circuits optimized for superconducting architectures [14].

Another example of adapting fault-tolerant protocols to specific architectures is the paradigm of measurement-based quantum computing (MBQC), which is particularly relevant to photonic architectures [38–44]. In MBQC, quantum computation is performed by preparing specific resource states, known as *graph states* or *cluster states*, which are then measured in a particular sequence to execute the computation [45–47]. A stabilizer code [48] can be transformed into a cluster state through a process called *foliation* [49, 50], resulting in a measurement-based protocol that acts as a memory channel and preserves the fault-tolerant properties and decoding problem of the original code (in the phenomenological noise model). Foliation was first introduced for the surface code [45], later extended to all CSS codes [49], and more recently generalized to arbitrary stabilizer codes and subsystem codes [50] and certain Floquet codes [51]. Foliation was also recently used to map CSS code error correction circuits to mixed-state phases of (decohered) cluster states [52]. Additionally, fault-tolerant MBQC protocols can be understood by associating a chain complex—called the cluster state complex or fault complex—with the protocol [43, 53, 54], which allows one to consider protocols beyond foliation [53, 55].

While the equivalence between the MBQC and the circuit model of fault-tolerance is well-understood in the context of the surface code—for instance with ZX-calculus [56]—, the more general case has not yet been rigorously proven.

## 1.2 Main results

This work advances the understanding of spacetime codes (viewed as chain complexes) by studying their equivalence under transformations that preserve fault-tolerant properties. Using this understanding, we provide a method to transform any Clifford circuit into an MBQC protocol with equivalent fault-tolerant properties and formulate its decoding problem using cluster state complexes. Specifically, we establish the following:
1. Stabilizer codes, subsystem codes and quantum circuits can all be described using chain complexes. While chain complexes have traditionally been used to construct, analyze, and transform CSS codes—and more recently, cluster states—we show that they can be applied more generally.

2. The equivalence of two spacetime codes can be characterized by a relaxed version of chain maps—that we call *weak chain maps*—between their associated chain complexes. We define a *fault-tolerant map* as a weak chain map that preserves the number of encoded qubits, fault distance, and minimum-weight solution to the decoding problem. We further establish the existence of two specific fault-tolerant maps, which we term reduction rules A and B.

3. Any Clifford circuit composed of single-qubit Clifford gates, controlled Pauli gates (where the Pauli operator may act on multiple qubits), and single-qubit Pauli measurements can be transformed into a measurement-based protocol with equivalent fault-tolerant properties. As examples, we construct cluster states from non-CSS, subsystem, and Floquet codes, as well as from logical Clifford operations on a given code. The decoding problem of these protocols can be represented by a novel cluster state complex, which generalizes previous formulations. Notably, our cluster state complexes can be non-bipartite, incorporate Y measurements, and include input and output nodes.

1.3 Reader's guide

Despite the length of this paper and a certain dependence between sections, some readers could find value in consulting only particular parts. We provide here a few pathways through the paper depending on different readers' interests:

* For a reader only interested in **understanding our chain complex formalism** for representing and manipulating codes beyond CSS stabilizer ones, Section 2 should be sufficient. A reader already familiar with chain complexes might want to jump directly to Example 2.2 and Example 2.3 to learn how they are used to represent non-CSS and subsystem codes, before going to Section 2.4, in which the new notion of fault-tolerant map between complexes is introduced. The particular fault-tolerant maps that we introduce—rules A and B—can be understood graphically from Fig. 3 on a first read, while Section 2.5 and Section 2.6 can be consulted if the formal proof of their properties is of interest.

* A reader mainly interested in **learning about spacetime codes** can start their reading in Section 3, in which we review this formalism while synthesizing previous approaches in the literature [19, 21, 23]. In particular, we show in Section 3.4—and more precisely Proposition 3.1—that the stabilizers of the spacetime code of Delfosse and Paetznick [23] are also stabilizers of the spacetime subsystem code of Bacon et al. [19], which can be obtained through the forward and backward propagations of measurements operators. The link between spacetime codes and chain complexes is only briefly mentioned, and it is therefore not required to have read Section 2 for an overall understanding of this section.

* For a reader interested in **understanding MBQC through the lens of chain complexes**, Section 4 is the most relevant section. Our main object of study, the cluster state
complex, is introduced in Section 4.3 (Definition 4.1) and shown to be equivalent to the spacetime code of the corresponding MQBC circuit in Theorem 4.1. While this construction itself can be read independently from the rest of the paper, its motivation and relation to spacetime codes can only be understood after reading Section 2 and Section 3.

* A reader whose objective is to construct MBQC protocols from Clifford circuits—with the goal of simulating or experimentally realizing them—should first get familiar with spacetime codes by reading through Section 3, and with our MBQC notations by reading through Section 4.1 and Section 4.2. They can then read through Section 5 while skipping the proofs of the different lemmas and propositions. Understanding those proofs require familiarity with the chain complex formalism of Section 2.

* For a reader whose objective is to construct MBQC protocols from non-CSS codes, subsystem codes or dynamical codes, understanding Definition 4.1 and consulting the main theorems of Section 6 or Section 7 should be sufficient. Understanding the proofs requires familiarity with all the preceding sections, and in particular all the lemmas of Section 5.

# 2 Quantum error correction from chain complexes

## 2.1 Notation

To every $n$-qubit Pauli operator $P$, we associate a $2n$-dimensional vector $v(P)$ in the binary symplectic format, where the first $n$ components represent the presence or absence of a Pauli $X$ operator on each qubit, and the last $n$ components the presence or absence of a Pauli $Z$ operator. For instance, the operator $P = X \otimes Y$ can be written as a vector $v(P) = (11|01)$. The symplectic matrix $\Omega$ is defined to be

$$ \Omega = \begin{pmatrix} 0_n & I_n \\ I_n & 0_n \end{pmatrix}, $$

where $0_n$ and $I_n$ are, respectively, the $n \times n$ zero matrix and identity matrix. One can readily check that two Pauli operators $P_1$ and $P_2$ commute if and only if $v(P_1)^T \Omega v(P_2) = 0$, where all operations are performed modulo 2.

## 2.2 Homological quantum error correction

**Definition 2.1 (Chain and cochain complexes).** A length-$\ell$ chain complex is a collection of $\ell + 1$ $\mathbb{F}_2$-vector spaces $C_0, \dots, C_\ell$, together with $\ell$ linear maps, called boundary operators, $\partial_1, \dots, \partial_\ell$, with $\partial_i : C_i \to C_{i-1}$, such that they obey the chain complex condition $\partial_{i-1} \circ \partial_i = 0$ for every $i$. We write a chain complex in the following diagrammatic form:

$$ C_{\ell} \xrightarrow{\partial_{\ell}} C_{\ell-1} \xrightarrow{\partial_{\ell-1}} \dots \xrightarrow{\partial_1} C_0. \qquad (1) $$

We denote such a chain complex by $C_\bullet$. The cochain complex associated to $C_\bullet$ is the collection of vector spaces $C^0, \dots, C^\ell$, where $C^i = \operatorname{Hom}(C_i, \mathbb{Z}_2)$ (the set of homomorphisms from $C_i$ to
$\mathbb{Z}_2$), along with coboundary operators $\partial^1, \dots, \partial^\ell$, with $\partial^i : C^{i-1} \to C^i$ defined as $\partial^i(f) = f \circ \partial_i$. We write it as

$$C^\ell \underset{\partial^\ell}{\stackrel{\partial^\ell}{\rightleftharpoons}} C^{\ell-1} \underset{\partial^{\ell-1}}{\stackrel{\partial^{\ell-1}}{\rightleftharpoons}} \dots \underset{\partial^1}{\stackrel{\partial^1}{\rightleftharpoons}} C^0 \qquad (2)$$

and denote it by $C^\bullet$.

**Remark.** If every space $C_i$ is finite-dimensional, we can identify the spaces $C_i$ and $C^i$. Indeed, for every linear form $f \in C^i$, there exists a unique vector $\tilde{f} \in C_i$ such that $f(x) = \tilde{f}^T x$ for every $x \in C_i$. The map $\psi : f \mapsto \tilde{f}$ is an isomorphism between $C^i$ and $C_i$ which can be written in matrix form as

$$\psi : (a_1 \dots a_n) \in C^1 \mapsto \begin{pmatrix} a_1 \\ \vdots \\ a_n \end{pmatrix} \in C_1. \qquad (3)$$

Every coboundary operator can then be associated with a map $\tilde{\partial}^i = \psi \circ \partial^i \circ \psi^{-1} : C_{i-1} \to C_i$. Writing the boundary and coboundary operators in matrix form, we then have the identity $\tilde{\partial}^i = \partial_i^T$. In the rest of this work, we assume all the chain complexes are defined over finite-dimensional spaces, and we omit the tilde from $\tilde{f}$ and $\tilde{\partial}_i$, implicitly identifying every dual space $C^i$ with $C_i$.

**Definition 2.2 (Cycles and boundaries).** An $i$-th *cycle* of a chain complex $C_\bullet$ is an element of $\ker(\partial_i)$. An $i$-th *boundary* is an element of $\mathrm{Im}(\partial_{i+1})$. Similarly, an $i$-th *cocycle* is an element of $\ker(\partial^{i+1})$, and an $i$-th *coboundary* is an element of $\mathrm{Im}(\partial^i)$.

**Definition 2.3 (Homology and cohomology groups).** The $i$-th homology group of a chain complex $C_\bullet$ (for $0 \le i \le \ell$) is defined by $H_i(C_\bullet) = \ker(\partial_i)/\mathrm{Im}(\partial_{i+1})$. The $i$-th cohomology group is the homology group of the corresponding cochain complex, that is, $H^i(C_\bullet) = H_i(C^\bullet) = \ker(\partial^{i+1})/\mathrm{Im}(\partial^i)$. To resolve the cases $i=0$ and $i=\ell$, we extend the chain complex to the left and right by the zero space and define the corresponding maps $\partial_0$ and $\partial_{\ell+1}$ as zero maps:

$$0 \xrightarrow{\partial_{\ell+1}=0} C_\ell \xrightarrow{\partial_\ell} C_{\ell-1} \xrightarrow{\partial_{\ell-1}} \dots \xrightarrow{\partial_1} C_0 \xrightarrow{\partial_0=0} 0. \qquad (4)$$

For any representative $x$ of $H_i(C_\bullet)$ or $H^i(C_\bullet)$, we denote by $[x]$ its corresponding coset.

As we will soon see, length-2 chain complexes play a special role in quantum error correction. In this context, it will be convenient to have a particular terminology for elements of the first homology and cohomology groups.

**Definition 2.4 (Logical errors and logical correlations).** For any length-2 chain complex

$$C_2 \xrightarrow{\partial_2} C_1 \xrightarrow{\partial_1} C_0 \qquad (5)$$

we call *logical errors* the elements of $H_1(C_\bullet) = \ker(\partial_1)/\mathrm{Im}(\partial_2)$, and *logical correlations* the elements of $H^1(C_\bullet) = \ker(\partial_2^T)/\mathrm{Im}(\partial_1^T)$. We say that a logical error (logical correlation) is *non-trivial* if it is not zero, that is, if its representatives do not belong to $\mathrm{Im}(\partial_2)(\mathrm{Im}(\partial_1^T))$.
A fundamental theorem in homological algebra—the universal coefficient theorem—relates the homology and cohomology groups [53, 57]:

**Theorem 2.1** (Universal coefficient theorem). The linear map $\phi: H^i(C_\bullet) \to \operatorname{Hom}(H_i(C_\bullet), \mathbb{Z}_2)$ defined by $\phi([f])([x]) = f(x)$ is a well-defined isomorphism.

**Corollary 2.1.** The intersection form $\Phi: C^i \times C_i \to \mathbb{Z}_2$ defined as $\Phi(f, x) = f^T x$ is invariant on every coset of $H^i(C_\bullet) \times H_i(C_\bullet)$, that is

$$ \Phi(f, x) = \Phi(f', x') \quad \text{if } [f] = [f'] \quad \text{and} \quad [x] = [x'] \qquad (6) $$

In other words, whether a given cycle and cocycle intersect on an even or odd number of elements only depend on their cosets, not on the specific representatives chosen.

*Proof.* We have $\Phi(f, x) = f^T x = \phi([f])([x])$, where $\phi$ is the map defined in Theorem 2.1. Therefore, $\Phi(f, x)$ only depends on the cosets of $f$ and $x$. $\square$

**Corollary 2.2.** There exists a basis $\{e_j\}$ of $H_i(C_\bullet)$ and $\{e^j\}$ of $H^i(C_\bullet)$ such that for every pair of representatives $x \in e_j$ and $f \in e^k$, we have $\Phi(f, x) = \delta_{jk}$

*Proof.* Let $\{e_j\}$ a basis of $H_i(C_\bullet)$. Let $\{f^j\}$ the dual basis of $H_i(C_\bullet)$, that is, the basis of $\operatorname{Hom}(H_i(C_\bullet), \mathbb{Z}_2)$ such that $f^j(e_k) = \delta_{jk}$ for every $j, k$. Since $\phi$ is an isomorphism, for every $j$ there exists a unique $e^j \in H^i(C_\bullet)$ such that $\phi(e^j) = f^j$. Since an isomorphism sends a basis to a basis, $\{e^j\}$ is itself a basis of $H^i(C_\bullet)$. Moreover, $\Phi(e^j, e_k) = \phi(e^j)(e_k) = f^j(e_k) = \delta_{jk}$. $\square$

In the specific case of length-2 chain complexes, we can interpret the intersection form as the parity of the number of elements in the intersection of a logical error and a logical correlation. Corollary 2.2 then implies that there exists a basis of logical errors and logical correlations, such that every basis logical error intersects non-trivially with a unique basis logical correlation.

We next introduce two properties of length-2 chain complexes, which require fixing a basis of $C_1$ in order to assign a weight to each vector. Specifically, for an $\mathbb{F}_2$-vector space with basis $\{b_i\}$, the weight of a vector $x = \sum_i x_i b_i$ is defined as $|x| = \sum_i x_i$ (where here the $x_i$ are interpreted as integers).

**Definition 2.5** (Distance). The distance $d(C_\bullet)$ of a length-2 chain complex $C_\bullet$, equipped with a basis $\{b_i\}_i$ for $C_1$, is the minimal weight of a non-trivial logical error, that is

$$ d = \min_{e \in \ker(\partial_1) \setminus \operatorname{Im}(\partial_2)} |e| \qquad (7) $$

where $|e| = \sum_i e_i$ when writing $e = \sum_i e_i b_i$.

**Definition 2.6** (Minimum-weight decoding). The minimum-weight decoding (MWD) function of a length-2 chain complex equipped with a basis for $C_1$ is the function $x^* : C_1 \to C_0$ defined as

$$ x^*(s) = \argmin |x| \quad \text{s.t.} \quad \partial_1(x) = s. \qquad (8) $$
**Example 2.1 (CSS code).** Let's consider an n-qubit Calderbank-Shor-Steane (CSS) code [58, 59] defined by the two parity-check matrices $H_X$ and $H_Z$, of dimensions $m_X \times n$ and $m_Z \times n$, respectively. Then the following diagram defines a valid chain complex:

$$S_X \xrightarrow{H_X^T} Q \xrightarrow{H_Z} S_Z, \qquad (9)$$

where $Q = \mathbb{Z}_2^n$, $S_X = \mathbb{Z}_2^{m_X}$ and $S_Z = \mathbb{Z}_2^{m_Z}$. Indeed, the chain complex condition $H_Z H_X^T = 0$ is equivalent to the commutation between all the X and Z stabilizers of the code. Moreover, any length-2 chain complex can be used to define a CSS code, by interpreting the two boundary operators as parity-check matrices for X and Z stabilizers, making it a convenient tool to classify and generate CSS codes. We note that in this chain complex, logical errors (as we defined them above) are only the X logical operators, while logical correlations are the Z logical operators. The intersection property of Corollary 2.2 tells us that there exists a basis of X logical operators $\{\bar{X}_1, \dots, \bar{X}_k\}$ and a basis of Z logical operators $\{\bar{Z}_1, \dots, \bar{Z}_k\}$ such that the intersection between $\bar{X}_i$ and $\bar{Z}_j$ is odd if and only if $i = j$, independently of the representatives chosen. The distance of this chain complex correspond to the X-distance of the CSS code and the minimum-weight decoding function to the decoding of X errors. The asymmetry between X and Z in our definition is resolved when considering a different chain complex formulation of stabilizer codes, which we present in the next example.

**Example 2.2 (Non-CSS code).** While less commonly used in quantum error correction, non-CSS Pauli stabilizer codes [48] can also be written as chain complexes. Let us consider a generic stabilizer code defined by a parity-check matrix $H$ of dimension $m \times 2n$ written in the binary symplectic format. Then the following diagram defines a valid chain complex:

$$S \xrightarrow{H^T} \mathcal{E} \xrightarrow{H_\Omega} S, \qquad (10)$$

where $S = \mathbb{Z}_2^m$, and $\mathcal{E} = \mathbb{Z}_2^{2n}$. Indeed, similarly to the CSS case, the chain complex condition $H_\Omega H^T = 0$ is equivalent to the commutation of the stabilizers. However, contrary to the CSS case, not all length-2 chain complexes define a stabilizer code in this way, as we have the additional constraints that $\partial_1 = \partial_2^T \Omega$ and $\mathcal{E}$ has even dimension.

**Example 2.3 (Subsystem code).** Let us consider an n-qubit Pauli subsystem code [6–8] defined by a gauge matrix $H_G$ of dimension $m_G \times 2n$. We denote its parity-check matrix by $H_S$, which has dimension $m_S \times 2n$. The following diagram then defines a valid chain complex, that we call the gauge complex of the subsystem code:

$$\mathcal{G} \xrightarrow{H_G^T} \mathcal{E} \xrightarrow{H_S \Omega} S, \qquad (11)$$

where $\mathcal{G} = \mathbb{Z}_2^{m_G}$, $S = \mathbb{Z}_2^{m_S}$, $Q$ is a $\mathbb{Z}_2$-vector space of dimension $n$, and $\mathcal{E} = \mathbb{Z}_2^{2n}$. Indeed, the chain complex condition $H_S \Omega H_G^T = 0$ is equivalent to the commutation of gauge operators and stabilizers. Not every chain complex gives rise to a subsystem code, since we have the additional constraints that $C_1$ is even and $\mathrm{Im}(\Omega \partial_0^T) \subset \mathrm{Im}(\partial_1)$ (every stabilizer is itself a gauge operator). Elements of the kernel of $H_S \Omega$ correspond to the undetectable errors of the code. The homology group $\ker(H_S \Omega)/\mathrm{Im}(H_G^T)$ (group of logical errors) of this chain complex corresponds to the dressed logical operators $\mathcal{N}(S)/\mathcal{G}$ of the code, while the cohomology group $\ker(H_G)/\mathrm{Im}(\Omega H_S^T)$ (group of logical correlations) corresponds to the bare logical operators
<figure><img src="image_4.png" /><figcaption>Figure 1: Example of graphical representation of a chain complex. Circles, squares and triangles represent basis elements of $C_2$, $C_1$ and $C_0$ respectively. The connections between circles and squares are specified by the boundary operator $\partial_2$, seen as a biadjacency matrix, while the connections between triangles and squares are specified by $\partial_1$. The chain complex condition $\partial_1 \circ \partial_2 = 0$ can be verified by checking that the neighborhood of any circle intersects with the neighborhood of any triangle on an even number of squares.</figcaption></figure>

$N(\mathcal{G})/S$. Notably, we can specialize this definition to CSS subsystem and stabilizer codes [60]. For a CSS subsystem code, all the spaces and maps split into X and Z parts:

$$ \mathcal{G}_X \oplus \mathcal{G}_Z \xrightarrow{\frac{(H_G^X)^T \oplus (H_G^Z)^T}{(H_S^Z \oplus H_S^X)}} \mathcal{Q} \oplus \mathcal{Q} \xrightarrow{\frac{H_S^Z}{H_S^X}} \mathcal{S}_Z \oplus \mathcal{S}_X, \quad (12) $$

which is the direct sum of the two complexes

$$ \mathcal{G}_X \xrightarrow{\frac{(H_G^X)^T}{(H_S^Z \oplus H_S^X)}} \mathcal{Q} \xrightarrow{\frac{H_S^Z}{H_S^X}} \mathcal{S}_Z \quad (13) $$

and

$$ \mathcal{G}_Z \xrightarrow{\frac{(H_G^Z)^T}{(H_S^X \oplus H_S^Z)}} \mathcal{Q} \xrightarrow{\frac{H_S^X}{H_S^Z}} \mathcal{S}_X. \quad (14) $$

In the special case of a CSS stabilizer code, where $\mathcal{G}_X = \mathcal{S}_X$ and $\mathcal{G}_Z = \mathcal{S}_Z$, we recover two copies of the usual chain complex for CSS codes:

$$ \mathcal{S}_X \xrightarrow{\frac{(H_S^X)^T}{(H_S^Z \oplus H_S^X)}} \mathcal{Q} \xrightarrow{\frac{H_S^Z}{H_S^X}} \mathcal{S}_Z \quad (15) $$

and

$$ \mathcal{S}_Z \xrightarrow{\frac{(H_S^Z)^T}{(H_S^X \oplus H_S^Z)}} \mathcal{Q} \xrightarrow{\frac{H_S^X}{H_S^Z}} \mathcal{S}_X. \quad (16) $$

## 2.3 Graphical representation of a chain complex

Let us consider a length-2 chain complex

$$ C_2 \xrightarrow{\partial_2} C_1 \xrightarrow{\partial_1} C_0, \quad (17) $$

where $C_2$, $C_1$ and $C_0$ have respective dimensions $n_2$, $n_1$ and $n_0$. We also equip each of the three spaces with a basis. The boundary operators $\partial_1$ and $\partial_2$ can then be represented as matrices of dimension $n_1 \times n_0$ and $n_2 \times n_1$, respectively. Interpreting $\partial_1$ as the biadjacency matrix of a graph with $n_1$ nodes of type $C_1$ (one for each basis element of $C_1$) and $n_0$ nodes of type $C_0$, and $\partial_2$ as the biadjacency matrix of a graph with $n_2$ nodes of type $C_2$ and $n_1$ nodes of type $C_1$, we can represent the chain complex as a graph with three types of nodes.
<figure><img src="image_5.png" /><figcaption>Figure 2: Gauge complex and reduced gauge complex of the Bacon-Shor code [61]. (a) Bacon-Shor code on a 4 × 4 grid with qubits on vertices. Vertical and horizontal edges represent X and Z gauge operators, respectively. The X stabilizers and Z stabilizers can be generated by pairs of rows and columns, respectively. (b) Gauge complex associated to those gauge and stabilizer generators. (c) The reduced gauge complex: using rule A, we can merge all the Z nodes in the same row, and all the X nodes in the same column, showing the equivalence of the Bacon-Shor code decoding problem to that of two repetition codes.</figcaption></figure>

The edges between nodes of type $C_2$ and $C_1$ are specified by the matrix $\partial_2$, the edges between nodes of type $C_1$ and $C_0$ are specified by the matrix $\partial_1$, etc. We will always represent nodes of type $C_2$ by circles, nodes of type $C_1$ by squares, and nodes of type $C_0$ by triangles. An example of such chain complex representation is shown in Fig. 1.

In the case that our chain complex represents a subsystem code

$$ \mathcal{G} \xrightarrow{H_G^T} \mathcal{E} \xrightarrow{H_S \Omega} \mathcal{S} \qquad (18) $$

we can moreover split the nodes of type $\mathcal{E}$ into X and Z type, each node representing a single-qubit X or Z error at a certain location. We call the nodes of type $\mathcal{G}$ gauge nodes, the nodes of type $\mathcal{E}$ error nodes, and the nodes of type $\mathcal{S}$ detector nodes. Note that due to the $\Omega$ matrix in the definition of $\partial_1$, detector nodes are connected to opposite Pauli error nodes in the graph than in their definition: a stabilizer $S = X_1Z_2$ is represented by a triangular node connected to square nodes $Z_1$ and $X_2$. An example of gauge complex, corresponding to the Bacon-Shor code [61], is shown in Fig. 2b.

## 2.4 Fault-tolerant maps

We would now like to develop a notion of equivalence between chain complexes, such that two chain complexes are equivalent if they have the same distance and number of logical cosets, and if the minimum-weight decoding function of one chain complex can be mapped to the minimum-weight decoding function of any other chain complex in the equivalence class.

A natural way to transform a chain complex while preserving its structure is to use a chain map. A chain map $f: C_\bullet \to C'_\bullet$ between two length-2 chain complexes

$$ C_2 \xrightarrow{\partial_2} C_1 \xrightarrow{\partial_1} C_0 $$

and

$$ C'_2 \xrightarrow{\partial'_2} C'_1 \xrightarrow{\partial'_1} C'_0 $$
is a triple of linear maps ($f_0, f_1, f_2$) with $f_i : C_i \to C'_i$ for $i \in \{0, 1, 2\}$, such that the diagram

$$ \begin{tikzcd} C_2 \arrow[r, "\partial_2"] \arrow[d, "f_2"] & C_1 \arrow[r, "\partial_1"] \arrow[d, "f_1"] & C_0 \arrow[d, "f_0"] \\ C'_2 \arrow[r, "\partial'_2"] & C'_1 \arrow[r, "\partial'_1"] & C'_0 \end{tikzcd} \qquad (19) $$

commutes, that is, $f_1 \circ \partial_2 = \partial'_2 \circ f_2$ and $f_0 \circ \partial_1 = \partial'_1 \circ f_1$. It can be shown that chain maps preserve cycles (elements of $\ker \partial_1$) and boundaries (elements of $\mathrm{Im} \partial_0$). Moreover, any chain map $f : C_\bullet \to C'_\bullet$ induces a well-defined map $f^* : H_1(C_\bullet) \to H_1(C'_\bullet)$ on the homology groups. We note that chain maps preserving the properties of CSS codes have been studied previously in the context of decoding topological codes [28, 29, 62].

However, the commutation requirement of chain maps is too strong for our purpose: we will soon present some examples of maps that preserve the desired properties of our complex without making the diagram above commute. We introduce here a weaker notion of chain maps, which still induces a well-defined map on the homology groups and preserves enough structure to make distance and decoding preservation possible.

**Definition 2.7 (Weak chain map).** A weak chain map $f : C_\bullet \to C'_\bullet$ between two length-2 chain complexes

$$ C_2 \xrightarrow{\partial_2} C_1 \xrightarrow{\partial_1} C_0 $$

and

$$ C'_2 \xrightarrow{\partial'_2} C'_1 \xrightarrow{\partial'_1} C'_0 $$

is a triple of linear maps ($f_0, f_1, f_2$) with $f_i : C_i \to C'_i$ for $i \in \{0, 1, 2\}$, such that $\mathrm{Im}(f_1 \circ \partial_2) \subset \mathrm{Im}(\partial'_2)$ and $f_0 \circ \partial_1 = \partial'_1 \circ f_1$.

We note that chain maps are particular instances of weak chain maps, since if $f$ is a chain map, we have $\mathrm{Im}(f_1 \circ \partial_2) = \mathrm{Im}(\partial'_2 \circ f_2) \subset \mathrm{Im}(\partial'_2)$. We now show that weak chain maps also induce well-defined maps at the homology level.

**Theorem 2.2.** A weak chain map $f : C_\bullet \to C'_\bullet$ induces a map $f^* : H_1(C_\bullet) \to H_1(C'_\bullet)$ defined as $f^*([x]) = [f_1(x)]$ for any $x \in \ker(\partial_1)$. This map is well-defined, that is, $f_1(x) \in \ker(\partial'_1)$ for all $x \in \ker(\partial_1)$, and $[f_1(x_1)] = [f_1(x_2)]$ for all $x_1, x_2 \in \ker(\partial_1)$ such that $[x_1] = [x_2]$.

*Proof.* Let us start by showing that $f_1$ maps cycles to cycles. Let $x \in \ker(\partial_1)$. Then $\partial'_1(f_1(x)) = f_0(\partial_1(x)) = 0$. Therefore, $f_1(x) \in \ker(\partial'_1)$.

Let us now show that the coset of $f_1(x)$ only depends on the coset of $x$. Let $x_1, x_2 \in \ker(\partial_1)$ such that $[x_1] = [x_2]$. Then $f_1(x_1) + f_1(x_2) = f_1(x_1 + x_2)$. Since $[x_1 + x_2] = 0$, we must have $x_1 + x_2 \in \mathrm{Im}(\partial_2)$. Therefore, there exists $y \in C_2$ such that $x_1 + x_2 = \partial_2(y)$. Hence, $f_1(x_1 + x_2) = f_1(\partial_2(y)) \in \mathrm{Im}(\partial'_2)$ by the definition of a weak chain map. Therefore, $[f_1(x_1) + f_1(x_2)] = 0$, that is, $[f_1(x_1)] = [f_1(x_2)]$. $\square$

We are particularly interested in the case where the induced map $f^*$ is an isomorphism, that is, a one-to-one map from logical errors of one chain complex to logical errors of the other chain complex. A chain map that is not necessarily an isomorphism, but whose induced map is, is called a *quasi-isomorphism*. We generalize this notion for weak chain maps.
<figure><img src="image_6.png" /><figcaption>Figure 3: Reduction rules A and B. Interpreting the represented chain complex as a CSS code, we can see that rule A corresponds to merging the two qubits in the support of a weight-two X stabilizer, while rule B corresponds to removing a qubit in the support of a weight-one X stabilizer.</figcaption></figure>

**Definition 2.8 (Weak quasi-isomorphism).** A weak quasi-isomorphism is a weak chain map $f$ such that the induced map $f^*$ is a group isomorphism.

For the purpose of this work, we would also like our chain maps to preserve the distance and decoding function of the chain complexes.

**Definition 2.9 (Distance-preserving map).** A weak chain map $f: C_{\bullet} \to C'_{\bullet}$ is said to be distance-preserving if $d(C_{\bullet}) = d(C'_{\bullet})$.

**Definition 2.10 (Decoding-preserving map).** A weak chain map $f: C_{\bullet} \to C'_{\bullet}$ is said to be decoding-preserving if the minimum-weight decoding functions $x^*$ and $x'^*$ of $C_{\bullet}$ and $C'_{\bullet}$ are related by $f_1 \circ x^* = x'^* \circ f_0$.

We can finally define our notion of fault-tolerant map:

**Definition 2.11 (Fault-tolerant map).** A weak chain map is called fault-tolerant if it is a distance-preserving and decoding-preserving weak quasi-isomorphism.

This notion allows us to define an equivalence class of chain complex as follows.

**Definition 2.12 (Equivalence of chain complexes).** Two chain complexes $C_{\bullet}$ and $C'_{\bullet}$ are equivalent if there exists a fault-tolerant map $f: C_{\bullet} \to C'_{\bullet}$ and a fault-tolerant map $g: C'_{\bullet} \to C_{\bullet}$.

We now introduce two specific fault-tolerant maps, called reduction rules A and B.

## 2.5 Rule A

Rule A is represented graphically in Fig. 3a. To describe it, let us consider a chain complex

$$C_2 \xrightarrow{\partial_2} C_1 \xrightarrow{\partial_1} C_0$$

along with bases $s_1, \dots, s_{n_0}$ for $C_0$, $e_1, \dots, e_{n_1}$ for $C_1$ and $g_1, \dots, g_{n_2}$ for $C_2$. To apply the rule, we assume the existence of a node of type $C_2$ only connected to two nodes of type $C_1$. Without loss of generality, we assume that the node of type $C_2$ is $g_{n_2}$ and the two nodes of type $C_1$ are $e_{n_1-1}$ and $e_{n_1}$, that is, $\partial_2(g_{n_2}) = e_{n_1-1} + e_{n_1}$. Rule A then consists of removing $g_{n_2}$ and merging $e_{n_1-1}$ and $e_{n_1}$. More precisely, it is a pair of linear maps $(f_A, h_A)$ with $f_A: C_{\bullet} : C'_{\bullet}$ and $h_A: C_{\bullet} : C'_{\bullet}$, where $C'_{\bullet}$ is defined as follows:

* $C'_2$ has dimension $n_2 - 1$ and is generated by a basis $g'_1, \dots, g'_{n_2-1}$,
• $C'_1$ has dimension $n_1 - 1$ and is generated by a basis $e'_1, \dots, e'_{n_1-1}$,

• $C'_0 = C_0$,

• The boundary operators transform the following way:

$$ \partial_2 = e_{n_1-2} \left( \begin{array}{c|c} e_1 & g_{n_2-1} \\ \vdots & \vdots \\ \tilde{\partial}_2 & 0 \\ \hline e_{n_1-1} & a \\ e_{n_1} & b \end{array} \right) \quad \mapsto \quad \partial'_2 = e'_{n_1-2} \left( \begin{array}{c|c} e'_1 & g'_{n_2-1} \\ \vdots & \vdots \\ \tilde{\partial}_2 & 0 \\ \hline e'_{n_1-1} & a+b \end{array} \right), \quad (20) $$

$$ \partial_1 = \underset{s_{n_0}}{s_1} \left( \begin{array}{c|c} e_1 & \cdots e_{n_1-2} \\ \tilde{\partial}_1 & c \end{array} \right) \quad \mapsto \quad \partial'_1 = \underset{s'_{n_0}}{s'_1} \left( \begin{array}{c|c} e'_1 & \cdots e'_{n_1-2} \\ \tilde{\partial}_1 & c \end{array} \right). \quad (21) $$

Note that $\partial_1$ can be written this way because if a node $s_i$ is connected to $e_{n_1-1}$, it must also be connected to $e_{n_1}$ for the chain complex condition to be valid (otherwise, $s_i$ and $g_{n_2}$ would have a neighborhood overlapping on an odd number of elements).

The map $f_A = (f_0, f_1, f_2)$ is defined as follows:

• $f_2(g_{n_2}) = 0$ and $f_2(g_i) = g'_i$ for all $i \le n_2 - 1$, In matrix form:

$$ f_2 = \underset{g'_{n_2-1}}{g'_1} \left( \begin{array}{c|c} g_1 & \cdots g_{n_2-1} \\ I_{n_2-1} & 0 \\ \vdots & \vdots \\ 0 & 0 \end{array} \right), \quad (22) $$

• $f_1(e_{n_1}) = e'_{n_1-1}$ and $f_1(e_i) = e'_i$ for all $i \le n_1 - 1$, In matrix form:

$$ f_1 = \underset{e'_{n_1-2}}{e'_1} \left( \begin{array}{c|c} e_1 & \cdots e_{n_1-1} \\ I_{n_1-1} & 0 \\ \vdots & \vdots \\ 0 & 1 \end{array} \right), \quad (23) $$

• $f_0(s_i) = s'_i$ for all $i \le n_0$,

and the map $h_A = (h_0, h_1, h_2)$ is defined as follows:

• $h_2(g'_i) = g_i$ for all $i \le n_2 - 1$. In matrix form:

$$ h_2 = \underset{g_{n_2-1}}{g_1} \left( \begin{array}{c|c} g'_1 & g'_{n_2-1} \\ I_{n_2-1} & 0 \\ \vdots & \vdots \\ 0 & 0 \end{array} \right), \quad (24) $$
• $h_1(e'_i) = e_i$ for all $i \le n_1 - 1$. In matrix form:

$$h_1 = \begin{pmatrix} e'_1 & \cdots & e'_{n_1-1} \\ \vdots & & \vdots \\ e_{n_1-1} & & e_{n_1} \\ & & \mathbf{I}_{n_1-1} \\ & & 0 \end{pmatrix}, \qquad (25)$$

• $h_0(s'_i) = s_i$ for all $i \le n_0$.

To prove that $f_A$ is a fault-tolerant map, we will need the following two lemmas:

**Lemma 2.1.** Let $f: C_{\bullet} \to C'_{\bullet}$ and $h: C'_{\bullet} \to C_{\bullet}$ be two weak chain maps between length-2 chain complexes $C_{\bullet}$ and $C'_{\bullet}$ such that $[f_1(h_1(x))] = [x]$ for all $x \in C'_1$, and $[h_1(f_1(x))] = [x]$ for all $x \in C_1$. Then $f$ and $h$ are both weak quasi-isomorphisms, and we have $f^{*} \circ h^{*} = \text{id}_{H_1(C'_{\bullet})}$ and $h^{*} \circ f^{*} = \text{id}_{H_1(C_{\bullet})}$.

*Proof.* Let $x \in C'_1$. We have $f^{*}(h^{*}([x])) = [f_1(h_1(x))] = [x]$. Therefore, $f^{*} \circ h^{*}$ is the identity on $H_1(C'_{\bullet})$. Similarly, for $x \in C_1$, we have $h^{*}(f^{*}([x])) = [h_1(f_1(x))] = [x]$, which shows that $h^{*} \circ f^{*}$ is the identity on $H_1(C_{\bullet})$. Thus, $f^{*}$ and $h^{*}$ are both isomorphisms, and therefore $f$ and $h$ are weak quasi-isomorphisms. $\square$

**Lemma 2.2.** Let $f: C_{\bullet} \to C'_{\bullet}$ and $h: C'_{\bullet} \to C_{\bullet}$ be two weak chain maps between length-2 chain complexes $C_{\bullet}$ and $C'_{\bullet}$ such that

• $f_0 \circ h_0 = \text{id}_{C'_1}$ and $h_0 \circ f_0 = \text{id}_{C_1}$,

• $f_1$ preserves the weight of any minimal-weight logical error,

• $f_1$ and $h_1$ are weight-nonincreasing, i.e. $|f_1(x)| \le |x|$ for every $x \in C_1$ and $|h_1(x)| \le |x|$ for every $x \in C'_1$.

Then $f$ and $h$ are both distance-preserving and decoding-preserving.

*Proof.* We start by showing that $f$ is decoding-preserving. Let $s \in \text{Im}(\partial_1)$. We need to show that $f_1(x^*(s)) = x^*(f_0(s))$, or in other words, that $f_1(x^*(s))$ is the minimum-weight element $x' \in C'_1$ such that $\partial'_1(x') = f_0(s)$. Let us start by showing that the constraint $\partial'_1(x') = f_0(s)$ is fulfilled:

$$\partial'_1(f_1(x^*(s))) = f_0(\partial_1(x^*(s))) = f_0(s). \qquad (26)$$

We then need to show that $f_1(x^*(s))$ is the minimum-weight element of $C'_1$ satisfying this constraint. We prove this by contradiction. Let $y \in C'_1$ satisfying $\partial'_1(y) = f_0(s)$ and $|y| < |f_1(x^*(s))|$. Using the weight-nonincreasing properties of $f_1$ and $h_1$, we get the series of inequalities:

$$|h_1(y)| \le |y| < |f_1(x^*(s))| \le |x^*(s)|. \qquad (27)$$

Moreover, $\partial_1(h_1(y)) = h_0(\partial'_1(y)) = h_0(f_0(s)) = s$. Therefore, $h_1(y)$ is an element of $C_1$ satisfying the syndrome constraint with a lower weight than $|x^*(s)|$, which contradicts the
definition of $x^*(s)$. Thus, $f_1(x^*(s))$ is the minimum-weight element of $C'_1$ satisfying the constraint, and $f$ is decoding-preserving. The same proof with $f$ and $h$ switched allows us to show that $h$ is decoding-preserving as well.

We now show that $f$ and $h$ are distance-preserving, meaning that $C_\bullet$ and $C'_\bullet$ have the same distance. Let $x \in C_1$ be a minimal-weight non-trivial logical error. By applying the proof above to $s = 0$, we can see that $f_1(x)$ is a minimum-weight logical error in $C'_\bullet$. Moreover, since $f$ is a weak chain map, Theorem 2.2 shows that it maps non-trivial logical errors to non-trivial logical errors. Therefore, $f_1(x)$ is a minimum-weight non-trivial logical error of $C'_\bullet$. Since by assumption, $|f_1(x)| = |x|$, we have $d(C'_\bullet) = d(C_\bullet)$. Therefore, both $f$ and $h$ are distance-preserving. $\square$

**Theorem 2.3.** $f_A$ and $h_A$ are fault-tolerant maps

*Proof.* We start by proving that $f_A$ and $h_A$ are weak chain maps. We first show that the diagram for $f_A$,

$$ \begin{array}{ccc} C_2 & \xrightarrow{\partial_2} & C_1 \\ \downarrow & & \downarrow \\ C'_2 & \xrightarrow{\partial'_2} & C'_1 \end{array} \xrightarrow{\partial_1} \begin{array}{ccc} C_0 & & \\ & f_1 & \\ & & f_0 \end{array} $$

commutes, making $f_A$ a chain map, and therefore a weak chain map. We can prove this by multiplying the matrices of the different operators involved:

$$ f_1 \circ \partial_2 = \partial'_2 \circ f_2 = \begin{pmatrix} \tilde{\partial}_2 & 0 \\ \vdots & \vdots \\ a+b & 0 \end{pmatrix}, \qquad (28) $$

$$ f_0 \circ \partial_1 = \partial'_1 \circ f_1 = (\tilde{\partial}_1 \ c \ c). \qquad (29) $$

Similarly, we show that the right square of the diagram for $h_A$,

$$ \begin{array}{ccc} C'_2 & \xrightarrow{\partial'_2} & C'_1 \\ \downarrow & & \downarrow \\ C_2 & \xrightarrow{\partial_2} & C_1 \end{array} \xrightarrow{\partial_1} \begin{array}{ccc} C'_0 & & \\ & h_1 & \\ & & h_0 \end{array} $$

commutes, using matrix multiplication:

$$ h_0 \circ \partial'_1 = \partial_1 \circ h_1 = (\tilde{\partial}_1 \ c). \qquad (30) $$

Moreover, for the left square, we have

$$ h_1 \circ \partial'_2 = \begin{pmatrix} \tilde{\partial}_2 \\ a+b \\ 0 \end{pmatrix}. \qquad (31) $$
Applying it to any $x \in C'_2$, we obtain

$$h_1(\partial'_2(x)) = \begin{pmatrix} \tilde{\partial}_2 x \\ (a+b)^T x \\ 0 \end{pmatrix}. \qquad (32)$$

Every element in the image of $\partial_2$ can be written as

$$\partial_2 \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} \tilde{\partial}_2 x \\ a^T x + y \\ b^T x + y \end{pmatrix}, \qquad (33)$$

where $x \in \mathbb{Z}_2^{n_2-1}$ and $y \in \mathbb{Z}_2$. Choosing $y = b^T x$, we obtain

$$\partial_2 \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} \tilde{\partial}_2 x \\ a^T x + b^T x \\ b^T x + b^T x \end{pmatrix} = \begin{pmatrix} \tilde{\partial}_2 x \\ (a+b)^T x \\ 0 \end{pmatrix}. \qquad (34)$$

Therefore, $h_1(\partial'_2(x)) \in \mathrm{Im}(\partial_2)$ for all $x \in C'_2$, and $h$ is a weak chain map.

We now show using Lemma 2.1 that $f$ and $h$ are both weak quasi-isomorphisms. Let us calculate $f_1 \circ h_1$ and $h_1 \circ f_1$ in matrix form:

$$f_1 \circ h_1 = I_{n_1-1}, \qquad (35)$$

$$h_1 \circ f_1 = \begin{pmatrix} I_{n_1-1} & \begin{vmatrix} 0 \\ \vdots \\ 0 \\ 1 \\ 0 \end{vmatrix} \\ \hline 0 \end{pmatrix} = I_{n_1} + \begin{pmatrix} 0 & \begin{vmatrix} 0 \\ \vdots \\ 0 \\ 1 \\ 1 \end{vmatrix} \end{pmatrix}. \qquad (36)$$

Applying $h_1 \circ f_1$ to any $x \in C_1$, we obtain

$$h_1(f_1(x)) = x + \begin{pmatrix} 0 \\ \vdots \\ 0 \\ x_{n_1} \\ x_{n_1} \end{pmatrix} = x + x_{n_1}(e_{n_1-1} + e_{n_1}) = x + x_{n_1} \partial_2(g_{n_2}), \qquad (37)$$

where $x_{n_1} = x \cdot e_{n_1}$. Therefore, $h_1(f_1(x)) \in x + \mathrm{Im}(\partial_2)$, and $[h_1(f_1(x))] = [x]$. Moreover, since $f_1(h_1(x')) = x'$ for all $x' \in C'_1$, we also have $[f_1(h_1(x'))] = [x']$. By Lemma 2.1, we can conclude that $f_A$ and $h_A$ are both weak quasi-isomorphisms.

It remains to show that $f_A$ and $h_A$ are distance- and decoding-preserving. For this, we show that the three conditions of Lemma 2.2 are satisfied. Let us start with the first one. For every basis element $s_i$ of $C_0$ and $s'_j$ of $C'_0$, we have

$$h_0(f_0(s_i)) = h_0(s'_i) = s_i, \qquad (38)$$

$$f_0(h_0(s'_j)) = f_0(s_j) = s_j. \qquad (39)$$
Therefore, $h_0$ and $f_0$ are inverses of each other.

To see that $f_1(x)$ has the same weight as $x$ if $x \in C_1$ is a minimum-weight logical error, let us consider four cases: $x$ is supported on (1) both $e_{n_1}$ and $e_{n_{1-1}}$, (2) $e_{n_1}$ but not $e_{n_{1-1}}$ (3) $e_{n_{1-1}}$ but not $e_{n_1}$, (4) neither $e_{n_1}$ nor $e_{n_{1-1}}$. We can see that the first case is not possible since $x + e_{n_1} + e_{n_{1-1}} = x + \partial_2(g_{n_2})$ would then be another non-trivial logical error with a weight reduced by two. In the second case, since $f_1(e_{n_1}) = e_{n_{1-1}}$ while all the other nodes remain unchanged, $f_1$ preserves the weight of $x$. In the third and fourth case, $f_1$ acts as an identity on all the nodes in the support of $x$, and it therefore preserves its weight as well.

Finally, we show that $f_1$ and $h_1$ are weight-nonincreasing. Let $x' \in C'_1$ such that $x' = \sum_i x'_i e'_i$. We have

$$h_1(x') = \sum_{i=1}^{n_1-1} x'_i h_1(e'_i) = \sum_{i=1}^{n_1-1} x'_i e_i. \quad (40)$$

Therefore,

$$|h_1(x')| = \sum_{i=1}^{n_1-1} x'_i = |x'|, \quad (41)$$

where in this equation the $x'_i$ are interpreted as integers. Thus, $h_1$ is weight-preserving, and therefore weight-nonincreasing.

Let $x \in C_1$ such that $x = \sum_i x_i e_i$. We have:

$$f_1(x) = \sum_{i=1}^{n_1} x_i f_1(e_i) = (x_{n_1-1} + x_{n_1}) e'_{n_1} + \sum_{i=1}^{n_1-2} x_i e'_i, \quad (42)$$

Therefore,

$$|f_1(x)| = \sum_{i=1}^{n_1-2} x'_i + (x_{n_1-1} + x_{n_1} \mod 2). \quad (43)$$

Since

$$(x_{n_1-1} + x_{n_1} \mod 2) \le x_{n_1-1} + x_{n_1}, \quad (44)$$

we have that $|f_1(x)| \le |x|$ and $f_1$ is weight-nonincreasing.

We finally apply Lemma 2.2 to conclude that $f_A$ and $h_A$ are distance- and decoding-preserving. $\square$

As an application of rule A, we show in Fig. 2c that the gauge complex of the Bacon-Shor code can be reduced to two connected components, where each component can be seen as the Tanner graph of a classical repetition code (one for $X$ errors and one for $Z$ errors). This is a new proof of the well-known fact that decoding the Bacon-Shor code is equivalent to decoding two repetition codes [63].
## 2.6 Rule B

We now move on to the description of rule B. We assume the existence of a node of type $C_2$ connected to only one node of type $C_1$. Without loss of generality, we assume that the node of type $C_2$ is $g_{n_2}$ and the node of type $C_1$ is $e_{n_1}$, that is, $\partial_2(g_{n_2}) = e_{n_1}$. Rule B then consists of removing $g_{n_2}$ and $e_{n_1}$. More precisely, it is described by a pair of linear maps $(f_B, h_B)$ between the original chain complex $C_\bullet$ and a new chain complex $C'_\bullet$ defined in the following way:

* $C'_2$ has dimension $n_2 - 1$ and is generated by a basis $g'_1, \dots, g'_{n_2-1}$

* $C'_1$ has dimension $n_1 - 1$ and is generated by a basis $e'_1, \dots, e'_{n_1-1}$

* $C'_0 = C_0$

* The boundary operators $\partial'_1$ and $\partial'_2$ are defined by removing all the edges connected to $g_{n_2}$ and $e_{n_1}$ in the original boundary operators $\partial_1$ and $\partial_2$. More precisely, writing down the transformation in matrix form, we have:

$$ \partial_2 = \begin{array}{c} \begin{array}{c} e_1 \\ \vdots \\ e_{n_1-1} \\ e_{n_1} \end{array} \\ \left( \begin{array}{c|c} g_1 \cdots g_{n_2-1} & g_{n_2} \\ \hline \tilde{\partial}_2 & 0 \\ \hline & \vdots \\ & 0 \\ \hline & 1 \end{array} \right) \end{array} \quad \mapsto \quad \partial'_2 = \tilde{\partial}_2, \qquad (45) $$

$$ \partial_1 = \begin{array}{c} \begin{array}{c} e_1 \cdots e_{n_1-1} \\ s_1 \\ \vdots \\ s_{n_0} \end{array} \\ \left( \begin{array}{c|c} e_{n_1} & 0 \\ \hline \tilde{\partial}_1 & \vdots \\ \hline & 0 \end{array} \right) \end{array} \quad \mapsto \quad \partial'_1 = \tilde{\partial}_1. \qquad (46) $$

Note that $\partial_1$ must have this form for the chain complex condition to be valid. Indeed, suppose that there existed a node $s_i \in C_0$ such that $\partial_1^T s_i = e_{n_1} + \dots$. Then, the overlap with the neighbourhood of $g_{n_2}$, $\partial_2(g_{n_2}) = e_{n_1}$, would be exactly $e_{n_1}$ and hence $\partial_2^T \partial_1^T s_i \neq 0$. This is why no triangle is connected to the square in Fig. 3b.

The map $f_B = (f_0, f_1, f_2)$ is defined as follows:

* $f_2(g_{n_2}) = 0$ and $f_2(g_i) = g'_i$ for all $i \le n_2 - 1$. Or in matrix form:

$$ f_2 = \begin{array}{c} \begin{array}{c} g_1 \cdots g_{n_2-1} \\ g'_1 \\ \vdots \\ g'_{n_2-1} \end{array} \\ \left( \begin{array}{c|c} I_{n_2-1} & 0 \\ \hline & \vdots \\ & 0 \end{array} \right), \end{array} \qquad (47) $$

* $f_1(e_{n_1}) = 0$ and $f_1(e_i) = e'_i$ for all $i \le n_1 - 1$. Or in matrix form:

$$ f_1 = \begin{array}{c} \begin{array}{c} e_1 \cdots e_{n_1-1} \\ e'_1 \\ \vdots \\ e'_{n_1-1} \end{array} \\ \left( \begin{array}{c|c} e_{n_1} & 0 \\ \hline I_{n_1-1} & \vdots \\ \hline & 0 \end{array} \right), \end{array} \qquad (48) $$
• $f_0$ is the identity map on $C_0$

and the map $h_B = (h_0, h_1, h_2)$ is defined as follows:

• $h_2(g'_i) = g_i$ for all $i \le n_2 - 1$. In matrix form:

$$h_2 = \begin{array}{c} \begin{array}{cccc} g'_1 & \cdots & g'_{n_2-1} & \\ \vdots & & \vdots & \\ g_{n_2-1} & & I_{n_2-1} & \\ g_{n_2} & & & 0 \end{array} \\ \hline \end{array}, \qquad (49)$$

• $h_1(e'_i) = e_i$ for all $i \le n_1 - 1$. In matrix form:

$$h_1 = \begin{array}{c} \begin{array}{cccc} e'_1 & \cdots & e'_{n_1-1} & \\ \vdots & & \vdots & \\ e_{n_1-1} & & I_{n_1-1} & \\ e_{n_1} & & & 0 \end{array} \\ \hline \end{array}, \qquad (50)$$

• $h_0(s'_i) = s_i$ for all $i \le n_0$.

Let us now show that $f_B$ and $h_B$ are fault-tolerant maps.

**Theorem 2.4.** $f_B$ and $h_B$ are fault-tolerant maps

*Proof.* We start by proving that $f_B$ and $h_B$ are weak chain maps. We first show that the diagram for $f_B$,

$$\begin{array}{ccc} C_2 & \xrightarrow{\partial_2} & C_1 \\ \cline{2-3} f_2 & & f_1 \\ \cline{2-3} C'_2 & \xrightarrow{\partial'_2} & C'_1 \\ \cline{2-3} & & C'_0 \end{array} \qquad \begin{array}{ccc} \partial_1 & & \partial_0 \\ \hline C_2 & & C_1 \\ \cline{2-3} C'_2 & & C'_1 \\ \cline{2-3} & & C'_0 \end{array}$$

commutes. We can prove this by multiplying the matrices of the different operators involved:

$$f_1 \circ \partial_2 = \partial'_2 \circ f_2 = (\tilde{\partial}_2 | 0), \qquad (51)$$

$$f_0 \circ \partial_1 = \partial'_1 \circ f_1 = \partial_1. \qquad (52)$$

Similarly, we show that right square of the diagram for $h_B$,

$$\begin{array}{ccc} C'_2 & \xrightarrow{\partial'_2} & C'_1 \\ \cline{2-3} h_2 & & h_1 \\ \cline{2-3} C_2 & \xrightarrow{\partial_2} & C_1 \\ \cline{2-3} & & C_0 \end{array} \qquad \begin{array}{ccc} \partial'_1 & & \partial'_0 \\ \hline C'_2 & & C'_1 \\ \cline{2-3} C'_2 & & C'_0 \end{array}$$

commutes, using matrix multiplication:

$$h_0 \circ \partial'_1 = \partial_1 \circ h_1 = \tilde{\partial}_1. \qquad (53)$$
Moreover, we have on the left square:

$$h_1 \circ \partial'_2 = \begin{pmatrix} \tilde{\partial}_2 \\ 0 \end{pmatrix}. \qquad (54)$$

Applying it to any $x \in C'_2$, we obtain:

$$h_1(\partial'_2(x)) = \begin{pmatrix} \tilde{\partial}_2 x \\ 0 \end{pmatrix}. \qquad (55)$$

Every element in the image of $\partial_2$ can be written as:

$$\partial_2 \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} \tilde{\partial}_2 x \\ a^T x + y \end{pmatrix}. \qquad (56)$$

where $x \in \mathbb{Z}_2^{n_2-1}$ and $y \in \mathbb{Z}_2$. Choosing $y = a^T x$, we obtain:

$$\partial_2 \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} \tilde{\partial}_2 x \\ a^T x + a^T y \end{pmatrix} = \begin{pmatrix} \tilde{\partial}_2 x \\ 0 \end{pmatrix}. \qquad (57)$$

Therefore, $h_1(\partial'_2(x)) \in \mathrm{Im}(\partial_2)$ for all $x \in C'_2$, and $h$ is a weak chain map.

We now show using Lemma 2.1 that $f$ and $h$ are both weak quasi-isomorphisms. We first calculate $f_1 \circ h_1$ and $h_1 \circ f_1$ in matrix form:

$$f_1 \circ h_1 = I_{n_1-1}, \qquad (58)$$

$$h_1 \circ f_1 = \begin{pmatrix} I_{n_1-1} & \begin{matrix} 0 \\ \vdots \\ 0 \end{matrix} \\ \hline 0 \end{pmatrix} = I_{n_1} + \begin{pmatrix} 0 & \begin{matrix} 0 \\ \vdots \\ 0 \end{matrix} \\ \hline 0 \end{pmatrix}. \qquad (59)$$

Applying $h_1 \circ f_1$ to any $x \in C_1$, we obtain:

$$h_1(f_1(x)) = x + \begin{pmatrix} 0 \\ \vdots \\ 0 \\ x_{n_1} \end{pmatrix} = x + x_{n_1} e_{n_1} = x + x_{n_1} \partial_2(g_{n_2}) \qquad (60)$$

where $x_{n_1} = x \cdot e_{n_1}$. Therefore, $h_1(f_1(x)) \in x + \mathrm{Im}(\partial_2)$, and $[h_1(f_1(x))] = [x]$. Moreover, since $f_1(h_1(x')) = x'$ for all $x' \in C'_1$, we also have $[f_1(h_1(x'))] = [x']$. By Lemma 2.1, we can conclude that $f_B$ and $h_B$ are both weak quasi-isomorphisms.

It remains to show that $f_B$ and $h_B$ are distance- and decoding-preserving. For this, we show that the three conditions of Lemma 2.2 are satisfied. Let us start with the first one. For every basis element $s_i$ of $C_0$ and $s'_j$ of $C'_0$, we have:

$$h_0(f_0(s_i)) = h_0(s'_i) = s_i, \qquad (61)$$

$$f_0(h_0(s'_j)) = f_0(s_j) = s_j. \qquad (62)$$
Therefore, $h_0$ and $f_0$ are inverses of each other.

To see that $f_1(x)$ has the same weight as $x$ if $x$ is a minimum-weight logical error, we notice that $x$ cannot be supported on $e_{n_1}$, since $x + e_{n_1} = x + \partial_2(g_{n_2})$ would then be another non-trivial logical error with a weight reduced by one. Since all the other nodes remain unchanged through the action of $f_1$, $x$ and $f_1(x)$ must have the same weight.

It remains to show that $f_1$ and $h_1$ are weight-nonincreasing. Let $x' \in C'_1$ such that $x' = \sum_i x'_i e'_i$. We have:

$$h_1(x') = \sum_{i=1}^{n_1-1} x'_i h_1(e'_i) = \sum_{i=1}^{n_1-1} x'_i e_i. \qquad (63)$$

Therefore,

$$|h_1(x')| = \sum_{i=1}^{n_1-1} x'_i = |x'|, \qquad (64)$$

where in this equation the $x'_i$ are interpreted as integers. Thus, $h_1$ is weight-preserving, and therefore weight-nonincreasing.

Let $x \in C_1$ such that $x = \sum_i x_i e_i$. We have:

$$f_1(x) = \sum_{i=1}^{n_1} x_i f_1(e_i) = \sum_{i=1}^{n_1-1} x_i e'_i. \qquad (65)$$

Therefore,

$$|f_1(x)| = \sum_{i=1}^{n_1-1} x_i \le \sum_{i=1}^{n_1} x_i = |x|. \qquad (66)$$

We finally apply Lemma 2.2 to conclude that $f_A$ and $h_A$ are distance- and decoding-preserving.

<figure><img src="image_7.png" /></figure>

# 3 Spacetime codes

In this section, we review the spacetime codes formalism. Following Refs [19, 21] we define the spacetime code associated to a Clifford circuit as a subsystem code, with gauge operators for each gate, measurement, and input state stabilizer. The stabilizers of this subsystem code then either correspond to redundancies between measurements—often referred to as detectors [22, 64, 65]—or measurements that could be made redundant by the addition of measurements later in the circuit (which we call incomplete detectors). Our approach is slightly different to that of Delfosse and Paetznick [23], where spacetime codes are stabilizer codes, with only complete detectors considered as stabilizers. We do however make use of results and definitions from their work.

## 3.1 Outcome code

Let us consider a circuit consisting Clifford gates and (multi-qubit) Pauli measurements. The input to the circuit is defined by a stabilizer group $S$, such that the input state is in the
codespace of the corresponding stabilizer code. We note that this, for example, allows us to
consider auxiliary qubits that are prepared in Pauli eigenstates.

The core idea behind spacetime codes is the observation that, in a circuit designed to
do error-correction, there are redundancies amongst measurement outcomes<fnref n="1" />. For instance,
in the circuit consisting of multiple rounds of stabilizer measurements of a stabilizer code,
each pair ($m_i, m_{i+1}$) of successive measurement outcomes of a given stabilizer should give the
same result, that is $m_i + m_{i+1} = 0$, where $m_i$ and $m_{i+1}$ are binary variables encoding the
measurement outcomes.

Suppose that the input stabilizer $\mathcal{S}$ contains the stabilizers being measured in the circuit, then the first set of stabilizer measurement outcomes will be deterministic, i.e., $m_1 = 0$. While the constraint $m_i+m_{i+1} = 0$ only depends on the circuit itself, the constraint $m_1 = 0$ depends on the circuit and the input stabilizer group. To put these two types of constraints on equal footing, we formally consider input stabilizers as measurements at the beginning of the circuit, whose output is post-selected to be 0. Denoting the input measurements by $s_1, \dots, s_k$ (one for each generator of the input stabilizer group), we always have $s_1 = \dots = s_k = 0$ after post-selection. However, when enumerating the redundancies between the measurements in a circuit, we will always suppose that those initial stabilizer measurements can take any value, as a trick to retain the stabilizers involved in a given redundancy. For instance, if a measurement $m_1$ somewhere in the circuit measures a stabilizer coming from the input space (that we replace by an initial measurement $s_1$), we will have $m_1 + s_1 = 0$ instead of $m_1 = 0$. The fact that $s_1 = 0$ is only used when decoding a particular instance of the circuit. The example in Fig. 4 illustrates this idea.

It was shown in Ref. [23] that, for any Clifford circuit with multi-qubit measurements, the set of measurement outcomes {$m_1, \dots, m_k$} forms an affine space. By considering input stabilizers as measurements themselves, as discussed above, this observation can be generalized to include stabilizers as well, that is, {$m_1, \dots, m_k, s_1, \dots, s_k$} forms an affine space. From now on, unless stated otherwise, we will stop making the distinction between measurements arising from input stabilizers or from actual measurements. By changing the sign of some measurement outcomes in post-processing, one can transform this affine space into a linear space. In other words, the set of measurement outcomes forms a (classical) linear code. Following the terminology of Ref. [23], we call this classical code the outcome code. The outcome code can be obtained efficiently from a given circuit, by following the procedure described in Ref. [23, Algorithm 1].

If errors occur during the circuit, some checks of the outcome code might be unsatisfied. The objective of spacetime code constructions is to map unsatisfied outcome code checks back to errors happening at different locations of the circuit—in other words, to rigorously formulate the decoding problem in the context of a circuit-level error model.

## 3.2 Detectors of the spacetime code

Once we know the outcome code of a circuit, the next step is to associate outcome code checks to fault locations and error types ($X$, $Y$ or $Z$) in the circuit. For this, we first need to introduce a coordinate system representing possible fault locations in the circuit. Let us

<footnote n="1">¹Such redundancies between measurement outcomes can also appear in circuits that are not associated to any particular code; see Fig. 4 for an example.</footnote>
<figure><img src="image_8.png" /><figcaption>Figure 4: Example of a circuit with redundant measurements. Red labels in measurement boxes represent the measurement outcomes, and blue labels on top of input states represent input stabilizers. The outcome code of the circuit has two checks, which we can write as $m_1 + m_2 + m_3 = 0$ and $s_1 + m_3 + m_4 = 0$. We also indicate in blue the coordinates $(i, t)$ of each spacetime location of the circuit. The last column of the circuit is added to fulfill the requirement that the number of timesteps must be odd.</figcaption></figure>

assume that every qubit is associated to a horizontal wire encompassing the whole circuit, and divide the circuit into $T$ time steps. We call $(i, t)$ the coordinates corresponding to row (or qubit) $i$ and column (or time step) $t$ of the circuit, where $i \in \{1, \dots, n\}$ and $t \in \{1, \dots, T\}$, with $t = 1$ representing the column of the circuit located before all the gates, and $t = T$ representing the column located after all the gates. The formalism requires that $T$ is odd, but this is not really a restriction as any circuit with even $T$ can be extended by one time step without changing the properties of the spacetime code. An example of circuit with a coordinate system as above is shown in Fig. 4

We define a spacetime operator as an assignment of a Pauli operator $P \in \{I, X, Y, Z\}$ to each coordinate of the circuit. We denote $P_{i,t}$ the spacetime operator comprising $P$ at coordinates $(i, t)$ and identity everywhere else. More generally, for an $n$-qubit Pauli operator $A$, we denote $A_t$ the corresponding spacetime operator located at time $t$.

We now consider an error model where Pauli errors can occur at every location of the circuit with a certain probability, and call the corresponding spacetime operator a *fault*. The goal is to associate to each check of the outcome code a spacetime operator, called a *detector*, such that a fault anticommutes with the detector if and only if it is detectable by the check.

We construct detectors in following way. Let us define the propagation of a Pauli operator $P$ from time $t$ to time $t' \ge t$ as $\Pi_{t \to t'}(P) = UPU^\dagger$ where $U$ is the unitary defined by all the unitary gates between $t$ and $t'$ ($U = I$ if $t = t'$). Any measurement between $t$ and $t'$ is considered to act as the identity, independent of whether $P$ commutes or anticommutes with it. Following the terminology of Refs. [19, 21], we then define the spackle of $P$ at $t$ as

$$ \text{spackle}_t(P) = \prod_{s=t}^{T} [\Pi_{t \to s}(P)]_s. \qquad (67) $$

By extension, the spackle of a measurement $M$ occurring between steps $t$ and $t+1$ is the spackle at $t+1$ of the Pauli operator $P$ being measured, i.e. spackle($M$) = spackle$_{t+1}$(P). Finally, the spackle of multiple measurements is the product of the individual spackles, i.e. spackle($M_1, \dots, M_k$) = spackle($M_1$) ... spackle($M_k$). Intuitively, the spackle of $P$ is its prop-
<figure><img src="image_9.png" /><figcaption>Figure 5: Spackles of measurements corresponding to (a) $m_1$, (b) $m_2$, (c) $m_3$ and (d) $s_1$.</figcaption></figure>

agation to all the following time steps, leaving a trace of the propagation at every time step. Examples of spackles are shown in Fig. 5.

We define the back-propagation of a Pauli operator from $t'$ to $t \le t'$ as $\overleftarrow{\Pi}_{t \leftarrow t'}(P) = U^\dagger P U$, where $U$ is the unitary defined by all the unitary gates between $t$ and $t'$. Then we define the backwards spackle (or *backle*) of a Pauli operator $P$ to be

$$ \text{backle}_t(P) = \prod_{s=t}^{1} [\overleftarrow{\Pi}_{s \leftarrow t}(P)]_s. \qquad (68) $$

And we define backle($M$) = backle$_t(P)$ where $M$ is a measurement of the Pauli operator $P$ between times $t$ and $t+1$.

We are now ready to define the notion of detector. The detector associated to a check of the outcome code involving the measurements $M_1, \dots, M_k$, is spackle($M_1, \dots, M_k$), i.e., the spackle of all the measurements involved in the check. Examples of detectors are shown in Fig. 6. It was shown in Ref. [23] that a fault anticommutes with a detector if and only if it anticommutes with an odd number of measurements of the check. Detectors are therefore in one-to-one correspondence with the checks of the outcome code, but with additional information on the possible locations and error types that can violate those checks. We note that
<figure><img src="image_10.png" /><figcaption>Figure 6: Detectors corresponding to the two outcome code checks of the circuit in Fig. 4.</figcaption></figure>

detectors are sometimes defined to directly be the checks of the outcome code, e.g., in the STIM software package [22].

## 3.3 Spacetime subsystem code

To define a spacetime code with the right decoding properties, we need to include the detectors defined above in the stabilizer group. Notice however that there are many faults that are not detectors but which commute with the detectors and have a trivial effect on the output of the circuit. This can happen when a fault consists of a certain Pauli operator before a gate together with its propagation after the gate (e.g. X before a Hadamard gate and Z after the gate). Another example is a fault consisting of a Pauli operator right after the measurement of this operator. Intuitively, these faults correspond to some degrees of freedom we have when decoding a spacetime code. Indeed, a decoding solution containing $X_i$ ($Z_i$) before a gate is equivalent to the same solution with $UX_iU^\dagger$ ($UZ_iU^\dagger$) after the gate. We do not want these faults to be logical operators of the spacetime code, so we consider them as gauge operators in a spacetime subsystem code.

We now specify the generators of the gauge group of the spacetime subsystem code, which we refer to as *elementary propagation operators*. For each gate of the circuit $U$, we have generators $P_{i,t}(UP_iU^\dagger)_{t+1}$ for all $i \in \text{supp } U$ and for $P \in \{X, Z\}$. We call these generators *gate propagation operators*; see Fig. 7 for some examples. For each input (stabilizer) measurement $S$ we have the generator $S_1$. For each measurement of an $m$-qubit Pauli operator $M$ at time $t$, we have the generator $Q_{t+1}$. We also have the generators $R_t R_{t+1}$ for $R$ in the centralizer of $M$ in the $m$-qubit Pauli group$^2$. For example, if $M = X_i X_j$, then the corresponding generators are $X_{j,t} X_{j,t+1}$, $X_{i,t+1} X_{j,t+1}$, $X_{i,t} X_{i,t+1}$, and $Z_{i,t} Z_{j,t} Z_{i,t+1} Z_{j,t+1}$. We use the term *measurement propagation operators* to refer to generators associated with measurements.

Since the spacetime code is now seen as a subsystem code, we can associate a gauge complex to it, which we call the *spacetime complex* of the circuit. In order to define the distance of a circuit, we need to equip the space of spacetime operators (middle space $C_1$ of

<footnote>$^2$We note that one can derive these generators by considering the elementary propagation operators of the standard “Hadamard test” circuit for measuring a Pauli operator.</footnote>
<figure><img src="image_11.png" /><figcaption>Figure 7: Examples of elementary propagation operators (gauge operators in a spacetime subsystem code).</figcaption></figure>

the spacetime complex) with a basis. In the rest of this paper, we choose single-qubit X and Z operators at every spacetime location of the circuit as our basis. Writing a vector in this basis is equivalent to writing it in the binary symplectic format. This choice is well-suited for noise models in which X and Z errors are considered to be independent, since single-qubit Y operators are for instance weight-two in this basis. We believe that our formalism could be extended to the case of correlated errors by defining a notion of distance/decoding function for an overcomplete generating set of $C_1$, but we leave this extension to future work.

Equipped with our basis for $C_1$, we can now define the distance of a circuit as the distance of the corresponding spacetime complex. We also say that two circuits are equivalent if their spacetime complexes are equivalent. An example spacetime complex, and its reduction using rule A, is shown in Fig. 8d

## 3.4 Stabilizers of the spacetime subsystem code

Here we characterize the stabilizers of the spacetime code, i.e. the gauge operators that commute with all gauge operators, in terms of spackles and backles. We show that detectors, in particular, are spacetime code stabilizers. We begin with two lemmas: one about the properties of elementary propagation operators, and one about spackles and backles.

**Lemma 3.1.** Every m-qubit gate or measurement has 2m associated independent and commuting elementary propagation operators. Furthermore, any Pauli operator commuting with all of these elementary propagation operators must be in their multiplicative span (up to a phase).

*Proof.* First consider an m-qubit unitary gate $U$, which has 2m associated elementary propagation operators $P_{i,t}(UP_iU^\dagger)_{t+1}$ for $i \in \text{supp } U$ and $P \in \{X, Z\}$. Consider two generators $P_{i,t}(UP_iU^\dagger)_{t+1}$ and $Q_{j,t}(UQ_jU^\dagger)_{t+1}$. Clifford unitaries preserve commutation relations so $[P, Q] = [PU^\dagger, QU^\dagger]$ and therefore $P_{i,t}(UP_iU^\dagger)_{t+1}$ and $Q_{j,t}(UQ_jU^\dagger)_{t+1}$ commute for all $P$ and for all $i$. Independence follows from the independence of the operators $\{P_{i,t} : P \in \{X, Z\}, i \in \text{supp } U\}$. Now consider an m-qubit measurement $M$, with associated elementary propagation operators $M_{t+1}$ and $R_t R_{t+1}$ for $R$ in the centralizer of $M$. The centralizer has $2m-1$ commuting generators so in total we have $2m$ independent and commuting elementary propagation operators.

Let $S$ denote the set of 2m independent and commuting elementary propagation operators associated with a gate or measurement. The support of $S$ spans 2m qubits, so $S$ defines a stabilizer state (a stabilizer code with no encoded qubits), whose centralizer within the Pauli group is exactly $S$. Therefore, any operator commuting with all elements of $S$ must be equal (up to a phase) to a product of operators in $S$. $\square$
**Lemma 3.2.** *Spackles and backles are gauge operators of the spacetime code*

*Proof.* For any $n$-qubit Pauli operator $P$ and time steps $t, t' \in \{1, \dots, T\}, t \le t'$, the spacetime operator $P_t[\Pi_{t \to t'}(P)]_{t'}$ is a product of gate propagation operators, and is therefore a gauge operator. Furthermore, for any measurement of a Pauli $M$ between times $t-1$ and $t$, $[\Pi_{t \to t'}(M)]_{t'} = M_t M_t[\Pi_{t \to t'}(M)]_{t'}$ is a gauge operator as a product of gate propagation operators and a measurement propagation operator. Consequently, spackle$_t(M) = \Pi_{s=t}^T [\Pi_{t \to s}(M)]_s$ is a gauge operator itself, and so is any spacetime operator of the form spackle$(M_1, \dots, M_\ell)$. Similarly, for any input stabilizer $S$, $[\Pi_{1 \to t'}(S)]_{t'} = S_1 S_1 [\Pi_{1 \to t'}(S)]_{t'}$ is a gauge operator as a product of gate propagation operators and input stabilizer (gauge) operators. Finally, to show that backles are gauge operators, we repeat the argument above, replacing $\Pi_{s \to t}(M)$ by $\overleftarrow{\Pi}_{s \leftarrow t}(M)$. $\square$

**Proposition 3.1.** *The stabilizers of the spacetime subsystem code are either the spackle of a set of measurements and input stabilizers or the backle of a set of measurements.*

*Proof.* Since spackles and backles are gauge operators by Lemma 3.2, those that commute with all gauge operators are stabilizers of the spacetime code.

In the other direction, let $S$ be a stabilizer of the spacetime code, and consider the support of $S$ at times $t$ and $t+1$, which we write as $P_t$ and $Q_{t+1}$, respectively. Since $S$ is a stabilizer, $P_t Q_{t+1}$ must commute with all the elementary propagation operators associated with the circuit elements acting between times $t$ and $t+1$. Consider some $m$-qubit circuit element $U$ whose elementary propagation operators share support with $P_t$ and $Q_{t+1}$. The operator $P_t Q_{t+1}$, restricted to the support of $U$, must commute with all of its elementary propagation operators, and therefore, by Lemma 3.1, must be in their multiplicative span$^3$. This is true for all circuit elements whose elementary propagation operators share support with $P_t Q_{t+1}$, and therefore $P_t Q_{t+1}$ must be equal to a product of elementary propagation operators.

Let $t_s > 1$ be the time step such that $G$ has no support on qubit $i$ at earlier time steps. And let $P_{i,t_s}$ denote the support of $G$ on qubit $i$ at time $t_s$. Suppose that the circuit element acting on qubit $i$ between time $t_s - 1$ and $t_s$ is a unitary gate. By Lemma 3.1, there are $2m$ independent gate propagation operators associated with an $m$-qubit gate, and so there will always exist a gate propagation operator that anticommutes with $P_{i,t_s}$. Now suppose that the circuit element acting on qubit $i$ between times $t_s - 1$ and $t_s$ is an $m$-qubit measurement $M$. By Lemma 3.1, there are $2m$ independent measurement propagation operators associated with $M$, and for $S$ to commute with all of these operators it must be contained in their multiplicative span. Furthermore, the only measurement propagation operator wholly supported on qubits at time $t_s$ is $M_{t_s}$ itself, and therefore $P_{i,t_s} = M_{i,t_s}$. Now consider the case for $t_s = 1$. Observe that $P_{i,1}$ will commute with all the gauge operators associated with the input stabilizers if the support of $S$ at the first time step is equal to an operator that commutes with the input stabilizers.

To summarize, since $S$ is a stabilizer it must be either preceded by the beginning of the circuit (and the $t=1$ support of $S$ must commute with the input stabilizers) or by a set of measurements such that the support of $S$ immediately following each measurement is equal to the operator being measured.

<footnote>$^3$We do not need to worry about the phases because the stabilizer group of a subsystem code is defined as the centre of the gauge group modulo phases.</footnote>
By an analogous argument, $S$ must either be followed by the end of the circuit or by a set of measurements such that the support of $S$ immediately preceding each measurement is equal to the operator being measured. Recall that $S$ must also be equal to a product of elementary propagation operators for every two consecutive timesteps. When $S$ is not preceded by the beginning of the circuit or followed by the end of the circuit, these conditions imply that $S$ is a spackle or backle of a set of measurements. Now suppose that $S$ is instead preceded by the beginning of the circuit and followed by the end of the circuit. Because $T$ is odd, the support of $S$ at the beginning of the circuit must be equal to an input stabilizer, as otherwise it would not be a product of elementary propagation operators. Therefore, $S$ is equal to the spackle of an input stabilizer. □

**Corollary 3.1.** *Detectors are stabilizers of the spacetime subsystem code.*

*Proof.* Let $M_1, \dots, M_k$ be a set of measurements that form a check of the outcome code. We show that spackle$(M_1, \dots, M_k)$ commutes with all the gauge operators, which implies (by Proposition 3.1) that it is a stabilizer of the spacetime subsystem code. First note that all the elementary propagation operators for a single gate commute with each other, by Lemma 3.1. For every $M_i$, spackle$_t(M_i)$ is constructed from elementary gate propagation operators, and therefore commutes with all elementary gate propagation operators occurring between times $t$ and $T$. And, in fact, this operator will commute with all elementary gate propagation operators, as any such operator occurring before time $t$ does not share support with spackle$_t(M_i)$. The remaining elementary propagation operators that we have not considered thus far are those that are associated with measurements. These operators may anticommute with spackles of measurements in general, but they necessarily commute with those operators when the measurements constitute a check of the outcome code. Without loss of generality, suppose that the circuit contains a measurement $N$ that occurs after measurements $M_1, \dots, M_l$ but before measurements $M_{l+1}, \dots, M_k$. The elementary propagation operator associated with $N$ commutes with spackle$(M_{l+1}, \dots, M_k)$ by definition. Now suppose that this elementary propagation operator anticommutes with spackle$(M_1, \dots, M_l)$. Then $M_1, \dots, M_k$ cannot possibly define a check of the outcome code as (informally) the measurement $N$ will destroy the correlation between $M_1, \dots, M_l$ and $M_{l+1}, \dots, M_k^4$. □

While we have shown that detectors are stabilizers of the spacetime code, they are not the only ones. As a simplified example, consider a measurement-only circuit where the operator $M$ is measured at time $t$. Now suppose that all subsequent measurements commute with $M$ and that $M$ cannot be decomposed into a product of any subset of the subsequent measurements. Observe that spackle($M$) is a stabilizer of the spacetime code, but it does not have an associated check of the outcome code. We call such operators *incomplete detectors*, as they could be made into detectors by appending further measurements to the circuit.

## 3.5 Logical operators of the spacetime subsystem code

We will characterize the logical operators of a spacetime subsystem code step by step, starting from a trivial example. Consider the trivial circuit on $n$ wires with $T$ time steps, i.e., the

<footnote n="4">⁴We do not present a formal argument here as it would necessitate the introduction of substantial additional notation and the result can be straightforwardly derived from [23, Algorithm 1].</footnote>
circuit consisting exclusively of identity gates. Without loss of generality, suppose that the input state to this circuit is in the codespace of some $[n, k, d]$ stabilizer code defined by the stabilizer group $S$. Let $\mathcal{G}$, $\mathcal{D}$, and $\mathcal{L}$ denote the gauge, stabilizer, and logical groups of the spacetime subsystem code associated with the circuit.

We have $2n(T - 1)$ gauge generators coming from the identity gates and $(n - k)$ gauge generators coming from the input stabilizers, all of which are independent. For each input stabilizer generator $S$, we have a stabilizer generator of the spacetime code spackle$_1(S)$, which—in the language of the previous section—is an incomplete detector. Now consider the spacetime operator spackle$_1(L)$, where $L$ is a logical operator of the input stabilizer code. This operator commutes with all the gauge operators (the argument is identical as for spackle$_1(S)$) but is not itself contained in the gauge group and is therefore a bare logical operator of the spacetime code. To see this, note that spackle$_1(L) = L_1L_2...L_T$, where $T$ is odd. The gauge group contains $S_1$ for all input stabilizers $S$, as well as $X_tX_{t+1}$ and $Z_tZ_{t+1}$ for all time steps $t$. Any odd-weight operator constructed from these components must act as a stabilizer at time step $t = 1$ and therefore cannot be equal to spackle$_1(L)$. There are $2k$ independent logical operators of the input stabilizer code, and therefore we have $2k$ generators of $\mathcal{L}$. Let $\mathrm{Mat}(\mathcal{G})$ denote the symplectic representation of the generators of $\mathcal{G}$, and similarly for $\mathrm{Mat}(\mathcal{D})$ and $\mathrm{Mat}(\mathcal{L})$. We have

$$ \begin{aligned} \mathrm{rk} \mathrm{Mat}(\mathcal{G}) + \mathrm{rk}(\mathrm{ker} \mathrm{Mat}(\mathcal{G})) &= \mathrm{rk} \mathrm{Mat}(\mathcal{G}) + \mathrm{rk} \mathrm{Mat}(\mathcal{D}) + \mathrm{rk} \mathrm{Mat}(\mathcal{L}), \\ &= [2n(T - 1) + (n - k)] + (n - k) + 2k = 2nT, \end{aligned} \quad (69) $$

as expected from the rank-nullity theorem (applied to $\mathrm{Mat}(\mathcal{G})$).

Now suppose that we replace the identity gates in our circuit with unitary gates. Consider, for example, replacing an identity gate with the Hadamard gate. This transforms the gate propagation operators as follows:

$$ X_{i,t}X_{i,t+1} \mapsto X_{i,t}Z_{i,t+1}, \quad Z_{i,t}Z_{i,t+1} \mapsto Z_{i,t}X_{i,t+1}, \quad (70) $$

i.e., we apply the Hadamard to the qubit with index $(i, t + 1)$. The transformation of the stabilizers and logical operators is analogous. Therefore, adding this gate to the circuit is equivalent to applying a Clifford unitary to a qubit of the spacetime code, which will not change the number of stabilizers or encoded qubits. Furthermore, the stabilizer generators will still be of the form spackle$_1(S)$ and the logical operators will still be of the form spackle$_1(L)$. Iterating this argument allows us to conclude that replacing identity gates with unitary gates does not change the number of stabilizers and encoded qubits of the spacetime code, or the form of the stabilizers and logical operators.

We now consider replacing identity gates with measurements. Recall that the input to the circuit is defined by the stabilizer group $S$; we call the corresponding stabilizer code the input code. Any $n$-qubit Pauli operator can be written in the form LSD, where $L$ is a logical operator of the input code, $S$ is a stabilizer of the input code, and $D$ is a destabilizer (sometimes called pure error) of the input code (see, e.g., [66]). We now consider the effect of measuring each of these types of operators in turn. If we measure a stabilizer $S$ between times $t$ and $t+1$ we gain an additional stabilizer generator spackle$_1(S)$ spackle$_t(S)$. But we also gain a relation between gauge operators as spackle$_1(S)$ spackle$_t(S)$ is equivalent to spackle$_{t-1}(S)$. The operators spackle$_1(L)$ are still logical operators, as $S$ and $L$ commute for all $L$. Now suppose that we measure a logical operator of the input code between times $t$ and $t + 1$.
We denote the measured logical operator as $L$ and its conjugate partner as $M$. In this case, spackle$_1(L)$ becomes a stabilizer, we gain an additional stabilizer spackle$_1(L)$ spackle$_t(L)$, and the operator spackle$_1(M)$ is no longer a logical operator of the spacetime code as it anticommutes with $L_t$. Finally, suppose that we measure a destabilizer $D$ between times $t$ and $t+1$, and that $D$ anticommutes exclusively with the stabilizer generator $S$. The operator spackle$_1(S)$ is no longer a stabilizer, but is replaced by the operator spackle$_t(D)$.

Now we are ready to consider a generic circuit containing unitary gates and measurements. We start from a circuit consisting of unitary gates only, and consider replacing some unitary gates with measurements. For example, suppose we replace a gate between times $t$ and $t+1$ with a measurement of a Pauli operator $P$. To understand the effect of this operator we need to consider the propagations of the input stabilizers and logical operators, i.e., $\Pi_{1 \to t}(S)$ and $\Pi_{1 \to t}(L)$ for all input stabilizer generators $S$ and input logical operators $L$. If the measurement is equal to $\Pi_{1 \to t}(S)^5$, then we gain a stabilizer spackle$_1(S)$ spackle$_t(P)$ and one relation between gauge generators. Similarly, if the measurement is equal to $\Pi_{1 \to t}(L)$ for some logical operator then we lose two logical operators (spackle$_1(L)$ and its conjugate partner) and gain two stabilizers (spackle$_1(L)$ and spackle$_1(L)$ spackle$_t(P)$). And finally, if the operator anticommutes with exclusively $\Pi_{1 \to t}(S)$, then we lose spackle$_1(S)$ from the stabilizer group but gain spackle$_t(P)$.

The above argument gives us a method for generating the stabilizers and logical operators of a spacetime subsystem code. Concretely, we start from a spacetime code and replace all the measurements with identity gates. The stabilizers and logical operators of this spacetime code are simply the spackles of the input stabilizers and logical operators. We then add the original measurements back into the circuit one by one (in the order in which they appear in the circuit), and update the gauge, stabilizer, and logical operator groups accordingly. Examples of logical operators in the general case are shown in Figs. 8b and 8c.

## 3.6 Relationship to other frameworks

To end this section, we would like to discuss the relationship between the spacetime code formalism and two other popular frameworks used to analyze error-correcting circuits: STIM's detector error model [22, 64, 65] and ZX-calculus with Pauli webs [14, 33, 34, 56, 67].

In STIM's detector error model, three types of objects are constructed from a given circuit: the detectors, the logical observables and the error mechanisms. A *detector* is a set of measurements that have a deterministic parity in the absence of errors, i.e. a check of the outcome code. A *logical observable* is a set of measurements whose value correspond to measuring a logical operator. An *error mechanism* is a set of errors that flip the same detectors and logical observables. From those three types of objects, one can draw a tripartite graph with error mechanism nodes connected to a detector or logical observable node when the error mechanism flips that detector or logical observable in a circuit execution.

We see three main differences between the spacetime code and the detector error model formalisms:

1. In spacetime codes, the groups of spacetime stabilizers, gauge operators, and logical correlations are derived directly from the circuit and the input stabilizer space. This stands

<footnote n="5">⁵The measurement can also be in the span of $\Pi_{1 \to t}(S)$ and the effect would be analogous.</footnote>
<figure><img src="image_12.png" /><figcaption>Figure 8: Example of a spacetime code, with its stabilizers, logical operators, and gauge complexes. (a) A Clifford circuit annotated with three generators of the stabilizer group of its associated spacetime subsystem code. The notation $S_{XX}$ means that the input state stabilized by $XX$. The purple and orange stabilizers are detectors, while the green operator is an incomplete detector. (b-c) First and second pairs of logical operators. In orange are the logical errors (dressed logical operators of the subsystem code) and in purple are the logical correlations (bare logical operators). (d) Spacetime complex of the circuit. Circles are gauge nodes, squares are qubit nodes, and triangles are detector nodes. Note that due to the symplectic matrix $\Omega$, an $X \leftrightarrow Z$ permutation is applied to the stabilizer generators in order to obtain the detector nodes. (e) Reduced gauge complex after applying Rule A on each gauge node associated to a Hadamard gate.</figcaption></figure>
in contrast to the detector error model, where detectors and logical observables are specified manually. The distinction, however, is largely practical rather than fundamental: defining detectors and observables by hand makes it possible to choose a low-weight basis that simplifies decoding, whereas generating them automatically facilitates the proof of fault-tolerant properties of circuits.

2. Spacetime codes are constructed with gauge operators first, while detector error models are constructed with logical observables first. In a spacetime code, the counterparts of the logical observables—the logical correlations—can be derived from the chain complex (by computing the cohomology). In a detector error model, the counterparts of the gauge operators can be derived by looking at all the combinations of error mechanisms that commute with all detectors and logical observables.

3. In our formalism, we take as our basis of errors all the single-qubit $X$ and $Z$ errors occurring at spacetime locations immediately before and after each gate. As noted at the end of Section 3.3, we expect that the framework can be extended to incorporate correlated errors, although this is not yet achieved in its present form. On the other hand, the detector error model has a flexible definition of error mechanisms, which can include correlated multi-qubit errors.

In the ZX-calculus formalism, a given circuit is turned into a ZX diagram, and a set of *Pauli webs*—colored edges representing both detectors and logical correlations—is drawn following some specific rules [56]. If the circuit has some input and output qubits, the corresponding edges are called *outer ports* of the ZX diagram. We can then partition the Pauli webs as follows:

* Pauli webs with no support in an outer port: those are equivalent to our full detectors.

* Pauli webs with support in outer ports that are either input or output, but not both: those are equivalent to our incomplete detectors.

* Pauli webs with support on both input and output outer ports: those are the logical correlations.

The set of trivial errors (the counterparts of our gauge operators) can also be read off from the ZX diagrams, as the set of constraints at each node that allow one to define the Pauli webs. Moreover, the recent development of distance-preserving [33, 34] and fault-equivalent [67] rewrite rules for ZX-diagrams makes the two formalisms comparable. The precise relationship between ZX diagrams and spacetime complexes—and therefore fault-tolerant maps and distance-preserving rewrite rules—is left to future work.

Finally, the spacetime code formalism can be compared with the dynamical code formalism of Fu and Gottesman [68], where subsystem codes are likewise constructed from circuits and a corresponding notion of distance is defined. A more detailed comparison will be provided in upcoming work by the authors [69].

# 4 Fault-tolerant measurement-based quantum computing

Quantum computing architectures based on the photonic platform are distinguished by an inherent scalability, allowing them to clear a major hurdle en route to the construction of
devices capable of solving classically intractable problems [38]. However, photonic approaches are only viable with low-depth optical circuits to preclude noise—especially loss—from accruing to levels incompatible with fault tolerance. This restriction invites reformulating the standard circuit model of quantum computing into the measurement-based paradigm [70–74], where flying qubits need only traverse a handful of physical gates before being measured out. In measurement-based quantum computing (MBQC), the entanglement is generated offline in a resource state called a *graph state* or *cluster state*, while the computation is embedded into a sequence of adaptive local measurements and classical feedforward. The ability to construct graph states and perform measurements in arbitrary bases—either directly or through auxiliary magic states—unlocks universality.

The construction of fault-tolerant graph states from quantum error correcting (QEC) codes dates back to early surface code work [45, 46, 75–78]. Since then, this work has been generalized to CSS codes in a process called *foliation* [49, 50, 54, 79]. In this procedure, the two disjoint Tanner graphs of the code (containing X-type and Z-type stabilizers, respectively) are interpreted as alternating layers of the foliated graph state. Data qubits between adjacent layers are entangled with each other, resulting in teleportation chains propagating quantum information from layer to layer with byproduct Hadamard gates. The X and Z checks are replaced by *detectors*, in this case combinations of X measurement outcomes in consecutive layers that add to zero in the absence of errors. Foliation has also been generalized to non-CSS codes and subsystem codes [50] and to certain Floquet codes [51].

In this section, we start by introducing the reader to measurement-based quantum computing, defining important terminology for the rest of the paper. We then study the fault-tolerant properties of MBQC circuits through the lens of the associated spacetime code. Finally, we show how the associated spacetime complex can be simplified to another chain complex, the cluster state complex, generalizing the chain complex formalism of Ref. [53].

## 4.1 Measurement-based quantum computing

The fundamental observation underlying the MBQC formalism is that any single-qubit diagonal unitary gate

$$U_z(\phi) = e^{-\frac{\phi}{2}Z} \qquad (71)$$

followed by a Hadamard can be implemented through the following teleportation circuit [78]:

<figure><img src="image_13.png" /></figure>

where $X_\phi$ is the measurement basis consisting of the two projectors $|0\rangle\langle0| \pm e^{i\phi}|1\rangle\langle1|$. In particular, the Hadamard gate is implemented by taking $\phi = 0$. Since any single-qubit gate can be decomposed into Hadamard and diagonal unitaries, we can implement any arbitrary single-qubit operation via successive teleportation circuits of the form of Eq. (72). Moreover, adding simple CZ gates (with no measurement) to our set of operations, we can see that any multi-qubit unitary operation can be implemented with only CZ gates, $|+\rangle$ ancilla state preparation, single-qubit measurements, and Pauli corrections.
In circuits of the form above, the Pauli correction can always be moved to the very end, as long as we perform the measurements sequentially and adapt the measurement bases depending on the previous measurements outcomes. For instance, two successive teleportation circuits with measurement bases $X_{\phi_1}$ and $X_{\phi_2}$, and without any Pauli correction, implements the following unitary:

$$X^{m_2} HU_z(\phi_2) X^{m_1} HU_z(\phi_1) = X^{m_2} Z^{m_1} HU_z(-\phi_2) HU_z(\phi_1) \quad (73)$$

where $m_1$ and $m_2$ are the outcomes of the first and second measurements, respectively. The Pauli correction has been propagated to the end, with the effect of transforming the second unitary from $U(\phi_2)$ to $U(-\phi_2)$. By changing the second measurement basis from $X_{\phi_2}$ to $X_{-\phi_2}$, we therefore recover the correct unitary. The same reasoning applies when adding more teleportation circuits and CZ gates.

In other words, we can implement any unitary operation with a circuit of CZ gates (between the input state and some ancilla qubits initialized in the $|+\rangle$ states), followed by a sequence of measurements (whose bases depend on the operation we are implementing and the outcome of the previous measurements), and finally some Clifford corrections (which can be done as a classical post-processing step). Any such circuit can therefore be constructed from the following data, often referred to as an MBQC pattern [47]:

1. A graph $G$ with adjacency matrix $A$, where each node represents a qubit and each edge a CZ gate between the corresponding qubits.

2. Two sets of nodes, the *input nodes* $\mathcal{I}$ and *output nodes* $\mathcal{O}$, such that input nodes represent the input state (as opposed to the ancilla qubits initialized in the $|+\rangle$ state), and the output nodes represent the qubits that are not measured at the end of the circuit.

3. A list $\mathcal{B}$ of angles assigned to each non-output node, representing the basis in which it is measured (not taking into account the change of basis due to Pauli propagations).

4. A list of integers $\mathcal{T}$ assigned to each non-output node, representing the time step at which it is measured.

We write such an MBQC pattern as MBQC($A, \mathcal{I}, \mathcal{O}, \mathcal{B}, \mathcal{T}$). The corresponding circuit made of CZ gates and measurements is called the *circuit realization of the MBQC pattern*, or MBQC circuit for short. We refer to the state obtained after applying all the CZ gates to an input state as a *cluster state* or *graph state*. We refer to the graph $G$ as the *cluster state graph* of the MBQC pattern.

As an example, the following circuit

<figure><img src="image_14.png" /></figure>

can be represented by the following MBQC pattern:
<figure><img src="image_15.png" /></figure>

where the blue nodes (apart from the output modes) are measured in the order of the blue indices, i.e. $\mathcal{T} = [1, 2, 3, 4]$. We only label the measurement basis of non-output nodes for non-zero angles, that is, $\mathcal{B} = [0, 0, \pi/4, 0]$. This means, that to run the circuit in a measurement-based way, we first need to initialize the non-input nodes $\{3, 4, 5, 6\}$ in the $|+\rangle$ state, perform a CZ for each edge, and measure the nodes $\{1, 2, 3, 4\}$ in increasing order in their respective basis, up to a sign which can be computed through the propagation of Pauli correction operators. We call this circuit the *circuit associated to the MBQC pattern*.

It should be noted that the mapping from a circuit to an MBQC pattern is far from unique in general: both the order of measurements and the graph itself can be modified without changing the corresponding channel, and a great deal of research has been done on how to optimize MBQC patterns; see for example [47, 80–82].

In the context of quantum error correction and spacetime codes, we are mainly interested in mapping *Clifford* circuits into MBQC patterns. In this case, it becomes unnecessary to update the measurement bases dynamically and the order of measurements becomes arbitrary. Indeed, if $U_z(\phi)$ is a Clifford gate, any Pauli correction $P$ propagates into a new Pauli correction $P'$, i.e. $U_z(\phi)P = P'U_z(\phi)$, by the definition of a Clifford gate, without a need to update the angle $\phi$. The measured angle on each qubit is therefore exactly the basis specified in $\mathcal{B}$. Moreover, since each component of $\mathcal{B}$ is either 0 or $\pi/2$ in the Clifford case, we can replace it by a vector $b$ such that $b_i = 0$ if $\mathcal{B}_i = 0$, and $b_i = 1$ otherwise. We call any such MBQC pattern built from a Clifford circuit a *Clifford MBQC pattern* and denote it $\text{MBQC}(A, \mathcal{I}, \mathcal{O}, b)$.

## 4.2 Spacetime code of an MBQC circuit

As discussed above, the circuit realization of the pattern $\text{MBQC}(A, \mathcal{I}, \mathcal{O}, b)$ can be written as a sequence of CZ gates, acting on some qubits divided into two categories: the input qubits $\mathcal{I}$, characterized by a stabilizer group $S_{\mathcal{I}}$, and the non-input qubits initialized in the $|+\rangle$ state. A subset of the qubits (the non-output qubits) is then measured in the $X$ or $Y$ basis. We associate to this circuit a noise model where errors can either happen before or after all the CZ gates. When the circuit is built by mapping a stabilizer or Floquet code experiment to MBQC, this noise model maps directly to the phenomenological noise model for the code (as we will prove in Section 6 and Section 7). To define the spacetime code corresponding to this noise model, we consider that all the CZ gates are applied at the same time step of the circuit and merged into a single unitary, that we call a *CZ network*. Since all the CZ gates commute, their order does not matter and this unitary is entirely characterized by the adjacency matrix $A$ of the cluster state graph, defined by $A_{i,j} = 1$ if and only if there is a CZ gate between qubits $i$ and $j$. To draw CZ networks within a circuit, we introduce a new circuit notation: a blue box surrounding a set of gates is treated as a single gate when constructing the spacetime code. In other words, no error can happen within such a box. Here is an example of MBQC circuit using this notation:
<figure><img src="image_16.png" /></figure>

We therefore currently have a circuit with two timesteps: $t = 1$ before the CZ network and $t = 2$ after. However, as discussed in Section 3.3, we need an odd number of steps to define a spacetime code. We therefore add a layer of identity gates after the CZ network, adding a third timestep $t = 3$ in the circuit. For instance, the circuit above becomes:

<figure><img src="image_17.png" /></figure>

We are now ready to describe the spacetime code. Every qubit $i$ initialized in the $|+\rangle$ state is associated with a gauge operator $X_{i,1}$, every input stabilizer $S$ to a gauge operator $S_1$ (i.e. the spacetime operator corresponding to $S$ at $t = 1$), and every measurement on qubit $j$ to a gauge operator $X_{j,3}$ or $Y_{j,3}$ depending on the measurement basis.

As discussed in Section 3.4, every spacetime stabilizer is either the spackle of some input gauge operators (coming from the input stabilizers) or the backle of some output gauge operators (coming from the final measurements). We give the following characterization of those spacetime stabilizers:

**Proposition 4.1.** Let MBQC($A, \mathcal{I}, \mathcal{O}, b$) be a Clifford MBQC pattern and $S$ its input stabilizer group. The stabilizers of the corresponding spacetime code are the spacetime operators $S$ that commute with all the gauge operators and have either:

* The restriction of $S$ to the input qubits at $t = 1$ is equal to an input stabilizer:

$$S_{\mathcal{I},1} \in S. \qquad (77)$$

* The restriction of $S$ to the output qubits at $t = 2$ and $t = 3$ is the identity:

$$S_{\mathcal{O},2} = S_{\mathcal{O},3} = I. \qquad (78)$$

*Proof.* Let $S$ be a stabilizer of the spacetime code. By Proposition 3.1, $S$ is either the spackle of some input stabilizers of the MBQC circuits—including both the single-qubit $X$ stabilizers
characterizing the $|+\rangle$ states, and elements of $S$ on the input qubits—or the backle of some $X/Y$ measurements at the end of the circuit. In the first case, the restriction of $S$ to the input qubits at $t = 1$ must be an element of $S$, which includes the identity in the case that $S$ is the spackle of single-qubit $X$ stabilizers at non-input qubits only. In the second case, the restriction of $S$ to the input qubits at $t = 1$ can be any operator that commutes with the input stabilizers. However, as the backle of some final measurements, it cannot have any support on the output qubits. Therefore, $S_{O,2} = S_{O,3} = I$.

In the other direction, let $S$ be a spacetime operator that commutes with all gauge operators of the spacetime code and obeys either Eq. (77) or Eq. (78). Since $S$ commutes with all gauge operators, it commutes in particular with the single-qubit $X$ operators at time $t = 1$ associated to the $|+\rangle$ states on non-input qubits, and with the single-qubit $X/Y$ measurement propagation operators at $t = 3$ on non-output qubits. This implies that $S$ must have either $X$ or $I$ on its non-input qubits at $t = 1$, either $X$ or $I$ on its non-output qubits measured in the $X$ basis at $t = 3$, and either $Y$ or $I$ on its non-output qubits measured in the $Y$ basis at $t = 3$.

If $S$ obeys Eq. (77), we have $S_{I,1} \in S$ and $S$ restricted to $t = 1$ can be written as product of measurement propagation operators. Moreover, since $S$ commutes with all gauge operators, it must be a gate propagation operator of the CZ network when restricted to $t = 1$ and $t = 2$, by Lemma 3.1. By the same argument, its restrictions to $t = 2$ and $t = 3$ must be identical, as there are only identity gates in-between those two timesteps. Therefore, $S$ must be the spackle of some initial stabilizers (including the single-qubit $X$ stabilizers on non-input qubits).

If $S$ obeys Eq. (78), we have $S_{O,3} = I$ and $S$ restricted to $t = 3$ can be written as a product of measurement propagation operators. By a similar argument as above, it must be identical at $t = 2$ and $t = 3$, and a CZ network gate propagation operator between $t = 1$ and $t = 2$, meaning that $S$ is the backle of some final measurements.

In all cases, $S$ is either a spackle or a backle and must therefore be a gauge operator by Lemma 3.2. Since $S$ commutes with all gauge operators and is a gauge operator, it is a stabilizer of the spacetime code. $\square$

## 4.3 Cluster state complex

It has recently been shown that many types of foliated and non-foliated cluster states can be understood using the language of chain complexes [53–55]. In particular, those works associate to a cluster state graph a chain complex of the form

$$C_3 \xrightarrow{\partial_3} C_2 \xrightarrow{\partial_2} C_1 \xrightarrow{\partial_1} C_0 \qquad (79)$$

where it is assumed that the nodes of the cluster state graph can be bipartitioned into primal and dual nodes, such that no edge connects a primal node to a dual node. In this case, detectors can also be bipartitioned into primal and dual detectors depending on the type of qubits in their support. The spaces $C_2$ and $C_1$ then represent, respectively, the primal and dual nodes, while $C_3$ and $C_0$ represent, respectively, the primal and dual detectors. This representation works for the foliation of any CSS code and also allows for the discovery of many non-foliated cluster states [53]. However, this representation breaks down when considering the foliation of non-CSS codes, due to the potential presence of $Y$ measurements in the MBQC pattern and length-3 cycles in the cluster state graph, preventing the existence of a bipartition of the nodes [50]. Moreover, the exact relationship between this chain complex
and the spacetime complex of the corresponding spacetime code has not been previously elucidated.

In this section, we generalize this chain complex formalism to any generic (Clifford) MBQC pattern. Using the reduction rules of Section 2.4, we then show that this chain complex is equivalent to the spacetime complex of the associated circuit.

**Definition 4.1 (Cluster state complex).** Consider a pattern MBQC($A, \mathcal{I}, \mathcal{O}, b$) and an input stabilizer group $\mathcal{S}$. We denote by $n_Q$ the dimension of $A$, $n_I$ the number of elements of $\mathcal{I}$, $n_O$ the number of elements of $\mathcal{O}$, $n_S$ the rank of $\mathcal{S}$, and $B = \text{diag}(b)$ the matrix with diagonal $b$ and zero elsewhere. The corresponding *cluster state complex* is a length-2 chain complex

$$ C_0 \xrightarrow{G^T} C_1 \xrightarrow{H} C_2 \qquad (80) $$

where $C_0, C_1$ and $C_2$ are finite-dimensional vector spaces over $\mathbb{F}_2$, and:

* $C_0$ has dimension $n_Q + n_S$, and we call the basis elements of this space *gauge nodes*. We have one gauge node per vertex of the cluster state graph, and one gauge node per input stabilizer. We partition those nodes into five sets:

- $G_S$ (nodes corresponding to input stabilizers),

- $G_{I\bar{O}}$ (nodes corresponding to input non-output vertices),

- $G_{\bar{I}O}$ (nodes corresponding to output non-input vertices),

- $G_{IO}$ (nodes corresponding to input output vertices),

- $G_{\bar{I}O}$ (nodes corresponding to non-input non-output vertices).

* $C_1$ has dimension $n_Q + n_I + n_O$, and we call the basis elements of this space *error nodes*. We have one error node per vertex of the cluster state graph, called a *Z-type node*, interpreted as a Z error applied to the corresponding qubit (at any timestep, as all the Z errors on a given wire are equivalent). We also have one additional error node per input and output vertex of the cluster state graph, called an *X-type node*, interpreted as an X error on this qubit applied either before the CZ network (for input vertices) or after (for output vertices). Since these nodes do not correspond to any vertex of the original cluster state graph, we call them *virtual nodes*, and we call the other basis elements *physical nodes*. Given a vector $x \in C_1$, we denote $x_I (x_O)$ its restriction to the physical input (output) nodes, and $x_{\bar{I}} (x_{\bar{O}})$ its restriction onto the virtual ones. We emphasize that if a vertex is both input and output, it is associated to two distinct virtual nodes in $C_1$. We partition the nodes into six sets:

- $X_{I\bar{O}}$ (virtual nodes corresponding to input non-output vertices),

- $X_{\bar{I}O}$ (virtual nodes corresponding to output non-input vertices),

- $X_{\bar{I}O}$ (physical nodes corresponding to non-input non-output vertices),

- $X_{IO}$ (first set of virtual nodes corresponding to input output vertices),

- $X'_{IO}$ (second set of virtual nodes corresponding to input output vertices),

- $Z_I$ (physical nodes corresponding to input vertices) and $Z_{\bar{I}}$ (physical nodes corresponding to non-input vertices).
• G is the $(n_Q + n_S) \times (n_Q + n_I + n_O)$ matrix:

$$ G = \begin{array}{c} \begin{array}{c} \chi_{\overline{IO}} \\ \chi_{IO} \\ \chi_{\overline{IO}} \\ \chi'_{IO} \\ \mathcal{Z}_I \\ \mathcal{Z}_{\overline{I}} \end{array} \\ \begin{array}{c} \mathcal{G}_S \left( \begin{array}{cccc|cc} S_{\chi_{\overline{IO}}}^X & S_{\chi_{IO}}^X & 0 & 0 & S^Z & 0 \end{array} \right) \\ \mathcal{G}_{\overline{IO}} \left( \begin{array}{cccc} I & 0 & 0 & 0 \\ 0 & 0 & I & 0 \\ 0 & I & 0 & I \\ 0 & 0 & 0 & 0 \end{array} \right) \\ \mathcal{G}_{IO} \\ \mathcal{G}_{\overline{IO}} \end{array} \end{array} \quad (81) $$

where $S = (S^X|S^Z)$ is the parity-check matrix of the input stabilizer group, and $S_E^X$ for a set $E$ denotes $S^X$ restricted to the column indices in $E$. Moreover, the rows and columns of $A$ and $B$ are reordered to correspond to the indicated row and column labels. We note that the matrix $G$, interpreted as the biadjacency matrix between basis elements of $C_0$ and $C_1$, has a simple graphical construction:

1. Insert a Z-type node for every vertex of the cluster state graph.

2. Insert an X-type node for every input and output vertex of the cluster state graph.

3. Insert a gauge node for every Z-type vertex $z$ of the graph, and connect it to all the Z-type nodes whose corresponding vertices in the cluster state graph were connected to the vertex corresponding to $z$. Moreover, if $z$ corresponds to an input or output vertex of the cluster state graph, connect $z$ to all the X-type nodes corresponding to this vertex. Finally, if $z$ corresponds to a vertex of the cluster state graph measured in the Y basis, connect the gauge node to $z$.

4. For every input stabilizer, insert a gauge node connected to all the input $X$ and $Z$-type nodes that make up the stabilizer.

• $C_2$ has dimension $m$, and represents the space of cluster state detectors. A detector is a vector $x \in \ker G$ such that either $(x_I|x_{\overline{I}}) \in S$ or $(x_O|x_{\overline{O}}) = 0$. $H$ is an $m \times (n_Q+n_I+n_O)$ matrix whose rowspace is the space of detectors.

The chain complex condition $HG^T = 0$ (or equivalently $GH^T = 0$) is fulfilled, since every row of $H$ belongs to $\ker G$ by construction.

Examples of cluster state complexes are shown in Fig. 9c, Fig. 10c and Fig. 11c. Before proving that this chain complex is equivalent to the gauge complex of the corresponding spacetime code, let us start by building some intuition. We begin by providing a graphical representation of the cluster state complex. As described in Section 2.3, the graphical representation of the chain complex in Eq. (80), contains three types of nodes: gauge nodes ($C_0$), error nodes ($C_1$) and detector nodes ($C_2$). However, it is possible to compress this graph and have a single node representing both a gauge operator and an error.

**Definition 4.2** (Compressed representation of a cluster state complex). Given a cluster state complex

$$ C_0 \xrightarrow{G^T} C_1 \xrightarrow{H} C_2 \quad (82) $$
<figure><img src="image_18.png" /><figcaption>Figure 9: The different representations of a cluster state. (a) Circuit consisting of two successive telepor-
tations of a two-qubit state, followed by a $ZZ$ measurement. We assume that the input state is stabilized
by $S = \{I, ZZ\}$. (b) Cluster state graph of the corresponding MBQC pattern. Purple and light blue nodes
indicate input and output qubits, respectively. (c) The corresponding cluster state complex, where circles
indicate gauge nodes, squares error nodes (X-type and Z-type), and triangles detector nodes. (d) Aug-
mented cluster state complex, where we have added a new gauge node for each input and output X-type
node, and one new error node and detector node (black square and triangle connected to it) for the gauge
node associated to the input $ZZ$ stabilizer. In this complex we have the same number of error and gauge
nodes, allowing to interpret the biadjacency matrix between circles and squares as an adjacency matrix. (e)
Compressed representation of the cluster state complex. Each circle now represents both an error operator
($Z$ for filled circles and $X$ for empty circles) and a gauge operator (defined by its neighborhood). Red
triangles represent the detectors. (f) Compressed co-representation of the cluster state complex, where
the arrows of the previous graph have been inverted. Error nodes now have the opposite interpretation:
the filled circles are $X$ and the empty ones are $Z$. This graph is useful to derive the detectors, as the
set of nodes with an empty boundary whose restriction to the input qubits is an input stabilizer or whose
restriction on the output qubits is empty.</figcaption></figure>
<figure><img src="image_19.png" /><figcaption>Figure 10: The different representations of a cluster state, where one node is both an input and output. See Fig. 9 for a more detailed description of the drawing conventions. (a) Circuit consisting of two successive teleportations of one of the two input qubits, followed by a $ZZ$ measurement. We assume that the input state is stabilized by $S = \{I, ZZ\}$. (b) Cluster state graph of the corresponding MBQC pattern. (c) Associated cluster state complex. The input-output node of the cluster state graph leads to a $Z$-type node in the complex, as well as two $X$-type nodes, representing the two different $X$ errors on that qubit, before and after the CZ network. (d) Augmented cluster state complex. (e) Compressed representation of the cluster state complex, without detector nodes for clarity. (f) Compressed co-representation of the cluster state complex, with detector nodes.</figcaption></figure>
<figure><img src="image_20.png" /><figcaption>Figure 11: Different representation of a cluster state with Y measurements. See Fig. 9 for a more detailed description of the drawing conventions. (a) Two-qubit circuit with one CZ gate, $|+\rangle$ initialization and Y measurement on all qubits. It has one spacetime stabilizer, labeled in red. (b) Associated cluster state graph. (c) Corresponding cluster state complex. The Y measurements are reflected through the gauge nodes connected to their own associated error node. (d) Compressed representation of the cluster state complex. The self-loops are due to the Y measurements of the corresponding qubits.</figcaption></figure>

we can construct an equivalent complex, called the *augmented cluster state complex*

$$C'_{0} \xrightarrow{\tilde{G}^{T}} C'_{1} \xrightarrow{\tilde{H}} C'_{2} \qquad (83)$$

such that $C'_0$ and $C'_1$ have the same dimension. For this, we add $n_I + n_O$ basis elements to $C_0$, i.e. $C'_0 = C_0 \oplus \mathbb{Z}_{2}^{n_I+n_O}$, and $n_S$ basis elements to $C_1$, i.e. $C'_1 = C_1 \oplus \mathbb{Z}_{2}^{n_S}$. We build the square matrix $\tilde{G}$, of size $n_Q+n_I+n_O+n_S$, by adding $n_I+n_O$ zero rows and $n_S$ zero columns to $G$. Finally, we add $n_S$ basis elements to $C_2$ and define $\tilde{H}$ as

$$\tilde{H} = \begin{pmatrix} H & 0 \\ 0 & I_{n_S} \end{pmatrix} \qquad (84)$$

The directed graph defined by the adjacency matrix

$$B = \begin{pmatrix} \tilde{G}^T & \tilde{H} \\ \tilde{H} & 0 \end{pmatrix} \qquad (85)$$

is called the *compressed representation of the cluster state complex*. The first $n_Q+n_I+n_O+n_S$ rows and columns of $B$ correspond to the error/gauge nodes, while the last $m$ rows and columns correspond to the detector nodes.

This graph can be constructed directly by starting from the cluster state graph and adding one new vertex per input qubit, output qubit and input stabilizer. Since we now have two vertices for each input and output qubit, we label the one present in the original graph as a Z-type vertex and the new one as an X-type vertex. We then add one directed edge from every Z-type vertex to its corresponding X-type vertex. For every input stabilizer ($h_X|h_Z$), we add a directed edge between its corresponding vertex in the graph, and every X-type (Z-type) input vertex in the support of $h_X$ ($h_Z$). We also add a self-loop to every vertex $i$ whose corresponding qubit is measured in the Y basis.

Finally, we add detectors to the graph. They can be found directly from our current graph, by first inverting all the arrows, i.e. drawing the graph with adjacency matrix $\tilde{G}$ instead of $\tilde{G}^T$. In this new graph, the X-type vertices are now interpreted as Z errors and the Z-type vertices as X errors (due to the symplectic matrix $\Omega$ present in the second boundary map of the chain complex). The detectors can be identified as independent sets of vertices with an
<figure><img src="image_21.png" /><figcaption>Figure 12: From the spacetime complex of the MBQC circuit to the cluster state complex.</figcaption></figure>

empty boundary (this corresponds to finding a basis of $ker(\tilde{G}))$ whose restriction to the input qubits is an input stabilizer or whose restriction to the output qubits is empty. Note that if a vertex $v$ is connected to another vertex $u$ by a directed edge, then $u$ is in the boundary of $v$ only if the directed edge goes from $v$ to $u$. The graph with arrows inverted and adjacency matrix

$$B^T = \begin{pmatrix} \tilde{G} & \tilde{H} \\ \tilde{H} & 0 \end{pmatrix} \qquad (86)$$

is called the compressed co-representation of the cluster state complex.

An example of the representation and co-representation of a cluster state complex is shown in Fig. 9e and Fig. 9f. We are now ready to prove the main theorem of this section:

**Theorem 4.1.** Given a pattern MBQC($A, \mathcal{I}, \mathcal{O}, b$) and an input stabilizer group $S$, the spacetime complex of its circuit implementation and its cluster state complex are equivalent.

*Proof.* Let's begin by setting up some notations. Let $e_i \in \mathbb{Z}_2^n$ the vector containing a 1 at position $i$ and 0 everywhere else, for any $i \in \{1, \dots, n\}$. For any matrix $M$, we write $M_i := Me_i$ for the $i$th column. Given the spacetime complex of a circuit, a column $j$ of that circuit, and a binary vector $v$, we write $\mathcal{X}_j(v)$ ($\mathcal{Z}_j(v)$) for the set of all $X$ ($Z$) nodes of the chain complex on column $j$ and row $i$ for all $i$ such that $v_i = 1$.

We now consider the chain complex $C_\bullet$ associated to the spacetime code of the MBQC circuit

$$C_2 \xrightarrow{G^T} C_1 \xrightarrow{H\Omega} C_0 \qquad (87)$$

We want to show that there exists a fault-tolerant map to the cluster state complex $C'_\bullet$:

$$C'_0 \xrightarrow{G'^T} C'_1 \xrightarrow{H'} C'_2 \qquad (88)$$

with spaces and boundary maps as defined in Definition 4.1. We will use a combination of rules A and B to construct this fault-tolerant map. We will start by describing the succession
of reductions we are applying and how they affect the error and gauge nodes. We will then see how they affect the detector nodes.

For every row $i$ of the circuit, the CZ network induces the following two gauge operators:

$$g_i^X = \mathcal{X}_1(e_i) + \mathcal{X}_2(e_i) + \mathcal{Z}(A_i) \qquad (89)$$

$$g_i^Z = \mathcal{Z}_1(e_i) + \mathcal{Z}_2(e_i) \qquad (90)$$

Since the second gauge operator has weight 2, we can use rule A to remove it from the chain complex and replace the nodes $\mathcal{Z}_1(e_i)$ and $\mathcal{Z}_2(e_i)$ by a single node, that we denote $\mathcal{Z}(e_i)$. We can often simplify the first gauge operator as well, in a way that depends on whether the wire corresponds to an input qubit or not, and whether it is measured in the X basis, Y basis or is an output qubit. Those six cases are illustrated in Fig. 12. Let us study them separately:

1. Non-input, X basis measurement: we have two weight-1 gauge operators connected to $\mathcal{X}_1(e_i)$ and $\mathcal{X}_2(e_i)$ respectively. We use rule B to remove those nodes from the chain complex, giving us the simplified gauge operator $g_i^X = \mathcal{Z}(A_i)$.

2. Non-input, Y basis measurement: we have one weight-1 gauge operators connected to $\mathcal{X}_1(e_i)$ and one weight-2 gauge operator connecting $\mathcal{X}_2(e_i)$ with $\mathcal{Z}(e_i)$. We use rules A and B to remove $\mathcal{X}_1(e_i)$ from the chain complex and merge $\mathcal{X}_2(e_i)$ with $\mathcal{Z}(e_i)$, giving us the new gauge operator $g_i^X = \mathcal{Z}(A_i + e_i)$.

3. Non-input, output: we have one weight-1 gauge operators connected to $\mathcal{X}_1(e_i)$, which we remove using rule B, giving us the new gauge operator $g_i^X = \mathcal{Z}(A_i) + \mathcal{X}_2(e_i)$.

4. Input, X basis measurement: we have one weight-1 gauge operators connected to $\mathcal{X}_2(e_i)$, which we remove using rule B, giving us the new gauge operator $g_i^X = \mathcal{Z}(A_i) + \mathcal{X}_1(e_i)$.

5. Input, Y basis measurement: we have one weight-2 gauge operator connecting $\mathcal{X}_2(e_i)$ with $\mathcal{Z}(e_i)$. We use rules A to merge $\mathcal{X}_2(e_i)$ with $\mathcal{Z}(e_i)$, giving us the new gauge operator $g_i^X = \mathcal{Z}(A_i + e_i) + \mathcal{X}_1(e_i)$.

6. Input, output: we cannot simplify such a row of the chain complex, and we therefore keep the gauge operator $g_i^X = \mathcal{Z}(A_i) + \mathcal{X}_1(e_i) + \mathcal{X}_2(e_i)$.

The reduced chain complex now has exactly $n_Q + n_I + n_O$ nodes: one $\mathcal{Z}(e_i)$ for every wire $i$, plus $\mathcal{X}_1(e_i)$ if it is an input wire and $\mathcal{X}_2(e_i)$ if it is an output wire. Moreover, it has one gauge operator per wire, connecting to $\mathcal{X}_1(e_i)$ ($\mathcal{X}_2(e_i)$) for input (output) qubits, as well as all the nodes in $\mathcal{Z}(A_i + b_i e_i) = \mathcal{Z}((A+B)_i)$. Finally, every input stabilizer $j$ corresponds to a gauge operator $g_j^S = \mathcal{X}_1(S_j^X) + \mathcal{Z}(S_j^Z)$. Putting those gauge operators in a matrix form gives exactly the G matrix of Eq. (81).

So far, we have shown the existence of a fault-tolerant map

$$ \begin{array}{ccc} C_2 & \xrightarrow{G^T} & C_1 \xrightarrow{H\Omega} C_0 \\ \downarrow_{f_2} & & \downarrow_{f_1} & \downarrow_{f_0} \\ C'_2 & \xrightarrow{G'T} & C'_1 & \xrightarrow{\partial'_1} C'_0 \end{array} $$
It remains to show that $H' = \partial'_1$, i.e., the detectors of the spacetime code transform into the cluster state detectors, which we defined as the elements $x \in \ker(G)$ such that either $(x_I|x_{\tilde{I}}) \in S$ or $(x_O|x_{\tilde{O}}) = 0$. We will first show that every spacetime code stabilizer maps into a cluster state detector under our fault-tolerant map. We will then show that every cluster state detector comes from a spacetime code stabilizer.

Let us start by showing that every spacetime code stabilizer maps into a cluster state detector. Let $s \in C_0$ be a spacetime code stabilizer and $S = H^Ts$ its binary symplectic representation. Let $x = (H\Omega)^Ts$ be its representation in $C_1$ (i.e. $S$ with $X$ and $Z$ exchanged), let $s' = f_0(s) \in C'_0$, and let $x' = \partial'_1 s' \in C'_1$. We know that $x \in \ker(G'^T)$ by the chain complex condition of $C'_\bullet$. We therefore just need to show that either $(x'_I|x'_{\tilde{I}}) \in S$ or $(x'_O|x'_{\tilde{O}}) = 0$. We first observe that $x$ and $x'$ are supported on the same rows of the chain complex, since we only applied rule A on gauge operators connecting nodes of the same row. In particular, $x$ and $x'$ have support on the same input and output rows. By Proposition 4.1, we know that either $S_{I,1} \in S$ or $S_{O,2} = S_{O,3} = 0$. In the first case, since for every input row $i$, $Z_1(e_i)$ maps to $Z(e_i)$ (physical input node) and $X_1(e_i)$ maps to $X_1(e_i)$ (virtual input node), we have $(x'_I|x'_{\tilde{I}}) \in S$ (since $S$ and $x$ have $X$ and $Z$ exchanged). In the second case, since $f$ cannot map a stabilizer not supported on output nodes to a stabilizer supported on them by the previous observation, we must have $x_{\tilde{O}} = x_O = 0$.

We now show that every cluster state detector comes from a spacetime code stabilizer. Let $x' \in \ker(G')$ such that either $(x'_I|x'_{\tilde{I}}) \in S$ or $(x'_O|x'_{\tilde{O}}) = 0$. We want to show that there exists a spacetime stabilizer $s \in C_0$ such that $x' = f_1((H\Omega)^Ts)$. Let us map back $x'$ to a vector $x \in C_1$ the following way: every $Z$-type node in the support of $x'$ is mapped to the corresponding three nodes $Z_{i,1}$, $Z_{i,2}$ and $Z_{i,3}$ of $C_\bullet$. Every $X$-type input node in the support of $x'$ is mapped to the input node $X_{i,1}$. Every $X$-type output node is mapped to the two output nodes $X_{i,2}$ and $X_{i,3}$. It is easy to see that applying $f_1$ to this new vector $x$ gives us back $x'$. Moreover, since input nodes map to input nodes and output nodes to output nodes, it is clear that $x$ is a spacetime stabilizer by Proposition 4.1. Therefore, there exists $s$ such that $x' = f_1(x) = ((H\Omega)^Ts)$, showing that any cluster state detector is in the image of a spacetime stabilizer. $\square$

# 5 Cluster state complex from a Clifford circuit

The goal of this section is to give a constructive proof of the following theorem:

**Theorem 5.1.** Let $C$ a Clifford circuit made of single-qubit Clifford gates, control-Pauli gates (where the Pauli operator can be multi-qubit) and single-qubit Pauli measurements at the end of the circuit. Then there exists an MBQC circuit equivalent to $C$.

Note that different compilations of a given unitary with different sets of gates can give rise to spacetime codes with different distances. For instance, while a SWAP gate preserves the weight of any input Pauli error, its compilation into three CNOTs leads to some error-spreading that can decrease the distance of a code, as shown in Fig. 13. However, we will show that for the specific case of the compilation of our initial Clifford circuit into its MBQC version, the chain complexes are equivalent.

The proof works by progressively transforming circuit elements of the original Clifford circuit until a fully measurement-based circuit is obtained, that is, a circuit made only of
<figure><img src="image_22.png" /><figcaption>Figure 13: SWAP gate vs CNOT compilation. We draw the circuits on the left, and the *X* connected component of the gauge part of the chain complexes on the right. While the two circuits represent the same channel, they do not have equivalent chain complexes: the weight-3 gauge nodes cannot be reduced to weight-2 gauge nodes through fault-tolerant maps. This formalizes the observation that weight-1 *X* errors happening on the top wire before the last CNOT propagate into weight-2 errors, thereby potentially reducing the distance of a spacetime code containing this component.</figcaption></figure>

ancilla qubits initialized in the $|+\rangle$ state, a CZ network, and final Pauli measurements. It is made of two main steps:

1. Compiling the single-qubit gates into H and HS gates, and the controlled-Pauli gates into CZ networks. This involves compiling some H gates into their MBQC version when Y measurements are present. This is the content of Section 5.2.

2. Compiling all the H and HS gates into their MBQC version and merging all the CZ networks. This can involve adding additional pairs of H gates in-between certain CZ networks. This is the content of Section 5.4.

Section 5.1 and Section 5.3 provide lemmas and propositions that are useful for the rest of the proof.

We often consider partial chain complexes associated to particular circuit elements, and we define input (output) nodes of such a partial chain complex to be those nodes corresponding to the *X* and *Z* spacetime operators at the beginning (end) of the circuit element on the wires that are not initialized (measured) on that circuit element. We will always represent them by wires with ellipses, on the left for input nodes and on the right for output nodes. Furthermore, we require that input and output nodes are preserved throughout any transformation. To transform a circuit element while preserving the fault-tolerant properties of the full circuit that contains it, we use rules A and B, introduced in Section 2.4, on the partial chain complex corresponding to that circuit element.

An important observation that makes the diagrammatic proofs below work, is that applying rules A and B to a given partial chain complex does not change the support of the detectors on the input and output nodes. Therefore, any element of the kernel of the gauge group that came from a spackle or a backle in the original circuit, will still come from the same spackle or backle after the transformation. Consequently, while the detectors of a circuit element are not fully defined without considering the full circuit, showing that the gauge part of the partial chain complex transforms correctly is enough to show that the detectors
transform into the detectors as well. Thus, we will not need to draw detector nodes when
deriving the equivalence of two partial chain complexes coming from circuit elements.

**5.1 General lemmas**

We start by proving a few preliminary lemmas that will be useful throughout this section and
the next.

**Lemma 5.1.** *Inserting two successive Hadamard gates in a circuit preserves its equivalence class.*

*Proof.* Using the reduction rule A shows that the chain complexes of the two circuits, drawn below, are equivalent:

<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /></figure>

**Lemma 5.2.** Let $U$ be a multi-qubit unitary gate that can be written as $U = U'H_i$, where $H_i$ is a Hadamard gate applied on qubit $i$ and $U'$ another unitary gate. Then any circuit with the gates $H_i$ and $U'$ applied at successive time steps is equivalent to the circuit with the gate $U$. This can be represented by the following circuit equivalence:

<figure><img src="image_25.png" /></figure>

The same result applies if $H_i$ is applied after $U'$.

*Proof.* Starting from the circuit element on the right-hand side, we apply rule A between the first and second timesteps of every wire. This gives us the circuit element of the left-hand side.
□

<figure><img src="image_26.png" /></figure>
**Lemma 5.3.** Any gate made of Hadamard gates sandwiched between two networks of CZs can be compiled into a single CZ network as follows:

<figure><img src="image_27.png" /></figure>

*Proof.* Let us begin by setting up some notation. Let $n$ be the number of wires of the circuit on the left, and $a$ the number of wires containing a Hadamard. Without loss of generality, we assume that the Hadamard gates lie on the first $a$ rows of the circuit, as in the circuit above. Let $A(B)$ the adjacency matrix associated to the first (second) CZ network. Let $e_i \in \mathbb{Z}_2^n$ be the vector containing a 1 at position $i$ and 0 everywhere else, for any $i \in \{1, \dots, n\}$. For any matrix $M$, we write $M_i := Me_i$. We use $\odot$ for the element-wise multiplication of vectors. Given the chain complex of a circuit, a column $j$ of that circuit, and a binary vector $v$, we write $\mathcal{X}_j(v) (\mathcal{Z}_j(v))$ for the set of all $X(Z)$ nodes of the chain complex on column $j$ and row $i$ for all $i$ such that $v_i = 1$.

We can now characterize the chain complex associated to the circuit on the left. Let $\mathcal{H} = \{1, \dots, a\}$ the set of rows containing a Hadamard, and $h$ the indicator vector of the set, i.e. $h_i = 1$ if and only if $i \in \mathcal{H}$. We use the notation $\bar{\mathcal{H}} = \{a, \dots, n\}$ and $\bar{h}$ for the rows that do not contain a Hadamard.

For every row $i \in \{1, \dots, n\}$, we have two gauge operators, one for the propagation of $X$ and one for the propagation of $Z$, that we denote $g_i^X$ and $g_i^Z$ respectively. If $i \in \mathcal{H}$, the $X$ operator on row $i$ propagates into $Z$'s after the gate through different pathways: through the Hadamard on that wire, through the CZ gates in $CZ_A$ connected to the wire $i$ and ending on a wire $j \in \bar{\mathcal{H}}$, and through those ending on a wire $j \in \mathcal{H}$, propagating to an $X$ with the Hadamard, and onto $Z$s through the gates in $CZ_B$. Through this last process, the $X$ operator on row $i$ also propagates into $X$'s after the gate on the wires $j \in \mathcal{H}$ connected to $i$ through $CZ_A$. Using vector notation, the resulting gauge operator can therefore be written as

$$g_i^X = \mathcal{X}_1(e_i) + \mathcal{X}_2(A_i \odot h) + \mathcal{Z}_2(e_i + A_i \odot \bar{h} + B(A_i \odot h)). \quad (93)$$

Similarly, the $Z$ operator on row $i$ propagates onto an $X$ on that wire, and onto $Z$s through
the second CZ network, resulting in the following gauge operator:

$$g_i^Z = \mathcal{Z}_1(e_i) + \mathcal{X}_2(e_i) + \mathcal{Z}_2(B_i). \qquad (94)$$

A similar analysis for the wires $i \in \tilde{\mathcal{H}}$ gives us the following gauge operators:

$$g_i^X = \mathcal{X}_1(e_i) + \mathcal{X}_2(e_i + A_i \odot h) + \mathcal{Z}_2(A_i \odot \bar{h} + B_i + B(A_i \odot h)), \qquad (95)$$

$$g_i^Z = \mathcal{Z}_1(e_i) + \mathcal{Z}_2(e_i). \qquad (96)$$

We now move to the circuit on the right. We write $\tilde{\mathcal{H}} = \{1, \dots, a\}$ for the set of rows that start with a $|+\rangle$, $\tilde{\mathcal{H}}' = \{a, \dots, 2a\}$ for the set of rows with a final measurement, and $\tilde{\mathcal{H}} = \{2a, a+n\}$ for the rest of the rows. As before, we denote by $\tilde{h}, \tilde{h}'$ and $\tilde{\bar{h}}$ their corresponding indicator vectors. We denote by $\tilde{g}_i^X$ and $\tilde{g}_i^Z$ the new gauge operators corresponding to the propagation of X and Z on every wire $i$. We use $\tilde{A}$ and $\tilde{B}$ to denote the adjacency matrices of the CZ networks now extended to all the new wires, and $\{\tilde{e}_i\}_i$ the canonical basis of $\mathbb{Z}_2^{n+a}$. We also define a new adjacency matrix $C$ for the new CZ network in the middle. To construct the chain complex, we first note that each single-qubit Z operator before the gate propagates into a single Z operator on that same wire, forming a weight-2 gauge operator, i.e. for every $i \in \{1, \dots, n+a\}$ we have

$$\tilde{g}_i^Z = \mathcal{Z}_1(\tilde{e}_i) + \mathcal{Z}_2(\tilde{e}_i). \qquad (97)$$

We also have single-qubit gauge operators on each wire $i \in \tilde{\mathcal{H}} \cup \tilde{\mathcal{H}}'$, corresponding either to the initial state or to the final measurement, and connected to an X-type node.

The rest of the gauge operators correspond to the propagation of X on each wire. For every wire $i$, we have

$$\tilde{g}_i^X = \begin{cases} \mathcal{X}_1(\tilde{e}_i) + \mathcal{X}_2(\tilde{e}_i) + \mathcal{Z}_2(C\tilde{e}_i + \tilde{B}_i) & i \in \tilde{\mathcal{H}}, \\ \mathcal{X}_1(\tilde{e}_i) + \mathcal{X}_2(\tilde{e}_i) + \mathcal{Z}_2(C\tilde{e}_i + \tilde{A}_i) & i \in \tilde{\mathcal{H}}', \\ \mathcal{X}_1(\tilde{e}_i) + \mathcal{X}_2(\tilde{e}_i) + \mathcal{Z}_2(\tilde{A}_i + \tilde{B}_i) & i \in \tilde{\mathcal{H}}. \end{cases} \qquad (98)$$

We now transform this chain complex into the chain complex of the original circuit. We start by contracting the weight-1 gauge operators using rule B, eliminating the nodes $X_1(\tilde{e}_i)$ for $i \in \mathcal{H}$ and $X_2(\tilde{e}_i)$ for $i \in \mathcal{H}'$. We also contract the weight-2 gauge operators $\tilde{g}_i^Z$ for all $i$, thereby replacing each $\mathcal{Z}_2(\tilde{e}_i)$ by $\mathcal{Z}_1(\tilde{e}_i)$. The gauge operators now become

$$\tilde{g}_i^X = \begin{cases} \mathcal{X}_2(\tilde{e}_i) + \mathcal{Z}_1(C\tilde{e}_i + \tilde{B}_i) & i \in \tilde{\mathcal{H}}, \\ \mathcal{X}_1(\tilde{e}_i) + \mathcal{Z}_1(C\tilde{e}_i + \tilde{A}_i) & i \in \tilde{\mathcal{H}}', \\ \mathcal{X}_1(\tilde{e}_i) + \mathcal{X}_2(\tilde{e}_i) + \mathcal{Z}_1(\tilde{A}_i + \tilde{B}_i) & i \in \tilde{\mathcal{H}}. \end{cases} \qquad (99)$$

We then relabel Z nodes to $\mathcal{Z}_1$ if they are in $\tilde{\mathcal{H}}'$ and $\mathcal{Z}_2$ if they are in $\tilde{\mathcal{H}}$ or $\tilde{\mathcal{H}}'$. With this new labeling, Eq. (99) becomes

$$\tilde{g}_i^X = \begin{cases} \mathcal{X}_2(\tilde{e}_i) + \mathcal{Z}_1(C\tilde{e}_i) + \mathcal{Z}_2(\tilde{B}_i) & i \in \tilde{\mathcal{H}}, \\ \mathcal{X}_1(\tilde{e}_i) + \mathcal{Z}_1(\tilde{A}_i \odot \tilde{h}') + \mathcal{Z}_2(C\tilde{e}_i + \tilde{A}_i \odot \tilde{\bar{h}}) & i \in \tilde{\mathcal{H}}', \\ \mathcal{X}_1(\tilde{e}_i) + \mathcal{X}_2(\tilde{e}_i) + \mathcal{Z}_1(\tilde{A}_i \odot \tilde{h}') + \mathcal{Z}_2(\tilde{A}_i \odot \tilde{\bar{h}} + \tilde{B}_i) & i \in \tilde{\mathcal{H}}. \end{cases} \qquad (100)$$
The objective is to now remove the connections between $\mathcal{X}_1$ and $\mathcal{Z}_1$ nodes in last two lines of Eq. (100). For this, we perform the following change-of-basis operation for all $i \in \tilde{\mathcal{H}}' \cup \tilde{\mathcal{H}}$:

$$ \tilde{g}_i^X \leftarrow \tilde{g}_i^X + \sum_{j \in \text{supp} C(\tilde{A}_i \odot \tilde{h}')} \tilde{g}_j^X, \qquad (101) $$

which cancels all the $\mathcal{Z}_1$ nodes and gives us the following new gauge operators $\tilde{g}_i'^X$:

$$ \tilde{g}_i'^X = \begin{cases} \mathcal{X}_2(\tilde{e}_i) + \mathcal{Z}_1(C\tilde{e}_i) + \mathcal{Z}_2(\tilde{B}_i) & i \in \tilde{\mathcal{H}}, \\ \mathcal{X}_1(\tilde{e}_i) + \mathcal{X}_2(C(\tilde{A}_i \odot \tilde{h}')) + \mathcal{Z}_2(C\tilde{e}_i + \tilde{A}_i \odot \tilde{h} + \tilde{B}(C(\tilde{A}_i \odot \tilde{h}')) & i \in \tilde{\mathcal{H}}', \\ \mathcal{X}_1(\tilde{e}_i) + \mathcal{X}_2(\tilde{e}_i) + \mathcal{X}_2(C(\tilde{A}_i \odot \tilde{h}')) + \mathcal{Z}_2(\tilde{A}_i \odot \tilde{h} + \tilde{B}_i + \tilde{B}(C(\tilde{A}_i \odot \tilde{h}')) & i \in \tilde{\mathcal{H}}. \end{cases} \qquad (102) $$

We notice that $\mathcal{X}_1(\tilde{e}_i)$ and $\mathcal{Z}_1(\tilde{e}_i)$ are only present in a gauge operator for $i \in \tilde{\mathcal{H}}' \cup \tilde{\mathcal{H}}$, while $\mathcal{X}_2(\tilde{e}_i)$ and $\mathcal{Z}_2(\tilde{e}_i)$ are only present for $i \in \tilde{\mathcal{H}}' \cup \tilde{\mathcal{H}}$. We can therefore relabel the error nodes as follows:

$$ \mathcal{X}_1(\tilde{e}_i) \mapsto \mathcal{X}_1(e_{i-a}) \quad i \in \tilde{\mathcal{H}}' \cup \tilde{\mathcal{H}}, \qquad (103) $$

$$ \mathcal{Z}_1(\tilde{e}_i) \mapsto \mathcal{Z}_1(e_{i-a}) \quad i \in \tilde{\mathcal{H}}' \cup \tilde{\mathcal{H}}, \qquad (104) $$

$$ \mathcal{X}_2(\tilde{e}_i) \mapsto \begin{cases} \mathcal{X}_2(e_i) & i \in \tilde{\mathcal{H}}, \\ \mathcal{X}_2(e_{i-a}) & i \in \tilde{\mathcal{H}}, \end{cases} \qquad (105) $$

$$ \mathcal{Z}_2(\tilde{e}_i) \mapsto \begin{cases} \mathcal{Z}_2(e_i) & i \in \tilde{\mathcal{H}}, \\ \mathcal{Z}_2(e_{i-a}) & i \in \tilde{\mathcal{H}}. \end{cases} \qquad (106) $$

This map is an isomorphism in the middle space of the chain complex and therefore trivially induces a fault-tolerant map. Under this transformation, we observe that $\tilde{g}_i'^X$ maps to $g_i^Z$ for $i \in \{1, \dots, a\}$, and to $g_{i-a}^X$ for $i \in \{a, \dots, n+a\}$. By introducing new error nodes $\mathcal{Z}_1(e_i)$ for $i \in \{a, \dots, n+a\}$, and weight-2 gauge operators that map them to $\mathcal{Z}_2(e_i)$, we recover all the gauge operators of the original chain complex. $\square$

## 5.2 Compilation of the circuit into H, HS and CZ networks

In this first step of the mapping, we show that all the gates of the circuit can be compiled into H, HS and CZ networks, while remaining in the same equivalence class of chain complexes. We begin by compiling all the single-qubit gates.

**Proposition 5.1.** All the single-qubit gates of the circuit can be compiled into H and HS without changing the equivalence class of the circuit

*Proof.* We first note that any Pauli gates can be removed from the circuit without changing the corresponding chain complex. Indeed, since the circuit is Clifford, Pauli operators commute through it, resulting in either sign changes in the measurements or output Pauli operators. In both cases, the detectors and gauge operators only change up to signs, which are modded out in our construction.
and both CNOT and CY can be compiled using CZ and H as:

$$ \text{CNOT gate} = \text{H gate} \quad (109) $$

$$ \text{CY gate} = \text{CNOT gate} = \text{H gate} \quad (110) $$

Using the compilations of CX and CY into Hadamard gates and CZs, as well as Lemma 5.2 to push the H gates away from the blue box, we compile the circuit above to the following equivalent circuit:

<figure><img src="image_28.png" /></figure>

To get a single CZ network in the middle, we compile the Hs into their measurement-based versions, using Lemma 5.3. □

## 5.3 Measurement-based H and HS gates

The next step is to show that H and HS gates are equivalent to their measurement-based version.

**Proposition 5.3.** The two following circuits, corresponding to a Hadamard gate and its measurement-based version, are equivalent:

<figure><img src="image_29.png" /></figure>

*Proof.* While this theorem could be seen as a special case of Lemma 5.3 where the two CZ networks are empty, we choose to do a more direct proof for clarity here. Here are the circuits and corresponding chain complexes whose equivalence we want to show:
<figure><img src="image_30.png" /></figure>

Starting from the chain complex of the measurement-based Hadamard, we apply rule A on the two weight-2 gauge operators linking the Z nodes, and rule B on the two weight-1 gauge operators. This gives us the following new chain complex:

<figure><img src="image_31.png" /></figure>

which is the same as the chain complex of the original Hadamard. □

We now move on to the HS gate.

**Proposition 5.4.** The two following circuits, corresponding to an HS gate and its measurement-based version, are equivalent:

$$ \boxed{\text{HS}} \sim \text{Y} \quad (111) $$

*Proof.* We can compare the chain complexes for the direct and MBQC implementations

<figure><img src="image_32.png" /></figure>
and use the following sequence of fault-tolerant maps to prove their equivalence:

<figure><img src="image_33.png" /></figure>

## 5.4 Merge of CZ networks

Our circuit is now composed of CZ networks, H gates and HS gates. The objective of this section is to show that we can turn the H and HS gates into their measurement-based versions, yielding a circuit only composed of CZ networks, and that all those CZ networks can be merged.

We begin by noting that, in general, CZ networks cannot be merged. For instance, the following two circuits are not equivalent:

<figure><img src="image_34.png" /></figure>

since the circuit on the left propagates single-qubit X errors between the two CZ into weight-2 errors, while the circuit on the right is equivalent to the identity gate and does not propagate any weight-1 error into a weight-2 error. However, as we will see, we can merge CZ networks after turning all the single-qubit gates into their measurement-based versions, as long as all the original CZ networks are Hadamard-separated.

**Definition 5.1** (Hadamard separation). We say that a pair of CZ networks is Hadamard-separated if, for each qubit of their intersection, the first CZ network is immediately followed by an H gate on that qubit, before any other potential gates. We say that a circuit, compiled into CZ networks, H and HS gates, is Hadamard-separated if every pair of CZ networks is Hadamard-separated.

We start by turning our circuit into an equivalent Hadamard-separated circuit. For this, we identify all the pairs of CZ networks that are not separated by any gate on some of their common wires, and insert a pair of Hadamard gates on those wires in between the two networks. We also identify all the HS gates immediately following a CZ network, and insert a pair of Hadamard gates before each such HS gate. By Lemma 5.1, the new circuit is equivalent to the original one. As an example, our method turns two successive CZ gates into a single CZ network the following way:
<figure><img src="image_35.png" /></figure>

Our proof that we can merge Hadamard-separated CZ networks splits into the following steps:

1. Showing that a CZ network can be merged with all the measurement-based H gates on its right.

2. Showing that any HS gate can be merged with a network resulting from the merge of a network with an H gate on the left of the HS gate.

3. Showing that the resulting CZ network can be merged with all the CZ networks that immediately follow it.

4. Showing that a CZ network can be merged with all the measurement-based H and HS gates on its left. This last part is useful in the case of a circuit starting with some H and HS gates, without any CZ network on their left to be merged with.

**Lemma 5.4.** Any H gate can be merged into a CZ network on its right by compiling it into its measurement-based version. Moreover, any HS gate with an H gate and a CZ network on
its right can be merged into a single CZ network.

<figure><img src="image_36.png" /></figure>

<figure><img src="image_37.png" /></figure>

*Proof.* Eq. (112) is a direct consequence of Lemmas 5.2 and 5.3:

<figure><img src="image_38.png" /></figure>

Using this equivalence, along with Eq. (111) to compile the HS gate, showing Eq. (113) comes
down to showing

<figure><img src="image_39.png" /></figure>

The left circuit is associated to the following chain complex:
<figure><img src="image_40.png" /></figure>

where for every row, we have contracted the three Z nodes of the row using rule A, and have placed the resulting node on the right of all the X nodes. Moreover, we have put ellipses on the left-most gauge operator of each row of the CZ network, indicating that those gauge operators are connected to the Z nodes at rows depending on the adjacency matrix of the CZ network.

A first application of rules A and B gives the following equivalent diagram:

<figure><img src="image_41.png" /></figure>

Using rule A on the first gauge operator on the second row then gives:

<figure><img src="image_42.png" /></figure>

Finally, using rule B to add a new X node, we recover exactly the chain complex of the circuit on the right of Eq. (115):
<figure><img src="image_43.png" /></figure>

☐

**Lemma 5.5.** We have the equivalence:

<figure><img src="image_44.png" /></figure>

*Proof.* The left-hand side of Eq. (116) is associated to the following chain complex:
<figure><img src="image_45.png" /></figure>

where we have labeled the ellipses A and B depending on whether a gauge operator corresponds to $CZ_A$ or $CZ_B$. A first application of rules A and B gives the following equivalent diagram:
<figure><img src="image_46.png" /></figure>

We then apply rule B on the third and fourth rows to eliminate the weight-1 gauge operators, rule A to merge the new weight-2 gauge operators of those rows, and finally rule B to add a new X node:
<figure><img src="image_47.png" /></figure>

This last diagram represents the chain complex at the right-hand side of Eq. (113), showing the desired circuit equivalence. ☐

The final step of the MBQC mapping is to merge any H or HS gate at the beginning of the circuit into a CZ network on its right. This can be done using the following lemma:
**Lemma 5.6.** We have the following circuit equivalences:

<figure><img src="image_48.png" /></figure>

<figure><img src="image_49.png" /></figure>

*Proof.* The equivalence in Eq. (117) is direct consequence of Lemma 5.2 and Lemma 5.3. To prove Eq. (118), we start by compiling the HS gate using Eq. (111). It remains to show that:

<figure><img src="image_50.png" /></figure>

The left-hand side of this equation is associated to the following chain complex, where we have used the same contraction of Z nodes as in the proof of Lemma 5.4:

<figure><img src="image_51.png" /></figure>
A first application of rules A and B gives the following equivalent diagram:

<figure><img src="image_52.png" /></figure>

We now use rule A on the second row, followed by rule B to add a new X node:

<figure><img src="image_53.png" /></figure>

This last diagram corresponds to the chain complex of the circuit at the right-hand side of Eq. (118). □

## 5.5 Example: transversal logical gate

As an application of our circuit transformation technique, we derive here the cluster state complex corresponding to the application of a transversal $S$ gate on the Bell state stabilized by $X^{\otimes 2}$ and $Z^{\otimes 2}$, with measurement of those stabilizers before and after the application of the gate. This protocol is a simplified version of the transversal $S$ gate applied to the [[4, 2, 2]] code or more general 2D color codes [27, 83, 84]. Since applying $S^{\otimes 2}$ to the Bell state only changes its stabilizers up to a sign, the circuit should have at least two spacetime stabilizers. Here is the circuit corresponding to the protocol, with the two detectors labeled in blue and
red:

<figure><img src="image_54.png" /></figure>

Since $X^{\otimes 2}$ turns into $Y^{\otimes 2}$ through the application of $S^{\otimes 2}$, the associated detector involves the measurement of both $X^{\otimes 2}$ and $Z^{\otimes 2}$ after the gate. The reason we change the measurement order before and after the gate is to obtain a more compact MBQC circuit, as we will soon understand.

To turn this circuit into an MBQC circuit, the first step is to rewrite the controlled-Pauli gates using CZ gates, and compile the S gate into H and HS gates:

<figure><img src="image_55.png" /></figure>

We then move the Hadamard gates out of the blue boxes using Lemma 5.2, and compile the two successive H gates coming after the HS gate into the identity. This is the trick that will give us a more compressed MBQC circuit and the reason we chose to measure the $X^{\otimes 2}$
operator first after the transversal gate.

<figure><img src="image_56.png" /></figure>

We now iteratively apply Lemma 5.6 and Lemma 5.5 to compile the H and HS gates into their MBQC versions and merge the resulting CZ networks. Starting with the Hadamard gates on the left, we obtain the following circuit:

<figure><img src="image_57.png" /></figure>
Next, we compile the H and HS gates, giving the following circuit:

<figure><img src="image_58.png" /></figure>
Finally, compiling the last H gates gives us:

<figure><img src="image_59.png" /></figure>
We can now draw the corresponding cluster state complex, in its compressed representation. To make the figure more readable, we omit the detector nodes, but circle in green the support of the two detectors derived above (the red-labeled one on the left figure and the blue-labeled one on the right figure):

<figure><img src="image_60.png" /></figure>

# 6 Cluster state complex from a stabilizer code

## 6.1 CSS stabilizer codes

We show here that we recover the usual foliated cluster state when the input circuit corresponds to a phenomenological memory experiment with a CSS code [49]. Two examples of cluster state complexes coming from a CSS code are shown in Fig. 14.

**Theorem 6.1.** Consider the circuit made of $T$ rounds of stabilizer measurements of an [[*n*, *k*, *d*]] CSS stabilizer code, where $m_X$ X stabilizers and $m_Z$ Z stabilizers are measured each round using some ancilla qubits, and errors are assumed to only happen in-between successive rounds. Let $H^X$ and $H^Z$ be the parity-check matrices associated to the X and Z stabilizers, respectively. This circuit is equivalent to a cluster state complex described by the following graph (in the compressed representation):

* It contains $2T+3$ layers {0, ..., $2T+2$} of error nodes, where each odd layer $ℓ = 2i+1$ (even layer $ℓ = 2i$) contains *n* data nodes $q_1^{(ℓ)}$, ..., $q_n^{(ℓ)}$ and, if $ℓ \le 2T$, $m_Z$ ($m_X$) ancilla nodes $a_1^{(ℓ)}$, ..., $a_{m_Z}^{(ℓ)}$ ($a_1^{(ℓ)}$, ..., $a_{m_X}^{(ℓ)}$). The nodes on layers 0 and $2T+2$ are virtual, while all the other nodes are physical.

* Within a given layer $ℓ \le 2T$, data nodes and ancilla nodes (both physical and virtual) are connected to each other according to the matrices $H^Z$ (for odd layers) and $H^X$ (for even layers), seen as biadjacency matrices, that is, $a_i^{(ℓ)}$ and $q_j^{(ℓ)}$ are connected if and only if $H_{ij}^Z = 1$ (for odd layers) or $H_{ij}^X = 1$ (for even layers).
<figure><img src="image_61.png" /><figcaption>Figure 14: Cluster state complexes of two foliated CSS codes, with stabilizer groups $\langle ZZ \rangle$ (a and b) and $\langle XX \rangle$ (c and d). (a) and (c) Compressed representation of the cluster state complex, without detector nodes for clarity. (b) and (d) Compressed co-representation of the cluster state complex, with detector nodes.</figcaption></figure>

• For $1 \le l \le 2T$, every data node $q_i^{(l)}$ is connected to the data node $q_i^{(l+1)}$ in the next layer. For $l = 0$, there is directed edge from $q_i^{(l+1)}$ to $q_i^{(l)}$. For $l = 2T + 1$, there is directed edge from $q_i^{(l)}$ and $q_i^{(l+1)}$.

• For every ancilla node $a_i^{(\ell)}$ ($1 \le \ell \le 2T$) connected to a set of data nodes $q_{j_1}^{(\ell)}, \dots, q_{j_k}^{(\ell)}$, we have a detector node connected to $a_i^{(\ell)}$, $q_{j_1}^{(\ell+1)}, \dots, q_{j_k}^{(\ell+1)}$, $a_i^{(\ell+2)}$ if $\ell \le 2T - 2$, and $q_{j_1}^{(\ell+3)}, \dots, q_{j_k}^{(\ell+3)}$ if $\ell = 2T - 1$. These detectors correspond to spackles in the spacetime code of the circuit. Corresponding to the backles, we also have one detector node per ancilla node $a_i^{(1)}$ on layer one, connected to $a_i^{(1)}$ and $q_{j_1}^{(0)}, \dots, q_{j_k}^{(0)}$, and one per ancilla node $a_i^{(2)}$ on layer two, connected to $a_i^{(2)}$ and $q_{j_1}^{(1)}, \dots, q_{j_k}^{(1)}$. Finally, we have one detector node per virtual ancilla node, connected only to it.

*Proof.* The circuit consists of several rounds of simultaneous measurements of all the stabilizers, where errors are assumed to happen in-between measurement rounds, on both the data qubits and ancilla qubits used to perform the measurements. For instance, two rounds of
stabilizer measurements correspond to the following circuit:

<figure><img src="image_62.png" /></figure>

where the sets {$S_i^X$} and {$S_i^Z$} are generators of the X and Z stabilizer groups respectively. We also provide (in red) an example of detector, corresponding the repeated measurement of $S_1^Z$ in the two rounds. The Z-part of this detector is in the support of $S_1^Z$.

We can transform every X stabilizer measurement into Z measurements by inserting Hadamard gates before and after the CX gates. Denoting by $\bar{S}_i^X$ the operator coming from $S_i^X$ where every X has been turned into a Z, and using Lemma 5.2, we get the following equivalent circuit:
<figure><img src="image_63.png" /></figure>

We finally use Lemma 5.3 to compile the Hadamard gates into their measurement-based versions within each blue box, and Lemmas 5.5 and 5.6 to merge the CZ networks at different rounds, giving us the following circuit for our two rounds of measurements:
<figure><img src="image_64.png" /></figure>

Since this circuit is made only of a CZ network with qubits either initialized in the $|+\rangle$ state or uninitialized, and measurements in the X basis, it defines an MBQC pattern MBQC($A, \mathcal{I}, \mathcal{O}, b = 0$). Using Definition 4.2, we get the compressed representation by adding $2n + m_X + m_Z$ virtual nodes to represent X errors at the input and output wires of the circuit, as well as gauge operators corresponding to the X and Z stabilizers of the input qubits. However, each one of
the $m_Z$ new gauge operators associated to an input $Z$ stabilizer is the same as the gauge operator associated to the first measurement of this $Z$ stabilizer, and can therefore be removed from the graph. The new graph corresponds exactly to the one described in the theorem statement.

The pure $X$-type detector drawn on the circuit above (corresponding to successive measurements of $S_1^Z$) is supported on the ancilla qubits used to measure $S_1^Z$ in layers one and three, and on the data qubits in round two. This readily generalizes to the successive measurement of any other stabilizer $S_i^Z$ or $S_i^X$.

It remains to derive the input and output detectors described in the theorem statement. Since the part of the original circuit representing the first round of $Z$ measurements has not been changed during the transformation, the following detector, corresponding to the backle of the first $S_1^Z$ measurement, remains a detector after the transformation:

<figure><img src="image_65.png" /></figure>

where the $Z$ labels on the data qubits represent the support of $S_1^Z$. This spacetime stabilizer becomes the detector connecting $a_1^{(1)}$ to $q_{j_1}^{(0)}, \dots, q_{j_k}^{(0)}$ in the compressed representation of the cluster state complex. We can also derive the detectors corresponding to the backle of the first round of $X$-type stabilizer measurements. For instance, for $S_X^1$ we draw the backle of the $X$ measurements of both the ancilla qubit used to measure $S_X^1$ and of the data qubits in
the support of $S_X^1$ (due to the replacement of the Hadamard gates by their MBQC version):

<figure><img src="image_66.png" /></figure>

where the X labels on the data qubits represent the support of $\bar{S}_1^X$. They allow the Zs to cancel on the top wires. This gives us the detector connecting $a_1^{(2)}$ to $q_{j_1}^{(1)}, \dots, q_{j_k}^{(1)}$ in the compressed representation of the cluster state complex.

Let us now derive the detectors corresponding to the spackle of X and Z measurements at the last round. The spacetime stabilizer corresponding to the last measurement of $S_1^Z$ is
as follows:

<figure><img src="image_67.png" /></figure>

where the X and Z labels on the data qubits both represent the support of $S_1^Z$. This spacetime stabilizer becomes a detector connecting $a_1^{(2T-1)}$ with $q_{j_1}^{(2T)}$, ..., $q_{j_k}^{(2T)}$ and $q_{j_1}^{(2T+2)}$, ..., $q_{j_k}^{(2T+2)}$ (due to the Z's on the last layer of data qubits) in the compressed representation of the cluster state complex. Similarly, the spacetime stabilizer corresponding to the final measurement of
$S_1^X$ is as follows:

<figure><img src="image_68.png" /></figure>

and turns into a detector connecting $a_1^{(2T)}$ with $q_{j_1}^{(2T+1)}, \dots, q_{j_k}^{(2T+1)}$ in the compressed representation of the cluster state complex.

Finally, the detectors connected to the virtual ancilla nodes come from the construction of the augmented cluster state complex (the identity part of $\tilde{H}$) in Definition 4.2. □

## 6.2 General stabilizer codes

We derive here the cluster state complex for a non-CSS code phenomenological memory experiment. The corresponding MBQC circuits are the same as the one described in [50]. Examples of such cluster state complexes are given in Fig. 15.

**Theorem 6.2.** Consider the circuit made of $T$ rounds of stabilizer measurements of a general [[*n*, *k*, *d*]] stabilizer code, where *m* stabilizer generators {*S*₁, ..., *S*ₘ} are measured each round using some ancilla qubits, and errors are assumed to only happen in-between successive rounds. Let *H* be the parity-check matrices associated to *S*₁, ..., *S*ₘ, written in the binary symplectic format. We write *H* = (*H*^X|*H*^Z) to distinguish the *X* part and the *Z* part of the parity-check matrix, and *S*ᵢ = (*S*ᵢ^X|*S*ⱼ^Z) to distinguish the *X* and *Z* parts of each stabilizer *S*ᵢ. The circuit is equivalent to a cluster state complex described by the following graph (in its compressed representation):

* It contains 2*T* + 3 layers {*0*, ..., 2*T* + 2}, where each layer *ℓ* contains *n* data nodes
<figure><img src="image_69.png" /><figcaption>Figure 15: Cluster state complexes of two foliated non-CSS codes, with stabilizer groups $\langle XZ \rangle$ (a and b) and $\langle XZ, ZX \rangle$ (c and d). (a) and (c) Compressed representation of the cluster state complex, without detector nodes for clarity. (b) and (d) Compressed co-representation of the cluster state complex, with detector nodes. In the second complex, the two ancilla nodes at each layer are connected due to the odd intersection between the X-part of XZ (i.e. $X_1$) and the Z-part of ZX (i.e. $Z_1$)</figcaption></figure>
$q_1^{(\ell)}, \dots, q_n^{(\ell)}$, and each odd layer $\ell \le 2T - 1$ contains $m$ ancilla nodes $a_1^{(\ell)}, \dots, a_m^{(\ell)}$. The nodes on layers 0 and $2T+2$ are virtual, while all the other nodes are physical.

* For any odd layer $\ell \le 2T - 1$, the ancilla node $a_i^{(\ell)}$ is connected to the data nodes at the same level according to $H_Z$ and at a level above according to $H_X$, that is, $a_i^{(\ell)}$ is connected to $q_j^{(\ell)}$ if and only if $H_{ij}^Z = 1$ and to $q_j^{(\ell+1)}$ if and only if $H_{ij}^X = 1$.

* The ancilla nodes $a_i^{(\ell)}$ and $a_j^{(\ell)}$ are connected if and only if $S_i^Z$ and $S_j^X$ have an intersection of odd weight, i.e. $|S_i^Z \cdot S_j^X| = 1$ modulo two. Note that for $i = j$, it means there is a self-loop on the node $a_i^{(\ell)}$ if and only if $S_i$ has an odd number of Y. For $1 \le \ell \le 2T$, every data node $q_i^{(\ell)}$ is connected to the data node $q_i^{(\ell+1)}$ in the next layer. For $\ell = 0$, there is a directed edge from $q_i^{(\ell+1)}$ to $q_i^{(\ell)}$. For $\ell = 2T+1$, there is a directed edge from $q_i^{(\ell)}$ and $q_i^{(\ell+1)}$.

* For every ancilla node $a_i^{(\ell)}$ ($1 \le \ell \le 2T$, $\ell$ odd) connected to a set of data node $q_{j_1}^{(\ell_1)}, \dots, q_{j_k}^{(\ell_k)}$ (with $\ell_1, \dots, \ell_k \in \{\ell, \ell+1\}$ and $j_1, \dots, j_k \in \{1, \dots, n\}$), we have a detector node connected to $a_i^{(\ell)}$, $q_{j_1}^{(\ell_1+1)}, \dots, q_{j_k}^{(\ell_k+1)}$, $a_i^{(\ell+2)}$ if $\ell \le 2T - 2$, and $q_{j_i}^{(2T+2)}$ for all $i$ such that $\ell_i = 2T$. These detectors correspond to spackles in the spacetime code of the circuit. Corresponding to the backles, we also have one detector node per ancilla node $a_i^{(1)}$ on the first layer, connected to $a_i^{(1)}$ and $q_{j_1}^{(\ell_1-1)}, \dots, q_{j_k}^{(\ell_k-1)}$. Finally, we have one detector node per virtual ancilla node, connected only to it.

*Proof.* One round of stabilizer measurements for a non-CSS code can be represented by the following circuit:

<figure><img src="image_70.png" /></figure>

where $M_i = X$ if there is an even number of Y in $S_i$, and $M_i = Y$ otherwise. This can be understood by noticing that for every CY in the decomposition of control-$S_i$, the initial X stabilizer of the $|+\rangle$ state propagates as follows:

$$ |+\rangle_X \rightarrow |+\rangle_Y \qquad (120) $$

Therefore, we need to measure the ancilla qubit in the $Y$ basis in order to measure $Y$ on the top qubit. Since every CY contributes to a $Z$ on the ancilla qubit when writing down the
Repeating this commuting process for all the stabilizers, our circuit takes the form:

<figure><img src="image_71.png" /></figure>

where $CZ_A$ is a network of CZ gates with adjacency matrix $A$, defined by $A_{ij} = 1$ if and only if $S_i^Z$ and $S_j^X$ have an odd intersection. We can now compile the control $S_i^X$ into H and CZ

<figure><img src="image_72.png" /></figure>

where $\bar{S}_i^X$ is the operator built from $S_i^X$ by turning every $X$ into a $Z$. Next we compile the H gates into their MBQC version using Lemma 5.3. Over two rounds of measurements, this gives the following circuit, where we also annotate an example detector, associated to
successive measurements of $S_1$:

<figure><img src="image_73.png" /></figure>

where we label in blue the Pauli operators acting on the support of $S_1^Z$ and in yellow those acting on the support of $S_1^X$. The initial $X$ operators on the ancilla wires (in red) propagate only to $M_1$ on the same wires due to the offsetting effect of the propagation of the blue $X$ operators (whenever $S_1^Z$ anticommutes with an $S_i^X$) and the $CZ_A$ gate. Moreover, it propagates to $M_1$ and not $X$ due to the possibility of $S_1^Z$ anticommuting with $S_1^X$, thereby propagating a $Z$ on this wire.

We can see that every round of measurements contributes to two teleportations of all the data qubits, and therefore to $2T + 1$ layers in the cluster state complex. Layers $\ell = 0$ and $\ell = 2T + 2$ are virtual layers representing $X$ errors on the input and output qubits. Moreover, every round of stabilizer measurements gives rise to $m$ ancilla qubits, which we place on the odd layers of the cluster state complex by convention. Finally, the CZ network of this circuit has the same graph as the one described in the theorem statements.

Moving on to the detector nodes, we can see that the detector corresponding to the
spacetime stabilizer displayed above (redundancy in two successive measurements of $S_1$), is connected to the ancilla nodes $a_1^{(\ell)}$ and $a_1^{(\ell+2)}$. Furthermore, this detector node is also connected the data qubits $q_{j_1}^{(\ell+1)}, \dots, q_{j_\alpha}^{(\ell+1)}$ and $q_{k_1}^{(\ell+2)}, \dots, q_{k_\alpha}^{(\ell+2)}$, where $q_{j_i}^{(t)}$ ($q_{k_i}^{(t)}$) are again the data qubits in the support of $S_1^Z$ ($S_i^X$) at the layer $t$. In other words, the detector node is connected to the data qubits one layer above those connecting the ancilla node, as stated in the theorem.

It remains to study the detector nodes corresponding to the input and output spacetime stabilizers. The detector corresponding to the last $S_1$ measurement has the following form in the circuit picture:

<figure><img src="image_74.png" /></figure>

where we again label in blue the Pauli operators acting on the support of $S_1^Z$ and in yellow those acting on the support of $S_1^X$. We can see that the corresponding detector node is connected to the ancilla qubit $a_1^{(2T-1)}$, as well as to the data qubits $q_{j_1}^{(2T)}$, ..., $q_{j_\alpha}^{(2T)}$, $q_{k_1}^{(2T+1)}$, ..., $q_{k_\beta}^{(2T+1)}$ and $q_{j_1}^{(2T+2)}$, ..., $q_{j_\alpha}^{(2T+2)}$, where $q_{j_i}^{(t)}$ ($q_{k_i}^{(t)}$) are again the data qubits in the support of $S_1^Z$ ($S_i^X$) at the layer $t$. The connection to data qubits at the layer $2T+2$ is due to the presence of Zs on the output qubits.

Finally, the detector corresponding to the first $S_1$ measurement has the following form in
the circuit picture:

<figure><img src="image_75.png" /></figure>

where again we labeled in blue the Pauli operators acting on the support of $S_1^Z$ and in yellow those acting on the support of $S_1^X$. This corresponds to a detector node connected to the ancilla qubit $a_1^{(1)}$, as well as to the data qubits $q_{j_1}^{(0)}$, ..., $q_{j_\alpha}^{(0)}$ and $q_{k_1}^{(1)}$, ..., $q_{k_\beta}^{(1)}$, where $q_{j_i}^{(t)}$ ($q_{k_i}^{(t)}$) are again the data qubits in the support of $S_1^Z$ ($S_1^X$) at layer $t$.

The final detectors connected only to the virtual ancilla node and again come from the construction of the augmented cluster state complex in Definition 4.2. □

# 7 Cluster state complex from a dynamical code

As our final example of mapping from codes to MBQC patterns, we consider the class of dynamical codes [1, 5, 68]. In the context of this work, we broadly define a *dynamical code* as a protocol running for $T$ rounds, such that a set $G^{(t)} = \{G_1^{(t)}, \dots, G_{m_t}^{(t)}\}$ of commuting Pauli operators is measured at each round $t \in \{1, \dots, T\}$. A similar definition of dynamical codes can be found in Fu and Gottesman [68]. We call the family of sets $\{G^{(t)}\}_{1 \le t \le T}$ the *measurement schedule* of the code.

Dynamical codes with a periodic function $t \mapsto G^{(t)}$ are called Floquet codes, and were introduced by Hastings and Haah as a broad generalization of stabilizer and subsystem codes [1]. The honeycomb code constructed in their work is a Floquet code of period 3 defined on a honeycomb lattice with qubits on vertices. For this code, $G^{(3t)}$, $G^{(3t+1)}$ and $G^{(3t+2)}$ are respectively the sets of XX, YY and ZZ Pauli operators associated with subsets of the edges the lattice. While the stabilizers and logical operators of the code change at each round, the logical information is preserved during the protocol and the presence of spacetime stabilizers in the corresponding circuit enable fault-tolerant error correction. Many variations of the
<figure><img src="image_76.png" /><figcaption>Figure 16: Schedule and round types for two dynamical variants of the [[4, 2, 2]]-code. (a) [[4, 1, 2]] subsystem code, which can be seen as a period-2 Floquet code. (b) Four-qubit ladder code, as introduced by Hastings and Haah [1]. It varies from the [[4, 1, 2]]-code schedule by the introduction of Y measurements every four rounds. We note that the last round is of XZ-type due to the previous one being of XZ-type as well (a Z-type round cannot follow an XZ-type round).</figcaption></figure>

honeycomb code have been constructed since then, including a CSS version of [2, 4], a planar version [2, 85-87], a hyperbolic version [88, 89] and a 3D version [4, 90-92]. Other examples have been obtained by "Floquetifying" stabilizer and subsystem codes. This works by starting from the measurement schedule of a given code and modifying it, often using ZX-calculus, to obtain new schedules with either lower-weight measurements or better general performance under some noise models [3, 32-35]. Floquetifying the Bacon-Shor code has for instance led to variations of the code with a non-zero threshold [11, 12].

However, our definition also allows the existence of non-periodic dynamical codes [2, 4, 5]. A common case arises when the measurement schedule carries out a specific logical operation on the code—for instance, using dynamical automorphisms [5]. More traditional protocols, such as lattice surgery [93] or gauge fixing [94-97], can likewise be framed as non-periodic dynamical codes.
<figure><img src="image_77.png" /><figcaption>Figure 17: Cluster state complex of the $[[4, 1, 2]]$ subsystem code for $T = 4$. For clarity, the six detectors are shown on separate graphs, by circling the nodes that are part of each detector.</figcaption></figure>

To any dynamical code, we associate a circuit of the form:

<figure><img src="image_78.png" /></figure>

where $M_i^{(t)}$ is either X or Y depending on whether the number of Y terms in $G_i^{(t)}$ is even ($M_i^{(t)} = X$) or odd ($M_i^{(t)} = Y$). To construct a cluster state complex that corresponds to this circuit, we need to progressively compile every round into a CZ network and merge those networks using Lemma 5.5. This can only be achieved if all the CZ networks are Hadamard-separated. In order to ensure this property during the compilation and have an MBQC circuit that is as compact as possible, we will derive a specific recursive compilation of this circuit, where the compilation of one round depends on that of the previous round. We start by labeling each round as X-type, Z-type, XZ-type or ZX-type. The assignment is done recursively for each round $t$ as follows:
<figure><img src="image_79.png" /><figcaption>Figure 18: Cluster state complex of the four-qubit ladder code for $T = 4$, in its compressed co-representation. For clarity, the six detectors are shown on separate graphs, by circling the nodes that are part of each detector. Moreover, while the two ancilla nodes (red empty circles) are shown at two different layers in the figure for visual clarity, they formally both belong to layer 0 in our construction.</figcaption></figure>

* If all the measurement in $G^{(t)}$ are pure X measurements, the round is labeled X-type

* If all the measurement in $G^{(t)}$ are pure Z measurements, then

- if either $t = 1$ or the previous round is of X-type or ZX-type, we label the round as Z-type,

- or if the previous round is of Z-type or XZ-type, we label the round as XZ-type.

* If the measurement in $G^{(t)}$ are made of both X and Z, then

- if either $t = 1$ or the previous round is of X-type or ZX-type, we label the round as ZX-type,

- or if the previous round is of Z-type or XZ-type, we label the round as XZ-type.

Every round will be compiled depending on its label, to ensure that rounds are always Hadamard-separated before merging and to avoid unnecessary double-Hadamard between two rounds. Two examples of dynamical codes with a labelled schedule are shown in Fig. 16. We are now ready to describe the cluster state complex corresponding to this circuit.

**Theorem 7.1.** Let us consider a dynamical code with measurement schedule $\{G^{(t)}\}_{1\le t\le T}$, $G^{(t)} = \{G_1^{(t)}, \dots, G_{m_t}^{(t)}\}$, and input stabilizer group $S = \langle S_1, \dots, S_{m_0}\rangle$, as well as a noise model where errors only happen in-between rounds. Let $D_S$ be the set of (full and incomplete) detectors that come from a spackle, where we see every element $D \in D_S$ as a subset of $\bigsqcup_t G^{(t)}$ corresponding to all the measurements involved in the detector. Similarly, let $D_B$ be the set of incomplete detectors that come from a backle. The circuit is equivalent to the following cluster state complex, described in the compressed representation:

* It has a layered structure, where layers are added recursively. We start by defining a layer $\ell = 0$ of virtual data nodes $q_1^{(0)}, \dots, q_n^{(0)}$ and a layer $\ell = 1$ with $n$ data nodes
$q_1^{(1)}, \dots, q_n^{(1)}$, with a directed edge from $q_i^{(1)}$ to $q_i^{(0)}$ for all $i \in \{1, \dots, n\}$. We also add ancilla nodes $a_1^{(0)}, \dots, a_m^{(0)}$, with a directed edge from each ancilla node $a_i^{(0)}$ to the data nodes at layer 0 according to the Z part of $S_i$, and to the data nodes of layer 1 according to the X part of $S_i$. Then, for each round $t$ of the dynamical code, let $\ell$ be the last layer added to the complex. We distinguish three cases, depending on the type of $G^{(t)}$:

1. $G^{(t)}$ is of Z-type. We add $m_t$ ancilla nodes $a_1^{(\ell)}, \dots, a_{m_t}^{(\ell)}$ to layer $\ell$, and connect them to the data nodes at this layer according to the support of each $G_i^{(t)}$.

2. $G^{(t)}$ is of X-type. We add two new layers $\ell+1$ and $\ell+2$ with new data nodes $q_1^{(\ell+1)}, \dots, q_n^{(\ell+1)}$ and $q_1^{(\ell+2)}, \dots, q_n^{(\ell+2)}$. We connect each data node $q_i^{(\ell)}$ to $q_i^{(\ell+1)}$, and $q_i^{(\ell+1)}$ to $q_i^{(\ell+2)}$. We add $m_t$ ancilla nodes $a_1^{(\ell+1)}, \dots, a_{m_t}^{(\ell+1)}$ to layer $\ell+1$ and connect them to the data nodes at this layer according to the support of the $G_i^{(t)}$.

3. $G^{(t)}$ is of ZX-type. We add two new layers $\ell+1$ and $\ell+2$ with new data nodes $q_1^{(\ell+1)}, \dots, q_n^{(\ell+1)}$ and $q_1^{(\ell+2)}, \dots, q_n^{(\ell+2)}$. We add $m_t$ ancilla nodes $a_1^{(\ell)}, \dots, a_{m_t}^{(\ell)}$ to layer $\ell$, and connect them to the data nodes at this layer according to the Z part of each $G_i^{(t)}$, and to the data nodes of layer $\ell+1$ according to the X part of each $G_i^{(t)}$. For all $i, j, i \neq j$, if the X part of $G_i^{(t)}$ has an odd intersection with the Z part of $G_j^{(t)}$, we add an edge between $a_i^{(\ell)}$ and $a_j^{(\ell)}$. This includes self-loops on in the case $i=j$.

4. $G^{(t)}$ is of XZ-type. We add two new layers $\ell+1$ and $\ell+2$ with new data nodes $q_1^{(\ell+1)}, \dots, q_n^{(\ell+1)}$ and $q_1^{(\ell+2)}, \dots, q_n^{(\ell+2)}$. We add $m_t$ ancilla nodes $a_1^{(\ell+2)}, \dots, a_{m_t}^{(\ell+2)}$ to layer $\ell+2$, and connect them to the data nodes at this layer according to the X part of $G_i^{(t)}$, and to the data nodes of layer $\ell+2$ according to the Z part of $G_i^{(t)}$. For all $i, j$, if the X part of $G_i^{(t)}$ has an odd intersection with the Z part of $G_j^{(t)}$, we add an edge between $a_i^{(\ell+2)}$ and $a_j^{(\ell+2)}$. This includes self-loops on in the case $i=j$.

Let $L$ be the last layer index $\ell$ added through this procedure. We then add a final output layer with data nodes $q_1^{(L+1)}, \dots, q_n^{(L+1)}$ with directed edges from $q_i^{(L)}$ to $q_i^{(L+1)}$ for all $i \in \{1, \dots, n\}$.

* To construct the detectors, we define the spackle of an ancilla node $a_i^{(\ell)}$, connected to the data nodes $q_{j_1}^{(\ell_1)}, \dots, q_{j_k}^{(\ell_k)}$ as the set of nodes consisting of $a_i^{(\ell)}$ and $q_{j_1}^{(\ell_1+2t+1)}, \dots, q_{j_k}^{(\ell_k+2t+1)}$ for all $t \ge 0$ such that $\ell+2t+1 \le L+1$. Similarly, the backle of $a_i^{(\ell)}$ is the set of nodes consisting in $a_i^{(\ell)}$ and $q_{j_1}^{(\ell_1-2t-1)}, \dots, q_{j_k}^{(\ell_k-2t-1)}$ for all $t$ such that $\ell-2t-1 \ge 0$. We now build one detector node per element $D \in \mathcal{D}_S$ ($D \in \mathcal{D}_B$), as the symmetric difference of the spackles (backles) of all the ancilla nodes corresponding to the measurements in $D$.

*Proof.* We construct the cluster state complex by progressively compiling every round of the dynamical code into a CZ network and merging it into the previous one. The proof works by induction on the number of compiled rounds.

The $n$ qubits of the initial circuit are first added to the graph as nodes $q_1^{(1)}, \dots, q_n^{(1)}$ on layer $\ell=1$.
We now assume that the first $t-1$ rounds of the dynamical code have been compiled into a CZ network, which gives the first $\ell$ layers of the cluster state complex described in the theorem statement. We examine the different possibilities for the $t$-th round of the dynamical code.

If $G^{(t)}$ is of X-type, we compile the measurements into a CZ network with H gates on both sides, using Lemma 5.2 to move the H gates outside the blue box:

<figure><img src="image_80.png" /></figure>

Here, $\bar{G}_i^{(t)}$ denotes the Pauli operator coming from $G_i^{(t)}$, where every X has been turned into a Z. The circuit inside the blue box is now a CZ network, which we can merge with a preceding CZ network by compiling the H gates before it into their MBQC version and using Lemma 5.5 to merge the networks. The new ancilla qubits used to compile the Hadamard gates give us a new layer of data nodes $q_1^{(\ell+1)}, \dots, q_n^{(\ell+1)}$ in the cluster state complex, which are connected to the data qubits of the layer below. The ancilla qubits used for measuring the operators $\bar{G}_i^{(t)}$ correspond to the ancilla nodes $a_i^{(\ell)}$ in the theorem statement. Finally, we also compile and merge the H gates coming after the CZ network using Lemma 5.4. This gives us a new layer of data nodes $q_1^{(\ell+2)}, \dots, q_n^{(\ell+2)}$ in the cluster state complex.

If $G^{(t)}$ is of Z-type, the circuit corresponding to the measurement of the Z-stabilizers $G_1^{(t)}, \dots, G_{m_t}^{(t)}$ is already a CZ network. If $t > 1$, since we are guaranteed that the previous round is of ZX- or X-type by construction of the labeling, it can be merged to the previous CZ network by Lemma 5.5. This compilation does not add any new layer to the cluster state complex, but only ancilla nodes connected to the data nodes of the current layer $\ell$ depending on the support of each $G_i^{(t)}$.

If $G^{(t)}$ is of XZ-type or ZX-type, we start by decomposing each measurement $G_i^{(t)}$ into
its X part—denoted $G_{i,X}^{(t)}$—and its Z part—denoted $G_{i,Z}^{(t)}$:

<figure><img src="image_81.png" /></figure>

We might now be tempted to turn every control Pauli into CZ and H, in order to then compile the H gates into their measurement-based versions. However, the presence of multiple layers of H gates within a blue box would prevent us from using Lemma 5.3 to compile the H gates into CZ gates. The key is to use one of the two circuit identities:

$$ \begin{tikzpicture}[baseline=(current bounding box.center)] \node (top) at (0,0.5) {}; \node (bottom) at (0,-0.5) {}; \draw (top) -- (bottom); \node at (0,0) {}; \node at (0.5,0.5) {}; \node at (0.5,-0.5) {}; \draw (top) -- (0.5,0.5) -- (0.5,-0.5) -- (bottom); \draw (top) -- (0.5,0.5) -- (0.5,-0.5) -- (bottom); \end{tikzpicture} = \begin{tikzpicture}[baseline=(current bounding box.center)] \node (top) at (0,0.5) {}; \node (bottom) at (0,-0.5) {}; \draw (top) -- (bottom); \node at (0,0) {}; \node at (0.5,0.5) {}; \node at (0.5,-0.5) {}; \draw (top) -- (0.5,0.5) -- (0.5,-0.5) -- (bottom); \draw (top) -- (0.5,0.5) -- (0.5,-0.5) -- (bottom); \end{tikzpicture} \qquad (122) $$

$$ \begin{tikzpicture}[baseline=(current bounding box.center)] \node (top) at (0,0.5) {}; \node (bottom) at (0,-0.5) {}; \draw (top) -- (bottom); \node at (0,0) {}; \node at (0.5,0.5) {}; \node at (0.5,-0.5) {}; \draw (top) -- (0.5,0.5) -- (0.5,-0.5) -- (bottom); \draw (top) -- (0.5,0.5) -- (0.5,-0.5) -- (bottom); \end{tikzpicture} = \begin{tikzpicture}[baseline=(current bounding box.center)] \node (top) at (0,0.5) {}; \node (bottom) at (0,-0.5) {}; \draw (top) -- (bottom); \node at (0,0) {}; \node at (0.5,0.5) {}; \node at (0.5,-0.5) {}; \draw (top) -- (0.5,0.5) -- (0.5,-0.5) -- (bottom); \draw (top) -- (0.5,0.5) -- (0.5,-0.5) -- (bottom); \end{tikzpicture} \qquad (123) $$

which allows us to push all the CZs to the left and all the CNOTs to the right (or the reverse), at the cost of adding new connections between ancilla qubits. We can use this identity to commute the control $G_{i,X}^{(t)}$ and $G_{i+1,Z}^{(t)}$ gates, inserting a CZ between their control qubits if $G_{i,X}^{(t)}$ and $G_{i+1,Z}^{(t)}$ intersect non-trivially on an odd number of qubits. For instance, if $G_{1,X}^{(t)}$ and $G_{2,Z}^{(t)}$ have an odd intersection, using Eq. (122) on the first two measurements gives us
the following the circuit:

<figure><img src="image_82.png" /></figure>

Repeating this commuting process for all the measurements, our circuit takes the form:

<figure><img src="image_83.png" /></figure>

where $CZ_A$ is a network of CZ gates with adjacency matrix $A$, defined by $A_{ij} = 1$ if and only if $G_{i,Z}^{(t)}$ and $G_{j,X}^{(t)}$ have an odd intersection. We can now compile the control $G_{i,X}^{(t)}$ into H and CZ

<figure><img src="image_84.png" /></figure>
where we used Lemma 5.2 to move the right-most H gates outside the blue box. Similarly, using Eq. (123), we obtain the following circuit where the X measurements come first:

<figure><img src="image_85.png" /></figure>

If the round $t$ is of $ZX$-type, we pick Eq. (124) as our compilation, while if it is of $XZ$-type, we pick Eq. (125). We can now compile the $H$ gates in-between the $CZ$ gates into their MBQC version using Lemma 5.3, giving us a $CZ$ network within the blue box.

If the round is of $ZX$-type, we are guaranteed that the previous round is of $X$- or $ZX$-type, meaning that the compiled version finishes with an MBQC Hadamard gate. We can therefore merge the $CZ$ network of Eq. (124) with the previous $CZ$ network by using Lemma 5.5. We also compile the right-most Hadamard gates of the circuit into their MBQC versions. If the round is of $XZ$-type, we compile the left-most Hadamard gates of Eq. (125) into their MBQC version and merge the $CZ$ networks using Lemma 5.5. For both types of round, this new addition to the $CZ$ network can be seen as adding two layers of data nodes to the cluster state complex. For a $ZX$-type round, the ancilla nodes connect the data nodes at layers $\ell$ and $\ell+1$, according to $G_{1,Z}^{(t)}$ and $G_{1,Z}^{(t)}$ respectively. For an $XZ$-type round, the ancilla nodes connect layers $\ell+1$ and $\ell+2$, according to $G_{1,X}^{(t)}$ and $G_{1,Z}^{(t)}$ respectively. Finally, due to the $CZ_A$ gate in the circuits, the ancilla nodes of index $i$ and $j$ are connected to each other if $G_{i,X}^{(t)}$ and $G_{j,Z}^{(t)}$ have an odd intersection.

We finish the construction by adding the virtual data nodes at layer $\ell = 0$ and $\ell = L+1$, and their connections to layers $\ell = 1$ and $\ell = L$ respectively, which are added following the definition of the compressed representation of the cluster state complex.

Let us now derive the detector nodes of the complex. We start with the original circuit and study the evolution of the spacetime stabilizers as the circuit transforms in the process described above. For each $D \in \mathcal{D}_S$, we have a spacetime stabilizer consisting of the spackle of all the measurements in $D$. Since every measurement is implemented in the original circuit with a controlled-Pauli gate and an ancilla qubit initialized in the $|+\rangle$ state, the spackle of a measurement is here the spackle of the $X$ operator stabilizing the corresponding ancilla qubit.
For instance, the spackle of the measurement $G_1^{(t)}$ looks as follows

<figure><img src="image_86.png" /></figure>

where $P_1, \dots, P_n$ are the Pauli operators that comprise $G_1^{(t)}$, and $Q_1^{(\ell)}, \dots, Q_{m_\ell}^{(\ell)}$ for $\ell \ge t$ are residual Pauli operators due to $P_1, \dots, P_n$ potentially not commuting with some $G_i^{(\ell)}$. When multiplying the spackles of all the measurements involved in a spacetime stabilizer, all those residual operators will be equal to $I$ or $M_i^{(\ell)}$ (such that the operator commutes with the final measurement). We therefore only need to look at the evolution of $P_1, \dots, P_n$ at the different rounds when transforming the circuit.

If the round is of type XZ or ZX, the first step was to compile each round of the circuit into Eq. (125) or Eq. (124). When compiling the Hadamard gates into their MBQC versions in the next step, any spacetime operator transforms as:

$$ \begin{gathered} \xrightarrow{Z} \boxed{H} \xrightarrow{X} \xrightarrow{+} \xrightarrow{X} \xrightarrow{X} \xrightarrow{X} \\ \xrightarrow{X} \boxed{H} \xrightarrow{Z} \xrightarrow{X} \xrightarrow{+} \xrightarrow{X} \xrightarrow{X} \xrightarrow{X} \end{gathered} \qquad (126) $$
For instance, the spackle of a measurement at a ZX-type round transforms as:

<figure><img src="image_87.png" /></figure>

where $\bar{P}_i$ is the Pauli operator obtained from $P_i$ by exchanging $X$ and $Z$, and where $P_i^X$ (resp. $\bar{P}_i^X$) is the restriction of $P_i$ (resp. $\bar{P}_i$) to its $X$ part. We can see that we have $X$ operators on all the data qubits located one layer above those connected to the ancilla qubit in the cluster state complex. Compiling the subsequent Hadamard gates and propagating the $P_1, \dots, P_n$ to the rest of the circuit leads to an $X$ operator at every other layer, for each data qubit that supports an $X$ at a given layer, as one can see from Eq. (126). This includes the last layer of virtual nodes, which represent the $Z$ part of $P_1, \dots, P_n$ or $\bar{P}_1, \dots, \bar{P}_n$ at the output of the circuit. The same analysis can be done for ancilla qubits located at XZ-type, X-type and Z-type rounds, leading to $X$ operators on data qubits located every other layer, starting one layer above every data qubit connected to the ancilla qubit in the cluster state complex.

Consequently, the spackle of a measurement maps, up to the residual operators $Q_i^{(\ell)}$, to the spackle of the corresponding ancilla node in the cluster state complex. Since those residual operators cancel when considering the products of spackles forming a spacetime stabilizer, such a spacetime stabilizer maps exactly to the product of spackles of the associated ancilla nodes in the cluster state complex.

It remains to show that the spacetime stabilizers built from the backle of measurements map to the backles of the corresponding ancilla nodes in the cluster state complex. Let us look at the backle of the measurement $G_{1,Z}^{(t)}$ for a ZX-type round preceded by a Hadamard
gate:

<figure><img src="image_88.png" /></figure>

We can see that we have *X* operators on all data qubits located one layer below those connected to the ancilla qubit in the cluster state complex. Compiling the preceding Hadamard gates and propagating the $\bar{P}_1, \dots, \bar{P}_n$ to the rest of the circuit leads to *X* operators every other layers, as one can see from Eq. (126). This includes the first layer of virtual nodes, which represent the *Z* part of $P_1, \dots, P_n$ or $\bar{P}_1, \dots, \bar{P}_n$ at the input of the circuit. The same analysis can be done for ancilla qubits located at *XZ*-type, *X*-type and *Z*-type rounds, leading to *X* operators on data qubits located every other layer, starting one layer below every data qubit connected to the ancilla qubit in the cluster state complex. ☐

# 8 Discussion

We introduced a new framework for spacetime codes based on chain complexes, enabling the compilation of Clifford circuits into cluster states while preserving their fault-tolerant properties. This framework can be applied to construct cluster states from non-CSS, subsystem, or dynamical codes. It can also be used to construct cluster states implementing logical operations by compiling the logical circuit into MBQC using our prescription.

We believe that our framework can be applied more broadly. For example, in Section 5, we mapped certain Clifford circuits—those built from single-qubit gates, controlled-Pauli gates, and single-qubit Pauli measurements—into cluster states, leaving open whether more general Clifford circuits admit such a mapping. Furthermore, while we only presented applications of our framework to MBQC compiling, we believe it could also be applied to other areas of fault-tolerant compilation, such as more general fusion-based quantum computing [42], hook error
detection [18] and flag qubit design [98, 99], or Floquetification of codes [3, 32–34]. Finally, recent discoveries show that cluster states can be constructed beyond foliation [55]. Examples include crystal structures [53], which exhibit similar macroscopic behaviour to the foliated surface code but with different microscopic implementations. Our framework could help us understand these structures either as the compilation of spacetime codes or as fault-tolerant transformations of the foliated surface code circuit

Another interesting research direction emerging from our work concerns its connection to other frameworks. For instance, it would be interesting to study the connection between fault-tolerant maps and distance-preserving rewrite rules in ZX-calculus, which have been widely used in the context of Floquetifying codes [32–34, 67], but also to unify different models of fault-tolerance [56]. Similarly, chain maps have been used to reduce the stabilizer weights of low-density parity-check codes [100–102], to perform lattice surgery on quantum low-density parity-check codes [103–105], and to map decoders between different codes [28, 29], though it remains unclear whether these chain maps fit within our framework.

Finally, we identify several promising directions for extending our framework. One natural extension is to explicitly track the noise model as chain complexes are transformed by fault-tolerant maps. Doing so would ensure that simulations of different chain complexes yield identical logical error rates. Concretely, this could be achieved by associating a probability distribution to the middle space of the chain complex and tracking how this distribution evolves under circuit transformations. A second direction is to generalize fault-tolerant maps from individual chain complexes to families of chain complexes, where distance is preserved only asymptotically. Such a generalization could enable more powerful mapping results and, when combined with the probabilistic approach above, allow threshold theorems to be carried over from one family of fault-tolerant circuits to another.

## Acknowledgments

The authors would like to thank Dan Browne, Nicolas Delfosse, Oscar Higgott, Timo Hillmann, Julio Magdalena De La Fuente, Ewan Murphy, Clément Poirson and Abhishek Rajput for enlightening discussions. Research at Perimeter Institute is supported in part by the Government of Canada through the Department of Innovation, Science and Economic Development Canada and by the Province of Ontario through the Ministry of Colleges and Universities. This research was supported in part by grant NSF PHY-2309135 to the Kavli Institute for Theoretical Physics (KITP). AP was supported in part by the Engineering and Physical Sciences Research Council (EP/S021582/1).