Towards surgery with good quantum LDPC codes

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

We show that the good quantum LDPC codes of Panteleev-Kalachev [24] allow for surgery using any logical qubits, albeit incurring an asymptotic penalty which lowers the rate and distance scaling. We also prove that we can satisfy 3 of the 4 conditions for performing surgery without incurring an asymptotic penalty. If the last condition is also satisfied then we can perform code surgery while maintaining $k, d\in \Theta(n)$.

§ INTRODUCTION

Quantum Low-Density Parity Check (qLDPC) codes are of interest for low-overhead fault-tolerant quantum computation [4]. They typically require more complicated connectivity of qubits compared to the 2D layouts required for most topological codes, such as surface codes [11, 18]. It was recently proved that good qLDPC codes exist - that is, families of qLDPC codes which have the optimal asymptotic scaling of $k, d\in \Theta(n)$ [24, 22, 10]. The proofs rely on expansion properties of graphs or complexes, and due to their complexity the codes are complicated to reason about. The codes also require generating random classical codes, which satisfy the required conditions only probabilistically.

It is an open question how best to perform logical operations with qLDPC codes. A general protocol described by Gottesman [12] requires constant but large overhead to distill complicated states and perform gate teleportation. Several more recent works have investigated performing Clifford gates [19, 6], measurements [15] and entangling gates [27] with different kinds of qLDPC codes, with the allowed gates depending on the specifics of the codes. Importantly, we would like methods of computation which do not add significant resources on top of the error-protected quantum memory holding data.

An efficient method of performing logical operations with surface and other topological codes is lattice surgery [13, 11, 7, 23]. Given this method's success for topological codes, it might be expected to generalise to other qLDPC codes which are not inherently topological, particularly those which are also Calderbank-Shor-Steane (CSS) codes, and hence are homological in a suitable sense. There have been two descriptions of such a generalisation, which are similar but not identical.

(1) Cohen et al. [8] used Tanner graphs to give a prescription for performing surgery with the logical primitives being measurements of Pauli tensor products, as a generalisation of the method of lattice surgery in e.g. [20]. One initialises a `large' distance $d$ ancillary code connected to all codeblocks in the support of a Pauli product measurement, and measures all stabilisers for $d$ measurement rounds, before measuring out the ancilla code. This is a flexible procedure, as it can measure arbitrary Pauli tensor products. It has concrete benefits over performing surgery with surface codes at finite block length, but it is not asymptotically superior, as the ancillary code has vanishing rate and $d \in \Theta(\sqrt{n})$, the same as surface codes. This procedure has featured in recent end-to-end error correction protocols for superconductors and neutral atom arrays [2, 30]. In the latter we see the limitations of this technique for quantum expander codes [21], as it requires there to be only $o(\sqrt{k})$ logical qubits being used in any Pauli product measurements at a given timestep to retain the constant space overhead. We call this method `Type 1 surgery'.

(2) More recently, we gave a prescription for surgery as a categorical construction using homological algebra [9]. It is closer to the original description of lattice surgery, with primitives being parity measurements and splits. This protocol is abstract and requires a few subtle conditions, but in principle does not preclude performing surgery with CSS codes with any rate or distance scaling. In particular, for merges it requires only a `small' distance 2 ancillary code, which does not influence the asymptotic scaling of the protocol.[It may also have concrete benefits for near-term small fault-tolerant devices, but we do not tackle this problem here.] We call this `Type 2 surgery'. The subtle conditions make determining when we can do Type 2 surgery hard in general, as it is related to how systolic geometry [17] interacts with connected sums.

There are 4 conditions required for a Type 2 merge:

* The logical operators to participate in the merge must be matching.

* Each participating logical operator must satisfy the separation property.

* Each participating logical operator must be gauge-fixable.

* The merge must have distance bounded below.

while Type 1 surgery only requires condition (2).

§.§ Contributions

We first give an overview of Type 1 and Type 2 surgery in Section <ref>, and of balanced products in Section <ref>.
In Section <ref> we prove that balanced products of classical codes always have a choice of logical qubits such that there is a representative $\overline{Z}$ and $\overline{X}$ which is separated, for every logical qubit. This implies that Panteleev-Kalachev's good qLDPC codes [24], which are balanced products, admit Type 1 surgery between any logical qubits, as condition (2) is satisfied.
However, because Type 1 surgery requires an ancilla codeblock which scales in qubit count $n_a$ as $n_a \in \Theta(d^2)$, where $d$ is the code distance of the main codeblock, this does not allow for surgery while keeping $k, d\in \Theta(n)$.

We then move to Type 2 surgery in Section <ref>. We prove in Section <ref> that conditions (2) and (3) always coincide exactly, and therefore (3) is satisfed by good qLDPC codes. Condition (1) is trivially satisfied if we only perform pairwise merges between identical codeblocks, where a merge can be performed between two logical qubits with the same index. This is a restrictive computational model but we stick to it for simplicity.

The last remaining obstacle to performing code surgery while keeping $k, d \in \Theta(n)$ is therefore condition (4). We do not know how to prove or disprove that this condition holds, but give a description of one approach in Section <ref>.

§ OVERVIEW OF CODE SURGERY

Here we recap Type 1 and Type 2 surgery. Below we give a table summarising the distinction between the two types of surgery.

Surgery     Formalism     Conditions     Generalises     Ancilla patch scaling
Type 1     Tanner graphs     (2)     Pauli product measurements     $n \in \Theta(d^2)$

Type 2     Chain complexes     (1)-(4)     Merges & splits     $n \in \Theta(d)$

§.§ Type 1 surgery

On logical qubits, Type 1 surgery performs a non-destructive Pauli product measurement [8], e.g. a measurement of the operator $\overline{X} \otimes \overline{Y} \otimes \overline{Z}$. Given a quantum memory codeblock with parameters $\llbracket n, k, d\rrbracket$, Type 1 surgery performs a measurement of a Pauli tensor product in $d$ rounds of stabiliser measurements.

The construction of the ancilla patches works by first identifying logical operators which are separated, that is they do not contain any other logical operators in their support. For each of those logical operators we construct a hypergraph product code [26] with distance $d$ and `glue' it onto that operator; these hypergraph product codes are also glued together, to form a single ancilla patch which measures the tensor product of the logical operators. By construction, the procedure preserves the code distance of the quantum memory, and hence can be flexibly applied to a wide variety of codes.

For brevity we do not explain the full Tanner graph formalism for the procedure, but in the case of surface codes Type 1 surgery reduces to the following operation [20]:

\[\tikzfig{ppm_lattice}\]

where patches 1, 2 & 3 have their $\overline{X}$, $\overline{Y}$ & $\overline{Z}$ operators measured by the ancilla code above. Dashed lines denote rough boundaries and non-dashed lines smooth boundaries.

The procedure is limited by the fact that the ancilla hypergraph product codes have vanishing encoding rate and code distance $d_a \in \Theta(\sqrt{n_a})$. As $d_a = d$, we require a number of physical qubits quadratic in the code distance; the number of hypergraph product codes used also scales linearly with the number of logical Pauli terms in the tensor product being measured. This means that, while the procedure yields advantages at finite size over surface codes, it does not give improved asymptotics.

§.§ Type 2 surgery

Type 2 surgery performs merges and splits. We use ZX-diagrams [16] to describe the logical operations, as the notation is succinct and easy to reason with. On logical qubits we have ZX-diagrams of the form [5]:

\[\tikzfig{merge1}\quad ;\quad \tikzfig{merge2}\quad ;\quad \tikzfig{split1}\quad ;\quad \tikzfig{split2}\]

Where $a \in \{0, 1\}$ depends on the measurement outcome. That is, on the left we have measurements of the $\overline{Z}\otimes\overline{Z}$ and $\overline{X}\otimes \overline{X}$ operators, which are merges. On the right we have their adjoint isometries, which are splits. Given a quantum memory codeblock with parameters $\llbracket n, k, d\rrbracket$, Type 2 surgery performs one of these operations in $d$ rounds of stabiliser measurements; they can in principle be parallelised.

For merges we first identify two logical operators which are matching, and construct a low distance ancilla tensor product code which glues the two operators together. For splits we do the opposite, measuring out the ancilla qubits in the low distance product code. In the case of surface codes Type 2 surgery reduces to

\[\tikzfig{merge_lattice} \]

for a $\overline{Z}\otimes\overline{Z}$ merge.

Type 2 surgery trades off the flexibility and guarantees of Type 1 for asymptotic scaling which is not, in principle, limited to $d \in \Theta(\sqrt{n})$, and hence could be used for surgery between codes with much better asymptotics.

We elaborate on the procedure and the conditions later on in Section <ref>.

§ PRODUCT CODES

Throughout we assume familiarity with the CSS code-homology correspondence [4]. A (qubit) CSS code is a length-2 chain complex over $\F_2$:

\[\begin{tikzcd}S_\bullet = S_{2}\arrow[r, "\del_1"]& S_1\arrow[r, "\del_{0}"]& S_{0}\end{tikzcd}\]

where we choose the convention that $\del_1 = P_Z^\intercal$ and $\del_{0} = P_X$, with $P_Z$ and $P_X$ the parity check matrices for $Z$ and $X$ stabilisers respectively.

\[k = \dim(H_1(S_\bullet)) = \dim(\ker(P_X)/\im(P_Z^\intercal)) = \dim(\ker(P_Z)/\im(P_X^\intercal)),\]

where $H_1(S_\bullet):=\ker(P_X)/\im(P_Z^\intercal)$ is the first homology space of $S_\bullet$, and is isomorphic to $H^1(S_\bullet) :=\ker(P_Z)/\im(P_X^\intercal)$, the first cohomology space. The fact that $\ker(P_X)/\im(P_Z^\intercal) \cong \ker(P_Z)/\im(P_X^\intercal)$ means that there is a non-degenerate bilinear form:

\[\cdot : \ker(P_X)/\im(P_Z^\intercal) \times \ker(P_Z)/\im(P_X^\intercal) \rightarrow \F_2;\quad [u]\cdot [v] = u^\intercal v, u\in [u], v\in [v]\]

which entails a pairing of bases of the two spaces, i.e. $[u]_i\cdot [v]_j = \delta_{i,j}$, for any $[u]_i$ and $[v]_j$ basis elements of $\ker(P_X)/\im(P_Z^\intercal)$ and $\ker(P_Z)/\im(P_X^\intercal)$ respectively. Considering a basis of $H_1(S_\bullet)$ to be a choice of tensor product decomposition of the logical space into logical qubits, this form asserts that $\overline{Z}_i\overline{X}_j = (-1)^{\delta_{i,j}}\overline{X}_j\overline{Z}_i$, i.e. logical $X$ and $Z$ operators commute iff they are on different logical qubits.

§.§ Tensor products

Here we recap tensor products [1] of classical codes from the perspective of homological algebra. Let $C_\bullet$ and $D_\bullet$ be two linear binary codes

\[\begin{tikzcd}C_\bullet = C_1 \arrow[r, "A"] & C_0\end{tikzcd};\quad \begin{tikzcd} D_\bullet = D_1 \arrow[r, "B"] & D_0\end{tikzcd}\]

where $A$ and $B$ are parity matrices. These have parameters $[n_A, k_A, d_A]$ and $[n_B, k_B, d_B]$, and their dual codes have parameters $[n_A^\intercal, k_A^\intercal, d_A^\intercal]$ and $[n_B^\intercal, k_B^\intercal, d_B^\intercal]$. Explicitly,

\[n_A = \dim(C_1);\quad k_A = \dim(\ker(A));\quad n_A^\intercal = \dim(C_0);\quad k_A^\intercal = \dim(\ker(A^\intercal)) = \dim(C_0/\im(A)),\]
so $n_A, k_A$ are the length and dimension of the code $C_\bullet$, and $n_A^\intercal, k_A^\intercal$ are the length and dimension of the dual code $C_\bullet^*$. We will also use the respective distances $d_A, d_A^\intercal$. Similar definitions apply to $B$.

The tensor product quantum code is given by the chain complex:

\[\begin{tikzcd}(C\tens D)_\bullet = C_1\otimes D_1 \arrow[r, "\del_1"] & C_0 \otimes D_1 \oplus C_1 \otimes D_0 \arrow[r, "\del_0"] & C_0\otimes D_0 \end{tikzcd} \]

where by convention we say that $\del_1 = P_Z^\intercal$ and $\del_0 = P_X$, and

\[P_Z = \begin{pmatrix}A^\intercal \tens \id_{D_1} &\id_{C_1} \tens B^\intercal\end{pmatrix}; \quad P_X= \begin{pmatrix} \id_{C_0} \tens B & A \tens \id_{D_0}\end{pmatrix}\]

We will use some straightforward facts about this code. It has parameters

\[\llbracket n_A^\intercal n_B + n_An_B^\intercal, k_A^\intercal k_B+ k_Ak_B^\intercal, \min(d_A,d_B,d_A^\intercal,d_B^\intercal)\rrbracket.\]

That $n_{(C\tens D)} = n_A^\intercal n_B + n_An_B^\intercal$ is obvious from $\dim((C\tens D)_1)$. $k_{(C\tens D)} = \dim(H_1((C\tens D)_\bullet)) = \dim(\ker(P_X)/\im(P_Z^\intercal))$, which can be found using the Künneth formula [29]:

\[H_1((C\tens D)_\bullet) \cong H_0(C_\bullet) \tens H_1(D_\bullet) \oplus H_1(C_\bullet) \tens H_0(D_\bullet) \]

In particular we have the decomposition

\begin{equation}\ker(P_X) = \ker(P_X)/\im(P_Z^\intercal) \oplus \im(P_Z^\intercal) = C_0/\im(A) \otimes \ker(B) \oplus \ker(A)\otimes D_0/\im(B) \oplus \im(P_Z^\intercal).\end{equation}

The distance can be obtained easily using this expression for $\ker(P_X)$ and a similar one for $\ker(P_Z)$:

\begin{equation}\ker(P_Z) = \ker(A^\intercal) \otimes D_1/\im(B^\intercal) \oplus C_1/\im(A^\intercal) \otimes \ker(B^\intercal) \oplus \im(P_X^\intercal)\end{equation}

These equations are only required by the Künneth formula to hold up to isomorphism, but one can check using a simple counting argument that they hold on the nose.

Considering families of tensor product codes built from families of classical codes, the products will be LDPC iff the classical codes are also LDPC, and the parameters above mean that the scaling have $d \in \CO(\sqrt{n})$ and $k \in \CO(n)$. These bounds are saturated by quantum expander codes [21], using the fact that hypergraph product codes [26] are tensor product codes with one of the classical codes dualised.

§.§ Balanced products

Balanced products are an important ingredient in the construction of the first good qLDPC codes [24], and were used in much of the work leading up to that landmark result [3, 14, 25]. The intuition is that by systematically quotienting by a coherent action we can remove qubits and parity checks from our code while, in certain cases, leaving the encoding rate and distance high.

Let $C_\bullet$, $D_\bullet$ be classical codes. Let $G$ be a finite group, with a right action $\ra$ on $C_\bullet$ and left action $\la$ on $D_\bullet$, meaning that the following squares commute:

\[
\begin{tikzcd}
C_1 \otimes \F_2 G \arrow[r, "A \otimes \id"]\arrow[d, "\ra"] & C_0 \otimes \F_2 G \arrow[d, "\ra"]\\
C_1 \arrow[r, "A"] & C_0
\end{tikzcd}
\quad
\begin{tikzcd}
\F_2 G\otimes D_1 \arrow[r, "\id \otimes B"]\arrow[d, "\la"] & \F_2 G\otimes D_0 \arrow[d, "\la"]\\
D_1 \arrow[r, "B"] & D_0
\end{tikzcd}
\]

i.e. the actions are coherent with respect to the differentials. Then we have the balanced product $(C \underset{G}{\otimes} D)_\bullet$,

\[\begin{tikzcd}C_1\underset{G}{\otimes} D_1 \arrow[r, "\del_1"] & C_0 \underset{G}{\otimes} D_1 \oplus C_1 \underset{G}{\otimes} D_0 \arrow[r, "\del_0"] & C_0\underset{G}{\otimes} D_0 \end{tikzcd} \]

where $C_1\underset{G}{\otimes} D_1 = C_1 \otimes D_1/ (c\ra g \otimes d \sim c \otimes g\la d)$ etc, and so $C_0\underset{G}{\otimes} D_1$ has elements being equivalence classes $[c,d]$. The differentials are given by descent from the differentials in $(C\otimes D)_\bullet$ to the quotients, which works due to the coherence of the left and right actions.

This is a specific case of a more general structure, where $G$ can be any differential graded algebra and $C_\bullet$, $D_\bullet$ are right and left modules in the category of chain complexes. Here, we only use the finite group case.

We need a consistent definition of distance for the code, hence a consistent notion of weight for an equivalence class $[c,d] \in C_0 \underset{G}{\otimes} D_1$ and the same for $C_1 \underset{G}{\otimes} D_0$. To this end, we assume that $G$ acts by taking basis states to basis states for both the left and right actions, so $|c\ra g \otimes d| = |c \otimes g\la d|$.

Evidently when $G = \{e\}$, or otherwise acts trivially everywhere, the balanced product reduces to the tensor product above. Unlike the tensor product there do not exist straightforward expressions for $\llbracket n,k,d\rrbracket$ as these parameters depend on the group $G$ and its actions.

§ TYPE 1 SURGERY WITH BALANCED PRODUCT CODES

Here we show that all balanced product codes of classical codes always have a choice of logical qubits such that there is a representative $\overline{Z}$ and $\overline{X}$ which is separated, for every logical qubit. Thus we can perform Type 1 surgery with such codes.

A logical $\overline{Z}$ or $\overline{X}$ operator $v$ is separated if there is no other logical operator $u$ such that $\supp(u) \subset \supp(v)$.

Let $\del_A : A_1 \rightarrow A_0$ be a matrix over $\F_2$. Then there is always a basis $\CA$ of $\ker(\del_A)$ such that each element of $\CA$ has no other non-zero element of $\ker(\del_A)$ contained in its support.

Start with an arbitrary basis $\CA'$ of $\ker(\del_A)$. If a basis element $v \in \CA'$ has another non-zero vector $u$ contained in its support, it must also have the vector $v + u$ contained too. At least one of these must be linearly independent of the other vectors in $\CA'$. Then, replace $v$ with either $u$ or $v+u$ – whichever one is linearly independent of the rest – in $\CA'$. Iterate this for all elements of $\CA'$ until no elements contain another non-zero vector in $\ker(\del_A)$ and we are left with $\CA$.

Every CSS code has a choice of logical qubits such that there is a $\overline{Z}$ operator on each logical qubit which is separated.

For the $\overline{Z}$ operator, let $\del_A$ above be $P_X$, and let $A_1 = C_1, A_0 = C_0$ in our 3-term chain complex. Then there is a basis $\CA$ of $\ker(P_X)$ such that each element of $\CA$ has no other non-zero element of $\ker(P_X)$ contained in its support. A choice of logical qubits is the same as a choice of basis of $H_1(C_\bullet) = \ker(P_X)/\im(P_Z^\intercal)$. This is a quotient of $\ker(P_X)$ and so any basis of $\ker(P_X)$ must span $H_1(C_\bullet)$, although there may be some elements in $\CA$ which land in the same equivalence classes. Then, there is a basis $\{[v]_i\}$ of $H_1(C_\bullet)$ such that there is a representative of each equivalence class $[v]_i$ in the basis which belongs to $\CA$ and so is separated.

As a corollary, the same applies to $\overline{X}$ operators by dualising. Unfortunately, we could not prove that these choices of logical qubits can always coincide, allowing separated $\overline{X}$ and $\overline{Z}$ operators with the same logical qubits. However, when the CSS codes are suitable products we can prove this.

Let $(C\otimes D)_\bullet$ be a tensor product such that the classical parity-check matrices. Then there is a basis of $H_1((C\otimes D)_\bullet)$, i.e. a tensor product decomposition of the logical space into qubits, such that all logical qubits have separated $\overline{Z}$ and $\overline{X}$ operators.

Given $\ker(P_X)/\im(P_Z^\intercal) = C_0/\im(A) \otimes \ker(B) \oplus \ker(A)\otimes D_0/\im(B)$, we choose a basis such that it has a paired basis in $\ker(P_Z)/\im(P_X^\intercal) = \ker(A^\intercal) \otimes D_1/\im(B^\intercal) \oplus C_1/\im(A^\intercal) \otimes \ker(B^\intercal)$. Let $\CB$ and $\CA$ be bases of $\ker(B)$ and $\ker(A)$ such that all basis elements contain no other basis elements, which we can always do by Lemma <ref>. Similarly let $\CB^\intercal$ and $\CA^\intercal$ be such bases for $\ker(B^\intercal)$ and $\ker(A^\intercal)$.

Now, each basis element $b_i$ in $\CB$ can overlap with at most $|b_i|-1$ entries in the support of any other basis element in $\CB$, so there are at least $k_B$ entries of $D_0$ which belong to exactly one basis element in $\CB$. We claim that these $k_B$ entries are representatives of a basis for $D_1/\im(B^\intercal)$. $D_1/\im(B^\intercal) \cong \ker(B)$, so there are enough entries. The entries are evidently linearly independent, so we must show that none belong to the same equivalence class. If any two entries $e_{\alpha}, e_{\beta}$ belong to the same equivalence class, there is some vector $w$ in $\im(B^\intercal)$ such that $e_{\alpha} = e_{\beta} + w$. But $\im(B^\intercal)$ is the row space of $B$, which is the same as $\ker(B)^\perp$. As $e_{\alpha}$ and $e_{\beta}$ belong to different vectors $b_{\alpha}, b_{\beta}$ in $\ker(B)$ there will be a vector $w$ in $\ker(B)^\perp$ such that $|b_{\alpha} \odot w| = 1$ and $|b_{\beta} \odot w| = 1$, but this is a contradiction as the weight of the Hadamard product must be even. Hence these entries all belong to different equivalence classes.

We choose a basis of $C_0/\im(A)$, $C_1/\im(A^\intercal)$ and $D_0/\im(B)$ in the same manner, using $\ker(A^\intercal)$, $\ker(A)$ and $\ker(B^\intercal)$ respectively. We claim that these amount to a pairing of bases, i.e. $[u]_i \cdot [v]_j = \delta_{i,j}$ for basis elements $[u]_i \in \ker(P_X)/\im(P_Z^\intercal)$ and $[v]_j \in \ker(P_Z)/\im(P_X^\intercal)$. Let $[u]_i = [f_{\alpha}\otimes b_\beta] \in C_0/\im(A) \otimes \ker(B)$ have a representative $f_{\alpha} \otimes b_\beta$, which we claim has a paired representative $a_{\alpha} \otimes e_\beta \in [a_\alpha \otimes e_\beta] \in \ker(A^\intercal) \otimes D_1/\im(B^\intercal)$, belonging to $[v]_i$.

$|f_\alpha \odot a_\beta| = 1$ and $|b_\alpha \odot e_\beta| = 1$ by the fact that $f_\alpha$ is an entry inside $\supp(a_\alpha)$ and $e_\beta$ is an entry inside $\supp(b_\beta)$. Hence $[f_\alpha\otimes b_\beta] \cdot [a_\alpha \otimes e_\beta] = 1$. As $f_\alpha$ and $e_\beta$ do not belong to any other vectors in $\CA^\intercal$ or $\CB$ their dot product with any other element in $\ker(P_Z)/\im(P_X^\intercal)$ is zero. Then follow the same argument for $\ker(A)\otimes D_0/\im(B)$ and $C_1/\im(A^\intercal) \otimes \ker(B^\intercal)$ and we are done.

Let $(C \underset{G}{\otimes} D)_\bullet$ be a balanced product. Let $G$ act by taking basis elements to basis elements. Then there is a basis of $H_1((C\underset{G}{\otimes} D)_\bullet)$, i.e. a tensor product decomposition of the logical space into qubits, such that all logical qubits have separated $\overline{Z}$ and $\overline{X}$ operators.

Call $G_\bullet = \F_2 G = G_0$.
A balanced product is a cokernel in the category of chain complexes over $\F_2$. We have the chain map $f_\bullet: (C\otimes G \otimes D)_\bullet \rightarrow (C\otimes D)_\bullet$ such that $f_\bullet = (\ra \otimes \id)_\bullet$, so e.g. $(C_1\otimes G\otimes D_1) \ni c \otimes g \otimes d \mapsto c\ra g \otimes d \in (C_1 \otimes D_1)$. Similarly let $h_\bullet = (\id \otimes \la)_\bullet$. Then we have a cokernel ${\rm coker}(f+h)_\bullet$, with components:

\[\begin{tikzcd}
C_1\otimes G_0 \otimes D_1 \arrow[r] \arrow[d, "f_2+h_2"]& C_0\otimes G_0\otimes D_1\oplus C_1\otimes G_0\otimes D_0 \arrow[r]\arrow[d, "f_1+h_1"]& C_0\otimes G_0\otimes D_0\arrow[d, "f_0+h_0"]\\
C_1 \otimes D_1 \arrow[r, "\del_1"] \arrow[d, "{\rm coker}(f_2+h_2)"] & C_0\otimes D_1\oplus C_1 \otimes D_0 \arrow[r, "\del_0"] \arrow[d, "{\rm coker}(f_1+h_1)"]& C_0\otimes D_0 \arrow[d, "{\rm coker}(f_0+h_0)"]\\
(C_1 \underset{G}{\otimes} D_1) \arrow[r, "\del_1' "] & C_0 \underset{G}{\otimes} D_1\oplus C_1 \underset{G}{\otimes} D_0 \arrow[r,"\del_0' "] & C_0 \underset{G}{\otimes} D_0
\end{tikzcd}\]

The map ${\rm coker}(f_1+h_1)$ is a quotient, and restricts to $\ker(\del_0)$ then lifts to $H_1((C \otimes D)_\bullet)$. Thus a basis of the homology space $H_1((C \otimes D)_\bullet)$ automatically spans $H_1((C \underset{G}{\otimes} D)_\bullet)$. Additionally, $H_1((C \otimes D)_\bullet) \cong H^1((C \otimes D)_\bullet)$ and $H_1((C \underset{G}{\otimes} D)_\bullet) \cong H^1((C \underset{G}{\otimes} D)_\bullet)$ so the same applies to a basis of the cohomology space.

We now check that the basis elements from Lemma <ref> are suitable. First, we choose bases of all the individual spaces as before, e.g. $\ker(B)$ and $D_1/\im(B^\intercal)$ together, and $C_0/\im(A)$ and $\ker(A^\intercal)$ together.

By coherence of the $G$-action, any element $b \in \ker(B)$ remains in $\ker(B)$ under the left action. Any separated basis element $b\in \ker(B)$ remains separated under this action. If it did not, then there would be a vector in $\ker(B)$ contained in $\supp(g\la b)$, which could be moved to $\supp(b)$ by $g^{-1}\la$, meaning that $b$ would not be separated. The same applies to the right action.

We then form equivalence classes $[c \ra g \otimes d] = [c \otimes g \la d ] \in C_0 \underset{G}{\otimes} D_1$ under the $G$-action. Some previously different basis elements may be put into the same equivalence classes, or no longer be linearly independent, so we choose a subset of elements which are. The weight of the Hadamard product is invariant under the right $G$-action, i.e. $|a \odot c| = |(a \ra g) \odot (c \ra g)|$, $\forall a, c \in C_0$. If it were not, $|a+c| \neq |(a+c)\ra g|$, but the action maps between basis states of $C_0$ so this is impossible. The same applies to the left action. We can thus consistently define the Hadamard product weight between two equivalence classes under the $G$-action, and the basis vectors we chose are all still separated. These then give paired bases for $H_1((C \underset{G}{\otimes} D)_\bullet)$ and $H^1((C \underset{G}{\otimes} D)_\bullet)$.

[14, 4]
Let $A$ and $B$ be the incidence matrices of the cycle graphs $\CC_6$ and $\CC_3$:

\[\tikzfig{c6}\quad \quad \tikzfig{c3}\]

the only non-zero elements of $\ker(A)$ and $\ker(B)$ are the all-1 vectors in $\F_2^6$ and $\F_2^3$ respectively.
Let $G = \Z_3$ act on each graph by rotating by $2\pi/3$. Then $(C \underset{G}{\otimes} D)_\bullet$ is described by the cell complex

\[\tikzfig{twisted_toric}\]

where grey vertices and edges wrap around to the other side, giving us the $\llbracket 12, 2, 3\rrbracket$ twisted toric code. Separated $\overline{Z}$ logical operators given by Theorem <ref> are then those of the form:

\[\tikzfig{twisted_toric2} \quad\quad \tikzfig{twisted_toric3}\]

and separated $\overline{X}$ logical operators

\[\tikzfig{twisted_toric4} \quad\quad \tikzfig{twisted_toric5}\]

where green edges have $Z$ Paulis acting on them, and when a red string crosses an edge that edge has an $X$ Pauli.

Picking out separated logicals for each logical qubit is easy by eye in this case, but in general is nontrivial.

We have proved that good qLDPC codes, along with other balanced product codes, are amenable to Type 1 surgery. Unfortunately, as discussed previously, Type 1 surgery with good qLDPC codes will hamper the asymptotics. Even if only $o(\sqrt{k})$ logical qubits are involved in any Pauli product measurement at a given timestep, as in [30], the weight of a single operator is at least $d \in \Theta(n)$, and hence the number of physical qubits required for the ancilla patch scales as $n^2$. We therefore move to Type 2 surgery.

§ TYPE 2 CODE SURGERY AS A PUSHOUT

This section is a recap of CSS code surgery as given in [9]. We describe a Type 2 merge along a logical $\overline{Z}$ operator, with the understanding that all other operations – $\overline{X}$-merges and both splits – follow immediately as corrolaries.[We shift the indices up in the complexes when compared to the original definition for convenience.] As the raw definitions are quite abstract we first give some intuition of the conditions in Section <ref> and follow with the basic example of lattice surgery with surface codes.

Matching means that the logical operator exists in both codes, and is in the support of the `same' $X$-checks. This is so we can build a small intermediate code which bridges between the two operators. The separation property means that the logical operators $v$ and $w$ must not contain another logical operator in their support. This condition makes the merge of codes quotient only the desired two logicals together. We also require the logical $\overline{Z}$ operators $v$ and $w$ to each be gauge-fixable[Nomenclature adapted from [28].], i.e. each qubit $e_i$ in the support of $v$ must have a matching $\overline{X}$ operator $u$ such that $u \odot v = e_i$, where $\odot$ is the Hadamard product i.e. elements multiplied entrywise, and the same for $w$. Together with separation, this means that the merge is genuinely a $\overline{Z}\tens \overline{Z}$ measurement, as gauge-fixability guarantees that measurement outcomes of stabilisers in the new bridging code yield the two different outcomes of the $\overline{Z}\tens\overline{Z}$ measurement. Last, we require that the merged code has distance at least as large as the minimum of the input codes, that is have distance bounded below; the $X$ distance is guaranteed by <cit.> to satisfy this, but the $Z$ distance may decrease (this is flipped for an $\overline{X}\otimes\overline{X}$ measurement). In an abuse of terminology, we sometimes refer to merges which have distance bounded below as being distance preserving, although technically a merge could increase the distance.

Given two surface codes, we can choose our matching $\overline{Z}$ operators to be strings running along the left and right boundaries from top to bottom.

\[\tikzfig{surgery_example1}\]

The operators are matching, as they have the same number of qubits and the same $X$-checks on each of these qubits. They are separated, as they contain no other $\overline{Z}$ operators. For gauge-fixability, observe that for each qubit in the $\overline{Z}$ operators we have an orthogonal $\overline{X}$ operator stretching across the lattice, e.g.

\[\tikzfig{surgery_example2}\]

such that the orthogonal operator only crosses the $\overline{Z}$ operator at that qubit. This is important for the next step. We initialise new qubits connecting the two lattices, one for each pair of $X$-checks the $\overline{Z}$ operators are in the support of:

\[\tikzfig{surgery_example3}\]

And also create new $Z$ stabilisers for each pair of qubits in the $\overline{Z}$ operators, i.e. the new faces. Measuring all stabilisers now constitutes a $\overline{Z}\otimes\overline{Z}$ measurement. If the new $Z$ stabilisers all return the measurement outcome +1, then we have acquired the overall outcome +1 on the logical measurement. If one of the new stabilisers returns a -1 outcome, this is the same as a +1 outcome but with an $\overline{X}$ operator acting on the associated qubit:

\[\tikzfig{surgery_example4}\]

An odd number of these outcomes then means we have received an overall $-1$ outcome on the logical measurement, as the -1 measurement branch is the same as a +1 branch but with an $\overline{X}$ operator on one of the qubits before the measurement. We can do this on either side of the lattice, which gives the same logical outcome up to a relabelling of output basis states, and for an $\overline{X}$ operator on any of the qubits involved in the merge. Gauge-fixability of the $\overline{Z}$ operators implies that we can always do this for merges, and so the merges will genuinely constitute $\overline{Z}\otimes\overline{Z}$ measurements.

Alternatively this could be defined as creating a new surface code consisting of just the middle strip, then gluing it into the first and second initial codes. More generally, if the codes are defined from cell complexes the merged code is defined by two connected sums of cell complexes: gluing the first cell complex to a small intermediate cell complex, and then gluing that to the second cell complex. Proving distance bounds for arbitrary merges of codes will be complicated, as it concerns how systolic geometry [17] interacts with connected sums.

As described in Section <ref> the model we adopt for the rest of the paper is one where we have two identical codeblocks, and we can perform merges pairwise between logical qubits of the same index, like so:

\begin{equation}\tikzfig{merge_schema}
\end{equation}

This is so we can guarantee the matching condition. It will often be possible to do merges between logical qubits with different indices, and this is important for computation, but it requires additional knowledge about the specific codes, whereas the limited pairwise model can be studied quite generally.[One can always perform transversal CNOTs to give pairwise logical CNOTs between CSS codes. In general, this requires every qubit to be used in a CNOT, and performs logical CNOTs on every logical qubit. The model of pairwise merges is different, allowing for pairwise parity measurements and splits between only the desired logical qubits. It is still a far cry from enabling universal quantum computation.]

We now get into some definitions.

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

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

where $\tilde{V}_1$ is the basis of $V_1$, ${\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 subspace $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_1 \subseteq C_1$ etc.
Let $V_\bullet$ be a logical operator subcomplex of two chain complexes
\[\begin{tikzcd}C_\bullet = C_{2}\arrow[r, "\del_1"]& C_1\arrow[r, "\del_{0}"]& C_{0}\end{tikzcd}\]
\[\begin{tikzcd}D_\bullet = D_{2}\arrow[r, "\del_1"]& D_1\arrow[r, "\del_{0}"]& D_{0}\end{tikzcd}\]
simultaneously, so there is some vector $v \in C_1$ and $w \in D_1$ such that $\tilde{V}_1 \cong {\rm supp\ } v \cong {\rm supp\ } w$, $\del^{V_\bullet}_{0} = \del^{C_\bullet}_{0}\restriction_{{\rm supp\ } v} \cong \del^{D_\bullet}_{0}\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 means that there is a matching $\overline{Z}$ logical operator given by $v$, $w$ in our parlance.

For the separation property see Definition <ref>. This is a slightly simpler and more restrictive definition than the one used in [9], but it will suffice for our purposes.

Let $C_\bullet$ be a qubit CSS code and $u$ be a representative of the equivalence class $[u]\in H_1(C_\bullet)$, which is a basis vector for $H_1(C_\bullet)$. Let $x$ be a basis vector of $C_0$, with $|x| = 1$ and $u \odot x = x$. We say that $x$ is a qubit in the support of $u$. Recall that $u$ has a unique paired basis vector $[v]\in H^1(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 $u \odot v = x$. We say that $u$ is gauge-fixable when it is possible to safely correct all qubits in the support of $u$.

(Distance bounded below)
Let the output code $M_\bullet$ of a logical $\overline{Z}$-merge have no logical $\overline{Z}$ operators with weight lower than $\min(d_C,d_D)$. Then we say that the merged code has distance bounded below.

If these conditions are satisfied, we can perform a merge, which is defined using a small distance 2 tensor product code:

Let $V_\bullet = \begin{tikzcd}V_1\arrow[r] & V_{0}\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_2 \arrow[r] &W_1 \arrow[r] & W_{1}\end{tikzcd}\]

\[W_2 = P_1\tens V_1 = V_1;\quad W_1 = (P_0\tens V_1)\oplus (P_{1}\tens V_{0}) = (\F_2^2\tens V_1)\oplus V_{0};\quad W_0 = P_0\tens V_{0} = \F_2^2 \tens V_{0}\]

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

Let $V_\bullet$ be a simultaneous $\overline{Z}$ logical operator subcomplex of both $C_\bullet$ and $D_\bullet$. Then define the `sandwiched code' $M_\bullet$ as the pushout of a pushout:[This is a categorically `evil' notion, as we require not just pushouts up to isomorphism, but such that Hamming weights of vectors remain the same as in the starting codes. The chosen member of the isomorphism class is one for which all morphisms in the pushouts map basis elements to basis elements, and so is defined up to permutation of rows and columns, which is sufficient.]

\[\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] & & M_\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_1$ into each of the copies of $V_1$ in $W_1$, and the same for $V_0$ into $W_0$.

\[\begin{tikzcd}M_\bullet = C_2 \oplus D_2 \oplus V_1 \arrow[r] &C_1 \oplus D_1 \oplus V_0 \arrow[r] & C_0 \oplus D_0 \end{tikzcd}\]

The $\overline{Z}$-merge is then given by taking the initial codes $C_\bullet, D_\bullet$ and initialising a fresh set of $r$ qubits in the $\ket{+}$ state, where $r$ is the number of $X$-stabiliser generators which the logical operator is in the support of. Then measure all stabiliser generators as normal. This is guaranteed by the conditions above to constitute a $\overline{Z}\otimes \overline{Z}$ measurement on the two logicals combined by the merge, while preserving error-correction at all timesteps.

As the number of checks a qubit participates in is bounded above by a constant for qLDPC codes, and the number of qubits in a logical operator can scale at most linearly with $n$, we incur no asymptotic overhead by initialising the fresh qubits for a merge. Similarly, we add at most 1 qubit to the support of any check in the code, and add only a linear number of new stabiliser generators. We showed in [9] that merges between qLDPC codes maintain the qLDPC property.

§ SEPARATION IS GAUGE-FIXABILITY

We will prove in this section that for all CSS codes having separated and gauge-fixable operators are equivalent properties. Hence all balanced product codes have separated and gauge-fixable operators for each logical qubit.

A vector $u \in \ker(P_X)\backslash \im(P_Z^\intercal)$ is gauge-fixable iff for every pair $(e_i, e_j)$ of basis vectors in ${\rm supp\ }(u)$ there is a vector $a$ in $\im(P_X^\intercal)$ such that $u \odot a = e_i+e_j$.

If there are two vectors $v, w$ paired with $u$ such that $v \odot u = e_i$ and $w \odot u = e_j$ then $v+w \odot u = e_i + e_j$. As each basis vector in $u$ must be safely correctable, $u$ always has a vector $a = v+w \in \im(P_X^\intercal)$ such that $a \odot u = e_i + e_j$. Going the other way, there must be at least one paired vector $v$ with $u$ such that $u \cdot v = 1$ – we don't assume that $|u \odot v| = 1$, just that the dot product is 1, i.e. they have an odd number of intersecting basis vectors. This can be reduced to an intersection of 1 by applying a vector in $\im(P_X^\intercal)$ corresponding to a pair $(e_i, e_j)$ to each of the pairs of intersecting basis vectors apart from the last one. This single basis vector can then be moved around $u$ by further applications of vectors in $\im(P_X^\intercal)$.
We find this equivalent definition of gauge-fixing more helpful in practice, as it requires only data about the $X$ stabilisers, rather than paired logical operators, the choice of which depends on the choice of basis of $H_1(C_\bullet)$.

Let $\del_A : A_1 \rightarrow A_0$ be a matrix over $\F_2$. Then for any $v \in \ker(\del_A)$, either for any pair of basis vectors of $A_1$ $(e_i, e_j) \in \supp(v)$ there is a vector $b \in \im(\del_A^\intercal)$ such that $v \odot b = e_i+e_j$ or there is another non-zero vector $u \in \ker(\del_A)$ such that $\supp(u) \subset \supp(v)$.

Define the vector space $S = \{w \odot v : w \in \ker(\del_A)^\perp \}$. Observe that any vector in $S$ must have even Hamming weight, and that

\[S \cong \{w \odot v : w \in \ker(\del_A\restriction_{\supp\ v})^\perp \} = \ker(\del_A\restriction_{\supp\ v})^\perp,\]

as any vectors in $\ker(\del_A)^\perp$ wholly outside of $\supp(v)$ will not contribute to the Hadamard product, and the isomorphism merely entails chopping off some entries which will always be $0$. Now, $\dim(S) \leq |v|-1$, as $\dim(\ker(\del_A\restriction_{\supp\ v})) \geq 1$ by definition.

Suppose $\dim(S) = |v|-1$. Then $v$ has no other vectors in $\ker(\del_A)$ contained in its support, as then $\dim(\ker(\del_A\restriction_{\supp\ v})) = 1$, and for any pair of basis vectors of $A_1$ $(e_i, e_j) \in \supp(v)$ there is a vector $b \in \im(\del_A^\intercal)$ such that $v \odot b = e_i+e_j$. To see this, view $S$ as the row space of a matrix:

\[\begin{pmatrix}
w_1\odot v\\
w_2\odot v\\
\vdots\\
w_m \odot v\\
\end{pmatrix}
\]

where $m = |v| - 1$, with some chosen basis of $S$. Then, put the matrix in row echelon form by performing Gaussian elimination:

\[\begin{pmatrix}
1 & * & * & * & \cdots & *\\
0 & 1 & * & * & \cdots & *\\
& & & \vdots & & \\
0 & 0 & 0 & 0 & \cdots & 1\\
\end{pmatrix}
\]

where $*$ values are unknown. As $\dim(S) = |v|-1$, without knowing anything else about the code, there will be exactly 1 row which is indented by 2 from the previous row. But each row must have an even number of 1s in it, including the last row, so the matrix must actually have the row echelon form:

\[\begin{pmatrix}
1 & *  & * & \cdots & * & *\\
0 & 1  & * & \cdots & * & *\\
0 & 0  & 1 & \cdots & * & *\\
& & \vdots & & & \\
0 & 0 & 0 & \cdots & 1 & 1\\
\end{pmatrix}
\]

Then, add rows from the bottom to the top as necessary to give

\[\begin{pmatrix}
1 & 0  & 0 & \cdots & 0 & *\\
0 & 1  & 0 & \cdots & 0 & *\\
0 & 0  & 1 & \cdots & 0 & *\\
& & \vdots & & &  \\
0 & 0 & 0 & \cdots & 1 & 1\\
\end{pmatrix}
\]

i.e. an identity matrix with one column unknown to the right. But once again each row must have an even number of non-zero entries, as $S = \ker(\del_A\restriction_{\supp\ v})^\perp$, so the column to the right must have all entries equal to 1. Therefore, we have $|v|-1$ different pairs, and combinations of these suffice to give any pair in $\supp(v)$.

Now, suppose $\dim(S) < |v|-1$. Then, as $\dim(\ker(\del_A\restriction_{\supp\ v})^\perp) > 1$, there must be another vector in $\ker(\del_A)$ contained in $\supp(v)$.

This means that a vector $v$ in $\ker(\del_A)$, with no other vectors in $\ker(\del_A)$ contained in $\supp(v)$, will always have the property that for any pair of basis vectors of $A_1$ $(e_i, e_j) \in \supp(v)$ there is a vector $b \in \im(\del_A^\intercal)$ such that $v \odot b = e_i+e_j$.

This lemma implies that separation and gauge-fixing coincide. As a consequence, by Theorem <ref> the gauge-fixability condition is satisfied for all logical qubits in balanced product codes.

§ DISTANCE PRESERVATION

It is difficult to prove when a merge has distance bounded below for generic codes, even when we know that the codes have product structures.

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

then $(C\otimes D)_\bullet$ is a toric code, with parameters $\llbracket 32, 2, 4 \rrbracket$. The vector $v = \begin{pmatrix}1\\1\\1\\1\end{pmatrix}$ is the only non-zero vector in $\ker(B)$, and hence basis vector. For a $\overline{Z}$-merge to an identical toric codeblock, we can choose any individual entry in $C_0$ to use for the element of $C_0/\im(A)$, as they all belong to the same equivalence class, giving us the separated gauge-fixable operator in $C_0\otimes D_1$. We can do similar for $C_1 \otimes D_0$, and perform merges without lowering the code distance.

If we modify $B$ slightly, so that now

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

then $\ker(B^\intercal) = 0$ so the tensor product $(C\otimes D)_\bullet$ has parameters $\llbracket 41, 1, 4 \rrbracket$. If we follow the same procedure of choosing a separated gauge-fixable operator in $C_0\otimes D_1$ and then perform a $\overline{Z}$-merge with an identical code then the merged code $M_\bullet$ has distance 3, which we check in Appendix <ref>; hence the distance has been lowered by the merge.

We can construct similar examples using balanced products with non-trivial actions of $G$. As a consequence we must be careful about the choice of classical codes used in the product codes, as minor modifications can result in the distance being lowered.

Let $S_\bullet$ be a CSS code with differentials $P_Z^\intercal$ and $P_X$, parameters $\llbracket n, k,d \rrbracket$ and a specified separated $\overline{Z}$ operator $v$. Then if we merge two copies of $S_\bullet$ along $v$ then $M_\bullet$ has the form

\[\begin{tikzcd}S_2\oplus S_2\oplus V_1 \arrow[r, "\del_1"] & S_1\oplus S_1\oplus V_0 \arrow[r, "\del_0"] & S_0\oplus C_0 \end{tikzcd}.\]

The differentials are

\[\del_1 = \begin{pmatrix}
P_Z^\intercal &0& L\\
0 & P_Z^\intercal & L\\
0 & 0 & \del_0^{V_\bullet}
\end{pmatrix}; \quad \del_0 = \begin{pmatrix}
P_X &0 & K\\
0 & P_X & K
\end{pmatrix}\]

where $L: V_1 \rightarrow S_1$ is a matrix with a single 1 in each column and at most a single 1 in each row. The non-zero rows are those which for $P_Z^\intercal$ land in $\supp(v) \subset S_1$. $K: V_0 \rightarrow S_0$ is also a matrix with a single 1 in each column and at most a single 1 in each row. The non-zero rows are those in $P_X$ with non-zero Hadamard product with $v$. These matrices satisfy $P_X L + K\del_0^{V_\bullet} = 0$, hence $P_X P_Z^\intercal = 0$.

In order to show that the merge is distance-preserving, we must show that there is no $\overline{Z}$ operator, i.e. vector $u$ in $\ker(\del_0)\backslash \im(\del_1)$, with weight lower than $d$ in $M_\bullet$; the $X$-distance is guaranteed to be preserved by <cit.>.
As $K$ has at most a single 1 per row, observe that any vector $u$ with $\supp(u) \subset V_0 \subset T_1$ is not in $\ker(\del_0)$. If $u$ has $\supp(u) \cap V_0 =0$ then it is a vector in $(S \oplus S)_1$ and hence guaranteed to either be in $\im(P_Z^\intercal \oplus P_Z^\intercal)$, not in $\ker(P_X \oplus P_X)$ or have $|u|\geq d$. Hence we are looking for $u$ to have support in $S_1 \oplus S_1 \subset T_1$ and also in $V_0 \subset T_1$. Given a vector $w$ with support in the first $S_1$ and $T_1$, it must also have support in the second $S_1$.

It is helpful to consider a chain complex which is simpler than $M_\bullet$. We call this chain complex $M_\bullet^{\rm red}$, the reduced chain complex of $M_\bullet$.

Let $M_\bullet^{\rm red}$ be the reduced chain complex of $M_\bullet$.

\[\begin{tikzcd}M_\bullet^{\rm red} = S_2 \oplus V_1 \arrow[r, "\del_1^{\rm red}"] & S_1 \oplus V_0 \arrow[r, "\del_0^{\rm red}"] &S_0\end{tikzcd}\]

\[\del_1^{\rm red} = \begin{pmatrix}
P_Z^\intercal & L\\
0 & \del_0^{V_\bullet}
\end{pmatrix}; \quad \del_0^{\rm red} = \begin{pmatrix}
P_X & K
\end{pmatrix}\]

Let $w$ be a vector with $l = \dim(\supp(w)\cap V_0)$, and $d$ be the distance of $S_\bullet$. $M_\bullet$ has a vector $u \in \ker(\del_0)\backslash \im(\del_1)$ with $|u| < d$ iff $M_\bullet^{\rm red}$ has a vector $w \in\ker(\del_0^{\rm red})\backslash \im(\del_1^{\rm red})$ such that $|w| < \frac{1}{2}(d + l)$.

Given $w$, we can always make a vector $u$ with entries in the second copy of $S_1$ identical to the entries in the first copy of $S_1$. By inspection this is guaranteed to be in $\ker(\del_0)\backslash \im(\del_1)$. If $|w| < \frac{1}{2}(d + l)$ then $|u| = 2(|w| - l) + l = 2|w| - l < d$.

Given $u$, with support in both copies of $S_1$ and also in $V_0$, let $s_1 = \dim(\supp(u) \cap S_1)$ for one of the copies of $S_1$ and $s_2$ for the other. Then $|u| = s_1 + s_2 + l$, for $l = \dim(\supp(u) \cap V_0)$. Then $s_1 = |u| - s_2 - l < d - s_2 - l$. W.l.o.g. assume that $s_1 \leq s_2$. Then $ 2s_1 + l \leq s_1 + s_2 + l < d$, so $s_1 < \frac{1}{2}(d-l)$, hence $s_1 + l < \frac{1}{2}(d+l)$, and identify $s_1 + l$ with $|w|$ for the corresponding $w \in \ker(\del_0^{\rm red})\backslash \im(\del_1^{\rm red})$.

Pairwise Type 2 surgery between Panteleev-Kalachev good qLDPC codes is possible while preserving $d \in \Theta(n)$ iff for each merge between separated logical operators the reduced merged code $M_\bullet^{\rm red}$ has $d_{M_\bullet^{\rm red}} > \gamma d$, for a fraction $0 < \gamma \leq 1$ constant as $n$ varies, and with $d$ the distance of the good qLDPC code.

Observe that when we are concerned solely with the asymptotic scaling of parameters, we can relax distance preservation such that a family of merges between codes in family is distance preserving iff it preserves the distance scaling of the code family.

Pairwise Type 2 surgery between Panteleev-Kalachev good qLDPC codes is asymptotically distance-preserving.

We do not know how to prove or disprove this conjecture, but it will require detailed knowledge of the logical operators being merged and the expansion and product-expansion properties of the Cayley graphs and local checks used in the construction respectively.

§ OPEN PROBLEMS

There other problems concerning Type 2 surgery which are open.

* When is it possible to do internal surgery, i.e. surgery within the same codeblock?

* Is it possible to adapt decoders for the initial codes and use them for merged codes as well?

* How do code thresholds interact with code merges?

* Which other codes with useful properties allow for distance-preserving surgery?

We believe that these questions are algebraically interesting and have important practical implications for performing computation with qLDPC codes.

§ ACKNOWLEDGEMENTS

We are grateful to Aleks Kissinger for helping with the proof of Lemma <ref>, and to Anthony Leverrier for answering several questions about quantum and classical codes. We thank the Wolfson Harrison UK Research Council Quantum Foundation Scholarship for making this work possible.

[1]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
[2]S. Bravyi, A. W. Cross, J. M. Gambetta, D. Maslov, P. Rall and Theodore J. Yoder, High-threshold and low-overhead fault-tolerant quantum memory, arXiv:2308.07915 [quant-ph]
[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]N. P. Breuckmann and S. Burton, Fold-Transversal Clifford Gates for Quantum Codes, arXiv:2202.06647 [quant-ph]
[7]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 2, 035007 (2017).
[8]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)
[9]A. Cowtan and S. Burton, CSS code surgery as a universal construction, arXiv:2301.13738 [quant-ph]
[10]I. Dinur, M. Hsieh, T. Lin and T. Vidick, Good Quantum LDPC Codes with Linear Time Decoders, In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023). Association for Computing Machinery, New York, NY, USA, 905–918. https://doi.org/10.1145/3564246.3585101
[11]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)
[12]D. Gottesman, Fault-tolerant quantum computation with constant overhead, Quantum Info. Comput. 14, 15–16 (November 2014), 1338–1372.
[13]D. Horsman, A. G. Fowler, S. Devitt and R. Van Meter, Surface code quantum computing by lattice surgery, New J. Phys. 14 (2012) 123011
[14]M. B. Hastings, J. Haah and R. O'Donnell, Fiber Bundle Codes: Breaking the $N^{1/2}{\rm polylog}(N)$ Barrier for Quantum LDPC Codes, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (2021), pp 1276-1288
[15]S. Huang, T. Jochym-O'Connor, T. J. Yoder, Homomorphic Logical Measurements, arXiv:2211.03625 [quant-ph]
[16]John van de Wetering, ZX-calculus for the working quantum computer scientist, arXiv:2012.13966 [quant-ph], https://doi.org/10.48550/arXiv.2012.13966
[17]M. G. Katz, Systolic geometry and topology, 137 (American Mathematical Soc., 2007).
[18]A. Kitaev, Fault-tolerant quantum computation by anyons, Ann. Phys.  303 (2003) 3–20
[19]Al. Krishna and David Poulin, Fault-tolerant gates on hypergraph product codes, Phys. Rev. X 11, 011023 (2021)
[20]D. Litinski, A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery, Quantum 3, 128 (2019)
[21]A. Leverrier, J. P. Tillich and G. Zémor, Quantum Expander Codes, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA, 2015, pp. 810-824, doi: 10.1109/FOCS.2015.55.
[22]A. Leverrier and G. Zemor, Quantum Tanner codes, in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), Denver, CO, USA, 2022 pp. 872-883.
doi: 10.1109/FOCS54457.2022.00117
[23]H. P. Nautrup, N. Friis and H. J. Briegel, Fault-tolerant interface between quantum memories and quantum processors, Nat. Commun. 8, 1321 (2017)
[24]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
[25]P. Panteleev and G. Kalachev, Quantum LDPC Codes With Almost Linear Minimum Distance, in IEEE Transactions on Information Theory, vol. 68, no. 1, pp. 213-229, Jan. 2022, doi: 10.1109/TIT.2021.3119384.
[26]J.P. Tillich and G. Zémor, Quantum LDPC Codes With Positive Rate and Minimum Distance Proportional to the Square Root of the Blocklength, in IEEE Transactions on Information Theory, vol. 60, no. 2, pp. 1193-1202, Feb. 2014, doi: 10.1109/TIT.2013.2292061.
[27]A. O. Quintavalle, P. Webster and M. Vasmer, Partitioning qubits in hypergraph product codes to implement logical gates, arXiv:2204.10812 [quant-ph]
[28]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)
[29]C. A. Weibel, An Introduction to Homological Algebra (Cambridge Studies in Advanced Mathematics), Cambridge University Press, doi:10.1017/CBO9781139644136 (1994)
[30]Q. Xu, J. Ataides, C. A. Pattison, N. Raveendran, D. Bluvstein, J. Wurtz, B. Vasic, M. D. Lukin, L. Jiang, H. Zhou, Constant-Overhead Fault-Tolerant Quantum Computation with Reconfigurable Atom Arrays, arXiv:2308.08648 [quant-ph]

§ A TENSOR PRODUCT MERGE WHICH LOWERS THE DISTANCE

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

and thus $(C \otimes D)_\bullet$, we can construct the reduced merged complex of a pairwise merge, performing a $\overline{Z}$-merge using the operator

\[c\otimes d = \begin{pmatrix}1\\0\\0\\0\\0\end{pmatrix} \otimes \begin{pmatrix}1\\1\\1\\1\\0\end{pmatrix} \in C_0\otimes D_1\]

where $d \in \ker(B)$, $c \in C_0 \backslash \im(A)$.
This is

\[M_\bullet^{\rm red}= \begin{tikzcd} \F_2^4\otimes \F_2^5 \oplus \F_2^4 \arrow[r, "\del_1^{\rm red}"] & \F_2^5\otimes \F_2^5 \oplus \F_2^4\otimes \F_2^4 \oplus \F_2^4 \arrow[r, "\del_0^{\rm red}"] & \F_2^5\otimes \F_2^4\end{tikzcd}
\]

\[ \cong \begin{tikzcd} \F_2^{24} \arrow[r, "\del_1^{\rm red}"] & \F_2^{45} \arrow[r, "\del_0^{\rm red}"] & \F_2^{20}\end{tikzcd}\]

\[\del_1^{\rm red} = \begin{pmatrix}
\id_5 & 0 & 0 & \id_5 & L'\\
\id_5 & \id_5 & 0 & 0 & 0 \\
0 & \id_5 & \id_5 & 0 & 0 \\
0 & 0 & \id_5 & \id_5 & 0 \\
0 & 0 & \id_5 & 0 & 0 \\
B & 0 & 0 & 0 & 0\\
0 & B & 0 & 0 & 0\\
0 & 0 & B & 0 & 0\\
0 & 0 & 0 & B & 0\\
0 & 0 & 0 & 0 & J'
\end{pmatrix}; \quad
\del_0^{\rm red} = \begin{pmatrix}
B & 0 & 0 & 0 & 0 & \id_4 & 0 & 0 & \id_4 & K'\\
0 & B & 0 & 0 & 0 & \id_4 & \id_4 & 0 & 0 & 0\\
0 & 0 & B & 0 & 0 & 0 & \id_4 & \id_4 & 0 & 0\\
0 & 0 & 0 & B & 0 & 0 & 0 & \id_4 & \id_4 & 0\\
0 & 0 & 0 & 0 & B & 0 & 0 & \id_4 & 0 & 0
\end{pmatrix}\]

\[L' = \begin{pmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 0 & 0
\end{pmatrix}; \quad J' = \begin{pmatrix}
1 & 1 & 0 & 0\\
0 & 1 & 1 & 0\\
0 & 0 & 1 & 1\\
1 & 0 & 0 & 1
\end{pmatrix}; \quad K' = \id_4.\]

The vector $w = 1_{5}1_{44}$, that is with a 1 at entries 5 and 44 and 0 elsewhere, is in $\ker(\del_0^{\rm red})\backslash \im(\del_1^{\rm red})$. This vector has $|w| = 2 < \frac{5}{2} = \frac{1}{2}(d + l)$, so the merged code has lower distance than the codes pre-merge.