3.2 From bits to qubits and their evolution

A classical bit (e.g. the position of gear teeth in Babbage’s differential engine, a memory element or wire carrying a binary signal, in contemporary machines) is a system comprising many atoms. Typically, the system is described by one or more continuous parameters, for example, voltage. Such a parameter is used to separate the space into two well-defined regions chosen to represent 0 and 1. Manufacturing imperfections and local perturbations may affect the signal, so signals are periodically restored near these regions to prevent them from drifting away. An -bit register of memory can exist in any of logical states, from ( zeros) to ( ones).

A quantum event in which we have two possible mutually exclusive outcomes is the elementary act of observation: all knowledge of the physical world is based upon such acts. An elementary act of observation is simultaneously like a coin-toss and not like a coin-toss. The information derived from an elementary act of observation is no more than a single bit, but there is more on it than that. To mark this difference Schumaker [120] has coined the name qubit. A quantum bit, qubit, is typically a microscopic system, such as an atom or nuclear spin or polarized photon. For example, the state of a spin- particle, when measured, is always found to be in one of two possible states, represented as

so one can use one spin state to represent 0, and the other spin state to represent 1. There is nothing special about spin systems – any 2-state quantum system can be equally used to represent 0 and 1. What is really special here is the existence of a continuum of intermediate states which are superpositions of 0s and 1s. Unlike the intermediate states of a classical bit (for example, any voltages between the “standard" representations of 0 and 1) which can be distinguished from 0 and 1, but do not exist from an informational point of view, quantum intermediate states cannot be reliably distinguished, even in principle, from the basis states, but do have an informational “existence".

An -qubit system can exist in any superposition of the form


(5)
where are (complex) numbers such that The exponential “explosion" represented by formula (5) distinguishes quantum systems from classical ones: in a classical system, which is completely described locally, a state is described by a number of parameters growing only linearly with the size of the system, but, as we shall see in the next section, quantum systems may not admit such a description (because quantum states may be “entangled").

For a better understanding we need some rudiments of (finite dimensional) Hilbert space theory. A Hilbert space is a mathematical model for representing vectors. The state of a quantum system can be described by a column vector in a Hilbert space of wave functions; as the system evolves, its state vector rotates with its base anchored to the origin of axes. Vectors can be added and multiplied by (complex) numbers. State vectors are typically written with a special angular bracket notation, the “ket vector" invented by Paul Dirac [54]. Row vectors, such as , are known as “bra" vectors; when you put together a column and a bra vector, you get a bracket, that is the inner product of the two vectors, , also written as .

                                                                              Figure 2: Paul Dirac

As we already have seen, a simple 2-state quantum system (the basic block of a quantum memory register) can, by definition, be in one of two possible states. To model it we need the smallest non-trivial Hilbert space , a two dimensional space. Assume that a particular complete orthonormal basis, denoted by , , has been fixed. These vectors, and , correspond to the classical bit values 0 and 1, respectively.

A qubit is a unit vector in the space , so for each qubit , there are two (complex) numbers such that


(6)
where

and .

The angle which a qubit makes with the vertical axis describes the relative contributions of and . The angle through which the vector is rotated about the vertical axis induces the so-called “phase". So, different qubits may have the same proportion of and , but with different phase factors. Phase is irrelevant for the whole states but it’s crucial for “quantum interference effects".

We can perform a measurement that projects the qubit onto the basis , . Then we will obtain the outcome with probability , and the outcome with probability . With the exception of limit cases and , the measurement irrevocably disturbs the state: If the value of the qubit is initially unknown, then there is no way to determine and with any conceivable measurement. However, after performing the measurement, the qubit has been prepared in a known state (either or ); this state is typically different from the previous state.

The above facts point out an important difference between qubits and classical bits. There is no problem in measuring a classical bit without disturbing it, so we can decode all of the information that it encodes. If we have a classical bit with a fixed, but unknown value (0 or 1), then we can only say that there is a probability that the bit has the value 0, and a probability that the bit has the value 1, and these two probabilities add up to 1. When we measure the bit, we acquire additional information; after measurement, we will know completely the value of the bit.

The ability of quantum systems to exist in a “blend" of all their allowed states simultaneously is known as the Principle of Superposition. Even though a qubit can be put in a superposition (6), it contains no more information than a classical bit, in spite of its having infinitely many states. The reason is that information can be extracted only by measurement. But, as we have argued, for any measurement of a qubit with respect to a given orthonormal basis, there are only two possible results, corresponding to the two vectors of the basis. On the other hand, it is not possible to capture more information measuring in two different bases because the measurement changes the state. Even worse, quantum states cannot be cloned, hence it’s impossible to measure a qubit in two different ways (even, indirectly, by using a copy trick, that is copying and measuring the copy).

Is a qubit identical to a probabilistic classical bit? The answer is negative and an argument is that the numbers and in (6 ) encode more than just the probabilities of the outcomes of a measurement in the , basis. For example, the relative phase of and is crucial.

Systems of more than one qubit need a Hilbert space which captures the interaction of the qubits. A two qubit system can be represented by a unit vector in the tensor product of two copies of , i.e. the space . Using Dirac notation, if and are the vectors of a basis in then, the set

is a basis in ; more precisely,



In general, a system containing exactly qubits is represented by copies of tensored together. Therefore, the state space is dimensional. A natural basis for this space consists of tensor products:

A classical string of bits with , , corresponds to the quantum state which is simply denoted by . If and are orthogonal unit vectors in , then the set

is an orthonormal basis in .

In contrast with the classical physics, where the state of a system is completely defined by describing the state of each of its component pieces separately, in a quantum system the state cannot always be described considering only the component pieces. For instance, the state

cannot be decomposed into separate states for each of the two bits. This means that we cannot express this state as a tensor product of two single qubits.

A state that cannot be expressed as a tensor product is called an entangled state. Since the space is spanned by the set , the existence of entangled states proves that the previous set is not a linear space. One can easily find entangled states in an qubit system, for any integer .

Note that it would require vast resources to simulate even a small quantum system on a conventional computer, as such a simulation would require keeping track of exponentially many states: the dimension of the cartesian product of multiple classical particles grows linearly with the number of particles, while the dimension of the tensor product of quantum systems grows exponentially. A reason for the (potential) power of quantum computers is the ability of exploiting the quantum state evolution as a computational mechanism.

Qubits evolve via a “unitary operators". Here are some simple examples of single qubit quantum state transformations. Any unitary operator can be viewed as a single qubit gate. Considering the basis , the transformation is fully specified by its effect on the basis vectors. In order to obtain the associated matrix of an operator , we put the coordinates of in the first column and the coordinates of in the second one. So, the general form of a transformation that acts on a single qubit is a matrix

which transforms the qubit state into the state :

For an arbitrary real number , the rotation is given by

Hence, acts as follows:

One can easily verify that , hence is unitary. Note that in the special case we get the identity transformation of :

We may think of logic gates as transformations. For example, the NOT transformation which interchanges the vectors and , is given by , that is the matrix

It flips that state of its input,

and

The phase shift gate is defined by the following operator: so

Since and , the operators NOT and are also unitary. The operator is also a unitary transformation and we have:

Therefore, its associated matrix is

Here is a really interesting gate, the square-root of NOT (introduced by Deutsch _[49]):



A routine check shows that


(7)
justifying its name. The square-root of NOT is a typical “quantum" gate in the sense that it is impossible to have a single-input/single-output classical binary logic gate that satisfies (7). Indeed, any classical binary

gate is going to output a 0 or a 1 for each possible input 0/1. Assume that we have such a classical square-root of NOT gate acting as a pair of transformations

Then, two consecutive applications of it will not flip the input! (See Williams _and Clearwater _[140] for more details.)

Finally we consider the Hadamard transformation is defined by

This transformation has a number of important applications. When applied to , creates a superposition state

Applied to bits individually, generates a superposition of all possible states. To see this we need some rudiments on tensor products.

Consider two operators and . The tensor product of and is the operator , with the property , for any and . A convenient way is, again, to work with matrices. Let be a matrix and a matrix. The (right) Kronecker product of and is the matrix defined as follows:

For example, if

are two matrices, then we have:

Two important mathematical results are useful:
(a) If and are matrices associated to the operators and , then the matrix associated to is the Kronecker product of and .


(b) The tensor products of two unitary transformations is also unitary. _
Consequently, considering the tensor product of single qubit transformations, we can obtain examples of unitary transformations acting on qubits.

For instance, let be the basis in . Then, can be expressed as

and will be written as
.
We are ready to come back to binary representations of the numbers from to via Hadamard operator. The Walsh–Hdamard transformation is defined recursively by

For example, if then





























































so the associated matrix is



If we apply the Walsh–Hdamard transformation to we get a superposition of all possible states:

























For many quantum algorithms the state


(8)
is very convenient to be an “initial state" because it contains an equal weighted distribution of all basis states. An “empty" register can be “set" in the above state by an application of the Walsh–Hdamard transformation. In this way, using a linear number of operations we can transform one basis state into an exponentially large, equally weighted superposition of all basis states.

Finally, a very useful transformation on is the “controlled-NOT" gate, _ defined as follows:
.
Given the input state , , the output state produced by is , where (mod 2). The first bit is not disturbed (it is a control bit) and the second one interchanges 0 and 1 if and only if the first bit is 1, which corresponds to the logical exclusive-OR (XOR). The transformation is unitary. Its main feature is given by the following property:
cannot be written as a tensor product of two operators.
Similarly, one can define the “controlled-controlled-NOT" transformation, , operating on three qubits, which negates the rightmost bit if and only if the first two are both :


.