5.5 Grover’s algorithm

Many problems, ranging from sorting and graph colouring to database search, can be phrased as search problems of the form “find some such that is true", where is an appropriate predicate. For example:
(a) Given an element vector , find a permutation of such that for all we have .
(b) Given a graph with vertices and edges , and a set of colours , find a colouring map from to such that for all in , .

           
                                                                                        Figure 17: Lov Grover

Some problems, such as 3-SAT or graph colourability, have an “inner structure" that can be exploited to construct full solutions from (smaller) partial solutions; in such cases, efficient algorithms are known. But, in general, the search space has no special structure. To see the difference between a structured and an unstructured search space think, with Brassard _[22], of the task of finding someone’s (you know her name) phone number in a city’s directory versus the task of finding the name of a stranger whose phone number you happen to know. To search a simple unstructured file, a computer would have to run through, on average, half of the data to locate an entry satisfying . It is easily proven that there can be, in general, no shortcuts, so randomly testing the predicate seems the best strategy that can be adopted on a conventional computer. For a search space of size , the general unstructured search problem is of complexity O(), once the time it takes to test the predicate is factored out. When we said “no shortcuts are possible in general" we meant “no shortcuts are possible if we use conventional computers". However, Grover _[66] showed that the unstructured search problem can be solved with bounded probability within O() time with a quantum computer.

This advantage is not dramatic for our example of locating a name in the phone directory of a city; however, things are different if we are interested in databases that are so large that they would not fit in the memory of all the world’s (conventional) computers put altogether. Such databases cannot “exist" explicitly, of course, but they can be specified by a rule that allows the construction of any required record on demand. As an example consider one of the most widely used systems to protect the confidentiality of information, the Data Encryption Standard (DES). Encipher and decipher are controlled by a 56-bit key, which the legitimate participants must share in secret. The goal of an eavesdropper, that has intercepted matching pairs of clear and enciphered text, is to find the key that maps one into the other. This problem can be described by a virtual “phone directory" in which each possible key is a name and the enciphered text with that key is the corresponding phone number. Given the intercepted enciphered text, our name-finding problem corresponds to searching for the required secret key to decode the rest of the enciphered text. An exhaustive search needs to try an average of keys before hitting the right one, an operation that takes more than 1 year even if one billion keys are checked every second. By comparison, Grover’s algorithm can solve the problem, after quantum-DES enciphering the known clear text, in just 185 million times. Hence, Grover’s quantum searching algorithm can “in principle" be used to break classical cryptographic systems such as DES.

Grover’s search algorithm _is more efficient than any known conventional algorithm searching a completely unstructured solution space. More precisely, Grover’s algorithm is optimal for completely unstructured searches, see Zalka _[144]. But, many search problems involve searching a structured solution space. One would expect that this extra information would enable more efficient searching strategies. Hogg _[74] has developed quantum algorithms that use the problem structure in a similar way to classical heuristic search algorithms. Small cases indicate that Hogg’s algorithms are more efficient than Grover’s algorithm applied to structured search problems, but the speed up is likely to be only polynomial.

As we already pointed out, Grover’s _algorithm searches an unstructured list of size to find one item satisfying a given condition. It is assumed that it is easy to check whether an arbitrary element satisfies the given condition. Let be such that . Assume that predicate is implemented by a quantum gate

where true is encoded as 1. Grover’s algorithm consists of the following steps:

Step 1. Prepare a register containing a superposition of all of the possible values .
Step 2. Compute on this register.
Step 3. Change amplitude to , for all such that
Step 4. Apply inversion about the average to increase amplitude of with
Step 5. Repeat steps 2 through 4 times.
Step 6. Read the result. _

Computing for all possible inputs can be done by applying to a register containing the superposition

with a register set to 0:

This is done with the classical technique in steps 1 and 2.

The difficulty is, as usual, to obtain a useful result from this superposition. For any such that is true, will be part of the result superposition, but chances are very slim to get it via measurement, , since its amplitude is . The “trick" is to change the resulting quantum state in such a way to greatly increase the amplitude of all vectors , for which the predicate is true, and decrease the amplitude of vectors , for which the predicate is false. This change in amplitudes is obtained using the inversion about the average transformation; it can be accomplished with O() quantum gates.

The transformation

is performed by the unitary matrix

The matrix can be defined as where is the Walsh–Hdamard transformation and is the matrix:

Next we explain how the inversion of amplitudes works. Consider the gate array

Apply to the superposition

and choose

to obtain a state where the sign of all with has been changed, but is unchanged.

Grover’s algorithm is optimal up to a constant factor; no quantum algorithm can perform an unstructured search faster. If there is only a unique such that is true, then after iterations of steps 2 through 4 the failure rate is . After iterating times the failure rate drops to . For a more detailed analysis see Gruska _[67].

We finish with a more general remark. Additional iterations will increase the failure rate: for example, after iterations, the failure rate is close to 1. This is an important feature of many quantum algorithms, which has little counterpart in conventional computing. Repeating quantum procedures may improve results for a while, but after some repetitions the results will get worse again. Quantum procedures are unitary transformations, which are rotations of complex space; repeated applications of a quantum transform may rotate the state closer and closer to the desired state for a while, but eventually it will rotate past the desired state to get further and further from the desired state. Thus to obtain useful results from a repeated application of a quantum transformation, it is paramount to know when to stop.