Chapter 11
Quantum error correction

Classical error correction is ubiquitous in modern computing. The basic idea is to pad out a message we want to send with some extra redundant data, which give us enough info to recover the original message as long as no (catastrophically bad) errors occurred. In the 1990s, people started to notice that many of the same concepts could be applied to quantum data. Namely, by encoding some qubits into a higher-dimensional system and making careful choices of measurements, we can often detect whether errors occurred and even correct them (again if they are not too bad). One of the key ideas behind quantum error correction is identifying analogous notions between classical, linear, error correction and stabiliser theory. We have already seen in previous chapters that there are several deep connections between stabiliser (i.e. Clifford) states and ${𝔽}_2$-linear structures, and it just so happens that ${𝔽}_2$-linear structures are the bread and butter of classical error correction. In this chapter, we will start to cash out these connections and show how quantum error correction can be done in a way that is, in many ways, similar to its classical counterpart. For example, if I want to send you three bits, $(x,y,z)$ and actually I send you six bits $(x,y,z,x\oplus y,y\oplus z,x\oplus z)$, then I can always recover the original message even if one of these six bits gets flipped. In this simple example, we encode our message (an element of ${𝔽}_2^3$) into a 3D subspace $S=\{(x,y,z,x\oplus y,y\oplus z,x\oplus z)|x,y,z,\in {𝔽}_2\}$ of ${𝔽}_2^6$ called the codespace. If a single error occurs in such an encoded bit string, it leaves the codespace, so we can detect it just by checking if the last three bits are indeed the correct parities of the first three. Furthermore, there is at most 1 element in the codespace that is within 1 bit flip of any string of six bits, so we can actually correct a single error. Hence, a major aspect of designing good error correcting codes is finding particular subspaces of ${𝔽}_2^n$ that have nice properties like this, as we’ll discuss in Section 11.1. Quantum error correcting codes can be defined as subspaces of $(ℂ2)\otimes n$ , the space of $n$ qubits, which have analogous nice properties. Unlike the classical case, these are going to be huge $ℂ$-linear subspaces, namely $2^k$-dimensional subspaces of the $2^n$-dimensional space $(ℂ2)\otimes n$ . As a result, it is not practical to work with these spaces explicitly (e.g by enumerating a spanning set of vectors). However, as we have already seen in Chapter 6, stabiliser theory gives us a powerful tool for efficiently representing complicated subspaces of ${({ℂ}^2)}^{\otimes n}$. Thanks to the Fundamental Theorem of Stabiliser Theory, we can fix a $2^k$-dimensional stabiliser subspace of $(ℂ2)\otimes n$ by giving $n-k$ independent generators of the stabiliser group.

11.1 Classical codes and parameters

Let’s look again at the codespace

We claimed before that $S$ can correct a single error. That is, if I start with a vector in $S$ and flip 1 bit, this vector will no longer be in $S$, and furthermore, there is a unique vector in $S$ that is one bit-flip way. For example, if I receive the string: $(1,1,0,0,0,0)$, I can tell there is an error somewhere, since $x=y=1$ and $z=0$, but $x\oplus z=y\oplus z=0$. It could be that either my first 3 data bits are wrong, or it could be that the parity bits are wrong. However, there is only one way to satisfy all the parities by flipping a single bit, namely setting $z:=1$. Similarly, if I look at a string $(0,0,1,0,1,0)$, the only possibility for a single-bit error is that the final parity bit $x\oplus z=0$ is wrong. Since $S$ is a linear subspace, it turns out we can succinctly capture the property of being able to detect any of some family of errors (e.g. single bit-flips) and to correct those errors in a single concept called code distance.

Suppose we could flip a single bit of a vector $\overrightarrow{v}\in S$ and obtain another vector $\overrightarrow{w}\in S$. Then, their sum $\overrightarrow{v}\oplus \overrightarrow{w}$ is also in $S$, and it would just be a unit vector consisting of a single 1 in the location of the flipped bit, e.g.

The same applies if we flip $d$ bits: the sum will have 1’s in precisely the locations of the flipped bits. So, saying that flipping $d$ bits leaves $S$ is the same thing as saying there is no vector in $S$ with Hamming weight $d$. In other words, a space $S$ with code distance $d$ can detect any amount of errors strictly less than $d$. It is also the case that being able to correct a given number of errors can be stated in terms of the code distance. We noted before that the code $S$ in (11.1) has the property that, if we take any vector $\overrightarrow{v}\in S$ and flip a single bit, there is no other vector $\overrightarrow{w}\in S$ that is a single bit-flip away. In other words, there are no two vectors $\overrightarrow{v},\overrightarrow{w}\in S$ that are two bit-flips apart, or equivalently, $S$ has a code distance of (at least) 3. In fact, the code distance is exactly 3, which we can see by enumerating all 8 vectors in this 3D subspace:

and noting that all the non-zero vectors have Hamming weight 3 or more. This is a general feature: any code with distance $d=2e+1$ can always correct an error consisting of at most $e$ bit flips. To move toward the quantum analogue of classical linear codes, we can proceed by thinking of stabiliser measurements as analogous to classical parity checks. As we already mentioned, for classical codes, we can very quickly check whether $\overrightarrow{v}\in S$ by taking XORs of certain bits. For the code $S$ in (11.1), then $(v_1,v_2,v_3,v_4,v_5,v_6)$ is in $S$ precisely when the following linear equations are satisfied:

As we saw in Chapter 4, given a system of homogeneous ${𝔽}_2$-linear equations fixing a linear subspace $S$ essentially the same as giving a spanning set for $S^{\perp }$. In this case, this is:

To check $\overrightarrow{v}\in S$, it suffices to check ${\overrightarrow{w}}_i^T\overrightarrow{v}=0$ for each of the basis vectors ${\overrightarrow{w}}_i$ of $S^{\perp }$. If this holds, then we can be sure no error of weight $<d$ has occurred. If ${\overrightarrow{w}}_i^T\overrightarrow{v}=1$, this is called a syndrome, because it indicates that there is an error somewhere in $\overrightarrow{v}$.

11.2 Quantum stabiliser codes

In this section, we’ll expand on the analogy between parity checks and stabiliser measurements, and show how to define the notion of code distance for a stabiliser subspace. Fix a stabiliser group $S=⟨{\overrightarrow{P}}_1,\dots ,{\overrightarrow{P}}_m⟩$ with associated stabiliser subspace $S\subseteq (ℂ2)\otimes n$. Since we can use stabiliser subspaces to correct errors, we will from henceforth use the terms stabiliser subspace and stabiliser code interchangeably. This is analogous to the classical case, where we referred to subspaces of ${𝔽}_2^n$ as codes. Thanks to the Fundamental Theorem of Stabiliser Theory from Chapter 6, we know that $S$ is $2^k$-dimensional, for $k:=n-m$. Hence, we can think of the stabiliser subspace as encoding $k$ logical qubits in $n$ physical qubits. This gives us quantum analogues to the parameters $n$ and $k$ from classical codes. To build up to the notion of code distance, let’s have a look at how we can use $S$ to detect and correct errors. We can treat the generators of $S$ as “quantum parity checks” in a very specific way. If we measure an arbitrary state $|\psi ⟩\in (ℂ2)\otimes n$ with one of stabiliser generators, we can compute the Born rule probability as:

If we restrict to the case where $|\psi ⟩\in S$, then ${\overrightarrow{P}}_j|\psi ⟩=|\psi ⟩$, then by Proposition 6.2.2 we know $\mathrm{\Pi }(0){\overrightarrow{P}}_j|\psi ⟩=|\psi ⟩$. Hence:

So, we will always get outcome $s_j=0$ if no error occurred on $|\psi ⟩$. From this, we can also conclude that we’ll never get outcome $s_j=1$:

Now, suppose an error does occur on $|\psi ⟩$. For simplicity, we’ll initially assume that this error takes the form of a self-adjoint Pauli string $\overrightarrow{Q}$. In Section 11.2.2, we’ll show that arbitrary errors can be reduced to this case. Namely, if we can detect/correct Pauli errors, then we can detect/correct arbitrary errors. There are two possibilities, either the error commutes with $\overrightarrow{P}$ or it anti-commutes with $\overrightarrow{P}$. These two possibilities translate into the following commutation rule with respect to the Pauli box $\overrightarrow{P}$.

As a consequence of Exercise 11.1, if a commuting error $\overrightarrow{Q}$ happens to $|\psi ⟩$, the outcome of measuring ${\overrightarrow{P}}_j$ is unaffected:

So, $\mathrm{\text{Prob}}(s_j|\overrightarrow{Q}|\psi ⟩)=\mathrm{\text{Prob}}(s_j|\overrightarrow{Q}|\psi ⟩)$. Hence, we’ll again get outcome $s_j=0$ with certainty. However, if $\overrightarrow{Q}$ anti-commutes with ${\overrightarrow{P}}_j$, it kicks a $\pi$ up into the measurement outcome, so the probabilities flip:

Hence, we’ll get outcome $s_j=1$ with certainty. We can measure all $m$ stabilisers generating $S$. Since all of the stabilisers commute, we can either think of doing each of these measurements in sequence (where the order doesn’t matter), or equivalently, doing one big measurement whose outcome is given by:

If $|\psi ⟩$ is of the form $\overrightarrow{Q}|\varphi ⟩$ for some state $|\varphi ⟩$ in the stabiliser subspace and some (possibly trivial) Pauli error $\overrightarrow{Q}$, this will yield some particular bitstring of outcomes with certainty. If $\overrightarrow{Q}=I$, the outcome will always be $(s_1,\dots ,s_m)=(0,\dots ,0)$. Hence, each time $s_j=1$, this indicates that (1) some non-trivial error $\overrightarrow{Q}$ has occurred, and (2) that error anti-commutes with the $j$-th stabiliser ${\overrightarrow{P}}_j$. By analogy to the classical case, this vector of measurement outcomes is called the syndrome. If we are lucky, this syndrome will provide us with enough information to send $|\psi ⟩$ back to the error free state $|\varphi ⟩$. For example, if it uniquely fixes the Pauli string $\overrightarrow{Q}$, that is definitely good enough, because we can then just apply $\overrightarrow{Q}$ again to get $\overrightarrow{Q}|\psi ⟩={\overrightarrow{Q}}^2|\varphi ⟩=|\varphi ⟩$. However, we don’t even need to hit $\overrightarrow{Q}$ on-the-nose, because if we correct $|\psi ⟩$ with some ${\overrightarrow{Q}}^{\prime }$ that is the product of $\overrightarrow{Q}$ and some stabiliser $\overrightarrow{S}\in S$, we get:

So, we again recover the state $|\varphi ⟩$, possibly up to an irrelevant global phase. Lets see how this works by means of a simple example. Consider the following stabiliser group on three qubits:

$S$ has two independent stabilisers, so $\dim <!--\; FUNCTION\; APPLICATION\; -->(\text{Stab}(S))=2^{3-2}=2$. Hence, this code, called the GHZ code encodes one qubit into three. Fixing a basis for $\text{Stab}(S)$, we have

For the following discussion, it will be conventient to write $\text{Stab}(S)$ as the image of a map from one qubit into three qubits, called the encoder of $S$. We will say more about encoders in the following sections, including how to build them from stabiliser codes. But for now, note that:

It thus follows that:

Hence, we can write a generic state $|\mathrm{\Psi }⟩\in \text{Stab}(S)$ as:

As before, we can look at the Born rule probabilities associated with measuring the stabiliser generators ${\overrightarrow{Z}}_1$ and ${\overrightarrow{Z}}_2$. As was shown in Exercise 6.7, all-$Z$ and all-$X$ Pauli projectors take a particularly simple form:

This generalises to Pauli strings formed just from $Z$ and $I$ (or just $X$ and $I$) by connecting the projector to just the subset of qubits were a $Z$ (or $X$) appears. For example, we have:

Applying $\mathrm{\Pi }(k)\mathit{ZZI}$ to an encoded state:

we see that, as expected:

By symmetry, we see the same probabilities for measuring $I\otimes Z\otimes Z$. This is consistent with what we saw before: measuring states in $\text{Stab}(S)$ with the generators of $S$ will leave the states unchanged, and yield outcome 0 with probability 1. However, suppose we introduce an error to our encoded state, such as a ‘bit flip’, i.e. a Pauli $X$ applied to the first qubit. Since $X\otimes I\otimes I$ anti-commutes we $Z\otimes Z\otimes I$, we get:

Hence the Born rule probabilities are flipped:

so we obtain $s_1=1$ for out first syndrome bit. On the other hand, if we measure $I\otimes Z\otimes Z$ instead, this commutes with $X\otimes I\otimes I$, so:

so we obtain outcome $s_2=0$ for the second syndrome bit. By symmetry, it is easy to check that each of the single bit-flip errors can be associated with a unique syndrome:

Hence, if any single bit-flip error occurs, we always know how to fix it. We just need to measure the stabiliser generators and apply a Pauli $X$ on the correct qubit to cancel out the error. Unfortunately, the GHZ code is not good enough to correct arbitrary single qubit errors. Notably, if a Pauli Z error occurs on one of the qubits (which is sometimes called a ‘phase-flip’ error), it commutes with all of the generators of $S$. Hence, the syndrome will always be $(0,0)$, and we’ll have no idea that the error even happened. In this sense, the GHZ code is not very good at detecting or correcting errors. By analogy to the classical case, this a distance-one code, meaning that there are even single-qubit errors that can go undetected. In order to understand what this means (and ultimately to find codes which can detect and correct errors), we will now formalise the notion of code distance for quantum stabiliser codes.

11.2.1 Code distance for stabiliser codes

We saw in Section 11.1 that we could quantify the number of detectable errors using the classical code distance. We can do a similar thing for stabiliser codes, where the following notion plays the role of the Hamming weight.

For example, the Pauli string $X\otimes Z\otimes I$ has weight 2 and the identity string always has weight 0.

Using this notion, we can quantify the number of detectable errors. Note that an error produces a non-zero syndrome if and only if it anti-commutes with at least one of the generators of the stabiliser group. So, to be undetectable, it must commute with everything in $S$. Furthermore, we only care about errors that actually mess up the states in our stabiliser subspace, so we shouldn’t count elements of the stabiliser group itself as errors.

Note that, since $S$ is a subgroup, $I\in S$, so $\overrightarrow{P}$ must have non-zero weight. Also, note that $\overrightarrow{P}$ commutes with everything in $S$ if and only if it commutes with each of the generators, so we can efficiently decide whether $\overrightarrow{P}$ commutes with everything in $S$. However, like in the classical case, we cannot in general compute the code distance efficiently, since we need to show that all Pauli strings with $|\overrightarrow{P}|<d$ are either in $S$ or anti-commute with something in $S$. If a stabiliser code has distance $d$, it can detect any error with $|\overrightarrow{Q}|<d$. In other words, it can detect up to $d-1$ single-qubit errors. Similarly to the classical case, it can also correct up to $\lfloor (d-1)∕2\rfloor$ errors. More precisely, errors $\overrightarrow{Q}$ with $|\overrightarrow{Q}|\le \lfloor (d-1)∕2\rfloor$ are uniquely fixed, up to stabilisers.

So, as in the classical case, a quantum code can correct $e$ errors if $2e+1\le d$. Putting the three parameters together, we will write $[[n,k,d]]$ to indicate a quantum error correcting code that encodes $k$ logical qubits in $n$ physical qubits, with code distance $d$.

If we don’t care about error correction and just want to be able to detect an arbitrary weight-1 error, the following code will work.

In the last two examples, the codes were split into all-X and all-Z generators, which as we’ll see in Section 11.3 has some nice consequences which make them easier to work with. However, if we drop this restriction, we can find even smaller distance 3 codes.

In the next section, we will see how the code distance enables us to detect and correct not just Pauli errors, but a large class of errors.

11.2.2 Detecting and correcting quantum errors

A natural question arises when one first encounters quantum error correcting codes: why the fixation on Pauli errors? In the classical case, it is quite natural to focus on bit-flips (and sometimes bit-loss) as the only basic kinds of errors we care about. Intuitively, these are the only kinds of errors that can occur for classical data. However, there are many ways for a qubit to experience an error, so why is it we can get away with just Pauli X, Y, and Z? Indeed, quantum theory says that the physical processes that cause quantum errors could act in infinitely many ways on our qubits, and even interact our qubits with some external systems outside our control, introducing unwanted entanglement. To capture all such possibilities, a generic error can be modelled as a unitary like this:

where the first $n$ qubits represent the system we are actually doing the computation on, and the extra system $H$ represents some environment that those qubits might interact with when the error occurs. The key trick at this point is to realise that the Pauli matrices $I,X,Y,Z$ span the whole 4D space of $2\times 2$ matrices.

Consequently, Pauli strings of length $n$ span the whole space of $2^n\times 2^n$ matrices. Using this fact, we can decompose $E$ as follows:

where $D_{\overrightarrow{P}}:H\to H$ is some linear map on the rest of the space that can vary with $\overrightarrow{P}$. We don’t expect to be able to correct all errors of this form. For example, if $E$ simply swapped all our qubits out into $H$ and replaced them with garbage from the environment, there is no way to recover. So, we should put some kind of reasonable restriction on $E$. First, let’s split $E$ into two parts based on the weight of the Pauli strings:

For reasonably well-behaved error processes, the second part of the sum will get exponentially small as we increase $d$. So, in true physicist style, we will just ignore it! This gives us the following pretty good approximation for $E$:

This is a non-trivial assumption, which comes from the fact that we assume the interference from the environment is relatively localised (cf. Remark 11.2.7). An important consequence is that as $d$ gets larger, the form (11.4) gives us a better approximation of an arbitrary error process.

Let’s use this form of an error to talk about a single round of error detection or correction. We’ll start by assuming that we can perform stabiliser measurements perfectly (i.e. without introducing more errors). This is of course not the case, as we’ll see when we discuss fault-tolerant measurements in Section 11.4.2. Fix a stabiliser code of distance $d$ given by the stabiliser group $S=⟨{\overrightarrow{P}}_1,\dots ,{\overrightarrow{P}}_m⟩$. Suppose we start with a state $|\psi ⟩\in \mathrm{\text{Stab}}(S)$ at $t_0$, then measure the generators of $S$ at $t_1$. If we assume an arbitrary error of the form of (11.4) could happen between $t_0$ and $t_1$, the resulting state, which depends on the measurement outcomes $s_1,\dots ,s_m$ looks like this, up to normalisation:

If we did not detect an error, this means we get outcome $(s_1,\dots ,s_m)=(0,\dots ,0)$. In that case, the resulting state is the following:

From (11.4), we can expand $E$ as a sum over Pauli strings $\overrightarrow{P}$ with $|\overrightarrow{P}|<d$:

Then, since $S$ has distance $d$, all $\overrightarrow{P}$ are either elements of $S$ or anti-commute with at least one ${\overrightarrow{P}}_j\in S$. However, terms in (11.4) corresponding to anti-commuting Pauli strings vanish. To see this, note that stabiliser generators all commute, so we can always move the projector corresponding to ${\overrightarrow{P}}_j$ to the front of the list of projectors in (11.4). Then:

where $\text{(∗)}$ is using the fact that $\mathrm{\Pi }(0){\overrightarrow{P}}_j|\psi ⟩=|\psi ⟩$ since $|\psi ⟩\in \mathrm{\text{Stab}}(S)$. The only remaining terms are those where $\overrightarrow{P}\in S$. But then, $\overrightarrow{P}|\psi ⟩=|\psi ⟩$. Combining this with the fact that $|\psi ⟩$ is also invariant under the projection on to $\mathrm{\text{Stab}}(S)$, (11.6) reduces to:

where $D:={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{\overrightarrow{P}\in S,|\overrightarrow{P}|<d}{D}_{\overrightarrow{P}}$ is some (irrelevant) process acting independently on the environment, without disturbing $|\psi ⟩$. Hence, even though $E$ might not be a Pauli string, if we perform a round of stabiliser measurements and detect no errors, we will nevertheless project back on to the error-free state $|\psi ⟩$. But what happens if we do detect errors? Then, we can attempt to decode the error syndrome by finding some Pauli string $\overrightarrow{Q}\notin S$ that could have produced that error and undo it. In fact, for reasons that will soon become clear, we often want to find such a $\overrightarrow{Q}$ with weight as small as possible.

Clearly if $(s_1,\dots ,s_m)=(0,\dots ,0)$, the minimum weight decoding is $\overrightarrow{1}$. Otherwise, $\overrightarrow{Q}$ will always be a non-trivial Pauli string. If we post-compose the result of a round of stabiliser measurements (11.5) with $\overrightarrow{Q}$, we can push $\overrightarrow{Q}$ inside, which cancels out the $s_j$:

Hence, we obtain the form of (11.6) for a new error process $E^{\prime }$. If $E$ is a sum over Paulis with weight $\le \lfloor (d-1)∕2\rfloor$, and $|\overrightarrow{Q}|\le \lfloor (d-1)∕2\rfloor$, then $E^{\prime }$ is a sum over Paulis with weight at most $d-1$. Hence, if $S$ has distance $d$, we can use the same argument as before to reduce the expression above to $|\psi ⟩\otimes D$, so we have successfully corrected the error $E$. Note that the weight of the terms in $E^{\prime }$ depends on the weight of $\overrightarrow{Q}$. This is why we try to find $\overrightarrow{Q}$ with weight as small as possible, to give the greatest chance to correcting the error. Naïvely, we can find $\overrightarrow{Q}$ by enumerating all of the Pauli strings of weight $1,2,3,\dots$ until we find one with the correct syndrome. Clearly this will take exponential time, so it becomes infeasible for large codes. Minimum weight decoding for stabiliser codes is (at least) as hard as for classical codes, which is already known to be NP-hard for some families of error correcting codes. Hence, for a stabiliser code to be useful, it needs to not only have good parameters $[[n,k,d]]$, but also an efficient way to find minimum weight (or at least low weight) decodings.

11.2.3 Encoders and logical operators

An $[[n,k,d]]$ stabiliser code is defined by a stabiliser group $S$ with $m=n-k$ generators and fixes a $2^k$-dimensional subspace $\mathrm{\text{Stab}}(S)\subseteq (ℂ2)\otimes n$. Hence, we can think of this as $k$ logical qubits embedded in a space of $n$ physical qubits. $\mathrm{\text{Stab}}(S)$ tells us where those qubits lie within the big space, but it does not tell how exactly how those qubits are embedded. For example, if we are encoding 2 qubits, which part of $\mathrm{\text{Stab}}(S)$ corresponds to the first qubit and which to the second qubit? How do unitaries applied to the physical qubits map on to transformations of the logical qubits? If we only intend to use quantum error correction for quantum memory, the answers to these questions are not too important. However, as we will see in Section 11.4, they are of central importance when we start wanting to perform fault-tolerant computations on encoded qubits. For that reason, it is useful to define an explicit isometry $E:(ℂ2)\otimes k\to (ℂ2)\otimes n$ such that the image of $E$ is $\mathrm{\text{Stab}}(S)$. This isometry is called an encoder associated with code $S$:

We already saw some explicit examples of encoder maps, built as ZX diagrams in Equations (11.2) and (11.3). On some occasions, we may actually want to implement the encoder physically, e.g. as a unitary circuit with ancillae. However, this need not be the case, and in fact most of the time, it suffices to treat this as a purely mathematical object, tracking how our $k$ logical qubits are embedded into the space of $n$ physical qubits. Most importantly, it tracks the relationship between logical maps performed on our $k$ logical qubits and the associated physical maps performed on the $n$ physical qubits.

Intuitively, $F$ acts like $f$ on the codespace of $S$, which is isomorphic to the space of $k$ qubits. To formalise exactly what “acts like $f$” means, we need to choose an isomorphism between this subspace and $(ℂ2)\otimes k$, which is exactly what $E$ does for us. This is a very important concept, since in order for quantum error correction to work, our quantum data needs to be continuously protected from errors. Hence, we cannot decode and re-encode qubits every time we want to apply a gate. As we will see in Section 11.4, finding an $F$ satisfying equation (11.8) will help us to implement fault tolerant operations on encoded qubits. Given a generating set of stabilisers for $S$, we can always derive an encoder by following the procedure we used to prove the FTST in Section 6.2.1. Namely, we can on to $\text{Stab}(S)$ by finding an isometry $E$ such that $\mathrm{\Pi }=E^{†}E$:

Furthermore, an encoder derived this way will always be a Clifford isometry, so it is easy to reason about the propagation of Pauli errors. Note that the stabiliser group $S$ only fixes the image of $E$ (or equivalently, the projector $\mathrm{\Pi }$). There are many different ways to split a projector, so following the procedure from the proof of the FTST gives us just one possible choice. In particular, for any unitary $U:(ℂ2)\otimes k\to (ℂ2)\otimes k$, the encoders $E$ and $E^{\prime }:=\mathit{EU}$ have the same image in $(ℂ2)\otimes n$, hence they correspond to the same stabiliser code $S$. However, whenever $E$ is Clifford, we can perform a nice trick to describe $E$ fully in terms of Pauli strings: we bend the wires! If we bend the input wires around using cups, we obtain an $n+k$ qubit state $|E⟩$:

Now, we know from the Fundamental Theorem of Stabiliser Theory that $n+k$ independent stabilisers will uniquely fix $|E⟩$, and hence will uniquely fix $E$. We already have $n-k$ stabilisers given by the generators of $S=⟨{\overrightarrow{P}}_1,\dots ,{\overrightarrow{P}}_{n-k}⟩$:

So, the question is: where can we find $2k$ more stabilisers? The first thing to note is, assuming $E$ is a Clifford isometry, we can always push arbitrary Pauli strings from its inputs to its outputs, thanks to Proposition 6.1.6. In particular, we can always push single-qubit Pauli $X$ and $Z$ gates through $E$. As a consequence, we can always find a Pauli string ${\overrightarrow{X}}_i$ that implements (in the sense of Definition 11.2.9) a Pauli $X$ gate applied in the $i$-th logical qubit, i.e.

Similarly, for a $Z$ gate on the $i$-th qubit, there exists a different Pauli string ${\overrightarrow{Z}}_i$ such that:

This gives us $2k$ Pauli strings $\{{\overrightarrow{X}}_1,\dots ,{\overrightarrow{X}}_k,{\overrightarrow{Z}}_1,\dots ,{\overrightarrow{Z}}_k\}$ called the logical operators associated with $E$.

By moving the $X$ gate to the right-hand side of (11.11) and bending the wires, we see that each logical operator ${\overrightarrow{X}}_i$ gives us a stabiliser for the Choi state $|E⟩$:

Similarly, each ${\overrightarrow{Z}}_i$ gives us a stabiliser for $|E⟩$:

Note that the operators of the form (11.13) and (11.14) all pairwise commute. This is because the $-1$ coming from anti-commuting an $X$ and $Z$ on the $i$-th qubit is always cancelled out by anti-commuting ${\overrightarrow{X}}_i$ with ${\overrightarrow{Z}}_i$ on the last $n$ qubits (cf. Exercise 11.5). If we combine the stabilisers coming from $S$ in equation (11.10) with those coming from the logical operators, we obtain $n-k+2k=n+k$ stabilisers for $|E⟩$, which is by construction an $n+k$ qubit state. Hence, $E$ is totally fixed up to a scalar factor. Hence, if we perform the method from Section 6.2.1 for the full set of $n+k$ stabilisers for $|E⟩$, then bend the wires, we’ll get the encoder associated with a stabiliser group and a set of logical operators. In general, this will be a relatively deep ZX-diagram, with approximately one layer for each stabiliser and logical operator. We could then try and simplify things to get a more compact form, e.g. by reducing to GSLC or AP form, but in general this picture of the encoder might be a bit awkward to work with. However, as we’ll see in Section 11.3, for a certain family of codes, called CSS codes, things get a lot simpler!

11.2.4 The decoder

The encoder has a dual operation, which we call the ideal decoder, or simply the decoder. This is slightly more difficult to work with than the encoder, so whenever possible we will state things in terms of the encoder rather than the decoder. However, having a way to at least in principle decode $n$ physical qubits back into $k$ logical qubits while detecting/correcting errors is still a useful thing to have in our back pocket. The encoder is an isometry, so we know how to implement it straight away as a unitary circuit with ancillae. In fact, this definition of $E$ is already clear from the definition of the encoder in equation (11.9) in terms of the splitting of the projectors onto the stabiliser subspace. However, we can’t deterministically implement $E^{†}$ because it would require performing the unitary $U^{†}$ then post-selecting each of the ancilla qubits on to $⟨0|$. However, we can measure those ancillae instead:

But what are these measurement outcomes $(s_1,\dots ,s_m)$? Recall the following equation from Exercise* 6.10:

This implies that for an encoded state $|\mathrm{\Psi }⟩$, performing $U^{†}$ and measuring the ancillae will give us the same outcome $\overrightarrow{s}$ as measuring all of the stabilisers. Hence, we can use the measurement outcomes from the ancillae to do error detection or correction. If we get outcome $\overrightarrow{s}=(0,\dots ,0)$, we can conclude that no logical error has occurred with weight $<d$. If we get any other syndrome, we can do least-distance decoding to find the smallest weight physical error $\overrightarrow{Q}$ with error syndrome $\overrightarrow{s}$, and then figure out the appropriate correction to do on the $k$ logical qubits we have left. Since $U^{†}$ is Clifford, we can do this efficiently.

Given this, we therefore define the decoder as a non-deterministic process consisting of a measurement yielding syndrome $\overrightarrow{s}$ followed by the associated Pauli correction ${\overrightarrow{P}}_{\overrightarrow{s}}$ defined as in Exercise 11.7:

When $\overrightarrow{s}=\overrightarrow{0}$, ${\overrightarrow{P}}_{\overrightarrow{s}}=I$, so ${\overrightarrow{D}}_{\overrightarrow{0}}=E^{†}$. Hence this process acts like $E^{†}$ in the error-free case, but it additionally also “swallows” any correctable errors when $\overrightarrow{s}\ne \overrightarrow{0}$.

11.3 CSS codes

In this section, we’ll define a family of stabiliser codes called Calderbank-Shor-Steane codes, or CSS codes for short. As you may have already noticed from Examples 11.2.4 and 11.2.5, some stabiliser codes have generators that split nicely into an all-X part and an all-Z part. In a sense, such codes behave like two classical error correcting codes mushed together, where the parity checks of one code become the Z stabilisers (which detect bit errors) and those of the other code become the X stabilisers (which detect phase errors). That is pretty much all there is to defining a CSS code, once you additionally account for the fact that all of the stabilisers need to commute. It turns out there is a very natural way to impose this in terms of bitstrings.

Hence, if we fix two classical codespaces, one for the X-stabilisers and one for the Z-stabilisers, all the stabilisers will commute precisely when those subspaces are mutually orthogonal. We say two subspaces $S,T$ are orthogonal if ${\overrightarrow{v}}^T\overrightarrow{w}=0$ for all $v\in S,w\in T$, or equivalently $T\subseteq S^{\perp }$.

That is, we let the basis vectors of $S$ define the X generators and we let the basis vectors of $T$ define the Z generators. Since addition in ${𝔽}_2$ is taken modulo 2, orthogonality guarantees that each X generator overlaps with a Z generator in an even number of places, which makes the group commutative. Using this fact, it is easy to verify the resulting group is a stabiliser group.

11.3.1 Stabilisers and Pauli ZX diagrams

Recall from Section 4.3 that phase-free ZX-diagrams can always be put into Z-X or X-Z normal form, which correspond respectively to representations of an ${𝔽}_2$-linear subspace $S$ using a basis for $S$ or a basis for $S^{\perp }$:

If we combine this knowledge with these equations, which follow from $(\pi )$:

we can see immediately how to derive a generating set of stabilisers for a phase-free ZX-diagram. As we’ll see in this section, those stabilisers always generate a CSS code, and conversely any CSS code can be presented using a phase-free ZX-diagram.

11.3.2 Maximal CSS codes as ZX diagrams

Eq. (11.16), plus the two normal forms from Section 4.3.1, will give us everything we need to prove our main theorem.

This proof gives us an evident way of translating the stabiliser generators of a maximal CSS code into a ZX diagram. In fact, it gives us two equivalent ways, using the Z-X normal form, which gives us a generating set of X stabilisers, or the X-Z normal form, which gives us the Z stabilisers. Interestingly, we only ever need to represent one kind of stabilisers for a maximal CSS code diagrammatically, because $S^{\perp }$ is uniquely fixed by $S$ and vice-versa.

11.3.3 Non-maximal CSS codes as ZX encoder maps

For a non-maximal CSS code, we should end up with an encoder map from $k$ logical qubits to $n$ physical qubits. Since we already know how to turn CSS stabilisers into phase-free diagrams, we can use the wire-bending trick from Section 11.2.3 to treat logical operators as stabilisers on a bigger $n+k$ qubit state and therefore add them to the diagram as well. As an example, lets return to the 7-qubit Steane code from Example 11.3.2. We will switch to a more compact notation for writing its stabilisers, where $X_i$ (resp. $Z_i$) corresponds to an $n$-qubit operator acting non-trivially on the $i$-th qubit with a Pauli $X$ (resp. $Z$):

This CSS code is non-maximal, and encodes $7-6=1$ logical qubits. Hence we should fix 2 additional logical operators $\overrightarrow{X}:=X_4{X}_5{X}_6$, $\overrightarrow{Z}:=Z_4{Z}_5{Z}_6$. As we noted before, we only need one kind of stabiliser to build the ZX diagram, so applying the recipe from the previous section to the $X$ stabilisers and logical operator, we obtain the following picture, where we label the logical qubit 0 and the physical qubits 1-7. We can then put the logical qubit on the left and rearrange some of the physical qubits to obtain the following:

Note that, if we follow this recipe, we will always get identity spiders on the inputs, which are redundant. If we simplify them away, we’ll always end up with something in generalised parity form (for the X form of the encoder) or the colour-reverse of generalised parity form (for the Z form of the encoder).

As a result, we can always write a CSS encoder map in generalised parity form using just its X-stabilisers and X-logical operators as follows:

1..

Place an output X-spider on all $n$ outputs.

2..

For each of the $k$ X-logical operator, add an input Z-spider connected to the output X-spiders of its support.

3..

For each X-stabiliser generator, add an internal Z-spider connected to the output X-spiders of its support.

Equation (11.17) gives the X-form of the Steane code encoder. If we used the Z-stabilisers and logicals instead, we’ll obtain the Z-form. In the case of the Steane code, this is the exact same picture, but with the colours reversed:

This will not always be the case, and it comes from the fact that the Steane code is self-dual. We’ll discuss self-dual codes more in Section 11.4.1.1.

So, we have seen how to turn any CSS code described by stabilisers and logical operators into a phase-free ZX-diagram of its encoder. Conversely, we can treat any isometry described by a phase-free ZX diagram as a CSS code just by computing its generalised parity form. Recall from Chapter 4 that the generalised parity form looks like this:

Furthermore if $E$ is an isometry, we can conclude from Proposition 4.2.8 that $j=0$, giving us:

From this picture, we can immediately read off the $m$ X-stabilisers and $k$ X-logical operators associated with $E$. If do everything colour-reversed, we’ll get a different normal form for the encoder:

from which we can read off the Z-stabilisers and Z-logical operators. In summary, we have given an efficient procedure for writing a phase-free isometry from a CSS code with logical operators and for turning any phase-free isometry into its associated CSS code and logical operators.

11.3.4 The surface code

One particular family of CSS codes has been so well-studied in recent years that it deserves some special attention. The surface code is a family of CSS codes that encode a single logical qubit in a square (or rectangular) lattice of physical qubits. Larger lattices define codes with a higher code distance. While they aren’t the most memory-efficient codes we know about, surface codes have a number of nice properties coming from this regular geometric structure. For one thing, they can be implemented using only nearest-neighbour gates on a 2D architecture, so there is never any need to perform swap gates or otherwise break planarity. A second nice feature is that even for surface codes with very high code distances, we have efficient algorithms for decoding error syndromes, as we’ll see in Section 11.3.4.1 below. Finally, they serve as a useful baseline for fault-tolerant computation, as we know (at least in principle) how to implement all the ingredients needed to implement universal quantum computation on surface-code-encoded qubits in a fault-tolerant manner. In fact, fault-tolerant computation in the surface code has one of the best thresholds we know about. That is, they can tolerate quite a bit of noise at the hardware level while still being able to supress errors. More on that later. In this section, we will use the slightly more compact, “rotated” version of the surface code. Stabilisers are defined as follows. We start with a rectangular lattice with $d\times e$ vertices, corresponding to qubits. We aim to encode a single logical qubit, so we need to fix $\mathit{de}-1$ stabilisers. To do so, we first colour in the lattice in a chequerboard pattern, where each red (darker) area corresponds to an $X$ stabiliser on all of its adjacent qubits, whereas each green (lighter) area corresponds to a $Z$ stabiliser. Colouring the inside of the lattice in this way gives $(d-1)(e-1)$ stabilisers. To get all $\mathit{de}-1$ stabilisers, we still need to fix $d+e-2$ additional stabilisers. To get these, we introduce weight-2 stabilisers along the boundaries at every other edge, which we depict as “blobs”. We colour these blobs in the oppose colour to the nearest tile, obtaining the following picture:

There are $2(d-1)+2(e-1)$ edges around the whole boundary, so adding a “blob” to every other edge gives us $(2(d-1)+2(e-1))∕2=d+e-2$ more stabilisers as required. By design, all stabilisers of different types overlap on two qubits, so they commute. Since we alternate edges, one pair of opposite boundaries (in this case the left and right) will end up with X-blobs and one pair (top and bottom) with Z-blobs. In the literature, these are called X-boundaries and Z-boundaries, respectively. The logical $\overrightarrow{X}$ operator consists of a line of Pauli $X$ operators connecting the two X-boundaries, whereas the logical $\overrightarrow{Z}$ operator consists of a line connecting the two Z-boundaries:

Note that the specific choice of path between the boundaries is not important and we are even allowed to cross tiles diagonally. However, it is important that the path touches each area of the opposite colour an even number of times. This ensures that the logical operator commutes with all of the stabilisers. In the example above we could have equivalently chosen $X_4{X}_5{X}_6$ or $X_5{X}_6{X}_7$ for $\overrightarrow{X}$, but not $X_7{X}_8{X}_5{X}_6$, because the latter touches a green tile 3 times. Using the stabilisers and the logical operators for the surface code, we can apply the recipe from the previous section to construct its encoder. In fact, we can represent the encoder using two equivalent ZX diagrams, one based on the X-stabilisers and one on the Z-stabilisers:

Note how the diagrams of the encoders have a direct visual relationship to the picture (11.20): to draw the X-stabilisers, we put an X spider on every vertex, place a Z spider in the centre of each red region in (11.20), and connect it to all of the adjacent vertices. Finally, we “embed” the logical X operator by placing a Z spider on the input and connecting it to each of the vertices where $\overrightarrow{X}$ has support. For the Z-stabilisers, we apply the same routine, reversing the roles of X and Z. In the surface code, we can topologically deform a logical operator by multiplying it by any stabiliser. We can perform the same calculation graphically using strong complementarity. As we saw in the proof of Lemma 4.3.4, we can treat spiders as bit-vectors, and by applying strong complementarity, we can “add” the neighbourhood of one spider to that of another, modulo 2. Applying this concept to the surface code, we obtain for example:

This just amounts to changing the basis for the linear space $S$ represented by this normal form, which has the same effect as changing the generators for the associated stabiliser group.

11.3.4.1 Decoding errors in the surface code

Aside from the fact that they can be implemented with nearest-neighbour operations in a 2D architectures, surface codes are also popular because error syndromes can be efficiently decoded by taking advantage of their geometric structure. Recall from Section 11.2.2 that the decoding problem for stabiliser codes refers to the problem of mapping the outcome of a sydrome measurement to a Pauli correction $\overrightarrow{Q}$ that is most likely to recover our error-free state. There are many proposals for fast decoders for the surface code. Here, we will sketch how one of the simplest ones, based on minimum weight perfect matching works. First note that since surface codes are CSS codes, we can identify Z-errors in $\overrightarrow{Q}$ using the outcomes of X stabiliser measurements, and vice-versa. Hence, we can treat these two types of errors independently. Suppose a certain configuration of Z errors occurs on our physical qubits. Much as we did in Section 11.2.2, we can figure out where the error syndrome will be by “pushing” the error through the Pauli projectors corresponding to X measurements, using the $\pi$-copy rule, and seeing which projectors end up with a $\pi$:

This is the same thing as figuring out which stabilisers anti-commute with the given error. If an even number of Z errors lie in the support of an X projector, a pair of $\pi$ phases will cancel out, yielding a $0$ measurement outcome. Hence, the syndrome only reveals the places where an odd number of errors overlap with a stabiliser. As a consequence, error syndromes will always appear as the endpoints of a “path of errors” through the lattice:

These paths will always either connect a pair of locations where the error syndrome is 1, as we see above, or they will connect a single syndrome-1 location to a boundary of the surface, as in this example:

Since Z boundaries don’t have any X stabiliser measurements, this also works. Hence, if we get just two syndrome-1 outcomes far from the boundary, the most likely place errors occurred were along the shortest path between those two spots (assuming as we have been that errors occur independently and with the same probability on every qubit, since a longer path must have involved more errors occurring). If we get just one syndrome-1 outcome, the most likely place errors occurred was along the shortest path between that syndrome and the boundary without non-commuting stabilisers. “Hang on!” you might say, “there can be multiple shortest paths between points!” And you’d be right. However, all of these paths are equivalent, up to stabilisers. For example, there are 3 shortest paths between the syndromes in (11.23). The 2 other ones can be obtained from the one shown by multiplying by Z stabilisers:

Here we started with the diagram (11.23), composed with one of the Z stabilisers that is not shown explicitly in this Z-X normal form. Since stabilisers don’t change the encoded state, correcting errors along any of these 3 paths (or actually any path between these endpoints) will have the same effect. The reason this works is, as we showed for the logical embedding at the end of the previous section, the stabilisers of the surface code relate topologically-equivalent paths through the surface, provided they have the same end points. Of course, this only tells us what to do if we see zero, one, or two syndrome-1 measurements. However, we can extend this to an algorithm that does a pretty good job decoding any syndrome. First, we make a graph whose nodes correspond to places where we observe a syndrome-1 outcome (and an extra dummy node for the boundary). We label the edges with a weight indicating the length of the shortest path between those locations, e.g.

A perfect matching is then a subset of the edges of this graph, where every node (except the “dummy” node for the boundary) is adjacent to exactly 1 edge. A minimum weight perfect matching (MWPM) is a perfect matching where the sums of the weights on the chosen edges is minimal. An example of a MWPM for the graph above is:

The simplest minimum weight perfect matching decoder therefore proceeds as follows. For the X stabiliser measurements, make a syndrome graph as in equation (11.25) and compute its MWPM. Then, correct Z errors along the paths indicated by the MWPM. After that, rinse and repeat for Z stabiliser measurements and X errors. It is worth noting that this algorithm does not always find the minimum weight error associated with a syndrome, but it often gets pretty close, especially in the case where there aren’t too many syndrome-1 outcomes. It is also very fast, particularly if we are allowed to just approximate the MWPM and/or compute in parallel. We will briefly discuss various implementations of this algorithm and their performance in the References of this chapter.

11.3.5 Scalable ZX notation for CSS codes

As might be clear from diagrams like (11.17), writing CSS encoder maps explicitly can start to get unwieldy for large numbers of stabilisers or stabilisers with relatively high weight. Later on, we will also want to prove some generalities about all CSS codes, so it would be useful to come up with some notation for writing a generic CSS code as a ZX-diagram. Thankfully, the scalable ZX-calculus, which was introduced in Section 10.2, can solve both of these problems. To see how this works, we can start from the recipe given in the previous section for building an encoder for a CSS code from its X-logical operators and X-stabilisers. Suppose we represent this data as a pair of boolean matrices $L_X$ and $S_X$, whose columns correspond to each of the operators and whose rows correspond to qubits, where a 1 indicates the presence of an $X$. For example, the matrices $(L_X,S_X)$ associated with the Steane code are the following:

Whereas in the previous section, we needed to say in words how to build the encoder out of X operators, we can now do it succinctly as a single diagram, which works for any CSS code described by the pair $(L_X,S_X)$:

Inspecting this picture, we can indeed see that it is saying to introduce $k$ input spiders for the X-logicals, and connect them according to where $X$’s appear, then introduce $m$ internal spiders for the X-stabilisers and again connect them to outputs according to where $X$’s appear. This gives us the X form for the encoder, but of course we should also be able to construct a Z form by reversing the role of the two colours of spider. To get the colour reverse of a matrix arrow, we can just reverse the direction and take the transpose of the matrix:

Hence, if we equivalently present a CSS code as a pair of matrices $(L_Z,S_Z)$ describing the Z-logical operators and Z-stabilisers, respectively, we can write the associated encoder map as:

This not only gives us convenient notation for the encoder, but also for the stabiliser measurements themselves. It was shown in Exercise 6.7 that the Pauli projectors associated to all-X or all-Z Pauli stabiliser measurements take a particularly simple form:

If $s=0$, the projector on to a stabiliser ${\overrightarrow{Z}}_j$ consists of an isolated X-spider connected to Z-spiders on the support of the ${\overrightarrow{Z}}_j$. If we compose all of the projectors on to Z-stabilisers together and fuse spiders, we’ll obtain this picture:

Similarly, if we project on to the 0 outcome with all of the X stabilisers, we’ll obtain:

If we simply compose maps (11.29) and (11.30), we will get the projection onto the stabiliser subspace $\text{Stab}(S)$. This is what happens if we measure all of the stabilisers and get outcome 0. To represent other outcomes, we should place a $0$ or a $\pi$ on each of the internal spiders of the Pauli projections. To do this for generic outcomes, we need to extend the scalable notation a bit. Back when we introduced the scalable notation, we interpreted a scalable spider labelled by a phase $\alpha$ as $n$ spiders, all with the same phase $\alpha$ on them. However, we could just as well label a spider with a vector of different phases $\overrightarrow{\alpha }=({\alpha }_1,\dots ,{\alpha }_n)$ and define scalable spiders as:

Of particular interest for us are vectors of $0$s and $\pi$s, i.e. vectors of the form $\overrightarrow{b}\cdot \pi :=(b_1\pi ,\dots ,b_n\pi )$ for some boolean vector $\overrightarrow{b}\in {𝔽}_2^n$. Using this extended notation, a full stabiliser measurement for a CSS code with outcome syndrome $\overrightarrow{s}=(\overrightarrow{x},\overrightarrow{z})$ can be written compactly as:

For a CSS code, we can assume without loss of generality that all of the X-logical operators and X-stabilisers are linearly independent. In other words, we can assume the block matrix $(L_X{S}_X)$ is injective. Consequently, there exists some parity matrix $J$ such that:

Since injective parity maps are always isometries, we have:

This implies that the encoder (11.28) is an isometry, and is in fact a strictly stronger condition.

This gives us some nice tools for working with CSS codes generically, which we’ll use several times when it comes to deriving fault-tolerant operations in Section 11.4.

11.4 Fault-tolerance

If we want to perform quantum computations in a way that can withstand errors, coming up with a good quantum error correcting code is only half the story. We also need to figure out how to perform state preparations, gates, and measurements on encoded qubits. Suppose that every time we performed a gate we had to decode our $n$ physical qubits into $k$ logical qubits, perform the gate, then re-encode. This seems like a lot of work just to do one gate, but what is actually worse is that our logical state will be completely unprotected between when we decode and re-encode our qubits. We will run into similar problems with state preparations and measurements. We saw half of a solution to this problem already in Section 11.2.3 with Definition 11.2.9. If we want to perform a unitary gate $U$ on our logical qubits, we can find some other $\tilde{U}$ acting on the physical qubits, satisfying:

Essentially the same idea applies to state preparations, except there are no input wires, so we don’t need an encoder on the RHS. That is, we can implement the preparation of a logical state $|\psi ⟩$ by preparing some physical state $|\tilde{\psi }⟩$ satisfying:

Of course, one could prepare $|\tilde{\psi }⟩$ by preparing $|\psi ⟩$ then performing the encoder isometry as an actual quantum operation, which we could implement using unitaries and ancillae. However, as we’ll see later, there are various reasons we might want to prepare $|\tilde{\psi }⟩$ directly in a different way. Finally, implementing measurements on encoded qubits is also a similar idea, but with a little twist accounting for the fact that our physical measurement might have more outcomes than our logical one. While we might in general want to implement arbitrary measurements on encoded qubits, lets focus just on ONB measurements to make things a bit simpler. Let $[m]:=\{1,2,\dots ,n\}$ be a finite set of indices for any $m\in \mathbb{N}$. We say a physical ONB measurement $\tilde{M}={\{|{\tilde{\varphi }}_j⟩\}}_j$ on $n$ qubits implements a logical ONB measurement $M={\{|{\varphi }_i⟩\}}_i$ on $k$ qubits if there exists a function $\ell :[2^n]\to [2^k]$ where, for all states $|\psi ⟩$, we have:

This condition says that, for any logical state, the Born rule probabilities obtained from measuring $M$ can be computed in terms of the probabilities of $\tilde{M}$ measurements. Normally the function $\ell$ is very simple, e.g. if $k=1$, it could be simply computing the parity of boolean outcomes on the $n$ physical qubits. In Section 11.2.3, we mentioned that we usually don’t actually perform the encoder map on our quantum computer, but use it purely as a mathematical object to relate the logical qubits to the physical ones. Now we can see why that is the case. If we can find encoded states, gates, and measurements, then we can simulate any logical computation on $k$ qubits using a physical one on $n$ qubits without ever explicitly performing $E$. Suppose we are interested in the results of a logical computation involving applying a sequence of gates $U_1,\dots ,U_t$ to a state $|\psi ⟩$ and measuring in the logical ONB ${\{|{\varphi }_i⟩\}}_i$. Then we would like to sample from this distribution: