Chapter 3
The ZX-Calculus

Now that we have covered the basic concepts of quantum computing, it is time to do some interesting stuff. In the previous chapter we discussed string diagrams and how they can be used to represent linear maps and, in particular, quantum circuits. Actually calculating the linear map they represent is tedious though, and in some cases also (impossibly) hard, as the dimension of the spaces involved scales exponentially in the number of qubits. It would then certainly be nice if we could work directly with string diagrams instead. In this chapter we will introduce the ZX-calculus, a graphical language that works with a particular type of string diagrams we call ZX-diagrams. These ZX-diagrams can represent any quantum computation. In addition, the ZX-calculus gives us rules for manipulating ZX-diagrams. In this way we can prove interesting properties of states, unitaries, projections, or any other linear map between qubits we want, all the while working with diagrams instead of those pesky matrices. In this chapter we will see how to represent quantum circuits as ZX-diagrams, and how to use the basic rules of the ZX-calculus to start proving some interesting things about them. We will just barely be scratching the surface however, as there is much more to be said about the things we can do with the ZX-calculus. In fact, we will be spending the rest of the book doing exactly that!

3.1 ZX-diagrams

3.1.1 Spiders

ZX-diagrams arise as compositions and tensor products of the following basic linear maps:

Z-spiders	X-spiders

These generators are called spiders for no other reason than the fact that they look a bit like spiders when you draw them. Let’s focus on the Z-spider. Most of what we say will also be true of the X-spider, by symmetry. First, note this is actually not just a single map, but a family of linear maps of the form:

where the notation ${\text{(−)}}^{\otimes n}$ means ‘$n$ tensor copies’, e.g.

The number $m$ is the number of input ‘legs’ and the number $n$ is the number of output ‘legs’. These two numbers together are called the arity of a spider. These correspond to the number of qubits which the map takes as input and output, respectively:

where $⟨j{|}^{\otimes m}$ and $|j{⟩}^{\otimes n}$ are the $m$- and $n$-fold tensor products of bras and kets, respectively, and we take the convention that ${\text{(...)}}^{\otimes 0}=1$. Keep in mind that, just like in circuit notation, the ordering of composition is flipped between the picture and the bra-ket expression. For example, wires coming in the left side of the diagram above correspond to bras which actually appear on the right side of the bra-ket expression. That’s why the $m$’s and $n$’s seem to have flipped around in equation (3.1). We can also describe a Z-spider in matrix notation. Start with a $2^n\times 2^m$ matrix of all $0$’s, then add a $1$ to the top-left corner and an $e^{\mathit{i\alpha }}$ to the bottom-right corner:

When $m=n=0$, we’ll get a $2^0\times 2^0=1\times 1$ matrix (i.e. a scalar), so the top-left corner is the bottom-right corner. In that case, the resulting scalar is $1+e^{\mathit{i\alpha }}$:

Unlike quantum gates, Z-spiders can have a different number of inputs from outputs, and hence do not need not be unitary. In fact, they are often not even invertible.

However, when $m=n=1$, Z-spiders are unitary and correspond to the familiar Z-phase gates we met in the previous chapter:

We don’t always write angles on spiders, in which case the ‘default’ angle is assumed to be $0$:

We will call such spiders phase-free. Some familiar quantum states arise out of phase-free Z-spiders when $m=0$. Namely, we obtain (unnormalised) Bell, GHZ, and $n$-fold GHZ states:

To normalise these states, we should multiply both sides in these examples by $\frac{1}{\sqrt{2}}$. We will indicate a scalar multiple of a ZX-diagram just like we would for any other kind of linear map. For example:

Most the time we won’t bother with normalisation unless it really matters. It usually doesn’t. Finally, looking at Z-spiders with a single output leg and $\alpha \in \{0,\pi \}$, we can construct X-basis (a.k.a. “plus” basis) elements $\text{|+⟩}$ and $\text{|−⟩}$, again up to normalisation:

X-spiders are pretty much the same as Z-spiders, but everything is defined relative to the X-basis rather than the Z-basis:

Hence, all of the special cases highlighted above apply equally well to X-spiders, after substituting $0\leftrightarrow +$ and $1\leftrightarrow -$. In particular, when $m=n=1$, the X-spider is unitary and represents the $X$-phase gate:

It will be useful for us to calculate the definition of an X-spider in terms of the Z-basis. This will enable us, for example, to do concrete matrix calculations involving both kinds of spiders, as well as understand some of the interaction properties we’ll meet later in this chapter. We’ll start with the basis states. Note that the Z and the X bases have a symmetric presentation with respect to each other:

Consequently, we can modify (3.3) to get an expression for the two Z-basis states:

Notice that X-spiders are used to construct Z-basis states and vice-versa. This is a common “gotcha” in ZX-calculation: to get basis elements, make sure you use spiders of the opposite colour. Now, let’s calculate the matrix for the special case where $\alpha =0$, $m=2$ and $n=1$:

If we expand the first term in the expression above, we’ll get a sum over all 8 possible combinations of Z-basis elements, times the normalisation factor:

Expanding the second term in (3.7), we get almost the same thing, except we pick up a $-1$ sign whenever there is an odd number of 1’s:

In Eq. (3.7) we add these two terms together, so we see that when we expand them that each term with an odd number of 1’s cancels, while those with an even number add together. We hence have:

We see then that this map is ‘classical’: it sends Z-basis states to Z-basis states. In particular, it maps $|00⟩$ and $|11⟩$ to $|0⟩$, while $|01⟩$ and $|10⟩$ are mapped to $|1⟩$. But this is exactly what the XOR does! So we have $X_2^1[0]|x,y⟩=|x\oplus y⟩$ where $x\oplus y$ is the XOR of the two bits $x,y\in 𝔽2$.

We can generalise this construction to see what any X-spider does on states in the Z-basis. Let’s consider a general X-spider as defined in (3.4). Expanding the first term gives a uniform superposition over all Z-basis elements:

The normalisation factor comes from the fact that we have $m$ copies of $\text{⟨+|}$ and $n$ copies of $\text{|+⟩}$, each of which contribute a $\frac{1}{\sqrt{2}}$, which multiply together. Expanding the second term in (3.4), we again get a sum over all of the Z-basis elements, but with different coefficients inside the sum:

Every term in the sum gets an $e^{\mathit{i\alpha }}$, but when any of the $i$’s or $j$’s is $1$, it also gets a factor of $-1$. Putting the two terms together, we get this expression for an X-spider:

where the coefficients are given by:

Now, that’s a pretty big expression, so let’s try to make some sense out of it. First, note that, whenever the bit string $(i_1,...,i_m,j_1,...,j_n)$ contains an even number of 1’s, this term has a coefficient of $1+e^{\mathit{i\alpha }}$, whereas if it contains an odd number of 1’s, it’s coefficient is $1-e^{\mathit{i\alpha }}$. This can be written succinctly in terms of an XOR as follows:

Here, we used the fact that the XOR of all the elements in the bitstring tells us if there were an even number of 1s or an odd number. For that reason, the XOR of a bunch of bits is sometimes called the parity (where the word “parity” means the property of something being even vs. odd). If we specialise to the case where $\alpha =0$, we get the numbers $2$ and $0$, respectively, in the two cases above. By swallowing the $2$ into the normalisation factor, we can write the coefficients for a phase-free X-spider as follows:

We can think of such spiders as a family of “generalised XOR” maps.

3.1.2 Defining ZX-diagrams

We will now give two equivalent definitions of ZX-diagrams: one that is closely related to quantum circuit notation and the other to tensor networks.

3.1.2.1 ZX-diagrams are “circuits” made of spiders

Just like gates form the building blocks for circuits, Z-spiders and X-spiders form the building blocks for ZX-diagrams, under tensor product and composition. For example:

A ZX-diagram can be built iteratively by composing other ZX-diagrams either horizontally, by connecting the output wires of the first to the input wires of the second, or vertically, simply by ‘stacking’ the diagrams to create the tensor product. The base case of this inductive construction starts with the Z- and X-spiders. To demonstrate how this works, let’s work through an example: we will show how to construct the CNOT gate using a Z- and X-spider. The first ingredient we need is the phase-free Z-spider with 1 input and 2 outputs:

Its matrix has 2 columns and 4 rows. In general, the matrix of a general ZX-diagram with $n$ inputs and $m$ outputs will have $2^n$ columns, and $2^m$ rows. Suppose now that we wish to vertically compose the spider (3.9) with an identity, which has matrix diag$(1,1)$. The way we calculate the result is with the Kronecker product:

Note that we said above that a ZX-diagram is built by composing spiders. We see here that that is not entirely true: we also need some ‘structural’ components like the identity wire. We’ll say a bit more about this later. We calculate the matrix of the other ingredient we need similarly:

Now to make a CNOT we need to horizontally compose these two subdiagrams:

To see that this is indeed a CNOT we calculate its matrix. On the level of the matrix, the horizontal composition of diagrams corresponds to matrix multiplication:

Up to a scalar factor of $\sqrt{2}$ this is indeed the matrix of the CNOT gate. If this matrix calculation business seems tedious: that is precisely why we want to use the ZX-calculus! We will see that many identities which would normally be proven by working with matrices can be replaced with graphical reasoning instead. In Eq. (3.10) we have first the Z-spider and then the X-spider. As we will see later, spiders have many symmetries, and for this reason we can also write the CNOT as first an X-spider and then a Z-spider:

Because it doesn’t matter in which direction the middle wire points, top-left to bottom-right or bottom-left to top-right, we can actually without ambiguity just write the wire vertically:

If we want to view this diagram as being composed of simple pieces via horizontal and vertical composition then we have to pick an orientation for this wire, but generally we can just leave it like it is. As a nice bonus this then matches nicely with the quantum circuit notation for a CNOT gate:

We saw that to construct the diagram for a CNOT we needed to use an identity wire. Note that however we could also write the identity as a spider, since:

To construct arbitrary ZX-diagrams we also need the ability to swap wires, so that we can connect the spiders up however we want. We can also represent a swap just using spiders, by using the standard trick to build it out of three CNOT gates:

Finally, we also need the cup and cap we saw in Section 2.1.7, but again we can construct these using spiders:

For the cap we just make the inputs into outputs instead. Note that Eq. (3.17) is just Eq. (3.15) but with the input bended to be an output. We see then that the “structural generators” of identity, swap, cup and cap can actually be constructed using spiders, so that we can in fact say that a ZX-diagram only consists of spiders. We will however consider these structural pieces as first-class citizens of ZX-diagrams, and not as derived from spiders, since they have useful properties by themselves, which we will see more of in Section 3.1.3.

3.1.2.2 ZX-diagrams are tensor networks

For those readers familiar with tensor networks it might be helpful to note that ZX-diagrams are in fact just tensor networks. Indeed, considering them as tensor networks, our notation matches the standard notion of a graphical tensor network as introduced by Penrose. Considered as a tensor network, each wire in a ZX-diagram corresponds to a 2-dimensional index and a wire between two spiders denotes a tensor contraction. The Z- and X-spiders are then defined as:

where $i_k,j_l$ range over $\{0,1\}$. Note that in both cases, the definition of the spider doesn’t depend on the order of indices nor whether the indices appear in the upper or lower position. Hence, permuting, raising, and lowering indices has no effect on the definition of a spider. For example:

So, unless it is important to distinguish inputs and outputs for some other reason (e.g. to do matrix multiplication in the usual way), we might as well take all indices to be upper indices. This allows us to simplify the expression for the Z-spider to:

When $\alpha =0$, $e^{\mathit{i\alpha }}=1$ so phase-free Z-spiders further simplify to:

This is a generalisation of the Kronecker delta matrix we introduced in Definition 2.1.3 from two indices $i,j$ to any number of indices. The intuition is very much same: a Z-spider ‘forces’ a collection of indices to take the same value by going to 0 whenever they do not. Consider for example the following tensor network involving a single Z-spider and some generic matrix $M$:

We can compute the elements of the tensor $T$ in terms of $M$ as follows:

In the rightmost step, we use a Kronecker-delta-like simplification to replace the sum over multiple indices with a sum over a single index. In fact, when the Z-spider does have a phase, we can do a similar simplification by collapsing all of its summed-over indices into a single index, but we should keep a 1-index Z-spider around to keep track of the phase. Generalising the example above, we have:

which can be written as a tensor contraction and simplified as follows:

X-spiders are defined identically to Z-spiders, except with respect to the X-basis $\text{{|+⟩,|−⟩}}$. For tensor networks it is more convenient to define everything in terms of a single, fixed basis. Hence, we express an X-spider concretely in terms of the Z-basis. We already computed the coefficients of this expression at the end of Section 3.1.1, so we use them here:

Just like the Z-spider, the X-spider treats inputs and outputs identically, so we can permute indices or raise/lower them at will:

Recall that in the previous section, we interpreted a ZX-diagram as a tensor and composition of some linear maps. This required us to make an arbitrary choice of how to “chop up” the diagram. Equivalently, since we now have expressions for spiders as tensors, we can interpret a ZX-diagram directly as a tensor network. For example the ZX-diagram:

can be interpreted as a tensor network as follows. First assign an arbitrary index to each wire, e.g.

then write $D$ as a contraction involving X- and Z-spiders:

Just like for general tensor networks, all of the indices that are not inputs or outputs are summed over. ZX-diagrams are just tensor networks whose basic components are only X-spider and Z-spider tensors. Certainly most of the ways tensor networks are used in the literature allow the component tensors to be any indexed set of complex numbers. A natural question then is: why focus only on spider tensors and not more general components? There are two reasons. First, we don’t lose anything in terms of expressiveness by restricting to spiders. Namely, any linear map on qubits can be constructed from spiders, and hence any tensor network with 2D wires can also be constructed purely out of spider tensors (we will have more to say about this in Section 3.1.7). Second, ZX-diagrams come with an extremely useful set of rewrite rules, the ZX-calculus, that lets us transform and simplify the tensor network itself. If our basic tensors were “black box” collections of numbers, we wouldn’t be able to do this. We’ll first meet these rules in Section 3.2, and we’ll be using them throughout the book.

3.1.3 Symmetries

We noted in the previous section that spiders are very symmetric tensors, and that we were allowed to raise, lower or permute their indices however we wanted. In this section we will see what this looks like graphically. Namely, this translates into some nice interactions between cups and caps, swap, and spiders. The SWAP interacts with spiders the way you would expect. Namely, that you can ‘slide’ a spider along the wires, such as in the equation commuting a CNOT gate through a swap below:

It is possible to write down a set of equations that formally captures this behaviour of ‘sliding through a swap’, but we will not bother with that and instead let your intuition do the work. An important point to note though is that we are not working in a ‘braided’ setting, and hence the swap is self-inverse:

The fact that we can permute the indices in the tensor of a spider corresponds to being able to swap the wires of their inputs or outputs:

These symmetries hold for all phases $\alpha$, for spiders with any number of input and output wires, and for the swapping of any of their inputs or outputs. We can’t just swap the wires among the inputs and outputs: we can also swap an input with an output. We do this using the cup and cap. Just as we can slide spiders along the wires of a swap gate (cf. (3.18)), we can slide a spider along the wires of cups and caps. For instance:

This again works for Z-spiders and X-spiders, with any phase, and with any number of input or output wires:

This might just look like some meaningless bending of wires and that is exactly the point. Spiders treat inputs and outputs in essentially the same way, where the distinction between the two is really just bookkeeping, which we represent in the graphical notation as “bending wires”. As a consequence, ZX-diagrams enjoy a particularly strong version of the principle of Only Connectivity Matters that was introduced in Section 2.1.6. There, we saw that the only relevant data in a string diagram was which inputs were connected to which outputs. For ZX-diagrams, the order and direction of wires connecting to a single spider are irrelevant. Hence, we can treat a ZX-diagram essentially as a labelled, undirected graph with some inputs and outputs. To make more clear the type of freedom this entails, only connectivity matters means that the following ZX-diagrams all represent the same matrix.

That is, any way we can interpret the diagrams above as compositions and tensor products of spiders, swaps, identities, cups, and caps will yield the same matrix simply because the spiders and their connectivity are the same. Note that while we can freely move around the spiders in the diagram, we have to make sure the order of the inputs and outputs of the diagram as a whole stays the same. So for instance, we have:

This works because for instance the top input stays connected to the same Z-spider in both diagrams, and the same for the other output and inputs. However, the following is not equal:

Even though the spiders in both diagrams are still connected in the same way, we see that in the second diagram the first input is connected to the X-spider while it was connected to the Z-spider in the first diagram.

3.1.4 Scalars

In the diagram deformation example given in equation (3.23), the zero-arity X-spider with a $-\frac{\pi }{2}$ phase can be moved completely freely throughout the diagram. This is because a zero-arity spider, or more generally any ZX-diagram with zero inputs and outputs, simply contributes an overall scalar factor. For instance, we have:

For this reason, we call ZX-diagrams with no inputs and no outputs scalar ZX-diagrams. Putting two such diagrams side-by-side corresponds to the tensor product, which for scalars just means multiplication. Note that just by using combinations of the scalar diagrams of (3.26) we can represent any complex number as a scalar ZX-diagram.

When working with ZX-diagrams we will often ignore non-zero scalar factors unless they are relevant to the calculation. This is for the same reason that physicists will sometimes work with unnormalised quantum states: it is simply inconvenient and sometimes unnecessary to know the exact scalar values. Recall that we use the notation $M\propto N$ to mean $M$ and $N$ are equal up to a non-zero scalar factor (see Remark 2.3.1). Because any scalar can be represented by a ZX-diagram, we could work just with ZX-diagrams even if we want to have the correct scalar values. For instance, if we want the scalar-accurate CNOT gate we could write:

However, we will mostly just write the actual number we need instead of the diagram representing the number. So instead of (3.27) we would just write:

3.1.5 Adjoints, transpose and conjugate

There are some useful global operations on ZX-diagrams that correspond to well-known matrix operations. First of all, if we take a ZX-diagram and negate all the phases in the spiders, so that for instance $\frac{\pi }{2}$ is mapped to $-\frac{\pi }{2}\equiv \frac{3\pi }{2}$, and $\pi$ is mapped to $-\pi \equiv \pi$, the matrix of the resulting diagram is the conjugate of the matrix of the original diagram (recall that the conjugate of a complex matrix is the pointwise complex conjugate of each the elements of the matrix). The transpose of a matrix is also easily represented by ZX-diagrams: we use cups and caps to change every input into an output and vice versa.

Note that these ‘crossovers’ of the wires are necessary to ensure that the first input is mapped to the first output, instead of to the last output. If we apply this procedure to the CNOT gate we can verify that the CNOT gate is indeed self-transpose:

Here in the first step we slid the spiders along the wires to the bottom, and in the second step we applied the first yanking equation (2.10). The adjoint of a matrix is constructed by taking the transpose and conjugating the matrix. Hence, the adjoint of a ZX-diagram is constructed by interchanging the inputs and outputs using cups and caps as described above, and then negating all the phases of the spiders in the diagram.

3.1.6 Hadamards

We introduce some special notation for the Hadamard gate:

This ‘Hadamard box’ is the final generator of ZX-diagrams that we will need (although note that we can in fact also define it in terms of spiders if we want to; see Section 3.2.5). By inspecting the matrix of the Hadamard it is easy to check that it is self-transpose:

This means that, just like with the spiders, the orientation of the Hadamard is not important, which is why we are allowed to draw it as a simple box. Also just like with the spiders, we can slide Hadamards along wires as intuition would suggest.

3.1.7 Universality

We have now seen that quite a number of quantum gates and constructions can be represented in the ZX-calculus. This raises the following question: exactly which linear maps can be represented in the ZX-calculus. The answer to this is simple: everything. Here, ‘everything’ means any complex matrix of size $2^n\times 2^m$ for some $n$ and $m$. To see why this is the case, let’s first look at which unitaries we can represent. Eqs. (3.2) and (3.5) show that we can represent $Z$ and $X$ phase gates using spiders. Using the Euler decomposition, any single-qubit unitary can be written as a composition of $Z$ and $X$ phase gates, and hence we can represent any single-qubit unitary as a ZX-diagram. In Eq. (3.14) we additionally saw how to represent the CNOT gate as a ZX-diagram. Note that this equation involves a complex number to get the correct scalar factor, but in Exercise 3.5 we saw how to represent any complex number as a ZX-diagram, so that is no problem. In Section 2.3.5 we recalled that any many-qubit unitary can be written as a circuit of CNOT gates and single-qubit unitaries. Hence, we then know we can write any unitary as a ZX-diagram:

Note that for most unitaries, the diagram we would get when we apply this procedure would be exponentially large, so it would not necessarily be useful to write it as a ZX-diagram. However, we can do it, and that is the important part in this section. Now let’s see which states we can represent as a ZX-diagram. We know we can represent $|0⟩$ using an X-spider (Eq. (3.6)). Hence, by taking tensor products we can represent $|0\cdots 0⟩$. Now if we have any other normalised $n$-qubit state $|\psi ⟩$, there will be some $n$-qubit unitary that maps $|0\cdots 0⟩$ to $|\psi ⟩$ (think back to your linear algebra classes, why is this the case?). We can then write:

So we can represent any normalised state as a ZX-diagram. Since we also have all complex numbers, we can multiply the normalised state by a number to get an unnormalised state. Or, the other way around: if we have an unnormalised state $|\varphi ⟩$ we want to represent, we first use Eq. (3.30) to represent the normalised $\frac{1}{\parallel |\varphi ⟩\parallel }|\varphi ⟩$ as a ZX-diagram, and then compose this with the number $\parallel |\varphi ⟩\parallel$, also represented as a ZX-diagram.

Now finally, let’s see how to represent arbitrary linear maps as diagrams. Suppose we are given some linear map $L$ from $n$ qubits to $m$ qubits. We can transform this into an $(n+m)$-qubit state by the Choi-Jamiołkowski isomorphism:

As this is a state, we know we can represent it as a ZX-diagram!

Here $\lambda$ is a complex number needed to scale the state to the right normalisation. We can now bend back the wires in order to get a diagram for $L$ itself:

We see now that we can indeed represent any linear map between qubits as a ZX-diagram.

We call this property universality. Later on we will also consider various restrictions of ZX-diagrams. We can then also say that this restriction is universal for a given subset of linear maps, if we can represent any linear map from this subset using a ZX-diagram satisfying this restriction. It is important to emphasise again that just because we can represent any linear map using a ZX-diagram, this does not mean that such representations will necessary be ‘nice’. It is an ongoing project to find good representations of useful linear maps in the ZX-calculus. For instance, in Chapter 9 we will introduce a new (derived) generator that allows us to more easily represent Toffoli gates in the ZX-calculus, since the ‘native’ representation as a ZX-diagram is a bit cumbersome.

3.2 The rules of the ZX-calculus

The thing that makes ZX-diagrams so useful, above and beyond plain old tensor networks, is a collection of rewrite rules called the ZX-calculus. These rules enable you to replace a little piece of a ZX-diagram with another, equivalent piece, without changing the linear map represented by the diagram. Let’s look at a simple example, involving a Z-spider from 1 to 2 wires and an X-spider from 2 to 1:

Then, using the fact that:

we can do a little calculation:

and we see that we have found a pair of ZX-diagrams that are equal, up to a scalar:

We won’t see many concrete calculations with bras and kets in this chapter, because once we know a few simple rules, we will be able to apply them graphically to do all the calculations we need to. For example, now that we have equation (3.33), we can use it to derive equations between bigger ZX-diagrams. Here’s one:

Note the scalar factor $\frac{1}{2}$ pops out in front, by linearity. The most commonly-used version of the ZX-calculus, and indeed what is often referred to as the ZX-calculus consists of the following set of rules in Figure 3.0.

We will use these 7 rules quite a bit in the coming pages, so we’ve tried to give them some reasonably easy-to-remember names:

This is sometimes also called the stabiliser or Clifford ZX-calculus, for reasons that will become clear in Section 5.5. Note that some of the rules of Figure 3.0 only hold up to a non-zero scalar. This is fine for most of the book, since we often don’t care about the exact scalar factors. In Section 3.6.2 we discuss rewriting with scalars in more detail, and we present a scalar-accurate version of the rewrites in Figure 3.0. These rules of the ZX-calculus will be our main tool for reasoning about quantum computation in this book, so we better make sure we are all on the same page about them. In the next few subsections we will discuss where each of the rules comes from, and some examples of how you can use them to prove interesting things.

3.2.1 Spider fusion and identity removal

The most fundamental of all the graphical rewrite rules allowed in the ZX-calculus is spider fusion. This says that we can fuse two spiders together when they are of the same colour and connected by one or more wires. When spiders are fused, their phases are added together. In terms of diagrams:

Note that we interpret the numbers $\alpha$ and $\beta$ as phases $e^{\mathit{i\alpha }}$ and $e^{\mathit{i\beta }}$, and hence this addition is assumed to be modulo $2\pi$. Spider fusion can be used to prove many well-known identities of quantum circuits. For instance, that a $Z$-phase gate commutes through the control of a CNOT gate:

Flipping the colours, we can use spider fusion to show that an $X$ gate commutes through the target of a CNOT gate:

That phases add when spiders fuse essentially generalises the observation that two rotations of the Bloch sphere in the same direction add together:

As we have and (cf. (3.6)), we also see that spider fusion proves that applying the Pauli $X$ gate to $|0⟩$ gives $|1⟩$:

An equation like $Z|-⟩=|+⟩$ is given similarly:

Note here that we have $\pi +\pi =2\pi \equiv 0$. The following rewrite rule we already saw in Eq. (3.15):

We call this rule identity removal. This rule can be interpreted in several ways. Considering a 1-input 1-output spider as a phase gate over either the Z- or X-axis, this rule says that a rotation by 0 degrees does nothing. Combining it with spider fusion it says that the inverse of a rotation by $\alpha$ is a rotation by $-\alpha$:

Composing the diagrams of (3.38) with a cup it says we can make a Bell state by either taking a maximally entangled state over the Z basis or over the X basis:

Identity removal also allows us to get rid of self-loops on spiders:

Here in the first step we applied the rule in reverse to add an identity. Then we fused the two spiders that are now connected by two wires using the spider fusion rule.

3.2.2 The copy rule and $\pi$-commutation

The second set of rules of the ZX-calculus we will look at concerns the interaction of the Pauli X and Z gates and their eigenstates $|0⟩,|1⟩,|+⟩,|-⟩$ with the spiders. Recall from Eqs. (3.3) and (3.6) that:

The spider fusion rule already covers the interaction of a couple of these maps and states. Indeed we can use the spider fusion rule to show that a Z gate commutes through a Z-spider:

Spider fusion also shows what happens when a $\text{|+⟩}$ or $\text{|−⟩}$ state is applied to a Z-spider:

By flipping all the colours we then also know that an X gate commutes through an X spider and that the $|0⟩$ and $|1⟩$ fuse into an X spider. A more interesting question is what happens to an X gate when it encounters a Z-spider (or vice versa, a Z gate that encounters an X-spider). Consider a Z-spider with just a single input and no phase. Its linear operator is then given by $|0\cdots 0⟩⟨0|+|1\cdots 1⟩⟨1|$. Hence, if we apply an X gate to the input the resulting linear operator is

as an X gate interchanges $|0⟩$ and $|1⟩$. This is easily seen to be equivalent to a Z-spider followed by an X gate on each of the outputs:

Hence, in terms of diagrams, we have:

We will refer to this as the $\pi$-copy rule. By applying the appropriate cups and caps we see that such a $\pi$-copy rule continues to hold regardless of how many inputs and outputs the spider has. But what about when the spider has a non-zero phase? Using spider fusion in reverse to unfuse the phase we can reduce this to a simpler question:

Hence, we need to resolve what happens when we apply an X gate to a $|0⟩+e^{\mathit{i\alpha }}|1⟩$ state:

Ignoring the global phase $e^{\mathit{i\alpha }}$ we can write this in terms of a diagram:

The most generic case, together with its colour-flipped counterpart is then:

With this rule we can also see what happens if there are already multiple $\pi$ phases present:

We see then that the position of the $\pi$’s on the wires of the spider gets toggled. Similar copy rules hold for the eigenstates of the X and Z operators. Indeed, applying a $|0⟩$ to the 1-input Z-spider $|0\cdots 0⟩⟨0|+e^{\mathit{i\alpha }}|1\cdots 1⟩⟨1|$ it is clear that we get the output $|0\cdots 0⟩$:

The same works for $|1⟩$ (although we then do get a global phase of $e^{\mathit{i\alpha }}$ that we will ignore):

By introducing a Boolean variable $a$ that is either $0$ or $1$ we can represent the last two equations as a single parametrised equation:

Here the $\mathit{a\pi }$ phase is either zero (when $a=0$), or $\pi$ (when $a=1$), and hence the input represents the $Z$-basis state $|a⟩$ (being either $|0⟩$ or $|1⟩$). As before, the same equation but with the colours flipped also continues to hold, which gives rules for copying $\text{|+⟩}$ and $\text{|−⟩}$ states through X-spiders. We will refer to all these rules as state-copy rules. These state-copy rules only hold when the spider being copied has a phase of $0$ or $\pi$. For any other phase the analogue of (3.48) does not hold, nor would we expect it to! Quantum theory famously does not allow you to clone arbitrary states. Note here the important quantifier of ‘arbitrary’. The reason that a Z-spider can act as a cloning process for the $|0⟩$ and $|1⟩$ states is because they are orthogonal. It does not clone any other state. Note that the orientation of the wires in the rewrite rules we have derived is irrelevant, as we can pre-compose and post-compose each rule with ‘cups and caps’ to change inputs to outputs and vice versa. For instance, for the ‘reverse’ of the state-copy rule:

These copy rules all deal with the Pauli $Z$ and $X$ and their eigenstates. We can prove similar copy rules for the Pauli $Y$ and its eigenstates, since we could also define a Y-spider as mentioned in Remark 3.1.1. In particular, we will find a way to write the $Y$ eigenstates in Exercise 3.15.

3.2.3 Colour changing

As has been noted several times in the preceding sections, when we have derived some rule in the ZX-calculus, an analogous rule with the colours interchanged also holds. This follows from the rules concerning the Hadamard gate:

The first of these rules states that the Hadamard gate is self-inverse, while the second says that commuting a Hadamard through a spider changes its colour (reflecting the fact that the Hadamard interchanges the eigenbasis of the Pauli $Z$ and $X$). Note that the Hadamard commutation rule also holds for spiders that have no inputs, so for instance:

Let us give an example to demonstrate how the two Hadamard rules (3.50) imply the colour-inverse of any other rule we have. For instance, suppose we want to prove the colour-inverse of Eq. (3.41):

We start with the left-hand side of the colour-swapped version, and then insert two Hadamards on the input by applying the self-inverse rule in reverse:

We then commute one of the Hadamards all the way to the outputs:

We now see the left-hand side of the original (not colour-swapped) equation (3.52), and hence we can apply it:

Now it remains to commute the Hadamards back to the left, and to cancel the resulting double Hadamard:

We have hence succeeded in proving the colour-inverse of Eq. (3.52):

Using the Hadamard commutation rule we can also prove that surrounding a spider with Hadamards changes its colour:

In Exercise (2.13) we saw a circuit for building the CZ gate using a CNOT and Hadamards. We can translate this circuit to a ZX-diagram and then simplify it using the Hadamard rules:

We see that the diagram we get looks symmetrically on the control and target qubit. This is because a CZ gate is acting symmetrically on its two qubits. I.e. we have $\text{SWAP}\circ \text{CZ}\circ \text{SWAP}=\text{CZ}$. So here the ZX-diagram directly reflects a useful property the unitary has.

3.2.4 Strong complementarity

The previous sets of rules all have a very distinct topologically intuitive character: spider fusion allows you to fuse adjacent spiders of the same colour; identity removal and the Hadamard self-inverse rule allow you to remove certain vertices; the $\pi$-copy, state-copy and colour-change rule allow you to commute certain generators through spiders by copying them to the other side. It is therefore relatively easy (after you gain some practice) to spot where they can be applied and what the effect of their application will be on the structure of the rest of the diagram. The last major rule of the ZX-calculus takes more time to work with intuitively, although it does correspond to a natural and crucial property of the interaction of the Z- and X-spider.

3.2.4.1 Bialgebras, CNOTs and SWAPs

Before we introduce the rule, let us give some motivation. Treating the $|0⟩$ and $|1⟩$ states as Boolean bits, we can view the phase-free 1-input, $n$-output Z-spider as the COPY gate that copies the bit $0$ to $0\cdots 0$ and the bit $1$ to $1\cdots 1$. Indeed, this is exactly what Eq. (3.48) states. Analogously, we can view the phase-free 2-input, 1-output X-spider as the XOR gate:

We already saw this in matrix form in Eq. (3.8), but we can also prove it using spider fusion and the fact that $2\pi \equiv 0$. The XOR gate and the COPY gate have a natural commutation relation: first XORing bits, and then copying the outcome is the same as first copying each of the bits and then XORing the resulting pairs:

This equation says that the XOR algebra and the COPY coalgebra together form a bialgebra. This is why the analogous equation in the ZX-calculus is often called the bialgebra rule:

However, for reasons we will explain below, we will refer to this rule as (a special case of) strong complementarity. This rule is essential to many proofs in the ZX-calculus. As a demonstration of its utility, let us prove a variation on the well-known ‘three CNOTs make a swap’ circuit identity. We will start with a circuit containing two CNOT gates, and deform it to make clear where we can apply the rule:

We then see that we can apply Eq. (3.56) in reverse, and then deform the diagram again to bring it into a simpler form:

We could have done all this without the diagram deformation, as the rewrite rules apply regardless of the orientation of the inputs and outputs. The circuit equality is then given in a single step by an application of Eq. (3.56):

We can see this as another interpretation of strong complementarity: it relates CNOT gates to the SWAP gate.

3.2.4.2 Complementarity

We called Eq. (3.59) a version of ‘three CNOTs make a swap’, but it is of course not the real deal. Let’s actually try to prove the real ‘three CNOTs make a swap’ rule:

Here in the last step we simply pushed the spiders of the first CNOT through the wires of the SWAP. To finish the proof it then remains to show that two CNOTs applied in succession cancel each other:

The first step towards doing this might seem clear, namely, we fuse the adjacent spiders of the same colour:

But now we are seemingly stuck. The solution comes from another equation between the Boolean gates XOR and COPY. When we first apply an XOR and then a COPY, we can commute the XOR by essentially ‘copying’ it through the COPY gate. But what happens when we first apply a COPY and then an XOR gate to the two outputs of the COPY:

We see that regardless of the input, we output a $0$. Generalising the notion of an XOR gate to allow for a 0-input XOR gate that just outputs its unit (namely $0$), and a 0-output COPY gate that copies its output zero times (and hence discards it) we can write this relation diagrammatically as:

An algebra (XOR) and a coalgebra (COPY) satisfying this equation are known together as a Hopf algebra. Which is why the following analogous equation between the Z- and X-spider is often called the Hopf rule:

However, we will refer to this rewrite rule as the complementarity rule, because this rule can also be seen as a consequence of the $Z$-basis and $X$-basis defining complementary measurements: having maximal information about the outcome of a $Z$ measurement on a state $|\psi ⟩$ (namely, we will obtain precisely 1 outcome with probability 1) entails minimal information about the outcome of an $X$ measurement (namely, we will obtain any outcome with equal probability). Writing $Z:=\{|0⟩,|1⟩\}$ and $X:=\{|+⟩,|-⟩\}$ for the Z- and X-eigenbases, we can see that they are mutually unbiased:

It turns out that complementarity can be derived from strong complementarity using some clever deformation of the diagram and the rules from the previous sections:

In this derivation, we first deformed the diagram, then we introduced identities, we unfused some spiders, applied the strong complementarity rule, copied a state twice, and in the last equation we removed the dangling scalar diagram as it just introduces some scalar factor. The complementarity rule is exceedingly useful. Indeed, combining it with some spider fusion we can use it to show that we can always cancel pairs of connections between spiders of opposite colours:

So if two spiders of opposite colour are connected by $n$ wires, then this can be reduced to $\mathit{n }\text{mod} 2$ wires. In particular, we can finish the proof that 2 CNOTs cancel each other out, and thus that 3 CNOTs make a SWAP:

3.2.4.3 General strong complementarity

We can extend equation (3.56) to spiders of arbitrary arity to obtain the full strong complementarity rule:

That is, for any two connected phase-free spiders of different colours we can apply strong complementarity, resulting in a fully connected bipartite graph as on the right-hand side. For $n=m=2$ this is exactly Eq. (3.56). For $n=1$ or $m=1$ this follows in a trivial manner by adding and removing identities (cf. Eq. (3.38)). When $n=0$ or $m=0$ this is just the state-copy rule, i.e. (the colour-swapped) Eq. (3.46). Now suppose $n=2$ and $m=3$, we will show how to derive its strong complementarity rule using just spider fusion and the $n=2,m=2$ version of the rule:

There are two common mistakes people make when using the strong complementarity rule. The first is that the rule (3.56) only works when the phases on the spiders are zero. When the phases are $\pi$ a modification is possible by combining it with the $\pi$-copy rules (3.44):

But when one of the spiders contains some arbitrary phase $\alpha$, the result will be more complicated:

The additional bit of diagram we get is called a phase gadget. We will have a lot more to say about phase gadgets in Chapter 7. The second common mistake is that people apply the rule (3.56) from right-to-left without paying attention to how many outputs the spiders have, wrongfully equating the following diagrams:

The correct way to apply strong complementarity here is to first unfuse the spider:

3.2.4.4 Strong complementarity as spider pushing

Because strong complementarity is one of the most useful rewrite rules, but also the hardest one to see when to use, we want to share one more perspective on what it means topologically. Recall that we can push a $\pi$ phase of the opposite colour through a spider:

Note that this is actually two equations, since it holds for both $a=0$ and $a=1$. Let’s see if we can’t compress this into just a single equation. To do this, we will unfuse the $\mathit{a\pi }$ phases and reduce them to just a single instance, by applying the copy rule (3.48) in reverse:

Now let’s compare this again to the left-hand side of Eq. (3.75), where we also unfuse the $\mathit{a\pi }$ phase onto its own spider:

Now we have an equation which holds for $a=0$ and $a=1$, where the phase $\mathit{a\pi }$ occurs in the same position: as an input to the first qubit. We can then see this as an equation of linear maps where we input a specific state into the top input. But these states are respectively $|0⟩$ and $|1⟩$ (up to a scalar factor). This means that this equation holds for a basis of the qubit! But then the linear maps themselves need to be equal regardless of the state that we input. We hence get:

But we recognise this as an instance of strong complementarity! This then gives us another perspective on strong complementarity: it is a ‘controlled’ version of the $\pi$ pushing we saw before, where we don’t have to specify what the phase is we want to push. We instead just leave the wire open.

Using this realisation of ‘strong complementarity as controlled $\pi$ pushing’, we can give a nice visual intuition to what happens when you apply strong complementarity:

Here we added an additional Z-spider the X-spider is connected to at the start to make it look a little more intuitive. We see then that in the same way that for $\pi$ pushing, the $\pi$ appears on all the other legs of the spider, with strong complementarity the X-spider also appears on all the other legs of the Z-spider.

3.2.5 Euler decomposition

The final rule of the ZX-calculus we need to introduce is a way to write the Hadamard in terms of spiders. Recall that any single-qubit unitary gate is equal (up to global phase) to a Z-rotation followed by an X-rotation, followed once again by a Z-rotation:

This is then of course also true for the Hadamard. In particular for $\alpha =\beta =\gamma =\frac{\pi }{2}$:

Here we have included the correct global phase for good measure. This Euler decomposition is just one possible way to write the Hadamard in terms of spiders. There is in fact an entire family of representations that will also be useful to note:

By including the rule (3.81) it looks like we are creating an asymmetry in the phases in the rules of Figure 3.0 with special significance being given to $\frac{\pi }{2}$ over $-\frac{\pi }{2}$. However, (3.82) shows that the situation is still fully symmetric. In particular, all the rules still hold when we flip the value of all phases from $\alpha$ to $-\alpha$. In particular we have the following ‘meta-rule’.

Such ‘flipping of the phases’ corresponds to taking the complex conjugate of the linear map the diagram represents.

3.3 ZX in action

Now that we have seen all the rules of the ZX-calculus, let’s see what we can do with them! In the previous section we have already seen a couple of small use-cases: simplifying a circuit to verify that it implements the correct state in Example 3.2.1, or pushing $\pi$ phases through a circuit to see where it maps Pauli gates in Example 3.2.2. Here we will give several more small examples that demonstrate the use of the ZX-calculus in reasoning about quantum computing. This will also demonstrate several best practices when trying to simplify a diagram using the ZX-calculus.

3.3.1 Magic state injection

The following circuit implements the well-known magic state injection protocol, where a $|T⟩:=|0⟩+e^{\mathit{i\pi }∕4}|1⟩$ magic state is pushed onto a qubit using a measurement and potential correction:

Here the double wire represents a classical measurement outcome being fed forward into the $S$ gate, so that the $S$ gate is only applied if the measurement outcome corresponded to $⟨1|$. We can represent this in the ZX-calculus by introducing a Boolean variable $a$ to represent the measurement outcome. We can then easily prove its correctness:

Most of this proof is spider (un)fusion, but there are a couple of interesting bits. The step labelled $(\pi )$ actually consists of two branches, because if $a=0$, then the X-spider can be removed using $(\mathrm{id})$ so that the phase on the Z-spider remains $\frac{\pi }{4}$, while if $a=1$, then $(\pi )$ is indeed applied, and the phase flips to $-\frac{\pi }{4}$. Combining these two branches we see that the phase becomes ${(-1)}^a\frac{\pi }{4}$. In the step after that we make the observation that ${(-1)}^a\frac{\pi }{4}=\frac{\pi }{4}-a\frac{\pi }{2}$. The usage of a variable to denote a measurement outcome is an easy way to deal with circuits that contain measurements and classically-controlled gates. While it is easy to use, it does have the drawback that it is less clear in which direction the information is ‘flowing’. Here $\mathit{a\pi }$ is the result of a measurement outcome that we don’t have control over, while $a\frac{\pi }{2}$ denotes a $\frac{\pi }{2}$ phase gate that we only apply when we saw the measurement outcome $a=1$. For more complicated scenario’s where we do care about showing this causality more clearly we could adopt a variant of the ZX-calculus where we allow both classical and quantum wires to exist. We will however not need this additional machinery in this book.

3.3.2 Teleportation

The standard state-teleportation protocol consists of two parties, Alice and Bob, that share a maximally entangled state $|00⟩+|11⟩$. Alice does some quantum operations, measures her states, sends the classical measurement outcomes to Bob, and Bob does some quantum corrections based on those outcomes. At the end Bob has the state that Alice started out with. We can represent this as a quantum circuit as follows:

Here the $|\mathrm{\Psi }⟩$ label is to denote that the bottom two qubits start in the maximally entangled Bell state. By representing the measurement outcomes by Boolean variables $a$ and $b$ we can again represent this in the ZX-calculus and prove the correctness of the protocol:

Here we used the fact that $2\mathit{b\pi }$ is either $2\pi$ or $0$ which are both $0$ modulo $2\pi$, and hence the spider can be removed using $(\mathrm{id})$. We see that we end up with a wire going directly from Alice and Bob. Hence, whatever state Alice puts in her qubit wire will end up at Bob.

3.3.3 Detecting entanglement

Let us now do a more involved calculation with the ZX-calculus, demonstrating how one goes about systematically simplifying a diagram. Suppose you are given the following (somewhat randomly chosen) quantum circuit:

Suppose further that you wish to know which qubits are entangled after applying this circuit. Calculating the state directly gives

While a trained eye might be able to spot that the 2nd qubit is unentangled, and that the remainder form a GHZ-state, at first glance this is altogether not obvious. Instead, let’s simplify this same circuit in the ZX-calculus and see where this gets us. In this simplification we have a step marked (*) which will be explained after.

If you don’t stare at diagrams for a living like we do, it might not necessarily be clear what is happening here, but we are in fact following a simple algorithm. Most of the steps follow the general pattern that we always try to fuse spiders of the same colours with $(\mathrm{sp})$ (though we don’t do that here for all spiders at the same time to prevent cluttering), always remove identities with $(\mathrm{id})$, always copy states through spiders with $(\mathrm{sc})$, and always remove parallel wires between spiders of opposite colours using the Hopf rule (3.64). Hadamards are moved out of the way with $(\mathrm{cc})$ when no other obvious move is available. Additionally we have used the rewrites of Eq. (3.83) and (3.84). We have marked one rewrite by (*), this is just an application of the Euler decomposition rule:

This equation is an example of how a series of Clifford phase gates can often be combined together into a simpler series of phase gates. We will have a lot more to say about Clifford gates in Chapter 5. The size of the circuit (3.87) is nearing the limit of what is still comfortable to rewrite manually. In fact, we used some software to verify and help with the rewriting here: the algorithm we just described is easily implemented, so that the entire simplification can be automated. We presented the derivation here in detail to show how one would go about systematically simplifying a ZX-diagram. We will look at more detailed approaches to simplifying diagrams in other chapters.

3.3.4 The Bernstein-Vazirani algorithm

Back in Section 2.4, we introduced the Bernstein-Vazirani algorithm, as a simple example where a quantum computer gets a modest advantage over a classical computer. Namely, one can extract a secret piece of information from an unknown function $f$ on $n$ bits using just a single quantum query to the function (i.e. one use of the unitary oracle $U_f$), rather than $n$ classical queries. Here is the problem, stated formally: Given: a function $f:{𝔽}_2^n\to {𝔽}_2$ such that there exists a fixed bitstring $\overrightarrow{s}$ such that $f(\overrightarrow{x})=\overrightarrow{s}\cdot \overrightarrow{x}$. Find: $\overrightarrow{s}\in {𝔽}_2^n$. We saw that the quantum algorithm for solving this problem is very simple. If we simply perform the following circuit:

we obtain the bitstring $\overrightarrow{s}$ as the measurement outcomes. We gave a proof using bra-ket calculations in Section 2.4. We’ll now give a different proof using the ZX calculus. This follows almost immediately from finding a nice diagram to capture the oracle $U_f$. We claim that $U_f$ can be written as follows:

where the labels on the wires mean there is an edge connecting the Z spider on the $i$-th qubit to the one X spider if and only if $s_i=1$. This works because, as we saw in Section 3.1.1, the X dot acts like an XOR on the computational basis. Hence, if we take the XOR of all the bits $x_i$ where $s_i=1$, we get the dot product $\overrightarrow{s}\cdot \overrightarrow{x}$. If we additionally XOR in some other bit $y$, we get $(\overrightarrow{s}\cdot \overrightarrow{x})\oplus y=f(\overrightarrow{x})\oplus y$. Since the Z dot copies computational basis elements, (3.88) does exactly what the Bernstein-Vazirani oracle should do:

Now, let’s see what happens if we plug $|+⟩=H|0⟩$ into the first $n$ qubits and $\text{|−⟩}$ into the last qubit. In Section 3.1.1, we saw that:

Plugging in, we get:

In the first step, the $\pi$-labelled Z spider is copied through the X spider. This will give a $\pi$-labelled Z spider on the last output and anywhere there is a wire to one of the other Z spiders, i.e. whereever $s_i=1$. If we fuse these in, we see that we get a $Z$ gate where $s_i=1$ and identity where $s_i=0$. We can capture this succintly in the middle picture above by writing this as the Z-phase gate $Z[s_i\pi ]$. After the final spider fusion, we can see the state on the first $n$-qubits is an element of the X basis. Hence, if we measure in the X basis (i.e. perform Hadamards then measure in the Z basis), we will obtain the outcome $(s_1,\dots ,s_n)$ with certainty. This completes the correctness proof for the Bernstein-Vazirani algorithm.

3.4 Extracting circuits from ZX-diagrams

We have already seen that ZX-diagrams are a strict superset of circuit notation. That is, if we have a quantum circuit, it is straightforward to translate it into a ZX-diagram. But what about the converse? How do we translate a ZX-diagram back into a circuit? The first thing to note is that ZX-diagrams can represent more types of maps, that aren’t necessarily unitaries or isometries, and hence in general there is no way to turn an arbitrary diagram back into a circuit. But what if you know somehow that the diagram implements a unitary, how do we get a circuit back out? It turns out this is hard enough that we should state it is a proper Problem:

It turns out that Circuit Extraction is a “Hard with a capital H” problem in the complexity-theory sense, which you will be asked to prove in Exercise* 7.8. Nevertheless, if we impose some restrictions on a ZX diagram, the problem becomes much easier. In this section we will show how diagrams we call circuit-like can be made back into circuits.

3.4.1 ZX-diagrams to circuits with post-selection

First, it’s worth noting that obtaining a circuit with post-selection is relatively straightforward. A generic ZX-diagram can be constructed using the following 5 things:

We can see this by transforming each X-spider into a Z-spider using $(\mathrm{cc})$, and then unfusing spiders until they all have at most 3 legs. We can interpret each of these generators as circuit fragments:

where the first two require ancilla qubits in the states $|0⟩$ and $\text{|+⟩}$ and the second two require post-selection onto $⟨0|$ or $\text{⟨+|}$. With this interpretation, there is an evident translation of any ZX-diagram into a post-selected circuit. First ‘unfuse’ the spiders into generators, then interpret them as post-selected circuits, e.g.

It could be that we are happy with this. Indeed any post-selected circuit corresponds to a particular sequence of measurement outcomes. And, if we start with a ZX-diagram that is not equal to zero, the post-selected circuit will also be non-zero, so it corresponds to a computation that is realisable with non-zero probability. However! The probability of getting the diagram we wanted will, in general, becomes exponentially small with the number of post-selections. So that kindof sucks. What would be much better is to turn a ZX-diagram into a computation that can be run deterministically (or at least with high probability) on a quantum computer.

3.4.2 Circuit-like diagrams and optimisation

One of the simplest kinds of ZX diagrams that are easy to extract are the circuit-like diagrams.

While this seems to be pretty much building the property we want directly into the definition, there is (essentially) an equivalent formulation for circuit-like diagrams which is called ZX diagrams with causal flow. We will meet these in Chapter 8 (specifically Section 8.2.4), along with several generalisations that are relevant to circuit optimisation and measurement-based quantum computing. Even though the circuit-like ZX diagrams are a very limited class of diagrams, we can already define a (pretty effective!) quantum circuit optimisation algorithm that never leaves the realm of circuit-like diagrams.

There are a few things that we should show before we are happy with Algorithm 3.4.3. First, we can see that (3.89) is indeed a derived rule. Since this is essentially just an “all-Z” variation on the complementarity rule we met in Section 3.2.4, this is straightforward enough to be an exercise for now.

The second thing we would like to know is that we indeed have a circuit-like ZX diagram by the time we get to step 3. The final thing we need to know is which spiders to unfuse to turn the circuit-like diagram into a circuit. Let’s look at these properties in turn.

Now, let’s see how to actually perform the spider-unfusions necessary to extract a circuit from a circuit-like diagram. It turns out we can actually just do this greedily. Imagine a frontier between the part of the diagram that has been decomposed into CZ, H, and $Z(\alpha )$ gates. We initially start with the frontier on the outputs, and move the frontier toward the inputs, performing spider-unfusions as necessary. For this, we consider three cases:

1..

If an $H$ gate is on the frontier, move it to the circuit part of the diagram.

2..

If a 2-legged Z spider is to the left of the frontier, it can only be an $R_Z[\alpha ]$ gate, so move it to the circuit part.

3..

If two spiders on the frontier are connected via a Hadamard gate, perform spider-unfusion as necessary to produce a CZ gate, and move it to the circuit part.

For circuit-like diagrams, this will never get stuck, and terminates when there are no spiders or Hadamards to the left of the frontier. Proving this is much easier when we have some extra tools in our tool belt (namely the aforemented notion of causal flow, which we introduce in Chapter 8), so we will postpone this proof until then. However, you should know enough at this point to code up a full-fledged circuit optimisation algorithm using the ZX calculus. You can see for yourself how well it works!

3.5 Summary: What to remember

1..

Spiders are a class of linear maps that can have any number of inputs and outputs. They come in two flavours: Z-spiders and X-spiders.

2..

Spiders can be connected together to form ZX-diagrams. Stacking ZX-diagrams correspond to the tensor product of linear maps, and connecting ZX-diagrams corresponds to composition.

3..

ZX-diagrams can be arbitrarily deformed as long as the order of inputs and outputs is preserved.

4..

ZX-diagrams are universal, meaning that they can represent any linear map between any number of qubits.

5..

In particular, any quantum circuit consisting of Z- and X-phase gates and CNOTs can be easily written as a ZX-diagram. Conversely, any ZX-diagram can be written as a post-selected quantum circuit.

6..

The ZX-calculus is a set of graphical rewrite rules for transforming ZX-diagrams while preserving the linear map they represent.

7..

There are 7 rules of the ZX-calculus (see Figure 3.0): spider fusion, colour change, $\pi$-copy, strong complementarity, identity, Hadamard-Hadamard cancellation, and Euler decomposition of the Hadamard.

8..

We can code up a pretty simple yet effective circuit simplification routine by converting all X-spiders to Z-spiders, and applying spider fusions, Hadamard-Hadamard cancellations and Hopf rules (Eq. (3.89)) wherever possible, and then extracting a circuit from this diagram.

3.6 Advanced Material*

3.6.1 Formal rewriting and soundness*

While many of you might be familiar with mathematical rewriting of algebraic expressions, you might be unfamiliar with doing the same with diagrams, and might even be sceptical that what we are doing is even valid mathematics. To ease those worries, we will say a bit more about what is actually going on formally when we rewrite a diagram. The rewrite rules we have given in this chapter are of the form $D_1=D_2$, where $D_1$ and $D_2$ are some ZX-diagrams with the same number of inputs and outputs. We then used these rewrite rules on larger diagrams that contain either $D_1$ or $D_2$ as subdiagrams. This is because when we are asserting $D_1=D_2$, we are actually asserting an entire family of equalities. We are for instance also asserting that $D_1\otimes E=D_2\otimes E$ for any other ZX-diagram $E$, and $D\circ D_1=D\circ D_2$ for any composable ZX-diagram $D$. In a sense we are assuming we have the following implication:

In words: if $D_1$ appears as a subdiagram of some larger ‘ambient’ diagram $D^{\prime }$, then $D_1$ can be replaced by $D_2$ inside of $D^{\prime }$. We are saying we can apply the rewrite rule regardless of the context. An important question to settle here is whether this is sound. A rewrite rule in a language is called sound when it preserves the underlying semantics, i.e. the underlying meaning. In the setting of ZX-diagrams, the language is the set of diagrammatic rewrite rules of the ZX-calculus, and the semantics of a ZX-diagram is the linear map it represents. So a rule in the ZX-calculus is sound when the diagrams on each side of the equation represent the same matrix. For a single equation like $D_1=D_2$ soundness is easy to check: just calculate the matrix on both sides. But how can we be sure that employing this rewrite rule in a larger context as in (3.90) is still sound when we would have to check an infinite family of diagrams? To make the following discussion more clear, we will denote the matrix of a ZX-diagram $D$ by $\mathit{⟦D⟧}$. We can then say a diagrammatic rule $D_1=D_2$ is sound when $⟦D_1⟧=⟦D_2⟧$. By definition of how we calculate the matrix of a ZX-diagram, we have $⟦D_1\otimes D_2⟧=⟦D_1⟧\otimes ⟦D_2⟧$ and $⟦D_1\circ D_2⟧=⟦D_1⟧\circ ⟦D_2⟧$, where this last composition is just matrix multiplication. Hence, if we have $⟦D_1⟧=⟦D_2⟧$, then we also have $⟦D_1\otimes \mathit{E⟧}=⟦D_1⟧\otimes \mathit{⟦E⟧}=⟦D_2⟧\otimes \mathit{⟦E⟧}=⟦D_2\otimes \mathit{E⟧}$, and hence $D_1\otimes E=D_2\otimes E$ is also sound. Similarly we have $⟦D_1\circ \mathit{E⟧}=⟦D_2\circ \mathit{E⟧}$. Since we build any ZX-diagram by iteratively composing and tensoring, this shows that the rewrite rule stays sound regardless of the context it appears in, and hence that the implication in (3.90) is indeed true. Even given this discussion, some of you might still not be happy about this. How can all of this be rigorous mathematics when it is just pictures on a page? Since this is a quantum computing book and not a mathematics book, we won’t give the actual proof that all of this is solid here, and instead we will give a Proof by Fancy Words and point the interested reader to the References of this chapter. So here it comes: the right formal language to think about the ZX-calculus is category theory. In a symmetric monoidal category we can compose morphisms via both horizontal and vertical composition. The coherence theorem then tells us that the coherence isomorphisms of a symmetric monoidal category are enough to prove we can move morphisms around on a page while preserving equality. Because ZX-diagrams have cups and caps they are actually an example of a compact closed category, for which an even stronger coherence theorem is true, so that we can move the generators around the cups and caps as well. The interpretation into linear maps is a strong monoidal functor from ZX-diagrams to the category of complex vector spaces. The rewrite rules can be understood as an equivalence relation which respect composition and tensor product, so that it induces a quotient category of ZX-diagrams modulo equality by rewrite rule. Soundness of the rewrite rules means that the functor into linear maps restricts to this quotient category.

3.6.2 Dealing with scalars*

We have been ignoring non-zero scalar factors in ZX-diagrams in this chapter, and will continue to do so for most of the rest of the book. This is not however because the ZX-calculus is incapable of reasoning about scalars. The opposite in fact: because it is a straightforward exercise to deal with the scalar factors once you know a couple of tricks, it just isn’t worth the effort of including them most of the time. In this section we will see what some of these tricks are. So first, the rule set of Figure 3.0 is not taking into account the actual scalar factors. Instead, we should use a rule set where we do have all the correct scalars. See Figure 3.0.

Most of these rules should look familiar, but there are some perhaps weird-looking things going on. Let’s go through the differences rule by rule. The spider-fusion rule and the colour-change rule are unchanged. We have split up the strong complementarity rule into two parts, a bialgebra rule and a state-copy rule. This is necessary because the scalar factor for strong complementarity depends on the number of inputs and outputs of the diagram. These scalar subdiagrams included in the rules should make more sense once you recall what they are equal to:

The identity-removal rule and the Hadamard cancellation rule are still the same, but we now have chosen for a different Euler decomposition of the Hadamard that does not need a global phase to be accurate. We have replaced the pi-commutation rule for a more minimal one that has now acquired a scalar factor (which corresponds to a global phase of $e^{\mathit{i\alpha }}$). Finally, there are two new rewrite rules. The first rewrite rule $(\mathrm{zo})$ tells us that in the presence of a zero scalar, essentially anything equals each other. For instance, as we will see later, we can use it to show that the identity wire disconnects. The second rule $(s)$ allows us to cancel some scalars. This essentially implements $\sqrt{2}\cdot 1∕\sqrt{2}=1$. Note that the right-hand side is the empty diagram. This rule is in fact necessary: there is no other rewrite rule that can produce an empty diagram, so the equation of $(s)$ can not be proven by any combination of the other rewrite rules. It can also be shown that $(\mathrm{zo})$ is necessary using a more complicated argument. Now in this section we will show two things we can do with scalars. First, we will show that when there is a zero scalar that the entire diagram can be simplified, so that every two diagrams with this scalar in it are the same. Second, we will show that certain scalar diagrams can be ‘multiplied’ together in exactly the way we would expect for their corresponding scalar values. So let’s prove some things about scalar diagrams. In this section, whenever we refer to a rewrite rule like $(\mathrm{sc})$, we are meaning the rewrite rules from Figure 3.0, not Figure 3.0. Note that due to $(\mathrm{cc})$ and $(\mathrm{hh})$ that all the rules also hold with the colours interchanged as usual.

Now we can show that any two diagrams that contain a zero scalar can be rewritten into each other by reducing them a unique normal form. This will require a couple of lemmas.

Now let’s see how we can combine some scalar diagrams by ‘multiplying’ them together.

As a special case, where $\alpha =\beta =\pi$ we can show that $(-\sqrt{2})\cdot (-\sqrt{2})=2$:

Note that when the X-spider does not have a $\pi$ phase, that the phases simply dissappear as in Lemma 3.6.4. We can also simplify some expressions involving . This is because this diagram equals $1+i$, and when we multiply it with itself, for instance, we get $(1+i)(1+i)=2i$, which should be equal to a simpler diagram. In order to prove this, we will need the following scalar-accurate version of Eq. 3.84 in Exercise 3.15.

There is of course more to be said about calculating the values of small scalar ZX-diagrams in this way, but hopefully the reader can see now how this generally can be done. We will use these results on manipulating scalars in Section 5.5 when we prove that the rules of Figure 3.0 are actually enough to prove all equalities concerning ZX-diagrams where the phases are multiples of $\frac{\pi }{2}$.

3.7 References and further reading

Categorical quantum mechanics The ZX-calculus came forth from the field of categorical quantum mechanics, an area of research initiated by [2] that aimed to study quantum phenomena abstractly, using nothing but the structure of symmetric monoidal categories. These are mathematical structures wherein both composition and tensor product make sense [205]: in a category we have composition [165], ‘monoidal’ means that there is a tensor product, and ‘symmetric’ means that we have a SWAP operation. In a ZX-diagram we can’t just swap two inputs, we can also swap an input with an output using cups and caps. A category with this kind of structure is called compact closed [141]. It is in this abstract category theory that it was proven that we can move the generators around on the page while preserving the semantics of the diagram, and hence why it even makes sense to write it as a diagram. The original categorical quantum mechanics paper [2] gave a proof of quantum teleportation that is essentially the basis of the ZX proof in Section 3.3.2.

The origin of the ZX-calculus The ZX-calculus was born on a bus in Iran in 2007. Bob Coecke, a professor at Oxford and Ross Duncan, a recently-finished PhD student, were discussing how to capture a certain feature of quantum measurements using category theory. In particular, they were thinking about mutually unbiased bases (mubs), i.e. sets of bases that pairwise satisfy equation (3.65) from Section 3.2.4.2. While mubs, which were first introduced by [204], are very simple to define, they have a suprisingly rich structure that is still only partially understood. A running joke at the time was, if you wanted to ruin a quantum computer scientist’s career (and personal life), you should just introduce them to the problem of classifying all mubs in dimension 6. Earlier that year, [55] gave a more “categorically flavoured” notion of fixing a measurement, which they called classical objects. These have gone under a variety of names—notably classical structures or dagger-special commutative Frobenius algebras—but these days most people refer to them as spiders. It seemed at the time that these abstract algebraic entities gave the correct notion of fixing an ONB without needing to refer to concrete Hilbert space structure, an intuition that was vindicated in 2013 when Coecke, Pavlovic, and Vicary showed that spiders are in 1-to-1 correspondence with ONBs [56]. By studying two families of spiders satisfying some interaction equations, Coecke and Duncan hoped to get some deeper insights in the behaviour of mubs, and hence the ZX-calculus was born [57]. In fact, it wasn’t called the ZX-calculus until almost three years later [58], with most early talks and papers referring to it as the “calculus of complementary observables”, simply “the graphical calculus”, or even the “Christmas calculus” due to its convention of using green and red dots for Z and X spiders. As the story goes, this convention was born from the fact that black and blue whiteboard markers in the Oxford Computing Laboratory were constantly running out of ink, so the only working ones were green and red.

Strong complementarity The name of strong complementarity for the rule of Section 3.2.4 was introduced in [59], but as noted in that section is also called the bialgebra equation. In fact, the bialgebra of a Z-spider and X-spider we have in the ZX-calculus is a very special case, as both spiders are Frobenius algebras. Two Frobenius algebras that form a bialgebra are called interacting Frobenius algebras. It was shown in [87] that these also form a Hopf algebra, essentially using the proof of Eq. (3.66), and hence that strong complementarity implies regular complementarity.

Completeness The version of the ZX-calculus from [57] was missing the Euler decomposition rule. This rule was introduced by [90], where the authors showed that, without this rule, the ZX-calculus is incomplete for Clifford ZX-diagrams. With this rule, one obtains a version of the ZX-calculus equivalent to the one used in this book, which was shown to be complete for Clifford ZX-diagrams by [19]. That same year, [203] showed that the Clifford ZX-calculus was incomplete for non-Clifford ZX-diagrams, i.e. if we allow angles that are not multiples of $\pi ∕2$. The counter-example, suggested by Kissinger, came from considering the two possible Euler decompositions of a single-qubit unitary:

It is always possible to compute ${\alpha }^{\prime },{\beta }^{\prime },{\gamma }^{\prime }$ as (fairly elaborate) trigonometric functions of $\alpha ,\beta ,\gamma$. When the angles on the LHS are not $\pi ∕2$ multiples, the angles on the RHS are typically irrational multiples of $\pi$, and it is not possible to prove equation (3.95) using just the Clifford ZX rules. This remained the status of completeness for several years, and it seemed like it might even be the case that no finite set of rules would suffice to show completeness for a computationally universal fragment of the ZX-calculus such as Clifford+T ZX-diagrams (with $\pi ∕4$ multiple phases) or all ZX-diagrams (with arbitrary phases). Some smaller results appeared, such as the one-qubit Clifford+T completeness of [20] and the 2-qubit completeness of [63], but it remained unclear how to extend these to $n$ qubits. In fact, Aleks would have bet money in 2015 that no finite, complete set of rules for $n$-qubit Clifford+T ZX-diagrams existed. Picturing Quantum Processes, the precursor to this book, which came out in the spring of 2017, had this problem as an “advanced exercise”, at least partially as a joke. However, it’s a good thing Aleks didn’t bet, because he would have lost his money. In the autumn of 2017, Jeandel, Perdrix, and Vilmart showed a complete ZX-calculus for the Clifford+T fragment [136], and later that same year Wang and Ng showed completeness for all ZX-diagrams [187]. The key idea in these two completeness theorems was to use an encoding into a related graphical calculus called the ZW-calculus, formulated by [53] and proved complete by [121]. While these presentations of the ZX-calculus were complete, they contained some redundancy, in the sense that some rules could be derived from others. A more compact presentation of the Clifford ZX-calculus, consisting just of the spider rules, strong complementarity, Euler, and colour change rules, was given by [24]. Similarly, a small complete set of rules for the full ZX-calculus was given by [229], essentially by adding (3.95) to the basic Clifford rules.

Measurement-based quantum computing Along with understanding the structure of mutually unbiased bases, a lot of the early development into ZX-calculus was motivated by providing a convenient notation for working with the one-way model of measurement-based quantum computation (MBQC), which we’ll discuss extensively in Chapter 8. The representation of cluster states as ZX-diagrams already appeared in the first paper [57] and started to be put to good use in subsequent work relating quantum circuits and measurement patterns [91] and doing ZX-based optimisation of quantum circuits [88].

Resources To some extent, this book grew out of the survey/tutorial paper ZX for the Working Quantum Computer Scientist [222], which presents some of the topics we cover in a more condensed form. A good place to start learning more about ZX is zxcalculus.com, which maintains a tagged list of $>$100 papers on ZX, related calculi, and applications. It also contains information about various communities, online seminars, and mailing lists. The diagrams in this book were typeset with the help of TikZiT, which acts as a GUI for making LaTeX suitable TikZ diagrams. TikZiT was made by Aleks in an effort to make typesetting the 5000 diagrams in his previous book somewhat less horrific, and his current coauthor John is very thankful for its existence.