# Improved quantum error correction using soft information

Christopher A. Pattison  Caltech, Institute for Quantum Information and
Matter, Pasadena, USA  Michael E. Beverland  Microsoft Quantum and Microsoft
Research, Redmond, USA  Marcus P. da Silva  Microsoft Quantum and Microsoft
Research, Redmond, USA  Nicolas Delfosse  Microsoft Quantum and Microsoft
Research, Redmond, USA

###### Abstract

The typical model for measurement noise in quantum error correction is to
randomly flip the binary measurement outcome. In experiments, measurements
yield much richer information—e.g., continuous current values, discrete photon
counts—which is then mapped into binary outcomes by discarding some of this
information. In this work, we consider methods to incorporate all of this
richer information, typically called soft information, into the decoding of
quantum error correction codes, and in particular the surface code. We
describe how to modify both the Minimum Weight Perfect Matching and Union-Find
decoders to leverage soft information, and demonstrate these soft decoders
outperform the standard (hard) decoders that can only access the binary
measurement outcomes. Moreover, we observe that the soft decoder achieves a
threshold $25\%$ higher than any hard decoder for phenomenological noise with
Gaussian soft measurement outcomes. We also introduce a soft measurement error
model with amplitude damping, in which measurement time leads to a trade-off
between measurement resolution and additional disturbance of the qubits. Under
this model we observe that the performance of the surface code is very
sensitive to the choice of the measurement time—for a distance-19 surface
code, a five-fold increase in measurement time can lead to a thousand-fold
increase in logical error rate. Moreover, the measurement time that minimizes
the physical error rate is distinct from the one that minimizes the logical
performance, pointing to the benefits of jointly optimizing the physical and
quantum error correction layers.

Due to the presence of errors and noise in quantum hardware, quantum error
correction is essential for the scalability and usefulness of quantum
computers [1]. The most promissing approaches to fault-tolerant quantum error
correction revolve around the surface code [2, 3], which tolerates high error
rates and is naturally implemented one a square grid of qubits using only
local gates. Numerical simulations show that the surface code performs well
for a variety of noise models [4], including gates corrupted by stochastic [3,
5] and coherent [6] errors. The error models that are typically considered
include a very simple representation of noisy measurements where binary
measurement outcomes during computations are flipped with some probability.

However, measurements in physical realizations of quantum computers are
rarely, if ever, binary. Measurement outcomes are physically represented by
much richer quantities, such as continuous currents or voltage, and are
converted into binary outcomes by additional processing that discards some
information. This is no different from the classical setting, where
information is similarly represented by currents and voltages (including non-
binary information, such as in the case of flash memories [7]). In classical
error correction, this richer physical representation, often referred to as
soft information (in contrast to the hard or sharp features of of binary
information), is exploited to obtain greater tolerance to errors, or to reduce
the noise required to achieve some logical error rate [8]. This naturally
raises the question of how to extract similar benefits from soft information
in the quantum setting. However, the classical approach of directly measuring
the soft values of all bits and computing parities in noiseless post-
processing cannot be applied to the quantum setting, as it would destroy the
quantum superpositions being protected. Moreover, parities computed with
quantum circuits can propagate errors, since these quantum circuits are noisy.
Fault-tolerant quantum error correction with soft information requires non-
trivial modifications.

This challenge has been partially addressed in systems with continuous
variable encodings of qubits [9, 10, 11, 12, 13, 14]. Here we consider a more
general setting, independent of the physical qubit encoding and grounded on
the conditional distributions of the measurement outcomes. Our main result is
the design of generic soft decoders for the surface code: a soft minimum
weight perfect matching (MWPM) decoder (which we show identifies a most likely
fault set for soft information), and a soft Union-Find (UF) decoder (which is
an approximation to the MWPM decoder, but with comparable performance and low
computational complexity). Both these decoders are modifications of existing
surface code decoders [4, 15], with similar computational overhead, but may
also be applied to other codes [16, 17, 18, 19, 20].

We evaluate the performance of these soft decoders numerically by introducing
concrete measurement error models with soft information: one where the
measurement outcome is correpted by white Gaussian noise (what we call
Gaussian soft noise), and another where the measurement outcome is corrupted
by amplitude damping and Gaussian noise (what we call Gaussian soft noise with
amplitude damping). We observe several remakable properties of the soft UF
decoder in the presence of soft Gaussian noise: the soft UF decoder
outperforms the hard UF decoder (both in terms of threshold and peformance
below threshold), and it also achieves a threshold that is 25% higher than the
optimal threshold achievable by any hard decoder [21]. Moreover, we find that
logical performance is highly sensitive to the measurement time. In the case
of soft Gaussian noise with amplitude damping, minimizing physical measurement
error rate can lead to logical error rates that are nearly 1000 times larger
over what is achievable, despite such minimization leading to a measurement
time that is only 5 times larger than the optimum.

We briefly review surface codes and provide some introductory definitions in
Section 1. This section also describes our general framework to describe soft
measurements, and gives specific examples including a model of the amplitude
damping channel during measurement. In Section 2, we define a general noise
model with soft measurement noise and we discuss the generalization of the
traditional phenomenological model and circuit models. The soft MWPM decoder
and the soft UF decoder are presented in Section 3. Then, we prove in Section
4 that the soft MWPM decoder returns a most likely fault set. We also provide
a sufficient condition for the success of the soft UF decoder, proving that
these two soft decoders perform well. In Section 5, we evaluate the
performance of the soft UF decoder for the phenomenological model and the
circuit model with soft noise. Finally, in Section 6, we use a toy model to
illustrate the benefits of optimizing measurement with awareness of the fault-
tolerant error correction protocol.

##  1 Background and definitions

###  1.1 Graph and hypergraphs

In this section, we review the language of graph and hypergraph theory [22].

A graph is a pair $G=(V,E)$ where $V$ is the vertex set and $E$ is the edge
set. An edge $e\in E$ is a pair of vertices $e=\\{u,v\\}$. In this work, we
consider only finite graphs. We will allow graphs to contain multiple copies
of the same edge $\\{u,v\\}$.

To describe subsets of edges and vertices, it is convenient to introduce the
language of chain complexes. A 1-chain in a graph is defined to be a formal
sum of edges $x=\sum_{e\in E}x_{e}e$ where $x_{e}\in\mathbb{Z}_{2}$. The
1-chain $x$ can be interpreted as the subset of edges $e$ such that $x_{e}=1$.
Conversely, any subset of $E$ defines a $1$-chain. Similarly, a 0-chain, which
represents a subset of $V$, is defined to be a formal sum of vertices
$y=\sum_{v\in V}y_{v}v$ where $y_{v}\in\mathbb{Z}_{2}$. Given the
correspondence between subsets and chains, we use the notation $e\in x$
(respectively $v\in y$) to refer to the fact that $e$ (respectively $v$)
belongs to the subset of edges corresponding to $x$ (respectively $y$).

For $i=0,1$, the set of $i$-chains, denoted $C_{i}$, is a
$\mathbb{Z}_{2}$-linear space equipped with the component-wise binary
addition. The boundary map is a $\mathbb{Z}_{2}$-linear map $\partial$ from
$C_{1}$ to $C_{0}$. The boundary of an edge $e=\\{u,v\\}$ is defined to be
$\partial(e)=u+v.$ and by linearity we have $\partial(x)=\sum_{e\in
E}x_{e}\partial(e)$ for all $x\in C_{1}$. In other words, the boundary of a
set of edges $A\subset E$ is the set of vertices that are incident with an odd
number of edges of $A$. Note that if $e_{1}$ and $e_{2}$ are two edges in $E$
which correspond to the same pair of vertices, we have that
$\partial(e_{1}+e_{2})=0$ by addition in $\mathbb{Z}_{2}$.

We also consider the restriction of the boundary to a subset of vertices.
Given a subset $U\subset V$, the restricted boundary map
$\partial_{U}\mathrel{\mathop{\mathchar 58\relax}}C_{1}\rightarrow C_{0}$ is
defined by $\partial_{U}(x)=\sum_{v\in\partial(x)\cap U}v.$

In this work, we also consider finite hypergraphs. A hypergraph is defined as
a pair $H=(V,E)$ where $V$ is the vertex set and $E$ is the set of hyperedges.
The difference from a graph is that a hyperedge can be an arbitrary subset of
$V$ that may contain more than two vertices. Like in the case of graphs, a
hypergraph can contain multiple copies of the same hyperedge. When the context
is clear, we will often use the term edges to refer to the hyperedges of a
hypergraph.

The chain complex language extends to hypergraphs. A 1-chain in a hypergraph
is a formal sum of hyperedges and a 0-chain is a formal sum of vertices. The
boundary of a hyperedge $e=\\{v_{1},\dots,v_{m}\\}$ is defined to be
$\partial(e)=v_{1}+\dots+v_{m}$ and the boundary map is extended to all
1-chains by linearity as for graphs.

###  1.2 Surface codes

In this section, we briefly review111Refs. [4, 23, 24] provide more complete
overviews of quantum error correction and quantum computation with surface
codes. the implementation of quantum error correction with the surface code
[25]. We focus on the rotated surface code represented in Figure 1(a).
However, all the results of this article generalize immediately to any surface
code with or without boundary, and also to hyperbolic surface codes [26].

The rotated surface code with minimum distance $d$ encodes one logical qubit
in a grid of $d\times d$ data qubits. Error correction with the surface code
is based on so-called plaquette measurements which each return one outcome
bit. Based on the outcomes extracted, a classical algorithm known as a decoder
is used to identify errors which corrupt the data qubits.

A plaquette measurement is a weight-four Pauli measurement
$X_{a}X_{b}X_{c}X_{d}$ or $Z_{a}Z_{b}Z_{c}Z_{d}$ acting on the four qubits
$a,b,c,d$ of a face of the grid of qubits. The boundary plaquettes represent
weight-two measurements $X_{e}X_{f}$ or $Z_{e}Z_{f}$ acting on the two qubits
of a face along the boundary of the grid.

A Pauli operator which is a product of plaquette operators is called a
stabilizer of the surface code. This is because it acts trivially on encoded
states. We sometimes refer to the measured plaquette operators as stabilizer
generators.

By symmetry, $X$ errors and $Z$ errors can be corrected with the same
strategy. In this section, we describe the correction of $X$ errors based on
the outcome of the measurement of $Z$ plaquettes.

(a)

(b)

Figure 1:  (a) The distance-five rotated surface code, which encodes one
logical qubit into a grid of $5\times 5$ data qubits (grey vertices). Blue and
white plaquettes support $Z$ and $X$ measurements respectively. (b) A
graphical representation of $X$ errors in the distance-five surface code. Each
of the 25 data qubits corresponds to an edge of the graph. Black vertices
support $Z$ plaquette measurements. White vertices are added to provide a
second endpoint for edges associated with a qubit that is incident to a single
$Z$ measurement. During a stabilizer measurement round, each black vertex
provides an outcome bit for a $Z$ plaquette. The set of blue edges represents
an $X$ error, and the outcome in a black vertex is given by the parity of the
number of incident blue edges.

First let’s assume that there is some error on the qubits but that the
plaquette measurements are performed perfectly. The value of the outcome bit
returned by a plaquette measurement is then given by the parity of the number
of qubits in the plaquette supporting the error. As a result, errors and
measurement outcomes exhibit a natural graph structure as one can see in
Figure 1(b). An $X$ error, which is supported on the edges of the decoding
graph $G_{X}$, can be represented by the 1-chain $x=\sum_{e\in E}x_{e}e$ such
that $x_{e}=1$ iff the edge $e$ suffers from an $X$ error. The set of outcomes
produced by all the plaquette measurements is represented by a 0-chain
$m=\sum_{v\in V}m_{v}v$ such that $m_{v}=1$ iff the outcome bit returned in
vertex $v$ is non-trivial.

In practice, the measurement of a plaquette is not perfect. It is typically
implemented using a small circuit that uses an additional ancilla qubit placed
in the center of the plaquette. The ancilla qubit is prepared in an initial
state $\ket{0}$ or $\ket{+}$ and a sequence of CNOT gates is performed between
the ancilla qubit and the plaquette’s qubits. Then, the outcome of the
plaquette measurement is extracted by measuring the ancilla qubit in the $Z$
or $X$ basis. It is possible to simultaneously extract the outcome bit of all
plaquettes in 6 time steps of operations by interleaving the CNOT gates in a
particular order (see Section 2.4). We refer to the extraction of bits for the
full set of a plaquettes of the surface code a stabilizer measurement round.

A single stabilizer measurement round is not enough to achieve good
performance, because the measurement circuits are implemented with imperfect
gates and the outcome measured is unreliable. To account for measurement
errors, the standard solution is to perform error correction based on multiple
consecutive rounds of measurement data, as we describe in more detail later.

###  1.3 Soft measurement

Measurements are subject to noise, as are other operations in quantum
hardware. Three standard models of noise are typically considered in the field
of quantum error correction. These all assume the depolarizing channel during
operations on the qubits (including idling operations), but the models differ
in how they treat plaquette measurements. The simplest is the _ideal
measurement model_ where plaquette measurements are assumed to be perfect. In
the _phenomenological noise model_ , this is amended by assuming that
following each perfect plaquette measurement the binary outcome can be flipped
before being reported. The _circuit noise model_ is the most realistic of the
standard models. In this case, plaquette measurements are implemented using
explicit circuits built from more basic operations, including single-qubit
measurements with a possible flip of the binary outcome.

In all three of these models, the outcomes of the stabilizer measurements are
discrete, and therefore decoding algorithms are typically designed to operate
using binary measurement outcomes. However, due to physical details of the
measurement apparatus, the output from a physical system will not be a simple
binary value, and may range from photon counts to continuous voltage waveform.
This output may be processed into a binary outcome, but this processing may
lead to information loss.

Here we seek to go beyond this paradigm. To do so, we introduce a simple model
of measurement which produces a more general output; see Figure 2. More
specifically, in our model of measurement there is first a projection of the
state into a subspace $\pi_{\bar{\mu}}$ as in the standard models, but the
_ideal outcome_ $\bar{\mu}\in\\{0,1\\}$ cannot be observed directly. What is
observed is instead a _soft outcome_ $\mu$, whose distribution is given by the
probability density function ${f}^{(\bar{\mu})}(\mu)$, which is conditioned on
the ideal outcome $\bar{\mu}=0$ or $1$. Our formalism can easily handle both
discrete and continuous measurement outcomes with minimal modifications. For
brevity, we focus on continuous-valued soft measurement outcomes in this
article.

Given the soft outcome, we can try to infer the ideal outcome by mapping the
soft outcome onto a binary outcome that we refer to as the hard outcome
$\hat{\mu}$. One particular choice for this hardening map corresponds to a
maximum likelihood assignment, where

$\displaystyle\hat{\mu}=\begin{cases}0&\text{ if
}{f}^{(0)}(\mu)\geq{f}^{(1)}(\mu),\\\ 1&\text{ otherwise.}\end{cases}$ (1)

Figure 2:  We model measurements as a perfect projection with ideal discrete
outcome $\bar{\mu}$, followed by a noisy process which outputs a continuous
soft outcome $\mu$. The soft outcome can be processed to produce a discrete
guess $\hat{\mu}$ of the ideal outcome, for example by comparing the
probability density functions for $\mu$ conditioned on different cases of
$\bar{\mu}$. There can be some loss of information in going from a soft to a
hard outcome. When the hard outcome does not match the ideal outcome, we say a
soft flip has occurred. Standard decoders use the hard outcome as their input,
whereas we propose using the soft outcome directly for decoding.

We say that a soft flip occurs during a measurement if the hard outcome
inferred is not equal to the ideal outcome. If the ideal outcome is
$\bar{\mu}$, the probability of a soft flip is given by

$\displaystyle{\mathbb{P}}(\text{soft
flip}|\bar{\mu})=\int_{f^{(\bar{\mu}^{\prime})}(\mu)>f^{(\bar{\mu})}(\mu)}{f}^{(\bar{\mu})}(\mu)\text{d}\mu,$
(2)

where $\bar{\mu}^{\prime}=\bar{\mu}+1\pmod{2}$. In general, this probability
depends on the value of the ideal outcome $\bar{\mu}$.

We say that a measurement is symmetric if the probability of a soft flip is
the same for both values of the ideal outcome $\bar{\mu}=0$ or 1. We then
define the probability $p_{M,\operatorname{soft}}={\mathbb{P}}(\text{soft
flip}|0)={\mathbb{P}}(\text{soft flip}|1)$ that a hard decoder interprets the
soft outcome as a flip after hardening. In this work we often consider
scenarios in which there can first be a flip of the ideal measurement outcome
with probability $p_{M}$ preceding symmetric soft noise. Then the probability
$p_{M,\text{hardened}}$ of a flip overall after hardening is

$\displaystyle
p_{M,\text{hardened}}=p_{M}+p_{M,\operatorname{soft}}-p_{M}p_{M,\operatorname{soft}}.$
(3)

A simple example of a symmetric soft measurement is the Gaussian soft noise in
which a ${f}^{(0)}={\cal N}(+1,\sigma^{2})$ and ${f}^{(1)}={\cal
N}(-1,\sigma^{2})$. Some physical processes may lead to asymmetric
measurements, as we discuss next in Section 1.4.

###  1.4 Example: Amplitude damping

Here we provide a toy model [27] for soft measurement noise based on amplitude
damping [28] which is common in solid state quantum devices such as
superconducting qubits and quantum dots [29, 30]—we call this model Gaussian
soft noise with amplitude damping. In this case the probability density
functions ${f}^{(0)}$ and ${f}^{(1)}$ can be tuned by setting the relative
duration of three timescales $\tau_{M}$, $\operatorname{\tau_{A}}1m$ and
$\tau_{F}$; see Figure 3. We therefore write these as
${f}^{(0)}(\mu;\tau_{M},\operatorname{\tau_{A}}1m,\tau_{F})$ and
${f}^{(1)}(\mu;\tau_{M},\operatorname{\tau_{A}}1m,\tau_{F})$, making their
dependence on $\tau_{M},\operatorname{\tau_{A}}1m,\tau_{F}$ explicit.

Under this noise model, at any infinitesimal time interval the qubit may decay
from $\ket{1}$ to $\ket{0}$ with a fixed time-independent rate
$1/\operatorname{\tau_{A}}1m$, but no transitions from $\ket{0}$ can occur.
Here we refer to $\operatorname{\tau_{A}}1m$ as the amplitude damping time,
although in the physics literature it is often referred to as the $T_{1}$
time. This asymmetry arises because in many systems the $\ket{1}$ state has
higher energy than the $\ket{0}$ state, and unintentional interactions with a
low-temperature bath lead to energy transfer from the qubit to the bath,
resulting in this decay (for this reason, amplitude damping is also known as
energy relaxation).

Since measurement relies on the accumulation of information about the state
over the measurement time $\tau_{M}$, any qubit decays during that time will
increase the probability that a $\ket{1}$ at the beginning of the measurement
is mistaken for a $\ket{0}$, but not the other way around.

In our amplitude damping model model, there is a signal $S(t)$ which builds up
over time $t$ starting from $S(0)=0$. The signal’s behavior is mathematically
equivalent to a one-dimensional continuous random walk with drift, where the
sign of the drift depends on whether the system is in the state $\ket{0}$ or
$\ket{1}$. Specifically, if the state of the system is $\ket{0}$ during an
infinitesimal time interval from $t$ to $t+\text{d}t$, the mean of $S$ is
increased by an amount proportional to $\text{d}t$. On the other hand if the
state of the system is $\ket{1}$ during this interval, the mean of $S$ is
decreased by the same amount. Irrespective of the state of the system, the
variance of $S$ increases by an amount proportional to $\text{d}t$ during this
time interval. The ratio between the variance and the square of the mean of
the increment over a small time interval is $\tau_{F}/\text{d}t$, where the
constant $\tau_{F}$ is refered to as the fluctuation time. The signal is read
out at a time $\tau_{M}$ giving $S(\tau_{M})$ which we take to be the
continuous measurement outcome $\mu$ (after scaling such that the mean of
$\mu$ is $+1$ when $\bar{\mu}=0$).

Although the derivation and precise forms of the conditional distributions
under this toy model are somewhat involved (see Appendix A), their qualitative
behavior is rather simple, as illustrated by Figure 3. When
$\tau_{M}\ll\operatorname{\tau_{A}}1m$, the distributions are well
approximated by Gaussians. These Gaussians have an overlap that decreases
monotonically with $\tau_{M}/\tau_{F}$, so and increasing $\tau_{M}/\tau_{F}$
lowers ${\mathbb{P}}(\text{soft flip}|\bar{\mu})$. As $\tau_{M}$ approaches
$\operatorname{\tau_{A}}1m$, ${f}^{(0)}$ remains unchanged but ${f}^{(1)}$ is
distorted and shifts towards ${f}^{(0)}$, so that as
$\frac{\tau_{M}}{\operatorname{\tau_{A}}1m}$ increases
${\mathbb{P}}(\text{soft flip}|1)$ approaches $\frac{1}{2}$ (the distributions
overlap completely). A regime of particular interest in this model is when
$\tau_{F}\ll\tau_{M}\ll\operatorname{\tau_{A}}1m$, so that ${f}^{(1)}$ is not
significantly distorted ($\tau_{M}\ll\operatorname{\tau_{A}}1m$), while the
overlap between the conditional distributions is also small
($\tau_{F}\ll\tau_{M}$).

increasing $\tau_{A}$increasing $\tau_{M}$ Figure 3: Conditional probability
density functions ${f}^{(0)}$ (blue) and ${f}^{(1)}$ (yellow) for
$\tau_{M}/\tau_{F}$ increasing from top to bottom, and
$\operatorname{\tau_{A}}1m/\tau_{F}$ increasing from left to right. The width
of ${f}^{(0)}$ is proportional to $\sqrt{\tau_{F}/\tau_{M}}$, and the scales
are chosen so that for $\tau_{M}\ll\tau_{A}$ the Gaussians are centered at
$\pm 1$. Intuitively, increasing measurement time $\tau_{M}$ narrows the
conditional distributions (making them more distinguishable), while decreasing
amplitude damping lifetime $\tau_{A}$ shifts the $\bar{\mu}=1$ distribution
towards the $\bar{\mu}=0$ distribution (making them less distinguishable).

##  2 Graphical models for soft noise in the surface code

In this section, we propose a general graphical noise model to describe errors
and soft measurement outcomes for surface codes, including correlated errors
and repeated measurements. This formalism includes the standard noise models
mentioned in Section 1.2 namely ideal measurement noise, phenomenological
noise and circuit noise [4] as special cases. Later in Section 3 we define
decoders which correct the errors in graphical noise models, and in particular
which make use of the soft data to outperform standard decoders which ignore
this soft information.

###  2.1 General graphical model

Here we present a general graphical model for arbitrary Pauli noise with soft
measurement outcomes. Faults can affect the outcomes of plaquette measurements
of the surface code and can leave residual errors on the data qubits. The
following definition captures this notion.

######  Definition 2.1.

A graphical model for $T$ rounds of measurements with the surface code is a
quadruple $(G_{T},p,f,\pi)$ defined by

  * •

Fault hypergraph: A hypergraph $G_{T}=(V_{T},E_{T})$ such that $V_{T}$
contains a vertex $(a,t)$ for each plaquette $a$ and for each round
$t=1,\dots,T$.

  * •

Fault probability: A value $p_{e}\in[0,1]$ for each hyperedge $e\in E_{T}$.

  * •

Measurement noise: A pair of probability density functions
$({f}^{(0)}_{a,t},{f}^{(1)}_{a,t})$ for each plaquette $a$ and for each round
$t=1,\dots,T$ describing the measurement outcome in this location.

  * •

Residual error: A Pauli error $\pi_{e}$ on the data qubits of the surface code
for each hyperedge $e\in E_{T}$.

We call the graph $G_{T}$ the _fault hypergraph_ or simply fault graph when it
is a proper graph. To construct the graph $G_{T}$ in this case, we begin by
including all the vertices from $G_{X}$ and $G_{Z}$ described in Section 1.2
for each of the $T+1$ layers. The set of measurement vertices of $G_{T}$,
denoted ${V_{\bullet}}$, is the set of vertices $(a,t)$ corresponding to the
spacetime locations of the plaquettes, where $a$ corresponds to the plaquette
and $t$ labels the measurement round. Each hyperedge of $G_{T}$ represents a
potential fault and the vertices contained in a hyperedge correspond to the
spacetime locations of measurements that detect this fault. In practice, a
fault may correspond to a Pauli error $X,Y$ or $Z$ or the flip of an outcome
bit. It could also be a combination of multiple Pauli errors and outcome bit
flips. The fault $e$ induces a residual error $\pi_{e}$ on the data qubits at
the end of the $T$ rounds of measurement. The hypergraph $G_{T}$ may contain
multiple copies of the same edge $e$ with different residual errors $\pi_{e}$.
The graph $G_{T}$ contains additional vertices which we call boundary
vertices, denoted ${V_{\circ}}=V\backslash{V_{\bullet}}$. Figure 4 shows an
example of a graphical noise model which corresponds to $T=3$ rounds of
measurement for the distance $d=5$ surface code.

Figure 4:  Examples of hyperedges corresponding to faults. A single-qubit $X$
error corresponds to a singe horizontal edge (blue). A flipped measurement
outcome corresponds to a singe vertical edge (red). More general faults are
possible, and correspond to hyperedges. Here we show an example of a weight-
two Pauli error and the resulting syndrome that could arise from a single
fault in a stabilizer measurement circuit (green).

In some cases, it is useful to define independent noise models for $X$ type
errors and $Z$ type errors in which case we define a separate hypergraph for
each. The $X$-type hypergraph contains vertices $(a,t)$ for $Z$ plaquettes
only.

###  2.2 Sampling from graphical models

In our graphical noise models, faults occurs independently of one another.
Correlated errors acting on different qubits at potentially different times
can occur since each fault has no restriction on the support of the residual
error or on the measurement vertices which it flips.

A fault set for the graphical model $G_{T}$ is defined to be a 1-chain $x$ of
$G_{T}$, that is a formal sum of hyperedges $x=\sum_{e\in E_{T}}x_{e}e$. The
probability of a fault set $x$ is

$\displaystyle{\mathbb{P}}(x)=\prod_{e\in x}p_{e}\prod_{e\notin x}(1-p_{e}),$
(4)

where each fault $e$ occurs with probability $p_{e}$.

For a trivial fault set, $x=0$, the ideal outcome in any measurement vertex
$(a,t)$ is $\overline{m}_{a,t}=0$. A fault $e$, containing a measurement
vertex $(a,t)$, induces a change of the value of the ideal outcome
$\overline{m}_{a,t^{\prime}}$ for all $t^{\prime}\geq t$. The ideal outcome
associated with a general fault set $x$ is obtained by combining the effects
of all its faults $e\in x$.

The soft outcome $m_{a,t}$ and the hard outcome $\hat{m}_{a,t}$ are generated
from the ideal outcome using the probability density functions
${f}^{(0)}_{a,t}$ and ${f}^{(1)}_{a,t}$ as explained in Section 1.3. Note that
although we use the term ‘ideal outcome’, this outcome depends on faults that
have occurred at earlier times.

For the decoders we define later it is also convenient to introduce the
syndrome which measures the changes between two consecutive rounds of
measurements. The syndrome, denoted $\hat{s}(m)$, is a 0-chain in $G_{T}$
which can be calculated from the observed soft measurement outcomes $m$ by
first using Eq. 1 to identify the hard outcomes $\hat{m}$, and then

$\displaystyle\hat{s}_{a,t}=\hat{m}_{a,t}+\hat{m}_{a,t-1}\pmod{2}$ (5)

for all measurement vertices $(a,t)$, with the convention $\hat{m}_{a,0}=0$.
The value of the syndrome in boundary vertices is 0. The syndrome provides the
same information as the hard outcome but it is more convenient for the decoder
to use the syndrome as an input instead of the hard outcome.

###  2.3 Example: Soft phenomenological noise

Here we define a generalization of the standard phenomenological noise model
introduced in [4] to include soft Gaussian noise affecting measurement
outcomes.

First we define the noise model’s $X$-type _fault graph_ $G_{T}$, by stacking
$T+1$ copies of the graph $G_{X}$ which was described in Section 1.2 and
represented in Figure 1(b), and connecting consecutive layers with vertical
edges; see Figure 5. The graph $G_{T}$ has two types of vertices.
Specifically, the set of measurement vertices of $G_{T}$, denoted
${V_{\bullet}}$, is the set of vertices $(a,t)$ corresponding to the space
time locations of the plaquettes, where $a$ corresponds to a plaquette and
$t=1,\dots,T$ labels the measurement round. The remaining vertices are
boundary vertices, denoted ${V_{\circ}}=V\backslash{V_{\bullet}}$. The
vertices of the $T+1$ layer are treated differently from other vertices in
$G_{T}$, in that they correspond to perfect measurements.

Figure 5:  Fault graph for the soft phenomenological noise model with $T=3$
rounds of measurements for the surface code with distance five. The graph
contains $T+1=4$ copies of the graph represented in Figure 1(b). There is a
copy of the graph for each time step and an additional copy corresponding to a
round of perfect measurement is added for a proper termination. Horizontal
edges correspond to qubit errors and vertical edges encode ideal outcome
flips.

Furthermore, a probability $p_{D}$ is assigned to each horizontal edge, and a
probability $p_{M}$ is assigned to each vertical edge in $G_{T}$. This
corresponds to qubits being affected by independent $X$ errors with
probability $p_{D}$ and independent ideal measurement outcome flips with
probability $p_{M}$. The pair of probability density functions ${f}^{(0)}$ and
${f}^{(1)}$ are assigned to each measurement vertex in $G_{T}$.

In this graphical description of the noise model, edges represent potential
faults and the vertices contained in an edge correspond to the measurements
whose ideal value will _change_ due to the presence of this fault. For
instance, the fault corresponding to the horizontal edge $\\{(a,t),(b,t)\\}$
in $G_{T}$ is an $X$ error being applied just before round $t$ of measurements
to the qubit associated with the edge $(a,b)$ in $G_{X}$. This fault occurs
with the probability assigned to the edge, namely $p_{D}$, and it results in a
change of the ideal outcome associated with the plaquettes $a$ and $b$ at time
$t$. In other words, it results in a change of the ideal outcomes of vertices
$(a,t)$ and $(b,t)$ when compared with $(a,t-1)$ and $(b,t-1)$ respectively.
In the absence of additional faults, these vertices then retain their new
ideal outcome for all rounds $t^{\prime}\geq t$. The fault corresponding to
the vertical edge $\\{(a,t),(b,t+1)\\}$ in $G_{T}$ is a flip of the ideal
outcome of the plaquette associated with $a$ in $G_{X}$ only at round $t$.
This fault occurs with probability $p_{M}$, and corresponds to a change in the
ideal outcome of the vertex $(a,t)$ with respect to the vertex $(a,t-1)$ and
then a further change of the ideal outcome of the vertex $(a,t+1)$ with
respect to the vertex $(a,t)$.

