Chapter 2
The Quantum Circuit Model

The goal of this chapter is not to provide a comprehensive overview of quantum computation, as there are already plenty of good general-purpose books on that topic (see Section 1.1.1 for some pointers). In this chapter, we will simply lay out some of the basic ingredients from quantum theory needed to get us started working with circuits, then dive straight into their super interesting underlying structures, which will be the topic of the following chapters.

2.1 Preliminaries

In this section, we will lay out the mathematical foundations and notation which will be used throughout the book. We will introduce Hilbert spaces and various linear algebraic operations on them, and two different notations:

• Dirac notation, which is by far the most common notation appearing in the quantum computing literature. It gives a compact way to express states and transformations for a single quantum system, but starts to get clunky if we want to express lots of systems interacting with each other.
• String diagram notation: a graphical notation for expressing very general compositions of linear algebraic operations (called tensor networks). This is the main notation used in the so-called quantum picturalism approach to quantum theory, which was adopted exclusively e.g. by this book’s predecessor Picturing Quantum Processes.

Readers familiar with the mathematics behind quantum theory, but unaccustomed to string diagram notation may wish to skip ahead to section 2.1.6.

2.1.1 Some things you should know about complex numbers

Before we go into defining Hilbert spaces, we’ll need to make a couple of remarks about complex numbers. We will write $ℂ$ for the set of complex numbers, and we will often write $\lambda \in ℂ$ for an arbitrary complex number. There are two main ways to write down a complex number. The first is the familiar cartesian form: $\lambda =a+\mathit{ib}$ in terms of real numbers $a,b\in ℝ$ and $i:=\sqrt{-1}$. The second, possibly less familiar, is the polar form: $\lambda =r{e}^{\mathit{i\alpha }}$ for a positive real number $r\in {ℝ}_{\ge 0}$ called the magnitude and an angle $\alpha \in [0,2\pi )$ called the phase. Phases play an important role in quantum theory, and they are often where the ‘quantum magic’ happens, so we’ll run into the polar form a lot. These two representations are related by the trigonometric identity:

which can be visualised in the complex plane as follows:

A useful operation on the complex numbers is the complex conjugation $\lambda \mapsto \overline{\lambda }$, which flips the sign of $b$ in cartesian form or the sign of $\alpha$ in polar form:

It’s pretty straightforward to derive from (2.1) that these two operations are the same for a complex number $\lambda$. This can be visualised by realising that flipping the sign of $b$ or $\alpha$ amounts to a vertical reflection of the complex plane:

We will slightly overload the term ‘phase’, and also refer to complex numbers of the form $e^{\mathit{i\alpha }}$ as phases. If there is some ambiguity, we will call $e^{\mathit{i\alpha }}$ the phase and $\alpha$ the phase angle. Because of the behaviour of exponents, when we multiply phases together, the phase angles add:

Consequently, multiplying a phase with its conjugate always gives $1$:

More generally, we can always get the magnitude of a complex number by multiplying with its conjugate and taking the square root:

As a consequence, whenever we have $\lambda =r{e}^{\mathit{i\alpha }}$ and $|\lambda |=1$, we can conclude $r=1$ so $\lambda =e^{\mathit{i\alpha }}$. In other words, $|\lambda |=1$ if and only if $\lambda$ is a phase. Getting the angle out is a bit trickier. For this we use a trigonometric function called arg, which for $\lambda \ne 0$ is defined (somewhat circularly) as the unique angle $\alpha$ such that $\lambda =r{e}^{\mathit{i\alpha }}$. If $\lambda =a+\mathit{ib}$ for $a>0$, $\arg <!--\; FUNCTION\; APPLICATION\; -->(\lambda )=\arctan <!--\; FUNCTION\; APPLICATION\; -->(\frac{b}{a})$. This obviously won’t work when $a$ is zero, and needs a bit of tweaking when $a$ is negative. Hence, the full definition of $\arg <!--\; FUNCTION\; APPLICATION\; -->$ needs a case distinction, which we’ll leave as an exercise.

2.1.2 Hilbert spaces

A Hilbert space is a vector space over the complex numbers, with an inner product defined between vectors, which we’ll write this way:

where $\psi$ and $\varphi$ are vectors in a Hilbert space $H$. Hilbert spaces can be finite- or infinite-dimensional. For finite-dimensional Hilbert spaces, we are already done with the definition. For infinite dimensions, we need to say some other stuff about limits and convergence, but since quantum computing is all about finite-dimensional Hilbert spaces, we won’t need to go into that here. So, for our purposes, the main thing that separates a Hilbert space from a plain ole vector space is the inner product. So let’s say a few things about inner products and introduce some handy notation. First, a definition.

It might seem weird that we only ask inner products to be linear in one of the arguments. However, combining conditions 1 and 2, we can show that the inner product is actually conjugate-linear in the first argument. Conjugate-linearity is pretty much the same as linearity, but scalar multiples pop out as their conjugates:

Since a Hilbert space has an inner product, we know a bunch of things about its vectors that a plain old vector space doesn’t tell you. For one thing, the inner product tells us how long vectors are, i.e. the norm $\parallel \psi \parallel :=\sqrt{⟨\psi |\psi ⟩}$, and in particular when a vector is normalised: $\parallel \psi \parallel =1$. It also tells us when two vectors are orthogonal: $⟨\psi |\varphi ⟩=0$. Putting these pieces together we get the following.

So, an inner product defines ONBs. In particular, if we were to equip the vector space with a different inner product, then which bases you consider orthonormal will change. This also works the other way: an ONB defines an inner product, in the sense of the following exercise.

Since the inner product is linear in it’s second argument, any vector $\psi \in H$ defines a linear map ${\psi }^{†}:H\to ℂ$ by $\varphi \mapsto ⟨\psi |\varphi ⟩$, which we call the adjoint of $\psi$. As you can see from (2.3), the adjoint of a column vector $\psi \in {ℂ}^n$ is the row vector given by its conjugate-transpose:

If we have a linear map between two (possibly) different Hilbert spaces $H$ and $K$, the adjoint $A^{†}$ of $A$ is the unique linear map satisfying the equation $⟨A^{†}\psi |\varphi ⟩=⟨\psi |\mathit{A\varphi }⟩$ for all $\varphi \in H$, $\psi \in K$. This definition takes a bit of head-scratching at first, but when $H={ℂ}^m$ and $K={ℂ}^n$, this again just amounts to the conjugate-transpose of $A$:

Like with matrix transposes, one can show that adjoints satisfy ${(A^{†})}^{†}=A$ and ${(\mathit{AB})}^{†}=B^{†}{A}^{†}$. Inner products and adjoints are so ubiquitous in quantum theory that we typically build them right into the way we write vectors down. For this, we introduce Dirac bra-ket notation. Rather than writing a vector as it’s usual naked self, we’ll wrap it up into a symbol called a ket:

If we want to write the adjoint of $|\psi ⟩$, we flip the ket into a bra:

Now, the ket $|\psi ⟩$ is still secretly just $\psi$, a vector in the Hilbert space $H$. However, the bra $⟨\psi |$ is an element of the dual space $H^{\ast }$. That is, it is a linear map from $H$ to the complex numbers. In particular, we can try plugging a ket into it, and some magic happens: we get a bra-ket, which is just the inner product again.

Breaking the two parts of an inner product apart gives us some extra flexibility. For example, if we have some linear map $M:H\to H$ that we want to sandwich in the middle of the inner product, we can do that: $⟨\psi |M|\varphi ⟩$. This also leads us to more naturally think of bras and kets themselves as processes, which are dual to one-another. We can think of $|\varphi ⟩$ as a process which starts with nothing and gives us something, namely the vector $\varphi \in H$:

Conversely, we can think of $⟨\psi |$ as a process which ‘swallows’ a vector and leaves nothing (well, actually nothing but a scalar):

The pictures to the right of ‘$⇝$‘ are in string diagram notation. This gives us a way to visualise compositions of linear maps as boxes (or other kinds of shapes), connected by wires. We’ve already seen how to draw bras and kets above. The only thing missing at this point (at least until we meet tensor products in section 2.1.4) is linear maps $M:K\to L$ between two arbitrary Hilbert spaces. These are pictured as a box with an input wire labelled $H$ and output labelled $K$:

We visualise composition by plugging wires together. For example:

There’s a couple of things to note about these two different notations. First, the string diagrams give slightly more information, since the wires can be labelled to tell us which Hilbert spaces the maps are defined on. We can drop these labels when it is clear from context, but sometimes it’s handy to get an extra visual cue for which maps can be plugged together, and which can’t. Second, the Dirac notation is being read from right-to-left, whereas the pictures are being read from left-to-right. This is an artefact of the usual ‘backwards’ way composition is defined symbolically. For example, function composition $g\circ f(x):=g(f(x))$ means first apply $f$ to an element $x$, then apply $g$ to the result. In other words: $g\circ f$ means ‘$g$ AFTER $f$’. Similarly, with composition of linear maps (and hence matrix multiplications) $\mathit{BA}|\varphi ⟩$ means first apply $A$ to $|\varphi ⟩$ then apply $B$ to the result, i.e. $\mathit{BA}$ means ‘$B$ AFTER $A$’. This is not such a big deal, as long as we remember to flip the order of maps around when we write them in Dirac notation. What is more of a big deal, as we’ll see in section 2.1.4, is that most quantum computations really want to be done in 2D. Dirac notation is only really handy for working with 1D chains of matrix multiplications like the ones above, and it gets a bit clunky when we start mixing (sequential) composition of linear maps with (parallel) tensor products. On the other hand, these more general kinds of composition are what string diagrams are meant for, so this is where they really start to shine.

