Chapter 8
Measurement-based quantum computation

Up to this point, whenever we talked about a quantum computation, we were talking about the circuit model. In this model of computation you start with a simple state, usually $|0\cdots 0⟩$, which is then inserted into a quantum circuit, i.e. a collection of simple unitaries that combine to make something more complex. At the end we measure the qubits in some fixed basis, and the outcome of these measurements is the outcome of our computation. This model of quantum computation is inspired by classic logic circuits. It is a universal model, meaning that we can in fact present arbitrary quantum computations in this way. This however does not mean that this is always the best way to think of a quantum computation, or the one that matches the most closely to how a real-world quantum computer would function. There are more ways to implement a computation on a quantum state than just by directly performing a unitary on it. If we have some entangled state, then measurement of one part of the state induces an action on the other part. Depending on the entanglement and the measurement this action could be unitary or non-unitary. Let’s take for example a slight modification of the teleportation example of Section 3.3.2 that we also saw in Section 6.5:

In this example of gate teleportation we have some maximally entangled state $|\psi ⟩$, which we entangle with the qubit we want to do a computation on using a CNOT. By then measuring some qubits, the resulting state has a unitary $U$ and a Pauli applied to it. The Pauli we apply however is determined by the measurement outcome. This is an inevitable feature of using measurements to do computations: measurement non-determinism. Since we don’t control which Pauli gets applied, and it is ‘stuck’ behind the $U$, this seems like it would prevent us to control which computations get executed. However, it turns out that for smart choices of measurements and smart choices of $U$, we can feed-forward the Pauli errors. In this way we can make the non-determinism ‘deterministic enough’ to work for us. There are various degrees of how much we can use measurements to do computations for us. On one end of the spectrum we don’t use measurements at all, performing all computations with unitary gates. Moving a bit further along the spectrum we can decide to implement only certain types of gates using gate teleportation (like in Eq. (8.1)), or using its closely related cousin of state injection. Even further along the spectrum we can let all multi-qubit dynamics be taken care of by measurements, which is the case in lattice surgery or fusion-based computation. We will have a lot more to say about lattice surgery in Chapter 11. On the extreme end of the measurement-based scale is the one-way model, where arguably all computation is done by measurements. In the one-way model we start with a large entangled graph state, and then we perform single-qubit measurements in different rotated bases. The choice of which qubit to measure and in what basis it is measured is informed by the computation you want to do and what the previous measurement outcomes were, while the starting graph state (apart from its given size) usually doesn’t depend on the particular computation. In this model all computation is done by measurements. Such a computation might for instance look like the following:

Here we start with a four qubit graph state, and then we measure each of these in different bases. The Boolean variables $a$, $b$, $c$ and $d$ represent each of the measurement outcomes and are the output of this computation. In this example we have pre-determined measurement planes, i.e. whether the measurement takes place in a (rotated) $Z$ or $X$ basis, but some adaptive measurement angles. I.e. while the top qubit is always measured in a basis with angle $\frac{\pi }{2}$, the third qubit has a measurement angle ${(-1)}^a\frac{\pi }{4}$, meaning that whether we measure it in the angle $\frac{\pi }{4}$ or $-\frac{\pi }{4}$ depends on the measurement outcome of the qubit $a$. This means there is an order fixed on the measurements of these qubits, with qubit $a$ having to be measured before qubit $c$. Collectively, we call models of quantum computation using measurements measurement-based quantum computing (MBQC). While the circuit model is inspired by classical circuits, MBQC has no classical counterpart. There are various reasons why we might want to consider MBQC as opposed to quantum circuits:

• Certain unitaries might be tricky to implement, requiring trial and error. By using a technique like gate injection we can prepare resource states ‘offline’, and have them ready for when they are needed.
• Replacing unitaries for measurements can sometimes help us trade ‘time’ for ‘space’, allowing us to parallelise more computation at the cost of requiring more qubits.
• For certain types of hardware, it makes less sense to implement operations using a series of simple unitaries, instead preferring to do more measurements so that your qubits are shorter-lived. For instance, if the qubits are photons, we can entangle them by doing a fusion measurement and then doing simple rotations and measurements. This is preferable since it is hard to store photons for a longer period of time, so here the trade-off between time and space needs to be more in the space direction.
• When we consider fault-tolerant models of computation like in Chapter 11, we will be doing constant measurements anyway in order to protect our data against errors, so why not use measurements to enact operations on our data at the same time.

