Chapter 10
Clifford+T

In the previous chapters, we have often seen a dichotomy between two classes of quantum computations. On the one hand, we have Clifford computations, which have a great deal of structure we can exploit to efficiently solve problems like circuit synthesis, deciding equality of computations, and strong classical simulation. On the other hand, we have looked at universal quantum computation, typically arising from adding $Z[\alpha ]$ gates for arbitrary angles $\alpha \in [0,2\pi ]$. While Clifford angles, i.e. integer multiples of $\frac{\pi }{2}$, satisfy many identities, we have so far treated non-Clifford angles as “black boxes”, which don’t seem to satisfy any extra rules, except for trivial ones coming from the spider fusion rule like

and variations thereof. It turns out that for generic angles, this is pretty much all we can do. In fact, as we’ll explain in the References, there is a way to make this statement precise. However, for dyadic angles, i.e. angles of the form $\frac{\pi }{2^k}$ for some integer $k$, there is a great deal more structure at play. As we’ll see in this chapter, we can take advantage of this dyadic structure in a variety of ways. First, we will see that it simplifies the problem of synthesising generic unitary maps using just Clifford gates and the first non-Clifford dyadic phase gate $T:=Z[\frac{\pi }{4}]$. We can characterise the set of unitary matrices that we can synthesise exactly using Clifford+T gates as those whose entries are all within a certain subset, called $𝔻[\omega ]$, of the complex numbers. Using some special properties of this set, and a little (light) ring theory, we can figure out precisely how many gates we need to synthesise such a matrix exactly and do this synthesis efficiently. Note, here “efficient” means efficient in the size of the matrix, not the number of qubits. For generic unitaries, this is the best we can hope for. We’ll also see that for any tolerance $𝜖>0$, we can approximate any unitary matrix within $𝜖$ with a $𝔻[\omega ]$-matrix, which we can in turn synthesise exactly using Clifford+T gates. Second, we will see that for dyadic angles, new rules start to hold that wouldn’t for generic angles. In particular, certain complex configurations of phase gadgets can all cancel each other out in ways that are not implied by the gadget-fusion law we met back in Chapter 7. These so-called spider nest identities come from a particular interaction between the parity (i.e. mod-2) structure of the phase gadget itself and the mod-$2^k$ structure of its angle. Similar to the representation from Chapter 7 of CNOT+phase circuits, we can represent phase gadgets as collections of binary vectors representing parities of qubits where phases get applied, and as before we can stick these vectors together into a matrix. We introduce a new Scalable ZX notation so that we can directly represent these matrices in an efficient way in our diagrams. Using these matrices representing collections of phase gadgets we can also recognise which configurations of $\frac{\pi }{4}$ phase gadgets will cancel out. Namely, it will be those whose “gadget matrix” satisfies a condition called strongly 3-even. In this chapter, we will work out some properties of strongly 3-even matrices and a closely related ${𝔽}_2$-linear structure called Reed-Muller codes. Finally, we will put the pieces together by classifying all the spider nest identities and explaining how they can be used for T count optimisation. Clifford+T circuits are especially important for fault-tolerant quantum computation, so in this chapter we will also be (secretly) laying the groundwork for Chapter 11, where we explain techniques for implementing universal quantum computation within a quantum error correcting code. In particular, in Section 10.5 we will see how we can relate circuits over different types of gate sets together using a technique called catalysis that allows you to perform certain ‘hard’ operations in an easy way as long as you have a suitable catalyst state lying around. Together with the classification of spider nest identities this will prove very handy for when we want to implement non-Clifford gates in fault-tolerant architectures.

10.1 Universality of Clifford+T circuits

Back in Chapter 2, we noted that CNOT gates plus arbitrary single-qubit unitaries are universal for quantum computation, in the sense that they can be used to build arbitrary unitaries over $n$ qubits. In this section, we will show that, in fact Clifford+T circuits are approximately universal, in the sense that they can get arbitrarily close to any $n$-qubit unitary. One way to show this, is to show how for any single-qubit unitary $U$ there exists some $U^{\prime }$ arbitrary close to $U$ expressed totally in terms of $H$ and $T$ gates. There are several ways to prove this. The “classic” way is to show that $V:=\mathit{HT}$ corresponds to a rotation about some axis of the Bloch sphere by an irrational multiple of $\pi$. Then, by raising $V$ to larger and larger powers, we will eventually land close to any possible rotation around that axis. We can do the same around some other axis, e.g. with $V^{\prime }=\mathit{TH}$, to obtain a pair of rotation gates that suffice to build any single-qubit unitary. It takes quite some work to spell out the details of this argument, and this has been done in several standard textbooks on quantum computing. There are also many variations one can use to obtain more or less efficient decompositions of single-qubit unitaries. We’ll give some pointers to where you can find all the gory details of this approach and variations at end of this chapter. However, in this section, we will start with a totally different approach to synthesis of unitaries in Clifford+T, which is based on number theory. This approach starts from the realisation that the numbers appearing in a unitary matrix built from CNOT, H, and T are not just any old complex numbers, but are actually quite special. First, lets have a look at the matrices again:

Clearly any $U$ that we can construct from these gates will have as its entries sums and products of integers, $\frac{1}{\sqrt{2}}$, and the complex phase $\omega :=e^{\mathit{i\pi }∕4}$. If we think about where $\omega$ lies on the complex plane:

we see that $\omega =\frac{1+i}{\sqrt{2}}$ and $\overline{\omega }=-{\omega }^3=\frac{1-i}{\sqrt{2}}$. Using these facts, it’s not hard to see that we can already build $\frac{1}{\sqrt{2}}$ using just integers, $\frac{1}{2}$, and $\omega$:

If we look at just the numbers we can build with integers and $\frac{1}{2}$, this consists of precisely the rational numbers whose denominator is a power of two. We give this set of numbers a special name.

Clearly $0,1\in 𝔻$, and for $q,r\in 𝔻$, $-q,q+r$ and $\mathit{qr}$ are also in $𝔻$. Hence, $𝔻$ forms a ring. However, unlike the full set of rational numbers, not every $q\in 𝔻$ has a multiplicative inverse in $𝔻$, so it is not a field. It turns out that, for the purposes of circuit synthesis, this is not a bug, but a feature, since rings can have very interesting properties owing to the fact that we cannot arbitrarily divide numbers by each other. To discuss the single-qubit synthesis algorithm, there are two relevant rings based on $𝔻$ we need to study. The first is $𝔻[\omega ]$, the ring obtained by allowing arbitrary sums and products of dyadic rationals with the complex number $\omega$. The second is $\mathbb{Z}[\omega ]⊊𝔻[\omega ]$, which is restricted just to integer multiples of powers of $\omega$. Such rings are called ring extensions, i.e. rings obtained by adding one or more elements outside of the original ring and closing under sums and products. Since ${\omega }^4=e^{\mathit{i\pi }}=-1$, we can concretely represent elements of $\mathbb{Z}[\omega ]$ and elements of $𝔻[\omega ]$ using quadruples of numbers taken respectively from $\mathbb{Z}$ or $𝔻$:

Clearly any unitary matrix built out of CNOT, H, and T will consist of elements from $𝔻[\omega ]$. Perhaps surprisingly, the converse is also true: any unitary matrix whose elements are in $𝔻[\omega ]$ can be constructed exactly as a composition of CNOT, H, and T gates. We will show this by giving a concrete algorithm for synthesising unitaries over $𝔻[\omega ]$ in the following sections, then conclude with some remarks on how this lifts to an approximate synthesis algorithm for unitaries over all complex numbers.

10.1.1 Exact synthesis of one-qubit gates

We’ll begin by considering the simplest non-trivial synthesis problem we can have: namely preparation of an arbitrary single-qubit state $|\psi ⟩$. That is, we want to find a sequence of $H$ and $T$ to transform $|0⟩$ into $|\psi ⟩$. Equivalently, we can find a sequence of $H$ and $T$ transforming $|\psi ⟩$ into $|0⟩$, then take the adjoint. One way to do this is starting with a state whose entries are in $𝔻[\omega ]$, and then applying gates to it until all of the entries are in $\mathbb{Z}[\omega ]$. The following lemma should make clear why this helps us.

If we get to ${\omega }^j|0⟩$, mission accomplished, up to a global phase. If we get to ${\omega }^j|1⟩$, we simply apply an $X$ gate (i.e. $H{T}^{4}H$) and again we are done. So, the name of the game is turning the coefficients of $|\psi ⟩$ into elements of $\mathbb{Z}[\omega ]$. One potential strategy is to factor $|\psi ⟩$ as:

then apply gates to $|\psi ⟩$ to try and make the coefficients $x$ and $y$ into even numbers. Then, we can factor out a $2$ from $x$ and $y$ and the leading scalar becomes $\frac{1}{2^{k-1}}$ and we’ve made some progress toward getting a state whose coefficients are in $\mathbb{Z}[\omega ]$. This does work, but it is a bit tricky to find the gates we need to apply to $|\psi ⟩$ to “make progress”. We can make life a bit easier if we express $|\psi ⟩$ differently, as:

where $\delta :=1+\omega$ is a “special” number that has some nice number-theoretic properties that will help with our synthesis algorithm (for more details on the number theory side of things, check out the advanced section 10.7.1). First, we should be able to check that $|\psi ⟩$ is indeed a vector over $𝔻[\omega ]$. For this, we should check that $\frac{1}{\delta }\in 𝔻[\omega ]$, which is not immediate because not every element in $𝔻[\omega ]$ has a multiplicative inverse. The elements of a ring that do have multiplicative inverses are called units. We can see that $\delta$ is a unit in $𝔻[\omega ]$ by letting ${\delta }^{-1}:=\frac{1}{2}(1-\omega +{\omega }^2-{\omega }^3)$ and calculating $\delta {\delta }^{-1}=1$. Conversely, we would like to know that any $|\psi ⟩$ with coefficients in $𝔻[\omega ]$ can be written in the form of (10.3). This is true if any $q\in 𝔻[\omega ]$ can be written as $\frac{x}{{\delta }^k}$ for some $x\in \mathbb{Z}[\omega ]$ and a high enough power $k$ of $\delta$. Put another way, we need to prove the following property of $\delta$.

The smallest $k$ needed to express $|\psi ⟩$ in the form of equation (10.3) is called the least denominator exponent (lde). If the lde is $0$, then $|\psi ⟩$ is already has coefficients in $\mathbb{Z}[\omega ]$, so by Lemma 10.1.2, it must be a basis state, up to a phase. It is easy to see that $k$ is minimal precisely when $x$ and $y$ are not both divisible by $\delta$, i.e. when there exists no pair $a,b\in \mathbb{Z}[\omega ]$ such that $\mathit{a\delta }=x$ and $\mathit{b\delta }=y$. We can easily check divisibility by $\delta$ using ${\delta }^{-1}$. Since ${\delta }^{-1}\notin \mathbb{Z}[\omega ]$, then it is not necessarily the case that $z{\delta }^{-1}\in \mathbb{Z}[\omega ]$ for some $x\in \mathbb{Z}[\omega ]$. In fact, it will be in $\mathbb{Z}[\omega ]$ precisely when $\delta$ divides $x$. The final piece of the puzzle is the following lemma, which lets us decrease the lde by applying H and T gates.

Since $x^{\prime },y^{\prime }$ become divisible by $\delta$, we can factor a $\delta$ out and reduce the least denominator exponent by 1. If we repeat this process over and over, eventually the lde will be $0$, so by Lemma 10.1.2 it will be a basis vector. The reason why Lemma 10.1.3 works has to do with the special behaviour of $\delta$ within the ring $\mathbb{Z}[\omega ]$. Namely, if we start computing numbers modulo $\delta$ (or powers of $\delta$) in $\mathbb{Z}[\omega ]$, we will see that $x$ and $y$ can always be broken down into a particular form that tells us how many $T$ gates to apply to make progress. To understand this, we will need to define the notion of a residue class, which lets us formalise what it means to work “modulo” some element of an arbitrary ring. We will do this and provide a proof for Lemma 10.1.3 in Section 10.7.1. However, if we believe the lemma, we now have a synthesis algorithm for qubit states. In fact, this also already gives a synthesis algorithm for single-qubit unitaries. This is because the columns of a unitary matrix must be orthogonal, so if we send the first column to a basis vector, the second column will also get sent to a basis vector, up to a phase. So after transforming the basis vector to the correct positions and phases, we will have synthesised the entire single-qubit unitary. We summarise this procedure in Algorithm 4.

10.1.2 Approximating arbitrary single-qubit gates

Suppose we want to use the exact synthesis algorithm from the previous section to approximate arbitrary, single-qubit unitaries. We now know that we can build any $2\times 2$ unitary matrix over the ring $𝔻[\omega ]$, and it is not hard to see that any complex number can be approximated to arbitrarily high precision by some element of $𝔻[\omega ]$. Indeed, if we take $\frac{a}{2^j}+\frac{b}{2^k}{\omega }^2=\frac{a}{2^j}+\frac{b}{2^k}i$ for $a,b\in \mathbb{Z}$ and some suitably high values of $j,k\in \mathbb{N}$, we can get as close as we like to an arbitrary complex number. We seem to be most of the way there on coming up with an approximate synthesis algorithm. The problem is, if we go through a complex-valued unitary matrix $U$ element-by-element and approximate each complex number with an element of $𝔻[\omega ]$, odds are we won’t get something unitary but just very nearly unitary. So we need a better idea. Like in the exact synthesis case, inspiration comes from looking at the least denominator exponenent. The idea is, for a target unitary matrix $U$ and a fixed error bound $𝜖>0$, we progressively raise the denominator exponent $k$ until we can find some $V=\frac{1}{{\delta }^k}{V}^{\prime }$ where

1..

$V^{\prime }$ is a matrix over $\mathbb{Z}[\omega ]$,

2..

$V$ is unitary, and

3..

for some global phase $\alpha$, $\parallel V-e^{\mathit{i\alpha }}U\parallel \le 𝜖$.

It turns out condition 2 is already quite restrictive. Since $V$ is a unitary, its columns need to be normalised. Hence, the norm-squared of the columns of $V^{\prime }$ must be $|\delta {|}^{2k}$. Using this fact, we can prove that for fixed $k$, there are only finitely many $V^{\prime }$ to choose from.

Since we already know that there are finitely many $V$ satisfying conditions 1 and 2 above for fixed $k$, we know that there must also be finitely many $V$ satisfying all 3 conditions. Hence, we can enumerate them for a fixed $k$. If we find a solution, we accept it. Otherwise, we increase $k$ and try again. It turns out that there is a way to do this enumeration of candidates satisfying conditions 1–3 efficiently, and that it terminates for $k=O(\log <!--\; FUNCTION\; APPLICATION\; -->\frac{1}{𝜖})$. The way this works has to do with properties of certain discrete subsets of the complex plane, which are a bit advanced for our purposes. Hence, we’ll finish our story on synthesis here, and make a few more remarks about this in the advanced Section* 10.7.3.

10.2 Scalable ZX notation

So far in this book we have used ZX-diagrams where each wire represents a single qubit. As we have seen, this already allows us to do a lot of interesting stuff. However, sometimes there is repetitive structure in the diagram that we should really try to abstract away, so that we don’t miss the forest for the trees. The way we do that will be with scalable ZX notation. This notation allows us to compactly represent operations on registers of many qubits, while still maintaining much of the flavour of calculations with standard ZX-diagrams. We will represent a register of qubits as a single thick wire:

Sometimes we will need to split a register into two registers, peal one qubit off to do something with, or merge registers together again. For that we introduce a little bit of extra notation:

We call these operations divide and gather. They don’t actually do anything as linear maps (they are just the identity), but they help us compactly write down more complicated maps. They come with some simple rewrites:

Note that in general we will only label the thick wires with the number of qubits they represent when it is necessary for clarity, and leave it implicit otherwise. Just being able to represent a qubit register as a single wire is not that useful, so let’s introduce some things we can do with them. We will use bold spiders (with a thick border) to represent a product of (unconnected) copies of a Z or X spider as a bold spider:

Note that in this notation each thick wire connected to the same spider needs to represent the same number of qubits, otherwise it is not a valid diagram. These bolded spiders can be labelled by a phase, and this phase then gets applied to each qubit separately. As the bolded Z- and X-spiders represent non-interacting parallel spiders, all the standard ZX rewrites still apply to them, and hence we can still do spider fusion, strong complementarity, etc. We can push spiders through a dividers and this in fact gives us a type of bialgebra between the Z/X spider and the dividers and gatherers (cf. Section 3.2.4):

Note that this also works when the spider has no additional outputs:

The most important component of the scalable notation, and what makes all of this worthwhile, is a new piece of notation called the matrix arrow, or just arrow for short, which allows us to represent arbitrary connectivity from $m$ Z-spiders to $n$ X-spiders using an $n\times m$ biadjacency matrix $A\in {𝔽}_2^{n\times m}$:

Taking the convention that $A_i^j$ represents the entry in the $i$-th column and $j$-th row of the matrix $A$, we have in Eq. (10.10) that $A_i^j=1$ if and only if the $i$-th Z-spider on the left is connected to the $j$-th X-spider on the right. Just using a single matrix arrow we can hence write down an arbitrary phase-free ZX-diagram in parity normal form (Definition 4.2.2), by directly writing the biadjacency matrix $A$ on the matrix arrow. Concretely, Eq. (10.10) corresponds, up to scalar factors, to a linear map that acts as $A$ on computational basis vectors:

Note that we treat the bit string $\overrightarrow{b}$ as a column vector for the purposes of matrix multiplication. Let’s consider some special cases for the matrix arrow, an all zero matrix and the identity:

Using Eq. (10.11), we can see that when we compose matrix arrows, we just calculate the matrix product:

We can also prove this diagrammatically by unrolling the definitions and using strong complementarity on all the internal spiders (this is essentially doing the reduction to parity normal form from Chapter 4). Spiders and arrows interact in nice ways. First, we have two “copy” laws allowing us to push arrows through spiders:

These can be proven by unrolling the definitions and using strong complementarity and spider fusion.

Second, we can express block matrices in terms of spiders:

We can combine these operations to get a decomposition of a matrix into smaller matrices:

We could view this as the definition of the matrix arrow, because this allows us to define it inductively, starting from trivial components and combining these into larger matrices. The block matrix and composition rules also imply a graphical rule for the sum of two matrices.

10.2.1 Scalable phase gadgets

Collections of phase gadgets turn out to look quite simple when using scalable ZX notation. First, let’s see how we can represent a single phase gadget:

Here ${\overrightarrow{1}}^T$ is the row vector $(1 \cdots 1)$, and hence the matrix arrow represents a collection of Z-spiders connected to a single X-spider, as needed. If instead the phase gadget is only connected to a subset of the wires, then we can replace $\overrightarrow{1}$ by a vector $\overrightarrow{v}$ where $v_i=1$ iff the gadget is connected to the $i$th qubit. We can then see how we can represent a composition of phase gadgets in scalable notation:

This construction generalises to any number of phase gadgets, for which we then get:

In this $k\times n$ matrix $M$ each of the $k$ rows describes a phase gadget, and each of the $n$ columns corresponds to a qubit. Hence, $M_i^j=1$ iff the $j$th phase gadget is connected to the $i$th qubit. Note that we can prove the gadget fusion rule of Section 7.1.2 in the scalable setting using what we have seen. This applies when we have two phase gadgets with the same connectivity, and hence the same row appears twice in the matrix:

Conversely, if we have gadgets with phases that are not $\frac{\pi }{4}$, but multiples of that, we can also represent them like (10.19), by unfusing them into additional rows of the matrix (doing (10.20) in reverse).

10.3 Rewriting Clifford+T diagrams

In Chapter 9 in order to construct the Toffoli and CCZ gate using more low-level gates, in particular T gates, we used a Boolean Fourier transform to switch from the multilinear phase polynomial ${(-1)}^{\mathit{xyz}}$ used in the CCZ gate to a phase polynomial built out of XOR terms that can be constructed using phase gadgets. In essence this all boiled down to the equation:

We used this equation to argue for the following diagrammatic equality:

But there is nothing special about the phase of the CCZ gate here, and in fact we can write a similar equation for a $\mathit{CCZ}(\alpha )$ gate:

Now when $\alpha =0$ both sides of this equation are obviously equal to the identity (just copy some spiders and cancel some identity spiders). But this should then also hold for $\alpha =2\pi$, and then this fact becomes less obvious. On the left-hand side we then have $e^{i2\pi }=1$ so that it is still the identity, but on the right-hand side we get a bunch of $e^{\pm i2\pi ∕4}=e^{\pm \mathit{i\pi }∕2}$ phases. In that case we can show this by using the $Y$ eigenstate identity of Exercise 3.15, the Euler decomposition of the Hadamard and local complementation:

In this case we can hence still prove this identity with the tools we have already seen. But when we generalise Eqs. (10.21) and (10.23) to work with more than 3 wires we start getting new and very useful identities. As the number of XOR terms blows up exponentially it will be helpful to introduce a slightly more compact way to talk about them. Note that we can represent a parity like $x_1\oplus x_3\oplus x_4$ with a bit string $\overrightarrow{y}=1011$ since $\overrightarrow{y}\cdot \overrightarrow{x}=y_1{x}_1\oplus y_2{x}_2\oplus y_3{x}_3\oplus y_4{x}_4=x_1\oplus x_3\oplus x_4$. We can hence write Eq. (10.21) more compactly as

Here $\overrightarrow{x}=x_1{x}_2{x}_3$ and the sum over the $\overrightarrow{y}$ goes over all the bit strings $𝔽2^3$ except for $\overrightarrow{0}=000$. We can then easily write down the generalisation of this equation to $n$ variables $x_1,\dots ,x_n$ as follows:

Now if we take $n=4$, and we consider the CCCZ gate, which applies the phase polynomial $e^{\mathit{i\pi }{x}_1{x}_2{x}_3{x}_4}$, then applying Eq. (10.25) would result in a bunch of phase gadgets with a phase of $\pm \frac{\pi }{8}$. But this is the Clifford+T chapter, so we want $\pm \frac{\pi }{4}$ phases. We can get those by instead considering the trivial phase polynomial $e^{2\mathit{\pi i}{x}_1{x}_2{x}_3{x}_4}$. This then results in a constellation of $2^4-1=15$ $\pm \frac{\pi }{4}$ phase gadgets:

While this might look like some sort of confusing alien spacecraft, there is some order to the picture above: it contains all the possible phase gadgets on four qubits: all those with one leg (the $\frac{\pi }{4}$ phases directly on the qubit wires), two legs, three legs, and the single four-legged one. All the gadgets with an odd number of legs have a phase of $\frac{\pi }{4}$, and all the gadgets with an even number of legs have a phase of $-\frac{\pi }{4}$. Eq. (10.26) is a genuinely new diagrammatic equation, a type of equation we call a spider-nest identity. As we will see in this chapter and the next, there are many uses of such equations. As a first application, note that if we bring the four-legged phase gadget to the other side of the equation that this says that whenever we have a four-legged gadget with a $\pm \frac{\pi }{4}$ phase, we can replace it by a collection of 14 three-, two- and one-legged phase gadgets involving all of the four-legged phase gadget’s legs. In fact, we can decompose any $n$-legged phase gadget with a phase of $\pm \frac{\pi }{4}$ into a collection of phase gadgets with a most 3 legs. For instance, when $n=5$:

So while we would a priori think that we could need $O(2^n)$ different phase gadgets, one for each possible parity, we see that we actually only need $O(n^3)$, only those with at most three legs. A different use-case for Eq. (10.26) is that we can use it to optimise the number of $T$ gates needed for a circuit. When we have a collection of phase gadgets with $\frac{\pi }{4}$ phases we can look for any subset of four qubits that has many phase gadgets and then use a version of Eq. (10.26) where we have those phase gadgets on the left and all the other parities on the right. Then by applying this equation we essentially ‘toggle’ which phase gadgets on these four qubits were present. As long as we started out with at least half of all the possible phase gadgets present, so at least 8, we end up with fewer phase gadgets. If we had 8 phase gadgets, then we get $15-8=7$ phase gadgets at the end. If we had $10$, then we end up with $15-10=5$ of them. The exact phases, whether $+\frac{\pi }{4}$ or $-\frac{\pi }{4}$ is not important for this, since if the signs don’t match, this just introduces a $\frac{\pi }{2}$ Clifford phase gadget.

10.3.1 Spider nests as strongly 3-even matrices

Using scalable ZX notation, we can represent a collection of phase gadgets using a parity matrix to describe the connectivity of the gadgets as in (10.19). The 4-qubit spider nest identity of Eq. (10.26) with 15 gadgets (more specifically, the modified version of Exercise 10.4 where all the phases are $+\frac{\pi }{4}$ so that we can get rid of the repeated rows) then corresponds to the following $15\times 4$ matrix:

Note that we write here the transpose of the matrix to use the space on the page a bit better. Any spider nest identity will be an identity of the form:

This means that when hunting for such identities, we are really looking for a particular type of boolean matrix. To find out what kind of matrices we need, we need to look at the pseudo-Boolean Fourier transform again. This time however, we want to translate phase gadgets back into controlled phase gates. The ‘inverse’ of the equation (10.25) which relates an AND to a sum of XORs is given by:

Here $[n]:=\{1,\dots ,n\}$, and $|S|$ is the number of elements of $S$. Hence, each term ${\prod <!--\; FUNCTION\; APPLICATION\; -->}_{i\in S}{x}_i=x_{i_1}\wedge \cdots \wedge x_{i_k}$ has a weight that is a power of $2$ in the decomposition. Now, if we are considering this in a phase polynomial, where our phase gadget has a coefficient of $\frac{\pi }{4}$, then in the decomposition the different terms will have a weight of $\pm 2^{|S|}\frac{\pi }{8}$. Since these are phases, we are working modulo $2\pi$ so that when $|S|>3$ each term is a multiple of $2\pi$ and disappears:

Hence, each phase gadget corresponds to a collection of $T$ gates (the linear terms), CS gates (quadratic terms) and CCZ terms (cubic terms).

If instead of a single gadget we have a collection of phase gadgets, then we can add together the respective $T,$ CS and CCZ gates of their decompositions. It turns out that such a circuit can only be equal to the identity if all the gates cancel in the trivial way. That is, each qubit should have a number of $T$ gates that is multiple of 8 since $T^8=I$, each pair of qubits should have a multiple of 4 CS gates and each triple should have an even number of CCZ gates.

From Eq. (10.31) we see that if a phase gadget involves the qubit $j$, that then a $T$ gate appears on that qubit. If it connects to both qubits $j_1$ and $j_2$ then there will be a CS gate on those qubits, and similarly a CCZ appears when the qubits $j_1,j_2$ and $j_3$ are in the phase gadget. Hence, a collection of phase gadget implements the identity when each qubit is part of $0\text{mod }8$ gadgets ($T^8=I$), each pair of qubits is part of $0\text{mod }4$ gadgets (${\text{CS}}^4=I$), and each triple is part of $0\text{mod }2$ gadgets (${\text{CCZ}}^2=I$). We can formalise this cancellation property as follows.

When we represent a collection of $\pi ∕4$ phase gadgets as a set of bit strings ${\overrightarrow{y}}^1,\dots ,{\overrightarrow{y}}^m$, where $y_i^l=1$ means the $l$th phase gadget is connected to the $i$th qubit and set the matrix $M_i^j=y_i^j$ we see that $M$ is strongly 3-even precisely when the gadgets make a spider nest.

Being just 3-even, as opposed to strongly 3-even, is a weaker condition that means the collection of gadgets is not exactly equal to the identity, but instead are equal to some Clifford unitary: instead of the $T$ gates exactly cancelling due to them appearing a multiple of $8$ times, they only appear a multiple of $2$ times on each qubit and hence combine into $T^2=S$ gates, which are Clifford. Similarly, the CS gates appear an even number of times to create CZ gates, and the CCZ gates still completely cancel. For convenience we will also call a set of gadgets that is equal to a Clifford (and hence corresponds to a 3-even matrix) a spider nest identity. We can find which Clifford it implements by rewriting all the gadgets using Eq. (10.31). However, if we have gadgets with many legs this can involve exponentially many terms. There is also an efficient way to do it.

10.3.2 Proving all spider nest identities

We can now see when a collection of phase gadgets is a spider nest identity: check whether its associated parity matrix is strongly 3-even. Diagrammatically this is not very satisfying however, as it doesn’t tell us how to find strongly 3-even matrices or what is required to diagrammatically prove all these identities. In this section we will see that we can build all spider nest identities from one particular one. To do so, we need to go back to the 4-qubit spider nest Eq. (10.26) which we arrived at by decomposing the ‘trivial’ phase polynomial $e^{2\mathit{\pi i}{x}_1\cdots x_4}$ into phase gadgets using Eq. (10.25). We can similarly get a 5-qubit spider nest by decomposing $e^{4\mathit{\pi i}{x}_1\cdots x_5}$. This then will have $2^5-1=31$ different phase gadgets. Note the factor of $4\pi$ instead of $2\pi$ which is needed to get a collection of $\pm \frac{\pi }{4}$ phases instead of $\pm \frac{\pi }{8}$ phases. We can in the same way build an $n$-qubit spider nest by decomposing $e^{2^{n-3}\mathit{\pi i}{x}_1\cdots x_n}$, which will result in a spider nest with $2^n-1$ phase gadgets with a $\pm \frac{\pi }{4}$ phase. Now, let’s take the 5-qubit spider nest, and then ‘subtract’ the 4-qubit spider nest from it:

Here on the left-hand side we first have all the phase gadgets on five qubits, but then we subtract from those all the phase gadgets that don’t act on the first qubit. On the right-hand side we are then left with precisely those phase gadgets that do involve the first qubit. These are hence the parities like $x_1$, $x_1\oplus x_2$, …, $x_1\oplus x_2\oplus x_3\oplus x_4\oplus x_5$. Since these parities can involve any combination of the other four qubits, there are $2^4=16$ such parities (or alternatively you can see that we subtract $15$ parities from $31$ parities in Eq. (10.33) to arrive at $16$ parities).

It is this 16-gadget identity (10.33) that turns out to generate all the other ones. We need to do some work to see that though. The first step is to construct such collections of phase gadgets in a more systematic way.

Intuitively, this inductive definition results in a phase gadget connecting the single input wire to every subset of the output wires. For example:

where the last step follows from applying strong complementarity to the marked spider pair, and then applying spider fusion $(\mathrm{sp})$ as much as possible. Let’s formalise this intuitive explanation of $s_n$ using scalable notation. Let $B_n$ be the $n\times 2^n$ matrix whose $2^n$ rows consist of all $n$-bit strings. That is, the matrix defined inductively as follows:

where $\overrightarrow{0}$ and $\overrightarrow{1}$ are respectively the column vectors of all $0$’s and all $1$’s. For example, we have:

Now, we can put $s_4$ in a circuit and it can represent exactly the 16-gadget 5-qubit identity (10.33):

By plugging into all the inputs and yanking the first output to be an input we can present this in a slightly simpler way:

We call this the (S4) rule, and it is enough to prove all the spider nest identities. First, let’s note that because $s_4$ disconnects, all the $s_n$ for $n\ge 4$ also disconnect.

In Eq. (10.38) we used $s_4$ to represent the spider nest consisting of all gadgets connected to the first qubit. By using $s_n$ for $n\ge 4$ and using Lemma 10.3.5 we see then that the collection of all gadgets on $n+1$ qubits that are connected to the first qubit is also an identity. We can generalise this to the set of all gadgets connected to the first $k$ qubits. To do this, note that if we connect $s_n$ to an X-spider on the left that we obtain the following:

where $1$ is the $k\times 2^n$ matrix where every entry is 1. Hence, to represent a connection to the first $k$ qubits, we can just compose $s_n$ with an X-spider on its inputs. This then also leads to an identity:

Note that the special case of $k=0$ gives us the set of all phase gadgets on a set of wires, like the 15-gadget identity (10.26) (in that case $B_n$ has 16 rows, but the all-zero row of $B_n$ corresponds to an unconnected phase that can be removed as a scalar). As it turns out, every spider nest identity can be decomposed into a composition of the identities of the form (10.42), and so (S4) indeed suffice to prove all of them. To show this we will need some more machinery however.

10.3.3 Spider nests as Boolean polynomials

In the previous sections we saw that we can reduce a collection of phase gadgets to a series of bit strings denoting the connectivity of the gadgets:

Here we are ignoring the phase gadget with a $\frac{\pi }{2}$ phase, as it is Clifford. We saw in Eq (10.19) that these bit strings can be stored in one big matrix and in this way we can efficiently write down a collection of gadgets in scalable notation. Storing them all in a matrix is however not the only way in which we could capture the information of a set of bit strings. We could instead represent them using its Boolean indicator function. That is, to a set of bit strings $S\subseteq 𝔽2^n$ we associate the function $f_S:𝔽2^n\to 𝔽2$ defined by $f_S(\overrightarrow{y})=1$ iff $\overrightarrow{y}\in S$. We should note two important details about representing a collection of gadgets by its indicator function. First, this representation cannot deal with repeated gadgets / bit strings, and so this does not capture the exact phase of the gadgets (whether it is $+\frac{\pi }{4}$ or $-\frac{\pi }{4}$ for instance). This means that when representing a collection of gadgets by its indicator function that we only represent it up to some Clifford information. Second, because $\overrightarrow{0}$ corresponds to a phase gadget not interacting with any qubit, we don’t care about the value of the function at this value. It would hence be more accurate to write the functions as $f:𝔽2^n\setminus \{\overrightarrow{0}\}\to 𝔽2$, but we will ignore this detail for now. Any Boolean indicator function $f:𝔽2^n\to 𝔽2$ corresponds to a collection of phase gadgets: a gadget with connectivity $\overrightarrow{y}$ is in the collection if $f(\overrightarrow{y})=1$. Some collections of gadgets are spider nests, so let’s call $f$ a spider-nest function when its corresponding collection of gadgets forms a spider nest (up to a possible Clifford unitary). I.e. if a collection of bit strings $S$ forms the rows of a 3-even matrix, then $f_S$ is a spider-nest function. The indicator function of the 4-qubit spider nest of Eq. (10.26) is the constant function $1_4:𝔽2^4\to 𝔽2$ that always returns 1, since every phase gadget is part of the spider nest. The 5-qubit spider nest of Eq. (10.38) that contains all the gadgets using the first qubit has as indicator function $X_1:𝔽2^5\to 𝔽2$ that maps $X_1(\overrightarrow{y})=y_1$, since any bit string $\overrightarrow{y}$ is part of the set of gadgets if $y_1=1$. The spider nest of Eq. (10.42) that uses all gadgets touching the first $k$ qubits has indicator function $X_1\cdots X_k:𝔽2^{k+n}\to 𝔽2$, which acts as $X_1\cdots X_k(\overrightarrow{y})=y_1\wedge \cdots \wedge y_k$. These spider-nest functions are examples of Boolean monomials. A monomial is a function constructed by multiplying simple bit-indicator functions $X_j$ together. For instance $X_1{X}_3{X}_4(\overrightarrow{y})=X_1(\overrightarrow{y})\cdot X_3(\overrightarrow{y})\cdot X_4(\overrightarrow{y})=y_1\wedge y_3\wedge y_4$. We call the number of bit-indicator functions in such an expression the degree of the monomial. For instance the spider-nest function $X_1\cdots X_k$ has degree $k$. It turns out that in general, any monomial of degree at most $n-4$ corresponds to a spider-nest identity. Indeed, $X_1\cdots X_k:𝔽2^{k+n}\to 𝔽2$ for $n\ge 4$ is a spider-nest function. By permuting the qubits these give us all monomials of degree at most $n-4$. The number 4 in $n-4$ comes from the fact that the smallest spider-nest identity, corresponding to the Boolean function $1_4$ acts on four qubits. Note that the spider-nest functions form a linear space: suppose that both $f_{S_1},f_{S_2}:𝔽2^n\to 𝔽2$ correspond to spider nests. Then if we take the composition of all the phase gadgets with parities in $S_1$ and that of $S_2$ we end up with a new set of phase gadgets covering all the parities in $S_1$ and of $S_2$. However, the gadgets that are in both $S_1$ and $S_2$ will fuse and hence get a Clifford phase. We are ignoring the Clifford unitaries, so we see then that the collection of non-Clifford phase gadgets corresponds to the symmetric difference $S_1\mathrm{\Delta }{S}_2$. The indicator function is then $f_{S_1\mathrm{\Delta }{S}_2}=f_{S_1}\oplus f_{S_2}$. As this XOR of functions is just the sum in $𝔽2$, we see that any sum of spider-nest functions is again a spider-nest function, so that the spider-nests form a linear subspace of all Boolean functions. In particular, we can take a sum of monomials that are all spider-nest functions and create a Boolean polynomial that is a spider-nest function. Any Boolean function $f:𝔽2^n\to 𝔽2$ can be written in a unique way as a polynomial $f={\oplus <!--\; FUNCTION\; APPLICATION\; -->}_{\overrightarrow{a}}{\lambda }_{\overrightarrow{a}}{X}_1^{a_1}\cdots X_n^{a_n}$ where ${\lambda }_{\overrightarrow{a}}\in 𝔽2$ are the coefficients that determine which monomials are in the decomposition of $f$. The degree of a polynomial is then the maximum degree of its monomials. As a sum of spider-nest functions is still a spider-nest function, we then see that any Boolean polynomial of degree at most $n-4$ is a spider-nest function. What about the converse? Does any spider-nest function correspond to a degree at most $n-4$ polynomial?

We then see that we have proven the following.

We see then that when we restrict to just thinking about what we can do with diagrams, all the complexity of strongly 3-even matrices and degree $n-4$ Boolean polynomials reduces to just adding (S4) to the Clifford rules. Do note though that in the proof above we needed to know about Boolean polynomials and its decomposition into low-degree monomials in order to find which rewrites we should be applying to prove the spider-nest identity. In addition, the matrices corresponding to the monomials $M_j$ might contain exponentially many rows, and hence this rewriting is not efficient. In fact, it seems very likely that an efficient rewrite strategy for spider nests should not exist (see Exercise 10.9). Forgetting about all these details again, we can see that we can rephrase this result into a completeness result, which very neatly ties in some of the earlier completeness results we have seen.

10.4 Advanced T-count optimisation

We have now seen that there is a large number of configurations of $T$ gates that actually correspond to Clifford circuits. Getting rid of non-Clifford parts of a circuit is usually a good thing, as we’ve seen that we can do a lot of rewriting and simplification with the Clifford parts of a circuit. In addition, as we will see in Chapter 11, the $T$ gate in particular is quite costly to implement in many fault-tolerant architectures, and so we want to include as few of them as possible. The spider-nest identities suggest a simple rewrite strategy to optimise the number of $T$ gates in a Clifford+$T$ circuit. First, since spider nest identities apply to a collection of phase gadgets, and hence to CNOT+$T$ circuits, we need to split up our Clifford+$T$ circuit into CNOT+$T$ subcircuits. We can view the Clifford+$T$ gate set as consisting of CNOT, Hadamard, $S$ and $T$. Of these, only the Hadamard is not in the CNOT+$T$ set, and so we need to ‘split our circuit on Hadamards’. Then, pick a number of identities, preferably not containing too many gadgets and not acting on too many qubits. We want to see where in the CNOT+$T$ circuit we can apply an identity so that it reduces the $T$-count. This is done as described in the beginning of Section 10.3: for each identity in our list, we check whether more than half of the gadgets are present in the circuit. If this is the case, then we add all the gadgets from the identity to the circuit, which by gadget fusion makes the matching gadgets already present in the circuit into Cliffords, and adds the other gadgets as non-Cliffords. This is repeated greedily until none of the identities has an overlap of more than half with the gadgets present in the circuit. Note that if we have $n$ qubits in our circuit, then to match an $m$-qubit spider-nest identity, we need to check $\left(\genfrac{}{}{0.0pt}{}{n}{m}\right)$ different groupings of $m$ qubits to see whether the identity ‘matches’ there. Hence, as long as $m$ is bounded, the complexity of this algorithm is polynomial: $O(n^m)$. In practice, only checking spider nests with up to $5$ qubits, and using a simple heuristic based on the ‘density’ of the number of gadgets on a set of qubits, the run-time can be made quite reasonable. Of course such an algorithm is only a heuristic, and is heavily dependent on the type of identities we include in our search, and since we are applying the identities greedily, you might get stuck in a local optimum. The problem of optimisation of CNOT+$T$ circuits using spider nests is actually related to two well-known problems in computer science, which offer interesting and useful perspectives on this problem.

10.4.1 Reed-Muller decoding

We have seen that $n$-qubit spider nests correspond to Boolean polynomials of degree at most $n-4$. In addition, we have a correspondence between Boolean functions $f$ and collections of spider nests specified by their parities as $\{\overrightarrow{y}|f(\overrightarrow{y})=1\}$. Let’s call the set of all $n$-bit Boolean functions $B_n$, and the set of $n$-bit spider-nest functions $S_n\subseteq B_n$. Now, if we naively implement the set of gadgets corresponding to $f$ by just implementing each of the gadgets in turn, then this will require $|f|:={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{\overrightarrow{y}\ne \overrightarrow{0}}f(\overrightarrow{y})$ number of $T$ gates. We call $|f|$ the Hamming weight of $f$. It is the number of $1$s in $f$’s truth table. Note that we do not include $f(\overrightarrow{0})$ in this sum, as this corresponds to the trivial phase gadget not connected to any qubit. However, we don’t have to naively implement $f$, because we know that all $g\in S_n$ are actually free to implement: these correspond to Cliffords and hence do not require any $T$ gates. Instead of directly implementing $f$, we can implement $f\oplus g$, which corresponds to applying the spider nest identity of $g$ to the collection of gadgets of $f$. The cost of this implementation will then be $|f\oplus g|$. To implement $f$ with as few $T$ gates as possible we are hence looking for a $g\in S_n$ such that $|f\oplus g|$ is minimal. Let’s state this problem again in a slightly different way, and a bit more abstractly. We have a vector space $V$ with a specified subspace $S\subseteq V$. Given a vector $v\in V$, we want to find the closest $s\in S$ to $v$, i.e. such that $v-s$ is as small a vector as possible (in some norm). This is known as a linear decoding problem, where $S$ is our code space consisting of code words $s\in S$, and $v$ is our ‘noisy message’ we are trying to decode. We will spare you the details for now, as we will have a lot more to say about linear codes in Chapter 11. In our case the subspace $S_n$ consists of the spider-nest functions, which we know to be all the degree $n-4$ Boolean polynomials. This code space actually has a name: it is the degree $n-4$ Reed-Muller code, and hence optimising the $T$-count of a CNOT+$T$ circuit corresponds to decoding the Reed-Muller code. To summarise this optimisation approach now a bit more concretely: We start with a unitary $U$ that is built out of phase gadgets with phases that are multiples of $\frac{\pi }{4}$. We take its corresponding Boolean function $f\in B_n$. We then find the ‘closest’ degree $n-4$ polynomial $g\in S_n$ such that $|\overrightarrow{f}\oplus g|$ is as low as possible (corresponding to decoding the Reed-Muller code). We then implement the circuit $U^{\prime }$ corresponding to $f\oplus g$ by composing its phase gadgets. We know that $U$ is equal to $U^{\prime }$ up to some Clifford. We find the Clifford $C$ such that $U=U^{\prime }C$ (see Exercise 10.6). Then $U^{\prime }C$ is our new circuit, and this has $T$-count $|f\oplus g|$. Reed-Muller codes are used a lot in practice and their decoding problem has been extensively studied. So in principle we could use such a decoder to optimise the T-count of a circuit. However, the codes that are used in practice mostly have a size, corresponding in our case to the number of qubits $n$, that is not too large. However, we don’t want to restrict to just small $n$, so that is a problem. Decoding Reed-Muller codes for large $n$ is believed to be a hard problem, so we don’t expect there to be an efficient algorithm to optimally minimise the T-count of a CNOT+$T$ circuit. For optimising the T-count of general Clifford+$T$ circuits (that are allowed to contain Hadamards), there is a simple argument to see that T-count optimisation is NP-hard.