Quantum algorithms

(Lecture notes prepared by Cem Say for the Quantum Algorithms course in the Department of Computer Engineering of Boğaziçi University; see the bibliography. Please report any errors to say@boun.edu.tr)

(Last update: November 24, 2014)

Introduction

Using quantum-mechanical properties of natural particles, it is possible to build computers that are different in some interesting ways than the ones that we are used to.

In our usual computers, a bit is either 0 or 1 at a particular time. As a direct consequence of this, a group (register) of n bits can contain only one of 2ⁿ different numbers at a given time. A quantum bit (qubit), on the other hand, can be in a weighted combination (superposition) of both 0 and 1 at the same time. A group of n qubits can therefore hold all of those 2ⁿ different numbers simultaneously.

The act of measurement is important in quantum physics. When we measure a qubit, it settles on an exact value of 0 or 1, and that is what we see, not a combination of the two values. But which value do we see, 0 or 1? In general, this is a probabilistic event, and the probabilities are determined by the state of the quantum bit before the measurement. To represent the exact state of a qubit, we have to specify two complex numbers, called amplitudes, that describe the particular combination of 0 and 1 in that state.

In the following, we enclose the binary values of quantum registers between the symbols “” and “” to distinguish them from “classical” bits. So the expression represents quantum zero, and represents quantum one. The state of a qubit can then be represented by the expression , where  and  are the amplitudes of and , respectively, in this state. When we measure this qubit, we see with probability ||², and with probability ||². (Recall that, for a complex number c=a+b.i, |c| is the real number .) The laws of physics say that, in any quantum register, the sum of these square terms must be 1. So in our example, ||²+||²=1. Similarly, an n-qubit register will have 2ⁿ amplitudes, each determining the probability that the binary number corresponding to it will be seen when the register is read, and the squares of their absolute values will be 1.
We now provide an alternative notation which makes the description of quantum algorithms easier:
We describe the group of amplitudes that describe the state of a quantum register as a vector. A qubit with state , which is guaranteed to read 0 when it is measured, is represented by the vector , and a qubit with state is represented by the vector . (These two vectors are called the basis states.) So the amplitude of the value is given in the first row of the vector, and the amplitude of the value is given in the second row. We assume that we have the machinery to set any qubit to one of these two values at the beginning of our algorithm. An arbitrary qubit state is then represented by the vector , where  and  are complex numbers and ||²+||²=1.

The state of a register consisting of n qubits is represented by the tensor () product of the individual states of the qubits in it.

For two matrices A and B, where A is n by m, AB equals:

So the tensor product of two vectors and equals:

So if we have two qubits in a register, the state where both bits are can be represented as , and corresponds to the vector . Similarly, , , and correspond to the vectors , , and , respectively. (These four, corresponding to the only four possibilities that would exist if this was a classical register, are called basis states.) An arbitrary state of a 2-qubit register can then be described as , where, of course,

(This is called an Hadamard gate.) When the input is , this program changes the state of the qubit to

that is, to . So when you read the qubit at the end, you have exactly 50% chance of seeing a 0, and an equal chance of seeing a 1. Classical computers can never create truly random numbers, but this program can.

The combined effect of several single-qubit programs which run parallelly on the qubits in a register can be represented as the tensor product of their individual matrices. So if we apply the H program to each qubit of a 2-qubit register, the result of this procedure can be calculated by multiplying the matrix

with the 4-element amplitude vector describing the initial state of the two qubits. We can generalize this to n qubits easily. So when you have an n-qubit register, the effect of applying H to each qubit parallelly can be computed by multiplying the matrix that you would obtain by taking the tensor product of n H’s with the 2ⁿ-element vector describing the initial state of the register. Generalizing the example above, if this n-qubit register originally contains the value , it is transformed to the “mixed” state

by this program, and we would see each of the 2ⁿ binary numbers x with equal probability when we observe the register.

When the input to a single Hadamard gate is , we see that the output is

,

or, in our alternative notation, .

Let’s see what the parallel application of H gates do to a 2-qubit register originally containing :

,

or .

As these examples indicate, whenever we apply the H gate parallelly to a register initially at an arbitrary basis state , where x is a binary number with n bits, the output state is a superposition of all the different 2ⁿ basis states, where the absolute value of the amplitude of each basis state is , and the sign of the amplitude of such a basis state in the resulting superposition is positive if an even number of bits which were 1 in the original state are still 1 in , and negative otherwise. In other words, the parallel application of H gates to all qubits of an n-qubit register initially at state results in the state

,

where mod 2, such that x_i is the ith bit of x.

1. 
   Initialize the register so that the first n qubits are , and the last one is .
   
2. 
   Apply the H gate to each qubit.
   
3. 
   Apply B to the register.
   
4. 
   Apply the H gate to the first n qubits.
   
5. 
   Read (measure) the number z written in the first n qubits.
   
6. 
   If z= , f is constant, otherwise, f is balanced.
   

Let us see why the algorithm works correctly: At the end of stage 2, the state of the register is

At the end of stage 3, we have, for each x in the summation, such a term of the state in the register:

So the overall state after stage 3 is:

After stage 4, we end up with:

Now, for any number z, the probability that we see it at stage 5 is the square of its amplitude, that is,

So the probability of seeing 0ⁿ is

for a non-trivial s, the problem is to determine if f is one to one, if it is not then to find s. (We denote the functionality of U_f as a unitary transformation: )

Now, if f is one to one then both the domain and range (mirror of the domain under f) of f has the same cardinality . The state shown above is a superposition of the members of the Cartesian product of the domain and range of f. Therefore, states of the form are superposed, each with an amplitude equal to either or . Then, if the state of the first register is measured after Step 3, the probabilities for observing each of the basis states are equal and given by . Hence the outcome of such a measurement would be a random value between 0 and .

If then the amplitude for becomes zero. So if f is not one to one, then measuring the state of the first register after Step 3, returns a value of j such that .

We run these four steps n1 times to form a system of equations of the form . If a nontrivial s exists, then these equations are linearly independent with probability at least ¼. Why? Consider any (i1)-member prefix of our sequence of observations, namely t₁, t₂, …, t_i-1, where 2  i  n1. At most 2^i-1 n-bit vectors are linear combinations of these. (Note that it is now useful to view the t’s as vectors of bits, and the relevant operation among them is .) Since the maximum number of n-bit vectors t such that ts=0 is 2^n-1, the minimum number of vectors that are not the combinations of i1 vectors is 2^n-12^i-1. As a result, the probability that the i^th vector t_i is independent from the first i1 vectors is at least (2^n-12^i-1)/2^n-1  . Using this fact, and the constraint that the first observation should not be the all-zero vector, we see that the probability that one obtains n independent vectors is at least which can, with a little bit of extra cleverness, be shown to be greater than ¼.

Here is Grover’s algorithm for an n+1 qubit register, where n>2:

1. 
   Initialize the register so that the first n qubits are , and the last one is .
   
2. 
   Apply the H gate to each qubit.
   
3. 
   Do the following r times, where r is the nearest integer to :
   
4. 
   Apply G to the register.
   
5. 
   Apply the program V, which will be described below, to the first n qubits.
   
6. 
   Read (measure) the number written in the first n qubits, and claim that this is the value which makes f 1.
   

The program V is defined as the by matrix which has the number in all its main diagonal entries, and everywhere else.

We will now examine what each iteration of the loop does to the register.

At the end of the first execution of stage 3.a, we have, for each x in the summation, such a term of the state in the register:





.

Now let us generalize this to an arbitrary execution of this stage, where the amplitude of each need not be equal. It is easy to see that, if the last qubit is to start with, the resulting amplitude of a particular remains the same if and only if f(x) = 0. For the one value which makes f(x) = 1, the sign of the amplitude is reversed. And the last qubit remains unchanged at . We can therefore “forget” the last qubit and view stage 3.a as the application of an n-qubit program which flips the sign of the amplitude of the searched number and leaves everything else unchanged in the first n qubits.

Multiplication with the by matrix which has the number in all its entries yields the state

where a is the average of the amplitudes _i in the original state.

On the other hand, multiplying

with the by matrix which has -1 in all its main diagonal entries, and 0 everywhere else just flips the signs of all the _i in the original state. So what do we get when we add these two result vectors? Each basis state , which had the amplitude before stage 3.b, obtains the amplitude at the end of this stage. A useful way of interpreting this stage is saying that each amplitude is mapped to , that is, every amplitude that was u units above (below) the average amplitude before the execution is at u units below (above) the average amplitude after the execution.

At this point, we start seeing the logic of Grover’s algorithm: In the beginning, all the numbers in the n-qubit collection have the same amplitude, namely, . Stage 3.a flips the sign of the amplitude of the searched number , so now the amplitudes of all the other numbers are very close to the average amplitude a, but the amplitude of is approximately –a, at a distance of nearly 2a from the average. Stage 3.b restores the sign of ’s amplitude to positive, but during this process, its value becomes approximately 3a. Clearly, the amplitude of , and therefore the probability that will be observed when we read the first n qubits, will grow further and further as the iterations of the loop continue, and this amplitude will reach a value greater than after a certain number of iterations. Note that, if the amplitude of grows so much that the average at the beginning of stage 3.b becomes negative, each iteration would start shrinking, rather than growing, the amplitude of , so it is important to know exactly how many times this loop should be iterated. We are now supposed to find what that required number of iterations, which is also essential in the calculation of the time complexity of this algorithm, is.

To make this calculation, let us adopt a geometric visualization of the vectors we use to represent the states of our quantum registers. If we are talking about an n-qubit collection, as in this case, there are basis states, as already mentioned. An arbitrary state of our collection is then a vector with length one in the -dimensional space where each of those basis states can be viewed to be at an angle of /2 radians from each other. An arbitrary state is just the vector sum of all the component vectors in the expression for it. The length of each of these component vectors is just the absolute value of the corresponding amplitude. The application of a quantum program on an n-qubit register has just the effect of rotating the unit vector representing its state to a new alignment in this space. The probability of observation of a particular basis value x when we are at an arbitrary state = can be viewed as the square of the length of the projection of vector onto the vector . This projection’s length is just equal to the cosine of the angle between and . (Do not worry about the amplitudes being complex numbers in general; most what you already know about vectors is still valid here. By the way, in the particular example of Grover’s algorithm, the amplitudes have no imaginary components at any stage of the execution.)

With this visualization method in mind, we will examine what a single iteration of stage 3 makes to the n-qubit state. We already know that stage 3.a flips the sign of the amplitude of the component vector corresponding to searched number and leaves everything else unchanged. In the beginning of the first iteration, the state vector is = . So the angle between vector and each one of the basis state vectors is . In particular, the angle between and is . Think about the initial vector as the sum , where the second term is just what you get if you subtract from , and is the unit vector in that direction. Since the job of stage 3.a is to flip the sign of the amplitude of and leave everything else unchanged, the resulting vector is . The angle between this new vector and is , that is, the same as before! The vector rotated all right, but it ended up at the same angle from all the basis state vectors. Only its alignment changed with respect to . It is important to see that this is what any iteration of stage 3.a does: To reflect the current state vector around the axis in the plane defined by the and axes.

To have a deeper understanding of what is going on, let’s introduce more of the notation used in the quantum literature. For any column vector , the expression denotes the row vector obtained by replacing each component a+b.i of with the number a-b.i, and then writing these in a row. Note that the expression describes a square matrix. Now, the matrix of stage 3.a can be seen to equal , where I is the identity matrix of the appropriate size. So we know that a program of the form , when applied to a register in state , where the angle between the and vectors is /2, reflects the state vector around the axis in the plane defined by the and axes. But here comes another surprise: It turns out that, in quantum computing, multiplying a program’s matrix with any number of the form , where x is any real number (recall that ) yields a program which is completely equivalent to the original one from the point of view of the user. (This is because the measurement probabilities corresponding to the two amplitudes a+b.i and .(a+b.i) are identical, as you can check using the formula for given above.) This means that and (which is just multiplied by ) can be interchanged without changing the functionality of the program. So we can replace the program of stage 3.a with the completely equivalent program , which can easily be seen to transform the input to , that is, to reflect it around the axis, if we prefer such an interpretation.

Now think about the plane defined by the and axes, with horizontal and vertical. After stage 2, our state is , so it is a vector within the first quadrant of this plane. The angle between and can be seen to be . When stage 3.a acts, our vector is reflected around the axis. Since itself was in the - plane, and we reflected it around , the resulting vector is still in the - plane, radians away from the axis in the fourth quadrant. When stage 3.b acts, this vector is reflected around the axis. Once again, the resulting vector is in the - plane, and it is now radians from the axis in the first quadrant. It is easy to see that the combined effect of stage 3 for any iteration in this algorithm is to rotate the vector that it finds for radians in the counterclockwise direction in the - plane. We want to iterate the loop until the state gets sufficiently close to the axis so that the probability of observing during a measurement is greater than ½. Recall that the state vector was radians away from the axis before the loop. Clearly, a number r of iterations, where would be ideal. Since r has to be an integer, this is not always possible, so we settle for . Note that if the loop iterates this many times, the resulting vector can be at most radians away from the axis, and the probability of observing at stage 4 would be at least , which is greater than ½ for all n 2.

So what is the time complexity of Grover’s algorithm? If we measure it in terms of , which is the size of the “database” being searched, the loop iterates times. For big N, the numerator approaches , whereas tends to near the value of its own argument when the argument is nearing zero, so we can see that the time complexity is indeed O( ).
The reasoning above can be generalized easily to the case where the number of inputs for which f returns 1 is not one but M≤N/2.
Note that in all the algorithms above, we just analyzed the number of required quantum oracle calls and showed that they were better than the number of required classical oracle calls in the best possible classical algorithms for that job. A complete analysis would also require quantifying the amount of resources (in terms of, for instance, the number elementary quantum gates from a fixed set) that would be required to implement the rest of the algorithms as a function of the size of the input. Although we do not give that analysis here, those algorithms turn out to have good (polynomial) complexities in that regard as well.