In this chapter we will look in detail at the one-way model. It turns out that graph-like diagrams can naturally be understood as measurement patterns. In this way we can see that we can indeed do universal quantum computation in the one-way model. We will also see more broadly how we can determine when a computation can be made deterministic. We do this by studying generalised flow, or gflow for short, which tells us how to feed-forward Pauli errors. It turns out that any deterministic measurement pattern with gflow can be efficiently transformed back into a quantum circuit. This gives us a triangle of translations, from quantum circuits, to ZX-diagrams, to measurement patterns, and back to quantum circuits. Because we can rewrite ZX-diagrams, this gives us a unified way to think about circuit optimisation and measurement-pattern optimisation.

8.1 Measurement fragments

If we were to formally specify what a computation in the quantum circuit model is, it would be something like: prepare $n$ qubits in the $|0⟩$ state, apply a series of unitary gates $G_1,\dots ,G_k$, then measure all $n$ qubits in the computational basis, giving some bit string $\overrightarrow{x}$, and finally post-process this with some output function $p(\overrightarrow{x})$ giving the final outcome. In contrast, we might formally specify a one-way computation as follows.

Note that we will talk about what these ‘measurement planes’ are in more detail later, for now you can think of the $\mathit{XY}$ plane as corresponding to $Z$-spiders and the $YZ$ plane as corresponding to $X$ spiders.

Definition 8.1.1 specifies a complete calculation from beginning to end where all qubits end up measured. If we represent it as a ZX-diagram it hence corresponds to a scalar ZX-diagram, i.e. a diagram with no inputs or outputs. This is no different from the circuit model, where for a full computation we also have to fix an input state and end by measuring all qubits. However, just as it is useful in the circuit model to think of just a part of a computation which has some input and output qubits, it is also useful to think of ‘fragments’ of a measurement-based computation that can be composed together to create more complicated computations. These fragments have inputs and outputs just like a quantum circuit would. For instance, a measurement fragment that implements a CNOT gate is given by the following diagram:

Here the top qubit is both an input and an output and hence isn’t measured. The third qubit is an input, but is not an output and hence is measured. The fourth qubit is an output and hence also isn’t measured. The second qubit is ‘internal’ and is hence prepared and measured as part of this fragment. The fragment (8.3) implements a CNOT gate up to a known Pauli error that depends on the measurement outcomes $a$ and $b$. We can calculate this Pauli error by simplifying the diagram:

Hence we end up with the circuit $(Z^b\otimes (Z^b{X}^a))\circ \text{CNOT}$. Since the error is a known Pauli, later measurements can be adapted to absorb these errors so that the overall effect of this measurement fragment is the application of a CNOT gate. We call this process of pushing Pauli errors outside of the pattern into the future feed-forward. Let’s give a bit more formal definition of a measurement fragment. For that we need the concept of an open graph.

The reason we call this a ‘stand-alone’ fragment is because this definition doesn’t deal with fed-forward Pauli errors. To prevent making this too complicated for now, we postpone that discussion until later. This definition is maybe a lot to take in, but the corresponding ZX-diagrammatic picture should make things more clear. We construct the ZX-diagram corresponding to a measurement fragment as follows. For every vertex in $V$ we add a Z-spider, and for every edge in $E$ we add a Hadamard edge between them. Then we add an input wire on a spider if it is in $I$ and an output wire if it is in $O$. This so far gives us a graph-like diagram and an open graph (where the graph-like diagram is phase-free). However, now we also add an additional output wire to every non-output spider, to get a diagram that looks something like this:

Now on each of those additional output wires, we are going to plug in a measurement effect, corresponding to the measurement plane and angle of that vertex:

Here the ${\alpha }_k$ denotes the measurement angle of the pattern, and the $b_k$ is a Boolean variable denoting the outcome of the measurement. Note that ${\alpha }_k$ is actually a function of the variables $b_1,\dots ,b_{k-1}$ representing the outcomes of the previous measurements. These names $\mathit{XY}$, $\mathit{XZ}$ and $YZ$ come from the fact that these effects lie on those corresponding planes of the Bloch sphere:

We see then that if in the fragment (8.5) we choose $\mathit{XY}$ for the measurement-plane of both qubits and we simply set the measurement angles to $0$ that we get precisely the measurement fragment (8.3) implementing the CNOT gate. We can also construct a fragment that implements an arbitrary single-qubit unitary. Recall that we can use the Euler decomposition of such a unitary to write it as a sequence of a $Z$ phase gate, and $X$ phase gate, and then another $Z$ phase gate: $\text{<object data="svgs/euler-decomposition.svg" alt="diagram of euler-decomposition" class="svg-diagram"></object>}$. Let’s try to write down a measurement fragment that implements this, by putting each of the phases $\alpha ,\beta$ and $\gamma$ into the measurement angle of a qubit:

This is not exactly correct. There are a couple of things we need to fix. For one thing, there is a Pauli error at the end: an $X$ gate depending on $b+d$ and a $Z$ error depending on $a+c$. We will learn how to deal with such errors later. But there is also a problem with the phases. We want the phases to be $\alpha$, $\beta$ and $\gamma$, but we see that depending on the measurement outcomes we might have actually gotten $-\beta$ or $-\gamma$. This is where the condition of Definition 8.1.4 comes in that measurement angles are allowed to depend on previous measurement outcomes. To make this fragment do what we want it to do, we need to make it adaptive. We first measure the qubit labelled by the measurement outcome $a$. If $a=0$, we measure the qubit $b$ in the angle $\beta$, which gives what we want. Otherwise we measure it in the angle $-\beta$. Hence, the measurement angle is ${(-1)}^a\beta$. Rerunning the calculation (8.7) with $\beta$ replaced by ${(-1)}^a\beta$, we see that we get the final phase of ${(-1)}^a{(-1)}^a\beta =\beta$, so that now the final angle no longer depends on the measurement outcome! We can do the same with $\gamma$, letting the measurement angle instead be ${(-1)}^b\gamma$. With these changes the measurement fragment becomes:

Apart from the Pauli error at the end that we still need to deal with, this implements the unitary we want. Note that in the fragment implementing the CNOT (8.3), the measurement angles didn’t depend on each other, so that the order of measuring the qubits wasn’t important. In (8.8) however, the measurement angles of some of the qubits depend on the measurement outcomes of other qubits, so that those qubits have to be measured first. This gives us a ‘direction of time’ on the pattern. It makes sense that we need to have some kind of adaptivity or dependency in our calculation. If we could do universal computation without such dependencies, then we could measure all qubits simultaneously, and do computations in constant time! So now we have a measurement fragment implementing a CNOT and another one implementing arbitrary single-qubit unitaries. Hence, if we can combine these then we can implement arbitrary unitaries. However, now we get to why we called these measurement fragments ‘stand-alone’: there is the problem of the Pauli errors. Let’s see what we can do with them. If a fragment with a Pauli error occurs at the end of our computation this is easy enough to deal with. At the end, we measure all the qubits in the computational basis anyway. This means that these errors just change how we should interpret the measurement outcomes:

So if we were feedforwarding an $X$ error, i.e. $x=1$ above, then this changes how we should interpret the measurement outcome we got. If we observe the measurement outcome $a^{\prime }$ then this is actually $a^{\prime }=a\oplus x$. So to get the ‘actual’ measurement outcome $a$, we just take $a^{\prime }\oplus x=a\oplus x\oplus x=a$. A $Z$ error ($z=1$) doesn’t change the measurement outcome when we measure in the computational basis, so we can ignore those in this setting. A $Y$ error, i.e. where both a $Z$ error and an $X$ error occurred, we can treat the same as an $X$ error here. In general though, the measurement fragment will happen somewhere in the middle of the computation so that the errors will not change the final measurement outcomes, but change how we should run the next fragments in the sequence. For instance, let’s see what would have happened if a Pauli error had happened on the input qubit prior to executing the measurement fragment (8.8):

We see that we can push these errors to the output of the fragment, at the cost of changing the angles in the unitary to potentially have minus signs, and additionally changing our output Pauli error. But these Pauli errors we have on the input arise from measurements we have done before, so we know what this error is. This means we can decide the measurement angle of our measured qubits based on this input Pauli error, in the same way we also change it based on the measurement outcomes of the qubits internal to the fragment. The full pattern that can also deal with incoming errors then becomes:

This still gives us a Pauli error at the end, but this is fine since we now know how to deal with this. In the definition of a stand-alone measurement fragment Definition 8.1.4 we only allowed the measurement angles to depend on previous measurement outcomes, and not on Pauli errors being fed-forward into it. Now that we know that we need this kind of adaptivity, we can give a definition of the kind of fragment we need.

Note that we take it as part of the definition of a measurement fragment to specify what the output errors are. By specifying what we consider ‘errors’ we are at the same time specifying what our desired outcome is, and hence what the linear map we are trying to implement is. We also need this error information as it needs to be fed-forward into the fragments following it.

Now that our definition of a measurement fragment can specify how incoming Pauli errors should change the measurement angles, and how the resulting errors should be fed-forward, we can actually compose these fragments together. We will not formally define how to do so, as this is quite tedious, but one can visualise it as just connecting the associated ZX-diagrams together and pushing the internal Pauli errors to the end.

8.1.1 Universal resources

We have described a measurement fragment to implement a CNOT gate and one that can implement an arbitrary single-qubit unitary. As CNOT gates and single-qubit unitaries form a universal gate set, we see then that we can construct a measurement fragment for any unitary we would want to implement. Hurray! Note however that the resulting graph state we need will depend on the specific unitary we want to implement. There is then still some ‘information’ about the computation that is present in the starting resource state. This then raises an interesting question: can we implement arbitrary unitaries using a measurement fragment that has a fixed graph state? We need to be a bit careful about how to formally state this question, because there are unitaries that are really hard to implement, and so we would expect them to require a large resource state to prepare (put simply: if we only have $k$ measurements, we could represent at most a $k$-dimensional subset of all unitaries, but the space of all unitaries scales exponentially with the number of qubits). We hence shouldn’t consider a fixed resource, but rather a family of resource state that is allowed to scale with the cost of the unitary. A more formal version of the question would hence be something like:

Does there exist a family of open graphs $G_k$ where $G_k$ consists of poly$(k)$ vertices, such that for any $n$-qubit unitary $U$ with $m$ gates, we can find a measurement pattern implementing $U$ which uses the open graph $G_k$ where $k=\text{poly}(n,m)$?

Maybe perhaps surprisingly, the answer to this is yes! There exist universal resource states which allow you to implement arbitrary quantum computations up to some size. A particularly nice example of a family of universal resource states are the 2D cluster states:

I.e. the graph is just a big square grid. The trick to seeing why this is universal, is that we can use measurements in the $YZ$ plane to strategically cut holes into the grid:

This allows us to shape the grid into whatever pattern we need it to be to perform the computation we want.

8.2 Determinism and gflow

We have now seen that we can do universal computation using the one-way model. An important part in getting there was knowing how to deal with the wrong measurement outcomes by finding ways to feed them forward. So far we have done this essentially by trial and error: we construct a simple fragment, observe that we get the wrong phases sometimes, and then change them to correct for this. In this section we will find a more systematic way to think about correcting errors and when we can see that a measurement fragment can be made deterministic. But first: let’s look at the connection between measurement fragments and graph-like diagrams.

8.2.1 Graph-like ZX-diagrams as measurement fragments

It turns out that if we take the ZX representation of a measurement pattern, ignore the adaptivity needed to correct for ‘wrong’ measurement outcomes, and fuse some spiders, that we get a graph-like diagram. For instance, doing this for the fragment (8.7), we get:

This graph-like diagram is then a representation of the ‘post-selected’ measurement fragment, where all the measurement outcomes where what we wanted them to be. It turns out the converse is also true: any graph-like diagram can be seen as a post-selected measurement fragment, just by unfusing some phases and introducing some identities:

If we were to actually try to run this as a measurement fragment, we would of course usually get some of the ‘wrong’ measurement outcomes. So this fragment is only useful if we know how to deal with all measurement outcomes, so that we can make the pattern deterministic. Can we do this somehow? This is not just a niche question we are asking because we like diagrams. We can write any quantum circuit as a graph-like diagram, so if we could do this then this would give us an easy way to translate a circuit into a deterministic measurement fragment. It turns out that it is in general not possible to turn graph-like diagrams into deterministic measurement fragments. This is for the simple reason that we can write down ZX-diagrams that are not isometries. For instance, consider the following graph-like diagram:

By doing some colour changing and identity removals, we see that this is just a 2-input, 2-output Z-spider, which is a projection and is not unitary. If we could deterministically perform such a projection, we could do non-unitary quantum computation! Or even more simply, consider the graph-like diagram . If we could implement this ZX-diagram deterministically, we would be doing post-selection. So it is not always possible to turn a graph-like diagram into a deterministic measurement fragment. But can we at least somehow determine when we can do so? As it turns out: yes. For a particularly strong type of deterministic measurement pattern there is a one-to-one correspondence to graph-like ZX-diagrams with a property called gflow.

8.2.2 The measurement correction game

To understand when we can implement a correction strategy for measurement errors on a graph-like ZX-diagram, let’s consider a small toy diagram to see what we can do:

This is of course not a realistic diagram that we would expect to encounter when doing MBQC, but it will serve to demonstrate the principle of correction. Here our goal is to get rid of the $\pi$ phase. We can do this by changing the spider with the $\beta$ phase:

Hence, as long as we measure the qubit with phase $\beta$ after the one with $\alpha$, an error at $\alpha$ can be corrected by changing the measurement angle of the $\beta$ qubit to be $-\beta$. Here we could have also chosen to change $\gamma$ in order to correct the error at $\alpha$. Finding the right correction was easy here, because the $\beta$ spider was only connected to $\alpha$ and nothing else. Let’s consider a slightly more complicated diagram:

In this case, changing the phase of $\beta$ does still remove the error at $\alpha$, but it also changes the phases at the other spiders:

Now if we can run the pattern such that the qubits with the $\gamma$ and $\delta$ phase can be measured after the $\alpha$ qubit, then this is fine, since we can still decide to measure them with a different phase to correct for the additional $\pi$ phase they have. But if we suppose that we have already measured the qubit with the $\gamma$ phase, then this would not be possible. In that case however, we see that we can apply the same ‘$\pi$-pushing’ trick with $\delta$ to remove the additional phase $\gamma$ got:

This gave us an additional $\pi$ phase at $\beta$ as well, but that is fine as we are already considering changing the phase at $\beta$. Hence, to correct the error at $\alpha$, we can decide to change the phase at $\beta$ and $\delta$, and this leaves the phase at $\gamma$ invariant. Let’s try to formalise what is happening here. We see that the trick of pushing out an $X(\pi )$ phase affects the phases on all the neighbours of this vertex, and that if we affect the phase of a vertex twice, that this then cancels out the effect. The qubits will be measured in some order, so we must make sure that whatever qubits we affect the phase of must be measured after the qubit we are trying to correct an error at. We can capture this behaviour in a little game: you are given an open graph with vertices $V$ where every vertex is labelled with either the presence or absence of an error (a 1 or 0). You are allowed to do the operation ${\mathbf{\text{flip}}}_v$ for a vertex $v\in V$, which flips the value of the error on all the neighbours of $v$ (but not at $v$ itself). The goal is to move all the $1$’s (the errors) to the output vertices. For example:

For some open graphs and configurations of errors, this task might be impossible. For example, there is no solution for the following graph:

Which makes sense, because if we were to try to build a one-way model computation on this open graph, it would map two qubits to one qubit, so there is no way we could do such a computation deterministically. The question then is, for which graphs can you always win this game, regardless of where the errors occur? We can see that a winning strategy is the following: first, find an ordering $\prec$ of vertices which give a direction of ‘time’ going from inputs to outputs, and find for each non-output vertex $u$, a correction set $g(u)\subset V$ of vertices in the future of $u$ (with respect to the ordering $\prec$) such that applying ${\mathbf{\text{flip}}}_v$ for all $v\in g(u)$ flips the bit on $u$, and potentially also flips some other bits, as long as those bits all belong to vertices that are in the future of $u$ (again, with respect to $\prec$). Now, for any instance of the game we can apply the following strategy: find a minimal vertex $u$ (w.r.t. $\prec$) which has an error. Then apply ${\mathbf{\text{flip}}}_v$ to all $v\in g(u)$. This removes the error on $u$, and only introduces new errors on vertices in the future of $u$. Then find a new minimal vertex with an error and repeat until all the errors are moved all the way to the end at the outputs. This game describes the property of $g(u)$ in terms of the $\mathbf{\text{flip}}$ operation, but we can actually make the description a bit simpler and more natural to graph-theory language. Namely, we see that a vertex $w$ get its bit flipped by applying ${\mathbf{\text{flip}}}_v$ for all $v\in g(u)$ precisely when it is connected to an odd amount of vertices in $g(u)$. This is because if it is connected an even amount of times to vertices in $g(u)$, then it gets its bit flipped twice, so that nothing happens. Let’s capture this in a definition.

Using odd neighbourhoods we can rephrase the condition we needed on the correction sets $g(u)$: we need $u\in {\text{Odd}}_G(g(u))$ (applying flip for all vertices in $g(u)$ results in a flip at $u$) and if $v\in {\text{Odd}}_G(g(u))$ then $u\prec v$ (if $v$ gets flipped by the corrections for $u$, then $v$ needs to be in the future of $u$). This is in fact exactly what we require, and allows us to give the definition of the central concept of this chapter: gflow.

With what we discussed above we see that if an open graph has gflow, that this gives us a winning strategy for the error correction game.

8.2.3 Diagrams with gflow are deterministic measurement patterns

We can use gflow to describe how to transform a graph-like ZX-diagram into a deterministic measurement pattern. Let’s assume we have a graph-like ZX-diagram $D$ such that its corresponding open graph $G$ has a gflow $(\prec ,g)$. We see from Definition 8.1.5 that to describe a measurement fragment, we need to supply a number of data to fully define it. The first parts are easy enough to specify:

• We need to specify an open graph. For this we will just take the open graph we already have: $G$.
• A measurement order. For this we will take any order that is compatible with the partial order $\prec$. That is: we take a minimal vertex $v$ in the order (which does not have any vertices earlier in the order) and assign it to be measured first. We then find a new minimal vertex in the set $V\setminus \{v\}$ and assign it to be measured second. We repeat this until all vertices in $V\setminus O$ have been assigned a measurement order.
• A measurement plane function. Here we just assign every measured vertex to be measured in the $\mathit{XY}$ plane (we will discuss this choice in more detail in Section 8.5).

But now comes the hard part: we need to describe the measurement angles, and more importantly, how they are affected by the measurement outcomes. In practice, what this means is that we have a standard measurement angle $\alpha$ that comes from the angle we had in the ZX-diagram $D$. But then this $\alpha$ gains either a $+\pi$ phase or a negation depending on whether it appears in any correction sets, or odd neighbourhoods of correction sets of measured qubits that require a correction. Let’s write ${\alpha }_u$ for the phase that the spider $u$ has in the original diagram $D$ and $a_u$ for the measurement outcome when the spider $u$ is measured. Hence, if all the measurement outcomes $a_u$ are $0$, then the measurement angles we want to measure every qubit in is just ${\alpha }_u$. We will change these ${\alpha }_u$ to functions ${\alpha }_u^{\prime }$ that may depend on the $a_v$ of qubits $v$ that have been measured before $u$. Let’s first consider an input $u\in I$, which has to deal with a fed-forward Pauli $X$ error, but no other corrections from inside the pattern:

We see that we should change our initial choice of measurement ${\alpha }_u$ to a function ${\alpha }_u^{\prime }(z,x)={(-1)}^x\alpha +\mathit{z\pi }$ in order to account for the error being fed-forward into the spider. This doesn’t fully capture the incoming Pauli error though, as we see that the $X$ error has to be further fed-forward into the neighbours of $u$. All this does is change the measurement angle of that neighbour by $\mathit{x\pi }$, so we will ignore this detail. While this deals with the incoming Pauli error, it does not deal with the measurement error $a_v$ that it produces itself. To correct this we need the gflow condition. This procedure is the same regardless of whether the spider is an input or not, so let’s just take $u\in V\setminus O$ to be any measured qubit now. We then have a set of correction qubits $g(u)=\{v_1,\dots ,v_k\}$ and a set of ‘corrected’ qubits ${\text{Odd}}_G(g(u))=\{u,w_1,\dots ,w_l\}$. We then see that by changing the measurement angles at the correction and corrected qubits, we can remove the measurement error at $u$:

Here for simplicity we have assumed that each $v_i$ and $w_j$ is not an output, as we will deal with that case later. We have given every qubit in this diagram an additional output wire to denote that it can also be connected to some other spiders. The last application of $(\pi )$ does not affect these additional qubits, precisely because they are not in the odd neighbourhood of the correction set. So for every $v\in g(u)$ we set ${\alpha }_v^{\prime }(a_u)={(-1)}^{a_u}{\alpha }_v$ and for every $w\in {\text{Odd}}_G(g(u))$ with $w\ne u$ we set ${\alpha }_w^{\prime }(a_u)={\alpha }_w+a_u\pi$. In general, a spider could of course be part of multiple correction sets and odd neighbourhoods of correction sets. It will be useful to give these a name:

Then the actual measurement angle, as a function of the previous measurement outcomes, is

We are now almost done! The above tells us how to change measurement angles to correct errors when the correction sets $g(u)$ and corrected sets ${\text{Odd}}_G(g(u))$ only contain non-outputs. When instead an output qubit $o$ is in such a set, then we don’t change the measurement angle of $o$ (which we can’t do since $o$ is not measured), but we change the Pauli error that is being fed-forward. If $o\in g(u)$, then we get a Pauli $X$ error of $a_u\pi$, and if $o\in {\text{Odd}}_G(g(u))$, then we get a Pauli $Z$ error $a_u\pi$. In general then, the output Pauli that gets forwarded at output $o$ is $(z,x)=({\sum <!--\; FUNCTION\; APPLICATION\; -->}_{u\in S_2(o)}{a}_u,{\sum }_{u\in S_1(v)}{a}_u)$. We have now specified what all the measurement angles of the qubits should be, based on the fed-forward errors and the internal measurement outcomes, and we have specified what the outgoing fed-forward errors will be based on the measurement outcomes. This then indeed gives us a measurement pattern. By how we constructed the pattern, we see that it implements the ZX-diagram we started out with regardless of the internal measurement outcomes (up to the fed-forward Pauli error at the end). We have then proved the following result.

8.2.4 From circuits to measurement patterns

We started out this section with the goal of understanding how we can systematically create measurement fragments that are deterministic. We have seen that we have one powerful tool for ensuring determinism: the existence of a gflow. What we have however not yet done is finding a good source of measurement fragments that have gflow. As it turns out, if we take a unitary circuit consisting of Clifford and phase gates, and then turn it into a graph-like diagram by fusing all spiders and colour changing to Z-spiders as described in Proposition 5.1.8, the resulting diagram has gflow.

There are also some simple modifications we can make to an open graph that preserve the existence of a gflow. Like adding new vertices after an output or adding and removing connections between output vertices.

Note that these results only talk about creating a new pattern that also has a gflow. We are not defining an actual measurement pattern, and hence we are not saying anything about whether this new pattern implements the same linear map or not. In Section 8.3 we will prove that some more elaborate ways in which we can change graphs also preserve the existence of a gflow.

8.2.5 Focussed gflow

The definition of a gflow allows the correction set $g(u)$ to also induce corrections on other vertices, as long as those other vertices are in the future of $u$. That is, ${\text{Odd}}_G(g(u))$ can contain more than one vertex. It turns out that we can modify a gflow to just allow $u$ to be corrected and no other measured vertex (this turns out to be useful later).

8.3 Optimising deterministic measurement patterns

In Chapter 5 we saw two rewrites that proved very useful for optimising Clifford diagrams: local complementation and pivoting. These rewrites allowed us to remove internal spiders from a graph-like diagram. As we’ve seen in this chapter, we can view graph-like diagrams as measurement patterns, and then internal spiders become measured qubits. Hence, these rewrites now offer ways to optimise the number of qubits we need to measure in the pattern. Of course, this is only useful if it preserves our ability to deterministically implement the measurement pattern, i.e. if it preserves the existence of a gflow. That is precisely what we will prove in this section. While we tried to present the proofs here in as simple a way as possible, it still requires some stamina to process all the odd-neighbourhood acrobatics. So perhaps on a first read-through you might want to just read the statements of Proposition 8.3.2 and 8.3.5 and then move on to the next section to see what we will use these results for. Recall that for a graph $G$, we defined $G\star u$ to be the graph where we locally complemented about $u$. In this graph the neighbourhoods have been updated as follows for any $v\in V$:

We will also need to know how the odd neighbourhood of a set changes when you apply a local complementation.

Proving that pivoting preserves gflow is done quite similarly. Just like how we needed a lemma that told us how odd neighbourhoods evolved under application of a local complementation, we need one that tells us what happens when a pivot happens. For this it will be helpful to introduce a little bit of extra notation.

Let $u$ and $v$ be some vertices of $G$, and write $G\wedge \mathit{uv}$ for the graph where we pivoted along $\mathit{uv}$. Then for any $w$ we have:

We hence see that we can indeed do the spider-removing version of local complementation and pivoting while preserving the existence of gflow. You might at this point wonder whether we couldn’t just do the local complementation without removing the spider, and whether this preserves gflow. It in fact does not, but that is because we aren’t using the right notion of gflow for this: the spider-preserving version of local complementation (Lemma 5.2.4) introduces a $X(\frac{\pi }{2})$ phase on the spider being pivoted on. This makes it so that we can no longer interpret this spider as being measured in the $\mathit{XY}$ plane. The solution to this is to treat it as a qubit measured in a different type of plane. We will see how to do this in Section 8.5.

8.4 From measurement patterns to circuits

Starting with a quantum circuit, we can transform it into a graph-like diagram which has gflow (Proposition 8.2.6), and hence we can turn this circuit into a deterministic measurement pattern. We have also seen several ways in which we can change a measurement pattern while preserving gflow. These patterns we get don’t necessarily look very circuit-like any more, so it is not obvious any more how the connections and measurements in this pattern correspond to unitaries acting on an input state. In this section we will see that nevertheless we can transform an arbitrary deterministic measurement pattern with gflow back into a circuit that implements the same linear map. Since these patterns are deterministic, we can represent the linear map they implement just as a graph-like ZX-diagram, like we did in Section 8.2.1. The input of our algorithm will be a graph-like diagram whose underlying open graph has a gflow, and the output should be an equivalent quantum circuit. We call this process circuit extraction. The basic idea will be similar to the CNOT circuit extraction algorithm we saw way back in Chapter 4, but instead of doing one round of Gaussian elimination to get a circuit out, we will be doing ‘a little bit’ of row elimination in order to extract a single internal spider from the pattern. We repeat this until the diagram contains no more internal spiders. We then have a diagram looking very similar to the Clifford GSLC normal form of Section 5.3.3, which we know how to turn into a circuit. Since our algorithm doesn’t work with measurement patterns directly, but with ZX-diagrams, we can let the input be any graph-like diagram whose underlying open graph has gflow. Such a diagram will then look something like this:

We put some phases on the spiders for concreteness, but as our only consideration is whether the diagram has gflow, these are pretty much irrelevant to the steps we need to do to extract a circuit out of a diagram. So let’s start trying to make this diagram more circuit like. As in Section 5.3.3, we first observe that the spiders on the boundary already directly correspond to quantum gates: either single-qubit gates or two-qubit CZ gates:

Here we mark the two parts of the diagram by ‘unextracted’ and ‘extracted’ to denote that we are done with the part on the right. This part already looks like a circuit now, so we don’t have to do anything with that anymore. We will refer to the spiders on the boundary of the extracted and unextracted part as the frontier. We will be applying operations to the frontier in such a way that we can move frontier spiders to the extracted part and internal spiders onto the frontier. The reason we start at the end of the diagram instead of at the beginning is because it will be easier to show that such operations preserve the existence of a gflow on the remaining diagram. The extraction algorithm is only guaranteed to work if the diagram has gflow, so it is important that all the steps change the diagram in ways which preserve the existence of a gflow. For instance, in Eq. (8.25) the underlying graph of the unextracted part only changed in having no more connections between the output vertices. This is exactly the transformation that we showed in Exercise 8.4 preserves gflow. In the case of the GSLC normal form of Section 5.3.3, we realised that the internal connectivity of the diagram corresponds to a CNOT circuit. Here we can do something similar, but instead of rewriting the entire diagram to a CNOT circuit directly, we can ‘extract’ a single CNOT in order to change the connectivity of the diagram:

To demonstrate how we can use this, let us write down the biadjacency matrix from the frontier to the other spiders in our example diagram:

We see that if we add the fourth row to the third row that there will be only a single 1 on the third row. This means that the third frontier spider is only connected to a single internal spider, and hence corresponds to an identity spider that can be removed:

We now have one less spider in the unextracted part. We can again unfuse the phase of the frontier spider into the extracted part, and the same for the connections between the frontier spiders. We then rinse and repeat, extracting the spiders one by one. But why can we always do this? This is where gflow comes into play. Using gflow we can show that the biadjacency matrix always has this property that we can reduce at least one of the rows to contain a single $1$ using row operations: Suppose we have a graph-like diagram $D$ and that its underlying open graph $G$ has a gflow $(\prec ,g)$. Pick now the vertex $u$ that is maximal according to the partial order $\prec$ in the set $V\setminus O$. That is, $u$ corresponds to the last measured qubit. Now we know that $g(u)$ and ${\text{Odd}}_G(g(u))\setminus \{u\}$ only contain vertices in the future of $u$. So in this case they must only contain outputs. So let $o_1,\dots ,o_k$ be the outputs that form $g(u)$. Their sets of neighbours $N(o_j)$ then correspond to rows of the biadjacency matrix we wish to simplify. We are assuming we have already gotten rid of any connections between outputs, so that there are no outputs in the set $N(o_j)$. We know that ${\text{Odd}}_G(g(u))\subseteq O\cup \{u\}$ and furthermore ${\text{Odd}}_G(g(u))=N(o_1)\mathrm{\Delta }\cdots \mathrm{\Delta }N(o_k)$ (Exercise 8.2). So in fact ${\text{Odd}}_G(g(u))=\{u\}$. Now here comes the kicker: Taking the symmetric difference of sets follows exactly the logic of addition in $𝔽2$! If we ‘add’ two sets $A\mathrm{\Delta }B$, then if there is an $s$ with $s\in A$ and $s\in B$, then $s\notin A\mathrm{\Delta }B$, exactly how $1\oplus 1=0$. All the other cases are checked similarly. So when we were adding together rows in the biadjacency matrix, what we were really doing was calculating the symmetric difference of the neighbourhoods. So since $N(o_1)\mathrm{\Delta }\cdots \mathrm{\Delta }N(o_k)=\{u\}$, that means if we add together the rows of the biadjacency matrix corresponding to the outputs $o_j$, then the resulting row has just a single $1$, which corresponds to $u$. Hence, gflow tells us exactly which rows we can add together, and hence which CNOTs we need to place, in order to make progress. As we can do row operations on our biadjacency matrix using Proposition 8.4.1 and this preserves gflow, we will have after extracting a vertex still a diagram which has gflow. And hence when we repeat this procedure we will always be able to find some rows in the biadjacency matrix that combine together to form a row with a single $1$, whose spider can then be extracted. Note that this is a similar procedure to how we extracted a circuit from a CNOT+Phase diagram in Section 7.2: there we did column operations in order to reduce a column to contain just a single 1. Because we are extracting from the right here, we are doing row operations instead. At some point we will have removed all internal spiders, in which the case the remaining diagram is like the GSLC normal form of the previous chapter, except that the phases on the spiders can be arbitrary. This final bit can then also be transformed into a circuit using a variation on the procedure described in Section 5.3.3 and then we are done. We can then conclude with the following theorem.