Chapter 9
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 we 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 and reliably implement $U$, possibly up to performing some later corrections.

Hence, general models of quantum computation can do the bulk of the computation with either unitary gates, with careful choices of measurements, or with something in-between. At one end of the spectrum is the circuit model, where measurements are limited to fixed ONB measurements performed at the very end, and the “code” that implements an algorithm consists entirely of the choice of 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. (9.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 (which we’ll meet in Chapter 12) or more exotic models like fusion-based computation. On the opposite end of this “gates-vs-measurements” spectrum from the circuit model is the one-way model, where essentially all of the computation is done by measurements. In the one-way model we start with a large fixed 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 we 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. 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 teleportation we can prepare resource states ‘offline’, and have them ready for when they are needed.
• Replacing unitaries with 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 can be difficult to implement operations using many simple unitaries in sequence but relatively easy to do basic measurements on a large number of relatively short-lived qubits. For instance, if the qubits are photons, there are techniques one can use to produce entangled states and perform simple single-qubit 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 12, 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 focus on a particular model of MBQC called the one-way model, which relies on performing single-qubit measurements on graph states and feeding forward Pauli corrections. Along the way we will see techniques that apply more generally to optimising quantum computations, including circuits, using the ZX-calculus.

Graph-like ZX-diagrams can naturally be understood as computations in this model, which are called measurement patterns (Section 9.2.1). Using this connection, we will see that one 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 precisely how to feed-forward Pauli corrections when we obtain the ‘wrong’ measurement outcome during a computation (Section 9.2.2). It turns out that any deterministic measurement pattern with gflow can be efficiently transformed back into a quantum circuit (Section 9.4). 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.

9.1 Measurement patterns

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, a computation in the one-way model consists of a graph state $|G⟩$, a choice of single-qubit measurements at each vertex of $G$ (i.e. each qubit of $|G⟩$), and possibly some classical post-processing. Crucially, we allow each choice of single-qubit measurement to depend on previous measurement outcomes, which is called feed-forward. In this section, we will define a measurement pattern, which is a formal ‘program’ on the one-way model, playing an analogous role to a circuit in the circuit model.

Fixing a single-qubit measurement is the same as picking a single point (and its antipode) on the Bloch sphere. In the one-way model, we restrict to planar measurements, that is measurements which lie in one of the three perpindicular planes $\{\mathit{XY},YZ,\mathit{XZ}\}$ of the Bloch sphere. For a fixed plane, we can specify the choice of measurement as a single angle $\alpha$:

Notably, such measurements have the property that one can map between the two basis elements by applying a Pauli operator. This property will become important soon.

Normally, we assume the measurement plane is fixed, but the measurement angle ${\alpha }_v$ at time step $k$ depends on the outcomes of measurements at time steps $1,\dots ,k-1$. In fact, this already gives us a universal model of computation even if we fixed $\mathit{XY}$ plane measurements everywhere. However, we allow the other planes as a convenience. We will initially consider $\mathit{XY}$ plane measurements whose measurement effects are representable by (phased) Z-spiders. Starting in Section 9.5 we will see how the other two planes play a role, e.g. in representing phase gadgets.

Another convenience is to allow computations in the one-way model to have some input and output qubits. Recall that a complete computation in the circuit model consists of state preparation and measurement. So, in some sense there is only classical input (the circuit) and classical output (the measurement outcomes). However, it is still nevertheless useful to consider smaller parts of circuits, ranging from individual gates to subroutines, which have some quantum inputs and outputs.

The situation in the one-way model is similar. A complete computation in the one-way model fully prepares a graph state and measures all of its qubits, but 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 computation 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 pattern (9.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 pattern is the application of a CNOT gate. This is why we allow feed-forward in the one-way model.

In order to account for inputs and outputs to a measurement pattern, we work with open graphs.

We let an open graph with a specified measurement order and measurement-plane function correspond to a ZX-diagram 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.

We see then that if in (9.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 implementation (9.3) of the CNOT gate.

We can also construct a measurement pattern 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: . Let’s try to write down a measurement pattern 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 why we need to allow measurement angles to depend on previous measurement outcomes. To make this pattern do what we want it to do, we need to make use of feed-forward to account for previous measurement outcomes. 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 (9.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 pattern 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 pattern implementing the CNOT (9.3), the measurement angles didn’t depend on each other, so that the order of measuring the qubits wasn’t important. In (9.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. We could then do computations in constant time. While quantum computing is powerful, it is not that powerful!

So now we have a measurement pattern implementing a CNOT and another one implementing arbitrary single-qubit unitaries. Hence, if we can combine these then we can implement arbitrary unitaries. However, there is still the problem of the Pauli errors that need to be fed-forward. Let’s see what we can do with them.

If a pattern 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 pattern 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 patterns 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 pattern (9.8):

We see that we can push these errors to the output of the pattern, 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 pattern. 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: it should either be pushed through the next pattern, or otherwise be updating the final measurements in the computation.

We then see that for a good definition of measurement pattern, we should allow measurements to not only depend on previous measurement outcomes, but also on Pauli errors being fed-forward into the pattern. Accounting for these errors gives us all the data we need, so we are now ready to give a formal definition of a measurement pattern.

Note that we take it as part of the definition of a measurement pattern 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 patterns following it.

Since our definition of a measurement pattern 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 patterns 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:

Here ${\overrightarrow{z}}^{\prime }=f_Z(\overrightarrow{z},\overrightarrow{x},\overrightarrow{a})$ and ${\overrightarrow{x}}^{\prime }=f_X(\overrightarrow{z},\overrightarrow{x},\overrightarrow{a})$ are the Z- and X-errors as fed-forward through the first pattern, while $\overrightarrow{a}$ and ${\overrightarrow{a}}^{\prime }$ are the measurement outcomes of respectively the first and second pattern. The measurement angles of the second pattern now do not depend on $\overrightarrow{z}$ and $\overrightarrow{x}$, but on the fed-forward ${\overrightarrow{z}}^{\prime }$ and ${\overrightarrow{x}}^{\prime }$ instead.

9.1.1 Universal resources

We have described a measurement pattern 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 pattern 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 pattern 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 only have $k$ continuous degrees of freedom to pick out a specific unitary. However, the number of degrees of freedom in an arbitrary unitary grows exponentially with the number of qubits. We therefore shouldn’t consider a fixed resource, but rather a family of resource state that is allowed to scale with the cost of the unitary.

In order to get resource states whose cost scales in (approximately) the same way as quantum circuits, it is natural to ask if there exists a family of generic resource states $G$ with increasing numbers of 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 in $G$ with $O(\text{poly}(n,m))$ vertices. 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:

Cluster states are just big rectangular grids. In order to see that they are universal, 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:

We can then use the patterns we have already seen to implement a universal set of gates on the remaining parts of the graph state. Using this strategy, we can see that the width of the initial cluster state we need is linear in the qubit count and the height is linear in the gate depth.

9.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 pattern, 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 pattern can be made deterministic.

But first, let’s look at the connection between measurement patterns and graph-like diagrams.

9.2.1 Graph-like ZX-diagrams as measurement patterns

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 pattern (9.7), we get:

This graph-like diagram is then a representation of the post-selected measurement pattern, where all the measurement outcomes are the ones we wanted to get.

It turns out the converse is also true: any graph-like diagram can be seen as a post-selected measurement pattern just by unfusing some phases and introducing some identities:

If we were to actually try to run this as a measurement pattern, we would of course usually get some of the ‘wrong’ measurement outcomes.

If we wanted to implement this graph-like diagram in the one-way model, we could simply repeat this computation many times until we got the outcomes we wanted. However, the probability of this happening gets exponentially small in the number of measurements, so what would be even better is to come up with a general purpose strategy for finding the corrections we need to implement a given diagram deterministically. Since any quantum circuit can be represented using a graph-like ZX-diagram, this would give us an easy way to implement computations in the circuit model (and more!) using measurement-based quantum computing.

It turns out that it is in general not possible to turn graph-like diagrams into deterministic measurement patterns. 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 pattern. 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.

9.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 turn $\gamma +\pi$ back into $\gamma$:

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 fixed order, so we must make sure that the angles we change only affect measurements taking place after the error we are trying to correct.

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:

We should expect to have no solution for the example above, 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. There is no way we could do such a computation deterministically, so we don’t expect to find a deterministic strategy for implementing it in the one-way model.

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 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$ gets its bit flipped by applying ${\mathbf{\text{flip}}}_v$ for all $v\in g(u)$ precisely when it is connected to an odd number of vertices in $g(u)$. This is because if it is connected an even number of times to vertices in $g(u)$, then it gets its bit flipped an even number of times, so nothing happens. Let’s capture this in a definition.

For $v\in G$, let $N_G(v)$ denote its neighbourhood, i.e. its set of adjacent vertices or neighbours.

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.

By construction, whenever an open graph has gflow, it has a winning strategy for the error correction game we described above. Hence, it supports deterministic computation.

A useful tool for doing gflow calculations is the symmetric difference $A\mathrm{\Delta }B$ of sets. This is the set-theoretic equivalent of XOR: it consists of the set of elements in $A$ or $B$, but not both. For example $\{1,2,3\}\mathrm{\Delta }\{2,3,4\}=\{1,4\}$. This operation is associative and commutative, so just like unions or intersections, we can write the symmetric difference of many sets using index notation. For $I=\{1,\dots ,n\}$,

We will perform many calculations with symmetric difference in the coming sections, so we’ll conclude this section with a little warm-up.

9.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 saw in Definition 9.1.2 that a full description of a measurement pattern requires various pieces of data. The first pieces 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 9.5).

But now comes the more complicated part: we need to describe the measurement angles, and more importantly, how they are affected by the measurement outcomes. We have already done this informally when we discussed how to use gflow to win the measurement correction game from Section 9.2.2, but now we will formalise this.

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 gets negated if it appears in a correction set of some previous measurement that got the ‘wrong’ outcome, or it gets a $\pi$ added to it if it appears in the odd neighbourhood of such a correction set.

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. Note we only need to flip the ${\alpha }_u$ term, because for angles $\pi =-\pi$.

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.

9.2.4 From circuits to measurement patterns

We started out this section with the goal of understanding how we can systematically create measurement patterns 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 patterns 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 9.3 we will prove that some more elaborate ways in which we can change graphs also preserve the existence of a gflow.

9.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).

Intuitively we can focus a gflow because being in ${\text{Odd}}_G(g(u))$ means that a vertex $v$ gains a $Z(\pi )$ phase if $u$ had the wrong measurement outcome. However, as $v$ is measured in the XY-plane, gaining a $Z(\pi )$ phase is also what happens when $v$ itself gets the wrong measurement outcome:

Since we know that we can correct the wrong outcome of $v$, we can push the phase $a_u\pi$ at vertex $v$ to the same correction set as we would’ve pushed $a_v\pi$. Hence, if we add the correction set of $v$ to that of $u$, we see that we no longer have $Z(a_u\pi )$ appearing at $v$, but instead only in the future of $v$. We then repeat this process until the $Z(a_u\pi )$ phase only appears at outputs.

9.3 Optimising deterministic measurement patterns

In the same way as we can think of optimising a circuit in terms of reducing the gate count or reducing the total depth by parallelising gates as much as possible, we can also think of optimising a measurement pattern by removing as many measured qubits as possible, or by reducing the total correction depth, the longest chain of measurements whose measurement angles depend on each other. Another consideration for measurement patterns is that we need to do these optimisations in a way that preserves determinism, and ideally the existence of gflow.

In this section we will show that qubits measured in a Clifford angle $k\frac{\pi }{2}$ are particularly amenable to optimisation in measurement patterns. We will show first that all qubits with a Clifford measurement angle can be measured simultaneously so that the depth of the computation only depends on the number of non-Clifford angles. We will then show that we can in fact remove qubits with a Clifford measurement angle from the pattern all together. This will use the local complementation and pivoting rewrites from Chapter 5. These rewrites allowed us to remove internal spiders from a graph-like diagram and 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. We will show in this section that these rewrites preserve the existence of a gflow, and hence that the pattern remains deterministically realisable.

9.3.1 Parallelising Clifford measurements

We will show here that we can measure all qubits with a Clifford measurement angle simultaneously in a pattern with gflow. But first, since we said above that we can actually remove qubits measured in a Clifford angle from a pattern anyway: why bother? Those rewrites will change the structure of where we have Hadamard edges in the diagram. Hence, if we had carefully constructed our pattern to fit for instance in the cluster state shape of Section 9.1.1, then we would break this shape with these rewrites. The arguments we will use here however do not change anything about the shape of the pattern, and purely make the pattern take less time to execute by parallelising the number of measurements.

So suppose we have some measurement pattern with gflow $(g,\prec )$. Using the results of Section 9.2.5 we may assume this gflow is focussed, and hence no measured qubits are in the odd neighbourhood of a correction set. We wish to show that we can in fact ignore the order of measurement $\prec$ and instead measure each qubit $v$ with ${\alpha }_v=0,\pi ,\frac{\pi }{2},-\frac{\pi }{2}$ simultaneously.

The obstacle we need to overcome to make this work, is that a Clifford vertex $v$ might be in the correction set $g(u)$ of some other vertex $u$. We make a case distinction on the phase of $v$ to see what that means for the linear map the pattern implements. Let’s first suppose ${\alpha }_v=\mathit{k\pi }$:

We see that the needed correction for $u$ is just absorbed in the $\mathit{k\pi }+a_v\pi$ phase without changing anything. Hence, the way we measure $v$ actually doesn’t depend on $u$, and so we are free to measure $v$ before $u$ instead of after. Note that the gflow conditions don’t ‘know’ about this possibility, since a measurement pattern has gflow regardless of the specific measurement angles we choose. In this particular case, when we know that the measurement angle is $0$ or $\pi$, we see that it can absorb any correction, and hence that it doesn’t have to satisfy some of the gflow conditions.

Let’s now consider the other possibility for a Clifford phase: ${\alpha }_v=\pm \frac{\pi }{2}$:

The $X(a_u\pi )$ correction always toggles the measurement phase from ${\alpha }_v$ to ${(-1)}^{a_u}{\alpha }_v$. In this particular case, since the phase is $\pm \frac{\pi }{2}$, flipping it to $\mp \frac{\pi }{2}$ is the same thing as adding a $\pi$ phase to it, so that we see that the needed $X(a_u\pi )$ correction is actually equivalent to a $Z(a_u\pi )$ here. Since this is precisely the correction needed to correct the measurement outcome $a_v\pi$ of $v$ itself, we can push this phase to the correction set $g(v)$. Hence, we don’t need $v$ to correct $u$, we can instead use the correction set $g(v)$. Note that this argument is very similar to the one we used when focussing gflow in Section 9.2.5, but now by making this change we might actually be breaking the gflow conditions. However, because we have just shown that we are preserving the linear map of the pattern, and because $g(v)$ is in the future of $v$ and hence of $u$, this is fine!

This shows that for a single Clifford qubit $v$ we can ignore the dependency on $\prec$ and just measure it whenever we want. In order to do this for all Clifford qubits, we need to make these changes in order of $\prec$, starting with the earliest Clifford vertex and working our way to the end. This is because when the phase is ${\alpha }_v=\pm \frac{\pi }{2}$, we see that we must update each $g(u)$ containing $v$ to $g(u)\mathrm{\Delta }g(v)\mathrm{\Delta }\{v\}$ instead. Because this pushes corrections further into the future, we need to make sure we are not ‘undoing’ work we have done before.

Putting this all together we see that we have shown the following.

We showed this result only in the context of measurement patterns with $\mathit{XY}$-plane measurements. However, such a result also holds when we have measurements in the $YZ$ and $\mathit{XZ}$ planes and 3-plane gflow, which we’ll introduce in Section 9.5, for similar reasons.

9.3.2 Removing Clifford vertices from measurement patterns

Instead of just parallelising all Clifford measurements, we can just remove the Clifford measurements entirely! We will show here that the spider-removing versions of local complementation and pivoting from Chapter 5 can also be thought of as modifications to an open graph in such a way that it preserves the existence of a gflow. Hence, these rewrites can be used to optimise measurement patterns with gflow and result in patterns with fewer measured qubits.

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 9.3.3 and 9.3.6 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: