CSS code surgery as a universal construction

Alexander Cowtan
Dept. of Computer Science,  University of Oxford,
Wolfson Building, Parks Road, Oxford OX1 3QD, UK
Terrington House, 13-15 Hills Road, Cambridge CB2 1NL, UK
Simon Burton
Terrington House, 13-15 Hills Road, Cambridge CB2 1NL, UK

We define code maps between Calderbank-Shor-Steane (CSS) codes using maps between chain complexes, and describe code surgery between such codes using a specific colimit in the category of chain complexes. As well as describing a surgery operation, this gives a general recipe for new codes. As an application we describe how to `merge' and `split' along a shared $\overline{X}$ or $\overline{Z}$ operator between arbitrary CSS codes in a fault-tolerant manner, so long as certain technical conditions concerning gauge fixing and code distance are satisfied. We prove that such merges and splits on LDPC codes yield codes which are themselves LDPC.

§ INTRODUCTION

Quantum computers have become larger and more sophisticated in recent years [1, 12], but fault-tolerance is necessary to perform many practically relevant quantum algorithms. Qubit stabiliser error-correction codes are a well-studied approach to fault-tolerant quantum computing [22] and are favourable both for their practicality and theoretical simplicity. Such codes store logical data using entangled states of physical qubits and repeated many-body measurements, and so long as the physical errors on the qubits stay below a certain threshold the logical data is protected.

The most well-known example of a qubit stabiliser code
is the toric code, in which qubits are embedded on the
surface of a torus, and properties of the logical space
are determined by the topology of the surface [17, 30].
This is a basic example of a qubit Calderbank-Shor-Steane
(CSS) code; there are several equivalent ways of defining
CSS codes, but for our purposes we shall describe them
as codes which are all homological in a suitable
sense [4, 6].

This means that we can study CSS codes using the tools of homological algebra [42]. This approach has recently seen much success, for example in the construction of so-called good low-density parity check (LDPC) code families using a balanced product of chain complexes [38]. Such code families have an encoding rate $k/n$ of logical to physical qubits which is constant in the code size, while maintaining a linear code distance $d$, a substantial asymptotic improvement over simpler examples such as the toric code. The main caveat is, informally, that the connectivity between physical qubits is non-local. This complicates the architecture of the system, and also complicates the protocols for performing logical gates.

There have been several recent works on protocols for logical gates in CSS codes [31, 11, 8, 39, 26], of varying generality. Here, we build on this work by defining surgery, in the abstract, using arbitrary CSS codes which form a categorical span, although the practical implementation of such surgery has several important caveats. The idea is that merging two codes works by identifying a common structure in each code and quotienting it out. CSS code surgery is particularly convenient when the CSS codes are compatible, in the sense that they have at least one identical $\overline{Z}$ or $\overline{X}$ logical operator. In this case, the common structure being quotiented out is the logical operator. In order to formalise this, we take a step back and look at the category of chain complexes $\Chains$.

We start by giving a recap of the relevant categorical
background of chain complexes, and the view of classical
linear binary codes and qubit CSS codes using chain complexes.
We then define code maps between CSS codes using morphisms
between chain complexes. These are maps which send $X$-checks
to $X$-checks and $Z$-checks to $Z$-checks in a coherent
way, and have a convenient presentation as phase-free
ZX diagrams, which we prove in Proposition <ref>.

We believe that code maps crop up throughout the CSS
code literature. We see 3 primary use-cases for code maps:

* Encoders/decoders [18, 16, 24].

* Constructing new codes.

* Designing fault-tolerant logical operations.

We intend to expound on code maps in future work, but
presently we focus on items 2 and 3.

We define CSS code merges as a colimit – specifically, a coequaliser/pushout – in the category of chain complexes. Not only does the construction describe a surgery operation, but it also gives a general recipe for new codes. An application of our treatment is the description of certain classes of code surgery whereby the codes are merged or split along a $\overline{Z}$ or $\overline{X}$ operator. This is closely related to the notion of `welding' in [36], and generalises the cases for 2D topological codes given in [25, 33, 37]. We prove that merging two LDPC codes in such a manner still yields an LDPC code. We give a series of examples, including the specific case of lattice surgery between surface codes. Lastly, we discuss how to apply such protocols in practice. We prove that when 3 technical conditions are satisfied then code surgery can be performed fault-tolerantly, allowing us to perform logical parity measurements on codes.

§.§ Guide to reading the paper

Section <ref> gives a bird's eye view of category theory and universal constructions, which will be useful later on. Section <ref> describes the category of chain complexes with morphisms as matrices over $\F_2$. Category theorists may wish to skip past these sections.

We then give a rundown of CSS codes viewed as chain complexes in Section <ref>. Readers familiar with basic category theory and this perspective of CSS codes can safely skip to Section <ref>, where we introduce the notion of code maps, that is coherent transforms between codes.

We introduce surgery of codes as a colimit in Section <ref>. This is when the notion of `gluing' codes together comes in, and we prove several results about these codes when the colimit uses logical $\overline{Z}$ or $\overline{X}$-operators.
Lastly, we introduce a protocol for performing logical $\overline{Z}\tens\overline{Z}$ and $\overline{X}\tens\overline{X}$ measurements fault-tolerantly in Section <ref>.

§ UNIVERSAL CONSTRUCTIONS

§ CHAIN COMPLEXES

We now recap some elementary homological algebra. All of this section is known [42], but we fix notation and look explicitly at the particular category of interest.

Let $\MatF$ be the category which has as objects based finite-dimensional vector spaces over $\F_2$, so each vector space $V$ has a specified basis $\tilde{V}$, and we have $V \cong \F_2^{|\tilde{V}|}$. A morphism $f: V\rightarrow W$ in $\MatF$ is a $\dim \ W\times \dim \ V$ matrix valued in $\F_2$.

Each $V$ has a dual space $V^*$. As $V\cong V^*$, we may fix the duals such that $V^* = V$, and $\tilde{V}^*= \tilde{V}$. This has the benefit of forcing the dual of any matrix $f : V\rightarrow W$, which is given by $f^* : W^* \rightarrow V^*$, to strictly be the transpose $f^\intercal : W \rightarrow V$.

Let $\Chains$ be the category of bounded chain complexes in $\MatF$. We now recap some of the basic properties of this category. A chain complex $C_\bullet$ looks like this:

\[\begin{tikzcd}
\cdots \arrow[r] & C_{n+1}\arrow[r, "\del_{n}"] & C_{n}\arrow[r, "\del_{n-1}"] & C_{n-1}\arrow[r] & \cdots
\end{tikzcd}\]

where each component $C_i$ is a based vector space and $n\in \Z$ is called the degree of the component in $C_\bullet$. $C_\bullet$ has $\F_2$-matrices as differentials $\del_n:C_{n+1}\rightarrow C_{n}$ such that $\del_n\circ\del_{n+1}=0 \pmod 2$, $\forall n \in \Z$. To disambiguate differentials between chain complexes we will use $\del^{C_\bullet}_n := \del_n \in C_\bullet$ when necessary.

All our chain complexes are bounded, meaning there is some $k\in \Z$ such that $C_{n > k} = 0$ and $l\in\Z$ such that $C_{n < l} =0$, i.e. it is bounded above and below. We call $k-l$ the length of $C_\bullet$ for $k$ and $l$ the smallest and largest possible values respectively.

Given a chain complex $C_\bullet$ we let

\[Z_n(C_\bullet) = \ker (\del_{n-1});\quad B_n(C_\bullet) = \im(\del_{n}) \]

and call $Z_n, B_n$ the $n$-cycles and $n$-boundaries. We also define a quotient $H_n(C_\bullet) = Z_n(C_\bullet)/B_n(C_\bullet)$, and call $H_n$ the $n$th homology space of $C_\bullet$.

Recall that $\dim (\ker (\del_{n-1})) = {\rm null}(\del_{n-1}) = \dim C_n - {\rm rank}(\del_{n-1})$. Note that throughout we sometimes use $\ker (f)$ of a matrix $f$ to mean the kernel object, i.e. subspace, and sometimes the kernel morphism, i.e. inclusion map. It should be clear from context which is meant.

Let $\Gamma$ be a finite simple undirected graph. We can form the incidence chain complex $C_\bullet$ of $\Gamma$, which has $\tilde{C}_{-1} = V(\Gamma)$ and $\tilde{C}_0 = E(\Gamma)$, say, so that $C_{-1} = \F_2^{|V(\Gamma)|}$, $C_0 = \F_2^{|E(\Gamma)|}$. All other components are zero. The sole nonzero differential $\del_{-1}$ is the incidence matrix of $\Gamma$, with $(\del_{-1})_{ij} = 1$ if the $j$th edge is attached to the $i$th vertex, and 0 otherwise.
$H_0(C_\bullet)$ is determined by the graph homology of $\Gamma$ [42].

A morphism $f_\bullet: C_\bullet\rightarrow D_\bullet$ in $\Chains$ is called a chain map, and consists of a collection of matrices $\{f_i: C_i\rightarrow D_i\}_{i\in \Z}$ such that each resultant square of maps commutes:

\[\begin{tikzcd}\cdots \arrow[r] & C_{n+1}\arrow[r, "\del^{C_\bullet}_{n}"]\arrow[d, "f_{n+1}"] & C_{n}\arrow[r, "\del^{C_\bullet}_{n-1}"]\arrow[d, "f_{n}"] & C_{n-1}\arrow[r]\arrow[d,"f_{n-1}"] & \cdots\\
\cdots \arrow[r] & D_{n+1}\arrow[r, "\del^{D_\bullet}_{n}"] & D_{n}\arrow[r, "\del^{D_\bullet}_{n-1}"] & D_{n-1}\arrow[r] & \cdots\end{tikzcd}
\]

As we specified bounded chain complexes only a finite number of the $f_i$ matrices will be non-zero. A chain map $f_\bullet$ is an isomorphism in $\Chains$ iff all $f_i$ are invertible, in which case one can think of the isomorphism as being a `change of basis' for all components, which thus transforms the differential matrices appropriately. Observe also that every pair of chain complexes has at least two chain maps, the zero chain maps, between them, given by a collection of entirely zero matrices either way.

A chain map at a component $f_n : C_n \rightarrow D_n$ lifts to a matrix $H_n(f_\bullet) : H_n(C_\bullet)\rightarrow H_n(D_\bullet)$.

It is easy to check that $f_n$ induces matrices from $Z_n(C_\bullet)\rightarrow Z_n(D_\bullet)$ and the same for $B_n$.

This lemma is equivalent to saying that $H_n(-)$ is a functor from $\Chains \rightarrow \MatF$.

$\Chains$ has several known categorical properties which will be useful to us. One way to see a chain complex $C_\bullet$ in $\MatF$ is as a $\Z$-graded $\F_2$-vector space, with specified bases and a distinguished map $\del : C_\bullet \rightarrow C_\bullet$ with components $\del_i : C_{i+1} \rightarrow C_i$, such that $\del\circ\del = 0$. Many of the properties of $\Chains$ are inherited directly from those of $\Z$-graded $\F_2$-vector spaces.

$\Chains$ is an additive category, i.e. it has all finite biproducts.

Adding two chain maps obviously gives a chain map. Define the biproduct of $C_\bullet$ and $D_\bullet$ with shorthand $(C\oplus D)_\bullet$ of chain complexes $C_\bullet, D_\bullet$. It has components

\[(C\oplus D)_n = C_n \oplus D_n\]

and the same for differentials. This is both a categorical product and coproduct. Lastly, the zero object is

\[\begin{tikzcd}
\mathbf{0}_\bullet = \cdots \arrow[r] &0\arrow[r] &0 \arrow[r] &0\arrow[r] &\cdots
\end{tikzcd}\]

i.e. all $\mathbf{0}_i$ are $0$.

Homology preserves direct sums (coproducts): given chain complexes $C_\bullet$ and $D_\bullet$,

\[H_n((C\oplus D)_\bullet) \cong H_n(C_\bullet)\oplus H_n(D_\bullet)\]

This is obvious, considering the blocks of each differential in $(C\oplus D)_\bullet$.

Let the dual chain complex $C^*_\bullet$ have components

\[(C^*)_n = C_{-n}\]

and differentials

\[\del^{C^*_\bullet}_{n} = (\del^{C_\bullet}_{-n-1})^\intercal.\]

Our choice of duals means that $C_\bullet^{**} = C_\bullet$ on the nose.

For a chain complex $C_\bullet$,

\[H_i(C_\bullet) \cong H_{-i}(C^*_\bullet)\]

\[\ker ((\del^{C_\bullet}_{i})^\intercal)/\im ((\del^{C_\bullet}_{i-1})^\intercal) \cong \im (\del^{C_\bullet}_{i})^\perp/\ker (\del^{C_\bullet}_{i-1})^\perp \cong \ker (\del^{C_\bullet}_{i-1})/ \im (\del^{C_\bullet}_{i}).\]

The dual of a chain map $f$ is straightforward: it has matrices $(f^*)_i = (f_{-i})^\intercal$. Thus $f_\bullet^{**} = f_\bullet$ on the nose.

These are categorical duals with respect to a tensor product of chain complexes. As we only need this tensor product for a very specific construction in Section <ref> we relegate it to Appendix <ref>.

§ QUANTUM CODES

Here we introduce classes of both classical and quantum codes as chain complexes. We give easy examples such as the surface and toric codes. Up until Section <ref>, this part is also well-known, although we describe the relationship between $Z$ and $X$ operators in greater detail than we have found elsewhere.

§.§ Codes as chain complexes

Binary linear classical codes which encode $k$ bits using $n$ bits can be described by a $m\times n$ parity check $\F_2$-matrix $P$. The parity check matrix $P$, when applied to any codeword of length $n$, gives $Pc = 0$, and thus $k = \dim \ker(P)$; if the result is non-zero then an error has been detected, and under certain assumptions can be corrected. The distance $d$ of a binary linear classical code is the minimum Hamming weight of its nonzero codewords, and one characterisation of codes is by their metrics $[n,k,d]$. Given $P$, $G$ is uniquely defined up to isomorphism as the matrix $\ker (P)$, so we use only $P$ to define the code. We may trivially view a binary linear classical code as a length 1 chain complex in $\Chains$, with indices chosen for convenience:

\[\begin{tikzcd}C_\bullet = \cdots \arrow[r] &C_0\arrow[r, "\del^{C_\bullet}_{-1}"]&C_{-1} \arrow[r]& \cdots\end{tikzcd}\]

where $C_0 = \F_2^n$, $C_{-1} = \F_2^m$, and $\del^{C_\bullet}_{-1} = P$, the chosen $m\times n$ parity check matrix. Then we have $k = \dim \ H_{0}(C_\bullet) =\dim \ Z_{0}(C_\bullet)$, where $Z_{0}(C_\bullet)$ is the codespace.

Let $C_\bullet$ be a $[3,1,3]$ repetition code, encoding 1 bit into 3 bits. In this case, let

\[P = \begin{pmatrix} 1&1&0\\1&0&1\end{pmatrix}\]

Let $C_\bullet$ be the $[7,4,3]$ Hamming code. Then let

\[P = \begin{pmatrix} 1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1 \end{pmatrix}\]

From Example <ref> we know that each graph defines length 1 chain complex, and so every graph evidently specifies a classical code, with edges as physical bits and vertices parity checks. An easy case is for cycle graphs, whereby we have a repetition code with one redundant parity check, i.e. vertex. In general, the cycle graph $\CC_n$ with $n$ vertices gives an $[n,1,n]$ repetition code.

We now move on to quantum codes. Qubit Calderbank-Shor-Steane (CSS) codes are a type of stabiliser quantum code. Let $\mathscr{P}_n = \mathscr{P}^{\tens n}$ be the Pauli group over $n$ qubits. Stabiliser codes start by specifying an Abelian subgroup $\mathscr{S} \subset \mathscr{P}_n$, called a stabiliser subgroup, such that the codespace $\mathscr{H}$ is the mutual +1 eigenspace of all operators in $\mathscr{S}$. That is,

\[U\ket{\psi} = \ket{\psi} \quad \forall U \in \mathscr{S}, \ket{\psi}\in \mathscr{H}\]

We then specify a generating set of $\mathscr{S}$, of size $m$. For CSS codes, this generating set has as elements tensor product strings of either $\{I,X\}$ or $\{I,Z\}$ Pauli terms, with no scalars other than 1. One can define two parity check $\F_2$-matrices $P_X, P_Z$, for the $X$s and $Z$s, which together define a particular code. Each column in $P_X$ and $P_Z$ represents a physical qubit, and each row a measurement/stabiliser generator. $P_X$ and $P_Z$ thus map $Z$ and $X$ operators on physical qubits respectively to sets of measurement outcomes, with a $1$ outcome if the operators anticommute with a given stabiliser generator, and $0$ otherwise; these outcomes are also called syndromes. $P_X$ is a $m_X \times n$ matrix, and $P_Z$ is $m_Z\times n$, with $m_X,m_Z$ marking the division of the generating set into $X$s and $Z$s respectively, satisfying $m=m_X+m_Z$. We do not require the generating set to be minimal, and hence $P_X$ and $P_Z$ need not be full rank.

We say that $w^Z$ is the maximal weight of all $Z$-type generators and $w^X$ the same for the $X$-type generators. These are the highest weight rows of $P_Z$ and $P_X$ respectively. Similarly, we say that $q^Z$, $q^X$ is the maximal number of $Z$, $X$ generators sharing a single qubit. These are the highest weight columns of $P_Z$ and $P_X$.

CSS codes are characterised by $\llbracket n,k,d \rrbracket$, with $k$ the number of encoded qubits and $d$ the code distance, which we define presently.

That the stabilisers must commute is equivalent to the requirement that $P_X P_Z^\intercal = P_Z P_X^\intercal = 0$. We may therefore view these matrices as differentials in a length 2 chain complex:

\[\begin{tikzcd}C_\bullet = C_{1}\arrow[r, "\del_0"]& C_0\arrow[r, "\del_{-1}"]& C_{-1}\end{tikzcd}\]

where $\del_0 = P_Z^\intercal$ and $\del_{-1} = P_X$, or the other way round ($\del_0 = P_X^\intercal, \del_{-1} = P_Z$) if desired, but we start off with the former for consistency with the literature. The quantum code then has $C_0 \cong \F_2^n$. We will typically fix $C_0 = \F_2^n$ for convenience.

The code also has $k = \dim\ H_0(C_\bullet)$. To see this, observe first that $C_0$ represents the space of $Z$ Paulis on the set of physical qubits, with a vector being a Pauli string e.g. $v=\begin{pmatrix} 1&0&1\end{pmatrix}^\intercal \leadsto Z\tens I \tens Z$. Each vector in $H_0(C_\bullet)$ can be interpreted as an equivalence class $[v]$ of $Z$ operators on the set of physical qubits, modulo $Z$ operators which arise as $Z$ stabilisers. That this vector is in $Z_0(C_\bullet)$ means that the $Z$ operators commute with all $X$ stabilisers, and when the vector is not in $[0] = B_0(C_\bullet)$ it means that the $Z$ operators act nontrivially on the logical space. A basis of $H_0(C_\bullet)$ constitutes a choice of individual logical Paulis $\overline{Z}$, that is a tensor product decomposition of the space of logical $Z$ operators, and we set $\overline{Z}_1 = \overline{Z} \tens \overline{I}\cdots \tens \overline{I}$ on logical qubits, $\overline{Z}_2 = \overline{I} \tens \overline{Z}\cdots \tens \overline{I}$ etc. There is a logical qubit for every logical $Z$, hence $k =\dim \ H_0(C_\bullet)$.

To get the logical $X$ operators, consider the dual $C_\bullet^*$. The vectors in $H_{0}(C_\bullet^*)$ then correspond to $\overline{X}$ operators in the same manner. As a consequence of Lemma <ref> there must be an $\overline{X}$ operator for every $\overline{Z}$ operator and vice versa.

A choice of basis $\{[v]_i\}_{i\leq k}$ for $H_0(C_\bullet)$ implies a choice of basis $\{[w]_j\}_{j\leq k}$ for $H_0(C_\bullet^*)$.

First, recall that we have the nondegenerate bilinear form

\[\cdot : \F_2^n \times \F_2^n \rightarrow \F_2;\quad u\cdot v = u^\intercal v\]

which is equivalent to $\cdot : C_0 \times (C^*)_0 \rightarrow \F_2$; computationally, this tells us whether a $Z$ operator commutes or anticommutes with an $X$ operator. Now, let $u \in Z_0(C_\bullet)$ be a (possibly trivial) logical $Z$ operator, and $v \in B_0(C^*_\bullet)$ be a product of $X$ stabilisers. Then $P_X u = 0$, and $v = P_X^\intercal w$ for some $w \in C_{-1}$. Thus $u \cdot v = u^\intercal v = u^\intercal P_X^\intercal w = (P_X u)^\intercal w = 0$, and so products of $X$ stabilisers commute with logical $Z$ operators. The same applies for $Z$ stabilisers and logical $X$ operators.

As a consequence, $v\cdot w = (v + s)\cdot (w+t)$ for any $v \in Z_0(C_\bullet)$, $w\in Z_0(C_\bullet^*)$, $s \in B_0(C_\bullet)$, $t\in B_0(C_\bullet^*)$, and so we may define $[v]\cdot [w] = v\cdot w$ for any $[v] \in H_0(C_\bullet)$, $[w]\in H_0(C_\bullet^*)$ with representatives $v, w$. The duality pairing of $C_0, (C^*)_0$ thus lifts to $H_0(C_\bullet), H_0(C_\bullet^*)$, and a choice of basis $\{[v]_i\}_{i\leq k}$ for $H_0(C_\bullet)$ implies a choice of basis of $H_0(C_\bullet^*)$, determined uniquely by $[v]_i\cdot [w]_j = \delta_{i,j}$.

The above lemma ensures that picking a tensor product decomposition of logical $Z$ operators also entails the same tensor product decomposition of logical $X$ operators, so that $\overline{X}_i\overline{Z}_j = (-1)^{\delta_{i,j}}\overline{Z}_j\overline{X}_i$, for operators on the $i$th and $j$th logical qubits.

\[d^Z = \min_{v \in Z_0(C_\bullet)\backslash B_0(C_\bullet)} |v| ;\quad d^X = \min_{w \in Z_0(C_\bullet^*)\backslash B_0(C_\bullet^*)} |w|\]

where $|\cdot |$ is the Hamming weight of a vector, then the code distance $d = \min(d^Z,d^X)$. $d^Z$ and $d^X$ are called the systolic and cosystolic distances, and represent the lowest weight nontrivial $Z$ and $X$ logical operators respectively.

As all the data required for a CSS code is contained within the chain complex $C_\bullet$ – and potentially a choice of basis of $H_0(C_\bullet)$ – then we could define a CSS code as just the single chain complex, but it will be convenient to have direct access to the dual complex as well.

A CSS code is a pair $(C_\bullet, C_\bullet^*)$ of a length 2 chain complex centred at degree 0 and its dual:

\[\begin{tikzcd}C_\bullet = C_{1}\arrow[r, "P_Z^\intercal"]& C_0\arrow[r, "P_X"]& C_{-1}\end{tikzcd};\quad \begin{tikzcd}C_\bullet^* = C_{-1}\arrow[r, "P_X^\intercal"]& C_0\arrow[r, "P_Z"]& C_{1}\end{tikzcd}\]

A based CSS code additionally has a choice of basis for $H_0(C_\bullet)$, and hence for $H_0(C_\bullet^*)$. We call the first of the pair the $Z$-type complex, as vectors in $C_0$ correspond to $Z$-operators, and the second the $X$-type complex.

As $C_\bullet^{**} = C_\bullet$, we see that given any CSS code $(C_\bullet, C_\bullet^*)$ we can exchange $Z$ and $X$ stabilisers (and operators) to obtain $(C_\bullet^*, C_\bullet)$.

Employing the direct sum $(C \oplus D)_\bullet$ of chain complexes we have the CSS code $((C \oplus D)_\bullet, (C^* \oplus D^*)_\bullet)$, which means the CSS codes $(C_\bullet, C_\bullet^*)$ and $(D_\bullet, D_\bullet^*)$ perform in parallel on disjoint sets of qubits, without any interaction. The $Z$ and $X$ operators will then be the tensor product of operators in each.

In summary, there is a bijection between length 1 chain complexes in $\Chains$ and binary linear classical codes, and between length 2 chain complexes in $\Chains$ and CSS codes. That this is a bijection is because we have been quite careful: under our definitions, two classical codes with different matrices but which are the same up to, say, Gaussian elimination are counted as being different classical codes. Morally, these could be considered equivalent codes for some purposes, as they have the same codespaces, code distances and number of physical bits. A similar qualification applies to quantum CSS codes. Additionally, there is no guarantee that the chain complexes will give useful codes. For example, a length 2 chain complex could be an exact sequence and thus have a homology space of zero at all components, in which case there are no logical qubits in the code; even if there is nontrivial homology, the (co-)systolic distance could be very low and thus not practical as a code.

There are many classical and quantum codes which do not fit into this classification using $\Chains$, such as nonlinear classical codes and stabiliser quantum codes which are not CSS (although any $\llbracket n,k,d\rrbracket $ stabiliser code can be mapped to a $\llbracket 4n,2k,2d\rrbracket $ CSS code [7]). There are also fault-tolerant topological quantum systems which certainly don't live in $\Chains$, although they have similar homological properties [30, 14]. Lastly, there are CSS codes for higher dimensional qudits, but for simplicity we stick to qubits.

Rather than just individual codes we tend to be interested in families of codes, where $n,k,d$ scale with the size of code in the family. Of particular practical interest are quantum low density parity check (LDPC) CSS codes, which are families of codes where all $w^Z$, $w^X$, $q^Z$ and $q^X$ in the family are bounded from above by a constant. Equivalently, this means the Hamming weight of each column and row in each differential is bounded by a constant.

§.§ Basic quantum codes

Let $(C_\bullet, C_\bullet^*)$ be the $\llbracket 9,1,3\rrbracket $ Shor code, so we have $C_{-1} = \F_2^2$, $C_0 = \F_2^9$, $C_1 = \F_2^6$. The parity check matrices are given by

\[
P_X = \begin{pmatrix}
\end{pmatrix}; \quad
P_Z = \begin{pmatrix}
\end{pmatrix}
\]

We then have $\dim \ Z_0(C_\bullet) =\dim \ C_0-{\rm rank}(P_X) = 9-2 = 7$ and $\dim \ B_0(C_\bullet) = {\rm rank}(P_Z^\intercal) = 6$. Thus $k =\dim \ H_0(C_\bullet) = 1$. $H_0(C_\bullet)$ has a single nonzero equivalence class $[v] \in H_0(C_\bullet)$, with a representative $v = \begin{pmatrix}1&1&1&1&1&1&1&1&1\end{pmatrix}^\intercal$. Similarly $H_0(C_\bullet)^*$ has the nonzero vector $w = \begin{pmatrix}1&1&1&1&1&1&1&1&1\end{pmatrix}^\intercal$, which is a representative of $[w]\in H_0(C_\bullet)$. Hence, we have two logical operators $\overline{Z} = \bigotimes_i^8 Z_i$, $\overline{X} = \bigotimes_i^8 X_i$ with $Z_i$ on the $i$th qubit and the same for $X_i$. We equally have, say, $\overline{Z} = Z_1\tens Z_4\tens Z_7$ and $\overline{X} = X_1\tens X_2\tens X_3$ in the same equivalence classes as those above, $[v]$ and $[w]$.

We now consider two examples which come from square lattices. This can be done much more generally. In Appendix <ref> we formalise categorically the procedure of acquiring chain complexes – and therefore CSS codes – from square lattices, which are a certain type of cell complex.

Consider the following square lattice:

\[\tikzfig{box_product_cycles}\]

Edges in the lattice are qubits, so $n = 18$, the 9 $X$-checks are associated with vertices and the 9 $Z$-checks are associated with faces, which are indicated by white circles. Grey vertices indicate periodic boundary conditions, so the lattice can be embedded on a torus. This is an instance of the standard toric code [30].

The abstracted categorical homology from before is now the homology of the tessellated torus, with cycles, boundaries etc. having their usual meanings. Letting the code be $(C_\bullet, C_\bullet^*)$, we have $k = \dim \ H_0(C_\bullet) = 2$, and (co)systolic distances are the lengths of the essential cycles of the torus.

Now consider a different square lattice:

\[\tikzfig{box_product_paths}\]

This represents a patch of surface code $(D_\bullet, D_\bullet^*)$, where we have two smooth sides, on the left and right, and two rough sides to the patch, on the top and bottom. Observe that we have `dangling' edges at the top and bottom, which do not terminate at vertices. We have

\[\dim \ D_1 =  \dim \ D_{-1} = 6;\quad n = \dim \ D_0 = 13;\quad k=\dim \ H_0(D_\bullet) = 1 \]

The systolic distance is $3$, the length of the shortest path from the top to bottom boundary, and the cosystolic distance $3$, the same but from left to right.

§.§ Code maps

One may wish to convert one code into another, making a series of changes to the set of stabiliser generators to be measured, and potentially also to the physical qubits. The motivation behind such protocols is typically to perform logical operations which are not available natively to the code; not only might the target code have other logical operations, but the protocol is itself a map between logical spaces when chosen carefully. An example of a change to the measurements and qubits is code deformation. We do not formalise code deformation here, as that has some specific connotations [41]. Instead we define a related notion, called a code map, which has some overlap. A code map is also related to, but not the same as, the `homomorphic gadgets' from [26].

A $\overline{Z}$-preserving code map $\CF_{\overline{Z}}$ from a CSS code $(C_\bullet, C_\bullet^*)$ to $(D_\bullet, D_\bullet^*)$ is a dual pair of chain maps $(f_\bullet, f_\bullet^*)$, for $f_\bullet: C_\bullet \rightarrow D_\bullet$ and $f_\bullet^*: D_\bullet^* \rightarrow C_\bullet^*$.

\[\begin{tikzcd}
\ \arrow[d, "\CF_{\overline{Z}}"', Rightarrow] & (C_\bullet, C_\bullet^*)\arrow[d, "f_\bullet"', shift right=2ex]\\
\ & (D_\bullet, D_\bullet^*)\arrow[u, "f^*_\bullet"', shift right=2ex]
\end{tikzcd}\]

Note that the second chain map is strictly speaking obsolete, as all the data is contained in a single chain map $f_\bullet$, but as with chain complexes it will be handy to keep both around.

Let us unpack this definition. $\CF_{\overline{Z}}$ first maps $Z$-operators in $C_0$ to $Z$-operators in $D_0$, using $f_0$. It may map a single $Z$ on a qubit to a tensor product of $Z$s, or to $I$. It then has a map $f_1$ on $Z$ generators, and another $f_{-1}$ on $X$ generators. Recalling Definition <ref>, we have:

\[\begin{tikzcd}C_{1}\arrow[r, "\del^{C_\bullet}_{0}"]\arrow[d, "f_{1}"'] & C_{0}\arrow[r, "\del^{C_\bullet}_{-1}"]\arrow[d, "f_{0}"] & C_{-1}\arrow[d,"f_{-1}"]\\
D_{1}\arrow[r, "\del^{D_\bullet}_{0}"'] & D_{0}\arrow[r, "\del^{D_\bullet}_{-1}"']\arrow[ul, phantom, "\textrm{I}"] & D_{-1}\arrow[ul, phantom, "\textrm{II}"]\end{tikzcd}
\]

With two commuting squares labelled I and II. I stipulates that applying products of $Z$ stabiliser generators on the code and then performing the code map should be equivalent to performing the code map and then applying products of $Z$ stabiliser generators, i.e. $f_0\circ\del^{C_\bullet}_{0} =\del^{D_\bullet}_{0}\circ f_1 $. II stipulates that performing the $X$ measurements and then mapping the code should be equivalent to mapping the code and then performing $X$ measurements, so there is a consistent mapping between all measurement outcomes, i.e. $f_{-1}\circ\del^{C_\bullet}_{-1} =\del^{D_\bullet}_{-1}\circ f_0 $.

Then there is the chain map $f_\bullet^*$. This has the component $f^\intercal_0 : D_0 \rightarrow C_0$, which maps an $X$-operator in $D_0$ back to an $X$-operator in $C_0$. Similarly for $f^\intercal_{-1}$ and $f^\intercal_1$, each of which come with commuting squares which are just the transposed conditions, e.g. $f_1^\intercal \circ (\del^{D_\bullet}_0)^\intercal = (\del^{C_\bullet}_0)^\intercal \circ f_0^\intercal$, so they say nothing new. This is not surprising, as all the data for $f^*$ is given by $f$ already.

We now show that this definition entails some elementary properties. For a start, Lemma <ref> implies that a code map gives a map from a $\overline{Z}$ operator in $H_0(C_\bullet)$ to $\overline{Z}$s in $H_0(D_\bullet)$; this can also map to a tensor product of logical $\overline{Z}$s, and in particular map $\overline{Z}$ to zero i.e. $\overline{I}$, but it must not map a $\overline{Z}$ to an operator which can be detected by the $X$ stabiliser measurements. Hence $(f_\bullet, f^*_\bullet)$ preserves the fact that any $\overline{Z}$ is an undetectable operator on the codespace. A similar requirement holds for $\overline{X}$ operators, but this time the condition is inverted. Every $\overline{X}$ in $H_0(D_\bullet^*)$ must have a map only to logical operators in $H_0(C_\bullet^*)$, but the other way is not guaranteed.

Let $n_C$ and $n_D$ be the number of physical qubits in codes $(C_\bullet, C_\bullet^*)$ and $(D_\bullet, D_\bullet^*)$ respectively. We may interpret $\CF_{\overline{Z}}$ as a $\C$-linear map $M$ in $\FHilb$, the category of Hilbert spaces. This $\C$-linear map has the property that $M U_Z = U'_Z M$, where $U_Z$ is a tensor product of $Z$ Paulis on $n_C$ qubits and $U'_Z$ is a tensor product of $Z$ Paulis on $n_D$ qubits. In particular, given any $U_Z$ we have a specified $U'_Z$. The same is not true the other way round, as the map $f_0$ is not necessarily injective or surjective. Similarly, $M U_X = U'_X M$. This time, however, given any unique $U'_X$ on $n_D$ qubits we have a specified $U_X$ but vice versa is not guaranteed, depending on $f_0^\intercal$.

As a consequence, the linear map $M$ is stabiliser, in the sense that it maps Paulis to Paulis, but not unitary in general. $M$ is unitary iff $f_0$ is invertible.

If $M$ is not even an isometry, it cannot be performed deterministically, and the code map must include measurements on physical qubits. There will in general be Kraus operators corresponding to different measurement outcomes which will determine whether the code map has been implemented as desired; for now we assume that $M$ is performed deterministically, and leave this complication for Section <ref>. Similarly, while the code map can be interpreted as a circuit between two codes, we do not claim that such a circuit can be performed fault-tolerantly in general.

For the following proposition, and at various points throughout the rest of the paper, we will use the ZX-calculus, a formal graphical language for reasoning about computation with qubits. We do not give a proper introduction to this calculus for brevity, but Sections 1-3 of [40] are sufficient for the interested reader. Our use of ZX diagrams is unsophisticated, and primarily for convenience.

Let $\CF_{\overline{Z}}$ be a $\overline{Z}$-preserving code map between codes $(C_\bullet, C_\bullet^*)$ and $(D_\bullet, D_\bullet^*)$ with qubit counts $n_C$ and $n_D$. The interpretation of $\CF_{\overline{Z}}$ as a $\C$-linear map $M$ in $\FHilb$ has a presentation as a circuit with gates drawn from $\{{\rm CNOT},\ket{+},\bra{0}\}$.

We start with the linear map $M: (\C^2)^{\tens n_C}\rightarrow (\C^2)^{\tens n_D}$:

\[\tikzfig{M_map}\]

By employing the partial transpose in the computational basis we convert it into the state

\[\tikzfig{M_as_state}\]

i.e. inserting $n_C$ Bell pairs. By the definition of $f_0$ we know that this has an independent stabiliser, with one $Z$ and $n_C-1$ $I$s followed by some $n_D$-fold tensor product of $Z$ and $I$, for each of the $n_C$ qubits. From $f_0^\intercal$ it also has an independent stabiliser, with some $n_C$-fold tensor product of $X$ and $I$ followed by $n_D-1$ Is and one $X$, for each of the $n_D$ qubits. $\ket{\psi}$ is therefore a stabiliser state. Further, from Theorem 5.1 of [28] it has a presentation as a `phase-free ZX diagram', of the form

\[\tikzfig{M_state_ZX}\]

where the top $n_C$ qubits do not have a green spider. We perform the partial transpose again to convert the state $\ket{\psi}$ back into the map $M$, which has the form

\[\tikzfig{map_ZX_diagram}\]

Any ZX diagram of this form can be expressed as a matrix over $\F_2$, mapping $X$-basis states from $(\C^2)^{\tens n_C}$ to $(\C^2)^{\tens n_D}$. The example above, ignoring the ellipses, has the matrix

\[\begin{pmatrix}
\end{pmatrix}\]

which is equal to $f_0$; the point of the above rigmarole is thus to say that $f_0$ is precisely a linear map between $X$-basis states, which one can check easily. We can then perform Gaussian elimination on $f_0$, performing row operations, which produce CNOTs on the r.h.s. of the diagram in the manner of [29], until the matrix is in reduced row echelon form. We then perform column operations producing CNOTs on the l.h.s. of the diagram, until the matrix has at most one 1 in each row and column. This can be performed using the leading coefficients to remove all other 1s in that row. The final matrix just represents a permutation of qubits with some states and effects. An empty column corresponds to a $\bra{0}$ effect, and an empty row a $\ket{+}$ state. We thus end up with a presentation of $M$ in the form

\[\tikzfig{big_gate}\]

On our example, this is then

\[\tikzfig{CNOT_decomp}\]

which one can check maps $Z\tens I\tens I \mapsto Z\tens Z$ etc.
As a consequence $\bar{M} = M$, i.e. the conjugate of $M$ is just $M$.

If $n_C =0$ then the map $M$ is actually a stabiliser state of the form $M = \ket{+}^{\otimes n_D}$. When $n_D = 0$ then $M = \bra{0}^{\otimes n_C}$.

When $n_C =0$ we see that $M$ has exactly $n_D$ independent stabilisers with 1 $X$ and $n_D-1$ $I$s, for each qubit to put $X$ on. The flipped argument applies when $n_D=0$.

An $\overline{X}$-preserving code map $\CF_{\overline{X}}$ from a CSS code $(D_\bullet, D_\bullet^*)$ to $(C_\bullet, C_\bullet^*)$ is a pair of chain maps $(f_\bullet, f_\bullet^*)$, for $f_\bullet: C_\bullet \rightarrow D_\bullet$ and $f_\bullet^*: D_\bullet^* \rightarrow C_\bullet^*$.

\[\begin{tikzcd}
\ \arrow[d, "\CF_{\overline{X}}"', Leftarrow] & (C_\bullet, C_\bullet^*)\arrow[d, "f_\bullet"', shift right=2ex]\\
\ & (D_\bullet, D_\bullet^*)\arrow[u, "f^*_\bullet"', shift right=2ex]
\end{tikzcd}\]

So $\CF_{\overline{X}}$ is just mapping in the other direction to $\CF_{\overline{Z}}$ from before, and we say that $\CF_{\overline{X}}$ is opposite to $\CF_{\overline{Z}}$. In this case, when we interpret $\CF_{\overline{X}}$ as a $\C$-linear map $L$, it has the property that $L U_X = U'_XL$ and that any $U_X$ gives a specified $U'_X$, and $L U_Z = U'_ZL$, but that any $U'_Z$ gives a specified $U_Z$ but not vice versa.

By inspecting the stabilisers we see that, for $\CF_{\overline{Z}}$ with interpretation $M$ and $\CF_{\overline{X}}$ with interpretation $L$, $L = M^\dagger = M^\intercal$.

Let $\CF_{\overline{X}}$ be an $\overline{X}$-preserving code map between codes $(D_\bullet, D_\bullet^*)$ and $(C_\bullet, C_\bullet^*)$ with qubit counts $n_D$ and $n_C$. The interpretation of $\CF_{\overline{X}}$ as a $\C$-linear map $L$ in $\FHilb$ has a presentation as a circuit with gates drawn from $\{{\rm CNOT},\ket{0}, \bra{+}\}$.

If $n_D = 0$ then $L = \ket{0}^{\otimes n_C}$, and if $n_C = 0$ then $L = \bra{+}^{\otimes n_D}$.

The restrictions of $\CF_{\overline{Z}}$ and $\CF_{\overline{X}}$ to use only $H_0(f_\bullet)$ and $H_0(f_\bullet^*)$ also have interpretations as $\C$-linear maps on logical qubits in the same way, and Proposition <ref> and Corollary <ref> also apply to such interpretations.

While our definitions are for chain complexes of length 2, in principle one can map between any two codes with an arbitrary number of meta-checks, or between a classical code and quantum code, which could be interpreted as `switching on/off' either $X$ or $Z$ stabiliser measurements.

While code maps are related to code deformations, we are aware of code deformation protocols which do not appear to fit in the model of chain maps described. For example, when moving defects around on the surface code for the purpose of, say, defect braiding [20], neither $\overline{Z}$ nor $\overline{X}$ operators are preserved in the sense we give here.

§ CSS CODE SURGERY

§.§ Colimits in $\Chains$

To understand code surgery we require some additional chain complex technology, namely colimits. Coproducts, pushouts and coequalisers are directly relevant for our applications. We have already covered coproducts in Lemma <ref>, so we describe pushouts and coequalisers here.

The pushout of chain maps $f_\bullet: A_\bullet \rightarrow C_\bullet$ and $g_\bullet:A_\bullet \rightarrow D_\bullet$ gives the chain complex $Q_\bullet$, where each component is the pushout $Q_n$ of $f_n$ and $g_n$. The differentials $\del^{Q_\bullet}_n$ are given by the unique mediating map from each component's pushout. Specifically, if we have the pushout

\[\begin{tikzcd}
A_\bullet \arrow[r, "g_\bullet"]\arrow[d, "f_\bullet"'] & D_\bullet \arrow[d,"l_\bullet"]\\
C_\bullet \arrow[r,"k_\bullet"'] & Q_\bullet\arrow[ul, phantom, "\usebox\pushout", very near start]
\end{tikzcd}\]

then for degrees $n, n+1$ we have

\[\begin{tikzcd}
A_n\arrow[rrr,"g_n"]\arrow[ddd,"f_n"'] & & & D_n\arrow[ddd, "l_n"]\\
& A_{n+1}\arrow[ul, "\del^{A_\bullet}_n"]\arrow[r, "g_{n+1}"]\arrow[d, "f_{n+1}"'] & D_{n+1}\arrow[ur, "\del^{D_\bullet}_n"]\arrow[d, "l_{n+1}"] &\\
& C_{n+1}\arrow[dl,"\del^{C_\bullet}_n"]\arrow[r,"k_{n+1}"'] & Q_{n+1}\arrow[dr, dotted, "\del^{Q_\bullet}_n"]\arrow[ul, phantom, "\usebox\pushout", very near start] &\\
C_n\arrow[rrr, "k_n"'] & & & Q_n
\end{tikzcd}\]

\[Q_n = (C \oplus D)_\bullet/f_n\sim g_n; \quad k_n(c)=[c] \in Q_n;\quad l_n(d)=[d]\in Q_n.\]

with $[c]$ being the equivalence class in $Q_n$ having $c$ as a representative, and the same for $[d]$. As $k_n\circ \del^{C_\bullet}_n\circ f_{n+1} = l_n\circ \del^{D_\bullet}_n\circ g_{n+1}$ and the inner square is a pushout in $\MatF$, there is a unique matrix $\del^{Q_\bullet}_n$. The differentials satisfy $\del^{Q_\bullet}_n\circ \del^{Q_\bullet}_{n+1} = 0$, and one can additionally check that this is indeed a pushout in $\Chains$ by considering the universal property at each component.

The coequaliser of chain maps $\begin{tikzcd} C_\bullet \arrow[r, "f", shift left=1.5ex]\arrow[r, "g"', shift right=1.5ex]& D_\bullet \end{tikzcd}$ is a chain complex $E_\bullet$ and chain map $\coeq(f,g)_\bullet : D_\bullet \rightarrow E_\bullet$, which we will just call $\coeq_\bullet$. We have $E_n = D_n/f_n\sim g_n$ and $\coeq_n(d) = [d]$.

Doing some minor diagram chasing one can check that this is indeed a coequaliser in $\Chains$.

We can view the pushout

\[\begin{tikzcd}
A_\bullet \arrow[r, "g_\bullet"]\arrow[d, "f_\bullet"'] & D_\bullet \arrow[d,"l_\bullet"]\\
C_\bullet \arrow[r,"k_\bullet"'] & Q_\bullet\arrow[ul, phantom, "\usebox\pushout", very near start]
\end{tikzcd}\]

as the coequaliser of $\begin{tikzcd}A_\bullet \arrow[r, "\tau_\bullet \circ f_\bullet",shift left=1.5ex]\arrow[r, "\omega_\bullet \circ g_\bullet"',shift right=1.5ex]& (C\oplus D)_\bullet\end{tikzcd}$  for the inclusion maps $\begin{tikzcd}C_\bullet \arrow[r, "\tau_\bullet", hookrightarrow] & (C\oplus D)_\bullet\end{tikzcd}$, $\begin{tikzcd}D_\bullet \arrow[r, "\omega_\bullet", hookrightarrow] & (C\oplus D)_\bullet\end{tikzcd}$.
The difference is that the pair of chain maps $k_\bullet, l_\bullet$ have been replaced with the single map $\coeq_\bullet$, so we have

\[\begin{tikzcd}A_\bullet \arrow[r, "\tau_\bullet\circ f_\bullet",shift left=1.5ex]\arrow[r, "\omega_\bullet\circ g_\bullet"',shift right=1.5ex]& (C\oplus D)_\bullet \arrow[r, "\coeq_\bullet"] &Q_\bullet
\end{tikzcd}\]

We can view coequalisers as instances of pushouts as well, doing a sort of reverse of the procedure above.

As with all colimits, those above are defined by the
category theory only up to isomorphism.
Because we are working over a field, the isomorphism class
of a chain complex $Q_\bullet$ is completely determined by the dimensions of the underlying vector spaces $\{\dim Q_i\}_i$ and its Betti numbers,
which is the set $\{\dim H_i(Q_\bullet)\}_i$
of dimensions of the homology spaces.
This is a homological version of the rank-nullity theorem.
These are very large isomorphism classes, and we require
more fine grained control over which chain complexes
are chosen by the colimits. Thus we pick out the obvious
objects from their isomorphism
classes, which are those described in the definitions of the colimits above.

$\Chains$ is an Abelian category, and thus is finitely complete and cocomplete, meaning that it has all finite limits and colimits.

While this is well-known, we sketch a proof of this lemma in Appendix <ref> for completeness. There we also sketch some additional limits, but we only need colimits in this work.

§.§ Generic code surgery

We now give a general set of definitions for surgery between arbitrary compatible CSS codes; the condition for compatibility is very weak here. Working at this level of generality means that we cannot prove very much about the output codes or relevant logical maps. As a consequence, we will then focus on particular surgeries which make use of `gluing' or `tearing' along logical $\overline{Z}$ or $\overline{X}$ operators in Section <ref>.

Let $(C_\bullet, C_\bullet^*)$, $(D_\bullet, D_\bullet^*)$ and $(A_\bullet, A_\bullet^*)$ be CSS codes, such that there is a span of chain complexes

\[\begin{tikzcd}
A_\bullet \arrow[r, rightarrow, "g_\bullet"]\arrow[d, rightarrow, "f_\bullet"'] & D_\bullet\\
C_\bullet & &
\end{tikzcd}\]

The $Z$-type merged code of $(C_\bullet, C_\bullet^*)$ and $(D_\bullet, D_\bullet^*)$ along $f_\bullet, g_\bullet$ is the code $(Q_\bullet, Q_\bullet^*)$ such that $Q_\bullet$ is the pushout of the above diagram.

Recall from Remark <ref> that we can view any pushout as a coequaliser. We thus have

\[\begin{tikzcd}
A_\bullet \arrow[r, "\iota_C\circ f_\bullet",shift left=1.5ex]\arrow[r, "\iota_D\circ g_\bullet"',shift right=1.5ex] & (C\oplus D)_\bullet \arrow[r, "\coeq_\bullet"] &Q_\bullet
\end{tikzcd}\]

and we call $\coeq_\bullet$ the $Z$-merge chain map. We can bundle this up into a $Z$-merge code map:

\begin{equation}\begin{tikzcd}\label{eq:Z_merge_code_map}
\ \arrow[d, "\CF_{\overline{Z}}"', Rightarrow] & ((C\oplus D)_\bullet, (C\oplus D)_\bullet^*)\arrow[d, "\coeq_\bullet"', shift right=3ex]\\
\ & (Q_\bullet, Q_\bullet^*)\arrow[u, "\coeq^*_\bullet"', shift right=3ex]
\end{tikzcd}\end{equation}

We then call $\coeq_\bullet^*: Q_\bullet^*\rightarrow (C\oplus D)_\bullet^*$ an $X$-split chain map, and hence we have an $X$-split code map too:

\begin{equation}\begin{tikzcd}
\ \arrow[d, "\CF_{\overline{X}}"', Leftarrow] & ((C\oplus D)_\bullet, (C\oplus D)_\bullet^*)\arrow[d, "\coeq_\bullet"', shift right=3ex]\\
\ & (Q_\bullet, Q_\bullet^*)\arrow[u, "\coeq^*_\bullet"', shift right=3ex]
\end{tikzcd}\end{equation}

Let $(C_\bullet, C^*_\bullet)$, $(D_\bullet, D^*_\bullet)$ and $(A_\bullet, A^*_\bullet)$ be CSS codes, such that there is a span of chain complexes

\[\begin{tikzcd}
A^*_\bullet \arrow[r, rightarrow, "g^*_\bullet"]\arrow[d, rightarrow, "f^*_\bullet"'] & D^*_\bullet\\
C^*_\bullet & &
\end{tikzcd}\]

the $X$-type merged code of $(C_\bullet, C^*_\bullet)$ and $(D_\bullet, D^*_\bullet)$ along $f^*_\bullet, g^*_\bullet$ is the code $(Q_\bullet, Q^*_\bullet)$ such that $Q^*_\bullet$ is the pushout of the above diagram.

We have an $X$-merge chain map and thus $X$-merge code map using the coequaliser picture, so

\[\begin{tikzcd}
\ \arrow[d, "\CE_{\overline{X}}"', Leftarrow] & (Q_\bullet, Q_\bullet^*)\arrow[d, "\coeq_\bullet"', shift right=3ex]\\
\ & ((C\oplus D)_\bullet, (C\oplus D)_\bullet^*)\arrow[u, "\coeq^*_\bullet"', shift right=3ex]
\end{tikzcd}\]

We also have a $Z$-split chain map and the $Z$-split code map $\CE_{\overline{Z}}$ by taking the opposite.

\[\begin{tikzcd}
\ \arrow[d, "\CE_{\overline{Z}}"', Rightarrow] & (Q_\bullet, Q_\bullet^*)\arrow[d, "\coeq_\bullet"', shift right=3ex]\\
\ & ((C\oplus D)_\bullet, (C\oplus D)_\bullet^*)\arrow[u, "\coeq^*_\bullet"', shift right=3ex]
\end{tikzcd}\]

This is rather abstract, so let's see a small concrete example.

Consider the following pushout of cell complexes:

\[\tikzfig{small_pushout}\]

We have not properly formalised pushouts of square lattices in the main body for brevity, but we do so in Appendix <ref>. Informally, we are just `gluing along' the graph in the top left corner, where the edges to be glued are coloured in blue.

We can consider this pushout to be in $\Chains$ [Categorically, this is because there is a cocontinuous functor from the appropriate category of square lattices to $\Chains$.], giving the pushout:

\[\begin{tikzcd}
A_\bullet \arrow[r, "g_\bullet"]\arrow[d, "f_\bullet"'] & D_\bullet \arrow[d,"q_\bullet"]\\
C_\bullet \arrow[r,"p_\bullet"'] & Q_\bullet\arrow[ul, phantom, "\usebox\pushout", very near start]
\end{tikzcd}\]

\[\begin{tikzcd}A_\bullet = \F_2 \arrow[r, "\del_{-1}^{A_\bullet}"] & \F_2^2\end{tikzcd}\]

\[\begin{tikzcd}C_\bullet = \F_2 \arrow[r, "\del_{0}^{C_\bullet}"] & \F_2^3\arrow[r,"\del_{-1}^{C_\bullet}"] & \F_2^2\end{tikzcd}\]

\[\begin{tikzcd}D_\bullet = \F_2 \arrow[r, "\del_{0}^{D_\bullet}"] & \F_2^3\arrow[r,"\del_{-1}^{D_\bullet}"] & \F_2^2\end{tikzcd}\]

\[\del_{-1}^{A_\bullet} = \begin{pmatrix}1\\1\end{pmatrix};\quad
\del_{0}^{C_\bullet} = \del_{0}^{D_\bullet} = \begin{pmatrix}1\\1\\1 \end{pmatrix}; \quad
\del_{-1}^{C_\bullet} = \begin{pmatrix}1 & 1 & 0\\0&1&1 \end{pmatrix};\quad
\del_{-1}^{D_\bullet} = \begin{pmatrix}1 & 0 & 1\\0&1&1 \end{pmatrix}.
\]

One can see from the cell complexes that we have

\[\begin{tikzcd}Q_\bullet = \F_2^2 \arrow[r, "\del_{0}^{Q_\bullet}"] &\F_2^5 \arrow[r,"\del_{-1}^{Q_\bullet}"] & \F_2^2\end{tikzcd}\]

\[\del_{0}^{Q_\bullet} = \begin{pmatrix}1&0\\1&1\\1&0\\0&1\\0&1 \end{pmatrix};
\quad \del_{-1}^{Q_\bullet} = \begin{pmatrix}1&1&0&1&0\\0&1&1&0&1\end{pmatrix}\]

Rather than compute the pushout maps, let us instead give the coequaliser $\coeq_\bullet : (C\oplus D)_\bullet \rightarrow Q_\bullet$:

\[\begin{tikzcd}(C\oplus D)_{1}\arrow[r, "\del^{(C\oplus D)_\bullet}_{0}"]\arrow[d, "\coeq_{1}"] & (C\oplus D)_{0}\arrow[r, "\del^{(C\oplus D)_\bullet}_{-1}"]\arrow[d, "\coeq_{0}"] & (C\oplus D)_{-1}\arrow[d,"\coeq_{-1}"]\\
Q_{1}\arrow[r, "\del^{Q_\bullet}_0"] & Q_0\arrow[r, "\del^{Q_\bullet}_{-1}"] & Q_{-1}\end{tikzcd}
\]

We immediately see that $\coeq_1 = \id$. For the other two surjections we have

\[\coeq_0 = \begin{pmatrix}1&0&0&0&0&0\\0&1&0&0&0&1\\0&0&1&0&0&0\\0&0&0&1&0&0\\0&0&0&0&1&0\end{pmatrix};\quad \coeq_{-1} = \begin{pmatrix}1&0&1&0\\0&1&0&1\end{pmatrix} \]

Finally we interpret all the chain complexes in this pushout as being the $Z$-type complexes of CSS codes $(A_\bullet, A_\bullet^*)$, $(C_\bullet, C_\bullet^*)$ etc. Thus we have a $Z$-merge code map $\CF_{\overline{Z}}$, with an interpretation $M$ as a $\C$-linear map, using $\coeq_0$ and $\coeq_0^\intercal$. We refrain from writing out the full $32$-by-$64$ matrix, but as a ZX-diagram using gates from $\{{\rm CNOT}, \ket{+}, \bra{0}\}$ we have simply

\[\tikzfig{small_pushout_basis_state_map}\]

We know from Lemma <ref> that this map must restrict to a map on logical qubits. However, easy calculations show that $H_0((C\oplus D)_\bullet) = 0$, while $H_0(Q_\bullet) = 1$. That is, in the code $((C\oplus D)_\bullet, (C\oplus D)_\bullet^*)$ there are no logical qubits – there are still operators which show up as errors and some which don't, but all of those which don't are products of $Z$ or $X$ stabiliser generators. By Corollary <ref> and Corollary <ref> the logical map in $\FHilb$ is then just $\ket{+}$. This trivially preserves both $\overline{Z}$ and $\overline{X}$ operators, although its opposite code map $\CF_{\overline{X}}$ does not preserve $\overline{Z}$ operators.

This example was very simple, but the idea extends in quite a general way. To give an idea of how general this notion of CSS code surgery is, consider the balanced product codes from [3, 38].
The balanced product of codes is by definition a coequaliser in $\Chains$, and so we can convert it into a pushout using routine category theory. The coequaliser is

\[\begin{tikzcd}(C\tens A\tens D)_\bullet \arrow[r, "g_\bullet"', shift right=1.5ex]\arrow[r, "f_\bullet", shift left=1.5ex]& (C\tens D)_\bullet \arrow[r, "\coeq_\bullet"] &(C\tens_A D)_\bullet\end{tikzcd}\]

where $g_\bullet$ and $f_\bullet$ represent left and right actions of $A_\bullet$ respectively. Recall that we did not explicitly define the tensor product in the main body for brevity, but see Appendix <ref>. Then to this coequaliser we can associate a pushout,

\[\begin{tikzcd}
((C\tens A\tens D)\oplus (C\tens D))_\bullet \arrow[r, "(g_\bullet\ |\ \id_\bullet)"]\arrow[d, "(f_\bullet\ |\ \id_\bullet)"'] & (C\tens D)_\bullet \arrow[d,"l_\bullet"]\\
(C\tens D)_\bullet \arrow[r,"k_\bullet"'] & (C\tens_A D)_\bullet\arrow[ul, phantom, "\usebox\pushout", very near start]
\end{tikzcd}\]

where one can check that the universal property is the same in both cases. Thus we can think of a balanced product as a merge of tensor product codes, with the apex being two adjacent tensor product codes. As the maps in the span are evidently not monic, the merge is of a distinctly different sort from Example <ref>, and also the $\overline{Z}$- and $\overline{X}$-merges we will describe in Section <ref>.

It would be convenient if we could guarantee some properties of pushouts in general; for example, if the pushout of LDPC codes was also LDPC, or if the homologies were always preserved. Unfortunately, the definition is general enough that neither of these are true. We discuss this in slightly greater detail in Appendix <ref>, but the gist is that we need to stipulate some additional conditions to guarantee bounds on these quantities.

§.§ Surgery along a logical operator

The procedure of merging here is closely related to that of `welding' in [36]. Our focus is not just on the resultant codes, but the maps on physical and logical data. On codes generated from square lattices, the merges here will correspond to a pushout along a `string' through the lattice.

Let $\begin{tikzcd}C_\bullet = C_{1}\arrow[r, "\del_0"]& C_0\arrow[r, "\del_{-1}"]& C_{-1}\end{tikzcd}$ be a length 2 chain complex. Let $v\in C_0$ be a vector such that $v \in \ker(\del^{C_\bullet}_{-1})\backslash \im(\del^{C_\bullet}_{0})$. We now construct the logical operator subcomplex $V_\bullet$. This has:

\[\tilde{V}_0 = {\rm supp\ } v; \quad \del^{V_\bullet}_{-1} = \del^{C_\bullet}_{-1}\restriction_{{\rm supp\ } v}; \quad V_{-1} = \im(\del^{V_\bullet}_{-1})\]

where ${\rm supp\ } v$ is the set of basis vectors in the support of $v$, and $\del_i\restriction_S$ is the restriction of a differential to a subset $S$ of its domain. All other components and differentials of $V_\bullet$ are zero.

There is a monic $f_\bullet : V_\bullet \hookrightarrow C_\bullet$ given by the inclusion maps of $V_0 \subseteq C_0$ etc.

Let $V_\bullet$ be a logical operator subcomplex of two chain complexes
\[\begin{tikzcd}C_\bullet = C_{1}\arrow[r, "\del_0"]& C_0\arrow[r, "\del_{-1}"]& C_{-1}\end{tikzcd}\]
\[\begin{tikzcd}D_\bullet = D_{1}\arrow[r, "\del_0"]& D_0\arrow[r, "\del_{-1}"]& D_{-1}\end{tikzcd}\]
simultaneously, so there is some vector $v \in C_0$ and $w \in D_0$ such that $\tilde{V}_0 = {\rm supp\ } v = {\rm supp\ } w$, $\del^{V_\bullet}_{-1} = \del^{C_\bullet}_{-1}\restriction_{{\rm supp\ } v} = \del^{D_\bullet}_{-1}\restriction_{{\rm supp\ } w}$ etc. Then there is a monic span

\[\begin{tikzcd}
V_\bullet \arrow[r, hookrightarrow, "g_\bullet"]\arrow[d, hookrightarrow, "f_\bullet"'] & D_\bullet\\
C_\bullet & &
\end{tikzcd}\]

This monic span has the pushout

\[\begin{tikzcd}
V_\bullet \arrow[r, hookrightarrow, "g_\bullet"]\arrow[d, hookrightarrow, "f_\bullet"'] & D_\bullet \arrow[d,"q_\bullet"]\\
C_\bullet \arrow[r,"p_\bullet"'] & Q_\bullet\arrow[ul, phantom, "\usebox\pushout", very near start]
\end{tikzcd}\]

with components

\[Q_1 = C_1 \oplus D_1;\quad Q_0 = C_0\oplus D_0/v \sim w;\quad Q_{-1} = C_{-1} \oplus D_{-1}/ (\im(\del^{C_\bullet}_{-1}\restriction_{{\rm supp\ } v}) \sim \im(\del^{D_\bullet}_{-1}\restriction_{{\rm supp\ } w})).\]

The construction here is inspired by [11].

Let $(C_\bullet, C_\bullet^*)$ and $(D_\bullet, D_\bullet^*)$ be CSS codes. Let $(V_\bullet, V_\bullet^*)$ be a CSS code such that $V_\bullet$ is a logical operator subcomplex of $C_\bullet$ and $D_\bullet$; this means that $(V_\bullet, V_\bullet^*)$ can be seen as merely a classical code, as $V_1=0$. Then the $Z$-type merged CSS code $(Q_\bullet, Q_\bullet^*)$ is called the $\overline{Z}$-merged code of $(C_\bullet, C_\bullet^*)$ and $(D_\bullet, D_\bullet^*)$ along $(V_\bullet, V_\bullet^*)$.

We are particularly interested in based CSS codes, i.e. when the logical spaces have bases.
Let $\tilde{H}_0(C_\bullet) = \{[u]_i\}$, $\tilde{H}_0(D_\bullet) = \{[v]_j\}$ be the bases for the spaces of logical $Z$ operators in $C_\bullet$ and $D_\bullet$ respectively. Let $V_\bullet$ be a logical operator subcomplex such that for the inclusion maps $f_\bullet$ and $g_\bullet$, $\im(f_0)$ is the space spanned by nonzero basis vectors of $u$ for some $u \in [u]_i$ and $\im(g_0)$ is the space spanned by nonzero basis vectors of $v$ for some $v\in [v]_j$, i.e. the chosen $\overline{Z}$ logical operator acts on a single logical qubit in each of the bases. Further, assume that all $u' \in \ker(\del^{C_\bullet}_{-1})\backslash \im(\del^{C_\bullet}_{0})$ such that ${\rm supp\ }(u') \subseteq {\rm supp\ }(u)$ obey $u' \in [u]$, and also all $v' \in \ker(\del^{D_\bullet}_{-1})\backslash \im(\del^{D_\bullet}_{0})$ such that ${\rm supp\ }(v') \subseteq {\rm supp\ }(v)$ obey $v'\in [v]$. Lastly, assume that every vector $s\in V_0$, $f_0(s) \in \ker(\del^{C_\bullet}_{-1})\backslash \im(\del^{C_\bullet}_{0}) \iff g_0(s) \in \ker(\del^{D_\bullet}_{-1})\backslash \im(\del^{D_\bullet}_{0})$. By the previous assumption every vector in $\im (f_0)$ which is a nontrivial logical operator must belong to the same equivalence class, and the same for $\im (g_0)$. Then we say that $V_\bullet$ is a separated logical operator subcomplex. We also say that the corresponding $\overline{Z}$-merged code of $(C_\bullet, C_\bullet^*)$ and $(D_\bullet, D_\bullet^*)$ along $(V_\bullet, V_\bullet^*)$ is separated.

The intuition here, following [11], is that it is convenient when the logical operators we glue along do not themselves contain any nontrivial logical operators belonging to a different logical qubit; if they do, the gluing procedure may yield a more complicated output code, as we could be merging along multiple logical operators simultaneously. In Appendix <ref> we demonstrate that it is possible for this condition to not be satisfied, using a patch of octagonal surface code. Additionally, we do not want the gluing procedure to send any logical $\overline{Z}$ operators to stabilisers. We now prove some basic results.

Let $(Q_\bullet, Q_\bullet^*)$ be a separated $\overline{Z}$-merged code with metrics $\llbracket n_Q, k_Q, d_Q \rrbracket$, and let $\llbracket n_C, k_C, d_C\rrbracket$, $\llbracket n_D, k_D, d_D\rrbracket$ be the metrics of $(C_\bullet, C_\bullet^*)$ and $(D_\bullet, D_\bullet^*)$ respectively. Let $n_V = \dim V_0$ be the Hamming weight of $u$ and $v$. Then

\[n_Q = n_C + n_D - n_V;\quad k_Q = k_C + k_D -1\]

Further, let $\{[u]_i\}$ and $\{[v]_j\}$ be the bases for $H_0(C_\bullet)$ and $H_0(D_\bullet)$ respectively, and say w.l.o.g. that $u \in [u]_1$ and $v \in [v]_1$ are the vectors quotiented by the pushout. Then $H_0(Q_\bullet)$ has a basis $\{[w]_l\}$ for $l \leq k_C + k_D - 1$, where $[w]_1 = [u]_1 = [v]_1$, $[w]_l = [u]_l$ when $1 < l \leq k_C$ and $[w]_{l} = [v]_{l-k_C+1}$ for $k_C < l \leq k_C + k_D -1$.

$n_Q$ is immediate by the definition. For $k_Q$, we start off by considering the code $((C_\bullet \oplus D_\bullet), (C_\bullet \oplus D_\bullet)^*)$.
Given $u \in [u]_1$ and $v \in [v]_1$, any other representatives $y \in [u]_1$, $x \in [v]_1$ belong to the same equivalence class in $H_0(Q_\bullet)$, as $y \sim u \sim v \sim x$. [These equivalences are from different quotients: $y \sim u$ and $v\sim x$ are homology quotients, while $u\sim v$ is a quotient from the pushout.]

Now, let $s\in [u]_i$, $i\neq 1$. Let $z \in D_0$ be a vector such that $z\neq v$ and ${\rm supp\ }(z) \subset {\rm supp\ }(v)$. Then either $s+z \in [u]_i$, if $z \in \im(\del^{D_\bullet}_{0})$, or $s+z \notin Z_0(C_\bullet \oplus D_\bullet)$ otherwise, by the separation property. If $s+z \notin Z_0(C_\bullet \oplus D_\bullet)$ then $s+z \notin Z_0(Q_\bullet)$, as the quotiented vectors $u, v$ are both in $Z_0(C_\bullet \oplus D_\bullet)$.

So for any $s \in [u]_i$, $i\neq 1$, there is no $[t] \in H_0(D_\bullet)$ with representative $t$ such that $s \sim t$ in $Q_0$. A similar argument applies the other way around. The quotient is surjective, so there are no additional homology classes in $H_0(Q_\bullet)$. Thus the bases $\{[u]_i\}$ and $\{[v]_j\}$ remain partitioned, with the sole exception of $[u]_1$ and $[v]_1$ as above.

We would like to study not only the resultant code given some $\overline{Z}$-merge, but also the map on the logical space. We will now switch from pushouts to coequalisers. Recall the $Z$-merge code map $\CF_{\overline{Z}}$ from Equation <ref>. We call this a $\overline{Z}$-merge code map when the merge is along a $\overline{Z}$-operator as above, and from now on we assume that all merges are separated.

Let the $\overline{Z}$-merge code map

\[\begin{tikzcd}
\ \arrow[d, "\CF_{\overline{Z}}"', Rightarrow] & ((C\oplus D)_\bullet, (C\oplus D)_\bullet^*)\arrow[d, "\coeq_\bullet"', shift right=3ex]\\
\ & (Q_\bullet, Q_\bullet^*)\arrow[u, "\coeq^*_\bullet"', shift right=3ex]
\end{tikzcd}\]

of a separated $\overline{Z}$-merged code have its interpretation $M$ as a $\C$-linear map. Then $M$ acts as

\[\tikzfig{merge_map_ZX} = \begin{pmatrix}
1 & 0 & 0 & 0\\
0 & 0 & 0 & 1
\end{pmatrix}\]

on each pair of qubits in $((C\oplus D)_\bullet, (C\oplus D)_\bullet^*)$ which are equivalent in $(Q_\bullet, Q_\bullet^*)$ and $M$ acts as identity on all other qubits.

$M$ must have the following maps on Paulis on each pair of qubits being merged:

\[Z\tens I \mapsto Z;\quad I\tens Z\mapsto Z;\quad X\tens X \mapsto X\]

which uniquely defines the matrix above. In other words we have $\ket{00}\mapsto \ket{0}$, $\ket{11}\mapsto \ket{1}$, $\ket{01} \mapsto \ket{0}, \ket{10}\mapsto \ket{0}$ etc, which has the convenient presentation as the ZX diagram on the left above.

Let $(Q_\bullet, Q_\bullet^*)$ be a separated $\overline{Z}$-merged code of $(C_\bullet, C_\bullet^*)$ and $(D_\bullet, D_\bullet^*)$ along $(V_\bullet, V_\bullet^*)$. Call $f=H_0(\coeq_\bullet)$. Then

\[f([u]_i + [v]_j) = [w]_l\]

where $[w]_l$ was defined in Lemma <ref>.

This is obvious by considering the surjection in question and using Lemma <ref>. It essentially says that on each pair of logical operators in $((C\oplus D)_\bullet, (C\oplus D)_\bullet^*)$ which are both being quotiented, $\CF_{\overline{Z}}$ acts as:

\[\overline{Z}\tens \overline{I} \mapsto \overline{Z};\quad \overline{I}\tens \overline{Z}\mapsto \overline{Z};\quad \overline{X}\tens \overline{X} \mapsto \overline{X}\]

where the map on $X$s is inferred from the dual.

\[d^X_Q \geq \min(d^X_C, d^X_D)\]

By considering the code map $\CF_{\overline{Z}}$, we see that any $X$ logical operator in $(Q_\bullet, Q_\bullet^*)$ has a preimage which is also an $\overline{X}$ logical operator in $((C\oplus D)_\bullet, (C\oplus D)_\bullet^*)$. This is because $f^*$, the dual part of $\CF_{\overline{Z}}$, restricts to $H_0(f^*)$.

Note that we do not in general have a lower bound on $d^Z_Q$ in terms of $d^Z_C$ and $d^Z_D$. We can see this from the discussion in Section <ref>. Given the code map $\CF_{\overline{Z}}$, the chain map $f_0: (C\oplus D)_0\rightarrow Q_0$ restricts to $H_0(f)$, but this does not preclude there being other vectors in $(C\oplus D)_0\backslash \ker \del^{(C\oplus D)_\bullet}_{-1}$ which are mapped into one of the equivalence classes in $H_0(Q_\bullet)$. In computational terms, while we cannot have detectable $X$ operators in the initial codes which are mapped to logicals by the code map $\CF_{\overline{Z}}$, this is unfortunately possible with detectable $Z$ operators. We illustrate this with an example in Appendix <ref>.

We now show that, if we consider two codes to be merged as instances of LDPC families, their combined $\overline{Z}$-merged code code is also LDPC. Recall Definition <ref>.
Say our input codes $(C_\bullet, C_\bullet^*)$, $(D_\bullet, D_\bullet^*)$ have maximal weights of generators labelled $w^Z_C$, $w^X_C$ and $w^Z_D$, $w^X_D$ respectively. Let $(Q_\bullet, Q_\bullet^*)$ be a separated $\overline{Z}$-merged code of $(C_\bullet, C_\bullet^*)$ and $(D_\bullet, D_\bullet^*)$ along $(V_\bullet, V_\bullet^*)$. Then

\[w^Z_Q = \max(w^Z_C, w^Z_D);\quad w^X_Q < w^X_C + w^X_D.\]

Similarly, letting the input codes have maximal number of shared generators on a single qubit $q^Z_C$, $q^X_C$ and $q^Z_D$, $q^X_D$ we have

\[q^Z_Q \leq q^Z_C + q^Z_D;\quad q^X_Q = \max(q^X_C,q^X_D)\]

None of the $Z$-type generators are quotiented by a $\overline{Z}$-merge map, so $w^Z_Q = w^Z_{(C\oplus D)} = \max(w^Z_C, w^Z_D)$. For the $X$-type generators, in the worst case the two generators which are made to be equivalent by the merge are the highest weight ones. For these generators to appear in $V_{-1}$ they must have at least two qubits in each of their support which is in $V_0$, and thus these qubits are merged together, so $w^X_Q < w^X_C + w^X_D$.

Next, using again the fact that none of the $Z$-type generators are quotiented, a single qubit could in the worst case be the result of merging two qubits in $(C_\bullet, C_\bullet^*)$ and $(D_\bullet, D_\bullet^*)$ which each have the maximal number of shared $Z$-type generators, so $q^Z_Q \leq q^Z_C + q^Z_D$. For the $X$ case, if a qubit is in $V_0$ then all $X$-type generators it is in the support of must appear in $V_{-1}$. Therefore, when any two qubits are merged all of their $X$-type generators are also merged. Thus $q^X_Q = q^X_{(C\oplus D)} = \max(q^X_C,q^X_D)$.

Note that as $w^Z$, $w^X$ and $q^Z$, $q^X$ are at worst additive in those of the input codes, the $\overline{Z}$-merge of two  LDPC codes is still LDPC, assuming the pushout is still well-defined using matching $\overline{Z}$ operators for each member of the code families. Next, we dualise everything, and talk about $\overline{X}$-merges.

Let $(C_\bullet, C_\bullet^*)$ and $(D_\bullet, D_\bullet^*)$ be CSS codes. Let $(V_\bullet, V_\bullet^*)$ be a CSS code such that $V^*_\bullet$ is a logical operator subcomplex of $C^*_\bullet$ and $D^*_\bullet$, and $Q_\bullet^*$ is the merged complex along $V_\bullet^*$. Then the CSS code $(Q_\bullet, Q_\bullet^*)$ is called the $\overline{X}$-merged code of $(C_\bullet, C_\bullet^*)$ and $(D_\bullet, D_\bullet^*)$ along $(V_\bullet, V_\bullet^*)$.

In this case we glue along an $\overline{X}$ logical operator instead. The notion of separation, Lemma <ref> and Lemma <ref> carry over by transposing appropriately.

An $\overline{X}$-merge map $\CE_{\overline{X}}$ can be defined similarly, and a similar result as Lemma <ref> applies to separated $\overline{X}$-merged codes.

Let the $\overline{X}$-merge code map of a separated $\overline{X}$-merged code have its interpretation $L$ as a $\C$-linear map. Then $L$ acts as

\[\tikzfig{merge_map2_ZX} = \frac{1}{\sqrt{2}}\begin{pmatrix}
1 & 0 & 0 & 1\\
0 & 1 & 1 & 0
\end{pmatrix}\]

on each pair of qubits in $((C\oplus D)^*_\bullet, (C\oplus D)_\bullet)$ which are equivalent in $(Q^*_\bullet, Q_\bullet)$, i.e. $\ket{++}\mapsto \ket{+}$, $\ket{--}\mapsto \ket{-}$, and $L$ acts as identity on all other qubits.

This time, $L$ must have the maps

\[X\tens I\mapsto X; \quad I\tens X\mapsto X;\quad Z\tens Z\mapsto Z\]

Similarly, the maps on logical operators are

\[\overline{X}\tens \overline{I} \mapsto \overline{X};\quad \overline{I}\tens \overline{X}\mapsto \overline{X};\quad \overline{Z}\tens \overline{Z} \mapsto \overline{Z}\]

Having discussed $\overline{Z}$- and $\overline{X}$-merged codes, we briefly mention splits. These are just the opposite code maps to $\CF_{\overline{Z}}$ and $\CE_{\overline{X}}$. In both cases, all the mappings are determined entirely by Lemma <ref> by taking transposes or adjoints when appropriate.

In practice, when the CSS codes in question hold multiple logical qubits it may be preferable to merge/split along multiple disjoint $\overline{Z}$ or $\overline{X}$ operators at the same time. Such a protocol is entirely viable within our framework, and requires only minor tweaks to the above results. The same is true should one wish to merge/split along operators within the same code.

We now look at a short series of examples.

§.§ Examples of surgery

§.§.§ Lattice surgery

Lattice surgery is the prototypical instance of CSS code surgery. It starts with patches of surface code and then employs separated splits and merges to perform non-unitary logical operations [25]. The presentation we give of lattice surgery is quite idiosyncratic, in the sense that we perform the merges on physical edges/qubits, whereas the standard method is to introduce additional edges between patches to join them together. We remedy this in Section <ref>.

Consider the pushout of cell complexes below:

\[\tikzfig{pushout_cubicals}\]

As before, we informally consider this to be `gluing along' the graph in the top left, but for completeness it is formalised in Appendix <ref>. By considering the pushout to be in $\Chains$, we have:

\[\begin{tikzcd}
V_\bullet \arrow[r, "g_\bullet",hookrightarrow]\arrow[d, "f_\bullet"',hookrightarrow] & D_\bullet \arrow[d,"q_\bullet"]\\
C_\bullet \arrow[r,"p_\bullet"'] & Q_\bullet\arrow[ul, phantom, "\usebox\pushout", very near start]
\end{tikzcd}\]

Letting $\coeq_\bullet : (C \oplus D)_\bullet \rightarrow Q_\bullet$ be the relevant coequaliser map, we see that $\CF_{\overline{Z}} = (\coeq_\bullet, \coeq_\bullet^*)$ constitutes a separated $\overline{Z}$-merge map. In particular, observe that $\CF_{\overline{Z}}$ sends the logical operators:

\begin{align*}
&\overline{Z} \tens \overline{I} \mapsto \overline{Z}\\
&\overline{I} \tens \overline{Z} \mapsto \overline{Z}\\
&\overline{X} \tens \overline{X} \mapsto \overline{X}
\end{align*}

as predicted by Lemma <ref>.

The first two give $H_0(\coeq_\bullet) = \begin{pmatrix}1 & 1\end{pmatrix}$ and the last $H_0(\coeq_\bullet^*) = \begin{pmatrix}1\\1 \end{pmatrix}$. $\CF_{\overline{Z}}$ is evidently $\overline{Z}$-preserving but not $\overline{X}$-preserving, as $\overline{X} \tens \overline{I}$ is taken to an operation which is detected by the $Z$ stabilisers. Observe that we end up with a greater cosystolic distance of $(Q_\bullet, Q_\bullet^*)$ than we started with in $((C \oplus D)_\bullet,(C \oplus D)_\bullet^*)$.

If we instead consider the pair $(\coeq_\bullet, \coeq^*_\bullet)$ as an $\overline{X}$-preserving code map $\CF_{\overline{X}}$, then it is a separated $\overline{X}$-split map. In terms of cell complexes we would have [Pedantically, this is a morphism in the opposite category of cell complexes $\OACC^{\rm op}$.]

\[\tikzfig{X_split_patches}\]

We similarly have a separated $\overline{X}$-merge map and separated $\overline{Z}$-split map with the obvious forms by dualising appropriately.

While it is convenient to choose logical operators along patch boundaries to glue along, so that the complexes can all be embedded on the 2D plane, this is not necessary. One could intersect two patches along any matching operator.

Recall the toric code $(C_\bullet, C_\bullet^*)$ from Example <ref>. We can merge two copies of $C_\bullet$ along a logical $\overline{Z}$ operator, which corresponds to an essential cycle of each torus. The resultant code will then look like two tori intersecting, depending somewhat on the choices of essential cycle:

\[\tikzfig{toric_code_merge}\]

The $\overline{Z}$-merge map on logical qubits will be the same as for patches.

§.§.§ Shor code surgery

Of course, the pushout we take does not have to come from square lattices. Let $C_\bullet$ and $D_\bullet$ be two copies of Shor codes from Example <ref>.[The Shor code can be constructed as a cellulation of the projective plane, so it is actually not wholly dissimilar from the lattice codes [21].] We can perform separated merges between them. We give two examples. First, for a $\overline{Z}$-merge, we take the logical $\overline{Z}$ operator $\overline{Z} = \bigotimes_i^8 Z_i$ and apply Definition <ref> to get the logical operator subcomplex:

\[\begin{tikzcd}V_\bullet = \cdots \arrow[r] & V_0\arrow[r, "P_X"] &V_{-1}\arrow[r] & \cdots \end{tikzcd}\]

with $V_0 = \F_2^9$, $V_{-1} = \F_2^2$, and all other components zero. This is just $C_\bullet$ from Example <ref> truncated to be length 1, as this logical $\overline{Z}$ operator has support on all physical qubits. The monic chain map $f_\bullet$ given by inclusion into the Shor code is just

\[\begin{tikzcd}\cdots \arrow[r] & 0\arrow[r, "0"]\arrow[d, "0"] & V_0\arrow[r, "P_X"]\arrow[d, "\id"] & V_{-1}\arrow[r]\arrow[d,"\id"] & \cdots\\
\cdots \arrow[r] & C_1\arrow[r, "P_Z^\intercal"] & C_{0}\arrow[r, "P_X"] & C_{-1}\arrow[r] & \cdots\end{tikzcd}
\]

and the same for $g_\bullet$. The pushout of

\[\begin{tikzcd}
V_\bullet \arrow[r, hookrightarrow, "g_\bullet"]\arrow[d, hookrightarrow, "f_\bullet"'] & D_\bullet\\
C_\bullet & &
\end{tikzcd}\]

will then be

\[\begin{tikzcd}
Q_\bullet = \cdots \arrow[r] &\F_2^{12} \arrow[r, "\del^{Q_\bullet}_0"] &\F_2^9 \arrow[r, "\del^{Q_\bullet}_{-1}"] & \F_2^2\arrow[r] &\cdots
\end{tikzcd}\]

where $\del^{Q_\bullet}_{-1} = P_X$ and $\del^{Q_\bullet}_{0} = \begin{pmatrix}P_Z^\intercal | P_Z^\intercal \end{pmatrix}$. The map on logical data is fully determined by Lemma <ref>. We have ended up with virtually the same code as the Shor code, except that we have a duplicate for every $Z$-type generator, i.e. every measurement of $Z$ stabilisers is performed twice and the result noted separately. While this example is very simple, it highlights that the result of a merge can have somewhat subtle features, such as duplicating measurements, which the two input codes do not. [One can fix this categorically by specifying additional conditions on $V_\bullet$ if desired.]

For our second case, we use a different (but equivalent) logical operator, $\overline{Z} = Z_1\tens Z_4\tens Z_7$. We still glue two copies of the Shor code, but now we have $V_0 = \F_2^3$, $V_{-1} = \F_2^2$ and $\del^{V_\bullet}_{-1} = \begin{pmatrix} 1&1&0\\1&0&1\end{pmatrix}$. That is, our logical operator subcomplex is just the repetition code from Example <ref>. We then have

\[\begin{tikzcd}\cdots \arrow[r] & 0\arrow[r, "0"]\arrow[d, "0"] & V_0\arrow[r, "\del^{V_\bullet}_{-1}"]\arrow[d, "f_0"] & V_{-1}\arrow[r]\arrow[d,"\id"] & \cdots\\
\cdots \arrow[r] & C_1\arrow[r, "P_Z^\intercal"] & C_{0}\arrow[r, "P_X"] & C_{-1}\arrow[r] & \cdots\end{tikzcd}
\]

\[f_0 = \begin{pmatrix} 1&0&0\\0&0&0\\0&0&0\\0&1&0\\0&0&0\\0&0&0\\0&0&1\\0&0&0\\0&0&0\end{pmatrix}\]

and the same for $g_0$, forming again a monic span of chain complexes. The resultant $\overline{Z}$-merged code is then

\[\begin{tikzcd}
Q_\bullet = \cdots \arrow[r] &\F_2^{12} \arrow[r, "\del^{Q_\bullet}_0"] &\F_2^{15} \arrow[r, "\del^{Q_\bullet}_{-1}"] & \F_2^2\arrow[r] &\cdots
\end{tikzcd}\]

and the large matrices $\del^{Q_\bullet}_0$ and $\del^{Q_\bullet}_{-1}$ are easily obtained by quotienting out rows and columns from $\del^{C_\bullet}_0\oplus \del^{D_\bullet}_0$ and $\del^{C_\bullet}_{-1}\oplus \del^{D_\bullet}_{-1}$.

We do not expound on this example, but the protocols for performing $\overline{X}$ and $\overline{Z}$ measurements by generalised lattice surgery in [11] can be seen as using separated $\overline{Z}$- and $\overline{X}$-merged codes, with the caveat that they don't perform the merge maps; instead they initialise fresh qubits in the ancillary hypergraph code and measure all stabiliser generators. The present work has overlap with their protocols, but we do not subsume them; for example their $\overline{X}\tens \overline{Z}$ and $\overline{Y}$ measurement methods are outside of our formalism, as they lead to non-CSS codes.

§ FAULT-TOLERANT LOGICAL OPERATIONS

We now describe how our abstract formalism leads to a general set of fault-tolerant logical operations for CSS codes. We consider this to be a good application of the homological algebraic formalism, as we suspect these logical operations would be  challenging to derive without the machinery of $\Chains$. [An alternative approach could be to use Tanner graphs.] So far in our description of code maps there are two main assumptions baked in: that one can perform linear maps between CSS codes (a) deterministically and (b) fault-tolerantly, both of which are desired for performing quantum computation.

For assumption (a), we can only implement code maps which are interpreted as an isometry deterministically. If they are not, instead we must perform measurements on physical qubits. Recall from Proposition <ref> that every code map has an interpretation constructed from CNOTs and some additional states and effects taken from $\{\ket{+}, \bra{0}\}$ for a $\overline{Z}$-preserving code map or $\{\bra{+}, \ket{0}\}$ for an $\overline{X}$-preserving code map. This means that in order to implement the code map non-deterministically, one need only apply CNOTs and measure some qubits in the $Z$-basis (for a $\overline{Z}$-preserving code map) or the $X$-basis ($\overline{X}$-preserving code map). Of course, should we acquire the undesired measurement result, we induce errors in our code map. There is no protocol for correcting these errors in all generality. For assumption (b), there is no protocol for performing arbitrary CNOT circuits on physical qubits in a code fault-tolerantly. However, when performing CSS code surgery which is a separated $\overline{Z}$- or $\overline{X}$-merge, we have a protocol which addresses both (a) and (b).

§.§ Procedure summary

Our procedure for performing a fault-tolerant $\overline{Z}\tens\overline{Z}$ measurement is as follows:

* Find a matching $\overline{Z}$ logical operator which belongs to both initial codes, in the sense of Definition <ref>.

* Verify that this logical operator satisfies the separation property of Definition <ref> in both codes.

* Verify that the $\overline{Z}$ logical operator is gauge-fixable in those codes, in the sense of Definition <ref> below.

* Verify that the merge is bounded below, in the sense of Definition <ref> below.

* Perform the merge as described in Proposition <ref>.

We do not know how difficult it will be in general to perform the verification in steps (2), (3) and (4) for codes (or families of codes) of interest.

§.§ Full description of procedure

The first additional technical condition involves gauge fixing. For reasons of brevity we do not describe the connection between lattice surgery and gauge fixing, but refer the interested reader to [41]. Briefly, we will consider the whole system to be a subsystem code, and fix the gauges of the $\overline{Z}$ operators we are gluing along.

Let $C_\bullet$ be a chain complex and $u$ be a representative of the equivalence class $[u]\in H_0(C_\bullet)$, which is a basis vector for $H_0(C_\bullet)$. Let $x$ be a vector in $C_0$ such that $|x| = 1$ and $x\cdot u = 1$. We say that $x$ is a qubit in the support of $u$. Recall from Lemma <ref> that $u$ has a unique paired basis vector $[v]\in H_0(C_\bullet^*)$ such that $[u]\cdot [v] = 1$. It is possible to safely correct a qubit $x$ when there is a vector $v \in [v]$ such that $x\cdot v =1$ and $y \cdot v = 0$ for all other qubits $y$ in the support of $u$. We say that $u$ is gauge-fixable when it is possible to safely correct all qubits in the support of $u$.

Consider the Shor code from Example <ref> and Section <ref>. The $\overline{Z}$ operator

\[v = \begin{pmatrix}1&1&1&1&1&1&1&1&1\end{pmatrix}^\intercal\]

has qubits in its support for which it is not possible to safely correct, as there are only 4 representatives of the nonzero equivalence class $[w]\in H_0(C_\bullet^*)$ but 9 qubits for which being able to safely correct is necessary. However, it is possible to safely correct all qubits in the support of the $\overline{Z}$ operator

\[u = \begin{pmatrix}1&0&0&1&0&0&1&0&0 \end{pmatrix}^\intercal,\]

where $u\in [v]$, with the fixing operators:

\[\begin{pmatrix}1&1&1&0&0&0&0&0&0 \end{pmatrix}^\intercal;\quad \begin{pmatrix}0&0&0&1&1&1&0&0&0 \end{pmatrix}^\intercal;\quad \begin{pmatrix}0&0&0&0&0&0&1&1&1 \end{pmatrix}^\intercal\]

The same definition of gauge-fixability applies if we exchange $X$ and $Z$ appropriately. Next we will require the tensor product of chain complexes, for which see Appendix <ref>.

Let $V_\bullet = \begin{tikzcd}V_0\arrow[r] & V_{-1}\end{tikzcd}$ and $P_\bullet = \begin{tikzcd}P_1 \arrow[r, "\begin{pmatrix}1\\1\end{pmatrix}"] & P_0\end{tikzcd}$ be length 1 chain complexes. Then we can make the tensor product chain complex $W_\bullet = (P \tens V)_\bullet$. Explicitly,

\[W_\bullet = \begin{tikzcd}W_1 \arrow[r] &W_0 \arrow[r] & W_{-1}\end{tikzcd}\]

\[W_1 = P_1\tens V_0 = V_0;\quad W_0 = (P_0\tens V_0)\oplus (P_{1}\tens V_{-1}) = (\F_2^2\tens V_0)\oplus V_{-1};\quad W_{-1} = P_0\tens V_{-1} = \F_2^2 \tens V_{-1}\]

Also, $\del_{0}^{W_\bullet} = \begin{pmatrix}\id_{V_0}\\\id_{V_0}\\ \del_{-1}^{V_\bullet}\end{pmatrix}$ and $\del_{-1}^{W_\bullet} = \begin{pmatrix} \id_{\F_2^2}\tens \del_{-1}^{V_\bullet} &\del^{P_\bullet}_0 \tens \id_{V_{-1}} \end{pmatrix} = \begin{pmatrix}\del_{-1}^{V_\bullet} & 0 & \id_{V_{-1}}\\ 0 & \del_{-1}^{V_\bullet} & \id_{V_{-1}}\end{pmatrix}$.

In the case where $V_\bullet$ is a string along a patch of surface code, say of the form:

\[\tikzfig{open_graph_eg}\]

then $W_\bullet$ will be of the form

\[\tikzfig{sandwich_code}\]

as a square lattice, see Definition <ref>. We can see this as the `intermediate section' used to perform lattice surgery.

Let $V_\bullet$ be a $\overline{Z}$ logical operator subcomplex of a chain complex $C_\bullet$, and let $V_\bullet$ satisfy the separation property from Definition <ref>. Then

\[w_W^X = w_C^X + 1;\quad w^Z_W = q^X_C + 2; \quad q^X_W = \max(q^X_C, 2); \quad q^Z_W = \max(w^X_C,1)\]

and $\dim H_0(W_\bullet) = \dim H_0(V_\bullet) \geq 1$.

Observe that $\del_{-1}^{V_\bullet}$ has maximum row weight $w^X_C$ and column weight $q^X_C$. Then inspect the matrices $\del_{0}^{W_\bullet}$ and $\del_{-1}^{W_\bullet}$ from Definition <ref>. For $\dim H_0(W_\bullet)$, we use the Künneth formula, for which see Lemma <ref>, which in this case says $H_0((P \tens V)_\bullet) = (H_{0}(P_\bullet)\tens H_0(V_\bullet))\oplus (H_1(P_\bullet) \tens H_{-1}(V_\bullet))$. We then have

\[\dim H_{0}(P_\bullet) = 1; \quad \dim H_1(P_\bullet) = 1; \quad \dim H_0(V_\bullet) \geq 1; \quad \dim H_{-1}(V_\bullet) = 0\]

where the last comes from the fact that $V_{-1} = \im(\del_{-1}^{V_\bullet})$, using Definition <ref>. Note $\dim H_0(V_\bullet) \geq 1$ as there is always at least one nonzero vector which is mapped to zero by construction, and $B_0(V_\bullet) =0$. $\dim H_0(V_\bullet)$ may be greater than 1, as there may be other nonzero vectors in $Z_0(V_\bullet)$ which previously corresponded to products of $Z$ stabilisers in $C_\bullet$ and $D_\bullet$ before taking the logical operator subcomplex. Thus $\dim H_0(W_\bullet) = \dim H_0(V_\bullet) \geq 1$.

Let $V_\bullet$ be a simultaneous $\overline{Z}$ logical operator subcomplex of both $C_\bullet$ and $D_\bullet$, satisfying the separation property. Then define the `sandwiched code' $(T_\bullet, T_\bullet^*)$, with $T_\bullet$ as the pushout of a pushout:

\[\begin{tikzcd}&V_\bullet \arrow[r, hookrightarrow] \arrow[d, hookrightarrow]& C_\bullet \arrow[d]\\
V_\bullet \arrow[d, hookrightarrow]\arrow[r, hookrightarrow] & W_\bullet \arrow[r] & R_\bullet \arrow[d]\arrow[ul, phantom, "\usebox\pushout", very near start]\\
D_\bullet \arrow[rr] & & T_\bullet\arrow[ul, phantom, "\usebox\pushout", very near start]\end{tikzcd}\]

where the middle term is $W_\bullet = (P \tens V)_\bullet$ from Definition <ref> above, and the two inclusion maps $V_\bullet \hookrightarrow W_\bullet$ map $V_0$ into each of the copies of $V_0$ in $W_0$, and the same for $V_{-1}$.

Colloquially, we are gluing first one side of the code $W_\bullet$ to $C_\bullet$, and then the other side to $D_\bullet$. [We could equally do it the other way, in which case the two pushouts would be flipped, but this does not change $T_\bullet$.]

The `sandwiched code' $(T_\bullet, T_\bullet^*)$ has

\[n_T = n_C + n_D + r;\quad k_T = k_C + k_D - 1;\quad d^X_T \geq \min(d^X_C, d^X_D)\]

\[w^X_{T} \leq w^X_{C\oplus D} +1; \quad w^Z_{T} \leq
\max(w^Z_{C\oplus D}, q^X_{C\oplus D}+2);\quad q^Z_T \leq q^Z_{C\oplus D} + w^X_{C\oplus D}; \quad q^X_T = \max(q^X_{C\oplus D}, 2)\]

For $n_T$, just apply Lemma <ref> twice. For $k_T$, use Lemma <ref> but observe that all elements of $H_0(W_\bullet)$ are merged with $[0] \in H_0(C_\bullet)$ and $[0]\in H_0(D_\bullet)$, and thus do not contribute to $k_T$, apart from the single one corresponding to a logical operator in $H_0(C_\bullet)$ and $H_0(D_\bullet)$, by the separation property. Bearing this in mind one can also apply Lemma <ref> twice.

For $d^X_T$, we first show that $(R_\bullet, R_\bullet^*)$ has $d^X_R \geq d^X_C$. Every $\overline{X}$ operator in $(W_\bullet, W_\bullet^*)$ which is not sent to a stabiliser by the first pushout must anticommute with the $\overline{Z}$ operator used to construct $V_\bullet$, and thus must have support on those qubits. In addition, it must have a matched $\overline{X}$ operator in $(C_\bullet, C_\bullet^*)$, which also has support on those qubits. As the only other $\overline{X}$ operators in $(R_\bullet, R_\bullet^*)$ are those in $(C_\bullet, C_\bullet^*)$ which are unaffected by the merge, having no support on the qubits being merged, $d^X_R \geq d^X_C$. Then $d^X_T \geq \min(d^X_C, d^X_D)$ using Lemma <ref>.

For $w^X_{T}$, the pushouts will glue each $X$ type stabiliser generator in $W_\bullet$ into those in $C_\bullet$ and $D_\bullet$ in such a way that they will have exactly one extra qubit in the support, by the product construction of $W_\bullet$; we can see this from $\del_{-1}^{W_\bullet}$ in Definition <ref>, as there is exactly a single 1 which is not part of the $\del_{-1}^{V_\bullet}$ in any given row of the matrix.

For $w^Z_{T}, q^Z_T$ and $q^X_T$ we just use Lemma <ref> and apply Lemma <ref> twice.

The intuition here is that rather than gluing two codes $(C_\bullet, C_\bullet^*)$ and $(D_\bullet, D_\bullet^*)$ together directly along a logical operator, we have made a low distance hypergraph code $(W_\bullet, W_\bullet^*)$ and used that to sandwich the codes. A consequence of the above lemma is that this `sandwiching' procedure maps LDPC codes to LDPC codes.
Importantly, under suitable conditions the two pushouts let us perform a code map on logical qubits fault-tolerantly.

Let $(T_\bullet, T_\bullet^*)$ have no logical $\overline{Z}$ operators with weight lower than $d_{C\oplus D}$. Then we say that the merged code has distance bounded below.

Note that the only $Z$ operators which can lower the distance are those with support on the logical $\overline{Z}$ which is used to construct $V_\bullet$, as all others will be unchanged by the quotient. The condition for a merge to have distance bounded below is quite a tricky one, as we do not know of a way to check this easily. Because of Lemma <ref>, this problem is isolated to $\overline{Z}$ operators, as the distance is guaranteed to be bounded below for $\overline{X}$ operators.

Let $(C_\bullet, C_\bullet^*)$ and $(D_\bullet, D_\bullet^*)$ be CSS codes which share a separated gauge-fixable $\overline{Z}$ operator on $m$ physical qubits and $r$ $X$-type stabiliser generators each; let the relevant logical qubits be $i$ and $j$, and let $V_\bullet$ be the logical operator subcomplex of $C_\bullet$ and $D_\bullet$ such that the codes admit a separated $\overline{Z}$-merge. Further, let $d$ be the code distance of $((C\oplus D)_\bullet, (C\oplus D)_\bullet^*)$, and let the merged code $(T_\bullet, T_\bullet^*)$ have distance bounded below. Then there is a fault-tolerant procedure with distance $d$ for implementing a $\overline{Z}\tens \overline{Z}$ measurement on the pair $i$, $j$ of logical qubits, which gives the code $(T_\bullet, T_\bullet^*)$. This procedure requires $r$ auxiliary clean qubits and an additional $m$ $Z$-type stabiliser generators.

We aim to go from the code $((C\oplus D)_\bullet, (C\oplus D)_\bullet^*)$ to $(T_\bullet, T_\bullet^*)$. The code map we apply to physical qubits is as follows. We call the physical qubits in the support of the logical operators to be glued together the participating qubits. We initialise a fresh qubit in the $\ket{+}$ state for each pairing of $X$-measurements on the two logical operators of qubits $i$ and $j$, that is for each qubit in $(W_\bullet,W_\bullet^*)$ which is not glued to a qubit in $(C_\bullet, C_\bullet^*)$ or $(D_\bullet, D_\bullet^*)$.

We now modify the stabilisers to get to $(T_\bullet, T_\bullet^*)$. To start, change the $X$ stabiliser generators with support on the participating qubits to have one additional fresh qubit each, so that each pairing of $X$-measurements shares one fresh qubit. We add a new $Z$ stabiliser generator with weight $a+2$ for each participating qubit in one of the logical operators to be glued, where $a$ is the number of $X$ type generators of which that physical qubit is in the support. One can see this using Definition <ref>, as on the middle code $(W_\bullet, W_\bullet^*)$ we have

\[P_Z = (\del_0^{W_\bullet})^\intercal = \begin{pmatrix}\id_{\F_2^m} & \id_{\F_2^m} & (\del^{V_\bullet}_{-1})^\intercal\end{pmatrix}\]

We then measure $d$ rounds of all stabilisers. All of the qubits in the domain of the last block of $P_Z$ above are those which were initialised to $\ket{+}$. The only other qubits which contribute to the new $Z$ stabiliser generators are those on either side of the sandwiched code, i.e. those along the $\overline{Z}$ logical operators of qubits $i$ and $j$. Each of the physical qubits in the support of these logical operators is measured exactly once by the new $Z$ stabiliser generators, and they are measured in pairs, one from each side; therefore performing these measurements and recording the total product is equivalent to measuring $\overline{Z}\tens \overline{Z}$. We will now check this, and verify that it is fault-tolerant.

Let the outcome of a new $Z$-type measurement be $c_{\lambda} \in \{1,-1\}$, and the overall outcome $c_L = \prod_{\lambda \leq m} c_{\lambda}$. Whenever $c_{\lambda} = -1$ we apply the gauge fixing operator $X_{\lambda} = \bigotimes_{(i \in v\ |\ v_i = 1)} X_i$ for the specified $v \in C_0^*$ (or one could choose a gauge fixing operator using $D_0^*$ instead). We let $X_{c_L} = \prod_{(\lambda\ |\ c_{\lambda} = -1)}X_{\lambda}$. On participating physical qubits, the merge is then

\[X_{c_L} \prod_{\lambda}\frac{I + c_{\lambda}Z}{2} = \prod_{\lambda}\frac{I + Z}{2} X_{c_L}\]

where we abuse notation somewhat to let $I$ and $Z$ here refer to tensor products thereof. As each $X_{\lambda}$ belongs to the same equivalence class of logical $\overline{X}$ operators in $H_0(C_\bullet)$, if $c_L = 1$ then $X_{c_L}$ acts as identity on the logical space; if $c_L = -1$ then $X_{c_L}$ acts as $\overline{X}$ on logical qubit $i$ in the code before merging. One can then see that these two branches are precisely the branches of the logical $\overline{Z}\tens \overline{Z}$ measurement. As the measurements were performed using $d$ rounds of stabilisers, and the gauge fixing operators each have support on at least $d$ qubits, the overall procedure is fault-tolerant with code distance $d$.

We also check that the procedure is insensitive to errors in the initialisation of fresh qubits. If a qubit is initialised instead to $\ket{-}$, or equivalently suffers a $Z$ error, then the new $Z$ stabiliser measurements are insensitive to this change, and it will just show up at the $X$ measurements on either side of the fresh qubit. If it suffers some other error, say sending it to $\ket{1}$, then each new stabiliser measurement with that qubit in its support may have its result flipped. By construction of $V_\bullet$, each fresh qubit is in the support of an even number of new $Z$ stabiliser measurements, and so initialising the fresh qubits incorrectly will not change $c_L$.

As ZX diagrams, the branches are:

\[\tikzfig{merge_map_branch1}\ ;\quad \tikzfig{merge_map_branch2}\]

on logical qubits $i$ and $j$, and all other logical qubits in the code are acted on as identity. We can freely choose which logical qubit may have the red $\pi$ spider, as it will differ only up to a red $\pi$ – i.e. a logical $\overline{X}$ – on the output logical qubit. In practice, depending on the code there will typically be cheaper ways of fixing the gauges than using an $\overline{X}$ logical operator for each $-1$ outcome, as there could be an $\overline{X}$ logical operator which has support on multiple of the qubits belonging to new stabilisers. Moreover, one can just update the Pauli frame rather than apply any actual $\overline{X}$ logical operators. The ability to do so is necessary, however, so that the $-1$ outcome is well-defined.

The protocol obviates the problem of performing the code map on physical qubits deterministically, as the only non-isometric transformations we perform are measurements of stabiliser generators. However, the code map on logical qubits is still not isometric, hence we have a logical measurement.

For the prototypical example of lattice surgery we then have:

\[\tikzfig{sandwich_merge}\]

We also look at a less obvious example, that of fault-tolerant surgery of the Shor code, in Appendix <ref>.

By dualising appropriately one can perform an $\overline{X}$-merge by sandwiching in a similar manner. We can also do the `inverse` of the merge operation fault-tolerantly:

Let $(T_\bullet, T_\bullet^*)$ be a CSS code formed by sandwiching codes $(C_\bullet, C_\bullet^*)$ and $(D_\bullet, D_\bullet^*)$ together along a $\overline{Z}$ operator. Then there is a fault-tolerant procedure to implement a code map on logical qubits $\CE_{\overline{X}}$ from $(T_\bullet, T_\bullet^*)$ to $((C\oplus D)_\bullet, (C\oplus D)_\bullet^*)$.

As the initial code is already a sandwiched code we can just take the opposite of sandwiching. We delete the qubits belonging to the intermediate code $(W_\bullet, W_\bullet^*)$ but not $(C_\bullet, C_\bullet^*)$ or $(D_\bullet, D_\bullet^*)$ by measuring them out in the $X$-basis. The code map $\CE_{\overline{X}}$ on participating logical qubits is

\[\tikzfig{split_map}\]

by following precisely the same logic as for traditional lattice surgery [25].
Again, by dualising appropriately we get the last split operation.

Given a procedure for making $\overline{Z}\tens\overline{Z}$ and $\overline{X}\tens\overline{X}$ logical measurements and the isometries from splits, one can easily construct a logical CNOT between suitable CSS codes following, say, [5] and observing that the same ZX diagrammatic arguments apply. Augmented with some Clifford single-qubit gates and non-stabiliser logical states one can then perform universal computation. As opposed to some other methods of performing entangling gates with CSS codes, e.g. transversal 2-qubit gates, the schemes above require only the $m$ qubits from the respective $\overline{Z}$ or $\overline{X}$ operators to participate, and we expect $m \ll n$ for practical codes. Unlike that of [11], our method does not require a large ancillary hypergraph product code, which can have significantly worse encoding rate and code distance scaling than the LDPC codes holding data. Our method does not require the code to be `self-ZX-dual' in the sense of [8], and unlike [26] our method does not require the code to be defined on any kind of manifold, and is purely algebraic in description; moreover, these works study single qubit gates and measurements rather than entangling gates.

§ CONCLUSIONS AND FURTHER WORK

We believe our constructions are flexible and conceptually quite simple. The immediate next step is to benchmark our CSS code surgery against other methods of performing entangling logical gates and characterise which CSS codes admit gauge-fixable  separated logical operators such that the merges have distance bounded below.

The pushouts we gave along logical operators are the most obvious cases. By taking pushouts of more interesting spans other maps on logical data can be obtained, although by Proposition <ref> and Corollary <ref> all code maps as we defined them are limited and do not allow for universal quantum computation; we also do not know whether other pushouts would allow the maps on logical data to be performed fault-tolerantly.

Herein we assumed that the two codes being `glued' are different codes, but the same principles apply if we have only one code we would like to perform internal surgery on. In this case, the correct universal construction to use should be a coequaliser. There may be other uses of colimits in $\Chains$. The method of constructing good families of quantum LDPC codes in [38] uses a balanced product, which is also a coequaliser, and the instance used there could be generalised. The initial classical codes come from expander graphs, and the quotient is with respect to actions of a finite group $G$. This group could be changed to some other differential graded algebra, and the starting codes do not have to come from graphs. A generalised balanced product in this way cannot have asymptotically better $\llbracket n,k,d\rrbracket$ metrics than those of [38], up to constant factors, as their construction already saturates the relevant bounds. However, it would be interesting to see if one can obtain better metrics for concrete instances. Calculating the homologies of such codes is likely to require tools such as spectral sequences.

It should be possible to extend the definitions of $\overline{X}$- and $\overline{Z}$-merges straightforwardly to include metachecks [10], say by specifying that the logical operator subcomplex $V_\bullet$ now runs from $V_0$ to $V_{-2}$, so it has $X$-checks and then metachecks on $X$-checks, but we have not proved how this affects metachecks in the merged code.

There are several ways in which our constructions could be generalised to other codes. The obvious generalisation is to qudit CSS codes. For qudits of prime dimension $q$, everything should generalise fairly straightforwardly using a different finite field $\F_q$ but in this case the cell complexes will require additional data in the form of an orientation on edges, as is familiar for qudit surface codes. When $q$ is not prime, one formalism for CSS codes with dimension $q$ looks to be chain complexes in $\Z_q$-$\mathtt{FFMod}$, the category of free finite modules over the ring $\Z_q$. As $\Z_q$ is not generally a P.I.D. this may complicate the homological algebra.

Second, if we wish to upgrade to more general stabiliser codes we can no longer use chain complexes. The differential composition $P_X P_Z^\intercal$ is a special case of the symplectic product $\omega(M,N) = M\omega N^\intercal$ for $\omega = \begin{pmatrix} 0_n &I_n\\ -I_n&0_n \end{pmatrix}$ [23], but by generalising to such a product we lose the separation of $Z$ and $X$ stabilisers to form a pair of differentials. It is unclear what the appropriate notion of a quotient along an $\overline{X}$ or $\overline{Z}$ operator is for such codes.

For quantum codes which are not stabiliser but are based on cell complexes, such as the Kitaev model [30], there are no stabiliser generators, but the codes are still `CSS-like', in the sense that vertices correspond to actions of the group algebra $\C G$ and faces actions of the function algebra $\C(G)$, with each measurement outcome corresponding to an irreducible representation of the quantum double $D(G) = \C(G)\lcross\ \C G$. More generally we can replace $\C G$ and $\C(G)$ with $H$ and $H^*$ for any semisimple Hopf algebra $H$ [35, 14] while retaining the relevant features of the model. Just as there are no stabiliser generators, there are no longer $Z$ and $X$-operators, but there are ribbon operators. As special cases there are ribbon operators which correspond to actions of only $\C G$ or $\C(G)$. The first author recently generalised lattice surgery to Kitaev models [15], albeit with some caveats. In the same way that CSS codes generalise stabiliser codes based on cell complexes, we imagine there could be a general class of commuting projector models using the quantum double, which are not necessarily defined on a tessellated manifold. The details of such a class are not known to us, and generalising the notion of `sites' on a lattice seems difficult. We speculate that the notion of `gluing' along, say, a $\C G$ operator could work for such commuting projector models.

§ ACKNOWLEDGEMENTS

AC thanks Aleks Kissinger for helpful discussions about Lemma <ref>, and both Aleks Kissinger and John van de Wetering for helpful discussions about Proposition <ref>. AC also thanks the Wolfson Harrison UK Research Council Quantum Foundation Scholarship for making this work possible.

We are grateful to Christophe Vuillot for spotting a crucial error in an earlier version of this paper, and for providing us with the illustrative example in Appendix <ref>.

[1]F. Arute, K. Arya, R. Babbush et al., Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019)
[2]B. Audoux and A. Couvreur, On tensor products of CSS Codes, Ann. Inst. Henri Poincaré Comb. Phys. Interact. 6 (2019), no. 2, pp. 239–287
[3]N. P. Breuckmann and J. N. Eberhardt, Balanced Product Quantum Codes, IEEE Transactions on Information Theory 2021
[4]N. P. Breuckmann and J. N. Eberhardt, Quantum Low-Density Parity-Check Codes, PRX Quantum 2 (4), 040101, 2021
[5]N. de Beaudrap and D. Horsman, The ZX calculus is a language for surface code lattice surgery, Quantum 4, 218 (2020)
[6]H. Bombin and M. A. Martin-Delgado, Homological error correction: Classical and quantum codes, Journal of Mathematical Physics, vol. 48, no. 5, p. 052105 (2007)
[7]S. Bravyi, B. M. Terhal and B. Leemhuis, Majorana fermion codes, New Journal of Physics, vol. 12, no. 8, p. 083039 (2010)
[8]N. P. Breuckmann and S. Burton, Fold-Transversal Clifford Gates for Quantum Codes, arXiv:2202.06647 [quant-ph]
[9]N. P. Breuckmann, C. Vuillot, E. Campbell, A. Krishna and B. M. Terhal, Hyperbolic and Semi-Hyperbolic Surface Codes for Quantum Storage, Quantum Science and Technology, Volume 2, Number 3, 2017
[10]E. T. Campbell, A theory of single-shot error correction for adversarial noise, Quantum Science and Technology 4, 025006 (2019)
[11]L. Z. Cohen, I. H. Kim, S. D. Bartlett and B. J. Brown, Low-overhead fault-tolerant quantum computing using long-range connectivity, Sci. Adv. 8, eabn1717 (2022)
[12]C. Ryan-Anderson, N. C. Brown, M. S. Allman et al., Implementing Fault-tolerant Entangling Gates on the Five-qubit Code and the Color Code, arXiv:2208.01863 [quant-ph]
[13]A. Cowtan, Qudit lattice surgery, In Proceedings QPL 2022, arXiv:2204.13228 [quant-ph]
[14]A. Cowtan and S. Majid, Quantum double aspects of surface code models, J. Math. Phys. 63 (2022) 042202
[15]A. Cowtan and S. Majid, Algebraic aspects of boundaries in the Kitaev quantum double model, arXiv:2208.06317 [math.QA]
[16]N. Delfosse, Decoding color codes by projection onto surface codes, Phys. Rev. A 89, 012317 (2014)
[17]E. Dennis, A. Kitaev, A. Landahl and J. Preskill, Topological quantum memory, J. Math. Phys. 43, 4452-4505 (2002)
[18]G. Duclos-Cianci and D. Poulin, A renormalization group decoding algorithm for topological quantum codes, Information Theory Workshop (ITW), 2010 IEEE, pp.1-5, Aug. 30 2010-Sept. 3 2010
[19]D. S. Farley, Finiteness and CAT(0) properties of diagram groups, Topology, Vol. 42, Issue 5 (2003) pp. 1065-1082
[20]A. G. Fowler, M. Mariantoni, J. M. Martinis and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation, Phys. Rev. A 86 (2012)
[21]M. H. Freedman and D. A. Meyer, Projective plane and planar quantum codes, Foundations of Computational Mathematics 1, 325 (2001)
[22]D. Gottesman, Stabilizer Codes and Quantum Error Correction, Caltech PhD. thesis, arXiv:quant-ph/9705052
[23]J. Haah, Algebraic Methods for Quantum Codes on Lattices, Revista Colombiana de Matemáticas, 50(2), 299-349 (2016)
[24]O. Higgott, M. Wilson, J. Hefford, J. Dborin, F. Hanif, S. Burton and D. E. Browne, Optimal local unitary encoding circuits for the surface code, Quantum 5, 517 (2021)
[25]D. Horsman, A. G. Fowler, S. Devitt and R. Van Meter, Surface code quantum computing by lattice surgery, New J. Phys. 14 (2012) 123011
[26]S. Huang, T. Jochym-O'Connor, T. J. Yoder, Homomorphic Logical Measurements, arXiv:2211.03625 [quant-ph]
[27]G. Hahn and G. Sabidussi, Graph symmetry: algebraic methods and applications, NATO Advanced Science Institutes Series, vol. 497, Springer, p. 116 (1997) ISBN 978-0-7923-4668-5
[28]A. Kissinger, Phase-free ZX diagrams are CSS codes (...or how to graphically grok the surface code), In Proceedings QPL 2022, arXiv:2204.14038 [quant-ph]
[29]A. Kissinger, A. Meijer-van de Griend, CNOT circuit extraction for topologically-constrained quantum memories, Quantum Information and Computation, 20, 7& 8, (2020)
[30]A. Kitaev, Fault-tolerant quantum computation by anyons, Ann. Phys.  303 (2003) 3–20
[31]Al. Krishna and David Poulin, Fault-tolerant gates on hypergraph product codes, Phys. Rev. X 11, 011023 (2021)
[32]T. Leinster, Basic Category Theory, Cambridge Studies in Advanced Mathematics, Vol. 143, Cambridge University Press, 2014
[33]A. J. Landahl and C. Ryan-Anderson, Quantum computing by color-code lattice surgery, arXiv:1407.5103 [quant-ph]
[34]Math stackexchange, https://math.stackexchange.com/questions/1046209/pullbacks-and-pushouts-in-the-category-of-graphs, accessed 25/10/22
[35]C. Meusburger, Kitaev lattice models as a Hopf algebra gauge theory, Commun. Math. Phys. 353 (2017) 413–468
[36]K. P. Michnicki, 3D Topological Quantum Memory with a Power-Law Energy Barrier, Phys. Rev. Lett. 113, 130501
[37]H. P. Nautrup, N. Friis and H. J. Briegel, Fault-tolerant interface between quantum memories and quantum processors, Nat. Commun. 8, 1321 (2017)
[38]P. Panteleev and G. Kalachev, Asymptotically Good Quantum and Locally Testable Classical LDPC Codes, STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
[39]A. O. Quintavalle, P. Webster and M. Vasmer, Partitioning qubits in hypergraph product codes to implement logical gates, arXiv:2204.10812 [quant-ph]
[40]J. van de Wetering, ZX-calculus for the working quantum computer scientist, arXiv:2012.13966 [quant-ph]
[41]C. Vuillot, L. Lao, B. Criger, C. G. Almudéver, K. Bertels and B. M. Terhal, Code deformation and lattice surgery are gauge fixing, New J. Phys. 21 033028 (2019)
[42]C. A. Weibel, An Introduction to Homological Algebra (Cambridge Studies in Advanced Mathematics), Cambridge University Press, doi:10.1017/CBO9781139644136 (1994)

§ LIMITS AND COLIMITS IN $\CHAINS$

$\Chains$ has all kernels and cokernels.

Recall that $\MatF$ has all kernels and cokernels, i.e. subspaces and quotient spaces. Then given a chain map $f : C_\bullet \rightarrow D_\bullet$ we define ${\rm ker}(f)$ with

\[\begin{tikzcd}
\cdots \arrow[r, dotted] & K_{n+1} \arrow[r, dotted, "\del^{K_\bullet}_n"] \arrow[d, "{\rm ker}(f_{n+1})"'] & K_n \arrow[d, "{\rm ker}(f_n)"] \arrow[r, dotted]& \cdots\\
\cdots \arrow[r]& C_{n+1} \arrow[r, "\del^{C_\bullet}_n"] \arrow[d, "f_{n+1}"'] & C_n \arrow[d, "f_n"] \arrow[r]& \cdots\\
\cdots \arrow[r]& D_{n+1} \arrow[r, "\del^{D_\bullet}_n"] & D_n \arrow[r]& \cdots
\end{tikzcd}\]

where $\del^{K_\bullet}_n$ always exists and is uniquely defined, because

\[f_n\circ \del^{C_\bullet}_n\circ {\rm ker}(f_{n+1}) = \del^{D_\bullet}_n\circ f_{n+1}\circ {\rm ker}(f_{n+1}) = 0\]

and so by the universal property of ${\rm ker}(f_{n})$ there is a unique matrix $\del^{K_\bullet}_n: K_{n+1}\rightarrow K_n$.  These satisfy $\del^{K_\bullet}_n\circ\del^{K_\bullet}_{n+1} = 0$ as

\[{\rm ker}(f_n)\circ\del^{K_\bullet}_n\circ\del^{K_\bullet}_{n+1}=\del^{C_\bullet}_n\circ\del^{C_\bullet}_{n+1}\circ {\rm ker}(f_{n+2})=0\]

and then kernels are monic. $K_n = \{v \in C_n\ |\ f_n(v)=0\}$ by the definition of kernels in $\MatF$. Given the correct choice of basis, $\del^{K_\bullet}_n$ is thus just $\del^{C_\bullet}_n\circ {\rm ker}(f_{n+1})$ as a matrix but without the all-zero rows which map into $C_n/K_n$.

That ${\rm ker}(f)$ is a genuine kernel in $\Chains$ is straightforward to check but we do not give further details.

The reversed argument applies for cokernels, giving quotient complexes $D_\bullet/{\rm im}(f)$ with components $D_n/{\rm im}(f_n)$ etc.

As $\Chains$ is additive, equalisers and coequalisers can be seen as special cases of kernels and cokernels by defining ${\rm eq}(f,g) = {\rm ker}(f-g)$ and ${\rm coeq}(f,g) = {\rm coker}(f-g)$, for $f,g : C_\bullet \rightarrow D_\bullet$. For the chain complex part $E_\bullet$ of an equaliser we have components $E_n = \{c\ |\ f(c)=g(c)\}\subseteq C_n$. For the chain complex part $F_\bullet$ of a coequaliser, we have components $F_n = D_n/f(c)\sim g(c)$, for $c\in C_n$.

We now sketch a proof of Lemma <ref>.
Recall that an Abelian category is an additive category such that:

* Every morphism has a kernel and cokernel.

* Every monomorphism is the kernel of its cokernel.

* Every epimorphism is the cokernel of its kernel.

The first is just Lemma <ref>, and the other two follow using the fact that they hold degree-wise in $\MatF$.

We will now spell out pullbacks. While they can be defined using equalisers and products we construct them explicitly, as it is easy to do so.

The pullback of chain maps $f: X_\bullet \rightarrow Z_\bullet$ and $g:Y_\bullet \rightarrow Z_\bullet$ gives the chain complex $W_\bullet$, where each component is the pullback $W_n$ of $f_n$ and $g_n$. The differentials $\del^{W_\bullet}_n$ are given by the unique map from each component's pullback. Specifically, if we have the pullback

\[\begin{tikzcd}
W_\bullet \arrow[r, "w"]\arrow[d, "v"']\arrow[dr, phantom, "\usebox\pullback", very near start] & Y_\bullet \arrow[d,"g"]\\
X_\bullet \arrow[r,"f"'] & Z_\bullet
\end{tikzcd}\]

then for degrees $n, n+1$ we have

\[\begin{tikzcd}
W_n\arrow[rrr,"w_n"]\arrow[ddd,"v_n"'] & & & Y_n\arrow[ddd, "g_n"]\\
& W_{n+1}\arrow[ul, dotted, "\del^{W_\bullet}_n"]\arrow[r, "w_{n+1}"]\arrow[d, "v_{n+1}"']\arrow[dr, phantom, "\usebox\pullback", very near start] & Y_{n+1}\arrow[ur, "\del^{Y_\bullet}_n"]\arrow[d, "g_{n+1}"] &\\
& X_{n+1}\arrow[dl,"\del^{X_\bullet}_n"]\arrow[r,"f_{n+1}"'] & Z_{n+1}\arrow[dr, "\del^{Z_\bullet}_n"] &\\
X_n\arrow[rrr, "f_n"'] & & & Z_n
\end{tikzcd}\]

\[W_n = \{(x,y)\ |\ f_n(x) = g_n(y)\} \subseteq X_n\oplus Y_n; \quad v_n(x,y)=x \in X_n;\quad w_n(x,y)=y\in Y_n.\]

As $f_n\circ \del^{X_\bullet}_n\circ v_{n+1} = g_n\circ \del^{Y_\bullet}_n\circ w_{n+1}$ and the outer square is a pullback, there is a unique matrix $\del^{W_\bullet}_n$. One can check by diagram chasing that the differentials $\del^{W_\bullet}_n\circ \del^{W_\bullet}_{n+1} = 0$, and then that this is indeed a pullback in $\Chains$.

§ TENSOR STRUCTURE OF $\CHAINS$

Let $C_\bullet,D_\bullet$ be chain complexes in $\Chains$. Define $(C\tens D)_{\bullet}$ with components

\[(C\tens D)_n = \bigoplus_{i+j=n}C_i \tens D_j \]

where the latter tensor product is the normal tensor product in $\MatF$. Differentials between components are given by

\[\del^{(C\tens D)_\bullet}_{n} = \line(1,0){10} {}_{i+j=n}\begin{pmatrix}\id_{C_i} \tens \del^{D_\bullet}_j | \del^{C_\bullet}_i \tens \id_{D_j}\end{pmatrix}\]

where the horizontal line $\line(1,0){10}$ indicates that all these matrices are stacked vertically, which we illustrate in an example below. One can check that $\del^{(C\tens D)_\bullet}_{n}\circ\del^{(C\tens D)_\bullet}_{n+1}=0 \pmod 2$, as desired.

Also define the object $\mathbf{1}_\bullet \in \Chains$ as

\[\begin{tikzcd}
\mathbf{1}_\bullet = \cdots\arrow[r]& 0 \arrow[r]& \mathbf{1}_0 \arrow[r]& 0 \arrow[r]& \cdots
\end{tikzcd}\]

where $\mathbf{1}_0 = \F_2$, and all other $\mathbf{1}_i$ are $0$.

One can check that $(C\tens D)_{\bullet}$ is a $\F_2$-linear monoidal product $\tens$ in $\Chains$, which follows from associativity and distributivity of $\oplus$ and $\tens$ in $\MatF$. For the unit, observe that

\[(C\tens \mathbf{1})_n = C_n \tens 1 = C_n;\quad \del^{(C\tens \mathbf{1})_\bullet}_n = \begin{pmatrix}\id_{C_n} \tens \del^{\mathbf{1}_\bullet}_0 | \del^{C_\bullet}_n \tens \id_{\mathbf{1}_0}\end{pmatrix} = \del^{C_\bullet}_n.\]

Consider two chain complexes of length 1:

\[\begin{tikzcd}C_\bullet = \cdots\arrow[r]& 0\arrow[r]& C_1 \arrow[r, "\del^{C_\bullet}_0"]& C_0\arrow[r]& 0 \arrow[r]& \cdots\end{tikzcd}\]

\[\begin{tikzcd}D_\bullet = \cdots\arrow[r]& 0\arrow[r]& D_1 \arrow[r, "\del^{D_\bullet}_0"]& D_0\arrow[r]& 0 \arrow[r]& \cdots\end{tikzcd}\]

In this case we have

\[(C\tens D)_0 = C_0\tens D_0;\quad (C\tens D)_1 = (C_1\tens D_0)\oplus(C_0\tens D_1); \quad (C\tens D)_2 = C_1\tens D_1\]

for nonzero components, and

\[\del^{(C\tens D)_\bullet}_0 = (\id_{C_0} \tens \del^{D_\bullet}_0|\del^{C_\bullet}_0\tens \id_{D_0});\quad
\del^{(C\tens D)_\bullet}_1 = \begin{pmatrix}\underline{\del^{C_\bullet}_0\tens \id_{D_1}}\\ \id_{C_1} \tens \del^{D_\bullet}_0\end{pmatrix}\]

for nonzero differentials. Then

\[\del^{(C\tens D)_\bullet}_0\circ \del^{(C\tens D)_\bullet}_1 = \del^{C_\bullet}_0\tens \del^{D_\bullet}_0 + \del^{C_\bullet}_0\tens \del^{D_\bullet}_0 = 0 \pmod 2\]

as the matrix partitions factor upon multiplication.

This example illustrates an interesting property of $\tens$ in $\Chains$: both $C_\bullet, D_\bullet$ have only one nonzero differential, but $(C\tens D)_\bullet$ has two. It is easy to see that given two complexes of lengths $s,t$ the tensor product will have length $s+t$.

[42]

\[H_n((C\tens D)_\bullet) \cong \bigoplus_{i+j=n} H_i(C_\bullet)\tens H_j(D_\bullet)\]

That is, the homology subspaces factor through the tensor product conveniently. This is also called the Künneth formula. The manner in which the homology factors through does not make $H_n(-)$ a monoidal functor with respect to the tensor product.

The tensor product is used to build codes from other CSS codes [2].

§ GRAPHS AND CELL COMPLEXES

In this appendix we give some categorical background on abstract cell complexes. This is not necessary to define CSS code surgery, but codes obtained from cell complexes are an important motivating example, as they include surface codes, toric codes [30], hyperbolic codes [9] and the balanced product codes from [38]. In general, if a CSS code comes from tessellating a manifold, it is likely to use cell complexes. Cell complexes are important in the study of topological spaces, and many of the constructions of CSS codes, such as balanced/lifted products, can also be phrased in the language of topology, but we stick to cell complexes for brevity. As a warm-up, we describe certain categories of graphs, and then move on to a specific kind of cell complex.

Let $\Gamma$ be a finite simple undirected graph. Recall that as a simple graph, $\Gamma$ has at most one edge between any two vertices and no self-loops on vertices. $\Gamma$ can be defined as a pair of sets, $V(\Gamma)$ and $E(\Gamma)$, with $E(\Gamma) \subseteq 2^{V(\Gamma)}$, the powerset of vertices, where each $e \in E(\Gamma)$ has 2 elements i.e. it can be expressed as $e = \{v_1, v_2\}$. An example of a graph is $\CC_n$, the cycle graph with $n$ vertices and edges. We will also use $\CP_n$, the path graph with $n$ edges and $n+1$ vertices.

Let $\Grph$ be the category of finite simple undirected graphs. A morphism $\Gamma \rightarrow \Delta$ in $\Grph$ is a function $f : V(\Gamma)\rightarrow V(\Delta)$ such that $\{v_1, v_2\} \in E(\Gamma) \implies \{f(v_1), f(v_2)\} \in E(\Delta)$, i.e. the function respects the incidence of edges.

$\Grph$ has several different products and other categorical features. We are particularly interested in colimits. $\Grph$ has a coproduct $\Gamma + \Delta$ being the disjoint union, with $V(\Gamma + \Delta) = V(\Gamma) \sqcup V(\Delta)$ and $E(\Gamma + \Delta) = E(\Gamma) \sqcup E(\Delta)$. It also has an initial object $I$ given by the empty graph. However, $\Grph$ is not cocomplete, as it does not have all pushouts.

As a counterexample [34], given the diagram

\[\tikzfig{pushout_counterexample}\]

no cocone exists, as the graphs are not allowed self-loops. Therefore, no pushout exists.

One can easily see that there are diagrams for which pushouts do exist, though.

More than just graphs, we would like to allow for open graphs, i.e. graphs which may have edges which connect to only one vertex, but are not self-loops. For example,

\[\tikzfig{open_graph_eg2}\]

We call $\CG_3$ the 3rd open path graph, where the $n$th open path graph $\CG_n$ has $n$ edges in a line with $n-1$ vertices between them. We now give a particular formalisation of open graphs.

Let $\Gamma$ be a finite simple undirected graph with two disjoint vertex sets $V(\Gamma)$ and $B(\Gamma)$, where $E(\Gamma) \subseteq 2^{V(\Gamma)\cup B(\Gamma)}$. We then say that $\Gamma$ is an open graph. We call $V(\Gamma)$ the internal vertices and $B(\Gamma)$ the boundary vertices.

So in the picture of $\CG_3$ above there are vertices at either end of the open wires, but they are considered `invisible', i.e. they belong to $B(\Gamma)$.

Let $\OGrph$ be the category of open graphs. A morphism $\Gamma \rightarrow \Delta$ in $\OGrph$ is a function $f: V(\Gamma)\cup B(\Gamma) \rightarrow V(\Delta)\cup B(\Delta)$ such that $\{v_1, v_2\} \in E(\Gamma) \implies \{f(v_1), f(v_2)\} \in E(\Delta)$ and $f(x) \in V(\Delta) \iff x \in V(\Gamma)$.

This restriction disallows internal vertices from being `created' or `deleted' by a graph morphism by converting them to boundary vertices. $\OGrph$ has very similar properties to $\Grph$. Its initial object is the empty open graph. $\OGrph$ has a coproduct, where $V(\Gamma + \Delta) = V(\Gamma)\sqcup V(\Delta)$ and $B(\Gamma + \Delta) = B(\Gamma)\sqcup B(\Delta)$. Like $\Grph$, $\OGrph$ is not cocomplete, as Example <ref> also works in the setting of open graphs. It is obvious that $\Grph$ is a subcategory of $\OGrph$.

We now move on to cell complexes, in particular abstract cubical complexes. These are abstract cell complexes which are `square', unlike their `triangular' relatives simplicial complexes.

The abstract $d$-cube is the set $\{0,1\}^d$, with the $0$-cube $\{0,1\}^0 := \{0\}$. A face of the abstract $d$-cube is a product $A_1\times\cdots \times A_d$, where each $A_i$ is a nonempty subset of $\{0,1\}$.

Let $S$ be a finite set and let $\Omega$ be a collection of nonempty subsets of $S$ such that:

* $\Omega$ covers $S$.

* For $X, Y \in \Omega$, $X \cap Y \in \Omega$ or $X \cap Y = \emptyset$.

* For each $X \in \Omega$, there is a bijection from $X$ to the abstract $d$-cube for some choice of $d$, such that any $Y \subset X$ is in $\Omega$ iff it is mapped to a face of the $d$-cube.

Then $\Omega$ is an abstract cubical complex.

Abstract cubical complexes are combinatorial versions of cubical complexes, meaning they are stripped of their associated geometry. The elements in $\Omega$ are still called faces. We can consider $\Omega$ to be a graded poset, with subset inclusion as the partial order, and the grading $\dim (X) =  \log_2|X|$. We also call this grading the dimension $d$ of $X$, and we call $X$ a $d$-face. The set of $d$-faces in $\Omega$ is called $\Omega_d$. There is a relation $\Omega_d \rightarrow \Omega_{d-1}$ taking a $d$-face to its $(d-1)$-face subsets.

We call the vertex set $V(\Omega) = S = \Omega_0$, and also define the dimension of a cubical complex

\[\dim (\Omega) = \max_{X \in \Omega} \dim (X)\]

The $d$-skeleton of $\Omega$ is the maximal subcomplex $\Upsilon \subseteq \Omega$ such that $\dim (\Upsilon) = d$. The $1$-skeleton of an abstract cubical complex is a finite simple undirected graph. The $2$-skeleton of an abstract cubical complex is `like' a square lattice, in that it has $2$-faces which each have 4 $0$-faces as subsets and 4 $1$-faces.

Let $\ACC$ be the category of abstract cubical complexes. A morphism $f : \Omega \rightarrow \Upsilon$ in $\ACC$ is a function $f: V(\Omega) \rightarrow V(\Upsilon)$, such that $\{x,\cdots,y\}\in \Omega_d \implies \{f(x),\cdots,f(y)\}\in \Upsilon_d$, i.e. incidence is preserved at each dimension.

Similar to $\Grph$, $\ACC$ has coproduct given by $(\Omega + \Upsilon)_i = \Omega_i \sqcup \Upsilon_i$ and an initial object $I = \emptyset$, and does not generally have pushouts, where we can reuse the same counterexample as $\Grph$. Another categorical property we highlight here is that $\ACC$ has a monoidal product called the box product.

Let $\Upsilon\ \Box\ \Omega$ be the box product of abstract cubical complexes. Then

\[(\Upsilon\ \Box\ \Omega)_n = \sum_{i+j=n} \Upsilon_i \times \Omega_j.\]

We now check that $\Upsilon\ \Box\ \Omega$ is indeed an abstract cubical complex.
First, it has a vertex set $V(\Upsilon\ \Box\ \Omega) = V(\Upsilon)\times V(\Omega)$, and thus trivially covers $\Upsilon_0\times \Omega_0$. Second, let $X \times Y \in \Upsilon_i\times \Omega_j$ and $T\times U \in \Upsilon_k\times\Omega_l$. This has
$(X\times Y)\cap (T\times U) = (X\cap T)\times (Y\cap U)$ which is either in $\Upsilon_m \times \Omega_n$ for some $m \leq i, m\leq k$ and $n\leq j, n\leq l$, and thus $(X\cap T)\times (Y\cap U) \in \Upsilon\ \Box\ \Omega$, or $(X\cap T)\times (Y\cap U) = \emptyset$. Third, if $X$ and $Y$ each have a bijection to an $i$-cube and $j$-cube respectively, then $X\times Y$ has a bijection to an $(i+j)$-cube. Any $W \subset X\times Y$ can be expressed as $T\times U$, for $T \subset X$ and $U\subset Y$. Then $W$ is in $\Omega\ \Box\ \Upsilon$ iff $T$ is mapped to a face of the $i$-cube and $U$ to a face of the $j$-cube, thus $W$ to a face of the $(i+j)$-cube.

Let us compile this into a more digestible form for the case when $\Upsilon$ and $\Omega$ are both graphs. Given vertices $(u,u')$ and $(v,v')$ in $V(\Upsilon\ \Box\ \Omega)$, the 1-face $\{(u,u'),(v,v')\}\in(\Upsilon\ \Box\ \Omega)_1$ iff $(u = v\ \&\ (u',v')\in \Omega)$ or $((u,v)\in \Upsilon\ \&\ u'=v')$. Then $(\Upsilon\ \Box\ \Omega)_2 \cong E(\Upsilon)\times E(\Omega)$. The 1-skeleton of $\Upsilon\ \Box\ \Omega$ is just the normal box product of graphs [27].

Let $\CC_m$ and $\CC_n$ be cycle graphs with $m$ and $n$ vertices respectively, considered as abstract cubical complexes. Then $\CT = \CC_m\ \Box\ \CC_n$ admits an embedding as a square lattice on the torus, and has $\dim(\CC_m\ \Box\ \CC_n) = 2$. Setting $m = n =3$ we have

\[\tikzfig{box_product_cycles}\]

where the grey dots indicate periodic boundary conditions and the white circles specify 2-faces. This example comes up in the form of the toric code in Section <ref>.

Obviously, $\Grph$ is a subcategory of $\ACC$.

We are also interested in open abstract cubical complexes.

Let $\Upsilon$ be an open abstract cubical complex. $\Upsilon$ is an abstract cubical complex where $\Upsilon_0$ is divided into two disjoint vertex sets $V(\Upsilon)$ and $B(\Upsilon)$.

The 1-skeleton of an open abstract cubical complex is an open graph.

Let $\OACC$ be the category of open abstract cubical complexes. A morphism $f: \Omega \rightarrow \Upsilon$ in $\OACC$ is a function $f: V(\Omega)\cup B(\Omega) \rightarrow V(\Upsilon)\cup B(\Upsilon)$ such that $f(x) \in V(\Upsilon) \iff x \in V(\Omega)$ and $\{x,\cdots,y\}\in \Omega_d \implies \{f(x),\cdots,f(y)\}\in \Upsilon_d$.

As in our previous examples, $\OACC$ has the obvious coproduct and initial object, and does not have pushouts in general.

Let $\Upsilon$ be a `patch', a square lattice with two rough and two smooth boundaries:

\[\tikzfig{box_product_paths}\]

This patch has 6 2-faces, 13 1-faces and 6 0-faces.

We can perform the pushout of two smaller open abstract cubical complexes to acquire a patch:

\[\tikzfig{small_pushout}\]

where the apex is $\CP_1$, the blue edge indicates where the apex is mapped to, and the bottom right open abstract cubical complex is the object of the pushout.

Let $\CG_3$ be the open path graph, and let $\Omega$ be a patch. Then we have a pushout

\[\tikzfig{pushout_cubicals}\]

This example comes up in the context of lattice surgery on surface codes.
Evidently, both $\OGrph$ and $\ACC$ are subcategories of $\OACC$, and one can define a box product for $\OACC$ in the same way as we did for $\ACC$ in Definition <ref>.

One can define quantum codes using abstract cell complexes more generally, but abstract cubical complexes are the specific type which we make use of in examples in Section <ref> and onwards. We now relate the above cell complexes to chain complexes by way of functors.

Given an abstract cubical complex $\Omega$ we can define the incidence chain complex $C_\bullet$ in $\Chains$, where each nonzero component has a basis $\tilde{C}_{n-1}=\Omega_n$, say, and each nonzero differential $\del^{C_\bullet}_{n-1}$ takes an $n+1$-face to its $n$-dimensional subsets. [We choose to send $n$-faces to $(n-1)$-components, rather than $n$-components.] The differential is thus a matrix with a 1 where an $n$-face is contained within an $(n+1)$-face, and 0 elsewhere. It is an elementary fact that every $(d-2)$-face in a $d$-face is the intersection of exactly 2 $(d-1)$-faces, thus $\del^{C_\bullet}_{n-1}\circ\del^{C_\bullet}_{n} = 0 \mod 2$. Clearly, the incidence chain complex of a dimension 1 abstract cubical complex is just the incidence matrix of a simple undirected graph.

We can do essentially the same thing given an open abstract cubical complex $\Upsilon$. In this case, each nonzero component has a basis $\tilde{C}_{n-1} = \{X \in \Omega_n\ |\ X \not\subseteq B(\Omega)\}$, that is we ignore all faces which are made up only of boundary vertices, and differentials are the same matrices as above, with a 1 where an $n$-face which is not a subset of $B(\Omega)$ (and therefore would be `invisible') is contained in an $(n+1)$-face. It is easy to see that we still have $\del^{C_\bullet}_{n-1}\circ\del^{C_\bullet}_{n} = 0 \mod 2$, as making vertices `invisible' corresponds to deleting rows in $\del^{C_\bullet}_{-1}$, edges rows in $\del^{C_\bullet}_0$ etc. The incidence chain complex of a dimension 1 open abstract cubical complex is the incidence matrix of an open graph.

Let $C_\bullet$ and $D_\bullet$ be the incidence chain complexes of two abstract cubical complexes $\Omega$ and $\Upsilon$ with a morphism $f: \Omega \rightarrow \Upsilon$, and set $\tilde{C}_{-1}, \tilde{D}_{-1}$ as $V(\Omega), V(\Upsilon)$ respectively. This induces a chain map $g_\bullet : C_\bullet \rightarrow D_\bullet$, with the matrix $g_{-1}$ given by $f$, and all matrices on higher components generated inductively. Degrees $i < -1$ are assumed to be zero.

As a consequence, we can define a functor $\varphi:\ACC\rightarrow \Chains$, sending each abstract cell complex to its free chain complex as described in Definition <ref>. One can check that $\varphi(f) \in \Hom(\varphi(\Omega), \varphi(\Upsilon))$ for any morphism $f : \Omega \rightarrow \Upsilon$ between abstract cubical complexes. $\varphi$ is faithful but not full, as there exist morphisms, such as the zero morphism, which are not in the image of $\varphi$.

There is also a functor $\vartheta: \OACC \rightarrow \Chains$. On objects, this again follows Definition <ref>. On morphisms this is the same as $\varphi$ except it must obviously ignore maps between boundary vertices everywhere. Thus $\vartheta$ is not faithful.

Let $\Omega$ and $\Upsilon$ be two abstract cubical complexes. Then $\varphi(\Omega + \Upsilon) = \varphi(\Omega)\oplus \varphi(\Upsilon)$, which is easy to check. Similarly, $\varphi(\emptyset) = \mathbf{0}_\bullet$. The same is true of $\vartheta$, except that $\vartheta(\Xi) = \mathbf{0}_\bullet$ for any $\Xi$ with $V(\Xi) = \emptyset$.

The functors $\varphi$ and $\vartheta$ are cocontinuous i.e. they preserve colimits.

We give a proof sketch here. We know already that $\varphi$ preserves coproducts so it is sufficient to check that it preserves pushouts. Let

\[\begin{tikzcd}
\Xi \arrow[r, "g"]\arrow[d, "f"'] & \Upsilon \arrow[d,"l"]\\
\Omega \arrow[r,"k"'] & \chi\arrow[ul, phantom, "\usebox\pushout", very near start]
\end{tikzcd}\]