1.3.1 What is a qubit?

In fact, a qubit (short for quantum bit, sometimes also written as qbit, Qbit or even q-bit) is the minimal information unit in quantum computing. In the same way that a bit (short for binary digit) can be in state or in state , a qubit can be in state or in state . Here, we are using the so-called Dirac notation, where these funny-looking symbols surrounding and are called kets and are used to indicate that we are dealing with vectors instead of regular numbers. In fact, and are not the only possibilities for the state of a qubit and, in general, it could be in a superposition of the form

where and are complex numbers, called amplitudes, such that . The quantity is called the norm or length of the state and, when it is equal to , we say that the state is normalized.

All these possible values for the state of a single qubit are vectors that live in a complex vector space of dimension 2 (in fact, they live in what is called a Hilbert space, but since we will be working only with finite dimensions, there is no real difference). Thus we shall fix the vectors and as elements of a special basis, which we will refer to as the computational basis. We will represent these vectors, constituents of the computational basis, as the column vectors

and hence

If we are given a qubit and we want to determine or, rather, estimate its state, all we can do is perform a measurement and get one of two possible results: 0 or 1. We have nonetheless seen how a qubit can be in infinitely many states, so how does the state of a qubit determine the outcome of a measurement? As you likely already know, in quantum physics, these measurements are not deterministic, but probabilistic. In particular, given any qubit , the probability of getting upon a measurement is , while that of getting is . Naturally, these two probabilities must add up to 1, hence the need for the normalization condition .

If upon measuring a qubit we get, let's say, , we then know that, after the measurement, the state of the qubit is , and we say that the qubit has collapsed into that state. If we obtain , the state collapses to . Since we are obtaining results that correspond to and , we say that we are measuring in the computational basis.

So a qubit is, mathematically, just a 2-dimensional vector that satisfies a normalization condition. Who could have known? But the surprises do not end here. In the next subsection, we will see how we can use those funny-looking kets to compute inner products in a very easy way.

1.3.2 Dirac notation and inner products

Dirac notation can not only be used for column vectors, but also for row vectors. In that case, we talk of bras, which, together with kets, can be used to form bra-kets. This name is a pun, because, as we are about to show, bra-kets are, in fact, inner products that are written — you guessed it — between brackets. To be more mathematically precise, with each ket we can associate a bra that is its adjoint or conjugate transpose or Hermitian transpose. In order to obtain this adjoint, we take the ket's column vector, we transpose it and conjugate each of its coordinates (which are, as we already know, complex numbers). We use to denote the bra associated with and to denote the bra associated with , so we have

and, in general,

where, as it is customary, we use the dagger symbol () for the adjoint.

Important note

When finding the adjoint, do not forget to conjugate the complex numbers! For instance, it holds that

One of the reasons why Dirac notation is so popular for working with quantum systems is that, by using it, we can easily compute the inner products of kets and bras. For instance, we can readily show that

This proves that and are not just elements of any basis but of an orthonormal one, since and are orthogonal and of length 1. Thus, we can compute the inner product of two states and using Dirac notation by noting that

where and are the complex conjugates of and .

We now know what qubits are, how to measure them, and even how to benefit from Dirac notation for some useful computations. The only thing remaining is to study how to operate on qubits. Are you ready? It is time for us to get you introduced to the mighty quantum gates!

1.3.3 One-qubit quantum gates

So far, we have focused on how a qubit stores information in its state and on how we can access (part of) that information with measurements. But in order to develop useful algorithms, we also need some way of manipulating the state of qubits to perform computations.

Since a qubit is, fundamentally, a quantum system, its evolution follows the laws of quantum mechanics. More precisely, if we suppose that our system is isolated from its environment, it obeys the famous Schrödinger equation.

To learn more…

The time-independent Schrödinger equation can be written as

where is the Hamiltonian of the system, is the state vector of the system at time , is the imaginary unit, and is the reduced Planck constant.

We will talk more about Hamiltonians in Chapter 3, QUBO: Quadratic Unconstrained Binary Optimization, Chapter 4, Quantum Adiabatic Computing and Quantum Annealing, and Chapter 7, VQE: Variational Quantum Eigensolver.

Don't panic! To program a quantum computer, you don't need to know how to solve Schrödinger's equation. In fact, the only thing that you need to know is that its solutions are always a special type of linear transformations. For the purposes of the quantum circuit model, since we are working in finite-dimensional spaces and we have fixed a basis, the operations can be described by matrices that are applied to the vectors that represent the states of the qubits.

But not any kind of matrix does the trick. According to quantum mechanics, the only matrices that we can use are the so-called unitary matrices, which are the matrices such that

where is the identity matrix and is the adjoint of , that is, the matrix obtained by transposing and replacing each element by its complex conjugate. This means that any unitary matrix is invertible and its inverse is given by . In the context of the quantum circuit model, the operations represented by these matrices are called quantum gates.

When we have just one qubit, our unitary matrices need to be of size because the state vector is of dimension 2. Thus, the simplest example of a quantum gate is the identity matrix of dimension 2, which transforms the state of the qubit by... well, by not transforming it at all. A less boring example is the gate, whose matrix is given by

The gate is also called the NOT gate, because its action on the elements of the computational basis is

which is exactly what the NOT gate does in classical digital circuits.

A quantum gate with no classical analog is the Hadamard or gate, given by

This gate is extremely useful in quantum computing, for it can create superposition. To be precise, if we apply the gate on a qubit in state , we obtain

This state is so important that it has its own name and symbol. It is called the plus state and it is denoted by . In a similar way, we have that

and, as you probably guessed, this state is called the minus state and it is denoted by .

Of course, we can apply several gates to the same qubit one after the other. For instance, consider the following circuit:

We read gates from left to right, so in the preceding circuit we would first apply an gate, then an gate and, finally, another gate. You can easily check that, if the initial state of the qubit is , it would end up again in state . But were its initial state , the final state would become .

It turns out that this operation is also very important, and, of course, it has its own name: we call it the gate. From its action on and , we can tell that its matrix will be

something that we could have also deduced by multiplying the matrices of the gates , , and one after the other.

Exercise 1.5

Check that and that in two different ways. First, use Dirac notation and the actions of and (remember that we have defined as ). Then, derive the same result by performing the matrix multiplication

Since there are and gates, you may be wondering if there is also a gate. Indeed, there is one, given by matrix

Other important one-qubit gates include the and gates, whose matrices are

But, of course, there is an (uncountably!) infinite number of 2-dimensional unitary matrices and we cannot just list them all here. What we will do instead is introduce a beautiful geometrical representation of single-qubit states, and, with it, we will explain how all one-qubit quantum gates can, in fact, be understood as certain kinds of rotations. Enter the Bloch sphere!

1.3.4 The Bloch sphere and rotations

The general state of a qubit is described with two complex numbers. Since each of those numbers has two real components, it would be natural to think that we would need a four-dimensional real space in order to represent the state of a qubit. Surprisingly enough, all the possible states of a qubit can be drawn on the surface of an old-school sphere, which is a two-dimensional object!

To show how it can be accomplished, we need to remember that a complex number can be written in polar coordinates as

where is a non-negative real number and is an angle in . Consider, then, a qubit in a state and write and in polar coordinates as

We know that and, since , there must exist an angle in such that and . The reason for considering instead of in the cosine and sine will be apparent in a moment. Notice that, by now, we have

Another crucial observation is that we can multiply by a complex number with absolute value 1 without changing its state. Indeed, it is easy to see that does not affect the probabilities of obtaining 0 and 1 when measuring in the computational basis (check it!) and, by linearity, it comes out when applying a quantum gate (that is, ). Thus, there is no operation — either unitary transformation or measurement — that allows us to distinguish from . We call a global phase and we have just shown that it is physically irrelevant.

We can, thus, multiply by to obtain an equivalent representation

where we have defined .

In this way, we can describe the state of any qubit with just two numbers and that we can interpret as a polar angle and an azimuthal angle, respectively (that is, we are using what are known as spherical coordinates). This gives us a three-dimensional point

that locates the state of the qubit on the surface of a sphere, called the Bloch sphere (see Figure 1.2).

Notice that runs from to to cover the whole range from the top to the bottom of the sphere. This is why we used in the representation of our preceding qubit. We only needed to get up to for our angles in the sines and cosines!

In the Bloch sphere, is mapped to the North pole and to the South pole. In general, states that are orthogonal with respect to the inner product are antipodal on the sphere. For instance, and both lie on the equator, but on opposite points of the sphere. As we already know, the gate takes to and to , but leaves and unchanged, at least up to an irrelevant global phase. In fact, this means that the gate acts like a rotation of radians around the axis of the Bloch sphere…, so now you know why we use that name for the gate! In the same manner, and are rotations of radians around the and axes, respectively.

We can generalize this behavior to obtain rotations of any angle around any axis of the Bloch sphere. For instance, for the , , and axes we may define

where we use the symbol for equivalent action up to a global phase. Notice that , , , , and .

In fact, it can be proved (see, for instance, the book by Nielsen and Chuang [69]) that for any one-qubit gate there exists a unit vector and an angle such that

For example, choosing and we can obtain the Hadamard gate, for it holds that

Additionally, it can also be proved that, again for any one-qubit gate , there exist three angles , , and such that

In fact, you can obtain such a decomposition for any two rotation axes as long as they are not parallel, not just for and .

Moreover, in some quantum computing architectures (including the ones used by companies such as IBM), it is common to use a universal one-qubit gate, called the -gate, that depends on three angles and is able to generate any other one-qubit gate. Its matrix is

All these observations about how to construct one-qubit gates from rotations and parametrized families will be very important when we talk about variational forms and feature maps in Chapter 9, Quantum Support Vector Machines, and Chapter 10, Quantum Neural Networks, and also to construct controlled gates later in this chapter.

1.3.5 Hello, quantum world!

To put together everything that we have learned, we are going to create our very first complete quantum circuit. It looks like this:

It doesn't seem very impressive, but let's analyze it part by part. As you know, following convention, the initial state of our qubit is assumed to be , so that's what we have before we do anything. Then we apply the gate, so the state changes to . Finally, we measure the qubit. The probability of obtaining will be , and that of getting will also be , so we have created a circuit that — at least in theory — generates random bits following a perfectly uniform distribution.

We can modify the previous circuit to obtain any distribution over and that we desire. If we want the probability of measuring to be , we just need to consider and the following circuit:

For now, this is all that we need to know about one-qubit states, gates, and measurements. Let us move on to two-qubit systems, where the mysteries of entanglement are awaiting to be revealed!

1.4.1 Two-qubit states

So far, we have worked with qubits in isolation. But the real power of quantum computing cannot be unleashed unless qubits can talk to each other. We will start by considering the simplest case of quantum systems in which there is qubit interaction: two-qubit systems.

Of course, in a two-qubit system, each of the qubits can be in state or in state . Thus, for the two qubits, we have four possible combinations: both are in state , the first one is in state and the second one in state , the first one is in state and the second one in state , or both are in state . These four possibilities form a basis (called the computational basis) of a -dimensional space and we denote them, respectively, by

Here, is the symbol for the tensor product. The tensor product of two column vectors is defined by

Hence, the four basis states can be represented by four-dimensional column vectors given by

Usually, we omit the symbol and just write

or

or even

Obviously, in this last case, the number of qubits that we are using must be clear from the context in order not to mistake the state of a one-qubit system with the state of a two-qubit system — or, as we will see soon, any other multi-qubit system!

As we have mentioned, these four states constitute a basis of the vector space of possible states for a two-qubit system. The general expression for the state of such a system is

where , , , and are complex numbers (called amplitudes, remember?) such that .

If we measure in the computational basis both qubits at this generic state that we are considering, we will obtain with probability , with probability , with probability , and with probability . In all those cases, the state will collapse to the state corresponding to the outcome of the measurement, just as with one-qubit systems.

Let's now say that we only measure one of the qubits. What happens then? Suppose that we measure the first qubit. Then, the probability of obtaining will be , which is the sum of the probabilities of all the outcomes in which the first qubit can be . If we measure the first qubit and the result turns out to be , the system will not collapse completely, but it will remain in the state

where we have divided by to keep the state normalized. The situation in which the result of the measurement is is analogous.

Dirac notation is also useful to compute inner products of two-qubit states. We only need to notice that

apply distributivity and remember to conjugate the complex coefficients when obtaining a bra from a ket.

Then, for instance, we can notice that the inner product of and is

since and .

1.4.2 Two-qubit gates: tensor products

Of course, the operations that we can conduct on two-qubit systems need to be unitary. Thus, two-qubit quantum gates are unitary matrices that act on 4-dimensional column vectors. The simplest way to construct such matrices is by taking the tensor product of two one-qubit quantum gates. Namely, if we consider two one-qubit gates and and two one-qubit states and , we can form a two-qubit gate that acts on as

By linearity, we can extend to any combination of two-qubit states and we can associate a matrix to . In fact, said matrix is given by the tensor product of the matrices associated to and . More concretely, the expression for the tensor product, , of the matrices and is

Now it is easy to verify that this operation is indeed unitary and, hence, deserves the name of quantum gate.

Tensor products of gates occur naturally when we have circuits with two qubits and pairs of individual one-qubit gates are acting on each of them. For instance, in the following circuit, the gate acts on the two qubits and then it is followed by the gate , where is the identity gate:

You may complain that we haven't done anything new so far. And you would be right! In fact, quantum gates that are obtained as the tensor product of one-qubit gates can be seen as operations on isolated qubits that just happen to be applied at the same time. But wait and see! In the next subsection, we will introduce a completely different way of acting on two-qubit systems.

1.4.3 The CNOT gate

By taking tensor products of one-qubit gates, we can only obtain operations that act on each qubit individually. But this just leaves us with a (rather boring) subset of all the possible two-qubit gates. There are many unitary matrices that cannot be written as the tensor product of other simple matrices. In the two-qubit case, probably the most important one is the controlled-NOT (or controlled-) gate, usually called the CNOT gate, given by the unitary matrix

It is illuminating to see how this gate acts on the elements of the two-qubit computational basis. As you can easily check, we get

This means that the value of the second qubit is flipped if and only if the value of the first qubit is . Or, to put it in other words, the application of a NOT gate on the second qubit (that we call the target) is controlled by the first qubit. Now the name of this gate makes much more sense, doesn't it?

In a quantum circuit, the CNOT gate is represented as follows:

Notice that the control qubit is indicated by a solid black circle and the target qubit is indicated by the symbol (the symbol for an gate can also be used instead of ).

Sometimes, technical difficulties restrict the number of CNOT gates that can be actually implemented on a quantum computer. For instance, on a certain quantum chip you may have the possibility of applying a CNOT gate targeting qubit and controlled by qubit , but not the other way around. If you find yourself in such a situation, there's no need to panic. If you use the circuit

you are effectively applying a CNOT gate with target in the top qubit and control in the bottom one. And that's how you can save the day!

The CNOT gate can also be used to interchange or swap the states of two qubits, by using the following circuit:

In any case, the most prominent use of the CNOT gate is, without a doubt, the ability to create entanglement, an intriguing property of quantum systems that we will study next.

1.4.4 Entanglement

Oddly enough, in order to define when a quantum system is entangled, we first need to define when it is not entangled. We say that a state is a product state if it can be written as the tensor product of two other states and , each of at least one qubit,
as in

If is not a product state, we say that it is entangled.

For example, is a product state, because we know that it is just another way of writing . Also, is a product state, because we can factor on the second qubit to obtain

On the other hand, is an entangled state. No matter how hard you try, it is impossible to write it as a product of two one-qubit states. Suppose, for sake of contradiction, that it were possible. Then, you would have

But this forces to be , because we have no component in . Then, either , in which case is , or , from which follows. In both cases, it is impossible to reach the equality that we needed. Thus, it follows that the state is entangled.

When measured, entangled states can show correlations that go beyond what can be explained with classical physics. For instance, if we have the entangled state and we measure the first qubit, we can obtain or , each with probability . However, if we measure the second qubit afterwards, the result will be completely determined by the value obtained when measuring the first qubit and, in fact, will be exactly the same. If we invert the order and measure first the second qubit, then the result will be or , with equal probability. But, in this case, the result of a subsequent measurement of the first qubit will be completely determined!

This still happens even if we separate the two qubits thousands of light years apart, as if one qubit could somehow know what the result of measuring the other qubit was. This curious behavior haunted many physicists during the 20th century, including Albert Einstein, who called it a "spooky action at a distance" (see [34]). Nevertheless, the effects of entanglement have been repeatedly demonstrated in uncountable experiments (in fact, the Nobel Prize in Physics 2022 was awarded to Alain Aspect, John F. Clauser, and Anton Zeilinger, pioneers in studying and testing this phenomenon in practice [10, 25, 41, 19]). And, very importantly for us, entanglement is one of the most powerful resources available in quantum computing.

But entanglement is, by no means, the only puzzling feature of qubit systems. In the next subsection, we are going to mathematically prove that copying quantum information, an operation that you may have taken for granted, is not possible in general. These qubits are, indeed, full of surprises!

1.4.5 The no-cloning theorem

Another peculiar property of quantum systems is that, in general, they don't allow us to copy information. Surprising as this may seem, it is just an easy consequence of the linearity of quantum gates. To show why, let us be more precise about what we would need in order to copy information, for instance with just two qubits. We would like to have a two-qubit quantum gate that will be able to copy the first qubit into the second. That is, for any given quantum state , we would need

Then, and and, by linearity,

We should highlight that the state that we have obtained is entangled, as we proved in the previous subsection.

Nevertheless, notice that, in our original state, we can factor the second out to obtain

Then, in virtue of the action of , we should have

which is a product state. However, we had obtained earlier that , which is entangled! This contradiction implies that, alas, no such exists.

This remarkable result is called the no-cloning theorem and we should explain its meaning in a little more detail. On the one hand, notice that this does not imply that we cannot copy classical information. In fact, if is just or , we can easily achieve by taking to be the CNOT gate. On the other hand, the theorem applies to unknown states . If we know what is — that is, if we know a circuit that prepares starting from — then, of course, we can create as many independent copies of it as we want. However, if is handed to us without any additional information about its state, the no-cloning theorem shows that we cannot replicate its state in general.

After this brief detour, let's return to our study of two-qubit quantum gates. In the next subsection, we will show how to construct many interesting two-qubit unitary operations whose action is controlled by one of their inputs.

1.4.6 Controlled gates

You may be wondering if, in addition to a controlled- (or CNOT) gate, there are also controlled-, controlled-, or controlled- gates. The answer is a resounding yes and, in fact, for any quantum gate , it is possible to define a controlled- (or, simply, ) gate whose action on the computational basis is

Exercise 1.15

Check that the matrix of is

where is the matrix of . Check also that is unitary. What is the adjoint of ?

The circuit representation of a gate is similar to the one that we use for the CNOT gate, namely

where the solid black circle indicates the control and the box with inside indicates the target.

Constructing a controlled gate is simpler than it seems, provided your quantum computer already implements rotation gates and the two-qubit CNOT gate. In fact, from the decomposition in rotations that we mentioned at the end of Section 1.3.4, it can be proved (see the book by Nielsen and Chuang [69, Corollary 4.2]) that any one-qubit quantum gate can be written in the form

for some angle and gates , , and such that . Then, the following circuit implements :

Sometimes, though, constructing a controlled gate is much easier. For instance, it can be shown that a controlled- gate can be obtained from a controlled- and two gates, as shown in the identity of the following circuits:

We now have everything we need in order to construct our first two-qubit quantum circuit. Let's get those qubits entangled!

1.4.7 Hello, entangled world!

To finish up with our study of two-qubit systems, let us show how to create entangled states with the help of the CNOT gate. Consider the following circuit:

Initially, the state of the system is . After we apply the gate, we get into the state . Finally, when we apply the CNOT gate, the state changes to , which, as we proved in Section 1.4.4, is indeed an entangled state.

The state is known as a Bell state, of which there are four. The other three are , , and . All of them are entangled, and they can be prepared with circuits similar to the preceding one.

We are now ready for the big moment. In the next section, we will finally learn how to work with not just one or two qubits, but with as many as we can get in our quantum computers.

1.5.1 Multi-qubit systems

With all that we have learned so far, it will now be very easy to understand how to work with multi-qubit systems.

As you may have already deduced, if we have qubits, the states that constitute the computational basis are

We usually omit the symbol to write

or

or simply

Of course, a generic state of the system will then be of the form

subject to the only condition that the amplitudes should be complex numbers such that . Our dear old friend, the normalization condition!

If we decide to measure all the qubits of the system in the computational basis, we will obtain with probability . If that is the case, then the state will collapse to . But if we only measure one of the qubits, say the -th one, then we will obtain with probability

where is the set of numbers whose -th bit is . In this scenario, the state of the system after measuring would be

Computing inner products of -qubit systems in Dirac notation is very similar to doing it with two-qubit systems. The procedure is analogous to the one we showed in Section 1.4.1, but taking into account that

We can now turn to the question of how to operate on many qubits at once. Let's define multi-qubit gates!

1.5.2 Multi-qubit gates

Since -qubit states are represented by -dimensional column vectors, -qubit gates can be identified with unitary matrices. Similar to the two-qubit case, we can construct -qubit gates by taking the tensor product of gates on a smaller number of qubits. Namely, if is an -qubit gate and is an -qubit gate, then is an -qubit gate and its matrix is given by the tensor product of the matrices and .

To learn more…

The expression for the tensor product of two matrices and is

However, there are -qubit gates that cannot be constructed as tensor products of smaller gates. One such example is the Toffoli or CCNOT gate, a three-qubit gate that acts on the computational basis as

where is the XOR function and is the symbol for the AND Boolean function. Thus, CCNOT applies a doubly controlled (in this case, by the first two qubits) NOT gate to the third qubit — hence the name!

The Toffoli gate is important because, using it and with the help of auxiliary qubits, we can construct any classical Boolean operator. For instance, (where is the negation of ) and . This shows that, with quantum circuits, we can simulate the behavior of any classical digital circuit at the cost of using some additional ancillary qubits, since any Boolean function can be built with just negations and conjunctions. This is somewhat surprising, because we know that all quantum gates are invertible, while not all Boolean functions are. It then follows that we could make all of our digital circuits reversible just by implementing a classical version of the Toffoli gate!

We will not be studying any other concrete examples of gates that act on three (or more!) qubits because, in fact, we can simulate their behavior with circuits that only use one- and two-qubit gates. Keep on reading to know how!

1.5.3 Universal gates in quantum computing

Current quantum computers can't implement every possible quantum gate. Instead, they rely on universality results that show how any unitary operation can be decomposed as a circuit that uses a reduced set of primitive gates. In previous sections, we mentioned, for instance, that any one-qubit gate can be obtained by using just and rotations. It turns out that similar results exist for the general case of -qubit quantum gates.

To us, it will be important to know that, for any unitary operation, we can construct a circuit that implements it using only one-qubit gates and the CNOT gate. For this reason, we say that those gates are universal — in the same sense that, for example, negation and conjunction are universal for Boolean logic. This fact will be crucial for our study of feature maps and variational forms in connection to quantum neural networks and other quantum machine learning models.

To illustrate how CNOT and one-qubit gates can be used to implement any other quantum gate, the following circuit shows a possible decomposition of the Toffoli gate targeting the top qubit:

This concludes our review of the fundamentals of quantum computing. We've come a long way since the beginning of this chapter, but by now we have mastered all the mathematics that we will need in order to study quantum machine learning and quantum optimization algorithms. Soon, we will see all these concepts in action!