Quantum search algorithm

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.

The quantum search algorithm and teleportation were also experimentally tested. 

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

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

J.A. Jones, M. Mosca, R.H. Hansen, Implementation of a quantum search algorithm on a quantum computer,... 

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. 

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. 

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. 

For such applications of classical optimization theory, the data on energy and gradients are so computationally expensive that only the most efficient optimization methods can be considered, no matter how elaborate. The number of quantum chemical wave function calculations must absolutely be minimized for overall efficiency. The computational cost of an update algorithm is always negligible in this context. Data from successive iterative steps should be saved, then used to reduce the total number of steps. Any algorithm dependent on line searches in the parameter hyperspace should be avoided. 

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. 

Non-linear programming is a fast growing subject and much research is being done and many new algorithms appear every year. It seems to the Reporters that the current area of major interest in the field is the area of variable-metric methods, particularly those not needing accurate linear searches. Unfortunately, from a quantum chemical point of view, such methods are liable to be of use only in exponent and nuclear position optimization and in this context, as we have seen, Newton-like methods are also worth serious consideration. 

---