Chapter 4
CNOT circuits and phase-free ZX-diagrams

ZX-diagrams are a universal language for talking about quantum computing. This makes them useful, but it also means that for generic ZX-diagrams, we expect certain problems to be hard to solve with rewriting. For example, if we could efficiently determine if two different ZX-diagrams describe the same matrix, we can also determine if two quantum circuits actually describe the same unitary. However, we have good, complexity-theoretic reasons to believe that that is way harder than anything even a quantum computer can do (much less a classical one). As a special case, this would let us determine efficiently the complex number described by a diagram with no inputs and outputs, which would let us efficiently simulate quantum computers. This would of course make the whole project of quantum computation (and essentially the jobs of the authors of this book) pointless. Since we don’t believe we can efficiently solve certain problems for any ZX-diagram, it makes sense to restrict to classes of diagrams which can be reasoned about efficiently. The restriction of the ZX-calculus to a family of ZX-diagrams that is closed under composition and tensor product is a fragment of the ZX-calculus. In this chapter we will look in detail at one of the simplest possible fragments of the ZX-calculus: the phase-free ZX-calculus. This fragment concerns ZX-diagrams where all the phases on the spiders are required to be zero, and where we do not have Hadamard gates. The phase-free diagrams turn out to behave very nicely, and we can rewrite them in various fruitful ways. Their nice structure comes from a deep connection with linear algebra over the two-element field ${𝔽}_2$. Whereas quantum theory primarily concerns itself with (exponentially large) matrices whose elements are in $ℂ$, we’ll see in this chapter that a special class of operations can be described in a different way using (much smaller) matrices whose elements are in ${𝔽}_2$. The reason we care about phase-free ZX-diagrams is because such diagrams that are unitary correspond precisely to quantum circuits consisting solely of CNOT gates, so-called CNOT circuits. In this chapter we will explore in detail the relation between CNOT circuits, phase-free ZX-diagrams and linear parity maps.

4.1 CNOT circuits and parity matrices

In this section, we will see that the action of a CNOT circuit on $n$ qubits can be succinctly represented as an $n\times n$ matrix over the field ${𝔽}_2$ and how to translate to and from this representation.

4.1.1 The two-element field and the parity of a bit string

First and foremost: what is ${𝔽}_2$? Let’s give a formal definition.

This may not look much like the fields of numbers you are used to—like the real numbers $ℝ$, complex numbers $ℂ$, or rational numbers $\mathbb{Q}$—but just by thinking about the behaviour of XOR and AND, we can verify all of the field axioms. First off, we can easily see that XOR and AND are both associative, commutative, and have units 0 and 1 respectively:

But what about inverses? In a field, every number $x$ has to have an additive inverse $-x$ satisfying $-x+x=0$. A special property of ${𝔽}_2$ is that every element is its own additive inverse. We have $0+0=0\oplus 0=0$, but also $1+1=1\oplus 1=0$. Furthermore, for ${𝔽}_2$ to be a field, every non-zero number has to have a multiplicative inverse. But here there is only one non-zero number: $1$, and clearly $1\cdot 1=1$. We sometimes refer to an element in ${𝔽}_2$ as a parity. Parity is a property of bit strings: if a bit string contains an even number of 1s, we say it has parity 0, whereas if it contain an odd number of 1s, we say it has parity 1. For a bit string $\overrightarrow{b}=(b_1,\dots ,b_n)$, we can compute the parity by taking the XOR of all of its bits, i.e. we sum up the bits as elements of the field ${𝔽}_2$:

One is often interested not just in the overall parity of a bit string, but also the parity of some subset of bits. This can be computed using simple matrix operations. For example, we can express the operation of computing the parity of the 1st, 3rd, and 4th bits of a 4-bit string as a row vector:

More generally, if we are interested in computing several parities at once, we can arrange them in the rows of a matrix:

By saving or transmitting some parity information about a bit string, we can often detect and correct errors. For example, if the bit $b_2$ got lost in transmission, but we know the values of $b_3$ and $b_2\oplus b_3$, we can recover $b_2$ since $b_2=b_2\oplus b_3\oplus b_3$. Such basic operations are the basis of classical linear error correcting codes, and as we’ll see in Chapter 11, also play a major role in quantum error correction. However, before we get there, we’ll see a much more immediate connection between parity matrices and quantum circuits: the behaviour of a CNOT circuit can be exactly captured by an invertible parity matrix.

