Grover search algorithm

The first full implementation of Grover search algorithm by NMR was reported by Chuang, Gershenfeld and Kubinec, in 1998 [8], The authors used hydrogen and carbon nuclear spins in chloroform as qubits. One important aspect of this work is the reconstruction of the density matrix, and its comparison with the theoretical prediction. They constructed four optimized sequences of radiofrequency pulses, one for each element labeled by the oracle of the quantum search algorithm (see Chapter 3). The result is shown in Figure 5.3. One observes that the deviation from the theoretical prediction increases with... 

Figure 5.3 NMR implementation of the Grover search algorithm (adapted with permission from Ref. [8]). Each matrix represents a step in the algorithm implementation, and the deviation from the ideal theoretical prediction...

Almost simultaneously to the publication of Chuang, Gershenfeld and Kubinec, Jones, Mosca and Hansen [9] also reported an implementation of Grover search algorithm. They used the two hydrogen nuclei in partially deuterated cytosine as a quantum computer of two qubits. However, their analysis did not included tomographed density matrices. 

Ermakov and Fung [19] reported an implementation of a continuous version of the Grover search algorithm in a system of / = 3/2 nuclei. 

P5.2 - Grover search algorithm can be implemented for any item in a two-qubit system using the corresponding optimized pulse sequences [8] ... 

Figure 16.13 Grover s quantum search algorithm. A superposition of all the items in the database is prepared by a Walsh-Hadamard transformation, WH. With successive INV and DIF operations, the ampUtude of the target item increases toward 1.

HP xenon has also been used to enhance the polarization of a two-qubit NMR quantum computer using the C-enriched chloroform.Using the SPINOE transfer mechanism, this approach led to a polarization enhancement of the chloroform that was approximately 10 times the thermal values for H and Temporal spin-labeling methods along with measurements of the deviation density matrix were used to observe the formation of a pure spin state. The authors then demonstrated their approach by implementing a 2-qubit Grover s search algorithm. 

A classical search algorithm needs about 0(N) operations in order to find a specified item in a disordered list containing N elements. The quantum search algorithm, created by Grover is quadratically faster than its classical analogous, since only OiVN) operations are needed [19]. In a quanmm computer, the number of elements to be searched is the number of possible states of the system A = 2", where n is the number of qubit system. Grover s algorithm is then considered to be of B-type. For a two-qubit system, with N = 2 = 4... 

In Figure 3.11 the application of the Grover algorithm is illustrated, for (a) a two-qubit system and (b) a ten-qubit system N = 2 = 1024). Notice that the amplitude of the searched state oscillates with the number of times the G operator is applied. Thus, one must know in advance how many solutions exist and also the number of elements in the space where the search is being carried on, for there is a optimum number of runs of the algorithm. These numbers are approximately 1 and 25, for n = 2 and n = 10, respectively. 

Grover, L.K. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Aimual ACM Symposium on Theory of Computing, pp. 212-219, New York, NY (1996)... 

Another recent result that illustrates the power of quantum computation compared to classical computation has been dicovered by Grover [11] Say, you search for an element in a database, like you look for a phone number in a phone book. To make things even more difficult, assume the names in the phonebook are not sorted. Classical algorithms need to probe half of the entries in the phone book on average. With a quantum algorithm, it is possible to solve the problem in expected time that grows proportional to the square root of the number of entries. 

Grover s problem has even more an appeal of being important in real world. He considers a database in which the n entries are not sorted, like a phone book where the n names are not listed in alphabetic order. On average, a classical algorithm needs to probe n/2 entries in the phone book before it finds the name for which we search the phone number. Thus, the computational time scales linearly with the number of entries. The quantum algorithm given in [11], can solve the problem in expected time 0 y/n). 

Apart from fast factoring, another potential application of swift quantum computation is the search of unstructured data bases. Thus Grover (1997) has recently proposed a quantum algorithm that can query such files much faster than classical algorithms. 

---