Another advantage of writing vectors as kets is it gives us a compact way of writing the standard basis. Namely, we write the standard basis for ${ℂ}^n$ as $\{|i⟩|0\le i<n\}$, i.e. simply as numbers in a ket, ranging from $0$ to $n-1$:

In particular, the two-dimensional Hilbert space ${ℂ}^2$ has standard basis elements written as follows:

As we’ll see in Section 2.2, ${ℂ}^2$ represents quantum bits, or qubits. In ${ℂ}^2$, the basis vectors $|0⟩$ and $|1⟩$ play the role of the classical bits $0$ and $1$. Part of the power of quantum computing is that we cannot just access these classical bit states, but also many more, coming from taking arbitrary linear combinations of them.

2.1.3 Types of linear maps

The adjoint operation ${\text{(−)}}^{†}$ lets us define a handful of special kinds of linear maps that crop up in quantum theory. This first is isometries, where the adjoint acts as a one-sided inverse.

Next, we have a whole slew of maps from a Hilbert space to itself.

There are clearly some containments here: projectors are always positive (since $M=\mathit{MM}=M^{†}M$), and positive maps are always self-adjoint (since $M^{†}={(N^{†}N)}^{†}=N^{†}N=M$). Finally, everything in Definition 2.1.6 is normal. Unitaries are normal because $M^{†}M=I=M{M}^{†}$. Self-adjoint maps (and hence also positive maps and projectors) are normal because $M{M}^{†}=M^2=M^{†}M$. While this is a bit of a definition dump, we’ll treat the most important kinds of maps from Definitions 2.1.5 and 2.1.6 – as well as their significance to quantum theory – in their own sections later in this chapter. A nice feature about normal maps (and hence all the maps in Definition 2.1.6) is that they can always be diagonalised. That is, we can find an ONB $M={\{|{\varphi }_j⟩\}}_j$ such that for all $i$, $M|{\varphi }_j⟩={\lambda }_j|{\varphi }_j⟩$. The scalars ${\lambda }_j$ and vectors $|{\varphi }_j⟩$ are called eigenvalues and eigenvectors, respectively, whereas $M$ is called an eigenbasis. Bra-ket notation (and hence string diagram notation) gives us a convenient way to write maps in diagonal form.

A special case is the identity map, which diagonalises with respect to any ONB, with eigenvalues all equal to 1:

We call such a sum over an ONB a resolution of the identity by ONB ${\{|{\varphi }_i⟩\}}_i$. As it turns out, all of the particular kinds of normal maps can be characterised by the types of eigenvalues they have.

One thing you might notice is what happens when a map is unitary and self-adjoint: it’s eigenvalues are all in $U(1)\cap ℝ=\{-1,1\}$. This is indeed what happens with the Pauli maps, which as we’ll see later, have many nice properties.

2.1.4 Tensors and the tensor product

Quantum computing relies crucially on multiple systems interacting with each other. To build up to how we should represent multiple systems in quantum theory, we can first see what happens if we bring two classical systems together. The simplest classical system that has more than one state is a bit, which we can represent as the set $𝔹:=\{0,1\}$. A single bit has two possible states: $0$ and $1$. A pair of bits has four possible states: $00$, $01$, $10$, and $11$. In other words, the system describing two bits is the cartesian product of two one-bit systems:

Since the role of classical bit values $0$ and $1$ in the qubit system ${ℂ}^2$ is played by the basis vectors $|0⟩$ and $|1⟩$, it stands to reason that the system of two qubits should have four basis vectors $|00⟩,|01⟩,|10⟩,|11⟩$, labelled by the four possible bit strings. This is exactly what taking the tensor product does for us. There are lots of ways to define the tensor product of two vector spaces. For the sake of simplicity, we’ll adopt a fairly brutal definition here, which makes explicit use of some fixed bases for a pair of Hilbert spaces.

We call this a ‘brutal’ definition, because the tensor product doesn’t really depend on a choice of basis, but choosing a basis will make it easier for us to see concretely what’s going on. Note that the symbol $\otimes$ used in defining the product basis doesn’t really mean anything in it’s own right. The important thing is just that we have one basis vector for each pair of basis vectors from $H$ and $K$. We could just as well have written basis elements as $|\mathit{ij}⟩$. We will indeed do this sometimes, e.g. we will write the basis vectors of the four-dimensional space ${ℂ}^2\otimes {ℂ}^2$ as:

However, this notation is suggestive of how we want to send a pair of states $|\psi ⟩\in H$ and $|\varphi ⟩\in K$ into the bigger tensor product space $H\otimes K$. Suppose these states decompose in our chosen bases as follows:

Then, we’ll define the product state as follows, just by pulling the sums and scalars out:

This looks a bit abstract, but if we instantiate this to the case of qubit states, it becomes pretty obvious what is going on. We just ‘multiply things out’:

If we write things out as column vectors, it should be even more clear what’s going on:

Note that, by writing $|\psi ⟩\otimes |\varphi ⟩$ as a four-dimensional column vector, we are implicitly treating the four basis states as the standard basis for ${ℂ}^4$, just by counting them base-2:

This is a general phenomenon. When we take the tensor products of Hilbert spaces, the dimensions multiply. Hence, we can treat a basis vector $|i,j⟩\in {ℂ}^n\otimes {ℂ}^{n^{\prime }}$ as a basis vector $|i{n}^{\prime }+j⟩\in {ℂ}^{n{n}^{\prime }}$. So, taking the tensor product of ${ℂ}^m$ with ${ℂ}^n$ just multiplies the dimensions. Since every finite-dimensional Hilbert space is isomorphic to ${ℂ}^n$ for some $n$, it follows that the tensor product is associative and has a unit given by the one-dimensional Hilbert space $ℂ={ℂ}^1$:

The symbol ‘$\cong$’ here means ‘is isomorphic to’. Because of this associativity we are justified in dropping the brackets when writing tensor products of many different spaces, e.g. $H_1\otimes \dots \otimes H_k$. The equation (2.4) is actually a special case of a more general kind of operation we can apply to matrices of any size.

While this definition might be a bit of head-scratcher the first time you see it, it’s pretty easy to think about in terms of block matrices. To form the matrix $A\otimes B$, we form a big matrix which has a block consisting of the matrix $a_i^{j}B$ for every element of $A$. That is, for matrices:

the Kronecker product is the $n{n}^{\prime }\times m{m}^{\prime }$ matrix:

This applies to any dimension of matrix, not just matrices with the same numbers of rows or columns. For example, the Kronecker product of the $2\times 1$ matrix of a state $|\psi ⟩$ and the $2\times 2$ matrix of map $A$ is computed as follows:

The Kronecker product is furthermore non-commutative: $B\otimes A\ne A\otimes B$. The matrix of $B\otimes A$ will be the same size and contains the same elements, but those elements will be in different places. For example:

Often, rather than smooshing the upper and lower indices together into a single index, as we did in the definition of Kronecker product, we can keep them separate and simply allow ‘generalised matrices’ that have zero or more upper and lower indices:

Note, rather than having a fixed number of ‘rows’ and ‘columns’, we have fixed input dimensions $D_0,\dots ,D_{m-1}$ and output dimensions $D_0^{\prime },\dots ,D_{n-1}^{\prime }$. These generalised matrices are called tensors. In fact, we’ve already met some tensors: kets are represented by tensors with zero inputs and one output:

bras by tensors with one input and zero outputs:

and plain old numbers are tensors with no inputs and no outputs:

We can relate tensors to bra-ket notation by taking a big sum over all the basis elements, with the tensor elements as coefficients:

A tensor with two indices of dimensions $n$ and $n^{\prime }$ has the same data as one with a single index of dimension $n{n}^{\prime }$, just packaged up in a different way. With that in mind, we can simplify the definition of the Kronecker product to give us a very similar operation, which is often just called the tensor product:

This readily generalises to tensors with lots of indices:

In either case, we represent the tensor product in string diagrams by ‘stacking boxes’:

We can sequentially compose tensors the same way we would matrices. For matrix composition, we get the components of $\mathit{BA}$ by multiplying components $A$ and $B$ together, and contracting (i.e. summing over) the output index of $A$ with the input index of $B$:

For tensors, the story is much the same, except we contract all the upper indices of one with the lower indices of the other:

As the pictures indicate, we should think of $\mathit{BA}$ as a sequential composition and $A\otimes B$ as parallel composition. When we start mixing these two together, the magic happens.

2.1.5 Sums and diagrams

Since these diagrams describe linear maps, it makes perfect sense to take linear combinations of them: for linear maps $f,g$ and scalars $\lambda ,\mu$, the linear map $\mathit{\lambda f}+\mathit{\mu g}$ sends a vector $v$ to $\mathit{\lambda f}(v)+\mathit{\mu g}(v)$. At the level of matrices, this amounts to scalar multiplication and adding matrices together element-wise. In fact, we were already doing this back in Section 2.1.3 when we wrote diagonalisation as:

Conveniently, we can summarise all of the various linearity and bilinearity conditions involving composition and tensor products into one principle:

In other words, when a summation occurs somewhere inside a diagram, it can always be pulled to the outside. We can see how this works using the following example. Consider the following quantum state, which is often called the (unnormalised) Bell state:

This state famously satisfies the following yanking equation with its adjoint $⟨\mathrm{\Phi }|$. Shown both in bra-ket notation and as a string diagram, this equation is the following:

Intuitively, we can think of the diagram of the left-hand side as a zig-zag shape that we are “yanking” into a straight piece of wire. We can prove this by substituting the definitions of $|\mathrm{\Phi }⟩$ and $⟨\mathrm{\Phi }|$ into the diagram and pulling the sums out to the outside:

2.1.6 Tensor networks and string diagrams

What happens when we compose two matrices $A,B$ in sequence and two more matrices $C,D$ in sequence, then compose the results in parallel?

How about when we do it the other way around?

We get the same thing! The resulting equation is called the interchange law:

Let’s see what happens if we do the same thing in the string diagram notation. Doing the composition one way around, we plug $A$ and $B$ together in sequence, plug $C$ and $D$ together in sequence, then stack the results in parallel:

The other way around, we stack $A$ and $C$ in parallel, then stack $B$ and $D$ in parallel, then plug the results together in sequence:

We see that the interchange law becomes completely trivial in the language of string diagrams:

This is a good thing! The interchange law isn’t capturing something fundamental about the processes we are studying, but is instead just a bit of unavoidable bureaucracy we have to deal with to fit sequential and parallel composition all in one line. The more our notation can swallow this bureaucracy and let us focus on what’s really important, the better! You might have noticed that, while we have already been using string diagrams in this section, we haven’t yet defined them in generality. For our purposes, string diagrams are a graphical notation for a general kind of composition of tensors called a tensor network. A tensor network is a particular way of composing tensors, where the elements of each of the component tensors are multiplied together and some pairs of indices are matched and summed over. We can represent this as a string diagram by depicting each of the component tensors as boxes and indices as wires. Wires that are open at one end represent free indices (i.e. the indices corresponding to inputs/outputs of the tensor), whereas wires that are connected at both ends correspond to bound indices. The latter are matched pairs of indices that get summed over. This might sound a little abstract, but if we see an example, it should be pretty clear what is going on. Suppose we have the following string diagram describing a big linear map:

We can (arbitrarily) assign index names to each of the wires:

Then, this diagram describes the following tensor network:

We will typically work purely with string diagrams and omit the indices, which are only relevant inasmuch as they uniquely identify each wire in the diagram. One thing to notice is that wires can freely cross over each other and even form feedback loops. Also, if we deform the string diagram and draw it different on the page, it will still describe the same calculation (2.7). For example:

In other words, the only relevant data is which inputs and outputs are connected to which others. This fact can be summarised in the string diagram mantra:

The final thing to note is we can also build up arbitrary tensor networks from $\circ$ and $\otimes$, provide we add two additional ingredients: swap maps and the partial trace operation. The former is a linear map which interchanges the two tensor factors of a vector in $A\otimes B$:

By linearity, it is totally defined by how it acts on product vectors:

Note that the SWAP for two qubits has the following matrix:

The latter operation, the partial trace, sums the last input index together with the last output index of a tensor. That is, for a linear map $f:A\otimes X\to B\otimes X$, ${\text{Tr}}_X(f):A\to B$ is a linear map whose matrix elements are given by:

In the special case where a map has only one input and output, this is just the normal trace, i.e. summing over the diagonal elements of a matrix: for $g:X\to X$ we have $\text{Tr}(g)={\sum <!--\; FUNCTION\; APPLICATION\; -->}_k{g}_k^k$. Graphically, we depict the partial trace as introducing a feedback loop:

2.1.7 Cups and caps

If this is your first time seeing this notation for the partial trace it might make you... a little uncomfortable. Don’t these feedback loops introduce all kinds of nasty complications like grandfather paradoxes and other problems to do with time travel? One way to see that it is in fact all fine, is to remember that the string diagrams are just notation for particular linear maps, and a wire denotes an index you contract over, where a feedback loop simply means we are contracting an input and an output ‘in the wrong order’. So you can just ‘shut up and calculate’ and treat the loops as a handy piece of notation. But we can also go one step further and decompose the loop into a couple of smaller pieces, which correspond to some special types of tensors. We have in fact already seen these pieces: they are the Bell state $|\mathrm{\Phi }⟩$ and effect $⟨\mathrm{\Phi }|$. We introduce some special notation for these tensors:

The reason this notation works is because it makes the yanking equation of Eq. (2.5) particularly nice:

Here the second equation states the state is symmetric in its two outputs. In the context of string diagrams we call this special state the cup and the effect the cap. Note that when we consider the cup and cap of qubits, their matrices are:

We can generalise this to a matrix representation for a cup and cap over any dimension. We can also write the cup and cap using indices: ${\subset }^{\mathit{ij}}={\delta }_{\mathit{ij}}$ and ${\supset }^{\mathit{ij}}={\delta }_{\mathit{ij}}$, where ${\delta }_{\mathit{ij}}$ is the standard Kronecker delta. In this notation it becomes especially clear that the cup and cap are like ‘bended identities’, since ${\text{id}}_j^i={\delta }_{\mathit{ij}}$. Using the cup and cap we can view a trace not as a feedback loop, but as a composition of a cup, a cap, and an identity wire connecting the two of them:

We are then left with a string diagram where every input is connected to an output, and not vice versa.

2.2 A bluffer’s intro to quantum theory

Okay, so now we have all the mathematical apparatus to describe quantum theory. But what is quantum theory actually? You will have almost certainly heard of quantum mechanics, and you may have heard of a few things starting with the word ‘quantum’, like quantum optics, quantum electrodynamics, quantum chromodynamics, and the standard model (okay, that last one doesn’t start with ‘quantum’, but it’s still relevant here). These are all theories of physics, which cover the behaviours of certain kinds of things that exist in the world (electrons, photons, quarks, the Higgs boson, ...). They are all underpinned by quantum theory, which can be seen more as a framework to build theories of physics on top of, rather than a full-fledged theory of physics in its own right. All the theories of physics we might build based on quantum theory have some characteristics in common, which can pretty much be summed up in the following 4 statements, which we’ll call the SCUM postulates.

• States of a quantum system correspond to vectors in a Hilbert space.
• Compound systems are represented by the tensor product.
• Unitary maps evolve states in time.
• Measurements are computed according to the Born rule.

These 4 postulates are a (loose) paraphrase of the Dirac-von Neumann axioms of quantum theory, where we’ve put a bit more emphasis on the bits that are most relevant for quantum computing. Everything in bold above will get defined soon enough. The point here is to show that there really isn’t very much at the core of quantum theory. Quantum theory is in fact very simple, and yet it somehow happens to be very good at making predictions about a whole lot of different kinds of physical systems. However, if you have encountered other theories of physics which can be derived from simple postulates (and one in particular about space and time proposed by a dude with crazy hair), you’ll notice something a little strange about the von Neumann postulates: they are all about maths and not at all about stuff . This is pretty odd for a theory of physics, because of course physics is fundamentally about stuff, and mathematics is just the tool. This has led to almost a century of dissatisfaction about the ‘fundamental’ nature of quantum theory, and led to a lot of interesting arguments, many books, and the whole field called quantum foundations, which asks not just what quantum theory is, but why it is the way it is. That is to say, if after reading the four postulates and learning what all the words in bold mean, you are still scratching your head about what the words in bold mean, you are actually in good company.

2.2.1 Quantum states

There are a handful of equivalent ways we can represent a quantum state. The first is as a normalised vector $|\psi ⟩$ in a Hilbert space $H$. This representation is the simplest, but also contains a bit of redundancy, because as we will see in Section 2.2.4, quantum theory will make the exact same predictions about a state $|\psi ⟩$ as it will about $e^{\mathit{i\alpha }}|\psi ⟩$ for any angle $\alpha$. Hence, there is no physical difference between $|\psi ⟩$ and $e^{\mathit{i\alpha }}|\psi ⟩$. We call the scalar factor $e^{\mathit{i\alpha }}$ a global phase, and we say the states $|\psi ⟩$ and $e^{\mathit{i\alpha }}|\psi ⟩$ are equivalent up to global phase. So, technically, a quantum state is not just one vector, but a set of vectors $\{e^{\mathit{i\alpha }}|\psi ⟩|\alpha \in [0,2\pi )\}$ which are equivalent up to a global phase. But then, this is just all the normalised states in a one-dimensional subspace of $H$.

So, the second equivalent way to represent a quantum state is to write down it’s one-dimensional subspace $S$. Picking any normalised vector in that space will recover $|\psi ⟩$, up to a global phase, whereas looking at the space spanned by $|\psi ⟩$ will recover $S$. A third equivalent way to represent a quantum state is by doubling $|\psi ⟩$. Somewhat counter-intuitively, we can make the representation of the state less redundant by putting two copies of $|\psi ⟩$ together. Or, more precisely, by multiplying the ket $|\psi ⟩$ with its adjoint bra $⟨\psi |$:

The result is a linear map $P_{|\psi ⟩}:=|\psi ⟩⟨\psi |$ which goes from $H$ to $H$. So, why is this representation actually less redundant than just taking the ket $|\psi ⟩$? Well, if we think about doubling an equivalent state $|\varphi ⟩:=e^{\mathit{i\alpha }}|\psi ⟩$, something magic happens:

The global phase disappears! So, what’s going on here? There’s a couple of ways to think about this. The most natural way to see this, is that it has something to do with measurement probabilities, and the actual reason we don’t care about phases in the first place. We’ll return to this point in Section 2.2.4, once we know how measurement probabilities are computed. For now, perhaps the best way to think about this is that $|\psi ⟩⟨\psi |$ is just another way of representing a one-dimensional subspace $S$, which we already know is an equivalent way of representing a quantum state. To see that, first recall from Definition 2.1.6 that a projector $P$ is a linear map that is self-adjoint ($P^{†}=P$) and idempotent ($P^2=P$). Projectors are linear maps that ‘squash’ vectors down into a subspace, called the range of the projector: $S:=\{|\varphi ⟩|\exists <!--\; FUNCTION\; APPLICATION\; -->|\psi ⟩\in H:|\varphi ⟩=P|\psi ⟩\}\subseteq H$. If $S$ is an $n$-dimensional subspace, we say $P$ is a rank-$n$ projector on to $S$. Now, it happens to be that $P_{|\psi ⟩}:=|\psi ⟩⟨\psi |$ is a rank-1 projector, whose range is exactly $S:=\{\lambda |\psi ⟩|\lambda \in ℂ\}$. If we draw this as:

we can imagine vectors coming in the wire on the left, then getting ‘squashed’ down to nothing (i.e. just a scalar factor), then getting embedded back into the $H$ as a scalar times $|\psi ⟩$:

So, that completes our three equivalent pictures of the quantum state. A quantum state is:

1..

a normalised vector $|\psi ⟩\in H$, up to a redundant global phase $e^{\mathit{i\alpha }}$,

2..

a one-dimensional subspace $S\subseteq H$, or

3..

a rank-1 projector $|\psi ⟩⟨\psi |$.

Of course, this really just tells us how a quantum state is represented mathematically, which is enough for our purposes. What the quantum state it is actually representing is a whole other question, which has been debated for more than a century. We’ll make some remarks about this and point to some further reading in Section 2.8.

2.2.2 Qubits and the Bloch sphere

We now turn our attention to the most interesting system from the point of view of quantum computation: the quantum bit, or qubit. We’ll see in the next section that the one-dimensional Hilbert space ${ℂ}^1=ℂ$ is the trivial, ‘no system’ system. So, to get something non-trivial, we should go one dimension up, to ${ℂ}^2$. Hence, a qubit is a system whose state lives in the Hilbert space ${ℂ}^2$. Physically, qubits can be implemented with any physical system that has at least 2 states that can be perfectly distinguished by a single quantum measurement (which we’ll cover in Section 2.2.4). As the name suggests, a qubit is the quantum analogue of a bit. As such, we’ll give the two standard basis elements some suggestive names:

Graphically, we will depict these states as follows:

These are the quantum analogues of the two possible states $0$ and $1$ that a classical bit could take. In Section 2.3, we’ll see how this embedding of classical bits into two-dimensional vector spaces can be used to lift classical logic gates on bits to quantum logic on qubits. Because of this connection to classical computation, the basis $\{|0⟩,|1⟩\}$ is often called the computational basis. We will occasionally use this term, but will instead mostly call it the $Z$-basis, for reasons that will shortly become clear. We know from the last section that quantum states in ${ℂ}^2$ correspond to normalised vectors $|\psi ⟩\in {ℂ}^2$, up to a global phase. We’ll now use this fact to find a convenient way to parametrise a generic state $|\psi ⟩:=a|0⟩+b|1⟩$ in ${ℂ}^2$. First note that normalisation puts a restriction on the values $a$ and $b$ can take:

Since $|a{|}^2+|b{|}^2=1$, we can draw the following triangle with $1$ on the hypotenuse:

From the sine and cosine laws, we can always express $|a|$ and $|b|$ in terms of a single angle $𝜃$: $|a|=\cos <!--\; FUNCTION\; APPLICATION\; -->𝜃$ and $|b|=\sin <!--\; FUNCTION\; APPLICATION\; -->𝜃$. As a matter of convention, it’s slightly more convenient to use $\frac{𝜃}{2}$ instead of $𝜃$, so let $|a|=\cos <!--\; FUNCTION\; APPLICATION\; -->\frac{𝜃}{2}$ and $|b|=\sin <!--\; FUNCTION\; APPLICATION\; -->\frac{𝜃}{2}$. As we saw in Section 2.1.1, the absolute value of a complex number $\lambda =r{e}^{\mathit{i\alpha }}$ fixes $r$. Hence, we can conclude that $a=\cos <!--\; FUNCTION\; APPLICATION\; -->\frac{𝜃}{2}{e}^{\mathit{i\beta }}$ and $b=\sin <!--\; FUNCTION\; APPLICATION\; -->\frac{𝜃}{2}{e}^{\mathit{i\gamma }}$, for some phase angles $\beta ,\gamma$. So, using just normalisation, we can replace 2 complex numbers with 3 angles:

Now we can use the freedom to choose a global phase to get rid of another one of these angles. Since we can freely multiply $|\psi ⟩$ by a global phase without changing the physical state, the angle $\beta$ is actually redundant. We can cancel it out by multiplying the whole thing by $e^{-\mathit{i\beta }}$.

Letting $\alpha :=\gamma -\beta$, we can therefore write a generic qubit state $|\varphi ⟩$ conveniently as:

Since the quantum state is now totally described by two angles, we can plot it on a sphere, called the Bloch sphere:

This picture is useful for our intuition. For example, the more ‘similar’ two states are, that is, the higher the value of their inner product, the closer they are on the Bloch sphere. In particular, antipodes are always orthogonal states.

For a qubit, picking an orthonormal basis just comes down to picking a pair of orthogonal normalised states, hence, we can always think of orthonormal bases as different axes cutting through the Bloch sphere.

The three pairs of antipodal points each correspond to an orthonormal basis for ${ℂ}^2$:

These bases mark out the X, Y, and Z axes of the Bloch sphere. We’ll see in Section 2.3.2 that they are also eigenvectors of the Pauli $X$, $Y$, and $Z$ operations, respectively. Let’s now take a look at what unitaries do to qubit quantum states visually. A paradigmatic example is the Z phase gate:

On eigenstates $|0⟩$ and $|1⟩$, the $Z(\alpha )$ doesn’t do anything: or rather it only changes the state up to a global phase:

However, on a generic state, we end up multiplying the coefficient of $|1⟩$ by $e^{\mathit{i\alpha }}$, which amounts to adding $\alpha$ to its phase:

Since the phase of the coefficient of $|1⟩$ determines how far around the Z-axis to plot the state, we can conclude that $Z(\alpha )$ amounts to a Z-rotation of the Bloch sphere by an angle of $\alpha$.

While we said that $Z(\alpha )$ is a paradigmatic example, it is in fact (essentially) the only example of a unitary over ${ℂ}^2$, up to a global phase. We can see that by taking some generic unitary and diagonalising it:

Then, as we saw in Exercise 2.4, the eigenvalues of a unitary are always phases, so ${\lambda }_j=e^{i{\alpha }_j}$, hence up to a global phase, we have:

So, $U$ is basically $Z(\alpha )$, written with respect to another ONB $\{|{\varphi }_0⟩,|{\varphi }_1⟩\}$.

Hence, single-qubit unitaries correspond exactly to rotations of the Bloch sphere. A standard fact about rotations of a sphere is that any rotation can be generated by a sequence of three rotations about two orthogonal axes. The standard choice of orthogonal axes you see crop up in the quantum computing literature is a Z-axis rotation, which we’ve already met, and an X-axis rotation:

2.2.3 Unitary evolution

We won’t talk much about the Schrödinger equation in this book, but no bluffers intro to quantum theory would be complete without showing it at least once. So here it is, the time-dependent Schrödinger equation:

where $H(t)$ is a self-adjoint operator, called the Hamiltonian, which may depend on the time $t$ (and yes physicists, we are ignoring the constants and units). The actual form this operator takes depends on what sorts of physics is actually going on. If we for instance are describing the internals of a molecule we would have a particular Hamiltonian describing the momentum, the spin, and attraction or repulsion between all the electrons, protons and neutrons. If instead we are describing a lab situation where we are shining a laser on trapped ion, we might only care about the terms having to do with the time-dependent laser interaction. This differential equation describes how a quantum state evolves in time. When $H$ doesn’t depend on $t$, solutions to (2.13) take a nice form in terms of an initial state $|\psi (0)⟩$ and the matrix exponential $e^{\mathit{itH}}$. We’ll talk about matrix exponentials a lot more in Chapter 7, but for now, suffice to say that matrix exponentials behave a lot like plain ole number exponentials when you take their derivatives. In particular, for matrices we have $\frac{d}{\mathit{dt}}{e}^{\mathit{tM}}=M{e}^{\mathit{tM}}$, so taking the derivative of $e^{-\mathit{itH}}|\psi (0)⟩$ with respect to $t$ just pops out a factor of $-\mathit{iH}$. Hence:

So, $e^{-\mathit{itH}}|\psi (0)⟩$ gives a solution to the Schrödinger equation, and we can let $|\psi (t)⟩:=e^{-\mathit{itH}}|\psi (0)⟩$. Another handy thing is, whenever $H$ is self-adjoint, $e^{\mathit{itH}}$ is unitary (again we’ll see why in Chapter 7). Hence, $U(t):=e^{-\mathit{itH}}$ gives us the unitary time evolution operator of a quantum system. The reason we don’t talk much about the Schrödinger equation in this book is, for the purposes of quantum computation, it usually suffices to talk about time evolution abstractly, fully in terms of unitaries. That is, if a system is initially in state $|\psi ⟩:=|\psi (0)⟩$, its time evolution for a fixed chunk of time (say $t=1$) is described by some unitary map $U:=U(1)$. Conversely, there is a powerful theorem that says any unitary map arises as the time evolution of some Hamiltonian in this kind of way. For this reason, it is often convenient to just talk directly about the unitaries and leave it to the physicists to worry about Hamiltonians.

2.2.4 Measurements and the Born rule

Most quantum computations consist of preparing a quantum state, doing some unitary evolution of the state, then measuring the result. The only ingredient we are missing so far is measurement. In order to do a quantum measurement, we need to choose what we want to measure. A measurement is a (non-deterministic) process which extracts some information from a quantum system and usually changes the state of the system when we do it. Mathematically, this is represented as a set of projectors that sum up to the identity:

The probability of getting the $i$-th outcome when we measure a state $|\psi ⟩$ with $M$ is computed with the following M-sandwich: