Chapter 5
Clifford circuits and diagrams

In the previous chapter we saw that there were already a lot of interesting things to say about phase-free ZX-diagrams. However, interesting as they are, because there are no phases, these diagrams don’t allow us to do many cool quantum computing things. In this chapter we will remedy this problem and introduce some phases back into the picture. Instead of immediately allowing all possible phases, we will expand our scope to the Clifford ZX-diagrams. These are ZX-diagrams whose angles are all integer multiples of $\pi ∕2$. At first, this might seem somewhat artificial, but we’ll see that in this special setting, even huge diagrams can always be simplified all the way down to a compact canonical form, called GSLC form. It turns out this reduced diagram only has $O(n)$ spiders in it and $O(n^2)$ wires, where $n$ is the number of qubits. A couple of magical things happen as a consequence. In particular, virtually everything we would want to do with such a diagram is efficient, from computing single matrix elements to comparing two such diagrams for equality. Related to this: any circuit which can be translated into a Clifford ZX-diagram can be efficiently classically simulated. We call such circuits Clifford circuits, and this is (a version of) the famous Gottesman-Knill theorem. Just because we can efficiently reason about Clifford diagrams does not mean they are not useful, far from it! We will see that Clifford diagrams form the backbone in measurement-based quantum computing (Chapter 8) and quantum error correction (Chapter 11). In a standard textbook on quantum computing, Clifford circuits and the technique for efficiently classically simulating them would be introduced in the context of stabiliser theory, a powerful collection of tools based on group-theoretic properties of the Pauli group. These techniques are important and ubiquitous in the quantum information literature, and we’ll go through them in detail in Chapter 6. However, it is interesting to note that we also have a purely graphical bag of tricks based on the ZX-calculus that are extremely useful for working with Clifford circuits, and in fact already suffice to prove the Gottesman-Knill theorem. Thus, in this chapter, we’ll deal with Clifford circuits using just the ZX-calculus.

5.1 Clifford circuits and Clifford ZX-diagrams

In the previous chapter, we established a close correspondence between CNOT circuits and phase-free ZX-diagrams (see Section 4.2). Namely, we saw that any CNOT circuit translates into a phase-free ZX-diagram, and conversely any unitary phase-free ZX-diagram is equal to a CNOT circuit (Theorem 4.2.13). In this chapter we will see that a similar relationship exists if we generalise from only allowing the phase $0$ to allowing phases from the set $\{0,\frac{\pi }{2},\pi ,-\frac{\pi }{2}\}$. On one side of this correspondence, we have the following family of ZX-diagrams.

On the other side, we have a certain family of circuits, which generalises CNOT circuits.

It immediately follows that any Clifford circuit yields a Clifford ZX-diagram (as the Hadamard can be decomposed into a series of $\frac{\pi }{2}$ rotations, see Eq. (3.81)). That any unitary Clifford ZX-diagram can be realised by a Clifford circuit is less obvious, and proving this will in fact be one of the primary goals of this chapter.

5.1.1 Graph-like diagrams

When dealing with phase-free diagrams it turned out to be useful to simplify our diagrams somewhat in order to work more easily with them: we fused all the spiders and got rid of self-loops and double edges to get diagrams that we called two-coloured (Definition 4.2.3). In this chapter it will be useful to introduce a variation on this that allows us to more easily work with Hadamards. This type of diagram only contains Z-spiders. This can be achieved by changing the colour of every X-spider using the Hadamard colour-change rule $(\mathrm{cc})$. We can then cancel all double Hadamards that appear by the $(\mathrm{hh})$ rule and fuse all connected Z-spiders using $(\mathrm{sp})$. In the resulting diagram all connections of spiders will then go via a Hadamard. It will be useful to have a special name and notation for this.

Hadamard edges have a couple of useful properties. First, we only have to deal with at most a single Hadamard edge between a pair of spiders, since any parallel pair of Hadamard edges cancels.

Second, we can always remove a “Hadamard edge self-loop.”

Now let’s give the definition of this special class of diagrams we are interested in.

Every ZX-diagram can be efficiently reduced to an equivalent graph-like diagram.

The reason we call these diagrams graph-like is because they are neatly described by a structure that we call an open graph, a graph with a specified list of inputs and outputs. We will have more to say about open graphs in Chapter 8. For now, let’s just note that we can view each spider in a graph-like diagram as a vertex, and every Hadamard as an edge.

5.1.2 Graph states

A particularly useful subset of graph-like diagrams are the graph states. We can either describe these diagrammatically as a restricted set of graph-like diagrams, or directly as a type of quantum state. We will give the description as a quantum state first. For each simple undirected graph $G=(V,E)$, where $V$ denotes the set of vertices of the graph, and $E$ the set of edges, we can define its corresponding graph state $|G⟩$ as

I.e. we prepare the $\text{|+⋯+⟩}$ state, where the number of qubits is equal to the number of vertices in the graph, and then for every edge in $G$ we apply a CZ gate between the corresponding qubits (recall the CZ from Exercise 2.13). A $\text{|+⟩}$ state as a ZX-diagram is just a phase-free Z-spider with a single output. A CZ gate is a pair of Z-spiders connected via a Hadamard gate:

To go from a graph to a graph state represented as a ZX-diagram is then straightforward:

Here we get the diagram on the right by simply fusing all the spiders together. To go from a graph to the graph state represented as a ZX-diagram we see then that every vertex becomes a phase-free Z-spider with an output attached to it and each edge in the graph becomes a Hadamard edge between the corresponding spiders. With this description in hand we can also define a graph state as a particular type of graph-like diagram (spend some time convincing yourself that this definition is indeed equivalent to the description given above):

Some useful quantum states are not exactly graph states, but are instead merely very close to being a graph state. For instance, the GHZ-state (cf. (3.40)), is not a graph state, but we can construct it by starting with a graph state and then applying some Hadamard gates on a couple of the qubits:

In the context of graph states, we refer to the application of single-qubit unitaries on some of its outputs as local unitaries. Imagine for instance some quantum protocol where we start with a bunch of qubits in one spot, which are then entangled to make a graph state. We then give each of the qubits of this graph state to a different person, who are then allowed to take their qubit very far away from the others. While each of these people can’t change the graph state by applying some operation on multiple qubits at once, they can still modify the qubit they have access to by applying a unitary on just that qubit. Hence why we refer to single-qubit operations as ‘local’. Note furthermore that the operation we had to apply in the case of the GHZ state was not just any unitary but specifically a Clifford unitary. This leads us to our next definition of a useful subclass of states and ZX-diagrams.

We will often say a ZX-diagram is in GSLC form or (at the risk of sounding like the kind of people that say “ATM machine”) that a quantum state is a GSLC state. Every single-qubit Clifford unitary can be written as a composition of three phase gates where the phases are multiples of $\frac{\pi }{2}$ (cf. Exercise 5.1). So an example of a GSLC state would be a composition of the graph state of (5.2) with any $Z(\frac{\pi }{2})$ or $X(\frac{\pi }{2})$ phase gates:

Where here the Hadamard gate on the top qubit is a number of $\frac{\pi }{2}$ phase gates in disguise.

5.2 Simplifying Clifford diagrams

Now that we have all the tools we need, we will see how we can systematically simplify Clifford diagrams. Instead of rewriting arbitrary diagrams, we will work with graph-like diagrams. Thanks to Proposition 5.1.8, we can translate any ZX-diagram into a graph-like one, so we can do this without loss of generality. Because graph-like ZX-diagrams are pretty much just graphs with a bit of extra stuff, we can use some techniques from graph theory to simplify them. Before we do this in the general case, it pays to first look at the special case of GSLC states.

5.2.1 Transforming graph states using local complementation

When looking at a graph state it might seem at first glance that the presence or absence of an edge between two qubits determines whether those qubits are entangled. Considering again the scenario where we have prepared a graph state and sent each of the qubits far away from each other. This might then seem to mean that there is no way in which we can get any more entanglement between these qubits. However, the structure of entanglement in a graph state can be deceiving. It turns out that just applying local Cliffords can greatly affect the connectivity of the underlying graph. For instance, in Eq. (5.3) we saw that we can represent a GHZ state as a graph state with some local Cliffords. Because the GHZ is of course symmetric in all three qubits, that means we can do this in three equivalent ways, and hence the following graph states are all equal up to the application of some local Cliffords:

A natural question is then how we can find out when two graph states can be transformed into each other just using local Clifford operations. One important graph transformation we can do just by using local operations is the local complementation.

To transform a graph state so that its underlying graph is locally complemented about a vertex (i.e. qubit) $u$, we only need to apply a $X(-\frac{\pi }{2})$ gate on $u$, and a $Z(\frac{\pi }{2})$ gate on each of its neighbours:

Here $N(u)$ denotes the neighbourhood of $u$. In the remainder of this section we will prove that (5.4) indeed holds. To do this it will be helpful to introduce the family of fully connected ZX-diagrams.

When we fuse all the spiders in $K_n$ we see that they indeed give totally-connected graphs of Hadamard edges:

Using this definition of $K_n$ we can state the equality that will allow us to do local complementations:

Before we prove this, see Example 5.2.5 for a demonstration of how this is related to doing local complementations. The crucial point is that the introduction of a fully connected graph by Eq. (5.6) makes a parallel Hadamard edge if there was already a Hadamard edge present, which is then subsequently removed by Lemma 5.1.5.

For the proof of Lemma 5.2.4 we will need the following base case.

And now we can prove the general case.

5.2.2 Pivoting

It turns out that it is often useful to not just do a single local complementation, but to do a particular sequence on a pair of connected vertices.

Note that in this definition, the ordering of $u$ and $v$ does not matter.

On a graph, pivoting consists in exchanging $u$ and $v$, and complementing the edges between three particular subsets of the vertices: the common neighbourhood of $u$ and $v$ (i.e. $N_G(u)\cap N_G(v)$), the exclusive neighbourhood of $u$ (i.e. $N_G(u)\setminus (N_G(v)\cup \{v\})$), and exclusive neighbourhood of $v$ (i.e. $N_G(v)\setminus (N_G(u)\cup \{u\})$). Schematically:

As a pivot is just a series of local complementations, it can also be performed on a graph state by the application of a particular set of local Cliffords. Indeed, in terms of ZX-diagrams, we have:

I.e. we can perform a pivot on the graph state by applying a Hadamard to the vertices we pivot along, and applying a Z gate to the vertices in their common neighbourhood.

It turns out we can prove (5.8) more directly by using strong complementarity.

5.2.3 Removing spiders in Clifford diagrams

In Sections 5.2.1 and 5.2.2 we saw that we can apply the graph operations of local complementation and pivoting on graph states by introducing some local Cliffords. It turns out that we can use some variations on these rules to greatly simplify graph-like diagrams. As this chapter deals with Clifford diagrams, we will focus here on the variations that are useful to simplify these diagrams, but later on we will introduce some additional variations that can also simplify generic graph-like diagrams. The rules we introduce in this section all serve to remove one or more spiders from a Clifford diagram. By repeatedly applying these rules we then get smaller and smaller diagrams until there are no longer any spiders to remove using these rules. For these rewrite rules it will be useful to introduce a distinction between two classes of spiders in graph-like diagrams (see also Definition 4.2.5).

Our first simplification rule is based on the local complementation rule (5.6).

In words we can describe this rule as follows: if we have a spider (here marked on the left-hand side by a $\ast$) with a $\pm \frac{\pi }{2}$ phase in a graph-like diagram that is internal, i.e. that is not connected to inputs or outputs but only to other spiders, then we can remove it from the diagram by complementing the connectivity on its neighbourhood and changing some phases. The reason we complement the neighbourhood, is because in Lemma 5.2.9 we get a fully connected graph on the right-hand side, but if there were already edges present between some of the spiders, then the resulting double edges would be removed by Lemma 5.1.5, so that we indeed complement the edges in the neighbourhood. For the remainder of this chapter, when we say we ‘apply’ Lemma 5.2.9 we mean that we apply it from left to right on some chosen vertex, and that we immediately follow it by Lemma 5.1.5 in order to cancel the introduced parallel edges, so that we are still left with a graph-like diagram.

In a Clifford diagram each spider has a phase $k\frac{\pi }{2}$ for some $k\in \mathbb{Z}$. Using the rule above repeatedly on a graph-like Clifford diagram we can remove all internal spiders with a $\pm \frac{\pi }{2}$ phase. Hence, the only internal spiders that remain are those that have a $0$ or $\pi$ phase. Most of these internal spiders can also be removed, by using a variation on the pivot rule (5.8).

Here, the marked spiders on the left-hand side are internal connected spiders with a $0$ or $\pi$ phase. On the right-hand side, these spiders are removed, at the cost of complementing their neighbourhood in the manner described by the pivot rule, and introducing some phases (again, the complementation happens because fully connected bipartite connectivity is introduced, and parallel edges are then removed using Lemma 5.1.5).

5.3 Clifford normal forms

These simplification lemmas allow us to remove many of the spiders in a Clifford diagram. In fact, so many that the resulting types of diagrams deserve to be called normal forms for Clifford diagrams. In this section we will see two types of normal forms. The first is what you get if you just keep applying the local complementation and pivoting simplifications. The second requires an additional type of pivot operation that removes the final internal spiders.

5.3.1 The affine with phases normal form

Lemma 5.2.9 removes those internal spiders with a phase of $\pm \frac{\pi }{2}$ so that if we started with a Clifford diagram, the only phases left on internal spiders are $0$ are $\pi$. Then Lemma 5.2.11 can apply to any remaining internal spider that is connected to at least one other internal spider. Hence, once we are done applying Lemmas 5.2.9 and 5.2.11 on a Clifford diagram the only remaining internal spiders are then those that carry a $0$ or $\pi$ phase and are connected only to boundary spiders. These diagrams turn out to be rather useful, so let’s give them a name.

Our previous summary of the simplification procedure can then be summarised as follows.

In an AP form we have two groups of spiders. We have the boundary spiders and we have the internal spiders. The boundary spiders can be connected to any other spider (via a Hadamard edge) and carry any phase, but the internal spiders are only connected to the boundary spiders and can only have a phase of $0$ or $\pi$.

Thanks to condition 1 of Definition 5.3.1, AP forms don’t treat inputs and outputs differently. Thus, from hence forth we will primarily study states in AP form. Here, we implicitly use the fact that we can treat arbitrary AP form maps as states by ‘bending wires’ to turn inputs into outputs. For example, the map from Example 5.3.3 can be treated as a state as follows:

Why do we call these diagrams ‘affine with phases’? To answer this we need to look at what types of states they encode. There are a couple of different things going on here, so for simplicity we’ll start with just the ‘affine’ part of AP forms then build up to the general case. Recall from Section 4.3.2 that a phase-free X-Z normal forms give us a state defined by a system of linear equations:

Importantly, $S$ is always defined by a homogeneous system of linear equations, meaning the right-hand side of every equation is 0. Equivalently, it is the set of bit vectors $\overrightarrow{x}$ satisfying $M\overrightarrow{x}=0$ for some ${𝔽}_2$-matrix $M$. We can generalise this form by additionally allowing the X spiders to carry $0$ or $\pi$ phases. This gives us almost the same thing, except now $S$ can be defined by an inhomogeneous system of linear equations. Each X spider with a $0$ phase gives us an equation with a $0$ on the right-hand side, whereas an X spider with a $\pi$ phase gives us an equation with a $1$ on the right-hand side. For example:

That is, we get the set of vectors $\overrightarrow{x}$ satisfying $M\overrightarrow{x}=\overrightarrow{b}$ for some fixed matrix $M$ and vector $\overrightarrow{b}$. In the example above, its:

Whereas the set of all solutions to a system of homogeneous linear equations always gives us a linear subspace of ${𝔽}_2^n$, the solutions to an inhomogeneous system will, in general, form an affine subspace. Intuitively, an affine subspace is like a linear subspace that has been shifted away from the origin by some fixed amount.

Just like in the case of linear spaces, we have two equivalent representations for an affine subspace, either in terms of a spanning set of vectors or a system of equations. As before, these correspond to Z-X normal forms and X-Z normal forms, respectively. In both cases, the extra data needed to define an affine space (as opposed to a linear one) is included by introducing $\pi$ phases on to some of the X spiders.

As before, we have decorated spiders with vectors to mean that there is an edge to the $j$-th spider if the $j$-th entry of the associated vector is 1. Note the second row is a general form for (5.11), since ${\overrightarrow{w}}_i^T\overrightarrow{x}$ gives the XOR of the variables $x_j$ for which ${({\overrightarrow{w}}_i)}_j=1$. Equivalently, the vectors ${\overrightarrow{w}}_i$ correspond to the rows in a matrix $M$ such that $A=\{\overrightarrow{x}|M\overrightarrow{x}=\overrightarrow{b}\}$.

If we colour-change the X spiders, we see that we’re most of the way to an AP form:

Hence, if we do not have phases on the outputs or Hadamard edges between them, an AP form can always be described by an affine subspace. For a generic AP form, by spider (un)fusion, we can split off the affine part from the rest, which we’ll call the ‘phase’ part:

The reason for the name is that the ‘phase’ part always forms a diagonal unitary, which means all it will do to the state is introduce some phases on the computational basis states $|\overrightarrow{v}⟩$ from (5.13). By unfusing some spiders, we can see that this phase part is generated by S gates, which introduce $\pi ∕2$ phases to individual outputs, and CZ gates, which introduce Hadamard edges between outputs. We can see that each of these gates affects the phase in a way that depends on the computational basis state:

We can describe the action of unitaries built out of these gates using certain polynomials, called phase polynomials. For example:

Here, each single-qubit gate (i.e. the $S$ gate on the first qubit and the $S^2=Z$ gate on the second) contributes a linear term to $\varphi$, whereas each two-qubit CZ gate contributes a quandratic term, whose coefficient is always even. Note that, even though these polynomials can contain products of variables, they are always linear in each argument individually. For that reason, we call these phase polynomials in multilinear form. In Chapter 7 we will see phase polynomials in XOR-form, and in Chapter 9, we will see how these two forms are related. By applying a diagonal Clifford unitary to an affine state, the phase is applied to each of the terms in the same. So, if we combine the example above with (5.13) we get:

5.3.2 GSLC normal form

In a diagram in AP form there are still some internal spiders. It turns out that we can actually also get rid of these. However this does come at a cost: we must then allow Hadamards on input and output wires, so that the diagram is not what we have defined to be a ’graph-like diagram’. Just as it was useful to define a ‘graph state with local Cliffords’, it will be useful here to define a diagram that is graph-like up to Hadamards on the boundary wires.

Note that a graph-like diagram with Hadamards can be easily transformed into a graph-like diagram by introducing some additional Z-spiders using the $(\mathrm{id})$ rule. So how do we get rid of the final internal spiders in a Clifford diagram? Note that each of those spiders has a $0$ or $\pi$ phase and is only connected to boundary spiders (in particular, it is connected to at least one boundary spider, since otherwise it would just be a floating scalar we can ignore). The first step is to introduce some dummy Hadamards and identity spiders to make this boundary spider into an internal spider:

The diagram is now no longer just graph-like, but graph-like with Hadamards and the spider with the $\gamma$ phase has become internal. Then we make two case distinctions. If $\gamma =0$ or $\pi$, we have an internal pair of $0$/$\pi$ spiders, and we can remove them using the pivot simplification Lemma 5.2.11. If $\gamma =\pm \frac{\pi }{2}$, then we can first remove that spider using the local complementation Lemma 5.2.9. As a result of this, the phase of the spider with the $\mathit{j\pi }$ phase becomes $\mathit{j\pi }\mp \frac{\pi }{2}$ so that its phase is also $\pm \frac{\pi }{2}$. We can then also remove this spider using local complementation. In both cases we see that we can remove both spiders, and hence that we get rid of the original internal spider. Note that in the second case, when $\gamma =\pm \frac{\pi }{2}$, the other spiders it is connected to also gain a $\mp \frac{\pi }{2}$ phase, so that this might also give some additional opportunities to remove internal spiders using local complementation. We can repeat this procedure for any remaining internal spider. This might result in multiple Hadamards appearing on the same input or output wire. In that case we can of course cancel these Hadamards using $(\mathrm{hh})$. Combining the simplifications so far we see that we can hence actually remove all internal spiders in a Clifford diagram. Let’s give a name to such a type of diagram.

As before, GSLC here stands for graph state with local Cliffords. This is a fitting name, because states in GSLC form are graph states with local Cliffords as defined in Definition 5.1.11. Indeed, if we have a state, so a diagram with no inputs, that is in GSLC form, then every spider must be connected to an output, possibly via a Hadamard, so after unfusing the phases on the spiders, we see that it is indeed a graph state followed by some single-qubit Clifford unitaries:

Let’s summarise what we have shown in a proposition.

As a consequence of this, all Clifford states, those states that can be produced from applying a Clifford unitary to $|0\cdots 0⟩$, must be equal to graph states with local Cliffords.

In fact, we have something even stronger: we can apply the Clifford circuit to $|0\cdots 0⟩$, and then also post-select some outputs to be $⟨0|$ (or $⟨1|$, $\text{⟨+|}$ or $\text{⟨−|}$ for that matter), and still have a graph state with local Cliffords.

This means that allowing Z-basis measurements on Clifford states doesn’t give us something more general or powerful: we get exactly the same class of states. Finally, let us write down an equivalence between two different notions of Clifford states.

5.3.3 Normal form for Clifford circuits

In the previous section we saw that if we simplify a Clifford state, that we get a graph state with local Cliffords. What happens if we simplify a Clifford unitary in the same manner? Again, there are no internal spiders in the diagram, so each spider must be connected to at least one input or output. By introducing some dummy spiders we can ensure that each spider is connected to exactly one input or output. The diagram will then look something like the following:

We have possible Hadamards on the inputs and outputs as our reduced diagram is graph-like with Hadamards. Each spider can carry a phase, and each spider is connected to exactly one input or output, so that we have two layers of spiders. There are no further (obvious) restrictions for how the spiders can be connected via Hadamard edges. We will now investigate how we can make diagrams like this look more like circuits. First, note that we can unfuse the phases on both sides so that the Hadamards and the phases form a layer of local Cliffords:

Second, we can unfuse the connections between the spiders in the same layer. This reveals those connections to be CZ gates:

It remains to see what is happening in the middle-part of the diagram. This should become clear once we change the colour of the layer of spiders on the right:

We recognise this middle part of the diagram as a parity normal form (Definition 4.2.2)! So far, all the steps we have done on this GSLC diagram work regardless of whether the diagram is unitary. However, when the diagram is unitary, then this parity normal form must represent a unitary matrix itself, and hence by Proposition 4.2.12, it is equivalent to a CNOT circuit. Summarising this analysis of GSLC unitary diagrams we see that we can represent any Clifford unitary as a particular sequence of gates.

This is really surprising! For one thing, before we started this chapter you might think there are an infinite number of different unitaries you can build from the Hadamard, S and CNOT gate, as you can just make longer and longer circuits, but this result shows that we can always reduce such a long circuit to one consisting of just a few layers of gates. In particular, we need at most a quadratic number of gates in terms of the number of qubits.

We can also conclude another interesting fact from this extraction of a circuit from a GSLC normal form. The simplification procedure to get to this GSLC normal form works for any Clifford ZX-diagram, i.e. any ZX-diagram whose phases are multiples of $\pi ∕2$, not just those coming from a Clifford circuit. If such a diagram happens to be unitary, then we can use the procedure above to transform it into a Clifford circuit. Hence, the following proposition immediately follows.

5.4 Classical simulation of Clifford circuits

In the previous sections we saw that we can use two simple rewrites, local complementation and pivots, to reduce Clifford states to graph states with local Cliffords, and Clifford circuits to a normal form consisting of just a few layers of gates. There is a third class of relevant Clifford diagrams that we can simplify using these rewrite rules: scalars. Recall that a scalar diagram is any ZX-diagram that has no inputs or outputs. The reason we care about scalar diagrams is because they can represent amplitudes of a quantum computation. If we start with the basis state $|0\cdots 0⟩$, then apply a unitary $U$, and finally wish to know the amplitude of the state $U|0\cdots 0⟩$ with respects to some computational basis effect $⟨x_1\cdots x_n|$ we get the scalar $⟨x_1\cdots x_n|U|0\cdots 0⟩$. In our case we are interested in $U$’s that are Clifford unitaries, so that the resulting scalar ZX-diagram is also Clifford. So what happens if we feed a scalar Clifford diagram to the simplification procedure described in Section 5.2? Remember that the procedure allowed us to remove any internal Clifford spider. However, in a scalar Clifford diagram, all spiders are internal and Clifford, so after we are done simplifying there will be no spiders left! The diagram will have been simplified away completely. What does this mean? The empty diagram evaluates to the scalar $1$. However, remember that all our rewrites also introduce some scalar factors, which in the case of Clifford diagrams are always multiples of $1∕\sqrt{2}$ and $e^{i\frac{\pi }{4}}$. So the end result is just a number, which is equal to the amplitude we were calculating. Let’s summarise all this in a proposition.

This is really surprising! Clifford circuits contain essentially all the features we would expect from a quantum computation—entanglement, superpositions, and negative and complex amplitudes—and we can use Clifford circuits to realise many truly quantum protocols such as quantum teleportation or quantum key distribution, and yet, such circuits offer no computational benefit over classical computers. This result is known in the literature as the Gottesman-Knill theorem.

Gottesman-Knill theorem: A Clifford computation can be efficiently classically simulated.

Why is this the case? Well, on the surface we see it’s because we can just rewrite the corresponding diagrams very well. But why is it that we can do that? A hint is given by the affine with phases normal form of Clifford states. Apparently, Clifford circuits can only produce quantum states that are uniform superpositions of computational basis states that are efficiently described by an affine subspace of bit strings. This means there is a limit to how much we can actually use the complex amplitudes and entanglement present in Clifford states. There is for instance no way in which we can iteratively repeat a procedure to slowly add more and more amplitude to certain states like is done in Grover’s algorithm: the amplitudes are always distributed equally.

5.4.1 Simulating Cliffords efficiently

In Proposition 5.4.1 we said we could simulate a Clifford amplitude efficiently, but how efficient are we talking? The entire ‘simulation’ just consists of diagram simplification operations, so the complexity of the method, how expensive it is to actually calculate an amplitude, comes down to how hard it is to find the correct rewrite rule to apply, the number of rewrites we need to do, and how hard these rewrites are to perform. The first two of these questions are easily answered. First, how hard is it to find the correct rewrite rule to apply? Well, local complementation applies to any spider with a $\pm \frac{\pi }{2}$ phase, so we simply have to loop over the spiders of the diagram until we encounter a spider with the correct phase. When we are done doing local complementations, any spider will have a $0$ or $\pi$ phase left, so all the spiders are suitable for a pivot, and we only need to look at any neighbour, so that finding a place where we can apply a rewrite rule is quite trivial in this setting: we can do it anywhere. The second question, how many rewrite rules need to be applied, is also easily answered. Each of the rewrite rules, local complementation and pivoting, removes at least one spider, so that the number of rewrite rules applied is bounded by the number of spiders. Finally, how hard is it actually to change the diagram based on the rewrite rules? We will measure this in terms of the number of elementary graph operations we need to perform: vertex and edge additions or removals. When we do a local complementation, we remove a single vertex, and we toggle the connectivity of all its neighbours. In the worst case, the spider we wish to remove is connected to pretty much all other spiders. In this case we end up changing the connectivity of the entire graph. So if there are $N$ spiders, then this could cost $N^2$ edge additions and removals. A similar cost estimation holds for pivoting: we remove two spiders, and we toggle connectivity between three groups of spiders that could also pretty much encompass the entire graph, so that it also costs $N^2$ graph operations to implement a pivot. So a single simplification costs about $N^2$ elementary graph operations in the worst case, and as we’ve seen, we will need about $N$ rewrite rules to fully simplify the graph, which means we will need $N\cdot N^2=N^3$ graph operations in the worst case. In comparison to this, the cost of finding the right rewrite rules to apply is negligible (adding at most an $O(N)$ cost to the application of every rewrite rule). We can now state a more detailed version of Proposition 5.4.1.

Now, $O(N^3)$ is not too bad, but it does mean that once we start dealing with diagrams with, say, millions, of spiders, that we run into trouble. Can we do better? As it turns out: yes! With a more clever simplification strategy, we can actually obtain a significantly better upper bound. The reason we got this $N^3$ scaling, is because we weren’t telling the simplifier which spiders to target, so that we couldn’t limit the number of wires that end up in the diagram. There is a better strategy that we can use to simplify the diagram, which works when we know that the diagram came from a circuit. The idea is that once we have a GSLC diagram that we can very efficiently ‘absorb’ a Clifford gate and rewrite the whole thing as another GSLC diagram. So suppose we have a Clifford circuit consisting of CZ, Hadamard and $S$ gates (if your circuit contains CNOTs, then these can be converted into CZ gates surrounded by Hadamards). Now when we write this circuit as a ZX-diagram, it will only contain Z-spiders, so that it already looks a bit like a graph-like diagram. However, we will not actually reduce it to graph-like form like we did with our previous simplification algorithm. Instead we will keep the circuit structure intact. Now we will introduce some dummy spiders and Hadamards in order to insert a GSLC form diagram at the start of the circuit:

We will now consume gates one by one from the circuit and absorb them into the GSLC part of the diagram, transforming it into a different GSLC diagram, while not affecting the other parts of the diagram. Depending on the gate and on the specific configuration the GLSC part of the diagram is in, we will need to do different things. The easiest gate to deal with is the Hadamard. This is simply absorbed as part of the GSLC if there is no Hadamard already on that qubit, or cancelled if there is one:

For $S$ gates and CZ gates the situation is more complicated. If there are no Hadamards on the qubits they act on, then we can also absorb them as part of the GSLC:

For the CZ gate, as always, if there was already a Hadamard edge present between the spiders, then we simply toggle the connectivity. Now, if there is a Hadamard in the way then we can’t just fuse the $S$ or CZ gate into the GSLC. Instead, we will need to resort to our old friends, the local complementation and pivot. The reason we can use these, is because if there is a Hadamard in the way, with an $S$ or CZ gate on the right-hand side, then the spider that is part of the GSLC is ‘internal’ in the sense that all its connections are to other spiders via a Hadamard edge. Now, if this spider has a $\pm \frac{\pi }{2}$ phase, this is straightforward enough: we just apply a local complementation on it to remove it. This connects the spider of the $S$ or CZ gate to all the neighbours of this internal spider, so that the $S$ or CZ spider takes its place in the GSLC diagram:

Now, if the spider we wish to remove has a $0$ or $\pi$ phase, then we need to apply a pivot to get rid of it. The spider must be connected to at least one input spider (since the diagram is unitary), so that we can apply the standard non-spider-removing pivot rule of (5.8). The end result is that the output Hadamard disappears, so that the spider of the gate can be fused and become part of the GSLC diagram. Combining these different options we see that we can always absorb a gate into the GSLC portion of the diagram. We can hence simplify the entire circuit into a GSLC diagram.

Crucially, the connectivity change resulting from these local complementations and pivots is now restricted to just the other spiders of the GSLC diagram and the spider corresponding to the gate to be absorbed, instead of potentially involving the entire diagram. Letting $q$ denote the number of qubits, there are $2q$ qubits in the GSLC diagram, so that this requires toggling at most ${(2q)}^2$ edges. We need to do such a rewrite potentially for every gate we absorb, so that the entire simplification costs $O(N{q}^2)$ elementary graph operations where $N$ is the number of gates in the circuit. Compare this to our previous method that required $O(N^3)$ elementary graph operations. The number of gates is generally a lot more than the number of qubits, so this is a significant savings. Indeed, from Proposition 5.3.12 it follows that to represent an arbitrary Clifford unitary we need $O(q^2)$ gates, so taking $N=q^2$ we see that we have improved the complexity from $O(q^6)$ to $O(q^4)$.

5.4.2 Weak vs strong simulation

In the previous sections we discussed how to calculate the amplitude corresponding to observing a particular effect on a Clifford state and we called this ‘simulating’ a Clifford computation. But this is not entirely correct. In order to truly say we are simulating a quantum computation we should be getting the same types of outcomes that we would get when we would actually run the quantum circuit. These outcomes come in the form of measurement samples. Namely, we would prepare a quantum state, execute quantum gates on it, and finally measure each qubit. The outcome is then a bit string specifying which measurement outcome we got for each qubit. By running the experiment many times we will see a particular distribution of bit strings as outcomes. To simulate a quantum computation is then to be able to generate a series of bit strings that have a similar distribution of outcomes.

In this definition ‘suitably close’ can be made exact, but that won’t be necessary for us for now. With what we have seen up to now, it is not obvious how we can actually efficiently weakly simulate Clifford unitaries. We are however quite close to being able to strongly simulate Clifford circuits.

Let’s explain this definition. Recall that a marginal probability distribution is one where we don’t care about the outcome of one or more of the variables of the distribution. For instance, if we have a distribution $P(x_1,x_2,x_3)$ of three variables, then we can marginalise $x_3$ to get the distribution $P(x_1,x_2):={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{x_3}P(x_1,x_2,x_3)$. When $P(x_1,x_2,x_3)$ corresponds to the probabilities of observing particular measurement outcomes in a 3-qubit circuit, then this marginal $P(x_1,x_2)$ tells us the probability of observing $x_1$ on qubit 1 and $x_2$ on qubit 2, when we don’t measure qubit 3 at all. The reason we require the ability to determine any marginal probability in the definition of strong simulation, is that if we can only calculate the non-marginal probabilities, then it will generally take exponential resources to determine marginal probabilities. Consider for instance an $n$-variable distribution $P(x_1,\dots ,x_n)$ of Boolean variables. Then to calculate the marginal $P(x_1)$ we have to sum the values of $n-1$ variables $P(x_1)={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{x_2,\dots ,x_n}P(x_1,x_2,\dots ,x_n)$, and this summation contains $O(2^n)$ terms. Okay, so now that we understand what the definition says, it might be helpful to answer why we call this ‘strong’ simulation as opposed to ‘weak’ simulation. First of all, note that being able to weakly simulate doesn’t seem to easily imply the ability to calculate the value of the probabilities: it might be that some probability $P(x_1,\dots ,x_n)$ is exponentially small (in $n$), and hence we would need to sample at least exponentially many bit strings using weak simulation to get an estimate of its value. But the converse is true: if we can strongly simulate a unitary, then we can also weakly simulate it. To see how to do this, we need to recall the concept of conditional probabilities. A conditional probability distribution tells us the probability of observing some outcome conditional on some other variables taking particular values. For instance $P(x_1,x_2|x_3=1)$, the probability of observing the particular values $x_1$ and $x_2$ given that $x_3=1$, is equal to $P(x_1,x_2,1)∕P(x_3=1)$. Hence, since strong simulation allows us to calculate any marginal probability, we can then also calculate any conditional probability. So how do we use marginal and conditional probabilities to generate a sample bit string $\overrightarrow{y}$ with the correct distribution? We do this by determining the value of each bit of $\overrightarrow{y}$ in turn. First we ask for the probability $p_1=P(x_1=0)$, the marginal probability that we observe qubit 1 to give a value of $0$. We then decide with probability $p_1$ to set $y_1=0$ and otherwise we set $y_1=1$. We then calculate $p_2=P(x_2=0|x_1=y_1)$ and set $y_2=0$ with probability $p_2$ and otherwise $y_2=1$. This means that we have chosen $y_1$ and $y_2$ with probability

which is the correct distribution. We carry on and calculate $p_3=P(x_3=0|x_1=y_1,x_2=y_2)$ and repeat the procedure until we have determined the entire bit string $y_1\cdots y_n$. Repeating the argument of Eq. (5.21) we see that we will have chosen this specific bit string with probability $P(x_1=y_1,x_2=y_2,\dots ,x_n=y_n)$ so that we are indeed sampling correctly from this distribution. To summarise:

• Weak simulation is about sampling correctly from the probability distribution of measurement outcomes we would get if we were to actually run the quantum circuit.
• Strong simulation is about calculating the actual probabilities of observing certain measurement outcomes;
• If we can do strong simulation, then we can do weak simulation.

So how do we actually do strong simulation of Clifford circuits with the ZX-diagram simplification strategies we have discussed in this chapter? Well, we have seen how to calculate an amplitude $⟨x_1\cdots x_n|U|0\cdots 0⟩$ which allows us to calculate a non-marginal probability $P(x_1,\dots ,x_n)=|⟨x_1\cdots x_n|U|0\cdots 0⟩{|}^2$. But how do we calculate a marginal probability? To see this it first helps to expand $P(x_1,\dots ,x_n)$ in a way that allows us to more easily represent it as a diagram. Recall that for a complex number $z$ we have $|z{|}^2=z{z}^{\ast }$ where $z^{\ast }$ is the conjugate. The conjugate of the inner product $⟨x_1\cdots x_n|U|0\cdots 0⟩$ is $⟨0\cdots 0|U^{†}|x_1\cdots x_n⟩$. We can represent each of these by ZX-diagrams, and as they are scalar diagrams, their multiplication is implemented just by putting them next to each other:

We get these scalar factors of $1∕\sqrt{2}$ because the X-spiders only represent $|0⟩$ and $|1⟩$ up to a scalar. Note that these middle pairs of spiders correspond then (up to scalar) to operators $|x_i⟩⟨x_i|$. Now if we want to calculate a marginal probability then this corresponds to a sum of such diagrams where we vary the values of some of the $x_i$. Remember that ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_x|x⟩⟨x|=I$, hence on the diagram we can implement this summation by replacing the middle spiders by an identity wire:

Using this diagrammatic representation of a marginal probability allows to calculate the marginals of a Clifford computation.

Since we can now calculate any marginal probability, we have also found a way to sample measurement outcomes from the Clifford circuit.

It is perhaps a bit unsatisfying that the weak simulation seems to be more expensive than the so-called strong simulation. However, it turns out that there is a smarter way to perform weak simulation of Clifford circuits. To do this, we also need to simplify our unitary $U$ using ZX-calculus rewrites, but now instead of reducing to GSLC form, we want to reduce it to the affine with phases form (AP form) of Section 5.3.1. We can do this with the same order of graph operations as it takes to reduce to GSLC form. We can see this in two ways. Either we first reduce to GSLC form using Proposition 5.4.3, and then we do some final rewrites to reduce it to AP form. Or, we modify the algorithm used in Proposition 5.4.3 so that instead of absorbing gates into a GSLC part of the diagram, we absorb gates into an AP form diagram. We hence have the following.

Recall from Eq. (5.14) that a state in AP form can naturally be written as

for some phase function $f$, parity matrix $A$ and bit string $\overrightarrow{b}$. This state is an equal superposition of those $|\overrightarrow{x}⟩$ for which $A\overrightarrow{x}=\overrightarrow{b}$. Hence, if we measure all the qubits then the outcomes will correspond to one of those bit strings $\overrightarrow{x}$ for which this parity condition $A\overrightarrow{x}=\overrightarrow{b}$ is satisfied (the phase function is irrelevant for the outcomes). So we see that sampling from the distribution of $U$ boils down to being able to uniformly randomly select vectors that satisfy such parity conditions.

Instead of casting this algorithm in terms of Gaussian elimination, we can also view it as a diagram rewriting exercise. In Eq. (5.12) we saw that we can relate the affine part of an AP form diagram, a X-Z normal form, to a different Z-X form:

From this latter type of diagram we can easily read of which computational basis states $|\overrightarrow{x}⟩$ are part of the superposition making it up: each Z-spider represents a basis vector $\overrightarrow{x^j}$ of the kernel of $A$, where $x_i^j$ is $1$ precisely when the Z-spider is connected to output spider $i$. While the spiders give the solution to $A\overrightarrow{x}=\overrightarrow{0}$, the $\pi$ phases on the output transform this into solutions to $A\overrightarrow{x}=\overrightarrow{b}$.

5.5 Completeness of Clifford ZX-diagrams

We have seen in this chapter that we can prove a lot about Clifford circuits using the ZX-calculus, but can we actually prove everything? In the previous chapter we saw that the phase-free ZX-calculus is complete, meaning we can prove all equations between phase-free ZX-diagrams using the rules of the phase-free ZX-calculus. It turns out the same is true for Clifford diagrams, when we use the Clifford rewrite rules. In this section we will adopt the scalar-accurate rewrite rules of Section 3.6.2. We will then show that these rewrite rules are complete for the Clifford fragment, meaning that if we can represent a linear map by a Clifford diagram, then any two ways to do so can be rewritten into one another. We show completeness in two steps. First we study scalar Clifford diagrams and show that these can be reduced to a form that uniquely encodes the number they are equal to. Hence, any two scalars representing the same number are reduced to the same diagram, which shows that we have completeness for these scalar diagrams. Then we show that we can refine the AP normal form so that every Clifford diagram can be reduced to a unique normal form. This means that if two diagrams represent the same linear map, that they will be reduced to the same normal form, and hence we have a path of rewriting from one to the other.

5.5.1 A normal form for scalars

First let’s show that we can correctly deal with scalar Clifford diagrams, so that we are then again free to ignore them. For this we will use the results of Section 3.6.2, and hence we use the rules of Figure 3.0 there. We’ve seen in Proposition 3.6.5 that when the diagram contains a zero scalar , that the entire diagram can be reduced to a simple unique form. Hence, we may assume our scalar diagram is non-zero. Our strategy will be to simplify an arbitrarily complicated scalar Clifford diagram to a diagram that consists of small disconnected bits and pieces that can each be dealt with individually. It is straightforward enough to check that with the rules of Figure 3.0 we can prove all the rules of Figure 3.0 up to some scalar diagrams that contain at most two spiders. Hence, everything we have proven so far using the rules of Figure 3.0 remains true using our scalar-accurate set of rules, except that we might acquire some additional small scalar diagrams. This means that in particular our simplification strategy for Clifford diagrams still works, except for some small modifications. We can still use the local complementation simplification Lemma 5.2.9, but as noted in Remark 5.2.10, now it doesn’t actually remove the spider we complement on. Instead, the spider remains as an unconnected scalar. Hence, if we were to apply this rewrite to an unconnected spider (so where $n=0$ in that lemma), it would not remove the spider. In order for the simplification strategy to work we must then only apply this lemma to spiders with a $\pm \frac{\pi }{2}$ phase that are connected to at least one other spider. The same consideration holds for the pivot simplification Lemma 5.2.11, where we should only apply it if at least one of the spiders being pivoted on is connected to some other spider. In Section 5.4 it was noted that if we apply the simplification strategy to a scalar Clifford diagram, that the entire diagram is simplified away. With our scalar-accurate calculus we see that this now becomes slightly different. We can still remove most connections between spiders, but there will generally be some small scalar subdiagrams left.

Now, if our scalar diagram contains a then it can already be rewritten to a normal form, so let’s assume it does not contain that subdiagram. Then our diagram is a composition of five different types of diagrams. By applying $(s)$ we can ensure that the diagram does not contain both a and a (as they are each others inverses). What other relations hold between these scalars? Using Lemma 3.6.7 we see that there can be at most one subdiagram of and using Lemma 3.6.9 we can make it so that there is at most one spider with a $\pm \frac{\pi }{2}$ phase in our diagram.

This theorem tells us that we can always rewrite any two scalar Clifford ZX-diagrams into one another if they represent the same scalar, since they can both be rewritten into this unique normal form.

5.5.2 A unique normal form for Clifford diagrams

The previous section settled the question of completeness for scalar Clifford diagrams. In this section we will do the same for non-scalar Clifford diagrams. Since the question of scalars is now settled, we will again revert back to not caring about these scalar subdiagrams. As before, we will write $\propto$ when we are denoting an equality up to a non-zero scalar factor. We will just work with states in this section, so diagrams that don’t have any inputs. Once we have completeness for states, completeness for all diagrams follows easily just by bending some wires (like we did in Theorem 4.3.6). What we will show in this section is that we can refine the AP form, rewriting it into something more canonical. We will then show that this reduced normal form is unique. In particular, we will rewrite our diagrams to the following form.

Recall that the first non-zero element in a row of a matrix $A$ in RREF is called a pivot (no relation to the pivot graph rewrite rule). The variable $x_i$ is called a free variable if the $i$th column of $A$ does not contain a pivot, otherwise it is called a bound variable. The utility of looking at the reduced AP-form is the following theorem.

Our goal then will be to show that we can rewrite any Clifford diagram into reduced AP-form. We already know that we can rewrite the diagram to AP form using Proposition 5.3.2. Such a diagram is then fully described (up to scalar) by a parity matrix $A$, a bit string vector $\overrightarrow{b}$ and a phase function $\varphi$. We fully Gaussian eliminate the pair $(A,\overrightarrow{b})$ and do the corresponding transformation on the diagram as in Exercise 5.11, to bring it to RREF. If the Gaussian elimination shows that there is no solution to the affine system, then this corresponds to a scalar X-spider with phase $\pi$ appearing, which is equal to the scalar $0$. In this case, we can bring the diagram to the zero normal form of Proposition 3.6.5. So let’s suppose that this is not the case, and the affine system is not inconsistent. We remove all the zero rows of $A$ (which correspond to scalar spiders). So now each row of $A$ is a linear independent bit string. The affine part of the diagram is then unique. It then remains to show that we can rewrite the phase part so that the phase function $\varphi$ only depends on free variables. To do this it will be useful to introduce some notation. Each of the internal spiders in the diagram defines a parity set $P_j$ containing the spiders it is connected to. Since we have fully reduced the matrix $A$, each $P_j$ contains a pivot spider $p_j\in P_j$ that does not appear in any other parity set. We then need to rewrite the diagram so that the pivot spiders $p_j$ does not interact at all with $\varphi$. This means it must not have any phase, and not be involved with any CZs. First, if a pivot spider has a phase of $\pi$, then this can be pushed to the other spiders of its parity set:

If instead its phase is $\pm \frac{\pi }{2}$ then we can remove it by applying a local complementation type rewrite rule. We start by applying the local complementation Lemma 5.2.9 in reverse:

Here in the last step we also implicitly got rid of the scalar spiders that result after applying the copy rule $(\mathrm{sc})$. Now that all pivot spiders have no more phase, we will remove all the Hadamard edges that pivot spiders are involved in. First, we remove all the Hadamard edges from a pivot to a spider within its own parity set. We can do this by repeating the following rewrite:

After every such rewrite the number of Hadamard edges from a pivot strictly decreases, so that the procedure terminates. Finally, we can use a variation of this rewrite rule to remove Hadamard edges from a pivot to a spider outside its parity set:

Note that this rewrite can introduce new Hadamard edges to the pivot of the other parity set, namely when we apply the rewrite rule to two pivots that are connected to each other. However, the rewrite rule either decreases the total number of edges that are connected to a pivot or it decreases the number of pivots that are connected to each other, so that we can always keep applying it and it will always reduce one of these metrics, so that the procedure does terminate. In the end when we can no longer apply the rewrite rule anywhere, it must mean that there are no Hadamard edges attached to a pivot in the diagram.

We conclude then that we get a diagram in reduced AP form.

You might wonder how these reduced AP forms relate to graph states. We have already seen that we can transform a state in AP form to one in GSLC form by doing some boundary pivots. If the diagram is in reduced AP form, the translation is even simpler: since for every internal spider we have a pivot spider that does not have a phase, it’s Z-spider is actually an identity, and we can do some identity removal and colour change to turn it into a GSLC state:

We see that that every internal spider in AP form translates into a Hadamard on the output of its corresponding pivot in the resulting graph state.

5.6 Summary: What to remember

1..

Clifford circuits are circuits consisting of CNOT, Hadamard and $S$ gates. Clifford states are the quantum states that can be produced by starting with $|0\cdots 0⟩$ and then applying a Clifford circuit to it.

2..

Clifford circuits are represented by ZX-diagrams where all the phases are multiples of $\frac{\pi }{2}$. We call these diagrams Clifford diagrams.

3..

Any Clifford diagram that is unitary can be written as a Clifford circuit.

4..

We can efficiently simplify Clifford diagrams by the graph-theoretic operations of local complementation and pivoting.

5..

This allows us to

a)

reduce each Clifford circuit to a normal-form consisting of just a few layers of Hadamard, $S$, CNOT and CZ gates,

b)

write each Clifford state in the affine with phases form,

c)

write each Clifford state as a graph state with local Cliffords,

d)

efficiently calculate amplitudes of Clifford states,

e)

efficiently calculate marginal probabilities of Clifford states (strong simulation),

f)

efficiently sample measurement outcomes from a Clifford state (weak simulation).

6..

This scalar-accurate set of rewrites of the ZX-calculus is complete for Clifford ZX-diagrams, meaning that any two Clifford diagrams representing the same linear map can be rewritten into each other using these rewrite rules.

7..

This follows from the existence of a unique normal form for Clifford states that we call the reduced AP form.

5.7 References and further reading

Classical simulation Clifford circuits were first shown to be efficiently classically simulable by [113], using what he called the Heisenberg representation, which is now more commonly called the stabiliser representation or stabiliser tableau. We will go into detail on this structure in Chapter 6. Notably, the classical simulation theorem itself appears in this single-author paper by Gottesman as “Knill’s theorem”, crediting Knill with the idea. These days it is called the Gottesman-Knill theorem.

Circuit normal forms The first Clifford circuit synthesis algorithm was given by [1], which produced a circuit with 11 layers of distinct gate types. This was subsequently improved to more compact forms [79, 226, 170]. The shallowest decompositions, at the time of this writing, are due to [171] have a 2-qubit gate depth of $2n+O({\log <!--\; FUNCTION\; APPLICATION\; -->}^{2}n)$.

Graph states with local Cliffords The GSLC form for Clifford ZX diagrams is based on a result by [227], who showed that any stabiliser state, i.e. any state prepared from $|0\dots 0⟩$ using a Clifford circuit, can be expressed as a graph state with local Cliffords. The definition of GSLC form for ZX diagrams is due to [19], who used it to prove completeness of the Clifford ZX calculus. The reduction of an arbitrary diagram to GSLC form is from [88].

Local complementation Local complementation, as a purely graph-theoretic concept, goes back to [158]. It’s relevance to quantum computing originates with [225], who showed that two graph states are equal up to local Cliffords if and only if one graph can be transformed into the other via local complementations. [94] showed that, furthermore, this sequence of local complementations can be found efficiently. The local complementation rule was proved in the ZX-calculus by [90]. A more accessible proof is provided in Ref. [62, Prop. 9.125]. The pivoting rule was introduced for ZX diagrams by [92], where it was used to show completeness of the “real stabiliser” fragment of the ZX-calculus, i.e. for ZX diagrams generated by phase-free spiders and the Hadamard gate. The simplification-versions of local complementation and pivot rules (i.e. the ones that delete spiders) were introduced by [88] to simplify non-Clifford circuits, and with some additional variations on the pivoting rule, they were used in [23] to simplify MBQC patterns (though note that the idea that ’a pivot deletes vertices’ was also present in [178]).

AP normal form The AP form and reduced AP form were introduced in a preprint of this book in 2022 to give, among other things, a simplified proof of Clifford completeness. It first appears in published form in [192] for the case of odd-prime-dimensional qudits. A circuit decomposition for Clifford state preparations, which is closely related to the AP normal form, appears more than ten years earlier, in a classical simulation paper by [226].