 |
Business | Industries | Finance | Tax |
| Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z |
|
|||||
| First Prev [ 1 2 ] Next Last |
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 all 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.
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 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.
Consider an unsorted database with N entries. The algorithm requires an N-dimensional state space H, which can be supplied by log2N qubits.
Let us number the database entries by 0, 1, ... (N-1). Choose an observable, Ω, acting on H, with N distinct eigenvalues 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
and the corresponding eigenvalues by
We are provided with a unitary operatorIn functional analysis, a unitary operator is a bounded linear operator U on a Hilbert space satisfying U U UU I where I is the identity operator. This property is equivalent to any of the following: U is a surjective isometry U preserves the inner produc, Uω, which acts as a subroutineIn computer science, a subroutine function procedure or subprogram is a sequence of code which performs a specific task, as part of a larger program, and is grouped as one, or more, statement blocks; such code is sometimes collected into software librarie that compares database entries according to some search criterion. The algorithm does not specify how this subroutine works, but it must be a quantum subroutine that works with superpositions of states. Furthermore, it must act specially on one of the eigenstates, |ω>, which corresponds to the database entry matching the search criterion. To be precise, we require Uω to have the following effects:
Our goal is to identify this eigenstate |ω>, or equivalently the eigenvalue ω, that Uω acts specially upon.
The steps of Grover's algorithm are as follows:
| Politics | Business | Finance |
 |
 |
 |
|