Long-range  data transmission in

a fault-tolerant quantum bus architecture
1,2]Shin Ho Choe
1,2]Robert König
[1]Department of Mathematics, Technical University of Munich
[2]Munich Center for Quantum Science and Technology (MCQST), Munich, Germany

We propose a scheme for fault-tolerant  long-range entanglement generation at the ends of a rectangular array of qubits of length $R$ and a square cross section of size $d\times d$ with $d=O(\log R)$.
Up to an efficiently computable  Pauli correction, the scheme generates a maximally entangled state of two qubits using a depth-$6$  circuit consisting of nearest-neighbor Clifford gates and local measurements only. Compared with  existing fault-tolerance schemes for quantum communication, the protocol is distinguished by its low latency:  starting from a product state, the entangled state is prepared in a time $O(t_{\textrm{local}})$ determined only by the local gate and measurement operation time $t_{\textrm{local}}$. Furthermore, the requirements on local repeater stations are minimal: Each repeater uses only $\Theta(\log^2 R)$ qubits  with
a lifetime of order $O(t_{\textrm{local}})$.
We prove a converse bound $\Omega(\log R)$ on the number of qubits per repeater among all low-latency schemes for fault-tolerant  quantum communication over distance $R$. Furthermore, all operations
within a repeater are local when the qubits are arranged in a square lattice.

The noise-resilience of our scheme relies on the fault-tolerance properties of the underlying cluster state. We give a full error analysis, establishing a fault-tolerance threshold against   general (circuit-level) local stochastic noise affecting preparation, entangling operations and measurements. This includes, in particular, errors  correlated in time and space. Our conservative analytical estimates are surprisingly optimistic, suggesting that the scheme is  suited for long-range entanglement generation both in and between near-term quantum computing devices.

§ INTRODUCTION

The ability of operating on spatially separated qubits has been recognized early on as a key requirement for a working quantum computer [12, 47]. Long-range quantum communication is also a fundamental primitive at the core of quantum information-theoretic [22, 28, 54] and cryptographic [3, 21]
protocols in quantum networks, as well as e.g., distributed quantum computation [7, 36, 49] or distributed sensing [29, 16]. With increasingly powerful capabilities of present-day devices that can act as local nodes in such a network, finding appropriate protocols for entanglement sharing and quantum communication  over faulty networks remains an active and central theme of present-day research.

The nature of the best protocol to be used depends heavily
on the available hardware and its noise characteristics. Here we consider a monolithic architecture for point-to-point communication in a quasi-1D array of qubits. In terms of more standard terminology in quantum communication, this scheme can be interpreted as consisting of a line of repeater stations. Our proposal  addresses the specific constraints on near-term devices by optimizing the following aspects:

* minimal number of qubits per repeater station:
As a function of the total communication distance $R$, every repeater  only needs to manipulate $O(\log^2 R)$ number of qubits. This is in line with the best  currently known proposals for long-range quantum communication. We also provide a converse bound $\Omega(\log R)$ on the number of qubits per repeater for low-latency protocols as considered in this work.

* short coherence times: The required coherence time of each qubit  is independent of the overall communication distance $R$: It only needs to be of the order of the local  operation time $t_{\textrm{local}}$.  This is the maximal time
needed to perform a single- or two-qubit gate, a single-qubit measurement, or an entangling gate between two neighboring repeaters.

* simplicity of involved operations: Our scheme only involves one- and two-qubit gates between nearest-neighbor qubits in the architecture. In particular, assuming the repeater stations are connected appropriately, all operations at each repeater  are geometrically local when the qubits are arranged on a 2D array. This makes the scheme particularly attractive for, e.g., planar chip-like devices where the connectivity to neighboring devices is established through the third dimension.

Because of the simplicity of the scheme, we can explicitly specify and analyze all involved operations without resorting to fault-tolerant  gadgets (e.g., for encoding and recovery) that are often
treated in a black-box manner. In particular, this means that we can provide a stringent error analysis for fully general circuit-level noise.

* resilience to general errors: we provide a rigorous proof of the robustness of our scheme in the form of a fault-tolerance threshold theorem  allowing for general local stochastic noise. This models not only the commonly studied situation where qubits are depolarized according to identically and independently distributed errors (i.e., product channels), but also captures situations where errors are correlated both in space and time. We assume all involved operations (state preparation, gates and measurements)  to be non-ideal, i.e., affected by noise.

* minimal latency:  Our protocol minimizes the “time to entanglement” $T_{\textrm{ent}}$, the amount of time it takes to establish long-range entanglement from a product state of all qubits. The long-range entangled state is  available after a  time of order $T_{\textrm{ent}}=O(t_{\textrm{local}})$.
In contrast, the quantity $T_{\textrm{ent}}$ scales at least linearly with the total communication distance $R$  in several existing protocols based, e.g., on transmitting encoded information successively between neighboring repeaters.

We note that some of these protocols
reach the scaling $O(t_{\textrm{local}})$ per generated Bell pair asymptotically  when operated continuously, i.e.,
this is an achievable  rate of communication. In contrast, the quantity $T_{\textrm{ent}}$ measures the latency when starting to run the scheme, and may be particularly relevant in near-term applications in scenarios where continuous operation is challenging.

We note that our analysis treats Pauli errors and erasure errors on the same footing (similar to e.g., Refs. [42])  leading to a fault-tolerance threshold for situations where the noise strength of both of these types of noise is of the same order of magitude. Future work may examine using modified decoders [9] exploiting the high loss tolerance of topological codes [2]; indeed, we expect these schemes to be resilient to loss errors with a probability of occurrence closer to the percolation threshold of the square lattice, i.e., much higher than the thresholds we establish for local stochastic Pauli noise.

Because of the simplicity of the involved operations, our scheme is a candidate  architecture for transferring quantum information  between  as well as within quantum devices. That is, it can act as a data bus which can exchange information between various components as first studied in [5]. Because it prepares a Bell pair up to an (efficiently computable) Pauli error, it is compatible with e.g., magic-state injection methods to achieve universality: corrections can be propagated “in software”, i.e., by commuting Pauli operators through a stabilizer circuit without the need for physically applying a correction before proceeding with the computation.

In the area of quantum computing architectures, our protocol could be especially beneficial in settings where gates or measurements need to performed between spatially distant qubits. Such a need arises for example when using a quantum low-density parity check (LDPC) code whose stabilizer generators are not spatially local. With our scheme, we can  design a quasi-2D architecture that allows for the application of joint measurements on any subset of size $\ell=O(1)$ of a total of $n$ qubits, see Fig. <ref>.  Each such $\ell$-qubit measurement is executed with constant fidelity in a constant amount of time (up to Pauli correction whose classical postprocessing can typically be deferred to a later stage). The architecture requires $O(n \cdot \mathsf{polylog}(n))$ qubits in total. When combined with the recently discovered good quantum LDPC codes that have parameters close to optimal [44], this logarithmic overhead unfortunately  only leads to an encoding rate that decays as an inverse polylogarithmic function. In the near term, however, this still beats  e.g.,  surface-code based approaches [8, 32] that have an inverse polynomial encoding rate, although the latter have the advantage of being strictly 2D and not quasi-2D as our scheme.

A quasi-2D network of quantum buses. This architecture allows to perform a joint measurement on any subset of $\ell$ qubits (illustrated here for $\ell=3$) with constant fidelity by “busing" the corresponding qubits to the same location before the measurement, and subsequently transferring the qubits  back.
The transfer is achieved by teleporting the qubits using the long-range entanglement established with our protocol on each bus.

§.§.§ Prior work on entanglement generation from cluster states

Our work builds on the fault-tolerance properties of the 3D cluster state. In seminal work [48], Raussendorf, Bravyi and Harrington proved that  for temperatures below some threshold, the thermal state of the cluster state Hamiltonian on a simple 3D cubic lattice has localizable entanglement: applying single-qubit Pauli measurements
to each “bulk” qubit  results – up to Pauli corrections determined by the measurement outcomes  – in an encoded Bell state
of 2D surface codes lying on two opposing faces of the cube.  Since the initial thermal state is the cluster state with independent  and identically distributed Pauli-$Z$-errors on each qubit, and the cluster state can be created in constant depth with local operations, this provides a scheme for long-range (encoded) entanglement generation by a constant-depth circuit with local gates. While the assumed (physically motivated) noise model is somewhat restricted, the authors of [48] also point out that more general errors on the initial cluster state such as independent single-qubit depolarizing noise can be tolerated when using ideal (non-faulty) operations at the two surfaces.

Entanglement generation in a cubic lattice can indeed be achieved under more general noise:  As shown in [4], the Raussendorf-Bravyi-Harrington scheme produces a logical  Bell pair even under general local stochastic noise below some threshold. Local stochastic errors model general circuit-level Pauli noise that can include correlations in time and space. As a special case, this encompasses
independent and identically distributed (i.i.d.) Pauli noise on the initial cluster state, as well as e.g., measurement errors. We discuss this error model  and  the exact statement of [4] below. It shows that under local stochastic noise, it is possible to generate an encoded Bell pair which is corrupted by a residual local stochastic error. The latter can be  corrected by surface-code decoding.

The scheme of [48]  produces a surface-code encoded Bell pair, i.e., the resulting entanglement lives in a logical $2$-qubit subspace of a many-qubit system. In applications such as the one considered in [4], this is a desirable feature: the encoded information can be operated on without decoding, thus  preserving fault-tolerance properties. In a communication scenario, however, it may be more desirable to establish entanglement between two physical qubits instead. A scheme for achieving this kind of localization of the entanglement was  proposed in [45] by modifying the approach of [48]: Here a different single-qubit measurement pattern is used at the two (“surface code”) boundaries. This results in entanglement between two distinguished qubits in each surface. For the problem of establishing a constant-fidelity Bell pair in a cube of size $R\times R\times R$, the work [45] provides analytical and numerical threshold estimates in the case of i.i.d. Pauli-$X$ and Pauli-$Z$ errors in the cluster state. (It was argued in [45] that this error model captures a situation where initially, independent noisy Bell states are shared along each edge of the cubic lattice, and all subsequent (single-qubit) operations are ideal, i.e., noise-free.) In particular, it is shown that there is a threshold error rate such that constant-fidelity two-qubit entanglement (i.e., independent of $R$) is established for any error rate below that threshold.

To achieve long-distance communication, one can use cluster states on lattices of the form $d\times d\times R$ with $R\gg d$, i.e., lattices that  are elongated in the direction where quantum information is to be transferred. In this work, we denote a lattice of such form by $\cC[d \times d \times R]$, see Section <ref> for a detailed definition. The corresponding setup is quasi-1D, with $O(d^2)$ qubits arranged on a square on each “slice” along this direction. This idea has been explored numerically in the case of i.i.d. Pauli-$Z$ noise in [48]. For sufficiently small error rates, a fidelity of the encoded (error corrected) scaling as
$F\sim \exp\left(-R\kappa_1\exp(-d\kappa_2)\right)$ for some constants $\kappa_1,\kappa_2>0$ was observed. These simulations were carried out for period boundary conditions. Assuming the surface codes have similar behavior as toric codes away from the threshold, this implies that using $d=\Omega(\log R)$ (i.e., a polylogarithmic number $n=O(d^2)$ of qubits per repeater station) is sufficient to achieve constant fidelity over a distance $R$. In a similar vein, the results of [45] are stated for cubes (i.e., lattices of the form $R\times R\times R$), but the author suggests using lattices of the form $d\times d\times R$ with $d=\Theta(\log R)$.  Here we establish rigorous bounds on the fault-tolerance threshold for this scenario for a more general noise model.

§.§.§ Surface codes for communication and as topological quantum memories

Our work is closely related to [45]: indeed, the cluster state and measurement pattern used in our scheme is identical to that of [45].  As we explain below, this measurement strategy and the associated correction operation can be interpreted as a fault-tolerant single-shot decoding procedure for the surface code.
In fact, the corresponding  measurement pattern for the surface code has also previously been used in [33] to realize a fault-tolerant $T$-measurement. A similar  triangular pattern has been applied in Refs. [35, 34] for encoding, i.e., state preparation, for the surface code, and more specifically, for injecting  a magic state into the surface code [31].

Surface codes have found many uses  in  information-processing and communication settings. While some of these proposals are superficially similar to our work, they typically have different objectives. In particular, they often involve operations over an extensive amount of time, preventing realization by a constant-depth circuit:  Consider  first the fault-tolerant encoding/decoding scheme for the 2D surface code studied in [34]. This scheme establishes entanglement in time, i.e., gives a complete prescription (including preparation and readout) of how the surface code can be used to preserve quantum information. Similar to the seminal  work [10] showing that the surface code can be used as a quantum memory  even with noisy syndrome measurements, this leads to a matching problem on a 3D lattice in spacetime. This is conceptually different from our procedure: Our decoding procedure involves a “spacelike” 3D lattice, and the entire process is achieved in a constant  time. (Ref. [34] also gives a lower bound on the achievable fidelity in terms of “circuit volume” when using concatenated codes. The non-locality and complexity of the involved operations is mentioned as a challenge.)

The proposal of [19] also relies on surface codes: Several corresponding code patches are placed  next to each other along the communication direction and an encoded qubit is teleported through this architecture. Similar to a topological quantum memory with noisy syndrome measurements, the scheme relies on interaction and measurement patterns
that are repeated a number of times scaling linearly with the code distance.

§.§.§ Local stochastic noise and Clifford circuits

We consider quantum circuits subject to local stochastic noise. This is a general notion of errors introduced in [23]
to model situations where the noise is “locally decaying” but otherwise arbitrary. In particular, this model includes
not only i.i.d. noise on each qubit, but also adversarial settings where errors can have unspecified correlations both in space and time (i.e., at different circuit locations).

Here we follow the formalism used in [17]. When implementing an ideal circuit under local stochastic noise,
all qubits experience  a random Pauli error  at each time step (gate layer) of the circuit. The only assumption we make is that high-weight errors are exponentially suppressed as quantified by a parameter $p\in [0,1]$ called the noise strength. To be specific, consider a quantum circuit using $n$ qubits.
A Pauli error $E$ is a  random variables on the $n$-qubit Pauli group. Its support $\supp(E)\subseteq [n]$ is the (random) subset of qubits it acts on non-trivially, i.e., with either $X$, $Y$, or $Z$. We call a Pauli error $E$ a local stochastic error with strength $p\in [0,1]$, written $E\sim\cN(p)$, if  any subset of $k$ qubits is affected by $E$ with probability at most $p^k$, i.e., if

\begin{align}\label{eq:introlocalstochasticnoisecondition}
\Pr\left[F\subseteq\supp(E)\right]&\leq p^{|F|}\qquad\textrm{ for any subset }\qquad F\subseteq [n]\ .
\end{align}

Consider an ideal depth-$d$ circuit that starts in a product state $\ket{0^n}:=\ket{0}^{\otimes n}$ of $n$ qubits, applies a

\begin{align}
U=U_d\cdots U_1
\end{align}

consisting of $d$ gate layers $U_j$ (each of which is a depth-$1$ circuit consisting of one- and two-qubit gates) and subsequently measures a subset of the qubits in the computational basis. We call a noisy execution of this circuit with parameter $p$
the same kind of process, but with $U$ replaced by

\begin{align}
U_{\textrm{noisy}}&=E_{d+1}E_{d}U_d\cdots E_2 U_2 E_1 U_1E_0\  ,\label{eq:noisycircuitrealizationex}
\end{align}

where each error

\begin{align}
E_j\sim \cN(p)\qquad\textrm{ for  }\qquad j\in \{0,\ldots,d+1\} \label{eq:localerrorassumptiondem}
\end{align}

is a local stochastic error with strength $p$. This models both preparation errors (described by $E_0$), gate execution errors (described by $E_j$ for $j=1,\ldots,d$) and measurement errors, i.e., bit flips in the measurement outcome (described by $E_{d+1}$). Importantly, the random variables $\{E_j\}_{j=0}^{d+1}$ need not be independent, capturing situations where errors are correlated in time. Indeed, condition (<ref>) merely imposes constraints on the marginal distributions of the errors $\{E_j\}_{j=0}^{d+1}$.

Put succintly, the goal of fault-tolerance is to design an ideal circuit in such a way that any noisy implementation of the circuit  still realizes the desired functionality, assuming that
the error strength $p$ is below some threshold. The noise model considered here makes the corresponding analysis  tractable when working with Clifford circuits: Any local stochastic error can be commuted forward or backward (in time) through  such a circuit while preserving the property of being a local stochastic error. In addition, products of local stochastic errors are themselves local stochastic errors, meaning that errors can be accumulated, i.e., combined into a single local stochastic error. These manipulations change the error strength. More precisely, it is possible to establish conservative upper bounds on the error strength of the resulting error, see <cit.> for a formal statement of this calculus of local stochastic errors. Importantly, however, these manipulations do not change the nature of the errors: This is  because of the minimal assumptions used in the definition of local stochastic noise.

We note that the practice of commuting Pauli errors forward or backward through a circuit composed of Clifford gates is common throughout the literature. However, in some  earlier work on quantum repeaters,
the fact that such operations may introduce correlations between errors  when starting from an i.i.d. error model is sometimes neglected. The concept of local stochastic errors and the corresponding calculus elegantly sidesteps this difficulty: For any Clifford circuit
of constant depth $d$, it is sufficient to establish resilience against a single local stochastic error at any time step $t\in\{0,\ldots,d+1\}$ in the circuit, rather than considering the $d+1$-tuple $(E_0,\ldots,E_{d+1})$: Indeed, any noisy circuit (<ref>)  behaves identically to a circuit of the form

\begin{align}
U_{\textrm{noisy}}&=U_d\cdots U_{t+1} E U_t\cdots U_1 \  ,\label{eq:noisycircuitrealizationexcommuted}
\end{align}

with a certain local stochastic error $E\sim\cN(p^{O(1)})$.  A corresponding  upper bound on the error strength follows by applying commutation relations and combining errors according to rules such as those given in <cit.>.

§.§.§ Single-shot encoded Bell state preparation and surface code readout

To exemplify this line of reasoning, consider the (ideal) circuit studied [4]. Starting from a product state $\ket{0^n}$, it applies a
depth-$6$ circuit $W$ with nearest-neighbor Clifford gates  to prepare the cluster state $W\ket{0^n}$ on a lattice $\cC[d\times d\times d]$. Subsequently, a subset $\cA$ of qubits is measured in the computational basis, yielding an outcome (string $s$). Up to a Pauli correction $\mathsf{Rec}(s)$ determined by the measurement outcome $s$, this circuit prepares logical Bell state $\overline{\Phi}$ encoded in two surface codes on the two boundaries of the lattice, that is, we have

\begin{align}
\mathsf{Rec}(s)(\bra{s}_{\cA}\otimes I_{\cA^c})W\ket{0^n}&\propto\ket{\overline{\Phi}}\ .
\end{align}

Now consider a noisy execution of this circuit. There are three sources of error: Errors in the preparation of the initial state $\ket{0^n}$, errors during the execution of the circuit $W$, and errors affecting the single-qubit measurements.  The former two types of errors can be commuted forward in time past the last gate layer of $W$.  Measurement errors (where an error on a single qubit measurement corresponds to a Pauli-$X$-error before application of the ideal measurement) can be commuted backwards in time. Combining the commuted versions of these errors, it thus suffices to consider the case where  a single local stochastic error $E$ is applied after the execution of $W$. All other operations may be assumed to be ideal, i.e., noise-free: The overall process is equivalent to  measuring (using an error-free measurement) a noisy cluster state $EW\ket{0^n}$, corrupted by a local stochastic error $E$.

What does a noisy execution of the circuit achieve? It turns out that the procedure still prepares the logical Bell state $\overline{\Phi}$ up to the known Pauli correction $\mathsf{Rec}(s)$ (depending on the measurement result $s$) and an additional residual error $\mathsf{Rep}(E)$ (depending on the local stochastic error $E$). The main technical result established in [4] for this “single-shot preparation procedure” shows that this residual error itself is local stochastic, and its error strength can be related to the error strength $p$ of the original local stochastic error $E\sim\cN(p)$. Let us state the corresponding result since it motivates our construction.

Suppose $d\geq 4$. Then there is a threshold probability $p_0$ such that the following holds: Let $\cC[d\times d\times d]$ be the cubic lattice of linear size $2d-1$ with one qubit per site. Let  $E\sim\cN(p)$ be a local stochastic error with error strength $p<p_0$.
Then there is a local stochastic error $\mathsf{Rep}(E)$ with

\begin{align}
\mathsf{Rep}(E) \sim \cN(11p^{1/128})\ \label{eq:problRepE}
\end{align}

such that

\begin{align}
\mathsf{Rep}(E)\mathsf{Rec}(s)(\bra{s}_\cA\otimes I_{\cA^c})EW\ket{0^n}\propto \overline{\Phi}_{\cA^{c}}\
\end{align}

with certainty, where the probability is taken over the choice of $E$ and the syndrome (measurement result) $s$.

We note that Theorem <ref>  primarily constitutes   a proof-of-principle, giving a precise formulation of the idea that the final state is the encoded Bell state up to a locally decaying error. Both the threshold error strength obtained, as well as  the exponent in (<ref>) are likely to be more conservative bounds than necessary in reality, and are expected to be too demanding for experimentally relevant parameters ranges. Nevertheless, Theorem <ref> shows that the single-shot encoded Bell state preparation procedure can be combined with suitable surface code protocols that are resilient to local stochastic errors. Indeed, this is the way the cluster state is used in the application of [4] and follow-up work [25, 37].

One such noise-resilient surface code protocol is the single-shot decoding protocol discussed in [4].  It shows that measurement of the logical Pauli-$\overline{Z}$ operator in the surface code can be achieved fault-tolerantly by local operations even in the presence of local stochastic noise. Let us paraphrase the corresponding statement here.

Consider a surface code of distance $d\geq 7$
with $n=2d^2-2d+1$ qubits.
Let $E\sim \cN(q)$ be a local stochastic error with strength $q\leq 0.01$. Then there is a function $\mathsf{Dec}:\{0,1\}^n\rightarrow\{0,1\}$ such  that the following holds. Let $\overline{\Psi}$ be an arbitrary encoded state. Assume we measure every qubit of the state $E\overline{\Psi}$ in the computational basis obtaining the outcome $x\in \{0,1\}^n$.

\begin{align}
\left|
\Pr_{E,x}\left[
\right]- p_{\overline{Z}}(\overline{\Psi})
\right| &\leq 3 \exp(-0.2d)
\end{align}

\begin{align}
p_{\overline{Z}}(\overline{\Psi})&:=\frac{1}{2}\left(1+\bra{\overline{\Psi}}\overline{Z}\ket{\overline{\Psi}}\right)\ .
\end{align}

(We note that without loss of generality, the error $E$ can be assumed to be consisting of Pauli-$X$ operators only.)

Since $p_{\overline{Z}}(\overline{\Psi})$ is the probability of observing the outcome $+1$ when measuring the logical $\overline{Z}$-operator, Theorem <ref>  provides a way of fault-tolerantly performing a measurement of this operator. While we do not  directly use this result, it is part of the motivation for our single-shot decoding procedure and its analysis.

§.§.§ Prior work on quantum repeaters

A comparative study of different approaches to long distance quantum communication is provided in [42] where the authors discuss three generations of quantum repeater protocols:

The first generation of quantum repeaters  is based on heralded entanglement generation between neighboring stations or repeaters (where entanglement is generated using post-selection on suitable measurement outcomes) combined with heralded entanglement purification (where multiple imperfect Bell pairs are used to probabilistically produce higher-fidelity Bell pairs) [6, 51]. These steps are repeated recursively at different distance scales. First-generation protocols of this kind
require at a number of qubits polynomial in the total communication distance $R$ at each repeater station. The rate (i.e., number of Bell pairs established per channel use) is an inverse polynomial in $R$, and the total time per Bell pair is given determined by $\max\{R/c,t_0\}$, where $t_0$ is the gate time and $c$ the speed of light (corresponding to classical data transfer).

Second-generation protocols make use of heralded entanglement generation to counteract loss errors, and use  quantum error-correcting codes to deal with operation errors: long-range encoded entanglement is generated by (encoded) entanglement swapping [27, 39, 55]. This leads to a reduction in classical two-way communication previously required in the entanglement purification step. The communication rate is improved to an inverse polylogarithmic function of $R$, whereas the overall time-scale still scales as $\max\{R/c,t_0\}$.

Protocols of the third generation use quantum error correcting codes   to address not only operation errors, but also qubit loss [19, 41, 43, 40]. This family of protocols
proceeds by communicating encoded quantum information: Repeaters apply a recovery operation to each codeblock before retransmitting the entire block to the next repeater.
Because this family of protocols can be realized using one-way communication only, it requires little time per transmitted qubit: The time taken per transmitted qubit is  only limited by $O(t_0)$, where $t_0$ is the local gate operation time.     This advantage comes at the cost of requiring relatively high-fidelity quantum gates to realize the error correction operation at each repeater. The achieved rate in this generation of protocols is an inverse polylogarithmic function of $R$.

Our work is a close relative to these third-generation protocols: indeed, one interpretation  of the corresponding architecture is that it encodes logical information into a surface code at each repeater station. We emphasize, however, that this only motivates the scheme similar to the way e.g., cluster-state measurement-based quantum computation is related to braiding surface code anyons. For example, the scheme does not involve intermediate encoding/recovery operations associated with these surface codes.

Purely error-correction based schemes such as those of the third generation have a loss-tolerance limited by 50% because of the no-cloning theorem.  To sidestep this limitation, the more recent work [56] combines error correction with hashing-based entanglement purification. In this scheme, intermediate error correction operations are realized based on stabilizer (resource) states prepared at each repeater. The proposed scheme achieves a constant rate of qubit transmission. Here error correction is based on measurement-based gate teleportation using special (graph)  states encoding the recovery map at each repeater location.
While such schemes are ultimately desirable, the generation of these resource states is arguably more challenging to realize with near-term devices than the protocol discussed here.

§ OUR CONTRIBUTION: MAIN IDEAS AND RESULTS

§.§.§ A threshold theorem for long-range entanglement generation

In this work, we present a protocol for generating a long-range entangled two-qubit Bell state in a fault-tolerant manner in the presence of local stochastic noise. It is based on a 3D cluster state on a lattice of the form $d\times d\times R$, see Fig. <ref>.

A cluster state on the lattice $\cC[d\times d \times R]$ with $R \gg d$. Each sphere represents a qubit. Also indicated is the measurement pattern used in our protocol, consisting of single-qubit Pauli-$X$ and Pauli-$Z$ measurement. Entanglement is established between qubits $q_1$ and $q_2$.

To state our main result, we use the following notations: We let $\cC$ denote the set of qubits  on the cluster state lattice $\cC[d\times d\times R]$. For a subset $\Omega\subseteq \cC$, we write
$\ket{0^\Omega}=\bigotimes_{c\in\Omega}\ket{0}_c$ for the all-zero basis state on the qubits $\Omega$. Similarly, we write $H(\Omega):=\prod_{c\in\Omega} H_c$ for the product of single-qubit Hadamard operators on each qubit of $\Omega$. When measuring a subset $\Omega$ in the computational basis, we denote the measurement result by $s\in \{0,1\}^{\Omega}$, where  $s=(s_c)_{c\in\Omega}$ consists of one measurement outcome bit $s_c$ associated with each qubit $c\in\cC$. The standard two-qubit Bell state is denoted

\begin{align}
\ket{\Phi}=\frac{1}{\sqrt{2}} \left(\ket{00}+\ket{11}\right)\ ,
\end{align}

and the two-qubit Bell basis $\{\Phi_{(\alpha,\beta)}\}_{(\alpha,\beta)\in\{0,1\}^2}$ consists of the Bell states

\begin{align}
\Phi_{(\alpha,\beta)}&=(I\otimes Z^{\alpha}X^{\beta})\Phi\ .\label{eq:defbellstate}
\end{align}

Our main result is the following fault-tolerance threshold theorem:

Let $d\in\mathbb{N}$ with $d\geq 3$ and  $R \in \mathbb{N}$ be odd with $R \geq 3$.
Assume that

\begin{align}
R\leq  \frac{1}{d} \left(\frac{1}{10\sqrt{p}}\right)^{d-2} \ .\label{eq:Rupperboundmscaling}
\end{align}

There is a partition

\begin{align}
\cC=\cX\cup\cZ \cup \{q_1,q_2\}
\end{align}

of the set of qubits $\cC=\cC[d\times d\times R]$ into disjoint sets $\cX$, $\cZ$ and a set $\{q_1,q_2\}$ consisting of two qubits located at opposite ends of $\cC$, with coordinates $u_3=1$ and $u_3=R$, respectively, as well as two  efficiently computable functions

\begin{align}
\begin{matrix}
\alpha: & \{0,1\}^{\cC\backslash \{q_1,q_2\}} & \rightarrow &\{0,1\}\\
\beta: & \{0,1\}^{\cC\backslash \{q_1,q_2\}} & \rightarrow &\{0,1\}
\end{matrix}
\end{align}

such that the following holds. Consider the following protocol:

Prepare the cluster state $W_{\cC}\ket{0^\cC}$
by applying the local  depth-$6$ Clifford circuit $W_{\cC}$
to qubits associated with the cluster state lattice $\cC=\cC[d\times d\times R]$.

* Measure each qubit except the two  distinguished qubits $q_1,q_2$ according to the following pattern:

* Each qubit $c\in\cX$ is measured in the Hadamard basis

* Each qubit $c\in \cZ$ is measured in the computational basis.

Let $s\in \{0,1\}^{\cC\backslash \{q_1,q_2\}}$ be the (collection)  of measurement outcomes.
Assume that the state after step (<ref>) is corrupted by a local stochastic error $E\sim\cN(p)$ of strength

\begin{align}
p\leq \frac{1}{5006}\approx 2\times 10^{-4}\ .
\end{align}

\begin{align}
\psi_E(s)\propto (I_{q_1,q_2}\otimes \bra{s}H(\cX)) EW_\cC\ket{0^\cC}
\end{align}

be the post-measurement state on qubits $\{q_1,q_2\}$. Then  the post-measurement state on qubits $q_1,q_2$ is the Bell basis state $\Phi_{(\alpha(s), \beta(s))}$
with probability at  least

\begin{align}
\Pr_{E,s}\left[\psi_E(s)\propto \Phi_{(\alpha(s),\beta(s))}\right]&\geq 1- 5006p\ .
\end{align}

Recall that the cluster state lattice $\cC[d\times d\times R]$
has $m=2d^2-2d+1$ qubits
in each “sheet” (with fixed coordinate $u_3$) along the communication direction. This is the number of qubits that our protocol uses at each repeater station.
Eq. (<ref>) thus implies that, to produce constant-fidelity two-qubit entanglement (under constant-strength noise), our protocol uses $d=\Theta(\log R)$ or
\begin{align}
m&=\Theta\left( \log^2 R\right)\ . \label{eq:polylogscalingexplicitprotocol}
\end{align}

That is, the number $m$ of qubits per repeater station is polylogarithmic in the communication distance $R$ for our protocol.
We give a converse bound, see Theorem <ref> below.

The functions $\alpha$ and $\beta$ involve solving minimum matching problems on certain sublattices of $\cC$. With Edmond's algorithm [14, 30, 20, 53],
they can be evaluated in a time $O(d^6 \cdot R^3)$. In the context of surface code decoding, it has been shown that parallel processing leads to a polylogarithmic runtime instead [13, 11]. We expect that similar approaches are applicable here.

Our scheme  is essentially identical to the procedure of [45], but constructed in a modular manner: We introduce a new primitive we call single-shot decoding of surface codes. Combining this with the Raussendorf, Bravyi and Harrington-scheme [48], i.e., applying single-shot decoding to each of the two surface codes yields our scheme. Our work thus gives a reinterpretation of the scheme [45] along with a more general error analysis.

§.§.§ Optimality: A converse to the threshold theorem

We study to which extent the protocol provided by Theorem <ref> is optimal among protocols  with low latency, i.e., where the entanglement is created after a constant amount of time (modulo local correction operations).
Specifically, we consider protocols that are given by constant-depth quantum circuits, and ask if the relationship between the number $m$ of qubits at each repeater station and the communication distance $R$
can be better than polylogarithmic (cf. (<ref>)). We find that this is not the case, i.e., the  scaling of our protocol is essentially optimal.

The class of protocols we consider are given by constant-depth circuits. A depth-$\Delta$ circuit for entanglement generation

* starts with a product state among all qubits, where each repeater (site) has $m$ qubits,

* applies a depth-$\Delta$ circuit consisting of single-qubit measurements, single-qubit gates and two-qubit gates between qubits at a repeater (site) and/or between nearest-neighbor sites. Constant-depth here means that $\Delta$ is a constant (independent of $R$).

* returns a state on two qubits $\{q_1,q_2\}$ located at the two ends of the communication line at distance $R$. This state is supposed to be the  Bell state $\Phi$  up to a local (i.e., tensor product) correction that can be computed from the measurement outcomes.

We allow for adaptivity, i.e., unitaries can be classically controlled by measurement outcomes obtained during the execution of the circuit. Our  main no-go result applies to all such protocols irrespective of whether or not the classical computations determining these adaptive actions are efficient.

Our protocol is of this kind (for qubits arranged on the cluster lattice $\cC[d\times d\times R]$). Also of this kind are protocols proposed in the seminal work [1] on “entanglement percolation”. The work [1] considers a unitary error model where  the
resource state has a non-maximally entangled Bell state on each link. In addition to proposing protocols for this setting for 2D networks, it is shown in [1] that for a 1D chain of qubits, long-distance entanglement cannot be created by any single-shot protocol: Assuming any constant error per link, the fidelity of the resulting Bell state decays exponentially with distance.

We prove a converse to our “achievability” Theorem <ref>.  It generalizes the statement of [1] to a setting where instead of a  single (pair) of qubits per site (along the communication line), each site can have a polylogarithmic number of qubits. In addition, we allow constant-depth circuits instead of local measurements only. We find a local stochastic error of constant strength which leads any such protocol to fail if the communication distance $R$ is too large compared to the number $m$ of bits at each repeater station. That is, we show the following, see Corollary <ref> for a detailed version of this bound.

Let $\pi$ be a protocol for long-range entanglement generation over distance $R$ which

* uses $m$ qubits per repeater,

* is realized by a constant-depth (adaptive) circuit

* is resilient to arbitrary local-stochastic noise of strength $p$ below a constant threshold $p_0$, i.e., produces a constant-fidelity Bell pair.

Then we must have

\begin{align}
m&=\Omega\left(\log R\right)\ .\label{eq:mlowerboundgeneral}
\end{align}

The proof of  Theorem <ref> replaces the analysis of a low-latency protocol $\pi$ by that of an entanglement-assisted  protocol $\pi'$, and  follows from the fact that for any $p\in (0,1)$,  the qubit depolarizing channel $\cE_p(\rho)=(1-p)\rho+p \tr(\rho)\frac{I}{2}$
is a convex combination of an entanglement-breaking channel [26] and the identity channel (see Section <ref> for details). It implies that local stochastic noise with any constant noise strength prevents entanglement generation over distances greater than exponential in the number of qubits at each site. In particular, it shows that the protocol discussed in Theorem <ref> is essentially optimal
among all low-latency protocols:  Comparing (<ref>) with (<ref>), we conclude that
the polylogarithmic scaling of the number $m$ of qubits per site in the protocol of Theorem <ref> can at best be improved to a logarithmic scaling in $R$.

Closing the log-factor gap between  the converse Theorem <ref> and achievability  Theorem <ref> appears to require a new approach, however: We can show that the analysis of Theorem <ref> leading to the scaling (<ref>) is tight. In fact, the scaling is necessary for any procedure which is based on the cluster state and uses the same syndrome information using  functions $\alpha$ and $\beta$ as in our protocol: We show the lower bound

\begin{align}
m=\Omega(\log^2 R)
\end{align}

for any such protocol (see Theorem <ref> for a detailed statement). This result is obtained by a detailed analysis of the associated decoding problem, see Section <ref>. It applies, in particular, to natural variants of our scheme that are obtained, e.g., by replacing Edmond's minimal matching algorithm by other procedures, including heuristic algorithms.
This indicates that improving  over our protocol will require a different resource state or measurement pattern.

§.§.§ Combining cluster-state generation and single-shot decoding

Let us briefly discuss the main ideas underlying our work, giving a high-level overview focused on the two main building blocks:

The generation of a cluster state on an elongated lattice $\cC[d\times d\times R]$  and subsequent single-qubit measurement of “bulk” qubits located at sites not belonging to the two boundaries with third coordinate equal to $x_3=1$ and $x_3=R$, respectively. Up to local unitaries, this part of the procedure is identical to
the original  scheme of [48]. As shown in [4] (see Theorem <ref> above), this generates a surface-code encoded Bell pair up to a (computable) Pauli correction and residual local stochastic noise.

A novel single-shot decoding procedure for transferring surface-code encoded quantum information onto a single physical qubit. We show that this procedure is resilient to local stochastic noise: There is  a threshold $p^{\textrm{dec}}_0$ such that if the initial encoded state $\overline{\Psi}$ is corrupted by a local stochastic $E\sim \cN(p)$ with noise strength $p\leq p^{\textrm{dec}}_0$, then the fidelity of the resulting single-qubit state with the logical state $\overline{\Psi}$ is exponentially close to $1$ as a function of the code distance $d$. We refer to Theorem <ref> below for details.

From a conceptual point of view, it is clear that combining (<ref>) with (<ref>) results in a procedure for generating long-range entanglement: Theorem <ref> guarantees that
the state after the first part of the procedure is essentially an encoded Bell state  corrupted by a local stochastic error. Applying the single-shot decoding procedure to each of the two surface codes then results in a high-fidelity two-qubit Bell state. Indeed, our result (Theorem <ref> below) ensures that the local stochastic error is dealt with properly in the single-shot decoding phase.

While our scheme for long-range entanglement generation is indeed a direct combination of steps (<ref>) with (<ref>), our analysis of the resulting fidelity is not simply a combination of the analytical results stated above for each module (<ref>) and (<ref>). This is because a naive combination of these analytical building blocks only provides a proof-of-principle: A threshold result derived in this way does not yield parameters of practical relevance. Instead, we establish a significantly tighter threshold estimate by a direct analysis of the achieved fidelity for the entire (combined) process.

§.§.§ Fault-tolerant single-shot decoding for surface codes

The surface code of distance $d$ with the lattice (solid) and its dual (dotted). Each sphere represents a qubit. Logical string operators $\overline{X}$ (blue, solid edges) and $\overline{Z}$ (red, dotted edges) are illustrated.

In the following,
we consider a single qubit encoded into a surface code using an isometric encoding map $V:\mathbb{C}^2\rightarrow(\mathbb{C}^{2})^{\otimes n}$ that maps the single-qubit Pauli operators to the “canonical” logical string operators
$\overline{X}=VXV^\dagger$ and  $\overline{Z}=VZV^\dagger$ of the surface code, see Fig. <ref>.  Let us write $\overline{\Psi}:=V\Psi$ for the encoded version of a physical qubit $\Psi\in\mathbb{C}^2$. Our main  building block is a decoding procedure for the surface code that can be summarized as follows. It is illustrated in Fig. <ref>.

The measurement pattern for single-shot surface code decoding. The recovery sets $\cL_X \subset \cX$ (blue, solid edges) and $\cL_Z^{*} \subset \cZ$ (red, dotted edges) for fault-tolerant measurement of $\overline{X}$ and $\overline{Z}$ are illustrated.

Consider a distance-$d$ surface code with $d\geq 2$ consisting of $n=2d^2-2d+1$ qubits.
Then there is a partition $[n]=\cX\cup\cZ\cup \{q\}$
of the set of qubits into disjoint sets $\cX$, $\cZ$ and a set $\{q\}$ consisting of a single qubit $q$, and two  efficiently computable functions

\begin{align}
\begin{matrix}
\alpha: & \{0,1\}^{\cC\backslash \{q\}} & \rightarrow &\{0,1\}\\
\beta: & \{0,1\}^{\cC\backslash \{q\}} & \rightarrow &\{0,1\}
\end{matrix}
\end{align}

such that the following holds. Consider the following protocol applied to a surface-code encoded logical state $\overline{\Psi}:=V\Psi$ corrupted by
a local stochastic error $E\sim\cN(p)$ of strengh

\begin{align}
p \leq \frac{1}{144}\approx 7\times 10^{-3} \ ,
\end{align}

where  $\Psi\in\mathbb{C}^2$ is arbitrary:

* Each qubit $c\in\cX$ is measured in the Hadamard basis, and

* each qubit $c\in \cZ$ is measured in the computational basis.

Let $s\in \{0,1\}^{\cC\backslash \{q\}}$ be the (collection of) measurement outcomes, and let

\begin{align}
\psi_E(s)\propto (I_{q}\otimes \bra{s}H(\cX))EV\ket{\Psi}
\end{align}

be the corresponding  post-measurement state on qubit $q$. Then

\begin{align}
\Pr_{E,s}\left[Z_q^{\alpha(s)}X_q^{\beta(s)}\psi_E(s)\propto \Psi\right]\geq 1-94p \ .
\end{align}

This shows that the logical state encoded in the surface code can be transferred to a single qubit in a fault-tolerant manner, up to a Pauli correction which is determined by the measurement outcomes.  We refer to Theorem <ref> below for a more detailed statement.  Similarly as before,  the functions $\alpha,\beta$ are defined in terms of minimum matchings, and can be computed in time $O(n^3)$ in this case.

We note that  Theorem <ref> immediately yields a protocol for fault-tolerantly measuring the logical Pauli-$\overline{Z}$ operator, thus subsuming Theorem <ref>. The corresponding measurement protocol  proceeds by  applying a computational basis measurement on the post-measurement state $\psi_E(s)$  on qubit $q$ with outcome $m$, and outputting the corrected bit $m\oplus \beta(s)$.  In a similar manner, one can realize a fault-tolerant logical $T$-measurement as considered in [33].  Beyond measuring $\overline{Z}$ or $\overline{T}$, Theorem <ref> also permits to execute any logical measurement on the encoded information. More generally, as the information ends up being localized on qubit $q$, it can be acted on in subsequent quantum-information-processing protocols.

The protocol provided in Theorem <ref> bears some similarity to teleportation: encoded information is essentially teleported to a single physical qubit. To illustrate the basic
underlying idea, consider a CSS-stabilizer code encoding a single qubit, with a property that logical $\overline{X}$- and $\overline{Z}$-Pauli operators can be chosen in a way that they overlap only in a single qubit $q$. As a concrete example, consider
the stabilizer code with generators

\begin{align}
S_1 &=X_1X_3\\
S_2 &=Z_1Z_2Z_3\ .
\end{align}

It encodes  a single logical qubit into three physical qubits. We can choose logical operators as

\begin{align}
\overline{X}&=X_1X_2\\
\overline{Z}&=Z_1Z_3\ ,
\end{align}

which has the desired property (with $q$ being the first qubit). Suppose $\overline{\Psi}\in(\mathbb{C}^2)^{\otimes 3}$ is an encoded state associated with $\Psi\in\mathbb{C}^2$. Assume we measure qubit $2$ in the Hadamard basis, obtaining outcome $x\in\{0,1\}$, and measure qubit $3$ in the computational basis getting the outcome $z\in \{0,1\}$. This corresponds to measuring the observables $X_2$ and $Z_3$. Then it is easy to check that the post-measurement state $\varphi(x,z)\in\mathbb{C}^2$ on qubit $1$  has expectation values

\begin{align}
\bra{\varphi(x,z)} X\ket{\varphi(x,z)}&=(-1)^x \bra{\overline{\Psi}}\overline{X}\ket{\overline{\Psi}}\\
\bra{\varphi(x,z)} Z\ket{\varphi(x,z)}&=(-1)^z \bra{\overline{\Psi}}\overline{Z}\ket{\overline{\Psi}}\ .
\end{align}

It follows immediately that the state $Z^xX^z\ket{\varphi(x,z)}$ has identical expectation values as the logical state $\overline{\Psi}$, and hence must be proportional to $\Psi$. That is, the logical state $\overline{\Psi}$ is decoded, i.e., transferred to the first physical qubit. We note, however, that the process described here is not fault-tolerant. In particular, the measurement of the observables $X_2$ and $Z_3$ is not resilient to errors and may lead to an incorrect “correction” operation $Z^xX^z$.

Here we argue that for the surface code, an analogous process can in fact be made fault-tolerant. The idea is to use logical operators that again only overlap in a single qubit $q$, i.e.,

\begin{align}
\overline{X}&=X_q X(\cL_X)\\
\overline{Z}&=Z_q Z(\cL_Z^{*})\ ,
\end{align}

where $\cL_X$ and $\cL_Z^{*}$ are disjoint subsets of qubits, see Fig. <ref>. The goal, then, is to fault-tolerantly measure the observables $X(\cL_X)$ and $Z(\cL_Z^{*})$. Such a procedure can be obtained by modifying the protocol of Theorem <ref>. The latter gives a fault-tolerant way of measuring $\overline{Z}$ by measuring  all qubits in the computational basis, and, by considering the dual lattice, a way of measuring the logical operator $\overline{X}$ by measuring all qubits in the  Hadamard basis.
To simulate the measurement of both $X(\cL_X)$ and $Z(\cL_Z^{*})$ at the same time, we use a  pattern of single-qubit measurements that simultaneously measures a subset of qubits in the computational basis, and a subset of qubits in the Hadamard basis. The measurement pattern is “triangular” as shown in Fig. <ref>. We show that this procedure has the properties stated in Theorem <ref>.

§.§.§ Outline

In Section <ref>, we introduce our single-shot decoding protocol for the surface code accompanied with background material. In Section <ref>, we provide a combinatorial framework for analyzing  matching problems
arising in the analysis of both  our surface code decoding protocol and the  entanglement generation protocol introduced in Section <ref>. Using the framework, we prove in Section <ref> that our surface code decoding protocol is robust against local stochastic noise.

Then in Section <ref>, we introduce our long-range entanglement generation protocol.  We prove in Section <ref> that this protocol is resilient against local stochastic noise of strength below a certain threshold: A lower bound on the achievable distance of entanglement generation is presented in terms of the noise strength and the number of qubits. Finally, in Section <ref>, we present a converse result for low latency entanglement generation schemes.

§ SINGLE-SHOT SURFACE CODE DECODING

In this section, we define our single-shot decoding protocol for the surface code: We introduce all relevant definitions to apply this protocol in practice.  We defer the analysis of the resilience of this protocol against local stochastic noise to subsequent sections: In Section <ref>, we will first provide general bounds on certain matching problems on graphs. These will subsequently be applied in Section <ref> to establish a fault-tolerance threshold theorem for the single-shot decoding protocol introduced here.

§.§ Definition of surface code

We consider a distance-$d$-surface code with
a total of $n=2d^2-2d+1$ qubits associated with $d^2$ horizontal edges and $(d-1)^2$ vertical edges as illustrated in Fig. <ref>.  The code has smooth boundaries at the top and bottom, and rough boundaries on the left and right. In more detail, consider a square lattice in $\mathbb{R}^2$ consisting of sites

\begin{align}
\Cprime&=\left\{(u_1,u_2)\in\mathbb{Z}^2\ |\ 0\leq u_1\leq 2d\textrm{ and } 0\leq u_2\leq 2d-2\right\}\ .
\end{align}

We  place qubits at sites $(u_1,u_2)\in\Cprime$ with the property that one coordinate $u_j$ is even, whereas the other coordinate $u_k$ is odd, i.e., qubits are located at the sites

\begin{align}
\cC=\Cprime \setminus\{(o,o),(e,e)\}=\{(o,e)\}\cup \{(e,o)\}\subset\Cprime .
\end{align}

Here and below we write $e$ (respectively $o$) for an even (respectively odd) integer and use the convention that e.g., $\{(o,o)\}\subset\Cprime$ is the subset of all pairs $(u_1,u_2)\in \Cprime$ with both $u_1$ and $u_2$ even.  Let

\begin{align}
d(u,v):=\sum_{j=1}^2 \abs{u_j-v_j}\
\end{align}

denote Manhattan distance between $u$ and $v$. Given a site $u\in \Cprime$, the set of nearest  neighbors of $u$ is defined as

\begin{align}
\neigh(u) = \left\{v \in \mathcal{C} \mid d(u,v) = 1\right\}\
\label{eq:nearestneighborset}
\end{align}

i.e., the  nearest neighbors of $u$ are associated with qubits at Manhattan distance $1$ from $u$.

The  surface code graph $T_{sc}=(\Vsc,\Esc)$ is  defined as

\begin{align}
\Vsc&=\{(e,e)\}\subset \Cprime\\
\Esc&=\left\{\{u,v\}\in \Vsc\times \Vsc\ |\ (u_1,v_1)\not\in\{(0,0),(2d,2d)\}, d(u,v)=2\right\}\ .
\end{align}

In other words, edges of $\Tsc$ are associated with pairs $(u,v)$ separated by a distance $d(u,v)=2$, with the exception of pairs $(u,v)$ that lie on the same vertical at $u_1=v_1=0$ or $u_1=v_1=2d$. The corresponding vertices

\begin{align}
\Vdangsc &=\{(0,e)\}\cup \{(2d,e)\} \subset \Vsc
\end{align}

are degree-$1$ vertices in $\Tsc$, i.e., endpoints of “dangling” edges at one of the “rough” boundaries of $\Tsc$: they are connected only to their right respectively left nearest neighbor. We can therefore express the set of edges of $\Tsc$ succintly as

\begin{align}
\Esc&=\left\{\{u,v\}\in \Vsc\times \Vsc\ |\ d(u,v)=2\textrm{ and }  (u,v)\not\in\Vdangsc\times\Vdangsc\right\}\ .
\end{align}

In the following, it will be convenient
to label an edge $\{u,v\}\in \Esc$ by its midpoint $(u+v)/2\in \cC$.

We will extensively use a “dual graph” $\Tscdual=(\Vscdual,\Escdual)$. To define this, let us first consider the set

\begin{align}
\Cprimedual&=\left\{(u_1,u_2)\in\mathbb{Z}^2\ |\ 1\leq u_1\leq 2d-1\textrm{ and } -1\leq u_2\leq 2d-1\right\}\
\end{align}

of dual sites. We note that the location of qubits can equivalently be specified as

\begin{align}
\cC^{*}&=\{(o,e)\}\cup \{(e,o)\}\subset\Cprime^{*}\ .
\end{align}

i.e., $\cC = \cC^{*}$.
The dual surface code graph $\Tscdual=(\Vscdual,\Escdual)$
is defined by

\begin{align}
\Vscdual&=\{(o,o)\}\subset \Cprime_*\\
\Escdual&=\left\{\{u,v\}\in \Vscdual\times \Vscdual\ |\ (u_2,v_2)\not\in\{(-1,-1),(2d-1,2d-1)\} \textrm{ and }d(u,v)=2\right\}\ .
\end{align}

Here degree-$1$-vertices, i.e., those belonging to

\begin{align}
\Vdangscdual &=\{(o,-1)\}\cup \{(o,2d-1)\} \subset \Vscdual\ ,
\end{align}

are located at the top- and bottom “rough” boundaries.
Again, we sometimes refer to an edge $\{u,v\}\in \Escdual$ by its midpoint $(u+v)/2$.

The surface code associated with the surface code graphs $\Tsc,\Tscdual$ is defined as follow: For every vertex $u\in \Vsc$ with degree $\deg_{\Tsc}(u)\geq 3$, i.e.,
every vertex $u\in \Vsc\setminus\Vdangsc$ which is not the endpoint of a dangling edge $u$, there is a stabilizer generator $A_u:=\prod_{v\in \neigh(u)} X_v$ consisting of Pauli-$X$ operators only. Pauli-$Z$-stabilizer generators are defined similarly based on the dual graph $\Tscdual$: For every $u\in \Vsc^*$, there is a stabilizer generator $B_u:=\prod_{v\in\neigh(u)}Z_v$ consisting of Pauli-$Z$ operators only.

3|c| $\Tsc=(\Vsc, \Esc)$

subsets of $\Esc$     color     measurement

$\cX$     1.5cm0.3cm     $X$-basis

$\cZ$     1.5cm0.3cm     $Z$-basis

$\{q\}$      1.5cm0.3cm     -

3|c| $\Tscdual=(\Vscdual, \Escdual)$

subsets of $\Escdual$     color     measurement

$\cX$     1.5cm0.3cm     $X$-basis

$\cZ$     1.5cm0.3cm     $Z$-basis

$\{q\}$      1.5cm0.3cm     -

The surface code graph $\Tsc$, and the dual graph $\Tscdual$. All qubits are situated at the midpoints of the edges.
The protocol uses a measurement pattern where qubits belonging to $\cX$ (midpoints of blue edges) are measured in the Pauli-$X$ basis, qubits belonging to $\cZ$ (midpoints of red edges) are measured in the Pauli-$Z$ basis, and qubit $q$ (midpoints of green edges) is not measured.

§.§ Graphs with internal vertices: boundary map and minimal matchings

Our decoder is based on an algorithm $\mmatch$ which finds certain matchings of a graph with internal and external vertices.  Let us first discuss some basic notions.

We  consider  pairs $(G=(V,E),V^\mathrm{int})$ where $G$ is a graph and $V^\mathrm{int}\subset V$ a subset of vertices we call internal vertices. The complement $V^\mathrm{ext}:=V\setminus V^\mathrm{int}$ will be referred to as the set of external vertices.

Define a boundary map
$\partial:2^{E} \rightarrow 2^{V^\mathrm{int}}$ that takes a subset $\cE\subset E$ of edges
to a subset $\partial \cE\subset V^\mathrm{int}$ of internal vertices: An interval vertex $v\in V^\mathrm{int}$ belongs to $\partial\cE$ if and  only if the number of edges $e\in\cE$ incident on $v$ is odd.
The map $\partial$ can be understood as the “usual” $\mathbb{Z}_2$-boundary map taking $1$-chains  (sets of edges) on the graph $G$ to $0$-chains (sets of vertices)  on $G$, followed by a projection onto the subset of vertices $V^\mathrm{int}$. We observe that, interpreted as a function $\partial:\mathbb{Z}_2^{E}\rightarrow\mathbb{Z}_2^{V^\mathrm{int}}$, the boundary map $\partial$ is $\mathbb{Z}_2$-linear.

Let $\cV\subset V^\mathrm{int}$ be a subset of internal vertices. A subset $\cE\subset E$ of edges is  called a matching of $\cV$ if $\partial\cE=\cV$.
A matching $\cE$ of $\cV$ is called minimal if it its size $|\cE|$ is minimal among all matchings of $\cV$.

We note that for every graph $G=(V,E)$ with interval vertices $\Vint$, there is a deterministic algorithm $\mmatch$ which outputs a minimum matching $\mmatch(\cV)$ of the given subset $\cV \subset \Vint$ with runtime  bounded by $O(\abs{V}^3)$ [30, 20, 53]. This is obtained by suitably adapting Edmond's matching algorithm [14].

In Section <ref>, we will provide a general combinatorial analysis of matching on graphs with internal vertices. The “decoding” graphs of interest will be introduced in Section <ref>.

§.§ Measurement pattern used in protocol

Here we define the triangular measurement pattern used in our single-shot decoding protocol.  Let

\begin{align}
q&:=(1,0)\in \cC
\end{align}

be the qubit at the bottom left corner. The measurement pattern is then defined as follows (see Fig. <ref>):
Every qubit belonging to

\begin{align}
\cX&:=\left\{(u_1,u_2)\in \cC\setminus\{q\}\ |\ u_2\geq u_1+1\right\}
\end{align}

is measured in the Pauli-$X$-basis. Every qubit belonging to

\begin{align}
\cZ&:=\left\{(u_1,u_2)\in \cC\setminus\{q\}\ |\ u_2< u_1+1\right\}
\end{align}

is measured in the Pauli-$Z$ basis. The qubit at $q$ is not measured.

§.§ Recovery sets

We will consider a special subset $\cL_X\subset \Esc$ of edges, see Fig. <ref>. The set $\cL_X$ is located on a vertical strip and consists of edges associated with the qubits

\begin{align}
\cL_X&=\{ (1,u_2)\ |\ u_2\geq 2, u_2\textrm{ even }\}\ .\label{eq:cLXdefinition}
\end{align}

(Here we use the convention that an edge $\{u,v\}$ is represented by its midpoint; it is, however, more natural to think of elements of $\cL_X$ as edges of $\Esc$.)

Similarly, we consider a “dual” set $\cL_Z^*\subset\Edecdual$ located on a horizontal strip defined by their midpoints

\begin{align}
\cL_Z^*&=\left\{(u_1,0)\ |\ u_2\geq 3, u_2\textrm{ odd }\right\}\ .\label{eq:cLZdefinition}
\end{align}

We will argue below that our protocol will need to estimate parities of certain strings restricted to $\cL_X$ and $\cL_Z^*$, respectively, in order to fix errors. This is because the associated qubits are closely related to the logical Pauli operators of the surface code, as discussed below. For this reason, we call $\cL_X$ and $\cL_Z^*$  the recovery sets.

3|c| $\Tsc=(\Vsc, \Esc)$

subsets of $\Esc$     color     measurement

$\cL_X$     1.5cm0.3cm     $X$-basis

$\cX \setminus \cL_X$     1.5cm0.3cm     $X$-basis

$\cZ$     1.5cm0.3cm     $Z$-basis

$\{q\}$      1.5cm0.3cm     -

3|c| $\Tscdual = (\Vscdual, \Escdual)$

subsets of $\Edecdual$     color     measurement

$\cX$     1.5cm0.3cm     $X$-basis

$\cL_Z^{*}$     1.5cm0.3cm     $Z$-basis

$\cZ \setminus \cL_Z^{*}$     1.5cm0.3cm     $Z$-basis

$\{q\}$      1.5cm0.3cm     -

The surface code graph $\Tsc$ and the dual graph $\Tscdual$, as well as the associated recovery sets $\cL_X\subset \Esc$ (blue)  and $\cL_Z^*\subset \Escdual$ (red).

§.§ Decoding subgraphs and internal vertices

Let  us define the following “decoding” subgraph $\Tdec=(\Vdec,\Edec)$ of $\Tsc$, see Fig. <ref>. The graph $\Tdec$ is the subgraph induced by the set of vertices

\begin{align}
\Vdec&= \{(u_1,u_2)\in \Vsc\ |\ u_2\geq u_1>0\}\ .
\end{align}

Alternatively, we may say that $\Tdec$ is the subgraph of $\Tsc$ induced by
the set of edges $\Edec:=\cX$. Explicitly, the edges of $\Tdec$ are

\begin{align}
\Edec&=\left\{ \{u,v\}\in \Vdec\times \Vdec\ |\ d(u,v)=2\right\}\ .
\end{align}

Observe that the recovery set $\cL_X\subset\Edec$ is a subset of the edges of $\Tdec$. We will use $\Tdec$ to estimate a parity of a certain string restricted to $\cL_X$.

The graph $\Tdec$ has distinguished internal vertices

\begin{align}
\Vdecint&=\left\{u\in \Vdec\ |\ \neigh(u)\subset \Edec\right\}\  .\label{eq:tdecinterior}
\end{align}

A vertex $u\in \Vdec\setminus\Vdecint$ which is not internal is called external. We denote the set of external vertices of $\Tdec$ by $\Vdecext$, see Fig. <ref>. This definition is motivated by the fact that for every internal vertex $u\in\Vdecint$, the “star” operator $A_u$ of the surface code has support $\supp(A_u)\subset \Edec$ completely contained in the set of edges of $\Tdec$.  This is not the case for the external vertices.

3|c| $\Tdec=(\Vdec, \Edec)$

subsets of $\Edec$     color     measurement

$\cL_X$     1.5cm0.3cm     $X$-basis

$\cX \setminus \cL_X$     1.5cm0.3cm     $X$-basis

3|c| $\Tdecdual = (\Vdecdual, \Edecdual)$

subsets of $\Tdec$     color     measurement

$\cL_Z^{*}$     1.5cm0.3cm     $Z$-basis

$\cZ \setminus \cL_Z^{*}$     1.5cm0.3cm     $Z$-basis

The decoding graph $\Tdec$ and the dual decoding graph $\Tdecdual$.
Their internal (external) vertices are illustrated as white (black, resp.) spheres.
Edges are colored according to the subsets where their midpoints are contained (see the tables in the subfigures).

The “dual decoding subgraph” $\Tdecdual=(\Vdecdual,\Edecdual)$ of $\Tscdual$ is defined similarly:
The graph $\Tdecdual$ is the subgraph induced by the set of vertices

\begin{align}
\Vdecdual = \{(u_1, u_2) \in \Vsc \mid u_1 \geq u_2 > 0\} \setminus \{(1, -1)\} \ ,
\end{align}

and its edges are $\Edecdual := \cZ$. Explicitly, the edges of $\Tdecdual$ are

\begin{align}
\Edecdual = \{\{u,v\} \in \Vdecdual \times \Vdecdual \mid d(u,v) = 2\} \ .
\end{align}

Observe that the recovery set $\cL_Z^{*}$ is a subset of the edges of $\Tdecdual$.
We will use $\Tdecdual$ to estimate the parity of a certain string restricted to $\cL_Z^{*}$.

The internal vertices of $\Tdecdual$ are

\begin{align}
\Vdecdualint = \{u \in \Vdecdual \mid \neigh(u) \subset \Edecdual\} \ .\label{eq:tdecdualinterior}
\end{align}

Note that a vertex $u$ of $\Tdecdual$ is internal if and only if the “plaquette” operator $B_u$ of the surface code has support $\supp(B_u) \subset \Edecdual$ contained in the set of edges of $\Tdecdual$. A vertex $u \in \Vdecdual \setminus \Vdecdualint$ which is not internal is called external. We denote the set of external vertices of $\Tdecdual$ by $\Vdecdualext$.

§.§ Description of the single-shot decoding procedure

We provide the description of algorithm for single-shot surface code decoding.
Single-shot surface code decoding

[1]
A state on $(\mathbb{C}^2)^{\otimes \cC}$, where $\cC$
are the locations of qubits  of a distance-$d$ surface code.
Perform the following measurements: measure

every qubit in the set     in the      denote the outcome by

$\cX\subset \Edec$     $X$-basis     $x\in \{0,1\}^\cX$

$\cZ\subset \Edecdual$     $Z$-basis     $z\in \{0,1\}^\cZ$ .

Compute the boundaries of the subsets of edges $x$ and $z$ in $\Tdec$ and $\Tdecdual$, respectively, i.e., set

\begin{align}
s &\leftarrow \partial x\label{eq:sdefinitionboundarysingle}\\
s^{*} &\leftarrow \partial^*z\ .
\end{align}

Compute minimal matchings

\begin{align}
m &\leftarrow \mmatch(s)\\
m^* &\leftarrow \mmatch^*(s^{*})\
\end{align}

Compute the bits

\begin{align}
\hat{s}^X&\leftarrow \ztwoinner{m}{\cL_X}\label{eq:hatsxdefsingle}\\
\hat{s}^Z&\leftarrow \ztwoinner{m^{*}}{\cL^{*}_{Z}}\label{eq:hatszdefsingle}\ .
\end{align}

Determine  the bits

\begin{align}
\hat{c}_X &\leftarrow  \ztwoinner{x}{ \cL_X} \oplus \hat{s}^X\\
\hat{c}_Z& \leftarrow  \ztwoinner{z}{\cL^*_Z} \oplus \hat{s}^Z
\end{align}

Apply $Z^{\hat{c}_X} X^{\hat{c}_Z}$ to $q$.
Return the resulting qubit state on qubit $q$.

The following notation is used in the algorithm: For any two sets $A, B \in \cC$, we define

\begin{align}
\ztwoinner{A}{B} := \bigoplus_{j \in \cC} A_j B_j
\end{align}

where $A$ and $B$ are considered as strings (given by the characteristic function of the corresponding set) in $\{0,1\}^{\cC}$ and $\oplus$ denotes XOR on bits.
The value $\ztwoinner{A}{B}$ can  equivalently be defined as the parity of $\abs{A \cap B}$.
Considering the set of strings $\{0,1\}^{\cC}$ as a $\mathbb{Z}_2$-linear space, the map $\ztwoinner{\cdot}{\cdot}$ is clearly bilinear.

We also note that the runtime of Algorithm <ref>
is dominated by the computation of the matchings in step (<ref>), i.e.,
runs in time $O(\abs{\cC}^3)$, see the remark at the end of Section <ref>.

§ A BOUND ON MATCHING  WITH INTERNAL VERTICES

In this section, we
provide a general combinatorial framework for analyzing
decoding problems involving minimal matchings.  These arguments will be applied in Section <ref> to analyze the success probability
of the single-shot decoding Algorithm <ref> introduced in Section <ref> in the presence of local stochastic noise. We will also use these general concepts in Section <ref> to analyze the robustness of our entanglement generation protocol based on the 3D cluster state.

We first show in Section <ref> that a cycle, a set of edges in a graph with trivial boundary, can be decomposed as a disjoint union of simple closed paths and simple paths connecting two external vertices through internal vertices.

Next, in Section <ref>, we introduce the notion of a local stochastic subset of edges. This is a random variable $\cE$ which is
a random subset of edges, and whose distribution is exponentially decaying in the cardinality of the subset. We also introduce what we call  the resilience function associated with a fixed subset $\cL$ of edges. It is defined by a combinatorial expression in terms  of a sum over simple closed paths and simple paths connecting two external endpoint vertices through internal vertices.
We show that the value of resilience function is an upper bound on the probability that the parities of a local stochastic subset $\cE$  and the minimum matching $\mmatch{(\partial \cE})$ of the boundary of $\cE$ restricted to $\cL$ differ. In particular, this will allow us to use the parity of $\mmatch(\partial \cE) \cap \cL$ as an estimate of the parity of $\cE \cap \cL$. This is the key statement that we will subsequently use to analyze resilience against local stochastic noise.

§.§ Cycle decomposition

Let $(G = (V, E),\Vint)$ be a graph with a distinguished set of internal vertices $\Vint \subset V$. Let $\partial : 2^E \to 2^{\Vint}$ be the boundary map defined in Section <ref>.
A subset $\cE\subset E$ is called a cycle if the boundary $\partial \cE=\emptyset$ is trivial. We denote by $Z(G)$ the set of cyles on $G$.
By the linearity of $\partial$, the set of cycles $Z(G)$ forms a linear subspace of $\mathbb{Z}_2^{E}$ called the cycle space of $G$.
We will consider certain cycles which span $Z(G)$.

A closed loop $L=\{e_1, \dots, e_{\ell}\} \subseteq E$ is given by a sequence $(e_1, \dots, e_{\ell})$ of distinct edges such that there exists a set of vertices $\{v_1, \dots, v_{\ell}\}$  with the property  that $e_{j} = \{v_j, v_{j+1}\}$ for all $j = 1, \dots, \ell - 1$ and $e_{\ell} = \{v_{\ell}, v_1\}$.
In particular, any  closed loop $L$ belongs to $Z(G)$, that is, $\partial L = \emptyset$.
A simple closed loop $L=\{e_1, \dots, e_{\ell}\}$ is a closed loop with the property that the vertices $\{v_1, \dots, v_{\ell}\}$ are distinct.
We note that any closed loop can be decomposed into a set of pairwise (edge-)disjoint simple closed loops.
We will denote the set of simple closed loops on $G$ by $\Zcirc(G)$.

We say that a simple (i.e., not  self-intersecting) path $P=\{e_1, \dots, e_{\ell}\}\subseteq E$   connects two distinct external vertices through internal vertices if
there are distinct  vertices $v_1,v_{\ell+1}\in\Vext $ and $v_2,\ldots,v_{\ell}\in \Vint$
such that $e_j=\{v_j,v_{j+1}\}$ for $j=1,\ldots,\ell$.
Again, every such path $P$ belongs to $Z(G)$ and the edges $\{e_j\}_{j=1}^\ell$ are pairwise distinct by construction.
We will denote by $\Zpathext(G)$ the set of simple paths on $G$ connecting distinct external vertices through internal vertices.

The union of $Z_\circ(G)$ and $\Zpathext(G)$    spans the cycle space $Z(G)$. In fact, a stronger property holds:

Let $\cZ\in Z(G)$ be a cycle. Then $\cZ$ is the disjoint union of simple closed loops and simple paths with endpoints in $V^{ext}$ through internal vertices.
That is, there is a family

\begin{align}
\{\cZ_\alpha\}_{\alpha}\subset Z_\circ(G)\cup \Zpathext(G)
\end{align}

of cycles such that each $\cZ_\alpha$ is either a simple closed loop or a simple path with distinct endpoints in $V^{ext}$ passing through internal vertices, and

\begin{align}
\cZ=\bigcup_\alpha \cZ_\alpha\qquad\textrm{ with }\qquad \cZ_\alpha\cap \cZ_\beta=\emptyset\textrm{ for }\alpha\neq\beta\ .
\end{align}

Let $\cZ\in Z(G)$ be a cycle.
Suppose that there is a simple closed loop $L\in Z_{\circ}(G)$ that is contained in $\cZ$.
Then it follows immediately from the definitions that $\cZ':=\cZ\backslash L$ is also a cycle.
Proceeding inductively, we may decompose $\cZ$ as

\begin{align}
\cZ&=\tilde{\cZ}\cup \bigcup_{j=1}^r L_j\  \label{eq:czdecompositionclosedloops}
\end{align}

with pairwise disjoint simple closed loops $L_1,\ldots,L_r$ (with $r=0$ if $\cZ$ does not contain any simple closed loop) such that $\tilde{\cZ}$ contain does not contain any (simple) closed loop.

We claim that $\tilde{\cZ}$ is either empty or a union

\begin{align}
\tilde{\cZ}=\bigcup_{k=1}^s P_k\label{eq:pairwisedisjointpath}
\end{align}
of pairwise disjoint paths $\{P_k\}_{k=1}^s\subset \Zpathext(G)$ with distinct endpoints in $V^\mathrm{ext}$.
Consider the following two cases:

* If  $\tilde{\cZ}$ does not contain an edge $e\in \tilde{\cZ}$ with $e\cap \Vext\neq \emptyset$, i.e., if $\tilde{\cZ}$ only touches internal vertices of $V$, then the condition $\partial \tilde{\cZ}=\emptyset$ implies that
the number of edges belonging to $\tilde{\cZ}$ which are incident on any internal vertex $v\in V^\mathrm{int}$ is even. Because $\tilde{\cZ}$ does not contain any closed loop by construction, it follows that $\tilde{\cZ}=\emptyset$.

* Suppose there is an edge $e\in\tilde{\cZ}$ such that $e\cap (V \setminus V^\mathrm{int})\neq \emptyset$.
Let us assume that $e=\{v,w\}$ where $v\in V\backslash V^\mathrm{int}$ is an external vertex.
We can then construct a path $P=\{e_1,\ldots,e_\ell\}\subset\tilde{\cZ}$ that has $v=v_s$ as starting point, first traverses the edge $e_1:=e$, and finally ends at an external vertex $v_e\neq v_s\in V\backslash V^\mathrm{int}$.
Indeed, if $w\in V\backslash V^\mathrm{int}$ is an external vertex, then $P=\{e\}$ is such a path (of length $1$).
If $w\in V^\mathrm{int}$ is an internal vertex, then the condition $\tilde{\cZ}\in Z(G)$ implies that
the number of edges belonging to $\tilde{\cZ}$ and incident on $w$ is even.
In particular, there is an edge $e_2$ that is distinct from $e_1$.
We can proceed inductively to construct a path $\{e_1,\ldots,e_\ell\}\subset\tilde{\cZ}$.
Moreover, the path satisfies the desired properties, i.e., $P \in \Zpathext(G)$:
The condition $\partial\tilde{\cZ}=\emptyset$ guarantees that the path does not end at an internal vertex, and this implies that
the constructed path only touches internal vertices except for the endpoints $v_s$ and $v_e$ which are external vertices.
In addition, since $\tilde{\cZ}$ does not contain any closed loop, the path is simple.
In particular, its endpoint $v_e$ must be an external vertex which is distinct from $v_s$.

Once we have found such a path $P$, we can remove $P$ from $\tilde{\cZ}$, i.e., we can consider the set $\tilde{\cZ}':=\tilde{\cZ}\backslash L$.
It is easy to check that $\tilde{\cZ}'$ is also a cycle which does not contain any closed loops. Proceeding inductively, we obtain the claim (<ref>).

Combining (<ref>) and (<ref>) implies the claim.

§.§ Local stochastic subsets and the resilience function

A random subset $\cE$ of $E$ is a random variable specified by a distribution over subsets of $E$. We call a random subset $\cE$ local stochastic with parameter $p\in [0,1]$ if and only if

\begin{align}
\Pr\left[\cF\subseteq \cE\right]\leq p^{|\cF|}\qquad\textrm{ for all }\qquad \cF\subset E\ .
\end{align}

This will be denoted $\cE\sim\cN(p)$.

We will consider the difference of a random subset $\cE$ and a minimum matching $\mmatch\left(\partial\cE\right)$ computed from the boundary $\partial\cE$ of $\cE$. More precisely, we consider the parity of this difference restricted to a subset $\cL\subset E$. The following definition captures the relevant combinatorics of our estimates.

Let $(G=(V,E),V^\mathrm{int})$ be a graph with internal vertices $V^\mathrm{int}$.
Let $\cL\subset E$ be a subset of edges.
Then the resilience function $\res_\cL:[0,1]\rightarrow\mathbb{R}$ of $\cL$ is defined as

\begin{align}\label{eq:defofres}
\res_\cL(p):&=\sum_{\ell=1}^\infty
\binom{\ell}{\lceil \ell/2\rceil}\cdot \left|\left\{\cR\in
Z_\circ(G)\cup \Zpathext(G)\ |\ |\cR|=\ell\textrm{ and }\ztwoinner{\cR}{\cL}=1\right\} \right|\cdot p^{\lceil \ell/2\rceil}\ .
\end{align}

The resilience function $\res_\cL:[0,1]\rightarrow\mathbb{R}$
provides the following upper bound on the probability that the parity of $\cE$ and $\mmatch\left(\partial\cE\right)$  restricted to $\cL$ differ:

Let $\cE\sim \cN(p)$ be a local stochastic subset of $E$ with parameter $p\in [0,1]$.
Let $\cL\subset E$ be a subset of edges. Then

\begin{align}
\Pr\left[
\ztwoinner{\cE\oplus \mmatch\left(\partial\cE\right)}{\cL}=1\right]\leq \res_{\cL}(p)\ .
\end{align}

The proof follows the proof of <cit.> which is based on ideas of [18, 10].

\begin{align}
\mathrm{FAIL} := \left\{\cY \subseteq  E \mid \ztwoinner{\cY \oplus \mmatch\left(\partial \cY\right)}{\cL} = 1\right\}
\end{align}

such that the quantity of interest becomes $\Pr\left[\cE\in\mathrm{FAIL}\right]$.

For any set $\cY\subseteq E$, the set  $\cY \oplus \mmatch\left(\partial \cY\right)$
has trivial boundary by definition of $\mmatch$.
By Lemma <ref>, it belongs to the cycle space $Z(G)$ and can be   decomposed as a  union

\begin{align}
\cY \oplus \mmatch\left(\partial \cY\right)&=\bigcup_{\alpha}\cY_\alpha\ ,
\end{align}

where each $\cY_\alpha\in Z_\circ(G)\cup \Zpathext(G)$ is either a simple closed loop or a simple path connecting external vertices through internal vertices, and where
the sets $\cY_{\alpha}$ are pairwise disjoint.
It follows that for any $\cY\subseteq E$ with $\cY\in \mathrm{FAIL}$, there is at least one $\cY_\alpha$  with the property that $\ztwoinner{\cY_\alpha}{\cL}=1$.
That is, any such $\cY$ contains a subset $\cR \in \Zcirc(G) \cup \Zpathext(G)$ which satisfies $\ztwoinner{\cR}{\cL}=1$.

It follows that

\begin{align}
\Pr\left[\cE\in \mathrm{FAIL}\right] & \leq \Pr\left[\exists \cR\in  \Zcirc(G) \cup \Zpathext(G) : \cR\subset \cE\oplus \mmatch\left(\partial\cE\right)\textrm{ and }\ztwoinner{\cR}{\cL}=1\right] \ . \label{eq:pfailexpression}
\end{align}

For simplicity, let us define

\begin{align}
\cP(\cL) := \{\cR \in \Zcirc(G) \cup \Zpathext(G) \mid \ztwoinner{\cR}{\cL}=1\} \ .
\end{align}

With the union bound applied to (<ref>) we obtain

\begin{align}
\Pr\left[\cE\in \mathrm{FAIL}\right] &\leq \sum_{\cR\in\cP(\cL)}
\Pr\left[\cR\subseteq \cE\oplus \mmatch\left(\partial\cE\right)\right]\  .\label{eq:unionboundmainx}
\end{align}

Let $\cE\subset E$ be arbitrary and set $\cM:=\mmatch\left(\partial\cE\right)$.
Suppose that  $\cR\in\cP(\cL)$ satisfies

\begin{align}
\cR\subseteq \cE\oplus \cM\ .
\end{align}

We claim that at least half of the edges of $\cR$
do not belong to $\cM$, i.e.,

\begin{align}
\left|\cR\backslash \cM\right|\geq  |\cR|/2\ .\label{eq:claimzmlowerbound}
\end{align}

For the sake of contradiction, assume  that

\begin{align}
\left|\cR\backslash \cM\right|< |\cR|/2\ .\label{eq:contradictionassumption}
\end{align}
Then the set $\cM':=\cR\oplus \cM$ is a matching
of $\partial\cE$ since

\begin{align}
\partial \cM'&=\partial \left(\cR\oplus \cM\right)\\
&=\partial \cR\oplus \partial \mmatch\left(\partial\cE\right)\\
&=\partial\cE\ ,
\end{align}

where we used that every $\cR\in\cP(\cL)$ has trivial boundary $\partial\cR=\emptyset$.
Furthermore, we have

\begin{align}
|\cM'|&=|\cR\backslash \cM|+|\cM\backslash \cR|\\
&=|\cR\backslash \cM|+|\cM|-|\cM\cap\cR|\\
&=|\cR\backslash \cM|+|\cM|-(|\cR|-|\cR\backslash \cM|)\\
&<|\cM|\ ,
\end{align}

where we used our assumption (<ref>). Thus $\cM'$ is
a matching of $\partial\cE$ of smaller cardinality than $\cM$, contradicting the fact that $\cM$ is a minimum matching of $\partial\cE$.

Eq. (<ref>) shows that $\cR\subset\cE\oplus \cM$ together with $\cR\in\cP(\cL)$ imply that

\begin{align}
|\cR\cap \cE|&\geq |\cR|/2\ .\label{eq:zeintersetlowerbound}
\end{align}

Indeed, the fact that $\cR$ is contained in the symmetric difference
$\cE\oplus \cM$ implies that $\cR$ is the disjoint union $\cR=(\cR\cap \cE)\cup (\cR\cap \cM)$
and thus $\cR\cap \cE \supseteq \cR\backslash \cM$. This implies the claim (<ref>) together with (<ref>).

With (<ref>), we conclude that for every $\cR\in\cP(\cL)$, we have
$|\cR\cap \cE|\geq \lceil |\cR|/2\rceil$ (because $|\cR\cap \cE|$ is an integer) and thus

\begin{align}
\Pr\left[\cR\subseteq \cE\oplus \mmatch\left(\partial\cE\right)\right]&
\leq \Pr\left[
|\cR\cap \cE|\geq |\cR|/2\right]\\
&\leq \Pr\left[\exists \delta\subseteq \cR\ \textrm{ with } |\delta|=\lceil |\cR|/2 \rceil\textrm{ and }\delta\subseteq\cE \right]\ .
\end{align}

Here we used that for any set $\cE$ with $|\cR\cap \cE|\geq \lceil |\cR|/2\rceil$, there is a subset $\delta\subseteq \cR\cap \cE$ of size exactly equal to $\lceil |\cR|/2 \rceil$.
We can sum over subsets $\delta\subset\cR$ of cardinality $|\delta|=\lceil |\cR|/2 \rceil$ to obtain with the union bound

\begin{align}
\Pr\left[\cR\subseteq \cE\oplus \mmatch\left(\partial\cE\right)\right]&\leq \sum_{
\substack{
\delta\subseteq \cR\\
|\delta|=\lceil |\cR|/2 \rceil
\Pr\left[\delta\subseteq\cE\right]\\
&\leq \binom{|\cR|}{\lceil |\cR|/2 \rceil}
\cdot p^{\lceil |\cR|/2 \rceil}\ ,
\end{align}

where we used that $\cE\sim\cN(p)$, i.e., the fact that $\cE$ is local stochastic. The claim follows by inserting this into (<ref>) and applying the definition of $\res_\cL(p)$.

§ SINGLE-SHOT DECODING UNDER LOCAL STOCHASTIC NOISE

In this section, we establish our main result about single-shot decoding of the 2D surface code.
We consider a situation where a surface-code encoded state is corrupted by a local stochastic error, and where the output state $\rho_{\mathrm{out}}$ is obtained by running Algorithm <ref> on this corrupted logical state.

In Section <ref>, we consider a half-encoded Bell state $\ket{\Phi_{\cC R}}$ defined on the surface code system $\cC$ of the surface code and an auxiliary qubit system $R$. Supposing that Algorithm <ref> is executed on the surface code system of the Bell state corrupted by a Pauli error $E$ on the surface code qubits, we show that the output state then is one of the Bell basis states $\{\Phi_{(\alpha, \beta)}\}_{\alpha,\beta\in \{0,1\}}$, and find corresponding expressions for $\alpha$ and $\beta$.

In Section <ref>, we compute upper bounds on the resilience function of the recovery sets $\cL_X$ and $\cL_Z^{*}$.
Using these bounds and the expressions for $(\alpha,\beta)$ obtained in Section <ref>,
we prove in Section <ref> that for any input state corrupted by a local stochastic error of strength $p$ below a  certain threshold, the overlap $\ev{\rho_{\mathrm{out}}}{\Psi}$ between $\Psi$ and the output state $\rho_{\mathrm{out}}$ is at least $1-O(p)$.

§.§ Decoding on a corrupted half-encoded Bell state

In the following, we  use the logical Pauli operators

\begin{align}
\overline{X}&=X(\cL_X)X_q\\
\overline{Z}&=Z(\cL^*_Z)Z_q\
\end{align}

of the surface code.
We consider the action of  Algorithm <ref>  on a certain bipartite state of the form $\Phi_{\cC R}\in (\mathbb{C}^2)^{\otimes \cC\cup \{R\}}\cong (\mathbb{C}^2)^{\otimes \cC}\otimes\mathbb{C}^2$, where $R$ is a reference qubit. Specifically, we are interested in the Bell state $\Phi_{\cC R}$ between a surface-code encoded logical qubit and the reference qubit $R$.
We call this state the half-encoded Bell state (since the qubit $R$ is “physical”, i.e., not encoded). The  state has stabilizer generators $\{A_v\}_v\cup \{B_f\}_f\cup \{S^X,S^Z\}$, where $\{A_v\}_v$
and $\{B_f\}_f$ are the usual surface code generators (associated with vertices and faces  of the surface code lattice), and where

\begin{align}
\begin{matrix}
S^X &:=&\overline{X}X_R&=&X(\cL_X)X_qX_R\\
S^Z &:=&\overline{Z}Z_R&=&Z(\cL^*_Z)Z_qX_R\ ,
\end{matrix}\label{eq:sxszsingleexpr}
\end{align}

are the Bell state stabilizer generators. In addition to the stabilizer generators $\{S^X,S^Z\}$, the following sets $\{S^u\}_{u\in \Vdecint}$ and $\{S^{u^*}\}_{u^*\in \Vdecdualint}$ of stabilizers of the state $\Phi_{\cC R}$ play a special role in our argument. They are defined as follows: Any internal vertex $u\in \Vdecint$ of $\Tdec$ is associated with it a stabilizer generator $S^u$ of the surface code consisting of Pauli-$X$-operators only, namely $S^u=A_u$.
In a similar vein, any internal vertex $u^*\in \Vdecdualint$  of $\Tdecdual$ gives rise to a stabilizer $S^{u^*}$ consisting of $Z$-type operators, namely the face operator $B_{u^*}$ when $u^*$ is considered as a face of the original surface code lattice $\Tsc$.
Observe that for each $u\in \Vdecint$,
the support  $\supp(S^u)=\incident(u)$ of $S^u$  is
equal to the set of edges incident on $u$ in the graph $\Tdec$. Similarly, for each $u\in \Vdecdualint$, we have $\supp(S^u)=\incident^*(u)$ where $\incident^*(u)$ is the set of edges incident on $u$ in the graph $\Tdecdual$. That is, we have

\begin{align}
\prod_{v\in \incident(u)} X_v\qquad\textrm{ for }\qquad u\in \Vdecint\\
\prod_{v\in \incident(u)} Z_v\qquad\textrm{ for }\qquad u\in \Vdecdualint \ .
\end{cases}\label{eq:Suincidentrelations}
\end{align}

Consider the result of running the algorithm on a corrupted state

\begin{align}
\ket{\Psi_{\textrm{in}}}&=E\ket{\Phi_{\cC R}}\ \label{eq:noisyclusterstatesingle}
\end{align}

for a fixed Pauli error $E$.
We assume here that $\supp(E)\subseteq \cC$, i.e., the error acts on the surface code qubits only (and does not affect the reference system $R$). Let

\begin{align} \label{eq:pmstateinalgsingle}
\ket{\psi_{\mathrm{pm}}(x,z,E)} = \frac{1}{\sqrt{p(x,z|E)}} \left( \bra{x}_{\mathcal{X}}H(\mathcal{X})^\dagger\otimes \bra{z}_{\mathcal{Z}} \otimes I_{\{q,R\}} \right) E \ket{\Phi_{\cC R}}\
\end{align}

be the state obtained  after Step <ref> of the algorithm  on qubit $q$.
Here we denote by $p(x,z|E)$ the probability of obtaining the outcomes $(x,z)$ given a Pauli error $E$, i.e., for the input state (<ref>).
It will be convenient in the following to use the definition

\begin{align}\label{eq:defsyn}
\syn(P,Q) =
\begin{cases*}
0 & \textrm{ if $P$ and $Q$ commute}\\
1 & \textrm{ otherwise }
\end{cases*}
\end{align}

for any two Pauli operators $P$ and $Q$.
Then the following holds:

Let $S^X$ and $S^Z$ be the operators (<ref>). Let

\begin{align}
c_X &:=  \ztwoinner{x}{\cL_X} \oplus \syn(S^X, E)\label{eq:cxdefinitionsingle}\\
c_Z &:= \ztwoinner{z}{\cL^*_Z} \oplus \syn(S^Z, E)\ . \label{eq:czdefinitionsingle}
\end{align}

Then the post-measurement state $\psi_{\mathrm{pm}}(x,z,E)$ on the two qubits $q,R$
after Step <ref>
of Algorithm <ref>,   given an initial error $E$ and measurement outcomes $(x,z)$ is the Bell state (cf. (<ref>))

\begin{align}
\ket{\psi_{\mathrm{pm}}(x,z,E)} &=\ket{\Phi_{(c_X,c_Z)}}\ .
\end{align}

The claim is an immediate consequence of the fact that $S^X$ and $S^Z$ are stabilizers of $\ket{\Phi_{\cC R}}$,
as well as the expressions (<ref>) of the stabilizer generators: Replacing $\ket{\Phi_{\cC R}}$ in (<ref>) by $S^X\ket{\Phi_{\cC R}}$, we observe that the post-measurement state $\ket{\psi_{\mathrm{pm}}}=\ket{\psi_{\mathrm{pm}}(x,z,E)}$

\begin{align}
\sqrt{p}  \ket{\psi_{\mathrm{pm}}}    &= \left( \bra{x}_{\mathcal{X}}H(\mathcal{X})^\dagger \otimes \bra{z}_{\mathcal{Z}}\otimes I_q \right) E S^X\ket{\Phi_{\cC R}}\\
&=  (-1)^{\syn(S^X, E)} \left(  \bra{x}_{\mathcal{X}}H(\mathcal{X})^\dagger\otimes \bra{z}_{\mathcal{Z}} \otimes I_q\otimes I_R \right) S^X E  \ket{\Phi_{\cC R}}\\
&=  (-1)^{\ztwoinner{x}{\cL_X} \oplus \syn(S^X, E)} \left(\bra{x}_{\mathcal{X}}H(\mathcal{X})^\dagger \otimes \bra{z}_{\mathcal{Z}}\otimes X_qX_R\right) E
\ket{\Phi_{\cC R}}\ ,
\end{align}

where $p := p(x,z|E)$ and where we used (<ref>) as well as the identity

\begin{align}
X(\cL_X)H(\cX)\ket{x}_{\cX}&=(-1)^{\ztwoinner{x}{\cL_X}}H(\cX)\ket{x}_{\cX}\ .
\end{align}

We conclude that

\begin{align}
\ket{\psi_{\mathrm{pm}}}   &= (-1)^{\ztwoinner{x}{\cL_X} \oplus \syn(S^X, E)} X_{q}X_{R}
\ket{\psi_{\mathrm{pm}}}   \\
&= (-1)^{c_X} X_{q} X_{R}\ket{\psi_{\mathrm{pm}}}\ ,
\end{align}

by definition of $c_X$.

In an analogous manner, we can check that $\ket{\psi_{\mathrm{pm}}} = (-1)^{c_Z} Z_{q}Z_{R} \ket{\psi_{\mathrm{pm}}}$ by
$\ket{\Phi_{\cC R}}$ in (<ref>) by $S^Z\ket{\Phi_{\cC R}}$.  Thus the two-qubit state $\ket{\psi_{\mathrm{pm}}}$ on systems $q,R$      is stabilized by $\{(-1)^{c_X}X_{q}X_{R},(-1)^{c_Z}Z_{q}Z_{R}\}$. This implies the claim.

According to Lemma <ref>, the post-measurement state is fully determined by the single-qubit measurement results $(x,z)$ and the bits $\syn(S^X, E)$ and $\syn(S^Z, E)$.
To analyze these bits, we introduce decomposition

\begin{align}\label{eq:xzdecomposition}
\end{align}

of $E$ into a product of Pauli-$X$ and Pauli-$Z$ operators $E^X$ and $E^Z$, respectively.  (We note that if $E\sim\cN(p)$ is a local stochastic error of strength $p$, the same is true for both $E^X$ and $E^Z$, i.e., $E^X\sim\cN(p)$ and $E^Z\sim\cN(p)$, a fact we will use below.)

In (<ref>), the global phase is ignored since we will only need the supports $\supp(E^X)$ and $\supp(E^Z)$.
We show that the bits $\syn(S^X,E)$ and $\syn(S^Z,E)$  are determined by the physical errors on qubits $\{q_1,q_2\}$ as well as a certain restriction of the error as specified in the following statement:

Let $E$ be a Pauli operator on $\mathcal{C}$ and let $S^X$ and $S^Z$ be the Pauli operators defined by (<ref>). Decompose $E$ into a product $E = E^XE^Z$ of Pauli-$X$- and Pauli-$Z$-operators, respectively.

\begin{align}
\syn(S^X, E) &= \ztwoinner{\{q\}}{\supp(E^Z)} \oplus \ztwoinner{\cL_X}{\supp(E^X)}\label{eq:synviaEglsingle}\\
\syn(S^Z, E) &= \ztwoinner{\{q\}}{\supp(E^Z)} \oplus \ztwoinner{\cL_Z^*}{\supp(E^Z)}\ .\label{eq:synviaEgldualsingle}
\end{align}

Let $E$ be an arbitrary Pauli operator on $\cC$.
With expression (<ref>) for $S^X$, we have

\begin{align}
\syn(S^X,E)&=\syn\left(X_{q}X_{R}X\left(\cL_X\right),E\right)\\
&= \ztwoinner{\{q\}}{\supp(E^X)} \oplus \ztwoinner{\cL_X}{\supp(E^X)}
\end{align}

since $E$ acts trivially on the reference system $R$. The claim for $\syn(S^Z,E)$ follows similarly.

Unfortunately, the operators $E^X$ and $E^Z$ are not determined by the measurement results $(x,z)$. In particular, the bits $\syn(S^X,E)$ and $\syn(S^Z,E)$ cannot be computed from the measurement outcomes. Algorithm <ref> therefore generates estimates $\hat{s}^X$ and $\hat{s}^Z$ for these bits, see step <ref>.

To motivate the definition of these bits, and to derive a sufficient condition for when the algorithm is correct (i.e., generates the Bell state $\Phi$), we discuss how the measurement results $(x,z)$ constrain the error $E$, or more precisely
the operators $E^X$ and $E^Z$. That is, we consider what information can be gathered from these measurement outcomes. Observe  that the operators $(E^X,E^Z)$ are fully determined by the supports $\supp(E^X)$ and $\supp(E^Z)$.
We obtain constraints on these sets expressed in terms of the strings $s,s^*$ computed in Step <ref> of  Algorithm <ref>.

The strings $s \in \{0,1\}^{\Vdecint}$ and $s^* \in \01^{\Vdecdualint}$ computed (from the measurement outcomes $(x,z)$) in Step <ref>  satisfy

\begin{align}
s &= \partial \supp(E^Z)\label{eq:stglclaimsingle}\\
s^{*} &= \partial^* \supp(E^X)\ .\label{eq:stglclaimdualsingle}
\end{align}

Let $s = (s_u) \in \01^{\Vdecint}$ be the string computed in step <ref>, i.e., $s=\partial x$. Let $u\in \Vdecint$.
Since $s_u=(\partial x)_u=\ztwoinner{x}{\incident(u)}$
and  $\left(\partial \supp(E^Z)\right)_u=\ztwoinner{\incident(u)}{\supp(E^Z)}$, we need to show that

\begin{align}
\ztwoinner{x}{\incident(u)}&=\ztwoinner{\incident(u)}{\supp(E^Z)}\qquad\textrm{ for every }\qquad u\in \Vdecint\ .\label{eq:toprovexuinnersingle}
\end{align}

Note that $S^u$ stabilizes the (uncorrupted) state $\ket{\Phi_{\cC R}}$ (by definition of the latter).
Replacing $\ket{\Phi_{\cC R}}$ in (<ref>) by $S^u\ket{\Phi_{\cC R}}$ yields

\begin{align}
\ket{\psi_{\mathrm{pm}}}
&= \frac{1}{\sqrt{p}} \left(  \bra{x}_{\mathcal{X}}H(\mathcal{X})^\dagger \otimes \bra{z}_{\mathcal{Z}} \otimes I_{\{q,R\}} \right) E S^u W \ket{0^\cC}\\
&= \frac{1}{\sqrt{p}} (-1)^{\syn(S^u, E)} \left(\bra{x}_{\mathcal{X}}H(\mathcal{X})^\dagger \otimes \bra{z}_{\mathcal{Z}} \otimes I_{\{q,R\}} \right) S^u E W \ket{0^\cC}\\
&=  (-1)^{\syn(S^u, E) \oplus  \ztwoinner{x}{\incident(u) }} \ket{\psi_{\mathrm{pm}}} \ .\label{eq:psipmeigenvalsingle}
\end{align}

Here the third equality follows from the identity

\begin{align}
S^u H(\cX)\ket{x}&=
(-1)^{\ztwoinner{x}{\incident(u) }}H(\cX)\ket{x}\
\end{align}

which is a consequence of
the definition of $S^u$ (as an $X$-type
stabilizer generator the surface code), as well as the fact that for $u\in \Vdecint$, the set $\supp(S^u)$ does not contain $q$ for any $u\in \Vdecint$, see Eq. (<ref>).
Identity (<ref>)
implies that

\begin{align}
\syn(S^u,E)=\ztwoinner{x}{\incident(u)}\qquad\textrm{ for  }\qquad u\in V_{dec}^{int}\ .\label{eq:firststepclaimsingle}
\end{align}

Observe that according to (<ref>), we also have

\begin{align}
\syn(S^u, E) &=
\syn\left(\left(\prod_{v \in \incident(u)} X_v\right),E\right)      = \ztwoinner{\incident(u) }{\supp(E^Z)}\qquad\textrm{ for any }\qquad u\in \Vdecint\ . \label{eq:claimsecsingle}
\end{align}

Combining (<ref>) with (<ref>) gives the claim (<ref>).

The claim for $s^{*}$ can be proved in an analogous manner using (<ref>).

We now argue that the sets $m\subset \Edec$ and $m^*\subset \Edecdual$ computed
in Step <ref>
of Algorithm <ref> can be considered to be proxys for the sets $\supp(E^Z)\subset \Edec$ and $\supp(E^X)\subset \Edecdual$. More precisely, we may define
Pauli errors

\begin{align}
\begin{matrix}
\widehat{E}^X&=&X(m^*)\\
\widehat{E}^Z&=&Z(m)\ .
\end{matrix}\label{eq:widehatexzex}
\end{align}

We note that by definition of $m$ and $m^*$ as boundaries of subsets of edges in the graph $\Tdec$ and $\Tdecdual$, respectively,  and the definition of these graphs, neither $m$ nor $m^*$ contains the qubit $q$. Thus

\begin{align}
\{q\}\cap \supp(\widehat{E}^X)&=\{q\}\cap \supp(\widehat{E}^Z)=\emptyset\ .\label{eq:nosupportonqhatXhatz}
\end{align}

We trivially have

\begin{align}
\end{align}
by the definition (<ref>) of these operators, and it  follows immediately from the
definition of $m$ and $m^*$
that $(\widehat{E}^X,\widehat{E}^Z)$
satisfy constraints analogous to   the constraints (<ref>), (<ref>)   obeyed by $(E^X,E^Z)$, i.e.,  we have

\begin{align}
s &= \partial\supp(\widehat{E}^Z)\\
s^{*} &= \partial^*\supp(\widehat{E}^X)\ .
\end{align}

Thus $\widehat{E}:=\widehat{E}^X\widehat{E}^Z$ is an error consistent with the observed syndrome $(s,s^*)$ with the property that
$\widehat{E}^Z$ and $\widehat{E}^X$
each are minimum weight matchings in $\Tdec$ and $\Tdecdual$, respectively.

Because the error $\widehat{E}$ can be computed from the measurement outcomes, this motivates using the pair $\left(
\syn(S^X,\widehat{E}),
\syn(S^Z,\widehat{E})
\right)$ as an estimate for
\syn(S^X,E),
\syn(S^Z,E)
\right)$.  Indeed, this is the reasoning underlying the definition

\begin{align}
\begin{matrix}
\hat{s}^X&:=&\ztwoinner{\cL_X}{m}\\
\hat{s}^Z&:=&\ztwoinner{\cL_Z^*}{m^{*}}
\end{matrix}\label{eq:hatsxszdefclaimsingle}
\end{align}

in  Step <ref> of the algorithm: It is easy to check that $(\hat{s}^X,\hat{s}^Z)$ defined in this way satisfy

\begin{align}
\begin{matrix}
\hat{s}^X&=&\syn(S^X, \widehat{E})\\
\hat{s}^Z&=&\syn(S^Z, \widehat{E})\
\end{matrix}\label{eq:sxszhatconseqsingle}
\end{align}

because of Expressions (<ref>), (<ref>): Indeed, we have for example

\begin{align}
\syn(S^X,\widehat{E})&=\syn\left(X(\cL_X)X_qX_R,\widehat{E}^X\widehat{E}^Z\right)\\
\end{align}

where we used the definition (<ref>) in the first step, and the fact that $\hat{E}^Z$ has no support on $\{q,R\}$ in the second step (cf. (<ref>)).
Identity (<ref>) shows that the pair $(\hat{s}^X,\hat{s}^Z)$ is a natural estimate for
the bits $\left(\syn(S^X,E),\syn(S^Z, E)\right)$, the idea being  that $\widehat{E}$ is a decent estimate of $E$.

Having motivated the algorithm, let us show that Algorithm <ref> produces a Bell state $\Phi_{(\alpha,\beta)}$. Below, we will use the expressions for $(\alpha,\beta)$ computed here below to analyze the success probability of the protocol (i.e., the probability that $(\alpha,\beta)=(0,0)$) for local stochastic noise.

Let $E=E^XE^Z$ be an arbitrary Pauli operator on $(\mathbb{C}^2)^{\otimes \mathcal{C}}$.
Suppose Algorithm <ref> is executed
with an auxiliary qubit system $R$
and the initial state $
\ket{\Psi_{\textrm{in}}}$ specified by (<ref>), i.e., the (half-encoded)
Bell state $\Phi_{\cC R}$ corrupted by the error $E$.
Then the output
of   Algorithm <ref> on qubits $q,R$
is the Bell state $\ket{\Phi_{(\alpha,\beta)}}$, where

\begin{align}
\alpha &= \ztwoinner{\{q\}}{\supp(E^Z)} \oplus \ztwoinner{\supp(E^Z) \oplus \mmatch(\partial \supp(E^Z))}{\cL_X} \qquad \textrm{ and }\\
\beta  &= \ztwoinner{\{q\}}{\supp(E^X)} \oplus \ztwoinner{\supp(E^X) \oplus \mmatch^*(\partial \supp(E^X))}{\cL_Z^*}\ .
\label{eq:Ldecodingsuccesscondition}
\end{align}

We first show that the output is the Bell state $\Phi_{(\alpha,\beta)}$ with

\begin{align}
\alpha &= \ztwoinner{\{q\}}{\supp(E^Z)} \oplus \ztwoinner{\supp(E^Z) \oplus m}{\cL_X} \qquad \textrm{ and }\\
\beta  &= \ztwoinner{\{q\}}{\supp(E^X)} \oplus \ztwoinner{\supp(E^X) \oplus m^{*}}{\cL_Z^*}
\label{eq:toproveqexezmstar}
\end{align}

where $m\subset \Edec$ and $m^*\subset \Edecdual$ are the minimum matchings computed in Step <ref> of the algorithm.

According to Lemma <ref>, the
post-measurement state
after Step <ref>
of Algorithm <ref> is the Bell state $\ket{\Phi_{(c_X,c_Z)}}$

\begin{align}
c_X&=  \ztwoinner{x}{\cL_X}\oplus \syn(S^X, E)\\
c_Z&=  \ztwoinner{z}{\cL_Z^*}\oplus  \syn(S^Z, E)\ .
\end{align}

Since the algorithm applies
the correction operation $Z^{\hat{c}_X}X^{\hat{c}_Z}$
in Step <ref>, the output of the algorithm is  the Bell state $\ket{\Psi_{(c_X\oplus\hat{c}_X,c_Z\oplus\hat{c}_Z)}}$. It follows with the definition of $(\hat{c}_X,\hat{c}_Z)$ in Step <ref>,

\begin{align}
\hat{c}_X &= \ztwoinner{x}{\cL_X} \oplus \hat{s}^X\\
\hat{c}_Z&=\ztwoinner{z}{\cL_Z^*} \oplus \hat{s}^Z
\end{align}

the output is the Bell state $\ket{\Phi_{(\alpha,\beta)}}$ where

\begin{align}
\alpha &= \hat{s}^X \oplus \syn(S^X,E) \qquad \textrm{ and } \\
\beta &= \hat{s}^Z \oplus \syn(S^Z,E)\ .
\end{align}

The claim (<ref>) now follows by combining the expressions (<ref>), (<ref>) for $\left(\syn(S^X,E),\syn(S^Z,E)\right)$    from Lemma <ref>      with the
Definitions (<ref>) of $(\hat{s}^X,\hat{s}^Z)$ used in  Step <ref> of the algorithm.

The claim of the theorem now follows
by combining (<ref>) with the fact that

\begin{align}
m&= \mmatch(s)=\mmatch(\partial \supp(E^Z))\\
m^* &=\mmatch^*(s^{*})=\mmatch^*(\partial^* \supp(E^X))\
\end{align}

by the definition of $(m,m^*)$, and the expressions for $(s,s^*)$ established in  Lemma <ref>.

§.§ Bounds on the resilience functions  for $\Tdec$ and $\Tdecdual$

Here we establish the following bounds on the resilience functions of interest:

Consider the graph $\Tdec$  with internal vertices $\Vdecint$ defined by (<ref>), see Fig. <ref>.
Let $\cL_X\subset \Edec$ be the subset of edges on the vertical strip in Fig. <ref> (cf. (<ref>)).
Then the resilience function $\res_{\cL_X}$ satisfies

\begin{align}
\res_{\cL_X}(p)&\leq 54p \label{eq:upperboundresiliencefunctiontdec}
\end{align}

for any $p\in \interval{0}{\frac{1}{144}}$.

Consider a simple closed loop $L\in Z_\circ(\Tdec)$.
Clearly, the definition of $\cL_X$ implies that $L$ and $\cL_X$ have no overlap.
In particular, $\ztwoinner{L}{\cL_X}=0$, implying that closed loops do not contribute to the resilience function $\res_{\cL_X}$ in this case.

To describe the set $\Zpathext(\Tdec)$ of simple paths with endpoints in $\Vdecext$ through internal vertices, we label the external vertices in $\Vdecext$ as

\begin{align}
\Vdecext&=\left\{u_1,\ldots,u_{d-1},v_1,\ldots,v_{d-1}\right\}\ ,
\end{align}

see Fig. <ref>.
Explicitly, the external vertices are

\begin{align}
u_j = (0, 2j), \quad v_j = (2, 2j) \qquad \textrm{ for } \qquad j = \{1, \dots, d-1\} \ .
\end{align}

Clearly, a simple path $P\in \Zpathext(\Tdec)$ with endpoints in $\Vdecext$ through internal vertices satisfies $\ztwoinner{P}{\cL_X}=1$ if and only if
$P$ starts at $u_j$ (with $j\in \{1,\ldots,d-1\}$) and ends at $v_k$ (with $k\in \{1,\ldots,d-1\}$).
For $j\in \{1,\ldots,d-1\}$ and $\ell\in \mathbb{N}$, let $\Delta(u_j,\ell)$ be the set of all such paths $P \in \Zpathext(\Tdec)$ of length $\ell$ that start at $u_j$ and end at some vertex in the set $\{v_k\}_{k=1}^{d-1}$.
Then we have

\begin{align}
\res_{\cL_X}(p)&=\sum_{\ell=1}^\infty \binom{\ell}{\lceil \ell/2\rceil}\cdot
|\bigcup_{j=1}^{d-1}\Delta(u_j,\ell)|\cdot p^{\lceil \ell/2\rceil}\\
&=\sum_{j=1}^{d-1}\sum_{\ell=L^{\min}_j}^{L^{\max}_j} \binom{\ell}{\lceil \ell/2\rceil}\cdot
|\Delta(u_j,\ell)|\cdot p^{\lceil \ell/2\rceil}\ .\label{eq:deltaformofresLx}
\end{align}

because $\Delta(u_j,\ell)$ and $\Delta(u_{j'},\ell)$ are disjoint for $j\neq j'$ since correspondings paths have distinct starting points $u_j\neq u_{j'}$.
Here $L^{\min}_j$ and $L^{\max}_j$ are the minimal and maximal lengths of a simple path $P \in \Zpathext(\Tdec)$ starting at $u_j$ and ending in $\{v_k\}_{k=1}^{d-1}$ without touching any other external vertices.

The set $\Delta(u_1,1)$ consists of a single path, i.e., $|\Delta(u_1,1)|=1$. For $j\in \{2,\ldots,d-1\}$, we use that the graph $T_{dec}$ has vertices of degree at most $4$, which implies that

\begin{align}
|\Delta(u_j,\ell)|\leq 3^{\ell-1}\qquad\textrm{ for all }\qquad \ell\in\mathbb{N}\ .
\end{align}

This is because any path $P\in \Delta(u_j,\ell)$ has
the same first edge (connected to $u_j$), and there are  at most $3$ choices for each of the remaining edges.)  Furthermore, it is clear that

\begin{align}
L_j^{\min}\geq j\ .
\end{align}

We conclude  (where for $\ell>1$, we use the inequalities $p^{\lceil \ell/2\rceil}\leq p^{\ell/2}$ and
$\binom{\ell}{\lceil\ell/2 \rceil}\leq 2^\ell$) that

\begin{align}
\res_{\cL_X}(p)&\leq p+\sum_{j=2}^{d-1}\sum_{\ell=j}^{L_j^{\max}} 2^\ell 3^{\ell-1} p^{\ell/2}\\
&\leq p+\frac{1}{3}\sum_{j=2}^{d-1}\sum_{\ell=j}^{\infty} q^\ell\qquad\textrm{ where }\qquad q:=6\sqrt{p}\\
&=\frac{q^2}{6}+\frac{q^2-q^d}{3(1-q)^2} \\
&\leq p + \frac{4}{3}\left(q^2 - q^d\right) \\
&\leq p + \frac{4}{3} \cdot \left(6 \sqrt{p}\right)^2\\
&\leq 54p \ .
\end{align}

Here we used the fact $q \leq 6 \sqrt{\frac{1}{144}} = \frac{1}{2}$ and that $\frac{1}{1-q} \leq 2$.

A similar bound applies to the dual decoding graph $\Tdecdual$.

Consider the dual graph $\Tdecdual$  with internal vertices $\Vdecdualint$ defined by (<ref>), see Fig. <ref>.
Let $\cL_Z^{*} \subset \Edecdual$ be the subset of edges on the horizontal strip in Fig. <ref> (cf. (<ref>)).
Then the resilience function $\res_{\cL_Z^{*}}$ satisfies

\begin{align}
\res_{\cL_Z^{*}}(p)&\leq 38p \label{eq:upperboundresiliencefunctiontdecdual}
\end{align}

for any $p \in \interval{0}{\frac{1}{144}}$.

The proof is analogous to that of Lemma <ref>. We include it in Appendix <ref> for completeness.

§.§ A bound on single-shot decoding under local stochastic noise

Consider a distance-$d$ surface code of $\abs{\cC}=2d^2-2d+1$ qubits with $d\geq 2$ and logical operators $\overline{X}=\prod_{j\in \cL_X\cup \{q\}}X_j$ and $\overline{Z}=\prod_{j\in\cL_Z\cup\{q\}}$.
Let $\ket{\overline{0}}$ and $\ket{\overline{1}}$ be code states to eigenvalues $+1$ and $-1$ of $\overline{Z}$. Let

\begin{align}
\begin{matrix}
V:&\mathbb{C}^2 & \mapsto & \left( \mathbb{C}^{2} \right)^{\otimes \cC}\\
& \alpha\ket{0}+\beta\ket{1} & \mapsto & \alpha\ket{\overline{0}}+\beta\ket{\overline{1}}\
\end{matrix}
\end{align}

be an isometric encoding map, and let

\begin{align}
\begin{matrix}
\cE: & \cB(\mathbb{C}^2) & \rightarrow & \cB( \left( \mathbb{C}^{2} \right)^{ \otimes \cC} )\\
& \rho & \mapsto & V \rho V^{\dagger}
\end{matrix}
\end{align}

be an encoding channel associated with $V$.
For any state $\rho\in\cB(\mathbb{C}^2)$, the state $\cE(\rho)$  is the corresponding encoded (logical) state.

We  describe what single-shot decoding protocol achieves in terms of its logical action. For this purpose, let us define the  single-qubit
random Pauli channel

\begin{align}
\cP_\nu(\rho):=\nu_0 \rho +\nu_1 X\rho X^\dagger +\nu_2 Y\rho Y^\dagger +\nu_3 Z\rho Z^\dagger\ .
\end{align}

for any  probability distribution $\nu=(\nu_0,\nu_1,\nu_2,\nu_3)$, $\nu_j\geq 0$ and $\sum_{j=0}^3 \nu_j=1$.

For $p\in [0,1]$, let
$E\sim \cN(p)$ be a local stochastic error with parameter $p$. This defines a “noise channel” $\Lambda_p$ by

\begin{align}
\begin{matrix}
\Lambda_p:&\cB((\mathbb{C}^2)^{\otimes \cC})&\rightarrow &\cB((\mathbb{C}^2)^{\otimes \cC})\\
& \rho & \mapsto & \Lambda_p(\rho):=\sum_{E_0\textrm{ Pauli on }(\mathbb{C}^2)^{\otimes \cC}}\Pr\left[E=E_0\right]E_0\rho E_0^\dagger
\end{matrix}\label{eq:localstochasticnoisechanneldefb}
\end{align}

be the CPTP map that applies the error $E$ to a state. Finally, let $\cD:\cB((\mathbb{C}^2)^{\otimes \cC})\rightarrow \cB((\mathbb{C}^2)^{\{q\}})$ be the CPTP map corresponding to an ideal execution of Algorithm <ref>. Then the following holds:

Consider local stochastic noise as expressed by a CPTP map $\Lambda_p$ of the form (<ref>), with noise strength

\begin{align}
p\leq \frac{1}{144}\ .
\end{align}

There is a probability distribution $\nu=(\nu_0,\nu_1,\nu_2,\nu_3)$ over $(I,X,Y,Z)$ such that the following holds:

* Suppose we run algorithm <ref> on the noisy encoded  state $\Lambda_p \circ \cE (\rho)$, where
$\rho\in \cB(\mathbb{C}^2)$ is an arbitrary single-qubit state.
Then the resulting output state $\cD\circ\Lambda_p\circ \cE(\rho)$ on qubit $q$ is the state $\cP_\nu(\rho)$.

* We have $1-\nu_0\leq 94p$.

In particular, Theorem <ref> implies that applying Algorithm <ref>
to any encoded pure state $\Lambda_p(V\ketbra{\Psi}V^{\dagger})$ corrupted by $\Lambda_p$ yields an output state $\rho_{\textrm{out}}=\cD\circ\Lambda_p\circ \cE(\proj{\Psi})$ with overlap at least

\begin{align}
\bra{\Psi}\rho_{\textrm{out}}\ket{\Psi}\geq \nu_0\geq 1- 94p
\end{align}

with the original state.

Let us denote by $L\cong\mathbb{C}^2$ the “logical qubit” to be encoded, and let  $R\cong\mathbb{C}^2$ be a reference system. We consider the action of the noise
and the decoding protocol when applied to the two-qubit Bell state $\Phi_{RL}:=\Phi_{(0,0)}$, i.e., we compute the Choi-Jamiolkowski state

\begin{align}
J_{Rq}:=(\mathsf{id}_R\otimes \cD\circ\Lambda_p\circ \cE)(\Phi_{RL})\ .
\end{align}

Observe that $\Phi'_{R\cC}:=(\mathsf{id}_R\otimes \cE)(\Phi_{RL})$ is the half-encoded Bell state by definition. It thus follows from Theorem <ref> that

\begin{align}
J_{Rq}:=(\mathsf{id}_R\otimes \cP_{\nu})(\proj{\Phi_{(0,0)}})\label{eq:Jrqexpression}
\end{align}

for a probability distribution $\nu=(\nu_0,\nu_1,\nu_2,\nu_3)$ over $(I,X,Y,Z)$. In this expression, $\nu_0$ is the probability that the condition (<ref>) is satisfied.  Because of the Choi-Jamiolkowski isomorphism, Eq. (<ref>) shows that the channel $\cD\circ\Lambda_p\circ\cE=\cP_{\nu}$ is a random Pauli channel. It thus remains to establish an upper bound on $1-\nu_0$.

Let us introduce the following four random variables:

\begin{align}
B_Z&=\ztwoinner{\supp(E^Z) \oplus \mmatch(\partial \supp(E^Z))}{\cL_X}\\
B_X&:=\ztwoinner{\supp(E^X) \oplus \mmatch^*(\partial \supp(E^X))}{\cL_Z^*}\ .
\end{align}

Then (<ref>) translates to

\begin{align}
\nu_0&=\Pr\left[(A_Z,B_Z)\in \{(0,0),(1,1)\}\textrm{ and }(A_X,B_X)\in \{(0,0),(1,1)\}\right]\ .
\end{align}

The union bound gives

\begin{align}
1-\nu_0 &\leq \Pr\left[(A_Z,B_Z)\in \{(0,1),(1,0)\}\right]+\Pr\left[(A_X,B_X)\in \{(0,1),(1,0)\}\right]\ .
\end{align}

Again using the union bound, we have

\begin{align}
\Pr\left[(A_Z,B_Z)\in \{(0,1),(1,0)\}\right]&\leq \Pr\left[(A_Z,B_Z)=(0,1)\right]+\Pr\left[(A_Z,B_Z)=(1,0)\right]\\
&\leq \Pr\left[B_Z=1\right]+\Pr\left[A_Z=1\right]\ .
\end{align}

Applying the same reasoning to $(A_X,B_X)$, we conclude that

\begin{align}
1-\nu_0 & \leq\Pr\left[A_X=1\right] +\Pr\left[A_Z=1\right]+\Pr\left[B_X=1\right]+\Pr\left[B_Z=1\right]\ .
\end{align}

By definition, we have

\begin{align}
\Pr\left[A_Z=1\right]&=\Pr\left[\ztwoinner{\{q\}}{\supp(E^Z)}=1\right]\\
&\leq p
\end{align}

where we used that $E^Z\sim\cN(p)$ is local stochastic noise with the same parameter $p$ as $E$. By similar reasoning, we have

\begin{align}
\Pr\left[A_X=1\right]&\leq  p\ .
\end{align}

Furthermore,  we have

\begin{align}
\Pr\left[B_Z=1\right]&=\Pr\left[\ztwoinner{\supp(E^Z) \oplus \mmatch(\partial \supp(E^Z))}{\cL_X}=1\right]\\
&\leq \mathsf{res}_{\cL_X}(p)\\
&\leq 54p
\end{align}

where we used the definition of $A_Z$, the fact that $E^Z\sim\cN(p)$ and Proposition <ref>, as well as the upper bound (<ref>).  Similarly, we have

\begin{align}
\Pr\left[B_X=1\right]&\leq \mathsf{res}_{\cL_Z^{*}}(p)\\
&\leq 38 p \ .
\end{align}

Combining these inequalities, we obtain

\begin{align}
1-\nu_0& \leq  p + p + 38p + 54p \\
& \leq 94p
\end{align}

as claimed.

§ ENTANGLEMENT GENERATION FROM A NOISY 3D CLUSTER STATE

In the following, we describe a protocol for generating a two-qubit Bell state in a noise-robust fashion. It is based on the cluster state $W\ket{0^{\cC}}$ on a 3D lattice $\cC$, a state which can be generated by a depth-$6$ circuit $W$.  This state is measured using single-qubit measurements on all but two qubits. Based on the measurement outcomes, a certain correction operation is applied to one of the remaining two qubits.

In Section <ref> we discuss the relevant definitions underlying the cluster state. In Section <ref>
we describe the single-qubit measurement pattern used in the protocol. Section <ref> introduces certain subgraphs of the cluster state lattice and additional data such as  distinguished subsets of qubits having to do with the encoded logical information. These  are relevant  for the definition of certain decoding functions used in the protocol.

Section <ref> identifies certain stabilizers of the graph state that are key to the construction and analysis of the entanglement generation protocol. We give a complete description of the protocol in Section <ref>. Finally, in Section <ref>, we compute the output state of this algorithm when it is run on a noisy cluster state $EW\ket{0^{\cC}}$ which is corrupted by a Pauli error $E$. This will be used to analyze the success probability for local stochastic errors in Section <ref>.

§.§ Cluster state: Definition

Our construction is based on a 3D cluster state. To introduce this state, we mostly follow the conventions of [4] but
use different conventions to describe so-called  dangling edges. Contrary to Ref. [4] we will consider their  degree-$1$ endpoints as regular  vertices.

Let $d \geq 2$ and let $R\geq 3$ be an odd integer. Consider the set

\begin{align}
\Cprime[d\times d \times R] := \{(u_1, u_2, u_3) \in \mathbb{Z}^3 \mid 0 \leq u_1 \leq 2d,~ 0 \leq u_2 \leq 2d-2,~ 1 \leq u_3 \leq R\}
\end{align}

(From the perspective of coding, the integers $d$ and $R$ are associated with the distance $d$ of a surface code, and a “cluster state distance” $\frac{R+1}{2}$, respectively.) In the following, we simply write $\Cprime = \Cprime[d\times d \times R]$.
Elements $(u_1,u_2,u_3)\in \Cprime$ will be referred to as sites.

Qubits are located at each site belonging to the subset

\begin{align}\label{eq:defcCddR}
\cC[d \times d \times R]  := \{u \in \Ctilde \mid 1 \leq u_1 \leq 2d-1\} \setminus \left\{ (o,o,o), (e,e,e) \right\} \subset \Ctilde
\end{align}

where each $e~(o)$ refers to any even (odd) integer. The set $\cC=\cC = \cC[d \times d \times R]$ is called the cluster state lattice of the form $d \times d \times R$.  We will refer to a site $u\in \cC$ interchangeably as site $u$ or qubit $u$.
In the following, we use the convention that e.g.,
$\{(e,e,R)\}\subset\Cprime$  denotes the set of all $(u_1,u_2,u_3)\in \Cprime$ with $u_1,u_2$ even and $u_3=R$.

Given a site $u\in \Cprime$, the set of nearest  neighbors of $u$ is defined as

\begin{align}
\neigh(u) = \left\{v \in \mathcal{C} \mid
d(u,v)=1 \right\}\qquad\textrm{ where }\qquad d(u,v):=\sum_{i=1}^3 \abs{u_i - v_i}\ ,\label{eq:nearestneighborset}
\end{align}

i.e., the  nearest neighbors of $u$ are associated with qubits at Manhattan distance $1$ from $u$. Because elements of $\Cprime \setminus \cC$ are excluded in (<ref>), any  qubit $u\in\cC$ has at most four nearest neighbor qubits.

The cluster state of interest is associated with the graph whose vertex set is $\cC$, and where
the set of edges consists of pairs $\{u,v\}$ with $v\in \neigh(u)$, see Fig. <ref> for an illustration of this graph.
It is defined as

\begin{align}
W\ket{0^\cC}\ ,
\end{align}

\begin{align}
W = H(\cC)\left( \prod_{\left\{ u,v \right\}} CZ_{u,v}\right) H(\cC)\ ,
\end{align}

with the product taken over all edges of the graph, i.e., all pairs $u,v\in\cC$ such that $v\in \neigh(u)$.
Here $CZ_{u,v}$ denotes a controlled-$Z$ gate on qubits $u$ and $v$. By definition, the unitary $W$ can be implemented using a depth-$6$ circuit with nearest-neighbor gates. (Note that
our definition of the graph state differs from the more commonly used definition by an additional layer of Hadamard-gates.) The state $W\ket{0^{\cC}}$ is a stabilizer state with stabilizer group generated by

\begin{align}
G_u = Z_u \prod_{v \in \neigh(u)} X_v \qquad \textrm{ with } \qquad u \in \mathcal{C}\ .\label{eq:stabilizergeneratorsgraph}
\end{align}

The graph associated with the three-dimensional cluster state $W\ket{0^{\cC}}$. Each qubit is located at a vertex (sphere) in $\cC$. Measurement pattern used in protocol is illustrated with colors.

As in the case of surface codes, it will also need a dual description. For this, let $\Cprimedual= \Ctildedual[d \times d \times R]$ be the set of dual sites defined as

\begin{align}
\Ctildedual[d \times d \times R]:= \left\{(u_1,u_2,u_3)\in\mathbb{Z}^3\ |\ 1\leq u_1\leq 2d-1\textrm{ and }-1\leq u_2\leq 2d-1\textrm{ and }1\leq u_3\leq R \right\}\ .
\end{align}

Then we can equivalently express the location of qubits as

\begin{align}
\cC^{*} = \{u \in \Ctildedual \mid 0 \leq u_2 \leq r-1\} \setminus \{(o,o,o),(e,e,e)\} \subset \Ctildedual \ ,
\end{align}

i.e., we have $\cC = \cC^{*}$.

§.§ Measurement pattern used in protocol

In this section, we describe the measurement pattern used in our protocol. We partition the set of qubits as $\mathcal{C}=\cA\cup \cB$ where

\begin{align}
\mathcal{B}  &= \{(e,o,1),(o,e,1), (e,o,R), (o,e,R) \in \mathcal{C}\}, \\
\mathcal{A}  &= \mathcal{C} \setminus \mathcal{B}.
\end{align}

The set $\mathcal{B}$ is the union of $\{(e,o,1),(o,e,1)\}$, i.e., a subset of all qubits at the “front” layer (i.e., with $u_3=1$) of $\cC$, and  $\{(e,o,R),(o,e,R)\}$, a subset of all qubits at the “back” layer (i.e., with $u_3=R$) of $\cC$. In prior work [48, 4],
no measurements were applied to these qubits; instead, long-range encoded entanglement between two surface codes of distance $d$ associated with these front- and back-layer qubits was established.

The remaining qubits $\{(e,e,1)\}$ in the front layer are omitted from $\cB$ but belong to $\cA$. Similarly, qubits $\{(e,e,R)\}$ in the back layer belong to $\cA$. These are auxiliary qubits whose measurement (specified below) reveals information about the associated surface code stabilizers in the corresponding layer. Similarly, the measurement results associated with the remaining qubits of $\cA$ belonging to the “bulk” reveal information about the logical error of the encoded surface code state (or, in our scheme, the final two-qubit entangled state).

As in [48, 4], all qubits belonging to $\cA$ are measured in the $Z$-basis. Because our goal is to establish entanglement between two (physical) qubits, we additionally measure all qubits in $\cB$, except for two qubits

\begin{align}
\end{align}
belonging to the front and back layers, respectively.  Our protocol generates a Bell state between these two qubits.

The measurement pattern for the front layer qubits of $\cB$ mirrors the single-shot decoding procedure for the surface code: Qubits belonging to the upper left triangular region are measured in the $X$-basis, whereas qubits situated inside the lower right triangular region are measured in the $Z$-basis. Qubits in the back layer of $\cB$ are measured with an analogous pattern.  Formally, the sets of qubits in $\cB \setminus \{q_1, q_2\}$ measured in the $X$- respectively $Z$-basis are

\begin{align}
\cX &= \{(u_1, u_2, u_3) \in \mathcal{B} \setminus \{q_1,q_2\} \mid u_2 \geq 1 + u_1\}\\
\cZ &= \{(u_1, u_2, u_3) \in \mathcal{B} \setminus \{q_1,q_2\} \mid u_2 < 1 + u_1\}\ .
\end{align}

The measurement outcome will be denoted by $(a,x,z)$, where

\begin{align}
a &\in \{0,1\}^{\cA} \\
x &\in \{0,1\}^{\Xcl} \\
z &\in \{0,1\}^{\Zcl} \
\end{align}

are the measurement results associated with the qubits belonging to $\cA$, $\Xcl$ and $\Zcl$, respectively.
This completes the description of the measurements used in the protocol, see Fig. <ref>.

§.§ Subgraphs, recovery graphs and internal vertices

In this section, we introduce various subgraph of the cluster state lattice. We also
define certain subsets of qubits that are relevant for our entanglement generation protocol.

Specifically, in Section <ref>,
we introduce the “glued graph”  $\Tgl$,
as well as the “dual glued graph” $\Tgldual$. They are obtained by gluing together surface code graphs respectively dual surface code graphs with the cluster state lattice. These graphs are at the basis of our entanglement generation protocol, and clarify the relationship to the single-shot decoding procedure for the surface code discussed in Section <ref>.

In Section <ref>, we then introduce the decoding graph $\Tcldec$ and its  dual counterpart $\Tcldecdual$. In Section <ref>, we additionally define certain subsets of their edges, the so-called recovery sets. We also identify the associated internal vertices. Our entanglement generation protocol involves  solving corresponding matching problems.

§.§.§ Glued graphs

We introduce certain graphs in $\Ctilde$ and their dual in $\Ctildedual$ as discussed in [4].
Those graphs are  subgraphs or supergraphs of certain graphs that will be introduced in Section <ref>.

We first define an “even graph” $\Teven = (\Veven, \Eeven)$ in $\Ctilde$.
The set $\Veven = \Vcirceven \cup \Vdangeven$ of vertices has two disjoint subsets

\begin{align}
\Vcirceven &= \{u \in \{(e,e,e)\} \mid 2 \leq u_2 \leq 2d - 2\} \subset \Ctilde \qquad \textrm{ and } \\
\Vdangeven &=\{u \in \left\{ (e,e,1), (e,e,R) \right\} \mid u_1 \not \in \{0, 2d\}\} \cup \{(0,e,e)\}\cup \{(2d,e,e)\} \subset \Ctilde \ .
\end{align}

Here we avoid the terminology of dangling edges used in [4] and instead collect endpoints of such edges using the vertex set $\Vdangeven$.
We note that $\Vdangeven$ consists of vertices $u = (u_1,u_2,u_3)$ in the “front” ($u_3 = 1$), “back” ($u_3=R$), “left” ($u_1=0$), or “right” ($u_1=2d$) boundary.
Any pair $u,v\in \Veven$ of vertices at distance $d(u,v)=2$ is connected by an edge in $\Teven$, except when $u,v$ both belong to $\Vdangeven$.
Other edges in $\Teven$ are of the form $\{u,v\}$ with

\begin{align}\label{eq:distanceoneedgesinTeven}
u &= (u_1, u_2, u_3) \in \{(e,e,1), (e,e,R)\} \qquad \textrm{ and }\qquad
v= \begin{cases*}
(u_1,u_2,u_3 + 1) & \textrm{ if $u_3 = 1$}\\
(u_1,u_2,u_3 - 1) & \textrm{ if $u_3 = R$} \ .
\end{cases*}
\end{align}

It is easy to check that these edges constitute all pairs of vertices $u, v \in \Veven$ satisfying $d(u,v)=1$.
In summary, the set of edges of $\Teven$ is

\begin{align}
\Eeven &=\left\{\{u,v\} \in \Veven^2 \mid d(u,v)=2\textrm{ and } (u,v)\not\in \Vdangeven\times \Vdangeven\right\} \\
& \quad \cup \left\{ \{u,v\} \in \Veven^2 \mid d(u,v) = 1 \right\} \ .
\end{align}

The “odd graph” $\Todd=(\Vodd, \Eodd)$ in $\Ctildedual$ is a dual version of $\Teven$. The set $\Vodd = \Vcircodd \cup \Vdangodd$ of vertices consists of  two disjoint subsets

\begin{align}
\Vcircodd &= \{u \in \{(o,o,o)\} \mid u_2 \not \in \{-1, r\}, u_3 \not \in \{1, R\}\} \subset \Ctildedual \qquad \textrm{ and } \\
\Vdangodd &=\{u \in \left\{ (o,o,1), (o,o,R) \right\} \mid u_2 \not \in \{-1, r\}\} \cup \{u \in \{(o,-1,o), (o, r,o)\} \mid u_3 \not \in \{1, R\}\} \subset \Ctildedual \ .
\end{align}

We note that $\Vdangodd$ consists of vertices $u = (u_1, u_2, u_3)$ in the “front” ($u_3 = 1$), “back” ($u_3=R$), “top” ($u_2=2d$), or “bottom” ($u_2=-1$) boundary.
The set of edges of $\Todd$ is

\begin{align}
\Eodd = \{\{u,v\} \in \Vodd^2 \mid d(u,v) = 2 \textrm{ and } (u, v) \not \in \Vdangodd \times \Vdangodd\} \ .
\end{align}

The surface code graph $\Tclsc$ has vertices belonging to the set of primal sites $\Cprime$.
It has two connected components lying in the planes $u_3=1$ and $u_3=R$. Each connected component is isomorphic to the surface code graph $\Tsc=(\Vsc,\Esc)$ introduced  in Section <ref>.
Let us simply write

\begin{align}
\Tclsc &=\Tsc\times \{1,R\}\
\end{align}

for this graph to emphasize this fact. In more detail,  we have

\begin{align}
\Vclsc &=\left(\bigcup_{(u_1,u_2)\in \Vsc} \{(u_1,u_2,1)\}\right)\cup \left(\bigcup_{(u_1,u_2)\in \Vsc} \{(u_1,u_2,R)\}\right)\\
\Eclsc&=
\left(\bigcup_{
{\tiny \begin{matrix}
\{(u_1, u_2), (v_1, v_2)\}\in \Esc \end{matrix}}}
\Bigl\{
\left\{(u_1,u_2,1),(v_1,v_2,1)\right\}
\Bigr\}
\right)
\cup
\left(\bigcup_{
{\tiny \begin{matrix}
\{(u_1, u_2), (v_1, v_2)\}\in \Esc \end{matrix}}}
\Bigl\{
\left\{(u_1,u_2,R),(v_1,v_2,R)\right\}
\Bigr\}
\right) \ .
\end{align}

The graph $\Tclscdual$ similarly consists of two copies of the dual surface code graph $\Tsc$ located in the planes $u_3=1$ and $u_3=R$, respectively, which we express as

\begin{align}
\Tclscdual &=\Tscdual\times \{1,R\}\ .
\end{align}

Written out, this means that

\begin{align}
\Vclscdual &=\left(\bigcup_{(u_1,u_2)\in \Vscdual} \{(u_1,u_2,1)\}\right)\cup \left(\bigcup_{(u_1,u_2)\in \Vscdual} \{(u_1,u_2,R)\}\right)\\
\Eclscdual&=
\left(\bigcup_{
{\tiny \begin{matrix}
\{(u_1,u_2),(v_1,v_2)\}\in \Escdual\end{matrix}}}
\left\{(u_1,u_2,1),(v_1,v_2,1)\right\}\right)
\cup
\left(\bigcup_{
{\tiny \begin{matrix}
\{(u_1,u_2), (v_1,v_2) \}\in \Escdual\end{matrix}}}
\left\{(u_1,u_2,R),(v_1,v_2,R)\right\}\right)\ .
\end{align}

Now we are able to introduce a certain “glued graph” $\Tgl=(\Vgl,\Egl)$,
as well as a “dual glued graph” $\Tgldual=(\Vgldual,\Egldual)$, in terms of the subgraphs $\Teven$, $\Tclsc$, $\Todd$, and $\Tclscdual$, see Fig. <ref>.

The glued graph $\Tgl$ as a union of two subgraphs: $\Teven$ (gray) and $\Tclsc$ (green).

The dual glued graph $\Tgldual$ as a union of two subgraphs: $\Todd$ (gray) and $\Tclscdual$ (green).

The glued graph $\Tgl = \Teven \cup \Tclsc$ and the dual glued graph $\Tgldual = \Todd \cup \Tclscdual$.

The glued graph $\Tgl$ is obtained by  attaching the surface graph $\Tclsc$ to the even graph $\Teven$; here the two copies of the surface code
end up being connected to the rough front- and back boundaries of the even graph $\Teven$. The graph $\Tgl$ is formally defined by setting

\begin{align}
\Vgl &=\Veven\cup \Vclsc\\
\Egl &=\Eeven\cup \Eclsc\ .
\end{align}

We denote this construction simply by

\begin{align}
\Tgl&=\Teven\cup \Tclsc\ .
\end{align}

The  “dual glued graph” $\Tgldual=(\Vgldual,\Egldual)$ is defined by
gluing the dual surface graph $\Tclsc$ to  the odd graph $\Todd$, i.e.,

\begin{align}
\Tgldual &=\Todd\cup \Tclscdual\ .
\end{align}

§.§.§ Decoding subgraphs

In the following, we describe how to process the measurement results in order to determine a suitable correction operation on the post-measurement on qubits $\{q_1,q_2\}$ to obtain the Bell state $\Phi$.
More precisely, the correction is a Pauli operator of the form $Z^{\hat{c}_X}X^{\hat{c}_Z}$, where $\hat{c}_X$ and $\hat{c}_Z$ are computed from the single-qubit measurements results by a classical computation we describe below.
The computation of $\hat{c}_X$  requires finding a minimal matching of a subset of marked vertices on a certain “decoding” graph $\Tcldec$ with interior and exterior vertices.
The computation of $\hat{c}_Z$ proceeds in a similar “dual” manner and involves a “dual decoding graph” $\Tcldecdual$, see Fig. <ref> for an illustration of these graphs.

The graphs $\Tcldec$ and $\Tcldecdual$ play a central role in our protocol:  We will  relate the edges of the  graphs $\Tcldec$ and $\Tcldecdual$ with the measured qubits. We will argue how the measurement results  determine certain subsets of edges in these two graphs. These subsets are used  to obtain certain subsets of marked vertices (by taking  boundaries). The pair  $(\hat{c}_X,\hat{c}_Z)$ is computed from these subsets of marked vertices.

3|c| $\Tcldec=\left(\Vcldec, \Ecldec\right)$

subsets of $\Ecldec$     color     measurement

$\cLXcl \cap \cA$     1.2cm0.3cm     $Z$-basis

$\left(\Ecldec \setminus \cLXcl \right) \cap \cA$    1.2cm0.3cm     $Z$-basis

$\cLXcl \cap \cX$     1.2cm0.3cm     $X$-basis

$\left(\Ecldec \setminus \cLXcl \right) \cap \cX$     1.2cm0.3cm     $X$-basis

3|c| $\Tcldecdual=\left(\Vcldec, \Ecldec\right)$

subsets of $\Ecldecdual$     color     measurement

$\cLZcl \cap \cA$     1.2cm0.3cm     $Z$-basis

$(\Ecldecdual \setminus \cLZcl)\cap \cA$     1.2cm0.3cm     $Z$-basis

$\cLZcl \cap \cZ$     1.2cm0.3cm     $Z$-basis

$(\Ecldecdual \setminus \cLZcl) \cap \cZ$     1.2cm0.3cm     $Z$-basis

The decoding graph $\Tcldec$  as well as the dual decoding graph $\Tcldecdual$. External vertices  $\Vcldecext$ and $\Vcldecdualext$ (black spheres) and internal vertices $\Vcldecint$ and $\Vcldecdualint$ (white spheres) are illustrated.
The tables describe in which basis qubits corresponding to the edges are measured.

The decoding graph $\Tcldec=(\Vcldec,\Ecldec)$ is the result of gluing two copies of the subgraph $\Tdec\subset \Tsc$  (instead of two copies of the entire graph $\Tsc$) to $\Teven$, see Fig. <ref>.
By construction, the resulting decoding graph $\Tcldec$ is a subgraph of $\Tgl$. Concisely, we have

\begin{align}
\Tcldec &= \Teven\cup \left(\Tdec\times  \{1,R\}\right)\subset \Tgl\ .\label{eq:tcldecdef}
\end{align}

The dual decoding graph $\Tcldecdual=(\Vcldecdual,\Ecldecdual)$ is a subgraph of the dual glued graph $\Tgldual$ and is  defined in a similar manner by

\begin{align}
\Tcldecdual &= \Todd\cup \left(\Tdecdual\times  \{1,R\}\right)\subset \Tgldual\ ,\label{eq:tcldecdualdef}
\end{align}

see Fig. <ref>.

We explain the relationship between the qubits that are measured  and the edges of the graphs $\Tcldec$ and $\Tcldecdual$ using a bijection

\begin{align}
\Lambda : \Ecldec \cup \Ecldecdual \to \cC \setminus \{q_1, q_2\} \ .
\end{align}

called the “labeling” map. The map $\Lambda$ identifies  each edge of the graphs $\Tcldec$ and $\Tcldecdual$ with  the site of a qubit located at the midpoint of the edge or at one of the vertices adjacent to the edge: Let $e=\{u,v\}\in \Ecldec \cup \Ecldecdual $ be one of edges of the graphs $\Tcldec$ and $\Tcldecdual$.
If $d(u,v) = 2$, then $\Lambda$ maps the edge $e$ to the midpoint $\Lambda(e)=\frac{u+v}{2}$  of the vertices $u$ and $v$.
Otherwise, i.e., if $d(u,v)\neq 2$, then we must have $d(u,v)=1$ and it follows that $e$ belongs to $\Eeven \subset \Ecldec$, and is of the form

\begin{align}\label{eq:shortedgesintcldec}
\{u, v\} &= \begin{cases*}
\{(u_1,u_2,1),(u_1,u_2,2)\} & \textrm{ if $\{u_3,v_3\} = \{1,2\}$}\\
\{(u_1,u_2,R-1),(u_1,u_2,R)\} & \textrm{ if $\{u_3,v_3\} = \{R-1,R\}$}
\end{cases*}& \textrm{ with } \qquad u_1, u_2 \textrm{ even }
\end{align}

as stated in (<ref>) of Section <ref>.
In this case, the edge $e$ is mapped by $\Lambda$ to the site $(u_1,u_2,1)$ if $\{u_3,v_3\}=\{1,2\}$ or the site $(u_1,u_2,R)$ otherwise.
In summary, we can write the map $\Lambda$ as

\begin{equation}
\begin{aligned}\label{eq:defoflabeling}
\Lambda(\{u,v\})= \begin{cases*}
(u_1, u_2, 1) & \textrm{ if $\{u,v\} \in \Ecldec$, $d(u, v) = 1$ and $\{u_3, v_3\} = \{1, 2\}$} \\
(u_1, u_2, R) & \textrm{ if $\{u,v\} \in \Ecldec$, $d(u, v) = 1$ and $\{u_3, v_3\} = \{R-1, R\}$} \\
\left( \frac{u_1+v_1}{2}, \frac{u_2+v_2}{2}, \frac{u_3+v_3}{2} \right) & \textrm{ otherwise.}
\end{cases*}
\end{aligned}
\end{equation}

It is easy to check that the map $\Lambda$ is a bijection.

Using the labeling map $\Lambda$, we can identify each edge of $\Tcldec$ or $\Tcldecdual$ with one of  the measured qubits, or equivalently, the site of the latter. We say an edge $e\in \Ecldec \cup \Ecldecdual$ is labeled by a site $w \in \cC \setminus \{q_1,q_2\}$ if $\Lambda(e) = w$.

With the labeling map $\Lambda$, we have

\begin{align}
\begin{matrix}
\cX&= &\Lambda(\Edec \times \{1,R\}) \\
\cZ&= &\Lambda(\Edecdual \times \{1,R\}) \\
\Lambda(\Ecldec) \cap \cA &=& \Lambda(\Eeven) \\
\Lambda(\Ecldecdual) \cap \cA &=& \Lambda(\Eodd) \ .
\end{matrix}\label{eq:lambdamvs}
\end{align}

Sometimes we simply denote an edge $e$ by the corresponding label $\Lambda(e)$, leaving the map $\Lambda$ implicit. Following this convention  Eq. (<ref>) becomes

\begin{align}
\begin{matrix}
\cX&= &\Edec \times \{1,R\} \\
\cZ&= &\Edecdual \times \{1,R\} \\
\Ecldec \cap \cA &=& \Eeven \\
\Ecldecdual \cap \cA &=& \Eodd \ . \end{matrix}
\end{align}

Because of the definitions (<ref>)
and (<ref>)