Chapter 7
Universal circuits

We will now turn from studying Clifford circuits to universal ones. Whereas the Clifford circuits were generated from CNOT, H, and S gates, we can obtain an exactly universal set of gates by replacing the $S:=Z[\frac{\pi }{2}]$ gate with the family of $Z[\alpha ]$ gates for arbitrary angles $\alpha$. Perhaps more miraculously, we can obtain an approximately universal set of gates by replacing $S$ with some fixed phase gate $Z[𝜃]$ for any $𝜃$ that isn’t a multiple of $\pi ∕2$, the most popular choice being $T:=\sqrt{S}=Z[\frac{\pi }{4}]$. This tiny tweak takes us from the safe, efficient world of Clifford circuits to the wild and wonderful world of full-powered quantum computation. Given we can no longer efficiently compute the outputs of a universal quantum circuit with a classical computer, one might wonder how much we can still reason about these circuits. In this chapter we’ll see that the answer is, perhaps surprisingly, quite a lot! In this chapter we will see two different ways to think of universal circuits: path sums and Pauli exponentials. Path sums are an extension of the idea of phase polynomials. We already briefly encountered phase polynomials in Chapter 5 when discussing the AP normal form. In the same way that we could fully characterise a CNOT circuit as a parity matrix in Chapter 4, it turns out we can fully characterise a circuit consisting of CNOT gates and phase gates as a phase polynomial together with a parity matrix. However, this representation only deals with Hadamard-free circuits. To also work with Hadamards we need path sums. We can write the action of a Hadamard as $|x⟩{\sum <!--\; FUNCTION\; APPLICATION\; -->}_y{(-1)}^{x\cdot y}|y⟩$. In a path sum we interpret this as introducing a new variable $y$ on your qubit, and adding a term ${(-1)}^{x\cdot y}$ to your phase polynomial. The final expression for your circuit then contains a sum ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_y$ over all the different ‘paths’ a computational basis state can take trough your circuit. On the other hand, Pauli exponentials offer quite a different perspective on universal circuits. We have seen in the previous chapters that there is a whole lot to be said about the Pauli gates. They allow us to define stabiliser theory and Pauli projections, which lead to the idea of stabiliser states and Cliffords, which have a rich rewrite theory and will allow us to define quantum error correction in Chapter 11. But on the other hand the Clifford computation we have seen is efficiently classically simulable, so if we want to get our money’s worth with a real quantum computer, we had better do something more than just Cliffords. Luckily we don’t have to look far, we can still work with Paulis, but just in a slightly modified form. It turns out that for any Pauli $\overrightarrow{P}$ we can construct a family of unitaries out of it by considering the matrix exponential $e^{\mathit{i𝜃}\overrightarrow{P}}$ for phases $𝜃\in ℝ$. The resulting Pauli exponentials form a universal gate set for quantum computing. Certain Pauli exponentials also correspond to the native gate set of several types of quantum computers, like ion traps and superconducting quantum computers. In fact, Pauli exponentials form arguably the native gate set to understand quantum computation. They have a natural relation to Clifford computation; the number of them in a circuit directly corresponds to the cost of classically simulating a quantum computation; Hamiltonian simulation can be directly understood in terms of Pauli exponentials; Pauli exponentials can be readily understood in certain quantum error correcting codes like the surface code; and finally, which is important for us, Pauli exponentials have a very natural representation in the ZX-calculus.

7.1 Path sums

7.1.1 Phase polynomials

First, let us recap what we know about phase polynomials. Lets begin with a neat trick that works for any circuit built only out of CNOT and Z-phase gates. We already learned back in Chapter 4 that CNOT circuits correspond to parity maps, i.e. linear maps which send basis states to other basis states that can be described as the parities of input variables. We also saw that a convenient way to compute the parity map is to label each input wire with a distinct variable and simply push those variables through the circuit:

That is, we start with only the input wires labelled and work from left to right. When a CNOT is encountered, we label the output of the control qubit with the same label as the input of the control qubit and label the output of the target qubit with the XOR of the labels on the two input qubits. In fact, this is the same as computing the overall parity matrix by doing one primitive row operation (i.e. CNOT gate) at a time. Indeed if we look at the action of the unitary $U$ described in (4.1), it maps basis states to an XOR of basis states given by the expression on the output wires:

We also saw in Chapter 4 that any two CNOT circuits computing the same parity function are equal. By re-synthesising a circuit according to its parity function, we can often find a much more efficient implementation. In the example above, we can implement the unitary $U$ with just one CNOT gate:

Now, lets sprinkle some Z-phase gates into the circuit (4.1) above:

Note that we left the parity labels on the wires. Why are we justified in doing that? Z-phase gates are diagonal in the Z basis, so they preserve basis elements, up to a phase which depends on the basis element $|x⟩$:

We can now plug a single computational basis element $|x_1,x_2,x_3⟩$ into (7.4) and track its progress through the circuit. Applying the first two gates, we see the CNOT first updates the variables in the ket, then the Z-phase gate introduces a new phase, which depends on whether $x_2\oplus x_3$ is $0$ or $1$:

Continuing this through the rest of the circuit, the overall expression we get for the unitary $V$ described by circuit (7.4) is:

More generally, any CNOT+phase circuit yields a unitary of the form:

for some ${𝔽}_2$ matrix $L$ and function $\varphi :{𝔽}_2^n\to ℝ$. We already met the parity matrix $L$, which describes $U$’s action on basis vectors as an ${𝔽}_2$-linear map. To this we add $\varphi$, which is called the phase polynomial. This describes the phase associated with each input as a polynomial over XOR’s of the input bits. Just as we could read the parity map off the labelled CNOT circuit (4.1), we can read both the parity map and the phase polynomial off of the labelled circuit (7.4). As before, we can read the parity map off the output wires. For the phase polynomial, we introduce a term of $\alpha \cdot (x_{j_1}\oplus \dots \oplus x_{j_k})$ for each Z-phase gate $Z[\alpha ]$ occurring on a wire labelled $x_{j_1}\oplus \dots \oplus x_{j_k}$. We can now come up with a new circuit that implements the same parity map and phase polynomial. We will give a reasonably efficient, general-purpose circuit synthesis algorithm for this in Section 7.2, but for now lets just focus on our example. We already saw that, by ignoring the phase gates, we could produce a very efficient circuit (4.3) to implement the parity map $|x_1,x_2,x_3⟩\mapsto |x_1,x_2\oplus x_3,x_3⟩$ of the unitary $V$. In order to get the full unitary, we should inspect the phase polynomial of $V$:

Going term-by-term, it looks like we need to place Z-phase gates on wires labelled with the expressions $x_2\oplus x_3$, $x_1\oplus x_2$, and $x_2$. Inspecting the circuit in (4.3), we see that we already have wires labelled by $x_2\oplus x_3$ and $x_2$. Unfortunately, $x_1\oplus x_2$ is missing. However, we can temporarily make this parity available by introducing a redundant pair of CNOT gates:

We can then recover the full circuit for $V$ by placing Z-phase gates $\alpha +\gamma$ on any wire labelled $x_2\oplus x_3$, $\beta$ on $x_1\oplus x_2$ and $𝜃$ on $x_2$:

By computing the phase polynomial and re-synthesising, we reduced the circuit (7.4), which had 6 CNOT gates and 4 Z-phase gates to (7.6), which has 3 CNOT gates and 3 Z-phase gates, giving a significant savings. Notably, if two phases occur at the same parity, even in totally different parts of the circuit, their angles add in the phase polynomial. Hence they can always be re-synthesised into the same phase gate. This phenomenon is called phase-folding, and is one of the major advantages of the phase polynomial approach. For example, two phase gates in different parts of circuit (7.4) contributed a single term $(\alpha +\gamma )\cdot (x_2\oplus x_3)$ to the phase polynomial in (7.5). When we re-synthesised the circuit in (4.3), they became a single phase gate.

7.1.2 Phase gadgets

Phase polynomials give a very powerful, efficient way to manipulate CNOT+phase circuits. Some might even (blasphemously!) suggest that they are more effective than graphical techniques for many applications. However, it is nevertheless useful to see how these structures are reflected in the ZX-calculus. Along the way, we will meet certain little ZX diagrams called phase gadgets, which correspond exactly to the terms in a phase polynomial. We’ll meet phase gadgets a lot in the coming chapters, as they are really useful tools for lots of different applications, so it is worth spending some time now getting a handle on how and why they work. In this section, we’ll see how phase polynomials and in particular phase-folding show up graphically. Note that in some cases phase folding follows trivially from an application of spider fusion. For example, this circuit:

gives the following unitary:

We see that the phases $\alpha$ and $\beta$ combine in the phase polynomial. This can also be seen by commuting the $\alpha$ phase gate through the control wire of the last CNOT gate via spider fusion:

However, as we saw in the last section, phases can merge together even in completely different parts of the circuit. In this case, there is no obvious way to apply spider fusion to merge them. Hence, we’ll need to develop a generalisation of spider fusion, which allows distant phases in a CNOT+phase circuit to find each other. Let’s start with a slight variation on the example from the previous section:

All we’ve done is add one more CNOT gate at the end to make the overall parity map $L$ trivial. This unitary is now diagonal in the computational basis. That is, if we wrote down its matrix, it would only have a bunch of phases down the diagonal, as described by the phase polynomial. Explicitly, the circuit above implements the following unitary:

This circuit has 4 unknown, possibly non-Clifford phases in it, so none of the strategies we’ve studied so far let us reduce the whole circuit to any kind of normal form. However, what we can do is unfuse the unknown phases:

Now, we can treat the 4 wires connecting to unknown phases as outputs of the diagram and apply the simplification strategy we used back in Chapter 4 for CNOT circuits to the rest of the (phase-free) ZX-diagram. This diagram where we treat the phases as additional outputs is an isometry, and so after simplifying, we’ll get a parity normal form which only has Z spiders adjacent to inputs and only has X spiders adjacent to outputs and our 4 phases. Here’s what this gives:

Here, the actual output wires have all ended up with a 2-legged X spider, i.e. an identity map. This corresponds to the fact that the parity map $L$ is trivial. We will refer to this reduced form as the phase gadget form of a ZX diagram. These are so named after phase gadgets, which are little compound creatures consisting of a Z phase spider connected to a phase-free X spider with $k$ additional legs:

We will often treat these two spiders together as a single node in our diagram. Seen as a map with $k$ inputs and 0 outputs, a phase gadget takes a computational basis state to its XOR, then depending on whether the XOR is 0 or 1, this produces a scalar of either $1$ or $e^{\mathit{i\alpha }}$. To see this, lets first think about a 1-legged Z spider as a map from 1 qubit to 0 qubits, i.e. it sends a single-qubit state to a number. On the computational basis, it acts as follows:

We can summarise this using a very simple phase polynomial:

Recall from Section 3.1.1 that X spiders act like XORs on computational basis states, up to a scalar factor:

Putting these two together, we see that the phase gadget itself does this:

In order to get a unitary map from a phase gadget, we can use a bunch of Z spiders to make a copy of the basis state. One copy is sent to the phase gadget and one copy is output. This results in the following diagonal unitary:

Note that we have suppressed a ${\sqrt{2}}^{(k-1)}$ scalar factor. Since we’ll be working with unitaries in the rest of this section, we’ll just assume the overall scalar is chosen to make everything unitary. Returning to (7.9), we can see that this diagram can be seen as a composition of unitaries of the form of (7.11):

Each of these phase gadget unitaries contributes one term to the phase polynomial:

But there’s some redundancy here. As we noted in the previous section, $\alpha$ and $\gamma$ are applied to the same parity of input variables $x_2\oplus x_3$. By inspecting the phase polynomial, we can see that the unitary can be more compactly represented by just 3 phase gadgets:

To see this graphically, we would need a ZX rule that lets us “fuse” the phases on phase gadgets connected to an indentical set of wires. We indeed have such a rule, which we call the gadget fusion rule:

It is in fact a derived rule, which follows from the usual spider fusion rule and strong complementarity:

Since the $\alpha$ and $\gamma$ phase gadgets connect to the exact same spiders in (7.9), we can apply $(\mathbf{\text{gf }})$ directly to this diagram to simplify it:

Now, by unfusing spiders, we can see exactly the decomposition into phase gadget unitaries from (7.12). We can also directly read the phase polynomial from the diagram:

We computed the phase gadget form (7.9) by appealing to the simplification strategy for CNOT circuits from Chapter 4. However, there is a more direct way we can translate CNOT+phase circuits into circuits of phase gadgets, by studying the way that phase gadgets commute with CNOT gates. There are a few cases to think about here. First, is the trivial case where a phase gadget and CNOT gate share no qubits. Obviously these commute. Only slightly harder to see is if a phase gadget appears on the control qubit (i.e. the Z spider) of a CNOT gate. Then, commutation follows from spider fusion:

If the phase gadget overlaps with the target qubit (i.e. the X spider) of a CNOT gate, we can still push a phase gadget through, but it picks up an extra leg:

Just by reading the equation above in reverse, we can also see what happens when a phase gadget overlaps with both qubits of the CNOT gate. It loses a leg:

7.1.3 Universal circuits with path sums

In the previous section, we saw that CNOT+phase circuits can be expressed compactly as phase polynomials, or equivalently using ZX diagrams with phase gadgets. Both of these gates send Z basis states to Z basis states (up to a phase), so they can’t possibly be universal. In order to get a universal family of circuits, we need to include a gate which can produce superpositions of Z basis states, like the Hadamard gate. Unfortunately, Hadamard gates break our nice phase polynomial representation. However, we can salvage things somewhat if we are willing to introduce some extra variables that don’t appear in the input state. Let’s start by re-visiting the Euler decomposition of a Hadamard gate.

Back in Section 3.2.5, we saw that there are in fact equivalent ways to write the Hadamard. One way is to unfuse the middle $\pi ∕2$ from the X spider and change its colour:

This gives us a phase gadget connecting the input and the output spiders. However, unlike the phase gadgets we’ve met so far, this one is not appearing as part of a diagonal unitary gate like the one depicted in (7.11). That is, it doesn’t seem to be connected to different qubit wires, which can then be labelled by the variables in our phase polynomials. We can fix this by unfusing some spiders:

The result is a representation of the Hadamard gate where we first prepare an ancilla in the $\text{|+⟩}$ state, then do a diagonal 2-qubit unitary, and then post-select the input qubit onto $\text{⟨+|}$. We already know how to write the middle part in terms of a phase polynomial:

Note that we didn’t supress the $\frac{1}{\sqrt{2}}$ factor coming from the phase gadget (as we did before), so technically this is only unitary up to a scalar. This will help us get the Hadamard gate on-the-nose. The Z-spider plugged into the input means we should sum over $y$:

whereas the Z-spider plugging into the output means that we should send the computational basis state $|x⟩$ to $1$ (i.e. delete it), regardless of whether $x=0$ or $x=1$:

Putting these pieces together, we see that we can write the action of a Hadamard gate as something much like the phase polynomial form from before, but now with an extra variable $y$ getting summed over:

The extra variable $y$ is called a path variable and the overall expression is called a sum-over-paths or path sum representation of the unitary. The expression we got in (7.18) may not look much like the definition of a Hadamard gate as we know it, so let’s check that this indeed gives us the right thing. First, recall that a Hadamard acts like this on computational basis states:

We can summarise this as something that looks like a path sum as follows:

That is, we pick up a $-1=e^{\mathit{i\pi }}$ coefficient when the input variable $x=1$ AND the summed variable $y=1$. However, we don’t (yet) know how to introduce the AND of two variables into a phase polynomial. We only know how to introduce XORs using phase gadgets. Thankfully, for pseudo-boolean functions, i.e. functions from bitstrings to the real numbers, these two logical operations are related by the following equation:

This equation is easy to check just by trying all of values of $x,y\in \{0,1\}$. There is a deeper reason why this (and many related) equations hold, related to the Fourier transform of a pseudo-boolean function. We’ll see more about that in Chapter 9. For now, we can see that this is exactly what we need to show that the two expressions for the Hadamard gate, equations (7.18) and (7.19), agree. This trick of replacing a Hadamard gate with phase gadgets will work for any number of Hadamard gates in a circuit. Hence, for any circuit written in the Clifford+phase gate set, we can transform it into a phase polynomial circuit, at the cost of introducing some ancillae and post-selections:

The procedure for computing the path sum expression off of a circuit with CNOT, phase, and Hadamard gates can therefore be derived from the simpler one used for CNOT+phase circuits. We start labelling wires with parities as before, but as soon as a Hadamard gate is encountered, we replace the label with a new, fresh path variable. We then add 3 new terms to the phase polynomial and sum over the path variable.

7.2 Circuit synthesis and path sums

In the previous section we’ve seen how to convert a circuit into a phase polynomial or path sum expression. Now we will see how we can go back and get a circuit back out again. First of all, why would we want to do this? The obvious first application for this is circuit optimisation. Namely, we can start with a circuit, compute its path sum expression, then re-synthesise a (hopefully smaller!) circuit that implements the same unitary. We have already met this simplify-and-extract methodology with CNOT circuits in Section 4.2, and we’ll meet it again a couple more times in this book. We saw an instance of this already in passing from circuit (7.4) to the smaller circuit (7.6). This was a simple example, so we were able to find a smaller circuit implementing the same phase polynomial in an ad hoc way before. In Section 7.2.1 we will explore some algorithms for this which work for any phase polynomial. For general path sum expressions there is no known efficient algorithm for turning it back in a circuit. We will however in Section 7.2.2 consider a specific example where we can make it work. This actually brings us to the second application for constructing circuits from these expressions: it allows you to build new circuits from a higher-level description of the circuit behaviour. In Chapter 9, we’ll look at this in more detail and see how, thanks to a bit of boolean Fourier theory, we can build circuits in the Clifford+phase gate set implementing arbitrary classical functions on quantum data using phase polynomials and the circuit synthesis techniques from this section.

7.2.1 Synthesis from phase polynomials

Just like how we were able to commandeer the phase-free simplification algorithm from Chapter 4 to simplify CNOT+phase circuits, we can (essentially) repurpose the phase-free extraction algorithm for the parity form of a ZX-diagram to extract CNOT+phase circuits from the phase gadget form. Recall that a ZX-diagram in parity form looks like a row of Z-spiders connected to a row of X-spiders, e.g.

From this form, we can associate a biadjacency matrix:

and performing Gauss-Jordan reduction of this matrix gives us a CNOT decomposition, where each CNOT operations corresponds to a primitive column operation:

Now, suppose we generalise from the parity form to the phase gadget form, i.e. we add some phase gadgets connected to the input Z-spiders:

This describes a unitary with phase polynomial expression:

The first thing we realise from inspecting (7.22) is that most of the diagram is already in parity form, except for the two phases themselves:

Writing down the biadjacency matrix, we see that we now get a tall, skinny matrix, with some extra rows at the beginning corresponding to phase gadgets:

Just like before, precomposing with CNOTs performs primitive column operations. For example, this:

corresponds to this equation of ZX-diagrams:

But note that the $\alpha$ phase is now attached to a 1-legged phase gadget, i.e. an identity X-spider. So, we can use spider fusion to pull it out:

The reason we could do that, is because our primitive column operation turned one of the rows above the line in matrix (7.24) into a unit vector. Since this means that phase gadget is now 1-legged, we can always pull it out to become a Z phase gate. The remaining bit of the diagram in phase gadget form then has a biadjancency matrix obtained by deleting the first row:

We can now create a unit vector in the first row by adding the second column to the third column:

Again, the phase gadget turns into a simple Z phase gate, which we can pull out to the left:

Now that we have no phase gadgets left, there is nothing above the line in our biadjacency matrix, so we finish off by doing normal Gaussian elimination:

This then yields as a final circuit:

We can check our work by labelling wires with parities:

Comparing this labelled circuit to the phase polynomial expression in equation (7.23), we see that we have indeed synthesised a correct circuit for this unitary. Hence, the general algorithm for synthesising a circuit from a phase polynomial expression for a unitary $U$ is the following:

1..

Form a block diagonal matrix over ${𝔽}_2$ whose columns are labelled by input variables $x_1,\dots ,x_n$, where:

• the first $k$ rows correspond to the $k$ terms in the phase polynomial, with a $1$ in column $i$ iff $x_i$ appears in that term, and
• the last $n$ rows correspond to the parity map describing $U$’s action on basis states.

2..

Perform primitive column operations (i.e. CNOT gates) until one of the first $k$ rows is reduced to a unit vector with a $1$ in column $j$

3..

Apply a phase gate to the $j$-th qubit and delete the unit vector.

4..

Repeat from step 2 until the top block of the parity matrix is empty.

5..

Synthesise a CNOT circuit corresponding to the remaining $n$ rows.

Note that step 2 will always succeed: we can reduce any non-zero row to a unit vector using primitive column operations, and since steps 2-4 always remove a row, the algorithm will terminate. However, just as we saw in the CNOT case, the size of the resulting circuit is very sensitive to which column operations are performed and in which order. In fact, here we have two kinds of decisions to make: which rows to eliminate first, and which column operations should be used to eliminate a given row? The answer to these questions will depend on what our goals are. Namely, do we want to choose operations to minimise the depth of the circuit or just the CNOT count? Or maybe it could be beneficial on our architecture to do as many phase gates in parallel as possible. For the remainder of this section, we will discuss some heuristics for achieving these goals. It may also be the case that we cannot apply CNOT gates between arbitrary pairs of qubits, but only nearest neighbours in our architecture. We discuss how to deal with this in the References of this chapter.

7.2.2 Quantum Fourier transform

While it is possible to efficiently extract a circuit from a phase polynomial description, doing the same from a path-sum description is still an open problem. For certain special cases we can try to make it work just by using raw brainpower. In this section we will find a circuit for the Quantum Fourier transform based on its description as a path sum. Recall that this unitary is for instance the magic trick that makes Shor’s algorithm work. In general, for a $d$-dimensional space ${ℂ}^d$ we define its Fourier transform as follows. Let $|0⟩,\dots ,|d-1⟩$ be the standard basis states. Then

For instance, when $d=2$ we get $|x⟩\mapsto \frac{1}{\sqrt{2}}{\sum <!--\; FUNCTION\; APPLICATION\; -->}_y{e}^{\mathit{i\pi xy}}|y⟩$, which is exactly the Hadamard. We will be interested in the case where $d=2^n$, so that the space corresponds to $n$ qubits. We should read the expression $\mathit{xy}$ then as multiplying the numbers $x,y\in \{0,\dots ,2^n-1\}$, not as taking the inner product of two bit strings. But since we do like thinking about bit strings, let’s define a translation. For a bit string $\overrightarrow{x}\in 𝔽2^n$, define $b(\overrightarrow{x}):=2^{n-1}{x}_1+2^{n-2}{x}_2+\cdots +2^0{x}_n$. Then we can write the $n$-qubit QFT as follows:

7.3 Pauli exponentials

Now we will switch to a very different way of looking at universal quantum circuits. Not as a series of logic gates that create branches of computational basis states and evolve these with phase polynomials, but as a series of applications of rotations around Pauli gates.

7.3.1 Unitaries from Pauli boxes

In Chapter 6, we introduced Pauli boxes, which gave us a way to wrap up the pair of projectors coming from a Pauli measurement into a single object. We also saw in Exercise 6.8 that these are special case of measure boxes, which can represent an arbitrary (2-outcome) measurement using a single map satisfying the following properties:

These three conditions are equivalent to the condition that the following forms a measurement:

So, we get a measurement when plugging in X spiders into the control wire. Here’s a (seemingly) random question: what happens if we plug in Z spiders? To find out, lets see what happens when we form a linear map $L$ as follows:

Thanks to the third property of measure boxes, we have:

Using the other two properties:

and similarly, $L{L}^{†}=I$. So $L$ is a unitary!

Let’s expand out what is in the Pauli box to see what these unitaries from Proposition 7.3.1 actually look like. Recall from Definition 6.2.3 that

where

Hence, for the special case of $\overrightarrow{P}=Z\otimes \cdots \otimes Z$ we get:

We get phase gadgets! For a general unitary built from Pauli boxes, we can adapt Eq. (6.8): for any Pauli string $\overrightarrow{P}=P_1\otimes \dots \otimes P_n$ with $P_i\in \{X,Y,Z\}$, we have:

The general case can be obtained by additionally representing any $P_i=I$ by simply not connecting to the $i$-th qubit. The unitaries built from Pauli boxes in this way hence generalise phase gadgets: they are just phase gadgets surrounded by some particular single-qubit Cliffords. We will call such unitaries Pauli exponentials. As the name suggests, we can view these unitaries as special cases of matrix exponentials, which we’ll introduce in the next section.

7.3.2 Matrix exponentials

We first mentioned matrix exponentials back in Section 2.2.3 as a means of constructing solutions to the Schrödinger equation, but avoided giving a formal definition. We’ll do that now. At this point, we should be pretty used to raising $e$ to the power of a complex number $z$. For instance, when $z=\mathit{i\alpha }$ is imaginary, this is how to obtain phases. If we crack open a textbook on complex analysis, we’ll see that $e^z$ for any complex number is defined as the following power series:

Swapping out the complex number $z$ for a square matrix $A$ gives us a definition for the matrix exponential:

Here the powers $A^k$ are just multiplying $A$ with itself $k$ times, and in particular $A^0=I$ is the identity matrix. There are a few things we should know about matrix exponentials. The first is that if we are working with a diagonal matrix, then its matrix exponential is just the exponential of each of its components:

This works because, when we raise a diagonal matrix to a power $k$, it just goes inside:

The second thing we need to know is that conjugation by a unitary commutes with exponentiation:

With these facts we can easily compute the matrix exponential of any diagonalisable matrix. Let $A$ be a matrix with diagonalisation $A={\sum <!--\; FUNCTION\; APPLICATION\; -->}_j{\lambda }_j|{\varphi }_j⟩⟨{\varphi }_j|$ for some ONB $\{|{\varphi }_j⟩\}$. Write $U={\sum <!--\; FUNCTION\; APPLICATION\; -->}_j|{\varphi }_j⟩⟨j|$ for the unitary that maps the computational basis $\{|j⟩\}$ into the eigenbasis $\{|{\varphi }_j⟩\}$ of $A$, and write $D={\sum <!--\; FUNCTION\; APPLICATION\; -->}_j{\lambda }_j|j⟩⟨j|=\text{diag}({\lambda }_1,\dots ,{\lambda }_n)$ for the diagonal matrix of eigenvalues of $A$. Then we have $A=\mathit{UD}{U}^{†}$. Hence, we calculate $e^A=e^{\mathit{UD}{U}^{†}}=U{e}^D{U}^{†}$. As $e^D$ is the exponential of a diagonal matrix, it is easily calculated and so we get an easy expression for $e^A$, simply by multiplying out the matrices of its diagonalisation. There is one final property of the matrix exponential we will be interested in. Remember that for regular complex numbers $z_1$ and $z_2$ we have $e^{z_1+z_2}=e^{z_1}{e}^{z_2}$. The same holds for the matrix exponential as long as the matrices commute. That is, if we have matrices $A$ and $B$ that commute, then $e^{A+B}=e^A{e}^B$. When $A$ and $B$ allow diagonalisations, this is easily proven, as we can then find a joint diagonalisation, and reduce the problem to diagonal matrices.

When $A$ and $B$ do not commute, we generally have $e^{A+B}\ne e^A{e}^B$. In fact, studying ways to approximate the value of $e^{A+B}$ using just $e^A$ and $e^B$ is incredibly important for simulating quantum mechanical systems using a quantum computer. We’ll study this problem in more detail in Section 7.5.

7.3.3 Building unitaries as exponentials

With this mathematical machinery of matrix exponentials in hand, let’s look at how it can help us understand unitary maps. Suppose we have some $n$-dimensional unitary $U$. As discussed in Section 2.1.3, a unitary is a normal linear map and hence can be diagonalised: $U={\sum <!--\; FUNCTION\; APPLICATION\; -->}_j{\lambda }_j|{\varphi }_j⟩⟨{\varphi }_j|$. Using the description above we can then also write this as $U=VD{V}^{†}$ where $V$ is some unitary and $D$ is some diagonal matrix consisting of the eigenvalues of $U$. Now remember that all the eigenvalues of a unitary are phases so that ${\lambda }_j=e^{i{\alpha }_j}$ for some phases ${\alpha }_j$. This means that $D$ is a matrix of exponentials. In the previous section we saw that the exponential of a diagonal matrix is a matrix of exponentials. The converse is however also true. We can hence write $D=e^{i{D}^{\prime }}$ where $D^{\prime }=\text{diag}({\alpha }_1,\dots ,{\alpha }_n)$. We have here taken out the factor of $i$ out of the matrix for reasons that will become clear soon enough. So now we have $U=V{e}^{i{D}^{\prime }}{V}^{†}$. We can take this conjugation by $V$ inside of the matrix exponential to get $U=e^{\mathit{iH}}$ where $H=V{D}^{\prime }{V}^{†}$. Now the eigenvalues of $H$ are precisely the values in $D^{\prime }$, which are real numbers. As we saw in Exercise 2.4 a matrix whose eigenvalues are real numbers is self-adjoint. We hence have proven the following result.

Note that $H$ is not unique: we can add $2\mathit{\pi I}$ to it and still get the same result: $e^{i(H+2\mathit{\pi I})}=e^{\mathit{iH}}{e}^{i2\mathit{\pi I}}=e^{\mathit{iH}}$. Here in the last step we used $e^{2\mathit{i\pi }}=1$. In fact, adding any multiple of the identity to $H$ just changes the global phase of $U$, and so we don’t care about it. The converse of Proposition 7.3.3 is also true: if we take some self-adjoint matrix $H$, then $e^{\mathit{iH}}$ is unitary (This follows from Exercise 2.4, as the eigenvalues of $e^{\mathit{iH}}$ will all be complex phases). This gives us a way to construct unitaries. In fact, given a self-adjoint $H$, it will be useful to consider the entire family of unitaries constructed by rescaling $H$: for any $t\in ℝ$ we have that $e^{\mathit{itH}}$ is unitary. We use the letter $t$ here, as this gives the elapsed time in the Schrödinger equation.

In this direct calculation of the matrix exponential of the Pauli $X$ we actually only used that $X^2=I$, and nothing else, so this calculation works for any matrix with this property. As this is actually quite useful, let’s record this for later.

7.3.4 Pauli exponentials

Now that we can understand any unitary as a matrix exponential, let’s zoom in a bit and take a look at Pauli exponentials. The Examples 7.3.4 and 7.31 show that we can view the $Z$ and $X$ phase gates as exponentials of Pauli matrices. It turns out that this holds for essentially all unitaries if we do the same with multi-qubit Pauli strings. A Pauli string $\overrightarrow{P}$ is just a tensor product of single-qubit Paulis $\overrightarrow{P}=e^{\mathit{i\alpha }}{P}_1\otimes \cdots \otimes P_n$ where $P_i\in \{I,X,Y,Z\}$ and $\alpha \in ℝ$ is some global phase. Since we want to take exponentials of these to construct unitaries, we want $\overrightarrow{P}$ to be self-adjoint, which requires $e^{\mathit{i\alpha }}\in \{1,-1\}$.

Here we write $𝜃$ instead of $t$, because we will be thinking of this as an angle in a rotation, instead of an elapsed time. Using Proposition 7.3.6 we calculate:

Using this, we see that an identity in a Pauli string makes the Pauli exponential act as an identity on that qubit:

We can use this to calculate a circuit that implements any Pauli exponential using gates we have already encountered. Before we do that in full generality it will be useful to consider a specific example.

The expression we got in this example, $\text{CNOT}(I\otimes Z(\mp 2𝜃))\text{CNOT}$ consists only of gates we have already encountered, and that we can in particular write as a ZX-diagram:

It is also a phase gadget! This in fact remains true if we add more qubits, by realising that a CNOT ladder sends $Z\otimes \cdots \otimes Z$ to $Z_n$:

By Exercise 7.2 such CNOT ladders with a phase in the middle are phase gadgets. As the unitaries we constructed from Pauli boxes also were phase gadgets, we see that we can now relate them:

For a more general Pauli string $\overrightarrow{P}=P_1\otimes \dots \otimes P_n$ with $P_i\in \{X,Y,Z\}$ we can use the fact that the $U_i$ from Eq. (7.30) satisfy $P_i=U_{i}Z{U}_i^{†}$ to then write any Pauli exponential as a unitary from a Pauli box: setting $U=U_1\otimes \cdots \otimes U_n$ we have $\overrightarrow{P}=\mathit{UZ}\cdots Z{U}^{†}$, and hence

Hence:

It will be helpful to introduce some shorthand for $e^{\mathit{i𝜃}\overrightarrow{P}}$. For $Z$ and $X$ phase gates we have been writing $Z(\alpha )$ for a phase rotation over $\alpha$. We have also seen that $e^{\mathit{i𝜃Z}}\propto Z(-2𝜃)$, or in other words that $Z(\alpha )\propto e^{-\mathit{i\alpha }∕2Z}$. This suggests the following notation for any Pauli string $\overrightarrow{P}$:

Here we have included a global phase for good measure, so that $Z(\alpha )$ and $X(\alpha )$ match exactly to the definition of those phase gates that we were using before. For a multi-qubit Pauli string we will again adopt the shorthand of not writing the tensor product symbol $\otimes$. So we will for instance write $\mathit{ZZ}(\alpha )$ for the unitary $e^{\mathit{i\alpha }∕2}{e}^{-\mathit{i\alpha }∕2Z\otimes Z}$. Note that replacing $\overrightarrow{P}$ by $-\overrightarrow{P}$ in a Pauli exponential is equivalent to flipping the phase of the exponential: $e^{\mathit{i𝜃}(-\overrightarrow{P})}=e^{-\mathit{i𝜃}\overrightarrow{P}}$. Hence, in the definition Eq. (7.40) we get $[{(-1)}^k\overrightarrow{P}](\alpha )\propto \overrightarrow{P}({(-1)}^k\alpha )$. For the future let’s record some useful facts now that we have this correspondence between Pauli exponentials and Pauli boxes. First, we can represent any Pauli exponential using just a small number of standard gates.

Second, we see a Pauli exponential is Clifford iff its phase is Clifford.

The condition on ‘non-trivial’ here is necessary since the trivial Pauli exponential $e^{\mathit{i𝜃I}}$ is of course just the identity gate up to global phase for any $𝜃$.

7.4 Pauli exponential compilation

Now that we know a bit about Pauli exponentials, let’s see how they help us think about quantum circuits and compilation.

7.4.1 Pauli exponentials are a universal gate set

We have already seen that $Z$ and $X$ phase gates can be represented as Pauli exponentials. This means in particular that any single-qubit unitary can be represented as a composition of Pauli exponentials. We know that single-qubit unitaries together with the CNOT gate form a universal gate set, so if we can show that the $\text{CNOT}$ gate can be built out of Pauli exponentials, then we know that all unitaries are just compositions of Pauli exponentials. It will in fact be easier to look at the $\text{CZ}$ gate. Remember that the $\text{CNOT}$ is just a $\text{CZ}$ conjugated by Hadamards on the target qubit:

As a Hadamard is just a series of $Z$ and $X$ phase gates, which are Pauli exponentials, it then indeed remains to look at the CZ.

7.4.2 Compiling to Pauli exponentials

Theorem 7.4.2 gives one way to write a quantum circuit as a series of Pauli exponentials, but if we are interested in doing this with a small number of these, it doesn’t do a very good job. There is in fact a more interesting way to transform a circuit into Pauli exponentials, which also has practical relevance in quantum compilation (see the References for this chapter). To do this we need to use what we learned in the previous chapter. There we saw that pushing a Clifford unitary $U$ through a Pauli $\overrightarrow{P}$ gives you another Pauli: $\overrightarrow{P}U=U\overrightarrow{Q}$ for some $\overrightarrow{Q}$. Now, in Eq. (7.33) we saw that conjugating a matrix exponential is the same thing as exponentiating the conjugated matrix. This can be recast as a way to commute a unitary through a matrix exponential:

So if our matrix $A$ is actually a Pauli $\overrightarrow{P}$, and our unitary $U$ is a Clifford, then we can push the Clifford through the Pauli exponential to get another Pauli exponential:

How does Eq. (7.42) help us? Well, it helps us if we put on a different pair of glasses and view our circuit not as being given by $X$ and $Z$ phase gates and CZ/CNOT gates, but instead view it as consisting of Clifford gates and non-Clifford gates. With this perspective we consider CZ, CNOT, Hadamard, $S$ and $X(\frac{\pi }{2})$ gates to all be of the same sort, namely Clifford, while the other class of gates contains any $Z(\alpha )$ and $X(\alpha )$ where $\alpha$ is not a multiple of $\frac{\pi }{2}$. These non-Clifford phase gates we can then view as Pauli exponentials (which are only acting on a single qubit). So wearing these glasses we see the circuit as a series of Clifford gates and Pauli exponentials, where each Pauli exponential corresponds to a non-Clifford phase gate:

Here each of the Clifford unitaries $U_j$ can consist of multiple basic Clifford gates like CNOT, $S$ and $H$. Now let’s pick the first non-Clifford Pauli exponential in this circuit $e^{i{𝜃}_1{\overrightarrow{P}}^1}$ and push it through $U_1$ using Eq. (7.42) to get:

Here ${\overrightarrow{Q}}^1=U_1^{†}{\overrightarrow{P}}^{1}U$. We then push $e^{i{𝜃}_2{\overrightarrow{P}}^2}$ through both $U_2$ and $U_1$ and so on, until finally we get the circuit:

The circuit now has a very different structure! We see that each non-Clifford phase gate in the original circuit, which we saw as single-qubit Pauli exponentials, is transformed into some other Pauli exponential, which can now act on any number of qubits. All the Clifford gates of the original circuit are still present here, but are now pushed all the way to the end. In Chapter 5 we saw how to optimise Clifford circuits, and in particular that those circuits can be reduced to a normal form whose maximal size only depends on the number of qubits (Proposition 5.3.12). This structure is useful for a variety of reasons that we’ll explore in this chapter, so let’s give a name to it.

We’ll often shorten this to PE form or say it is a PE circuit.

As a first result, this form gives us a bound on the number of gates we need to write down an arbitrary circuit based on the number of non-Clifford gates it contains.

Note that in most useful quantum computations (those that do calculations that we can’t efficiently do classically) we will have $k\gg n$, and hence the number of gates in Pauli exponential form scales as $O(\mathit{kn})$. Let’s zoom out a bit. Why did it make sense to view our circuit as consisting of Clifford and non-Clifford gates, instead of using a more fine-grained difference between gates? In Chapter 5 we saw that computation involving just Clifford gates is efficiently classically simulable. The power of computation must then necessarily come from the inclusion of non-Clifford gates. We can then interpret a circuit in Pauli exponential form as first doing the ‘actual’ quantum computation using the Pauli exponentials, which are all non-Clifford, and then doing some final Clifford operations to ‘post-process’ the data in the right way. This analogy of Clifford operations being a type of post-processing becomes explicit when we are working with quantum error correcting codes. As we saw in Chapter 6, Clifford operations can often be done natively in a quantum error correcting code and so are ‘free’ operations. This is in contrast to non-Clifford operations which often require more complicated techniques to do fault-tolerantly.

7.4.3 Phase folding

Okay, so we can limit the number of Pauli exponentials we need to write an arbitrary circuit. But we can do even better! Remember from Proposition 7.3.2 that if we have two commuting matrices $A$ and $B$ that then $e^{A+B}=e^A{e}^B$. It will be helpful to think of this going in the other direction as well: if we have commuting matrices, then we can combine adjacent matrix exponentials $e^A$ and $e^B$ into a single matrix exponential. In particular, if we have a circuit in PE form then there will be many Pauli exponentials $e^{i{𝜃}_j{\overrightarrow{P}}^k}$ in a row. When we then have two Pauli exponentials $e^{i{𝜃}_k{\overrightarrow{P}}^k}$ and $e^{i{𝜃}_l{\overrightarrow{P}}^l}$ right next to each other such that ${\overrightarrow{P}}^k$ and ${\overrightarrow{P}}^l$ commute we can combine them into a single exponential. This is especially helpful if ${\overrightarrow{P}}^k={\overrightarrow{P}}^l=:\overrightarrow{P}$. Then we get:

With the notation of Eq. (7.40) we can write this as $\overrightarrow{P}(\alpha )\overrightarrow{P}(\beta )=\overrightarrow{P}(\alpha +\beta )$. Using Pauli boxes we can write this as:

However, the Pauli exponentials we want to combine into one might not be next to each other, as there might be other exponentials in the way. But remember also from Proposition 7.3.2 that if $A$ and $B$ commute, that then $e^A$ and $e^B$ will commute as well. So if two Pauli strings commute, then the associated exponentiated Paulis will commute as well:

So using this we can move exponentials out of the way in order to combine the ones we want.

All of this suggests the following algorithm for reducing the number of Pauli exponentials needed to write a circuit, which we will call phase folding.

1..

Start with a circuit in PE form (Definition 7.4.5)

2..

Consider the first (leftmost) Pauli exponential $\overrightarrow{P}(\alpha )$.

3..

If there is another $\overrightarrow{P}(\beta )$ in the circuit, look at all the Pauli exponentials in between $\overrightarrow{P}(\alpha )$ and $\overrightarrow{P}(\beta )$. If $\overrightarrow{P}$ commutes with all of these, then combine $\overrightarrow{P}(\alpha )$ and $\overrightarrow{P}(\beta )$ into one $\overrightarrow{P}(\alpha +\beta )$. Do this check and combination for all Pauli exponentials of $\overrightarrow{P}$ in the circuit.

4..

Repeat the procedure for the next Pauli exponential in the circuit.

5..

Check if any of the resulting Pauli exponentials is Clifford. If so, push these Clifford ones past the Pauli exponentials as described in Section 7.4.2, resulting in a new circuit in PE form. Repeat the algorithm. If no Clifford Pauli exponentials were created in the previous steps, we are done.

7.5 Hamiltonian simulation

Back in Section 2.2.3, we mentioned briefly that the time evolution of a quantum system comes from taking the matrix exponent of a certain operator, called the Hamiltonian, which encodes all of the physical interactions going on. Now, suppose a physicist or an engineer hands us a Hamiltonian, and asks us to simulate the behaviour of a quantum system it represents. Is there a way we can do this on a quantum computer? That is, if we start in a known quantum state $|\psi ⟩$, can we use a quantum computer to efficiently transform this state into it’s time-evolved state $e^{-\mathit{itH}}|\psi ⟩$, then perform some measurements to learn something about it? It turns out, if we just want to approximate $e^{-\mathit{itH}}|\psi ⟩$, the answer is yes! One way to do this is to employ the Suzuki-Trotter method, a.k.a. Trotterization. In our case, this will let us synthesise a circuit the approximates $e^{-\mathit{itH}}$ using Pauli gadgets. $H$ is a self-adjoint operator on $n$ qubits, so a generic $H$ could take an exponential amount of data to describe. Of course, in that case, we don’t have any hope of simulating it efficiently, because even reading $H$ will take exponential time. Thankfully, lots of useful, physically meaningful $H$’s can be written as a linear combination of Pauli strings:

where $m$ is polynomial in $n$. Then, if all the ${\overrightarrow{P}}_j$ commute, we’re laughing because thanks to Proposition 7.3.2, then $U(t):=e^{-\mathit{itH}}$ splits up as a bunch of Pauli gadgets:

i.e.

We already know how to synthesise Pauli gadgets, so we can build a nice Clifford+phase circuit, parametrised by $t$, that will perform time evolution for a generic input state. Life is good. Unfortunately, if the Pauli strings in $H$ don’t commute, we can’t use Proposition 7.3.2 to turn a sum in the exponent into a product of matrix exponents. Nevertheless, we can power on and try to decompose $H$ as a product of Pauli exponentials, but we might introduce some errors along the way. We’ll start with some Hamiltonian that is the sum of just two other Hamiltonians: $H=H_1+H_2$. In order to decompose its exponential into a composition of exponentials, we would like it to be the case that:

for some $𝜖$. Note that here we introduced some new notation for approximate rewriting by writing an $𝜖$ on top of the $\approx$ sign. By definition, this means:

It turns out that the left-hand side is bounded by $t^2\kappa$ for some $\kappa >0$, and hence to make this smaller than epsilon we can choose $t$ small enough such that $t^2\kappa \le 𝜖$. To see this is true, and to find this number $\kappa$, we will need to introduce some new tools, and to understand these tools, we will first do a warm-up exercise. We will prove that

for $A$ and $B$ self-adjoint. Then in particular $\parallel e^{-\mathit{it}{H}_1}-e^{-\mathit{it}{H}_2}\parallel \le \parallel -\mathit{it}{H}_1+\mathit{it}{H}_2\parallel =|t|\parallel H_1-H_2\parallel$, so that in this case the ‘$\kappa$’ is $\parallel H_1-H_2\parallel$. Define the matrix-valued function $f(t)=e^{\mathit{itA}}{e}^{i(1-t)B}$. Then note that $f(0)=e^{\mathit{iB}}$ and $f(1)=e^{\mathit{iA}}$. We hence want to calculate the expression $\parallel f(1)-f(0)\parallel$. Now, for some of you this might bring back very old memories, but we will need to use the Fundamental Theorem of Calculus to help us simplify this. Remember that this says that $f(x)-f(y)={\int }_y^x{f}^{\prime }(t)\mathit{dt}$ where $f^{\prime }$ is the derivative of the function. This also works for matrix-valued functions, so that we get

where in the last step we used a version of the triangle inequality for integrals (which is after all just a limit of sums). So let’s calculate what $f^{\prime }(t)$ is, which we will do using the product rule ${(f_1{f}_2)}^{\prime }=f_1^{\prime }{f}_2+f_1{f}_2^{\prime }$:

Here in the last step we commuted $A$ past $e^{\mathit{itA}}$ and grouped the terms together. Now, also recall that the norm is unitarily invariant, meaning that $\parallel \mathit{UA}\parallel =\parallel A\parallel$ for any unitary $U$ and arbitrary matrix $A$. As both $e^{\mathit{itA}}$ and $e^{i(1-t)B}$ are unitaries, we can hence simplify the expression of the norm: $\parallel f^{\prime }(t)\parallel =\parallel e^{\mathit{itA}}(A-B)e^{i(1-t)B}\parallel =\parallel A-B\parallel$. Putting it all together, we see then that:

Now, for the real deal: