in the alternative form
This implies that the product of the two factors on the left is a multiple of the number N. So, unless xr/2 ≡±1 mod N, at least one of these factors must be in common with N. Thus we have a good chance of finding a factor of N by computing, gcd(xr/2 + 1, N) and gcd(xr/2 – 1, N).
If r is odd, we choose another x and redo the previous steps till an x is found for which r is even. (With randomly chosen x, an even r will happen 50% of the time.) Once a factor u is found, Shor’s algorithm is repeated on N1 = N/u, and so on till all the factors of N are found.
The quantum part of Shor’s algorithm is determining the period r, and the classical part is computing the function gcd(), which is efficiently done using Euclid’s algorithm.
Shor’s algorithm verified. On Dec 19, 2001 IBM announced that it had built a 7-qubit quantum computer based on seven atoms which, because of the physical properties of those atoms, were able to work together as both the computer’s processor and memory, and that they were able to use the computer to show that Shor’s algorithm works by correctly identifying 3 and 5 as the factors of 1525.
Computational complexity of Shor’s algorithm. On classical computers (Turing machines) the best known factoring algorithm (the number field sieve) runs in O(exp[(64/9)1/3(ln N)1/3(ln ln N)2/3]) steps. This algorithm, therefore, scales exponentially with the input size log N. To give an example, in 1994, a 129-digit number was successfully factored using this algorithm on approximately 1600 workstations scattered around the world; the entire factorization took eight months. It was estimated that factoring a 250-digit number would take roughly 800,000 years and a 1000-digit number would require 1025 years (longer than the age of the universe!). Shor’s algorithm runs in O((log N)3) steps. This is roughly quadratic in the input size, so factoring a 250-digit number would require only a few billion steps.
10.4 Grover’s search algorithm
In 1996, Lov Grover found an efficient quantum search algorithm for the problem: Given an unstructured list of N elements, find a specific element x0 in the list. Grover’s algorithm is much faster than any known classical algorithm26.
For convenience, each element is mapped to a unique index, which is just a number in the range 0 to N-1. Further, assume that N = 2n (the index can be stored in n bits) and that the search problem has exactly M solutions, with 1 ≤M ≤ N. A particular instance of the search problem can be conveniently represented by a function f, which takes an integer x as input in the range 0 to N-1. By definition, f(x) = 1 if x is a solution to the search problem, otherwise f(x) = 0.
We now introduce the notion of a quantum oracle – a black box unitary operator O. The oracle’s unique ability is to recognize solutions of the search problem. It does this by setting an oracle qubit |q〉 in the following manner
where |x〉 is the index register. We can check if x is a solution to our search problem by preparing |x, 0〉, applying the oracle, and checking to see if the oracle qubit has been flipped to |1〉. (Recall that a similar trick was used in the Deutsch problem.)
Here, instead, we apply the oracle with the oracle qubit initially in the state (|0〉 – |1〉)/√2. If x is not a solution (i.e., f(x) = 0) to the search problem, applying the oracle to the state |x(|0〉 -|1〉)/√2 does not change the state. But if x is a solution, then |0〉 and |1〉 get interchanged to give the final state as – |x(|0〉 -|1〉)/√2. That is,
In this representation, the state of the oracle qubit has not changed; it remains (|0〉 – |1〉)/√2 throughout the quantum search algorithm, and therefore can be omitted from further discussion! Hence it is customary to depict the action of the oracle as follows:
and to note that the oracle marks the solution to the search problem by shifting the phase of the solution. There is, however, a subtle point here. In the above operation, the oracle does not know the answer, it can only recognize the answer! It is, of course, possible to do the latter without being able to do the former. For example, finding the prime factors of a very large number is a known difficult problem. But if the prime factors are given, we can easily verify if their product is the given number. The point is that even without knowing the prime factors, one can explicitly construct an oracle, which recognises the factors when it sees one.
Grover’s search algorithm begins with an n-qubit register in the state |0〉⊕n, to which the Hadamard transform is applied and an oracle qubit in the state |0〉 to which HX is applied:
To this we iteratively apply the Grover operator G, comprising the following 4 steps:
- 1. Application of the oracle O.
- 2. Application of the Hadamard operator H⊕n.
- 3. Performing a conditional phase shift on the computer, with every computation basis state except |0〉 receiving a phase shift of -1.
- 4. of the Hadamard operator H⊕n.
The oracle O marks solutions to the search problem by shifting the phase of the solution. Thus
where f(x) = 1 if x is a solution else f(x) = 0.
The third step requires a conditional phase shift to be applied to every computational basis state, except |0〉, such that, |0〉 →|0〉 and |x〉 → -|x〉 for x > 0. This is done by the operator 2|0〉〈0|- I.
Thus, G is
where the operator 2|0〉〈0| – I flips states about the |0〉 axis, i.e., it reverses every basis state except for |0〉. Further let |Ψ〉= H⊕n |0〉. Then since H2 = I, we can rewrite G as
One may show that the operation 2|Ψ〉〈Ψ| – I applied to a general state
Here 〈 α 〉 is the mean value of the αk. For this reason, 2|Ψ〉〈Ψ| – I is sometimes referred to as the inversion about the mean operation.
So, what does the Grover iteration do? Well, it can be seen as a rotation in the two-dimensional space spanned by the starting vector |Ψ〉 and the state consisting of a uniform superposition of solutions to the search problem. To see this clearly, let the prime on the summation sigma symbol below indicate a sum over the M values of x which are solutions to the search problem, and the double prime on the summation sigma symbol a sum over the remaining N-M values of x. Define normalized states as follows:
Hence the initial state |Ψ〉 may now be re-expressed as
So, the initial state of the computer is in the space spanned by |α〉 and |β〉. On this space the oracle O essentially performs a reflection about the vector |α〉 in the plane defined by |α〉 and |β〉. That is,
Similarly, 2|Ψ〉〈Ψ|- I also causes a reflection in the plane defined by |α〉 and |β〉 about the vector |Ψ〉 . And the product of two reflections is a rotation! We notice two things here. First, after the k-th iteration, the state Gk |Ψ〉 remains in the space spanned by |α〉 and |β〉 for all k. Second, it gives us the rotation angle. To get the rotation angle, let
The two reflections that comprise G take |Ψ〉 to
so the rotation angle is in fact θ. Repeated k applications of G takes the state to
Thus, G produces a rotation in the two-dimensional space spanned by |α〉 and |β〉, rotating the space by θ radians per application of G. Repeated application of G rotates the state vector close to |β〉. After R iterations, an observation in the computational basis produces, with high probability, one of the outcomes superposed in |β〉, i.e., a solution to the search problem.
Thus, in the|α〉, |β〉 basis, Grover’s iteration can be written as
where θ is a real number in the range 0 to π/2.
How is R chosen? Note that the initial state of the system was
Hence |Ψ〉 needs to be rotated by π/2 –θ/2 from its initial position to reach the solution state |β〉. Note also that
Therefore, rotating through
radians takes the system to |β〉 . Let CI(x) denote the integer nearest to the real number x, where by convention we round halves down – CI(3.5) = 3, for example – so that CI(x)≤ x. Then applying the Grover iteration
times rotates |Ψ〉 to within an angle π/2 ≤π/4 of |β〉. Observation of the state in the computational basis then yields a solution to the search problem with probability at least one-half. In fact, for specific values of M and N it is possible to achieve a much higher probability of success. For example, when M << N we have θ≈sin θ≈ 2√(M/N), and thus the angular error in the final state is at most θ/2≈ √(M/N), giving a probability of error of at most M/N. Note that R depends on the number of solutions M, but not on the identity of those solutions. Thus, applying Grover’s iteration, G, R times, for the case M = 1, we have
The result x0 is found by measuring the first n- qubits.
Boyer et al27 have shown that if there is a single solution x0, then after (π/8)√(2n) number of Grover iterations the failure rate is 0.5. After (π/4)√(2n) iterations the failure rate drops to 2-n. However, additional iterations will increase the failure rate! For example, after (π/2)√(2n) iterations the failure rate is close to 1. The reason is that unitary transformations are rotations in complex space, and thus while a repeated application of a quantum transformation may rotate the state closer and closer to the desired state for a while, eventually it will rotate past that state and get farther and farther away. Thus, to obtain useful results from a repeated application of a quantum transformation, one must know when to stop.
26 Grover (1997a). See also: Grover (1997b). A popularized version of the algorithm appears in Grover (1999).
27 Boyer, et al (1996).
28 See Chuang, Gershenfeld & Kubinec (1998). See also: Gershenfeld & Chuang (1998).