The quantum 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 

At the second stage, an operator, called Grover operator - G, is applied iteratively to the system, approximately / times, and after that the searched state will have a high probability of being found, when a measurement is performed. This operator is composed of four others, represented by G = H [2 0 (0 -1] H O, and they will be discussed below. 

The first operator of G is an unitary controlled operation, represented by G. It inverts the phase of the state, which is being searched. This controlled operation is constructed by applying the transformation indicated on Equation (3.8.8), such as f x) = 1 when x is the searched item and /(x) = 0 otherwise. Notice that the operation O only acts on the second set of qubits, leaving the first one intact. 

The operation 0 is considered to be a black box called an Oracle, whose construction has to be built individually for each item to be searched. 

Reminding that the Oracle acts only on the second set of qubits, in order to invert the phase of the searched state, it is necessary to prepare the system in the state x)[ 0)- l)]/V2. In this case, when the Oracle is applied, the system will evolve as described on Equation (3.8.9), similarly to what happens in the Deutsch algorithm. As it can be seen, the solution gets marked after the Oracle operation, inverting the phase of the desired state, i.e. x) — x), if x) is the desired item. 

---

The quantum search algorithm and teleportation were also experimentally tested. 

As discussed in the Chapter 3, the quantum search algorithm is one of the most important for quantum computation. It is used to search for one or more specific quantum states in an uniform superposition. It is often compared to a search of a name (or number) in a disordered list. The main feature of this algorithm is the operation, performed by the oracle , which labels the state (or states) to be searched, by inverting its (their) phase. The second operation is the inversion about the mean value, i.e. the amplitude of each state in the system. These two operations must be applied to the system a certain number of times, which depends on the number of items one is looking for and the total number of elements on the system. For a two qubit system, the number of searches is only 1. Another important application is the ability to use this algorithm for searching the solution of a specific problem, which can be done by preparing the action of the oracle operator. 

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 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.

This formula is exact for a quadratic function, but for real problems a line search may be desirable. This line search is performed along the vector — x. . It may not be necessary to locate the minimum in the direction of the line search very accurately, at the expense of a few more steps of the quasi-Newton algorithm. For quantum mechanics calculations the additional energy evaluations required by the line search may prove more expensive than using the more approximate approach. An effective compromise is to fit a function to the energy and gradient at the current point x/t and at the point X/ +i and determine the minimum in the fitted function. 

Non-derivative Methods.—Multivariate Grid Search. The oldest of the direct search methods is the multivariate grid search. This has a long history in quantum chemistry as it has been the preferred method in optimizing the energy with respect to nuclear positions and with respect to orbital exponents. The algorithm for the method is very simple. In this and subsequent algorithms we use x to indicate the variables and a to indicate a chosen point. 

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. 

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. 

Exploration of the PES to localize the minima and the associated stmctures is now a routine job performed by all well-known quantum chemistry packages (Gaussian, ADF, Gamess, NWChem, ORCA,...) see for instance [13] for detailed discussions on the methods and algorithms for conformational search on the PES. Conformational search is also called geometry optimization. This is a rather easy task for molecular systems with a reasonable number of internal degrees of... 

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)... 

Marchal, R., Carbonni re, R, Pouchan, C. (2010). A global search algorithm of minima exploration for the investigation of low lying isomers of clusters from DET-based potential energy surface. A theoretical study of Sin and Si iAl clusters. International Journal of Quantum Chemistry, 110(12), 2256-2259. 

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). 

---