If the ideal outcomes were reported, this would precisely reproduce the
standard phenomenological noise model introduced in Ref. [4]. Instead, the
reported output of each plaquette in each round is the soft outcome obtained
by sampling from the probability density functions assigned to the vertices of
$G_{T}$, namely ${f}^{(0)}$ for plaquettes with ideal outcome $0$ and
${f}^{(1)}$ for plaquettes with ideal outcome $1$.

###  2.4 Example: Soft circuit noise

Here we provide a generalization of the standard circuit noise model to
include soft measurement. Our model involves $T$ consecutive stabilizer
measurement rounds, where each measurement round is implemented by the circuit
shown in Figure 6.

$3$$1$$4$$2$$3$$1$$4$$2$$3$$4$$1$$2$

$Z$

$2$

$Z$

$4$

$Z$

$1$

$Z$

$3$

$Z$

$2$

$Z$

$4$

$Z$

$1$

$Z$

$3$

$Z$

$4$

$Z$

$3$

$Z$

$2$

$Z$

$1$ Figure 6:  Standard stabilizer extraction circuit for a distance 3 rotated
surface code (see for instance [31]). The circuit for an arbitrary distance
code is obtained by translating this circuit for all stabilizers. Note that
there are some idle circuit locations during which CNOT gates are being
applied and others during which measurement qubits are being applied, which we
treat separately in our model since measurement and gate times can be
different.

Each of the components of the circuit can fail in specific ways, and for each
of these possible failures we introduce a hyperedge to the graph $G_{T}$. In
particular, the following failures can occur for the circuit components:

  * •

Idle qubits waiting for CNOT gates: $X$, $Y$, $Z$ each occurs independently
with probability $p_{IG}/3$.

  * •

Idle qubits waiting for measurements: $X$, $Y$, $Z$ each occurs independently
with probability $p_{IM}/3$.

  * •

CNOT gates: $XI$, $YI$, $ZI$, $IX$, $XX$, $YX$, $ZX$, $IY$, $XY$, $YY$, $ZY$,
$IZ$, $XZ$, $YZ$, $ZZ$ each occurs independently with probability
$p_{\text{CNOT}}/15$.

  * •

Measurement outcomes (ideal): have their ideal outcome flipped with
probability $p_{M}$.

  * •

Measurement outcomes (soft): given the ideal outcome $\bar{\mu}\in\\{0,1\\}$,
the continuous outcome $\mu$ is sampled from the probability density function
${f}^{(\bar{\mu})}(\mu)$ as described in Section 1.3.

A few remarks are called for before describing how the graphical noise model
is constructed. First note that the circuit in Figure 6 only has time steps
during which either CNOTs or measurements are performed (but not both), making
it natural to consider the two above scenarios for idle qubits since a CNOT
gate may have a very different duration than a measurement. Secondly, here
each fault (even faults associated with the same operation in the circuit) are
applied independently. At first this may seem slightly different from the
standard circuit noise considered in the literature in different faults that
occur on the same operation are exclusive. However, the standard exclusive
circuit noise model and the inclusive circuit noise model assumed here are
actually exactly equivalent as proven in Appendix E of [18]. When mapping
between the inclusive and exclusive noise models, the probability with which
each fault occurs can change, although the change is very small in the regimes
of interest. We discuss this in more detail in Appendix B.

To construct the graph $G_{T}$ in this case, we begin by including all the
vertices from $G_{X}$ and $G_{Z}$ for $T+1$ layers from Section 1.2. For each
of the possible faults listed in the first four bullet points (i.e. excluding
the soft measurement) that can occur in the $T$ rounds of stabilizer
measurements implemented by the circuit, a hyperedge is added to the graph
$G_{T}$. The vertices included in the hyperedge are those vertices whose
measurement outcomes will flip if that fault occurs. The probability assigned
to the hyperedge is simply the probability that the fault occurs. The residual
error associated with the hyperedge is identified by observing what Pauli
operator is left on the data qubits at the end of the measurement round during
which the fault occurs. Lastly, each measurement vertex has the pair
$\\{{f}^{(0)}(\mu),{f}^{(1)}(\mu)\\}$ of probability density functions
assigned.

##  3 Soft decoding

In this section, we propose two efficient decoders for surface codes with soft
measurements. First, we propose a soft version of the minimum weight perfect
matching (MWPM) decoder [4]. Different variants of the MWPM decoder exploiting
some soft information were considered previously for the special case of GKP
surface codes [11, 12, 13, 14]. Although its complexity is polynomial, the
soft MWPM decoder may be too slow for some applications. Next, we propose a
soft version of the Union-Find (UF) decoder [15] which has lower complexity
and therefore could be more practical.

###  3.1 Decodability constraints

The ultimate goal of a decoder is to correct the data qubits, that is to
cancel the effect of the residual errors of the faults which occur. The two
decoders proposed in this article return a fault set $x$ for a given set of
soft outcomes. The correction to apply to the data qubits is the product of
the residual errors $\pi_{e}$ corresponding to the faults $e$ in $x$.

We will restrict ourselves to graphical models $(G_{T},p,f,\pi)$ that satisfy
the following decodability conditions:

(C1) All the edges in $G_{T}$ have rank two.

(C2) For all $e\in E_{T}$, we have $p_{e}<0.5$.

Condition (C1) guarantees that $G_{T}$ is a graph instead of a general
hypergraph. We require this because we expect the decoding problem for a
general hypergraph to be too difficult to solve. For example, the problem of
identifying a least likely fault set in that case includes the three-
dimensional matching problem which is NP-hard [32]. Condition (C2) excludes
pathological cases where faults occur with excessively high probability.

###  3.2 Soft decoding graph

In Section 2.1 we defined the fault hypergraph. Here, we introduce another
graph which will be used for decoding. The decoding graph, denoted
$\tilde{G}_{T}=(\tilde{V}_{T},\tilde{E}_{T})$, associated with the graphical
model $(G_{T},q,f,\pi)$ is the graph obtained from $G_{T}$ by adding an edge
(which we call a soft vertical edge) connecting $(a,t)$ with $(a,t+1)$ when
$(a,t)$ is a measurement vertex. The graph $G_{T}$ may already contain a
vertical edge connecting these two vertices. In that case, the decoding graph
$\tilde{G}_{T}$ contains two edges connecting $(a,t)$ and $(a,t+1)$ that we
refer to as the soft vertical edge and the hard vertical edge. Moreover, all
the boundary vertices of $\tilde{G}_{T}$ are identified to single vertex,
denoted $v_{g}$, that we refer to as the ghost vertex. By definition, we have
$\tilde{V}_{T}={V_{\bullet}}\cup\\{v_{g}\\}$ and $\tilde{E}_{T}$ is the set
$E_{T}$ augmented with soft vertical edges.

Consider a measurement vertex $(a,t)$. let $\mu$ be the soft outcome observed
in this vertex and $\hat{\mu}$ be the corresponding hard outcome. Denote by
$\hat{\mu}^{\prime}=\hat{\mu}+1\pmod{2}$ the other value of the hard outcome.
To define edge weights in the decoding graph, it is convenient to introduce
the likelihood ratio

$\displaystyle
L_{a,t}(\mu)=\frac{{f}^{(\hat{\mu}^{\prime})}_{a,t}(\mu)}{{f}^{(\hat{\mu})}_{a,t}(\mu)}\cdot$
(6)

This ratio can be computed from the knowledge of the probability density
functions and the value of the soft outcome $\mu$ because $\hat{\mu}$ and
$\hat{\mu}^{\prime}$ are derived from $\mu$. By definition of the hard
outcome, we have $L_{a,t}(\mu)\in[0,1]$.

Given the model parameters $p_{e}$ and the set of soft outcomes $m$ observed
over measurement vertices, we define edge weights for the decoding graph. Hard
and soft edges have different weights. The weight of the soft edge $e$ between
$(a,t)$ and $(a,t+1)$ is defined as a function of the soft outcome, whereas
the hard edge weight depends on the parameter $p_{e}$. Precisely, the edge
weight is defined by

$\displaystyle w(e)=\begin{cases}-\log L_{a,t}(m_{a,t})&\text{if $e$ is
soft,}\\\ -\log(p_{e}/(1-p_{e}))&\text{otherwise.}\end{cases}$ (7)

These edge weights are non-negative numbers. In some cases, we denote this
weight by $w_{\tilde{G}_{T}}(e)$ to avoid any ambiguity about which graph the
weight is defined with respect to.

###  3.3 Soft Minimum Weight Perfect Matching decoder

Our soft MWPM decoder is specified in Algorithm 1. The key ingredient is the
distance graph that we introduce below.

Algorithm 1 Soft MWPM decoder

0: The decoding graph $\tilde{G}_{T}$ for $T$ rounds of measurements. A set of
soft outcomes $m$.

0: A fault set, i.e. a 1-chain $x$ in $G_{T}$.

1: For each soft vertical edge $e$, compute $w_{\tilde{G}_{T}}(e)$ as a
function of $m$ using Eq. 7.

2: Compute the syndrome $\hat{s}$ from $m$ using Eq. 5. Let
$v_{1},\dots,v_{k}$ be the set of vertices of $\tilde{G}_{T}$ with non-trivial
syndrome.

3: Construct the distance graph $K(\hat{s})$ with vertex set
$V_{K}=\\{v_{1},\dots,v_{k}\\}$ and compute the edge weights
$w_{K}(\\{v_{i},v_{j}\\})=d_{\tilde{G}_{T}}(v_{i},v_{j})$ using Dijkstra’s
algorithm.

4: Compute a minimum weight perfect matching $M$ in $K(\hat{s})$.

5: For each edge $\\{u,v\\}\in M$, compute a geodesic
$\operatorname{geo}(u,v)$ in the graph $\tilde{G}_{T}$.

6: return the 1-chain $\tilde{x}=\sum_{\\{u,v\\}\in M}\operatorname{geo}(u,v)$
restricted to the graph $G_{T}$.

We consider the distance in the decoding graph $\tilde{G}_{T}$ induced by the
edge weights $w_{\tilde{G}_{T}}(e)$. The length of a path in $\tilde{G}_{T}$
is defined to be the sum of the weights of its edges. The distance between two
vertices $u$ and $v$, denoted $d_{\tilde{G}_{T}}(u,v)$, is defined to be the
minimum length of a path connecting $u$ and $v$. A minimum length path joining
$u$ and $v$ is called a geodesic. Given $u,v\in V_{T}$, let
$\operatorname{geo}(u,v)$ be the set of edges supporting a geodesic connecting
$u$ and $v$. If the decoding graph contains multiple geodesics between $u$ and
$v$, $\operatorname{geo}(u,v)$ is chosen arbitrarily among them. We will
consider $\operatorname{geo}(u,v)$ as a 1-chain in the decoding graph.

Given the decoding graph $\tilde{G}_{T}$ and a syndrome $\hat{s}$, the
distance graph $K(\hat{s})=(V_{K},E_{K})$ is defined to be the fully connected
graph with vertex set $V_{K}$ given by the set of measurement vertices
supporting a non-trivial syndrome. If $K(\hat{s})$ contains an odd number of
vertices, we add the ghost vertex to $V_{K}$. We define edge weights in $K$
based on the distance in the decoding graph, that is
$w_{K}(\\{u,v\\})=d_{\tilde{G}_{T}}(u,v)$.

Like in the standard MWPM decoder, the basic idea of Algorithm 1 is to compute
a minimum set of paths that connect pairs of syndrome vertices in the decoding
graph. This is done using a Minimum Weight Perfect Matching (MWPM) algorithm
[33]. The distance graph contains an even number of vertices and its edge
weights are non-negative making the application of the MWPM algorithm
straightforward.

The main difference between our soft MWPM decoder and the standard hard MWPM
decoder [4] is that the weights in the soft decoding graph depend on the set
of outcomes $m$ whereas they are fixed in the hard case. As a result, the
distances between all pairs of nodes can be precomputed in the standard MWPM
but not in the soft MWPM decoder. Similarly, one cannot precompute a geodesic
for each pair of nodes in the soft decoding graph. This increases the
execution time of the decoder. However, as we explain below, the worst-case
asymptotic complexity is no worse than the standard MWPM decoder.

The worst case complexity of the standard MWPM decoder is dominated by the
call of the MWPM algorithm. Based on Blossom V, a popular implementation of a
MWPM algorithm designed by Kolmogorov [34] which has a worst case complexity
in $O(n_{v}^{3}n_{e})$ for a graph with $n_{v}$ vertices and $n_{e}$ edges,
one can achieve a worst case complexity in $O(|V_{T}|^{5})$ for the hard MWPM
decoder, that is $O(d^{15})$ if $T=d$ rounds of measurement are used. Other
implementations of the MWPM decoder achieve a better worst-case complexity but
they might not run faster in practice (see Table I in [35]). The most
favorable asymptotic scaling for a MWPM algorithm [36] leads a worst-case
complexity in $O(\sqrt{n_{v}}n_{e})$ for the matching subroutine and a MWPM
decoder complexity in $O(d^{7.5})$ for $T=d$.

If Blossom V is used, the complexity of our soft variant of the MWPM decoder
remains the same, $O(d^{15})$, dominated by the cost of this MWPM subroutine.
We can also achieve $O(d^{7.5})$ worst-case complexity using the MWPM
algorithm of [36] despite the fact that distances and geodesic between the
syndrome nodes must be computed on the fly in our soft MWPM decoder. The
computation of all the distances $d_{\tilde{G}_{T}}(v_{i},v_{j})$ is performed
in step 3 and 4 of the algorithm with worst-case complexity
$O(|V_{T}||E_{T}|+|V_{T}|^{2}\log|V_{T}|)$ using Dijkstra’s algorithm.
Assuming $T=d$ measurement rounds, this subroutine runs in $O(d^{6}\log d)$.
The geodesics are computed in step 7 of Algorithm 1 also thanks to Dijkstra’s
algorithm with the same worst-case complexity as the distances calculation.

###  3.4 Soft Union-Find decoder

Here we provide a soft version of the UF decoder [15, 37], which achieves an
error correction performance similar to the MWPM decoder but with better time
complexity. Our soft UF decoder is specified in Algorithm 2.

Figure 7:  Illustration of the cluster growth subroutine of the UF decoder.
Edges of the decoding graph are split in the middle. The three red vertices
support a non-trivial syndrome. Initially, there are three odd clusters, one
for each syndrome vertex. One odd cluster has perimeter four and the other two
have perimeter three. At the first growth step, we select a cluster with
minimum perimeter and we grow the three edges $(a)$ by 0.5. Then, the edges
$(b)$, which belong to the least recently grown cluster with perimeter three,
are grown. This connects two odd clusters forming an even cluster. During the
next two steps ($(c)$ and $(d)$), the remaining odd cluster grows until it
meets a boundary node and becomes even.

The soft UF decoder works in two steps: First, we grow clusters of qubits in
the decoding graph until each of the clusters can be corrected separately. The
growth subroutine is shown in Figure 7. Then, the peeling decoder [38] is used
to find a correction inside the grown clusters in linear time. In what
follows, we explain the growth procedure used in our soft UF decoder.

To describe our soft UF decoder, it is convenient to introduce the split-edge
graph $\tilde{H}_{T}$ obtained from the decoding graph $\tilde{G}_{T}$ by
adding a vertex in the middle of each edge. Each edge $e$ of the decoding
graph splits into two edges of $\tilde{H}_{T}$ whose weights are given by
$w_{\tilde{G}_{T}}(e)/2$. The boundary vertices of $\tilde{H}_{T}$ are those
corresponding to boundary vertices of $\tilde{G}_{T}$.

To keep track of the edge growth, we associate a growth state
$\gamma(e)\in\mathbb{R}$ with each edge $e$ of $\tilde{H}_{T}$. An edge $e$ is
said to be fully grown if $\gamma(e)=w_{\tilde{H}_{T}}(e)$. The cluster of a
vertex $v$ of $\tilde{H}_{T}$ is defined to be the set of vertices of
$\tilde{H}_{T}$ that can be reached from $v$ through a path of fully grown
edges.

Given a syndrome $\hat{s}$, a cluster of $\tilde{H}_{T}$ is said to be even if
it contains an even number of vertices of $\hat{s}$ or at least one boundary
vertex. A cluster that is not even is said to be odd. If a cluster is even, we
can use the peeling decoder to determine a fault set included in the cluster
which cancels the syndrome of this cluster [38]. Therefore, we will grow odd
clusters until all clusters are even and can be corrected by peeling.

To determine which cluster to grow first, we consider the set $B(C)$ of edges
of $\tilde{H}_{T}$ connecting a cluster $C$ and its complementary. The
perimeter of the cluster $C$ is defined as the number of edges in $B(C)$. At
the beginning of the growth procedure, the growth state of each edge is
initialized to $\gamma(e)=0$. Then, at each growth step, we select an odd
cluster $C$ with minimum perimeter and grow all edges of $B(C)$ by
incrementing the growth states by

$\displaystyle\Gamma_{C}=\min_{e\in B(C)}(w_{\tilde{H}_{T}}(e)-\gamma(e)).$
(8)

$\Gamma_{C}$ is the smallest value $\Gamma$ such that growing all edges of
$B(C)$ by $\Gamma$ fills at least one edge. If multiple odd clusters have the
same perimeter, we prioritize the least recently grown cluster.

After the growth, we are left with only even clusters, and we will call the
peeling decoder to find an estimation of the fault set inside the grown
clusters. We consider the set $\varepsilon\subset\tilde{E}_{T}$ of edges of
the decoding graph $\tilde{G}_{T}$ for which both halves are fully grown in
the split-edge graph $\tilde{H}_{T}$. The peeling decoder takes as input the
subset $\varepsilon\subset\tilde{E}_{T}$ and a syndrome $\hat{s}$ and
computes, in linear time, a 1-chain $\tilde{x}\subset\varepsilon$ in
$\tilde{G}_{T}$ such that $\partial_{{V_{\bullet}}}(\tilde{x})=\hat{s}$. We
will use the notation $\tilde{x}=\textbf{Peeling}(\varepsilon,\hat{s})$. The
restriction of $\tilde{x}$ to $G_{T}$ is the output the soft UF decoder.

Algorithm 2 Soft UF decoder

0: The graph $\tilde{H}_{T}$ for $T$ rounds of measurements. A set of soft
outcomes $m$.

0: A 1-chain $x$ in $G_{T}$.

1: For each soft vertical edge $e$, compute $w_{\tilde{H}_{T}}(e)$ as a
function of $m$ using Eq. 7.

2: Compute the syndrome $\hat{s}$ from $m$ using Eq. 5.

3: For each edge $e$ of $\tilde{H}_{T}$, set $\gamma(e)=0$.

4: While there exists at least one odd cluster do:

5: Select an odd cluster $C$ with minimum perimeter. If there are multiple
such clusters select the least recently grown.

6: Compute $\Gamma_{C}$ defined in Eq. 8.

7: For all $e\in B(C)$ do $\gamma(e)\leftarrow\gamma(e)+\Gamma_{C}$.

8: Compute the set $\varepsilon$ of edges $e$ of $\tilde{G}_{T}$ such that the
two halves of $e$ in $\tilde{H}_{T}$ are fully grown.

9: Compute the 1-chain $\tilde{x}=\textbf{Peeling}(\varepsilon,\hat{s})$ of
$\tilde{G}_{T}$.

10: return the restriction of $\tilde{x}$ to the graph $G_{T}$.

The growth procedure of our soft UF decoder Algorithm 2 differs from the
growth of the variant of the UF decoder proposed in [37] in two ways. First,
we grow half-edges instead of the original edges of the decoding graph. This
is why we perform the growth in the graph $\tilde{H}_{T}$ instead of
$\tilde{G}_{T}$. Second, we prioritize the least recently grown cluster. We
checked that these two modifications bring a small improvement of the error
threshold of hard UF decoder for the standard circuit noise model.

The time complexity of the soft UF decoder depends on the precision required
for the edge weights of the soft decoding graph. Like in the circuit level
study of [37], we expect that a finite precision is sufficient to achieve good
decoding performance. Our simulations are done with 32-bits of precision for
the edge weights. In that case, the worst case complexity of the soft UF
decoder remains $O(d^{3}\alpha(d))$, where $\alpha(d)$ is the slowly
increasing inverse Ackermann function. This complexity is significantly better
than the soft MWPM decoder.

##  4 Proof of decoding success

In this section, we prove that the soft MWPM decoder and the soft UF decoder
perform well. First, we prove that the soft MWPM decoder returns a most likely
fault set. A key technical ingredient to establish this result is Lemma 4.3
which provides the probability of a fault set given a set of soft outcomes as
a function of the edge weights in the soft decoding graph. Then, we propose a
sufficient condition for the success of the soft UF decoder.

###  4.1 Technical definitions

Here we provide some definitions which are useful throughout this section.

Given a weighted graph $G$ and a 1-chain $a$, we denote by $|a|_{w}=\sum_{e\in
a}w(e)$ the sum of the edge weights in $a$. The diameter of a subset $C$ of
vertices of the graph, denoted $\operatorname{diam}_{w}(C)$, is the maximum
distance between two vertices of $C$ assuming that edge lengths are given by
$w(e)$. The diameter of a subset of edges or a 1-chain is defined to be the
diameter of the set of incident vertices.

A fault set for a graphical model is a 1-chain in the fault graph $G_{T}$.
Similarly, we can represent the set of soft flips for a given fault set $x$
with a set of soft outcomes $m$ as a 1-chain $x_{\operatorname{soft}}$ in the
graph $\tilde{G}_{T}$ with support on soft vertical edges. In what follows, we
denote $\tilde{x}=x+x_{\operatorname{soft}}$ the 1-chain representing a fault
set and its soft flips for a given set of soft outcomes. The value of
$x_{\operatorname{soft}}$ depends on $x$ and the set of soft outcomes observed
$m$.

The syndrome $\hat{s}(m)$ can be derived from the value of $\tilde{x}$ because
$\hat{m}$ can be computed from $x$ and from the location of the soft flips. As
a result, we can talk about a fault set $\tilde{x}$ with trivial syndrome.

The weighted minimum distance of a graphical model, denoted $d_{w}$, is
defined to be the minimum value $|x|_{w}$ for a fault set $x$ such that the
residual error is a non-trivial logical error of the surface code.

To guarantee that the soft UF decoder performs well, we assume that the
graphical model satisfies the following topological property.

(C3) Let $\tilde{x}$ be a fault set with trivial syndrome. If the diameter of
$\tilde{x}$ satisfies $\operatorname{diam}_{w}(\tilde{x})<d_{w}$ then $\pi(x)$
is a stabilizer of the surface code.

Both soft circuit noise and soft phenomenological noise satisfy this condition
with Gaussian soft measurements and amplitude damping soft measurements, which
include the cases we study numerically.

###  4.2 Success of the soft MWPM decoder

The goal of this section is to prove the following result.

######  Theorem 4.1.

For any graphical model satisfying (C1) and (C2), the soft MWPM decoder
(Algorithm 1) returns a most likely fault set.

###### Proof.

Let $m$ be a set of soft outcomes for a graphical model $(G_{T},p,f)$ and let
$\hat{s}$ be the corresponding syndrome. Given $m$ as an input, Algorithm 1
first generates the distance graph $K(\hat{s})=(V_{K},E_{K})$ associated with
$\hat{s}$. Then, it computes a minimum weight matching $M\subseteq E_{K}$ and
the corresponding 1-chain

$\tilde{x}_{M}=\sum_{\\{u,v\\}\in M}\operatorname{geo}(u,v)$

in the decoding graph $\tilde{G}_{T}$. The output of Algorithm 1 is the fault
set $x_{M}$ which is the restriction of $\tilde{x}_{M}$ to $G_{T}$. We will
prove by contradiction that it is a most likely fault set conditioned on the
set of soft outcomes $m$.

Assume that there exists a fault set $x^{\prime}$ (that is a 1-chain in
$G_{T}$) such that ${\mathbb{P}}(x^{\prime}|m)>{\mathbb{P}}(x|m)$. Consider
the extension $\tilde{x}^{\prime}=x^{\prime}+x_{\operatorname{soft}}^{\prime}$
as a 1-chain of $\tilde{G}_{T}$ obtained by adding the soft flip of
$x^{\prime}$. The value of $x^{\prime}_{\operatorname{soft}}$ can be derived
from $x^{\prime}$ and $\hat{s}$. By Lemma 4.2, the support of
$\tilde{x}^{\prime}$ contains a set of edge-disjoint paths in $G_{T}$
connecting each vertex of $\hat{s}$ either with another vertex of $\hat{s}$ or
with a boundary vertex. One can prove the existence of these paths by
induction. If our set of paths contains two paths connecting to the boundary,
we merge these two paths into a single paths in $\tilde{G}_{T}$. Then, each
path of this set corresponds to an edge in $K(\hat{s})$ and the complete set
of paths induces a perfect matching $M^{\prime}$ in $K(\hat{s})$. Moreover,
the weight of the matching $M^{\prime}$, which is a sum of weights of edges
included in $\tilde{x}^{\prime}$, satisfies
$w(M^{\prime})\leq\sum_{e\in\tilde{x}}w(e)$. Based on Lemma 4.3, this weight
is equal to

$\displaystyle
w(M^{\prime})\leq\sum_{e\in\tilde{x}^{\prime}}w(e)=C-\log{\mathbb{P}}(x^{\prime}|m)\cdot$

Using the assumption ${\mathbb{P}}(x^{\prime}|m)>{\mathbb{P}}(x_{M}|m)$, this
yields

$\displaystyle w(M^{\prime})$ $\displaystyle\leq
C-\log{\mathbb{P}}(x^{\prime}|m)$ $\displaystyle<C-\log{\mathbb{P}}(x_{M}|m)$
$\displaystyle<\sum_{e\in x_{M}}w_{K}(e)=w(M),$

which contradicts the minimality of $M$. This concludes the proof of the
proposition. ∎

In the proof of 4.1 we relied on the following two lemmas.

######  Lemma 4.2.

Let $x$ be a fault set for the graphical model $(G_{T},p,f,\pi)$ and let $m$
be a set of soft outcomes observed in the measurement vertices. Then, the
syndrome of $x$ satisfies

$\displaystyle\hat{s}(m)=\partial_{{V_{\bullet}}}(\tilde{x})$ (9)

where $\tilde{x}=x+x_{\operatorname{soft}}$ and $x_{\operatorname{soft}}$ is
the 1-chain of soft flips.

###### Proof.

To prove that the syndrome is equal to $\partial_{{V_{\bullet}}}(\tilde{x})$,
consider the syndrome value at a measurement vertex $(a,t)$. Assume first that
no soft flip occurs in this vertex. Then, the hard outcome and the ideal
outcome are identical and by definition of the syndrome, we have
$\hat{s}(a,t)=\overline{m}(a,t)+\overline{m}(a,t-1)\pmod{2}\cdot$ Using the
definition of the ideal outcome, we see that this number is the parity of the
number of edges of $x$ that are incident to $(a,t)$. This proves Eq. 9 in the
absence of soft flip. This equation is also satisfied if a soft flip occurs in
$(a,t)$ thanks to the additional vertical soft edge incident to $(a,t)$. ∎

######  Lemma 4.3.

Let $x$ be a fault set for a graphical model $(G_{T},p,f,\pi)$ and let $m$ be
the set of soft outcomes measured. The probability ${\mathbb{P}}(x|m)$ of the
fault set $x$ conditioned on the soft measurement outcome $m$ is given by

$\displaystyle\log{\mathbb{P}}(x|m)=C+\sum_{e\in\tilde{x}}w(e)$ (10)

where $\tilde{x}=x+x_{\operatorname{soft}}$ and $x_{\operatorname{soft}}$ is
the 1-chain of soft flips, for some constant $C$ that is independent of $x$.

###### Proof.

To compute ${\mathbb{P}}(x|m)$, we apply Bayes theorem to obtain

$\displaystyle{\mathbb{P}}(x|m)\propto{\mathbb{P}}(m|x){\mathbb{P}}(x)\cdot$
(11)

Here, we abuse notation and use ${\mathbb{P}}(m|x)$ to represent the
probability density function of the continuous random variable $m$ conditioned
on $x$. For simplicity, we focus on continuous distributions over sets of soft
outcomes $m$, but the same argument applies to discrete soft outcome
distributions.

We will consider the two terms of the right hand side of Eq. 11 separately.

Based on Eq. 4, we have ${\mathbb{P}}(x)=C_{1}\prod_{e\in
x}\frac{p_{e}}{1-p_{e}}$ where $C_{1}$ is the product of all the terms
$(1-p_{e})$ with $e\in E_{T}$. Taking the $\log$, this yields

$\displaystyle\log{\mathbb{P}}(x)=C_{1}^{\prime}+\sum_{e\in
x}+\log\left(\frac{p_{e}}{1-p_{e}}\right),$ (12)

for some constant $C_{1}^{\prime}$.

Consider now ${\mathbb{P}}(m|x)$. By definition of $m$, we have
${\mathbb{P}}(m|x)={\mathbb{P}}(m|\overline{m})$. Because the soft outcomes in
different measurement vertices $(a,t)$ are independent, we have

$\displaystyle{\mathbb{P}}(m|\overline{m})$
$\displaystyle=\prod_{(a,t)\in{V_{\bullet}}}{f}^{(\overline{m}_{a,t})}_{a,t}(m_{a,t})$
$\displaystyle=\prod_{\begin{subarray}{c}(a,t)\in{V_{\bullet}}\\\
\overline{m}_{a,t}=\hat{m}_{a,t}\end{subarray}}{f}^{(\hat{m}_{a,t})}_{a,t}(m_{a,t})$
$\displaystyle\times\prod_{\begin{subarray}{c}(a,t)\in{V_{\bullet}}\\\
\overline{m}_{a,t}\neq\hat{m}_{a,t}\end{subarray}}{f}^{(\hat{m}_{a,t}+1)}_{a,t}(m_{a,t})$
$\displaystyle=\prod_{(a,t)\in{V_{\bullet}}}{f}^{(\hat{m}_{a,t})}_{a,t}(m_{a,t})$
$\displaystyle\times\prod_{\begin{subarray}{c}(a,t)\in{V_{\bullet}}\\\
\overline{m}_{a,t}\neq\hat{m}_{a,t}\end{subarray}}\frac{{f}^{(\hat{m}_{a,t}+1)}_{a,t}(m_{a,t})}{{f}^{(\hat{m}_{a,t})}_{a,t}(m_{a,t})}$
$\displaystyle=C_{2}\prod_{\begin{subarray}{c}(a,t)\in{V_{\bullet}}\\\
\overline{m}_{a,t}\neq\hat{m}_{a,t}\end{subarray}}L_{a,t}(m_{a,t})$

$C_{2}=\prod_{(a,t)\in{V_{\bullet}}}{f}_{a,t}^{(\hat{m}_{a,t})}(m_{a,t})$
depends only on the set of soft outcomes $m$, since $\hat{m}$ is fully
determined by $m$. The condition $\overline{m}_{a,t}\neq\hat{m}_{a,t}$ in the
second product is equivalent to the presence of a soft flip in $(a,t)$.
Therefore, taking the $\log$ we obtain

$\displaystyle\log{\mathbb{P}}(m|\overline{m})=C_{2}^{\prime}+\sum_{e\in
x_{\operatorname{soft}}}-\log L_{a,t}(m_{a,t})\cdot$ (13)

By definition of the edge weights in the decoding graph, combining Eqs. 11, 12
and 13 concludes the proof of the lemma. ∎

From 4.5 and Lemma 4.3 we can infer the following useful corollary.

######  Corollary 4.4.

For any graphical model satisfying (C1) and (C2), the soft MWPM decoder
(Algorithm 1) successfully corrects all fault sets such that
$|\tilde{x}|_{w}<d_{w}/2$.

###### Proof.

Let $x$ be the fault set which occurs and let $m$ be the set of soft outcomes
observed. Assume that $|\tilde{x}|_{w}<d_{w}/2$. By 4.5, the soft MWPM decoder
returns a fault set $y$ such that ${\mathbb{P}}(y|m)\leq{\mathbb{P}}(x|m).$ By
Lemma 4.3, this translates into

$\displaystyle\sum_{e\in\tilde{y}}w(e)\leq\sum_{e\in\tilde{x}}w(e)$ (14)

which means $|\tilde{y}|_{w}\leq|\tilde{x}|_{w}$. As a result, the residual
fault set after correction $\tilde{x}+\tilde{y}$ has weight at most
$|\tilde{x}+\tilde{y}|\leq 2|\tilde{x}|_{w}<d_{w}$ proving the decoder
succeeds. ∎

###  4.3 Success of the soft UF decoder

Above we saw in 4.4 that the soft MWPM decoder successfully corrects all fault
sets such that $|\tilde{x}|_{w}<d_{w}/2$. Here we establish a similar
sufficient condition for the soft UF decoder.

######  Theorem 4.5.

For any graphical model satisfying (C1), (C2) and (C3), the soft UF decoder
(Algorithm 2) successfully corrects any fault set such that
$|\tilde{x}|_{w}<d_{w}/2$.

###### Proof.

Let $x$ be a fault set such that $|\tilde{x}|_{w}<d_{w}/2$. Consider the graph
$\tilde{H}_{T}(\gamma)$ represented in Figure 7 induced by the grown edges at
the end of the growth. For each edge $e=\\{u,v\\}$ of $\tilde{H}_{T}$ where
$v$ is the splitting vertex, if $\gamma(e)=w(e)$, then $\tilde{H}_{T}(\gamma)$
contains the edge $e$, otherwise it contains an edge $\\{u,u^{\prime}\\}$ with
length $\gamma(e)$ which represents the grown part of the edge $e$.

Denote by $\Gamma_{1},\Gamma_{2},\dots$ the growth rates in step 6 of
Algorithm 2. The connected components $C_{1},C_{2},\dots$ of
$\tilde{H}_{T}(\gamma)$ satisfy

$\displaystyle\sum_{i}\operatorname{diam}_{w}(C_{i})\leq 2\sum_{j}\Gamma_{j},$
(15) $\displaystyle\sum_{e\in\tilde{x}}\gamma(e)\geq\sum_{j}\Gamma_{j}.$ (16)

The first equation holds because during the $j$th growth step, the selected
cluster grows in all directions of $\Gamma_{j}$. Moreover, because the growing
cluster is odd, this growth step covers at least a fraction $\Gamma_{j}$ of an
edge of $x$, leading to the second equation. Combining the two equations
above, we obtain

$\displaystyle\sum_{i}\operatorname{diam}_{w}(C_{i})\leq
2\sum_{e\in\tilde{x}}\gamma(e)\cdot$ (17)

Let $\tilde{y}$ be the fault set returned by the peeling decoder in step 9 and
let $\tilde{z}=\tilde{x}+\tilde{y}$. Denote by
$\tilde{z}_{1},\tilde{z}_{2},\dots$ the connected components of $\tilde{z}$.
By construction $\tilde{y}$ is included in $\tilde{H}_{T}(\gamma)$. The only
edges of $\tilde{z}$ outside of $\tilde{H}_{T}(\gamma)$ are the edges of
$\tilde{x}$ such that $\gamma(e)=0$. As a result, we have

$\displaystyle\sum_{k}\operatorname{diam}_{w}(z_{k})$
$\displaystyle\leq\sum_{i}\operatorname{diam}_{w}(C_{i})+\sum_{\begin{subarray}{c}e\in\tilde{x}\\\
\gamma(e)=0\end{subarray}}w(e)$ (18) $\displaystyle\leq
2\sum_{e\in\tilde{x}}\gamma(e)+\sum_{\begin{subarray}{c}e\in\tilde{x}\\\
\gamma(e)=0\end{subarray}}w(e)$ (19) $\displaystyle\leq
2|\tilde{x}|_{w}<d_{w}\cdot$ (20)

Therein, the second inequality is obtained by applying Eq. 17. Because the
last round of measurement is assumed to be perfect and the decoder returns a
fault set $\tilde{y}$ which has the same syndrome as $\tilde{x}$, the residual
fault set after correction $\tilde{z}$ has trivial syndrome and we proved that
it obeys $|\tilde{z}|<d_{w}$. Therefore, applying (C3), the decoder succeeds.
∎

##  5 Performance of soft decoders

Figure 8:  The failure probability of the protocol for $d$ rounds of error
correction with soft phenomenological noise using the hard Union Find decoder
(left) and the soft Union Find decoder (right). In this noise model the $X$
and $Z$ errors are identical and independent, with the $X$ error probability
$p_{D}=p$, no hard ideal outcome flips $p_{M}=0$, and with Gaussian soft noise
with a spread $\sigma$ selected such that $p_{M,\text{hardened}}=p$. The
threshold value $p^{*}$ for each decoder is estimated from the crossings of
curves of different distance, and one standard deviation of uncertainty is
shaded.  Figure 9:  The threshold $p^{*}$ obtained with the soft decoder with
soft phenomenological noise with different ratios of soft to hard noise in the
measurement. In this noise model the $X$ and $Z$ errors are identical and
independent, with the $X$ error probability $p_{D}=p$, with a variable ratio
$r=p_{M,\text{soft}}/p_{M,\text{hardened}}$ but with the overall hardened flip
probability $p_{M,\text{hardened}}=p$. The threshold of the hard Union Find
decoder is the same for all values of $r$ and is indicated with a dashed line.
Note that $r=1$ corresponds to the setting of Figure 8 in which there is no
hard measurement flip, while $r=0$ corresponds to the only measurement noise
being a hard flip. The optimal threshold with a hard decoder was estimated in
Ref. [21] and is indicated with a solid horizontal line with numerical
uncertainty indicated with green shading.  Figure 10:  The failure probability
of the protocol for $d$ rounds of error correction with soft circuit noise
using the hard Union Find decoder (left) and the soft Union Find decoder
(right). We set $p_{IG}$, $p_{IM}$ and $p_{\text{CNOT}}$ equal to $p$, set
$p_{M}=0$ and use ${f}^{(0)}={\cal N}(+1,\sigma^{2})$ and ${f}^{(1)}={\cal
N}(-1,\sigma^{2})$ with $\sigma$ chosen such that $p_{M,\text{hardened}}=10p$.
The threshold value $p^{*}$ for each decoder is estimated from the crossings
of curves of different distance, and one standard deviation of uncertainty is
shaded.

In this section we analyze the performance of some of the decoders defined in
Section 3 under the soft noise models defined in Section 2. In particular we
compare the soft Union Find decoder that we have introduced with the standard
hard Union Find decoder that has access only to the hardened outcomes produced
by discretizing the soft measurement outcomes. In Section 5.1 we first specify
the protocol we use to evaluate the error correction performance, along with
other definitions used in the numerical analysis. Then in Section 5.2 and
Section 5.3 we present our numerical results for the performance of the soft
Union Find decoder under soft phenomenological and soft circuit noise
respectively.

###  5.1 Error correction protocol

It can be desirable to define a notion of logical error rate as the
probability that a logical operation fails given a specific noise model and
decoding scheme. In this section we describe how we estimate the logical error
rate of a noise model equipped with a decoder using Monte Carlo simulations.
Our simulations use a protocol starting with a perfectly prepared code state
which undergoes $T$ rounds of noisy syndrome measurements before a final round
of perfect syndrome measurement, which specifies a graphical noise model
$(G_{T},p,f,\pi)$.

In a Monte Carlo run of this protocol, first a fault set $x$ is sampled
according to the distribution ${\mathbb{P}}$ associated with the noise model.
For each fault $e$ in $x$, the corresponding residual error $\pi_{e}$ is
applied to the data qubits. Then, for each measurement vertex $(a,t)$
(including the final round of perfect measurement), the ideal outcome
$\overline{m}_{a,t}$ is computed and a soft outcome $m_{a,t}$ is sampled
according to the distribution $f_{a,t}^{(\overline{m}_{a,t})}$. Based on the
set of soft outcomes, the decoder returns a fault set $y$ and a correction

$\displaystyle\pi(y)=\prod_{e\in y}\pi_{e}$ (21)

is applied to the data qubits intending to cancel the effect of $x$. The
residual error on the data qubits after correction is then $\pi(x)+\pi(y)$.

Since the protocol ends with a perfect round of measurement, the decoders
studied here are guaranteed to produce a correction with a residual error
which is either a stabilizer or a non-trivial logical operator for the surface
code. We say the decoder succeeds if the residual error $\pi(x)+\pi(y)$ is a
stabilizer. Otherwise, we say the decoder fails. With a distance-$d$ surface
code, the failure probability of the protocol $p^{\text{fail}}_{d}(T)$ is the
expected value that the protocol fails, and in practice we estimate it from
the fraction of failures among a finite number of samples. The decoders we
study act separately on $X$ and $Z$ errors. We often find it convenient to
separately consider the probability $p^{X\text{fail}}_{d}(T)$ of a logical $X$
failure of the protocol, irrespective of whether or not there is a logical $Z$
failure.

There are a number of approaches in the literature to estimate a logical error
rate from the failure probability of this kind of protocol. The simplest and
most standard approach is to simply set $T=d$ and take
$p^{\text{fail}}_{d}(d)$ itself to be an estimate of the logical error rate.
The reason for setting $T=d$ in this approach is that typically logical error
operations (such as lattice surgery) with the surface code are assumed to take
$d$ rounds to ensure fault tolerance. However, the fact that the protocol ends
with a perfect measurement round can lead this approach to significantly
underestimate the true logical failure rate of a logical operation which takes
$d$ rounds [18]. Another drawback of this approach is that some logical
operations may not take $d$ rounds.

Here we instead estimate the logical failure rate per round, which we denote
by $\bar{p}_{d}$, which can then be multiplied by the number of rounds in a
logical operation to indicate its logical error rate. To avoid dependence on
the perfect preparation and final stabilizer measurement round in the protocol
on our estimate, we use a model of the protocol which applies for long times
$T$. Our model is based on the assumption that during each round a logical $X$
error occurs with probability $\bar{p}/2$ independently of other rounds [39].
After $T$ rounds, there is a logical $X$ failure in this model if an odd
number of rounds have experienced logical $X$ errors, which occurs with
probability

$\displaystyle\hat{p}^{X~{}\text{fail}}(T)=\frac{1-(1-\bar{p})^{T}}{2},$ (22)

which can be inverted to give
$\bar{p}=1-(1-2\hat{p}^{X~{}\text{fail}}(T))^{1/T}$. We use a hat to
differentiate the failure probability $\hat{p}^{X~{}\text{fail}}(T)$ of our
model from the failure probability $p^{X~{}\text{fail}}(T)$ of the protocol
itself. Assuming the validity of this model becomes accurate for large $T$, we
take the logical failure rate per round $\bar{p}_{d}$ to be calculated from
the protocol’s failure probability according to

$\displaystyle\bar{p}_{d}(T)$
$\displaystyle=1-(1-2p_{d}^{X~{}\text{fail}}(T))^{1/T},$ (23)
$\displaystyle\bar{p}_{d}$
$\displaystyle=\lim_{T\to\infty}\left(\bar{p}_{d}(T)\right).$ (24)

In practice we estimate $\bar{p}_{d}$ by evaluating $\bar{p}_{d}(T)$ for a
large value of $T$. More details on this model’s validity, and on the
numerical convergence of Eq. 24 can be found in Appendix C.

The error correction threshold is the value of a single-parameter noise model
below which error correction can be performed to achieve arbitrarily good
protection by increasing the code distance. For noise models which have a
number of parameters such as the soft noise models we have introduced, the
concept of a threshold generalizes to a threshold surface [40]. Alternatively,
one can introduce constraints on the parameters of a nosie model so that only
one free parameter remains, and then consider the threshold value of the
resulting single-parameter noise model. There are many approaches to
numerically estimate the value of the threshold, all of which can be expected
to agree in the limit of large code distances [41] because they are asymptotic
properties of a phase boundary [4]. Here we estimate the threshold $p^{*}$ of
single-parameter noise model using the standard approach of identifying the
intersections of the curves $p^{\text{fail}}(d)$ for different distances as a
function of the parameter $p$.

###  5.2 Performance under soft phenomenological noise

Here we consider the soft phenomenological noise model which was defined in
Section 2.3 and use the notation therein. In this model, the $X$ and $Z$
errors are generated and corrected independently. For simplicity we focus on
the $X$ errors here – the $Z$ errors are handled in the same way.

Recall that in this model, probabilities $p_{D}$ and $p_{M}$ are assigned to
horizontal and vertical edges in the $X$-type fault graph $G_{T}$
respectively, and the pair of Gaussian probability density functions
${f}^{(0)}={\cal N}(+1,\sigma^{2})$ and ${f}^{(1)}={\cal N}(-1,\sigma^{2})$
are assigned to each measurement vertex in $G_{T}$.

In Figure 8 we obtain a single-parameter noise model from the phenomenological
noise model by setting $p_{D}=p$, $p_{M}=0$ and setting $\sigma$ such that
$p_{M,\text{hardened}}=p$, where $p_{M,\text{hardened}}$ is calculated
according to Eq. 3. We plot the failure probability of the protocol for $d$
rounds using the soft UF decoder and the hard UF decoder, and estimate the
threshold $p^{*}$ by considering the crossings of the resulting curves for
different values of $d$. Note that the failure probabilities
$p^{\text{fail}}_{d}(T)$ reported include failures of both $X$ and $Z$ type.
We observe that the soft UF decoder significantly outperforms the hard UF
decoder, exhibiting a threshold of $3.665(2)\text{\times}{10}^{-2}$ versus
$2.637(1)\text{\times}{10}^{-2}$. Moreover, the optimal threshold of a decoder
using hard information only is $2.93(2)\text{\times}{10}^{-2}$ [21] which is
still below the value obtained using the soft UF decoder.

In Figure 9 we repeat this analysis again with $p_{D}=p$ and
$p_{M,\text{hardened}}=p$, but with different fixed values of
$r=p_{M,\text{soft}}/p_{M,\text{hardened}}$. For each value of $r$, this
specifies a single-parameter noise model for which we can estimate the
threshold using the same approach as was used in Figure 8 for the case $r=1$.
We plot these estimated threshold values for various values of $r$ in Figure
9.

Note that by construction the hard noise models which are obtained by
hardening the soft phenomenological noise models we study in Figure 8 and
Figure 9 reduce to the standard single-parameter phenomenological noise model.
In particular, the hardened version of the soft noise model for all values of
$r$ has $X$ error on each qubit with probability $p_{D}=p$ and outcome flips
of each plaquette measurement with the same probability
$p_{M,\text{hardened}}=p$.

###  5.3 Performance under soft circuit noise

Figure 11:  The failure probability per round for low error rates with the
same soft circuit noise parameterization as in Figure 10. We estimate the
failure rate per round $\bar{p}_{d}$ from the failure probability of the
protocol for $T=1000$ rounds using Eq. 24.

Here we consider the soft circuit noise model which was defined in Section
2.4. Recall that in this model, probabilities $p_{IG}$, $p_{IM}$ and
$p_{\text{CNOT}}$ specify the probabilities of each possible fault of idle
qubits during CNOT time steps, idle qubits during measurement time steps, and
faults of CNOT operations. Additionally, the probability $p_{M}$ specifies the
flip of ideal outcomes, and probability distribution functions
$\\{{f}^{(0)}(\mu),{f}^{(1)}(\mu)\\}$ characterize the soft noise. For the
numerical studies here we use the standard exclusive circuit noise model to
generate the faults (see Appendix B), while we use the inclusive circuit noise
model is Section 2.4 to specify the edge weights of the decoder as described
in Section 3.2. To improve the performance of the decoder, we merge all edges
sharing the same endpoints in the decoding graph and combine their edge
weights using the formula given in Appendix E of [18].

In Figure 10 we obtain a single-parameter noise model from the soft circuit
noise model by setting $p_{IG}=p$, $p_{IM}=p$, $p_{\text{CNOT}}=p$, $p_{M}=0$
and setting ${f}^{(0)}={\cal N}(+1,\sigma^{2})$ and ${f}^{(1)}={\cal
N}(-1,\sigma^{2})$ with $\sigma$ chosen such that $p_{M,\text{hardened}}=10p$.
We plot the failure probability of the protocol for $d$ rounds using the soft
UF decoder and the hard UF decoder, and estimate the threshold value of $p$ by
considering the crossings of the resulting curves for different values of $d$.
We observe that the soft UF decoder outperforms the hard UF decoder,
exhibiting a threshold of $5.824(6)\text{\times}{10}^{-3}$ versus
$4.991(5)\text{\times}{10}^{-3}$. In Figure 11 we estimate the failure rate
per round $\bar{p}_{d}$ using the soft UF decoder and the hard UF decoder with
Eq. 24 for $T=1000$ rounds.

For many hardware approaches, the readout fidelity can be significantly lower
than the gate fidelity, which motivated us to consider a measurement flip
probability $p_{M,\text{hardened}}$ which was ten times larger than the gate
error probability in Figure 10. In Table 1 we list a number of threshold
values including those for soft circuit noise but with $p_{M,\text{hardened}}$
equal to the gate error probability, in which case the threshold gap for the
hard and soft decoder is less pronounced due to the relatively larger effects
of ancilla qubit errors during the syndrome extraction circuit.

soft noise |  soft UF threshold |  hard UF threshold
---|---|---
phenomenological |  $3.665(2)\text{\,}\mathrm{\char 37\relax}$ |  $2.637(1)\text{\,}\mathrm{\char 37\relax}$
circuit $p_{M,\text{hardened}}=p$ |  $0.727(1)~{}\text{\,}\mathrm{\char 37\relax}$ |  $0.702(1)~{}\text{\,}\mathrm{\char 37\relax}$
circuit $p_{M,\text{hardened}}=10p$ |  $0.5824(6)\text{\,}\mathrm{\char 37\relax}$ |  $0.4991(5)\text{\,}\mathrm{\char 37\relax}$
Table 1:  Thresholds observed when using the soft and hard decoders for
various soft noise models. For soft phenomenological noise we set $p_{D}=p$,
$p_{M}=0$ and $\sigma$ is chosen such that $p_{M,\text{hardened}}=p$. We
consider two cases for soft circuit noise, each with
$p_{IG}=p_{IM}=p_{\text{CNOT}}=p$ and $p_{M}=0$, but with different
$p_{M,\text{hardened}}$.

##  6 Measurement time tradeoff

Figure 12:  The logical error rate per round $\bar{p}_{d}$ for the parametric
circuit noise model defined in section Section 6 as a function of measurement
time $\tau_{M}$. The $\tau_{M}$ which minimizes $\bar{p}_{d}$ depends on the
distance and decoder. The vertical dashed line marks the measurement time that
minimizes the average soft-flip probability of a single measurement with
respect to measurement time (instead of the logical error rate), and leads to
sub-optimal logical error rates.

In this section, we establish that the use of soft information can provide an
advantage in the overall logical cycle time of a quantum computing platform in
a model that considers the effects of measurement time. In real quantum error
correction applications, selecting a measurement time for measurements
represents a trade-off between measurement noise and data noise: Using too
short a measurement time gives little information about the state of the
ancilla. However, too long a measurement time gives time for additional errors
to accumulate on the data.

We define an experimentally motivated variant of the soft circuit noise model
where the noise parameter for each fault location is adjusted based on the
duration that each circuit operation takes. Recall that in the soft circuit
noise model, probabilities $p_{IG}$, $p_{IM}$ and $p_{\text{CNOT}}$ specify
the probabilities of each possible fault of idle qubits during CNOT time
steps, idle qubits during measurement time steps, and faults of CNOT
operations. Additionally, $p_{M}$ specifies the probability of a flip of an
ideal outcome, and the probability distribution functions
$\\{{f}^{(0)}(\mu),{f}^{(1)}(\mu)\\}$ characterize the soft noise. In our
parametric circuit noise model, we consider:

  * •

$p_{IG}=1-e^{-\frac{\tau_{G}}{\tau_{D}}}$,

  * •

$p_{IM}=1-e^{-\frac{\tau_{M}}{\tau_{D}}}$,

  * •

$p_{\text{CNOT}}=1-e^{-\frac{\tau_{G}}{\tau_{D}}}$,

  * •

$p_{M}=0$ and
${f}^{(\bar{\mu})}(\mu)={f}^{(\bar{\mu})}(\mu;\tau_{M},\operatorname{\tau_{A}}1m,\tau_{F})$.

This noise model assumes depolarizing noise, with additional Gaussian soft
noise with amplitude damping during measurement. As such, our parametric
circuit noise model is expressed in terms of the depolarizing time $\tau_{D}$,
the gate and measurement times $\tau_{G}$ and $\tau_{M}$, along with
additional parameters which specify the amplitude damping channel including
the relaxation time $\operatorname{\tau_{A}}1m$ and the fluctuation time
$\tau_{F}$ as described in Section 1.4 and Appendix A. As in Section 5.3 we
use the standard exclusive circuit noise model to generate the faults in our
numerical simulations here, while we use the inclusive noise model to specify
the edge weights of the decoder.

In Figure 12 we explore the effect of measurement time on the failure
probability. In this plot, we set $\tau_{G}=$10\text{\,}\mathrm{ns}$$,
$\tau_{D}=$30\text{\,}\mathrm{\SIUnitSymbolMicro s}$$,
$\operatorname{\tau_{A}}1m=$15\text{\,}\mathrm{\SIUnitSymbolMicro s}$$,
$\tau_{F}=$100\text{\,}\mathrm{ns}$$ and vary $\tau_{M}$. These parameters are
within the range that can be expected to be achievable using near-term
experiments [42, 43, 44, 45, 46]. We plot the failure rate per round
$\bar{p}_{d}$ using the soft UF decoder and the hard UF decoder, by using Eq.
24 for $T=1000$ rounds.

In contrast, we may choose $\tau_{M}$ to minimize the average soft flip
probability $\frac{1}{2}{\mathbb{P}}(\text{soft
flip}|0)+\frac{1}{2}{\mathbb{P}}(\text{soft flip}|1)$ for a single measurement
under the Gaussian soft noise with amplitude damping model (a metric often
considered in experimental demonstrations). This ignores the errors that
accumulate in the data qubits during the measurement of the ancilla, but
minimizes the probability of errors in the hard decision for each measurement
(for details see Appendix A).

For a long measurement time $\tau_{M}$, the data qubit noise rate per round is
high and as a result the logical failure probability approaches that of a
maximally mixed state. If the measurement time is too short, the information
obtained by the syndrome extraction circuit is not reliable enough, which
translates into a high logical error rate. In order to obtain the best
possible logical qubit, we should select the measurement time that minimizes
the logical error rate. In Figure 12, we observe that the optimal measurement
time using the soft decoder is reached around
$\tau_{M}/\tau_{A}=$1\text{\times}{10}^{-2}$$ with a logical error rate per
round close to $1\text{\times}{10}^{-7}$ for distance 19. For comparison, if
the measurement time is selected by minimizing the average soft-flip
probability, the measurement time is roughly five times longer and, for
distance 19, the logical error rate per round increases by nearly three orders
of magnitude to $1\text{\times}{10}^{-4}$. In these numerical results, we also
observe that the optimal measurement time for the soft UF decoder is shorter
than the optimal measurement for the hard UF decoder, which indicates that
metric to optimize is not simply a function of the soft flip probabilities and
the error rates on data qubits (as these are the same for the hard and soft
decoders).

##  7 Conclusion

We have described a general framework that incorporates soft information into
fault-tolerant quantum error correction with the surface code. This framework
is independent of the physical realization of the qubits, and requires only
knowledge of the distributions of soft outcomes conditioned on the qubit
state. We give explicit constructions of two soft decoders for the surface
code: a soft Minimum Weight Perfect Matching decoder (which we show identifies
a most likely fault set for soft information), and a soft Union-Find decoder.
Both of these decoders have the same computational complexity as their
counterparts that handle only hard information, while the soft Union-Find
decoder has lower computational overhead than the soft Minimum Weight Perfect
Matching decoder.

We introduce two error models to evaluate the decoder performance: one where
the syndrome is corrupted by Gaussian noise, and another where the syndrome is
corrupted by Gaussian noise and amplitude damping. We show that under these
error models the soft Union-Find decoder outperforms its hard counterpart both
in terms of error threshold as well as sub-threshold logical error rate.
Notably, the soft Union-Find decoder has a threshold that is $25\%$ larger
than the best possible hard decoder for the surface code, as estimated by
statistical mechanics models. These error models were also used to study the
trade-off between measurement time and logical error rate, where we found a
strong dependence between these quantities, and showed that optimizing the
measurement time with awareness of error correction can reduce the measurement
time five-fold while decreasing the the logical error rate a thousand fold
(even for relatively modest surface code distances). This highlights the
benefits of jointly optimizing the physical layer and the error correction
layer.

It would be valuable to develop theoretical methods to study the optimal
decoding threshold for soft noise in the surface code—for example, by
searching for a mapping to a generalized classical random-bond Ising model in
which subsets of binary spins are be replaced by continuous variables.

Beyond surface codes, it would be interesting to explore these soft decoders
with other codes such as color codes [47], other surface code variants [48]
and some quantum Low-Density Parity-Check codes [49].

Given the gains observed with the use of soft information in the surface code,
we expect that the addition of soft information to the quantum fault tolerance
arsenal will shorten the time horizon for useful scalable quantum computers.

##  8 Acknowledgment

M.E.B, M.P.S, and N.D. thank David Poulin for his friendship, inspiration, and
mentorship, as well as encouragement in the early stages of this work. C.A.P.
acknowledges helpful discussions with Evan Zalys-Geller and Microsoft Quantum
for support during his internship. C.A.P. is supported in part by Air Force
Office of Scientific Research (AFOSR), FA9550-19-1-0360.

## References

  * Shor [1996] P. Shor, Fault-tolerant quantum computation, in  _Proceedings of 37th Conference on Foundations of Computer Science_ (1996) pp. 56–65.
  * Kitaev [2003a] A. Y. Kitaev, Fault-tolerant quantum computation by anyons, Annals of Physics 303, 2–30 (2003a).
  * Raussendorf and Harrington [2007] R. Raussendorf and J. Harrington, Fault-tolerant quantum computation with high threshold in two dimensions, Physical Review Letters 98, 190504 (2007).
  * Dennis  _et al._ [2002] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Topological quantum memory, Journal of Mathematical Physics 43, 4452–4505 (2002).
  * Fowler  _et al._ [2009] A. G. Fowler, A. M. Stephens, and P. Groszkowski, High-threshold universal quantum computation on the surface code, Physical Review A 80, 052312 (2009).
  * Bravyi  _et al._ [2018] S. Bravyi, M. Englbrecht, R. König, and N. Peard, Correcting coherent errors with surface codes, npj Quantum Information 4, 1–6 (2018).
  * Wang  _et al._ [2011] J. Wang, T. Courtade, H. Shankar, and R. D. Wesel, Soft information for LDPC decoding in flash: Mutual-information optimized quantization, in  _2011 IEEE Global Telecommunications Conference-GLOBECOM 2011_ (IEEE, 2011) pp. 1–6.
  * Costello and Forney [2007] D. J. Costello and G. D. Forney, Channel coding: The road to channel capacity, Proceedings of the IEEE 95, 1150–1177 (2007).
  * Gottesman  _et al._ [2001] D. Gottesman, A. Kitaev, and J. Preskill, Encoding a qubit in an oscillator, Physical Review A 64, 012310 (2001).
  * Fukui  _et al._ [2017] K. Fukui, A. Tomita, and A. Okamoto, Analog quantum error correction with encoding a qubit into an oscillator, Physical Review Letters 119, 180507 (2017).
  * Vuillot  _et al._ [2019] C. Vuillot, H. Asasi, Y. Wang, L. P. Pryadko, and B. M. Terhal, Quantum error correction with the toric Gottesman-Kitaev-Preskill code, Phys. Rev. A 99, 032344 (2019).
  * Noh and Chamberland [2020] K. Noh and C. Chamberland, Fault-tolerant bosonic quantum error correction with the surface–Gottesman-Kitaev-Preskill code, Physical Review A 101, 012316 (2020).
  * Noh  _et al._ [2021] K. Noh, C. Chamberland, and F. G. Brandão, Low overhead fault-tolerant quantum error correction with the surface-GKP code, arXiv preprint arXiv:2103.06994 (2021).
  * Chamberland  _et al._ [2020] C. Chamberland, K. Noh, P. Arrangoiz-Arriola, E. T. Campbell, C. T. Hann, J. Iverson, H. Putterman, T. C. Bohdanowicz, S. T. Flammia, A. Keller, _et al._ , Building a fault-tolerant quantum computer using concatenated cat codes, arXiv preprint arXiv:2012.04108 (2020).
  * Delfosse and Nickerson [2017] N. Delfosse and N. H. Nickerson, Almost-linear time decoding algorithm for topological codes, arXiv preprint arXiv:1709.06218 (2017).
  * Bombin and Martin-Delgado [2007] H. Bombin and M. A. Martin-Delgado, Homological error correction: Classical and quantum codes, Journal of Mathematical Physics 48, 052105 (2007).
  * Delfosse [2014] N. Delfosse, Decoding color codes by projection onto surface codes, Physical Review A 89, 012317 (2014).
  * Chao  _et al._ [2020] R. Chao, M. E. Beverland, N. Delfosse, and J. Haah, Optimization of the surface code design for majorana-based qubits, Quantum 4, 352 (2020).
  * Delfosse  _et al._ [2021a] N. Delfosse, V. Londe, and M. Beverland, Toward a Union-Find decoder for quantum LDPC codes (2021a), arXiv:2103.08049 [quant-ph] .
  * Hastings and Haah [2021] M. B. Hastings and J. Haah, Dynamically generated logical qubits (2021), arXiv:2107.02194 [quant-ph] .
  * Wang  _et al._ [2003] C. Wang, J. Harrington, and J. Preskill, Confinement-Higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory, Annals of Physics 303, 31–58 (2003).
  * Berge [1973] C. Berge,  _Graphs and hypergraphs_ (North-Holland Pub. Co., 1973).
  * Fowler  _et al._ [2012] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation, Physical Review A 86, 032324 (2012).
  * Litinski [2019] D. Litinski, A game of surface codes: Large-scale quantum computing with lattice surgery, Quantum 3, 128 (2019).
  * Kitaev [2003b] A. Y. Kitaev, Fault-tolerant quantum computation by anyons, Annals of Physics 303, 2–30 (2003b).
  * Breuckmann  _et al._ [2017] N. P. Breuckmann, C. Vuillot, E. Campbell, A. Krishna, and B. M. Terhal, Hyperbolic and semi-hyperbolic surface codes for quantum storage, Quantum Science and Technology 2, 035007 (2017).
  * Gambetta  _et al._ [2007] J. Gambetta, W. A. Braff, A. Wallraff, S. M. Girvin, and R. J. Schoelkopf, Protocols for optimal readout of qubits using a continuous quantum nondemolition measurement, Phys. Rev. A 76, 012325 (2007).
  * Nielsen and Chuang [2011] M. Nielsen and I. Chuang,  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ (Cambridge University Press, 2011).
  * Blais  _et al._ [2004] A. Blais, R.-S. Huang, A. Wallraff, S. M. Girvin, and R. J. Schoelkopf, Cavity quantum electrodynamics for superconducting electrical circuits: An architecture for quantum computation, Phys. Rev. A 69, 062320 (2004).
  * Colless  _et al._ [2013] J. I. Colless, A. C. Mahoney, J. M. Hornibrook, A. C. Doherty, H. Lu, A. C. Gossard, and D. J. Reilly, Dispersive readout of a few-electron double quantum dot with fast rf gate sensors, Phys. Rev. Lett. 110, 046805 (2013).
  * Tomita and Svore [2014] Y. Tomita and K. M. Svore, Low-distance surface codes under realistic quantum noise, Physical Review A 90, 062320 (2014).
  * Garey and Johnson [1979] M. R. Garey and D. S. Johnson,  _Computers and Intractability: A Guide to the Theory of NP-Completeness_ (W. H. Freeman & Co., USA, 1979).
  * Edmonds [1965] J. Edmonds, Paths, trees, and flowers, Canadian Journal of mathematics 17, 449–467 (1965).
  * Kolmogorov [2009] V. Kolmogorov, Blossom V: a new implementation of a minimum cost perfect matching algorithm, Mathematical Programming Computation 1, 43–67 (2009).
  * Cook and Rohe [1999] W. Cook and A. Rohe, Computing minimum-weight perfect matchings, INFORMS journal on computing 11, 138–148 (1999).
  * Vazirani [1994] V. V. Vazirani, A theory of alternating paths and blossoms for proving correctness of the ${O}(\sqrt{V}{E})$ general graph maximum matching algorithm, Combinatorica 14, 71–109 (1994).
  * Huang  _et al._ [2020] S. Huang, M. Newman, and K. R. Brown, Fault-tolerant weighted Union-Find decoding on the toric code, Phys. Rev. A 102, 012419 (2020).
  * Delfosse and Zémor [2020] N. Delfosse and G. Zémor, Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel, Physical Review Research 2, 033042 (2020).
  * Chen  _et al._ [2021] Z. Chen, K. J. Satzinger, J. Atalaya, A. N. Korotkov, A. Dunsworth, D. Sank, C. Quintana, M. McEwen, R. Barends, P. V. Klimov, S. Hong, C. Jones, A. Petukhov, D. Kafri, S. Demura, B. Burkett, C. Gidney, A. G. Fowler, H. Putterman, I. Aleiner, F. Arute, K. Arya, R. Babbush, J. C. Bardin, A. Bengtsson, A. Bourassa, M. Broughton, B. B. Buckley, D. A. Buell, N. Bushnell, B. Chiaro, R. Collins, W. Courtney, A. R. Derk, D. Eppens, C. Erickson, E. Farhi, B. Foxen, M. Giustina, J. A. Gross, M. P. Harrigan, S. D. Harrington, J. Hilton, A. Ho, T. Huang, W. J. Huggins, L. B. Ioffe, S. V. Isakov, E. Jeffrey, Z. Jiang, K. Kechedzhi, S. Kim, F. Kostritsa, D. Landhuis, P. Laptev, E. Lucero, O. Martin, J. R. McClean, T. McCourt, X. Mi, K. C. Miao, M. Mohseni, W. Mruczkiewicz, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Newman, M. Y. Niu, T. E. O’Brien, A. Opremcak, E. Ostby, B. Pató, N. Redd, P. Roushan, N. C. Rubin, V. Shvarts, D. Strain, M. Szalay, M. D. Trevithick, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, S. Boixo, V. Smelyanskiy, Y. Chen, A. Megrant, and J. Kelly, Exponential suppression of bit or phase flip errors with repetitive error correction (2021), arXiv:arXiv:2102.06132 [quant-ph] .
  * Svore  _et al._ [2007] K. M. Svore, D. P. Divincenzo, and B. M. Terhal, Noise threshold for a fault-tolerant two-dimensional lattice architecture, Quantum Info. Comput. 7, 297–318 (2007).
  * Beverland  _et al._ [2021] M. E. Beverland, A. Kubica, and K. M. Svore, Cost of universality: A comparative study of the overhead of state distillation and code switching with color codes, PRX Quantum 2, 020341 (2021).
  * Arute  _et al._ [2019] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, Quantum supremacy using a programmable superconducting processor, Nature 574, 505–510 (2019).
  * Negîrneac  _et al._ [2021] V. Negîrneac, H. Ali, N. Muthusubramanian, F. Battistel, R. Sagastizabal, M. S. Moreira, J. F. Marques, W. J. Vlothuizen, M. Beekman, C. Zachariadis, N. Haider, A. Bruno, and L. DiCarlo, High-fidelity controlled-$z$ gate with maximal intermediate leakage operating at the speed limit in a superconducting quantum processor, Phys. Rev. Lett. 126, 220502 (2021).
  * Crippa  _et al._ [2019] A. Crippa, R. Ezzouch, A. Aprá, A. Amisse, R. Laviéville, L. Hutin, B. Bertrand, M. Vinet, M. Urdampilleta, T. Meunier, M. Sanquer, X. Jehl, R. Maurand, and S. De Franceschi, Gate-reflectometry dispersive readout and coherent control of a spin qubit in silicon, Nature Communications 10, 2776 (2019).
  * Jurcevic  _et al._ [2021] P. Jurcevic, A. Javadi-Abhari, L. S. Bishop, I. Lauer, D. F. Bogorin, M. Brink, L. Capelluto, O. Günlük, T. Itoko, N. Kanazawa, A. Kandala, G. A. Keefe, K. Krsulich, W. Landers, E. P. Lewandowski, D. T. McClure, G. Nannicini, A. Narasgond, H. M. Nayfeh, E. Pritchett, M. B. Rothwell, S. Srinivasan, N. Sundaresan, C. Wang, K. X. Wei, C. J. Wood, J.-B. Yau, E. J. Zhang, O. E. Dial, J. M. Chow, and J. M. Gambetta, Demonstration of quantum volume 64 on a superconducting quantum computing system, Quantum Science and Technology 6, 025020 (2021).
  * Xue  _et al._ [2021] X. Xue, M. Russ, N. Samkharadze, B. Undseth, A. Sammak, G. Scappucci, and L. M. K. Vandersypen, Computing with spin qubits at the surface code error threshold (2021), arXiv:2107.00628 [quant-ph] .
  * Bombin and Martin-Delgado [2006] H. Bombin and M. A. Martin-Delgado, Topological quantum distillation, Physical Review Letters 97, 180501 (2006).
  * Ataides  _et al._ [2021] J. P. B. Ataides, D. K. Tuckett, S. D. Bartlett, S. T. Flammia, and B. J. Brown, The xzzx surface code, Nature communications 12, 1–12 (2021).
  * Delfosse  _et al._ [2021b] N. Delfosse, V. Londe, and M. Beverland, Toward a union-find decoder for quantum ldpc codes, arXiv preprint arXiv:2103.08049 (2021b).
  * Gambetta  _et al._ [2008] J. Gambetta, A. Blais, M. Boissonneault, A. A. Houck, D. I. Schuster, and S. M. Girvin, Quantum trajectory approach to circuit qed: Quantum jumps and the zeno effect, Phys. Rev. A 77, 012112 (2008).
  * Gidney [2020] C. Gidney, Decorrelated depolarization, https://algassert.com/post/2001 (2020), accessed: 2021-07-26.
  * Gelman  _et al._ [2013] A. Gelman, J. B. Carlin, H. S. Stern, D. B. Dunson, A. Vehtari, and D. B. Rubin,  _Bayesian data analysis_ (CRC press, 2013).

##  Appendix A Gaussian soft noise with amplitude damping

We consider one of the simple measurement models described in Ref. [27],
namely, the measurement of a qubit with finite $\ket{1}$ lifetime $\tau_{A}$
and finite signal-to-noise ratio. This model was originally proposed to
describe the dispersive measurement of superconducting qubits, but it applies
to many other solid-state qubit implementations such as quantum dots. We
present the toy model here in some detail for completeness.

In our toy model we assume the Hilbert space of the quantum system is spanned
by two orthogonal states $\ket{0}$ and $\ket{1}$. Once the measurement is
turned on at time $\tau=0$, the (classical) continuous time output signal of
the measurement apparatus is given by

$\displaystyle\operatorname{d\\!}S(\tau)=v~{}R(\tau)~{}\operatorname{d\\!}\tau+\xi~{}\operatorname{d\\!}W(\tau)$
(25)

where $v$ is the signal amplitude, $R(\tau)$ is the measurement response,
$\xi$ is the noise amplitude, and $\operatorname{d\\!}W(\tau)$ is the Wiener
increment (a white Gaussian noise process with variance
$\operatorname{d\\!}\tau$ and zero mean).

We assume the state of the system collapses instantaneously into one of the
basis states once measurement starts at $\tau=0$, and that $R(\tau)$ depends
on the state of the system instantaneously, such that $R(\tau)=1$ if the
system is in state $\ket{0}$, and $R(\tau)=-1$ if the system is in state
$\ket{1}$.

The instantaneous response is important because the quantum system can
spontaneously decay at any moment from the state $\ket{1}$ to the state
$\ket{0}$ (but will remain in the $\ket{0}$ indefinitely). The decay time $K$
is an exponentially distributed random variable with rate $1/\tau_{A}$. If we
compute the probability that the system is still in state $\ket{1}$ at time
$\tau$, we find that ${\mathbb{P}}(\ket{1};\tau)=e^{-\tau/\tau_{A}}$ as
expected from the physics of spontaneous decay.

Throughout this appendix we will use capital letters to denote random
variables, and lower case letters otherwise. The probability density function
for a random variable $H$ will be denoted by $f_{H}(h)$, while the
corresponding cumulative density function will be denoted by $F_{H}(h)$, where
$F_{H}(h)=\int_{-\infty}^{h}~{}\operatorname{d\\!}{h^{\prime}}~{}f_{H}(h^{\prime})={\mathbb{P}}(H<h)$.
Following the convention in the main body of the text, superscripted random
variables indicate conditioning on the quantum basis state, while conditioning
on other random variables is indicated with the $|$ symbol.

###  A.1 Soft-outcome distributions

In order to determine what was the outcome of the quantum measurement, we
inspect the measurement signal and aim to classify the observed signal as
corresponding to a $\ket{0}$ or a $\ket{1}$ outcome. One approach is to simply
integrate the measurement signal for some measurement time $\tau_{M}$ 222The
signal may be post-processed in other ways [27, 50], but we focus on direct
integration for simplicity.. The resulting scalar is given by the random
variable

$\displaystyle S=\int_{0}^{\tau_{M}}~{}\operatorname{d\\!}S(\tau),$ (26)

and we are free to choose $\tau_{M}$ in order to improve performance (i.e.,
our ability to distinguish between $S$ when the state is $\ket{0}$ and when
the state is $\ket{1}$). We note that each realization of $S$ corresponds to
the soft outcome $\mu$.

Then, we have that

$\displaystyle S$
$\displaystyle=\int_{0}^{\tau_{M}}~{}\operatorname{d\\!}S(\tau),$ (27)
$\displaystyle=\underbrace{\int_{0}^{\tau_{M}}\operatorname{d\\!}\tau~{}v~{}R(\tau)}_{P}+\underbrace{\int_{0}^{\tau_{M}}\operatorname{d\\!}W(\tau)~{}n}_{Q}.$
(28)

It should be apparent that $Q\sim{\mathcal{N}}(0,\xi^{2}~{}\tau_{M})$
regardless of the qubit state, while the distribution for $P$ requires some
additional consideration conditioned on the initial state of the qubit.

If the initial state is $\ket{0}$, we have that $P_{0}=v~{}\tau_{M}$, so that
$S_{0}\sim{\mathcal{N}}(v~{}\tau_{M},\xi^{2}~{}\tau_{M})$.

If the initial state is $\ket{1}$, then the state can decay at some random
time $K$. We have that

$\displaystyle
P_{1}|K=\left\\{\begin{array}[]{ll}-v(2K-\tau_{M}),&K<\tau_{M}\\\
-v\tau_{M},&K\geq\tau_{M}\end{array}\right.$ (31)

and where $K$ has an exponential distribution with mean $\frac{1}{\tau_{A}}$.

In order to compute the distribution for $P_{1}$, we first consider the case
where $\tau_{M}\to\infty$, so that the output of the integral is a function of
the random variable $K$, i.e.,

$\displaystyle g(K)$ $\displaystyle=v(\tau_{M}-2K)$ (32) $\displaystyle
g^{-1}(P)$ $\displaystyle=\frac{\tau_{M}}{2}-\frac{P}{2v}$ (33)

so that

$\displaystyle\frac{\operatorname{d\\!}}{\operatorname{d\\!}P}g^{-1}=-\frac{1}{2v}$
(34)

and thus the distribution for $g(K)$ is

$\displaystyle
f_{g(K)}(p)=\frac{1}{2v}f_{K}\left(\frac{\tau_{M}}{2}-\frac{p}{2v}\right)$
(35)

where $f_{K}$ is the distribution for the decay time (an exponential
distribution).

Now, $g(K)$ differs from $P_{1}$ because $\tau_{M}$ is finite, so we condition
the transformation on the decay time. In particular,

$\displaystyle f_{P_{1}|K<\tau_{M}}(p)$
$\displaystyle=\frac{f_{g(K)}(p)}{F_{K}(\tau_{M})},$ (36) $\displaystyle
f_{P_{1}|K\geq\tau_{M}}(p)$ $\displaystyle=\delta(p+v\tau_{M}),$ (37)

and if we combine these we obtain

$f_{P_{1}}(p)=\Theta(p+v~{}\tau_{M})~{}\frac{1}{2v}~{}f_{K}\left(\frac{\tau_{M}}{2}-\frac{p}{2v}\right)+\\\
\delta(p+v~{}\tau_{M})~{}\left[1-F_{K}(\tau_{M})\right]$ (38)

where $\delta$ is the Dirac function, and $\Theta(\tau)$ is the Heaviside step
function.

When $\tau_{M}\ll\tau_{A}$, decay events are unlikely, and thus $S_{1}$ is
approximately ${\mathcal{N}}(-v~{}\tau_{M},\xi^{2}~{}\tau_{M})$. When
$\tau_{M}\gg\tau_{A}$, a decay is almost certain to happen during the
measurement, and $S_{1}$ is approximately the sum of a
$Q\sim{\mathcal{N}}(0,\xi^{2}~{}\tau_{M})$ and an a linear function of a
exponential random variable with mean $\frac{1}{\tau_{A}}$.

We can obtain the probability density function for $S_{1}$ by convolving
$f_{P_{1}}$ with $f_{Q}$, resulting in

${f}_{S_{1}}(s)=\frac{e^{-\frac{\tau_{M}}{\tau_{A}}-\frac{(v\tau_{M}+s)^{2}}{2\xi^{2}\tau_{M}}}}{4\xi
v\tau_{A}\sqrt{2\pi\tau_{M}}}\cdot\\\
\left\\{4v\tau_{A}+e^{\frac{\left[\xi^{2}\tau_{M}+2v\tau_{A}(v\tau_{M}+s)\right]^{2}}{8\xi^{2}v^{2}\tau_{A}^{2}\tau_{M}}}\xi\sqrt{2\pi\tau_{M}}\times\right.\\\
\left.\left[\mathrm{erf}\left(\frac{\xi^{2}\tau_{M}+2v\tau_{A}(s+v\tau_{M})}{2\xi
v\tau_{A}\sqrt{2\tau_{M}}}\right)\right.\right.-\\\
\left.\left.\mathrm{erf}\left(\frac{\xi^{2}\tau_{M}+2v\tau_{A}(s-v\tau_{M})}{2\xi
v\tau_{A}\sqrt{2\tau_{M}}}\right)\right]\right\\},$ (39)

so that we have analytical expressions for the conditional distributions of
the soft outcomes.

In the main text we use a slightly different convention for the soft outcomes,
where the conditional means are $\pm 1$ in the absence of decays. This can be
achieved by a simple change of variables, so that

$\displaystyle{f}^{(0)}(\mu)$
$\displaystyle=v~{}\tau_{M}~{}{f}_{S_{0}}\left(v~{}\tau_{M}~{}\mu\right),$
(40) $\displaystyle{f}^{(1)}(\mu)$
$\displaystyle=v~{}\tau_{M}~{}{f}_{S_{1}}\left(v~{}\tau_{M}~{}\mu\right).$
(41)

We can obtain a more convenient parameterization by defining the fluctuation
time $\tau_{F}=\frac{\xi^{2}}{v^{2}}$, which allows us to write the
conditional distributions in terms of the dimensionless ratios
$\frac{\tau_{M}}{\tau_{F}}$ and $\frac{\tau_{M}}{\tau_{A}}$, resulting in

$\displaystyle{f}^{(0)}(\mu;\tau_{M},\operatorname{\tau_{A}}1m,\tau_{F})$
$\displaystyle=\sqrt{\frac{\tau_{M}}{2\pi\tau_{F}}}e^{-\frac{(\mu-1)^{2}\tau_{M}}{2\tau_{F}}}$
(42) ${f}^{(1)}(\mu;\tau_{M},\operatorname{\tau_{A}}1m,\tau_{F})=\\\
\sqrt{\frac{\tau_{M}}{2\pi\tau_{F}}}e^{-\frac{{(\mu+1)}^{2}\tau_{M}}{2\tau_{F}}-\frac{\tau_{M}}{\tau_{A}}}-\frac{1}{4}\frac{\tau_{M}}{\tau_{A}}e^{\frac{\tau_{M}\tau_{F}}{8\tau_{A}^{2}}+\frac{1}{2}\frac{\tau_{M}}{\tau_{A}^{2}}(\mu-1)}\times\\\
\left\\{{\rm
erf}\left[\sqrt{\frac{\tau_{M}\tau_{F}}{8\tau_{A}^{2}}}+(\mu-1)\sqrt{\frac{\tau_{M}}{2\tau_{F}}}\right]\right.\\\
\left.-{\rm
erf}\left[\sqrt{\frac{\tau_{M}\tau_{F}}{8\tau_{A}^{2}}}+(\mu+1)\sqrt{\frac{\tau_{M}}{2\tau_{F}}}\right]\right\\}$
(43)

It is natural to take $\tau_{A}$, $\tau_{F}$ to be fixed, and vary $\tau_{M}$
to optimize the measurement. The justification for this is that $\tau_{A}$ is
set by qubit properties (materials, design, and fabrication), while $\tau_{F}$
is set by amplifier properties (noise temperature, compression point, etc.)
and other device properties (maximum tolerable signal power on the qubit,
coupling strength between qubit and measurement apparatus, etc.)—all of which
are fixed in an experiment.

The rough intuition is that $\operatorname{\tau_{A}}1m$ sets an upper limit to
$\tau_{M}$. As long as $\tau_{M}\ll\operatorname{\tau_{A}}1m$, increasing
$\gamma_{M}$ decreases the soft-flip error rate. As $\tau_{M}$ approaches and
surpasses $\operatorname{\tau_{A}}1m$, decay events cause the soft-flip error
rate to increase. Similarly, $\tau_{F}$ sets the lower limit on $\tau_{M}$. If
$\tau_{M}$ is comparable to $\tau_{F}$, the soft measurement distributions are
dominated by Gaussian noise. As $\frac{\tau_{M}}{\tau_{F}}$ increases above 1,
the distributions become distinguishable, as the overlap decays exponentially
with $\frac{\tau_{M}}{\tau_{F}}$ (for $\tau_{M}\ll\operatorname{\tau_{A}}1m$).
A low soft flip error rate can be achieved if
$\tau_{F}\ll\tau_{M}\ll\tau_{A}$.

###  A.2 Soft-flip probabilities

We can convert this to conditional probabilities of soft flips by integrating,
which yields

${\mathbb{P}}({\rm soft~{}flip}|0)=\frac{1}{2}\left[1+{\rm
erf}\left(\frac{\beta}{\sqrt{2}}-\sqrt{\frac{\tau_{M}}{2\tau_{F}}}\right)\right],$
(44) ${\mathbb{P}}({\rm soft~{}flip}|1)=\frac{1}{2}-\frac{1}{2}{\rm
erf}\left(\frac{\beta}{\sqrt{2}}-\sqrt{\frac{\tau_{M}}{2\tau_{F}}}\right)+\\\
\frac{1}{2}{\rm
exp}\left[\beta\sqrt{\frac{\tau_{M}\tau_{F}}{4\tau_{A}^{2}}}+\frac{\tau_{M}\tau_{F}}{8\tau_{A}^{2}}-\frac{\tau_{M}}{2\tau_{A}}\right]\times\\\
\left\\{{\rm
erf}\left[\frac{\beta}{\sqrt{2}}-\sqrt{\frac{\tau_{M}}{2\tau_{F}}}+\sqrt{\frac{\tau_{M}\tau_{F}}{8\tau_{A}^{2}}}\right]\right.\\\
\left.-{\rm
erf}\left[\frac{\beta}{\sqrt{2}}+\sqrt{\frac{\tau_{M}}{2\tau_{F}}}+\sqrt{\frac{\tau_{M}\tau_{F}}{8\tau_{A}^{2}}}\right]\right\\}$
(45)

where $\beta$ is the decision boundary for the hard decisions based on soft
outcomes. The maximum likelihood hardening map corresponds to a particular
foice for $\beta$ as a function of $\tau_{M}/\tau_{F}$ and
$\tau_{M}/\tau_{A}$. We vary $\beta$ and $\tau_{M}$ to optimize hard
measurement performance.

##  Appendix B Inclusive and exclusive circuit noise models

Here we discuss the distinction between two variations of the circuit noise
model: an inclusive model in which all faults are independent, and an
exclusive model in which some faults are mutually exclusive. In Section 2.4 we
presented an inclusive circuit model. The standard model of circuit noise
model is an exclusive model, in which each of the components of a circuit can
fail in the following specific ways:

  * •

Idle qubits waiting for CNOT gates: fail with probability $\tilde{p}_{IG}$.
When a failure occurs, an element of the set $\\{X,Y,Z\\}$ is uniformly
sampled and applied.

  * •

Idle qubits waiting for measurements: fail with probability $\tilde{p}_{IM}$.
When a failure occurs, an element of the set $\\{X,Y,Z\\}$ is uniformly
sampled and applied.

  * •

CNOT gates: fail with probability $\tilde{p}_{\text{CNOT}}$. When a failure
occurs, an element of the set of 15 non-trivial weight-two Pauli operators is
uniformly sampled and applied.

Here faults on different locations are applied independently of one another,
although faults which occur on the same operation are exclusive. The
measurement in the inclusive and exclusive models are treated identically. The
standard exclusive circuit noise model shown here and the inclusive circuit
noise model described in Section 2.4 exactly equivalent as proven in Appendix
E of [18]. The equivalence comes with a map for the probabilities between the
two models:

  * •

$\tilde{p}_{IG}=p_{IG}+O(p_{IG}^{2})$.

  * •

$\tilde{p}_{IM}=p_{IM}+O(p_{IM}^{2})$.

  * •

$\tilde{p}_{\text{CNOT}}=p_{\text{CNOT}}+O(p_{\text{CNOT}}^{2})$.

For low error rates the second order corrections (which can be calculated
using the formulas specified in Ref. [51]) are small. For example, for fault
probabilities of one percent and below, the corrections are at most
$5\text{\times}{10}^{-5}$. We therefore neglect any corrections between the
exclusive and inclusive circuit noise model throughout this work.

##  Appendix C Logical error rate per round

Here we discuss the model described in Section 5.1 that we use to extract an
estimate of the logical error rate per round from the probability
$p_{d}^{X~{}\text{fail}}(T)$ of a logical $X$ failure of the error correction
protocol with a distance-$d$ code over $T$ rounds. Our model is similar to
that in Reference [39] and is based on the assumption that during each round a
logical $X$ error occurs with probability $\bar{p}/2$ independently of other
rounds. After $T$ rounds, there is a logical $X$ failure in this model if an
odd number of rounds have experienced logical $X$ errors, which occurs with
probability

$\displaystyle\hat{p}^{X~{}\text{fail}}(T)=\frac{1-(1-\bar{p})^{T}}{2},$ (46)

which is a repeat of Eq. 22 in the main text. We use hats to distinguish the
model from the $X$ failure of the protocol itself.

While the assumptions that define this model may not apply to the protocol
itself, for a carefully selected value of $\bar{p}$ and for large $T$ the
formula $\hat{p}^{X~{}\text{fail}}(T)$ fits the data taken for the protocol
$p^{X~{}\text{fail}}_{d}(T)$ very well; see Figure 13. The good fit can be
understood from the fact that each of the decoders acts somewhat locally in
the 3D decoding graph, and the matching of errors which are well separated in
this graph occurs almost independently. In the regime of low logical error
rate, this can be expected to lead to logical errors (which are sparse in this
regime) which are also independent of one another.

Figure 13:  Convergence of $\bar{p}_{d}(T)$ calculated using Eq. 23 with $T$
using the soft phenomenological noise model. (a) The protocol’s $X$ failure
probability $p_{d}^{X~{}\text{fail}}(T)$ for a distance $d=15$ surface code
for a range of $T$. With a dashed line we show the model, namely
$\hat{p}^{X~{}\text{fail}}(T)=(1-(1-\bar{p})^{T})/2$ evaluated at
$\bar{p}=\bar{p}_{d}(300)$. (b) For each data point
$p_{d}^{X~{}\text{fail}}(T)$, we estimate $\bar{p}_{d}(T)$ according to Eq.
23. We observe a clear convergence of $\bar{p}_{d}(T)$ toward an asymptotic
value by $T=100$. We indicate $\bar{p}_{d}(300)$ by a dashed line.

The above model includes no explicit restriction on the correlation between
logical $X$ and logical $Z$ failures. Let us explore the consequences of some
additional assumptions. We can make the additional assumption that during each
round a logical $Z$ error occurs with probability $\bar{p}/2$ independently of
other rounds, such that
$\hat{p}^{Z~{}\text{fail}}(T)=\hat{p}^{X~{}\text{fail}}(T)$. If furthermore we
assume that $X$ and $Z$ failures are uncorrelated, then the overall
probability $\hat{p}^{\text{fail,unc}}(T)$ of either a logical $X$ failure, a
logical $Z$ failure or both is

$\hat{p}^{X~{}\text{fail}}(T)+\hat{p}^{Z~{}\text{fail}}(T)-\hat{p}^{X~{}\text{fail}}(T)\hat{p}^{Z~{}\text{fail}}(T).$
(47)

In this case of equal $X$ and $Z$ logical failure probabilities without
correlation, $\bar{p}$ approximately corresponds to the overall failure
probability of a single round
$\hat{p}^{\text{fail,unc}}(1)=\bar{p}-\bar{p}^{2}/4$. As we are primarily
interested in the regime of small $\bar{p}$, the $O(\bar{p}^{2})$ term can be
neglected, which justifies our reference to $\bar{p}$ as the logical failure
probability per round.

##  Appendix D Simulation Methods

Here we describe some further details of the simulation methods we used to
collect and analyze the data presented in the main text.

All of our data involves Monte Carlo sampling to estimate the probability $q$
of success of the error correction protocol described in Section 5.1 given
some noise model, code distance, and decoder. Given $n$ trials of which $k$
succeed, we use Bayesian inference to estimate the parameter of the
corresponding Bernoulli distribution $\mathrm{Bernoulli}(q)$ [52]. We take the
Jeffreys prior, so that the posterior distribution of $q$ given the data is
$\mathrm{Beta}(\frac{1}{2}+k,\frac{1}{2}+n-k)$. We report the mean of the
posterior distribution $\frac{k+1/2}{n+1/2}$ and 68% equal-tailed credible
intervals calculated directly from the inverse cumulative distribution
function of the Beta distribution. In many data points the intervals
indicating statistical uncertainty (indicated by vertical lines with end caps)
are smaller than the symbols which mark the data point.

For a noise model parameterized by a single parameter $p$, we often seek to
identify a threshold value $p^{*}$ of $p$ such as in Figure 9 and Figure 11.
We obtain a set of data points $p^{\text{fail}}_{d}(d)$ for a range of
distances and values of $p$ in the vicinity of the suspected value of $p^{*}$.
Following the usual universal scaling ansatz for critical points in the study
of phase transitions, we fit a quadratic in the scaled variable
$x=(p-p^{*})d^{1/\nu}$ to our data in this regime.

To minimize sensitivity to asymmetric measurement errors in models such as the
amplitude damping model of Section 1.4, at each measurement round, each
ancilla qubit is initialized in a known measurement eigenstate selected
uniformly at random.