4.1.2 From CNOT circuits to parity maps

The CNOT gate acts on a pair of qubits via $|x,y⟩\mapsto |x,x\oplus y⟩$. When we put multiple CNOT gates in a circuit, we can build unitaries that have more complicated actions on the computational basis states. For instance, suppose we have a CNOT from qubit 1 to 2, and then a CNOT from 2 to 1:

We can calculate its action on the computational basis state $|\mathit{xy}⟩$ as:

More generally, we can calculate the action of any CNOT circuit on a computational basis state by labelling each of the input wires with a variable $x_i$, then pushing those variables through the circuit:

That is, we work from left to right. When we encounter a CNOT gate whose input wires are labelled $a$ on the control qubit and $b$ on the target qubit, we copy the label $a$ onto the output wire of the control qubit and write $a\oplus b$ on the output wire of the target qubit. Once we get to the output of the circuit, we will have calculated the overall action of the unitary on computational basis states. For example, the circuit (4.1) implements the following unitary:

Generally we can describe the action of a CNOT circuit by a parity map:

By pushing variables through a circuit as in the example above, we can straightforwardly calculate the parity map for any CNOT circuit. Hence, the following proposition is immediate.

Furthermore, the parity map totally defines the unitary associated with the CNOT circuit. In particular, if we find another CNOT circuit with the same parity map, it implements the same unitary. For example, the unitary implemented by the CNOT circuit (4.1) could also be implemented by this much smaller CNOT circuit:

By starting with a CNOT circuit, computing its parity map, then finding a new circuit that implements that same parity map, we ended up with a circuit that was a lot smaller, with just one CNOT gate rather than six. We call the problem of generating a CNOT circuit that implements a given parity map the CNOT circuit synthesis problem. In the next section, we will show that, as long as a parity map is invertible, we can always synthesise a CNOT circuit that implements it.

4.1.3 CNOT circuit synthesis

We can view a bit string $\overrightarrow{x}\in {\{0,1\}}^n$ as a vector of the vector space $𝔽2^n$. With this in mind, it follows that parity maps, which only ever compute XORs of their input bits, are actually linear maps over such vector spaces. Consequently, we can always write them in matrix form.

One can show straightforwardly that for any parity map $f$, we can find a parity matrix $A$ such that $f(\overrightarrow{x})=A\overrightarrow{x}$. Indeed we saw an example of this in section 4.1.1 when we represented the parity map:

with the matrix:

In the last section, we saw how to represent the action of a CNOT circuit as a parity map. It will be convenient to write this map as a parity matrix. Since CNOT circuits represent reversible computations on bits, their associated parity matrices are always invertible.

Thinking about the action of a single CNOT gate:

we get the parity map $f(x_1,x_2)=(x_1,x_1\oplus x_2)$ and hence the following lower-triangular parity matrix:

Notably, since $1+1=0$ in ${𝔽}_2$, this matrix is its own inverse:

This captures the fact that two successive CNOT gates cancel out. We can generalise this to a single CNOT gate appearing in a larger circuit as follows.

You may have met matrices like these before in a linear algebra course. Matrices that look like the identity matrix with the exception of one additional non-zero value correspond to primitive row and column operations used for Gaussian elimination. If I multiply a generic matrix $M$ with $E^{\mathit{ij}}$ on the left, this has the effect of adding the $i$-th row of $M$ to the $j$-th row:

whereas if we multiply by $E^{\mathit{ij}}$ on the right, it has the effect of adding the $j$-th column to the $i$-th column:

A general property of invertible square matrices is we can reduce them to the identity matrix by means of primitive row operations or primitive column operations. For a generic field, there are two kinds of primitive row/column operations: multiplying a row/column by a non-zero scalar and adding one row/column to another. This is what happens when we apply the Gauss-Jordan reduction procedure, sometimes called simply Gaussian elimination, to an invertible matrix. For ${𝔽}_2$, there is only one non-zero scalar, $1$, so in fact the second kind is all we need. There are two, essentially equivalent ways we can do Gauss-Jordan reduction, either working from the left side of the matrix with row operations or the right side of the matrix with column operations. Although it is the (slightly) less typical version, here we’ll use column operations. This will make things easier when it comes to generalising to bigger families of circuits in Chapter 7. Suppose we find any sequence of $k$ primitive column operations that reduce a parity matrix to the identity. Then we have a series of elementary matrices $E^{i_1{j}_1},\dots ,E^{i_k{j}_k}$ such that:

As we noted in Example 4.1.6, each of the elementary matrices is their own inverse. So, we can move them to the other side of this equation, reversing the order:

Hence, we can see Gaussian elimination as a way of decomposing invertible matrices as a composition of elementary matrices. Since we know that every parity matrix coming from a CNOT circuit is invertible and that each elementary matrix corresponds to a CNOT gate, we see that synthesising CNOT circuits from parity matrices amounts to Gaussian elimination! We give the full synthesis procedure in Algorithm 1. Note we write ${\text{CNOT}}^{\mathit{ij}}$ for a CNOT gate with a control on the $i$-th qubit and a target on the $j$-th qubit.

4.2 The phase-free ZX calculus

Now that we understand CNOT circuits and their relationship to parity matrices a bit better, let’s turn our attention to phase-free ZX-diagrams and the phase-free ZX calculus. As we noted at the beginning of this chapter, phase-free ZX-diagrams are those without Hadamard gates and whose spiders all have phase 0. It turns out that once we make this restriction, one can simplify the rules a great deal. As we’ll see in Section 4.3.1, the rules in Figure 4.0 suffice to prove any true equation between phase-free ZX-diagrams. We will see in this section and the next that the phase-free ZX calculus encodes a great deal of information about CNOT circuits, and more generally linear algebra over ${𝔽}_2$. To start to get an idea of why this is the case, we’ll temporarily introduce some $\pi$ phases into X spiders to represent basis states, and recap some of the things we already saw in the previous chapter. Recall that we can represent the two $Z$-basis states as X-spiders, with a phase of $0$ or $\pi$, respectively:

where ‘$\propto$‘ here means we are ignoring the scalar factor. Due to this fact, it will be convenient to represent computational basis elements using a boolean variable $a\in \{0,1\}$:

A Z-spider acts on a computational basis state by copying it through, while an X-spider calculates the XOR of its inputs:

The latter follows from the fact that, for boolean variables $a,b$, we have $(a+b)\pi =(a\oplus b)\pi$, modulo $2\pi$. Recall what the CNOT gate looks like as a ZX-diagram:

With the interpretation of the Z-spider as copying and the X-spider as XOR we see that we can interpret this diagram as saying that we first copy the first bit, and then XOR it with the second bit, and this is indeed how we understand the functioning of the CNOT:

It turns out that this idea generalises to describe the action of an arbitrary parity matrix in the following way: suppose we have an $n\times m$ parity matrix $A$, then its corresponding ZX-diagram is given by

• one Z-spider connected to each input $1\le i\le n$ and one X-spider connected to each output $1\le j\le m$,
• a connection from the $i$th Z-spider to the $j$th X-spider if and only if $A_{\mathit{ij}}=1$.

Another way to say this is that the biadjacency matrix of the connectivity from the Z-spiders to the X-spiders is equal to the parity matrix. This biadjacency matrix has a row for each X-spider, and a column for every Z-spider, and there is a $1$ in the matrix when the corresponding Z-spider is connected to the corresponding X-spider, and a $0$ if they are not connected. Just like for CNOT circuits in the previous section, the parity matrix of a ZX-diagram in parity form exactly captures the action of the associated linear map on computational basis states.

It will be helpful to have a name for diagrams such as the one depicted in equation (4.5) above.

If a diagram is in PNF, the only relevant information is the number of inputs, number of outputs, and which inputs are connected to which outputs. Hence biadjacency matrices are in 1-to-1 correspondence with ZX-diagrams in parity normal form.

4.2.1 Reducing a ZX-diagram to normal form

We have now seen that we can represent a CNOT circuit as a parity matrix and parity matrices as ZX-diagrams in parity normal form. Additionally, using Gaussian elimination we can go back from this parity form to a CNOT circuit. There is just one step missing in this trifecta of representations: how to reduce a unitary phase-free ZX-diagram to parity normal form. This is what we will do in this section. Apart from it being useful to understand how CNOT circuits relate to ZX-diagrams, it will also give us a first taste about how to define simplification strategies in the ZX-calculus. The first step in this process of simplification will be to bring the ZX-diagram into a more canonical form.

We call such diagrams two-coloured because we can view them as simple graphs (where the spiders are the vertices) with a two-colouring (corresponding to the colours of the spiders).

Given a phase-free ZX-diagram we can apply the above procedure to reduce it a two-coloured diagram. This diagram will of course still be phase-free. Now we will apply rewrites to this diagram that bring it closer to parity normal form. In the parity normal form, all Z-spiders are connected to an input, while all X-spiders are connected to an output. So, ‘bringing it closer’ to the normal form means reducing the number of Z-spiders that are not connected to an input or reducing the number of X-spiders not connected to an output. The way we do this will be to strategically apply the strong complementarity rule $(\mathrm{sc})$.

To phrase the condition above in a different way, it is saying that there are only two kinds of Z-spiders: input Z-spiders and internal Z-spiders directly connected to output X-spiders. A similar categorisation applies to X-spiders, reversing the role of inputs/outputs. Hence, the generalised parity form looks like this, for some $m,n,j,k\ge 0$:

What makes this form “generalised” as opposed to diagrams in parity normal form is the possibility of some internal spiders. When $j=k=0$, we get exactly the parity normal form. In Algorithm 2 we show how to efficiently transform a phase-free ZX-diagram into generalised parity form.

Now, why do we care about generalised parity form? Well, it turns out that if the diagram describes a unitary, that such a diagram must be in parity normal form.

4.2.2 Graphical CNOT circuit extraction

In this section, we will see that we can derive the exact same CNOT circuit synthesis procedure from Section 4.1.3 starting with ZX-diagrams in parity normal form and applying strong complementarity to extract a CNOT circuit via Gaussian elimination. While the ZX reformulation doesn’t tell us something new about the specific case of CNOT circuits per se, we will see this basic graphical technique appearing in various guises throughout the book, so it will be instructive to work through it explicitly here. For instance, if we have a diagram that is more complicated, but locally has a part that looks like like a parity normal form, then we can still (partially) apply the graphical Gaussian elimination strategy. The key point to the proof is to realise that the phase-free ZX-calculus already ‘knows’ how to do ${𝔽}_2$-linear algebra. To get started, we’ll see that we can prove that CNOT matrices perform elementary column operations on parity matrices using just the ZX rules. First of all, what does this look like graphically? In a parity normal form, the Z-spiders correspond to columns of the biadjacency (i.e. parity) matrix, and the wires coming out of the Z-spider correspond to 1’s in that column. In order to see a CNOT as performing a column operation, we should therefore see that pre-composing two Z-spiders by a CNOT has the effect of “adding” the connections of one spider to the other, modulo 2. That is the content of the following lemma.

This lemma says that when we apply a CNOT to a pair of inputs in a diagram in parity normal form that we can ‘absorb’ this CNOT at the cost of changing the connectivity of the diagram. In the case of parity normal form diagrams, this change in connectivity corresponds precisely to an elementary column operation. This is easiest to see by means of an example.

As we noted in Section 4.1.3, whenever a parity matrix is invertible, it is possible to reduce it all the way to the identity using just elementary column operations. Hence, the following proposition follows immediately.

Combining Lemma 4.2.7 and Proposition 4.2.8 we see that we have a strategy for simplifying any unitary phase-free ZX-diagram to parity normal form. Additionally, such a diagram is equivalent to a CNOT circuit.

As CNOT circuits themselves are unitary phase-free ZX-diagrams, this theorem gives us an evident technique for a purely ZX-based method for optimising CNOT circuits: from a CNOT circuit compute the PNF, then re-extract using strong complementarity as in Example 4.2.11.

4.3 Phase-free states and ${𝔽}_2$ linear subspaces

Let’s have a look again at the generalised parity form (4.6):

In the previous section, we focussed on the special case where the phase-free ZX-diagram diagram describes a unitary, in which case we must have $j=k=0$. We now turn to a different special case, where the ZX-diagram depicts a state. In this case, $m=0$, and hence up to scalar factors, we can also take $j=0$. Hence, we are only left with a layer of $k$ internal Z spiders, followed by a layer of $n$ output X spiders:

Note that we could still represent such a diagram by its biadjaceny matrix, but columns correspond to internal Z spiders rather than inputs. In particular the order of the columns no longer matters, so rather than representing such a diagram as a matrix, it makes more sense to represent it simply as a set of ${𝔽}_2$-vectors.

At this point, the careful reader may note that a Z-X normal form might contain more than one Z spider connected to the exact same set of X spiders. From this, one might think we should actually describe the Z-X normal form by a multi-set of ${𝔽}_2$-vectors, i.e. a set that allows duplicate elements. However, thanks to the rules of the phase-free ZX calculus, we can always remove spiders corresponding to duplicate bit-vectors.

Unlike the parity form, the Z-X normal form is not unique. However, we will soon see that it is straightforward to discover when two Z-X normal forms actually describe the same state, and how in that case we can transform one into the other. The key point is to realise that the important information captured in $\{v_1,\dots ,v_k\}$ is not the set itself, but rather the subspace $S$ of ${𝔽}_2^n$ spanned by it. The usual way to define $S$ is as the set of all of the possible linear combinations of $\{v_1,\dots ,v_k\}$:

Equivalently, since the field is ${𝔽}_2$, we can think of $S$ as the set of all vectors obtained by XOR-ing any subset of $\{v_1,\dots ,v_k\}$, including the zero vector (which corresponds to XOR-ing the empty set). Since ${𝔽}_2$ is a finite field, any subspace of ${𝔽}_2^n$ (including ${𝔽}_2^n$ itself) is a finite set of vectors, so we can compute it explicitly. For example:

Let’s look at the Z-X normal form corresponding to the pair of vectors on the lefthand-side of (4.9).

We can compute the state explicitly by expanding each Z spider as a sum over X spiders:

The result is precisely the sum over all of the vectors in the subspace (4.9), written as elements of the computational basis. This is true in general, as stated in the following theorem.

This can be seen by direct calculation similar to (4.10), by expanding each of the Z spiders as a sum $|0...0⟩+|1...1⟩$ and using the fact that X spiders act like XOR.

Theorem 4.3.2 says that the state associated with an $n$-qubit Z-X normal form is uniquely described by an ${𝔽}_2$-linear subspace $S$ of ${𝔽}_2^n$. From the Z-X normal form itself, we can read off a spanning set of vectors for $S$. As a result, we are not too far from showing completeness of the phase-free ZX calculus.

4.3.1 Phase-free completeness

Recall that a completeness theorem states that if any two diagrams correspond to the same linear map, one can be transformed to the other just using graphical rules. In this section, we will prove completeness of the phase-free ZX-calculus for the fragment of phase-free ZX-diagrams. Since we have already shown that phase free states correspond to linear subspaces and their associated Z-X normal forms correspond to sets of vectors spanning those spaces, the only thing left to do is show that we can transform one spanning set into another using just the phase free ZX rules.

We will omit the proof here, as it is a standard result in linear algebra. Note that usually case 2 consists of replacing the pair $v,w$ with $v,\mathit{\lambda v}+w$ for some non-zero scalar $\lambda$. But in ${𝔽}_2$, the only non-zero scalar is $1$, so this simplifies. We can now prove the following lemma by reproducing the two cases of Proposition 4.3.3 using the ZX calculus.

We now have completeness of the phase-free ZX-calculus for states. To get the full completeness result we need to show how to adapt this to work for arbitrary diagrams. Because we can just bend wires this is not too hard.

In this proof we implicitly rewrote the “state form” of $D_1$ and $D_2$ into the Z-X normal form. If we take this normal form, and bend the input wires back we get a diagram that looks like the following:

We then have a layer of X-spiders connected to both the inputs and outputs, and these are connected via some internal Z-spiders. This is hence an alternative normal form for phase-free diagrams.

4.3.2 X-Z normal forms and orthogonal subspaces

All of the rules of the ZX calculus are colour-symmetric, so we could just as well obtain a normal form for phase-free ZX-diagrams consisting only of a row of internal X-spiders and a row of boundary Z-spiders. One way to see this is to start yet again from the generalised parity form:

and set $k=n=0$ this time. We’ll obtain a colour-reversed, mirror image of the Z-X normal form from (4.7):

Just like before, we can describe this object by a set of bit-vectors $\{w_1,\dots ,w_j\}$.

Suppose we plug some basis state $|v_1,\dots ,v_n⟩$ into an X-Z normal form. The result will be a scalar, which depends on the XORs of some subsets of the input bits. For example:

If either of the scalar X spiders has a phase of $\pi$, the whole thing goes to zero. If both X spiders have a phase of 0, then the scalar equals a fixed non-zero value $N$. In other words, the result is non-zero precisely when a collection of parities of input variables all equal zero. Hence, we can write the linear map as follows:

Recalling that in ${𝔽}_2$, $\oplus =+$ and the only possible coefficients in a linear equation are zero and one, requiring a set of parities to all be zero is the same thing as saying we have a solution to a system of homogeneous ${𝔽}_2$-linear equations. The term homogeneous just means all the righthand-sides are equal to zero, and famously the set of solutions to a homogeneous system of equations always forms a subspace. A handy perspective on a system of homogenous equations is to think of them as a spanning set of vectors for the orthogonal subspace, or “perp”, $S^{\perp }$ of $S$, defined this way:

Then, note:

So, giving a spanning vector for $S^{\perp }$ is really just giving a list of coefficients $w_1,\dots ,w_n$ for a linear equation. Rewriting the example above in terms of $S^{\perp }$, we have:

As in the case for spanning sets of vectors for $S$, there are many choices of spanning set for $S^{\perp }$, which correspond to equivalent systems of linear equations. For example, adding one of the equations in a system to another one doesn’t change the set of solutions:

Such a move just corresponds to changing the spanning set for $S^{\perp }$:

which, like in the Z-X case, can be replicated graphically thanks to strong complementarity:

The fact that we ended up writing X-Z normal forms as bra’s rather than ket’s is just an artifact of the convention we chose back in Section 4.2.1 to get Z spiders on the left and X spiders on the right in our generalised parity form. Everything in ZX is colour-symmetric, so we could have just as well done this the other way around to obtain an X-Z normal form for states. Hence, we actually get two equivalent ways to represent a state: the Z-X normal form and the X-Z normal form:

It is important to note that, most of the time, the number of vectors in these two forms will be different. For example, the GHZ state, given by the subspace $S=\mathrm{\text{Span}}\{(1,1,1)\}=\{(0,0,0),(1,1,1)\}$ has this Z-X normal form:

whereas $S^{\perp }=\mathrm{\text{Span}}\{(1,1,0),(0,1,1)\}$, so it has this X-Z normal form:

But of course, these two are equal, thanks to the rules of the ZX calculus:

This relationship between the Z-X and X-Z normal form will come in handy when we start thinking of quantum error correcting codes in Chapter 11.

4.3.3 Relating parity matrices and subspaces

We’ve seen that phase-free unitaries can be represented efficiently as ${𝔽}_2$ linear maps and phase-free states can be represented as ${𝔽}_2$ linear subspaces. So, a natural question is: what happens when we hit a phase-free state with a phase-free unitary? You may not be particularly surprised to find out that we can compute the subspace of the resulting state as the direct image of the original subspace. That is, for a phase-free unitary with parity map $p$:

and a phase-free state corresponding to a subspace $S\subseteq {𝔽}_2^n$:

we have that $|\psi ⟩$ gets mapped to a new phase-free state described by the subspace $p(S)$:

In fact, this just follows from linearity, and the fact that $U$ (which is injective) never takes two bit strings to the same place:

4.4 Summary: What to remember

1..

An $n$-qubit CNOT circuit corresponds to an $n\times n$ parity matrix: a matrix over the field with 2 elements $𝔽2=\{0,1\}$.

2..

A CNOT circuit can be synthesised from a parity matrix using Gaussian elimination.

3..

Phase-free ZX-diagrams are those diagrams where all the phases on the spiders are zero. They have a restricted rule set presented in Figure 4.0.

4..

Phase-free ZX-diagrams can efficiently be rewritten to several different normal forms: generalised parity form, Z-X normal form, or X-Z normal form.

5..

Unitary phase-free diagrams correspond to CNOT circuits.

6..

The row operations of Gaussian elimination correspond to doing strong complementarity in the ZX-calculus.

4.5 Advanced Material*

4.5.1 Better CNOT circuit extraction*

In the discussion on universal gate sets in Section 2.3.5 we saw that the only multi-qubit gate we need is the CNOT gate. In current physical devices entangling gates are harder to implement than single-qubit gates, incurring more noise and taking a longer time to execute. All this is to say that CNOT gates are important, and we should think hard about how we can optimise their use as much as possible. We saw in this chapter that we can always resynthesise a CNOT circuit using Gaussian elimination. Whereas a starting CNOT circuit can be as long as we want, with this resynthesis we can get a definite bound on how long the circuits can get. Each row operation in the elimination procedure gives us one CNOT gate. The question then is: how many row operations do we need in the worst case? Let’s suppose we have some arbitrary $n\times n$ parity matrix. We will find an upper bound to how many row operations we need to reduce it to the identity matrix. Let’s recall the distinct steps of Gaussian elimination. For every column we need to make sure there is a 1 on the diagonal. Then we eliminate all the elements on the column below the diagonal. Once we have done this with every column, the matrix is in upper-triangular form. We then need to do the same elimination, column-by-column, for all the elements above the diagonal. The first column in the first stage then gives us at most $n$ row operations: 1 for correcting the diagonal, and $n-1$ for correcting all the elements below the diagonal. Similarly, the second column takes $n-1$ operations. Reducing the matrix to upper-triangular form hence takes ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{k=1}^{n}k-1=n(n+1)∕2-1$, where this last $-1$ comes from the fact the final column will already have a $1$ on the diagonal when we are doing elimination and the matrix is full rank. To reduce the rest of the matrix we no longer have to correct the diagonal, and hence fixing the last column only takes $n-1$ operations, and the second $n-2$, and so on. This hence occurs ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{k=1}^{n-1}k=(n-1)n∕2$ operations. This gives us a total of $n(n+1)∕2-1+(n-1)n∕2=n^2+1∕2n-1∕2n-1=n^2-1$ operations exactly.

Requiring just $n^2$ gates, even though naively these circuits could be arbitrarily long is already pretty good. But is it also the best we can do? To determine this, we need to find some way to figure out how many CNOT gates the worst-case parity matrices require. We will do this by using a counting argument: we will count how many different possible invertible parity matrices there are, and then argue that therefore circuits must reach at least a certain length to represent them all. For instance, if we have just a single CNOT gate acting on $n$ qubits, then this can represent at most $n(n-1)$ different parity matrices, as these are all the different ways we can place the CNOT in the circuit. If instead we have $d$ CNOT gates, then there are ${(n(n-1))}^d$ different ways to place them, so that this is the maximum number of parity matrices we can represent. Since we actually care about how many parity matrices we can write down with circuits up to $D$ CNOT gates, we should also allow the identity operation as one possibility, so that there is actually $n(n-1)+1$ ways to optionally place a CNOT gate. Now let’s count how many invertible parity-matrices there are. Suppose we wish to build an invertible $n\times n$ parity matrix. We will do this column by column. The first column we can pick arbitrarily, as long as it is not all zero. We hence have $2^n-1$ options for that column. Let’s call this vector ${\overrightarrow{c}}_1$. Now for the second column we need to make sure that it is independent of the first column. So it can’t be ${\overrightarrow{c}}_1$ or $\overrightarrow{0}$, but otherwise we are free to choose it. So there are $2^n-2$ options for ${\overrightarrow{c}}_2$. Now to choose ${\overrightarrow{c}}_3$, we need to make sure it is independent of ${\overrightarrow{c}}_1$ and ${\overrightarrow{c}}_2$. The vector space spanned by these vectors has 4 elements, and hence there are $2^n-4$ options. At this point we can spot a pattern! The $k$th column has $2^n-2^{k-1}$ options to choose from. The total number of invertible parity matrices is then

If we then claim that we can represent any invertible parity matrix by a CNOT circuit of at most $d$ CNOT gates, then we must at least have:

If this wasn’t the case, then there would be no way for use to write down all the different parity matrices, since we just don’t have enough space in our circuit for that many unique options. Let’s take the logarithm in this equation, and rearrange the terms:

We see then that just to be able to represent all the parity matrices, we need circuits that have length at least of order $n^2∕\log <!--\; FUNCTION\; APPLICATION\; -->n$, and hence there will be parity matrices that require at least that many CNOT gates to write down. Our naive Gaussian elimination strategy gave us $n^2$ CNOT operations, and we see that this lower bound is $n^2∕\log <!--\; FUNCTION\; APPLICATION\; -->n$. It would certainly be nice if we could do some smarter elimination, just to squeeze out that last bit of logarithmic factor. And we can! The idea is that we don’t want to eliminate the matrix just element per element, but instead we divide each row up into small ‘chunks’. We then first try to eliminate whole chunks at a time. For instance, suppose we pick our chunk size to be 3, then we would first consider the first 3 columns at a whole, and we would look for any duplicate 3-bit strings in these columns. If we find any, then we apply a row operation to get rid of this whole bit string. Once we have done that, we proceed to eliminate these 3 columns as usual, and then go on to the second set of 3 columns. The benefit of doing this, is that when the chunk size is $c$, there are only $2^c$ different types of sub-rows, meaning that of all the $n$ elements in a row, at most $2^c$ can be non-zero after the chunk elimination, and hence the further standard elimination step only requires $c{2}^c$ row operations to clear out the $c$ columns. The cost of first doing the chunk elimination is $n$ (ignoring some details here regarding chunks being counted twice across the diagonal), and both these steps need to happen $n∕c$ number of times (assuming $c$ divides $n$), once for each of the chunked columns. We also have a cost of $n$ total to insert the right diagonal elements. The total cost is then

Setting $c=\alpha \log <!--\; FUNCTION\; APPLICATION\; -->n$ for some $\alpha <1$ then simplifies this cost to $O(\frac{n^2}{\log <!--\; FUNCTION\; APPLICATION\; -->n})$. Note that $\alpha <1$ is needed for the $n{2}^c=n^{1+\alpha }$ term to be asymptotically smaller then $n^2\log <!--\; FUNCTION\; APPLICATION\; -->n$. This hence gives us an algorithm with an asymptotically optimal CNOT count!

This algorithm isn’t just theoretically interesting: in practice it already gives better results than naive Gaussian elimination for very small number of qubits.

4.6 References and further reading

CNOT circuit synthesis An efficient CNOT circuit synthesis procedure based on Gaussian elimination was proposed by [7]. This was later refined by Markov, Patel, and Hayes in [169]. This algorithm is the one described in Section 4.5.1. This algorithm remains one of the best for unconstrained architectures, obtaining an asymptotically optimal gate count. Recently, there has also been work on synthesising CNOT circuits for architectures with topological constraints, such as superconducting devices. In these approaches, a graph is provided whose nodes are qubits and edges are places where CNOTs may be placed. This can be accomplished by constraining which row operations are allowed in Gaussian elimination using Steiner trees, a technique proposed simultaneously by [143] and [186]. A different technique, based on ${𝔽}_2$-linear decoding, was given by [78].

Interacting bialgebras The phase-free ZX calculus has also been called IB, for interacting bialgebras, in the categorical algebra literature [31]. This is because this set of generating maps:

as well as this set:

each form an algebraic structure called a bialgebra. Bialgebras, and the more specific structure of Hopf algebras, have been extensively studied in representation theory, as they generalise group algebras. This system is called interacting bialgebras because the two bialgebras (4.16) and (4.17) interact with each other, via the spider fusion laws. In algebraic terms, this means the four Z generators and the four X generators each form Frobenius algebras.

Normal forms In [31], the authors showed that any diagram built out the generators (4.16) and (4.17), i.e. any phase-free ZX diagram, can be put into one of two normal forms, which they called the span and cospan form. These are closely related to the Z-X and X-Z normal forms we used in this chapter. They also showed that the resulting maps from $m$ wires to $n$ wires are in 1-to-1 correspondence with ${𝔽}_2$-linear relations, i.e. subspaces $S\subseteq {𝔽}_2^{m+n}$. Up to bending wires, this is what we showed in Section 4.3.

PROPs This work lives in the broader field of studying PROPs, or PROduct categories with Permutations, a categorical formulation of algebraic structures whose generators can have many inputs or outputs. PROPs were first formulated by Mac Lane [166] and an important technique for composing PROPs together was developed by Lack [160]. The techniques used to get normal forms in [31] used abstract arguments based on composing PROPs, and did not directly show how to compute normal forms by applying graphical rules. The rewriting strategy used for obtaining normal forms in Section 4.2.1 is new to this book. Similar strategies have been known, but not published, for a while. For example, the graphical proof assistant Quantomatic [151] and the ZX library PyZX [146] both have implementations of such strategies, with the former implementation dating back to the mid-2010s.