Information AboutGrover's Algorithm |
|
Classically, searching an unsorted database requires a Linear Search , which is ''O(N)'' in time. Grover's algorithm, which takes ''O(N1/2)'' time, is the fastest possible quantum algorithm for searching an unsorted database. It provides "only" a quadratic speedup, unlike other quantum algorithms, which can provide exponential speedup over their classical counterparts. However, even quadratic speedup is considerable when ''N'' is large. Like many quantum computer algorithms, Grover's algorithm is probabilistic, in the sense that it gives the correct answer with high Probability . The probability of failure can be decreased by repeating the algorithm. (An example of a deterministic quantum algorithm is the Deutsch-Jozsa Algorithm , which always produces the correct answer with probability one.) APPLICATIONS Although the purpose of Grover's algorithm is usually described as "searching a database", it may be more accurate to describe it as "inverting a function". Roughly speaking, if we have a function ''y=f(x)'' that can be evaluated on a quantum computer, Grover's algorithm allows us to calculate ''x'' when given ''y''. Inverting a function is related to the searching of a database because we could come up with a function that produces a particular value of ''y'' if ''x'' matches a desired entry in a database, and another value of ''y'' for other values of ''x''. Grover's algorithm can also be used for estimating the Mean and Median of a set of numbers, and for solving the Collision Problem . In addition, it can be used to solve NP-complete problems by performing exhaustive searches over the set of possible solutions. This would result in a considerable speedup over classical solutions, even though it does not provide the "holy grail" of a polynomial-time solution. Below, we present the basic form of Grover's algorithm, which searches for a single matching entry. The algorithm can be further optimized if there is more than one matching entry and the number of matches is known beforehand. SETUP Consider an unsorted database with N entries. The algorithm requires an ''N''-dimensional State Space ''H'', which can be supplied by log''2N'' Qubit s. Let us number the database entries by 0, 1, ... (''N''-1). Choose an observable, ''Ω'', acting on ''H'', with ''N'' distinct Eigenvalue s whose values are all known. Each of the eigenstates of ''Ω'' encode one of the entries in the database, in a manner that we will describe. Denote the eigenstates (using Bra-ket Notation ) as #Apply the operator : Furthermore, the probability of obtaining the wrong answer becomes O(1/N), which goes to zero for large N. EXTENSIONS If, instead of 1 matching entry, there are ''k'' matching entries, the same algorithm works but the number of iterations must be ''π(N/k)1/2/4'' instead of ''πN1/2/4''. There are several ways to handle the case if ''k'' is unknown. For example, one could run Grover's algorithm several times, with : iterations. For any ''k'', one of iterations will find a matching entry with a sufficiently high probability. The total number of iterations is at most : which is still O(''N1/2''). It is known that Grover's algorithm is optimal. That is, any algorithm that accesses the database only by using the operator Uω must apply Uω at least as many times as Grover's algorithm but not as many as Shor's (Bernstein et al., 1997). REFERENCES # Grover L.K.: ''A fast quantum mechanical algorithm for database search'', Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212 (available online) # Grover L.K.: ''From Schrödinger's equation to quantum search algorithm'', American Journal of Physics, 69(7): 769-777, 2001. Pedagogical review of the algorithm and its history. # http://www.bell-labs.com/user/feature/archives/lkgrover/ # Bennett C.H., Bernstein E., Brassard G., Vazirani U., ''The strengths and weaknesses of quantum computation''. SIAM Journal On Computing 26(5): 1510-1523 (1997). Shows the optimality of Grover's algorithm. |
|
|