HOME

TheInfoList



OR:

In
quantum computing Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Thou ...
, Grover's algorithm, also known as the quantum search algorithm, refers to a
quantum algorithm In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite seq ...
for unstructured search that finds with high probability the unique input to a
black box In science, computing, and engineering, a black box is a system which can be viewed in terms of its inputs and outputs (or transfer characteristics), without any knowledge of its internal workings. Its implementation is "opaque" (black). The te ...
function that produces a particular output value, using just O(\sqrt) evaluations of the function, where N is the size of the function's
domain Domain may refer to: Mathematics *Domain of a function, the set of input values for which the (total) function is defined ** Domain of definition of a partial function **Natural domain of a partial function **Domain of holomorphy of a function *Do ...
. It was devised by Lov Grover in 1996. The analogous problem in classical computation cannot be solved in fewer than O(N) evaluations (because, on average, one has to check half of the domain to get a 50% chance of finding the right input). Charles H. Bennett, Ethan Bernstein,
Gilles Brassard Gilles Brassard, is a faculty member of the Université de Montréal, where he has been a Full Professor since 1988 and Canada Research Chair since 2001. Education and early life Brassard received a Ph.D. in Computer Science from Cornell Univ ...
, and Umesh Vazirani proved that any quantum solution to the problem needs to evaluate the function \Omega(\sqrt) times, so Grover's algorithm is
asymptotically optimal In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly en ...
. Since classical algorithms for
NP-complete problems In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
require exponentially many steps, and Grover's algorithm provides at most a quadratic speedup over the classical solution for unstructured search, this suggests that Grover's algorithm by itself will not provide polynomial-time solutions for NP-complete problems (as the square root of an exponential function is an exponential, not polynomial, function). Unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts, Grover's algorithm provides only a quadratic speedup. However, even quadratic speedup is considerable when N is large, and Grover's algorithm can be applied to speed up broad classes of algorithms. Grover's algorithm could brute-force a 128-bit symmetric cryptographic key in roughly 264 iterations, or a 256-bit key in roughly 2128 iterations. As a result, it is sometimes suggested that symmetric key lengths be doubled to protect against future quantum attacks.


Applications and limitations

Grover's algorithm, along with variants like
amplitude amplification Amplitude amplification is a technique in quantum computing which generalizes the idea behind the Grover's search algorithm, and gives rise to a family of quantum algorithms. It was discovered by Gilles Brassard and Peter Høyer in 1997, and ind ...
, can be used to speed up a broad range of algorithms. In particular, algorithms for NP-complete problems generally contain exhaustive search as a subroutine, which can be sped up by Grover's algorithm. The current best algorithm for
3SAT In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies ...
is one such example. Generic
constraint satisfaction problem Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constr ...
s also see quadratic speedups with Grover. These algorithms do not require that the input be given in the form of an oracle, since Grover's algorithm is being applied with an explicit function, e.g. the function checking that a set of bits satisfies a 3SAT instance. Grover's algorithm can also give provable speedups for black-box problems in
quantum query complexity In computational complexity the decision tree model is the model of computation in which an algorithm is considered to be basically a decision tree, i.e., a sequence of ''queries'' or ''tests'' that are done adaptively, so the outcome of the previ ...
, including element distinctness and the collision problem (solved with the Brassard–Høyer–Tapp algorithm). In these types of problems, one treats the oracle function ''f'' as a database, and the goal is to use the quantum query to this function as few times as possible.


Cryptography

Grover's algorithm essentially solves the task of ''function inversion''. 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. Consequently, Grover's algorithm gives broad asymptotic speed-ups to many kinds of brute-force attacks on
symmetric-key cryptography Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between ...
, including
collision attack In cryptography, a collision attack on a cryptographic hash tries to find two inputs producing the same hash value, i.e. a hash collision. This is in contrast to a preimage attack where a specific target hash value is specified. There are roug ...
s and
pre-image attack In cryptography, a preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage (set of possible inputs). In the context of attack, the ...
s. However, this may not necessarily be the most efficient algorithm since, for example, the parallel rho algorithm is able to find a collision in SHA2 more efficiently than Grover's algorithm.


Limitations

Grover's original paper described the algorithm as a database search algorithm, and this description is still common. The database in this analogy is a table of all of the function's outputs, indexed by the corresponding input. However, this database is not represented explicitly. Instead, an oracle is invoked to evaluate an item by its index. Reading a full database item by item and converting it into such a representation may take a lot longer than Grover's search. To account for such effects, Grover's algorithm can be viewed as solving an equation or satisfying a constraint. In such applications, the oracle is a way to check the constraint and is not related to the search algorithm. This separation usually prevents algorithmic optimizations, whereas conventional search algorithms often rely on such optimizations and avoid exhaustive search. The major barrier to instantiating a speedup from Grover's algorithm is that the quadratic speedup achieved is too modest to overcome the large overhead of near-term quantum computers. However, later generations of
fault-tolerant Fault tolerance is the property that enables a system to continue operating properly in the event of the failure of one or more faults within some of its components. If its operating quality decreases at all, the decrease is proportional to the ...
quantum computers with better hardware performance may be able to realize these speedups for practical instances of data.


Problem description

As input for Grover's algorithm, suppose we have a function f\colon \ \to \. In the "unstructured database" analogy, the domain represent indices to a database, and if and only if the data that ''x'' points to satisfies the search criterion. We additionally assume that only one index satisfies , and we call this index ''ω''. Our goal is to identify ''ω''. We can access ''f'' with a
subroutine In computer programming, a function or subroutine is a sequence of program instructions that performs a specific task, packaged as a unit. This unit can then be used in programs wherever that particular task should be performed. Functions ma ...
(sometimes called an
oracle An oracle is a person or agency considered to provide wise and insightful counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. As such, it is a form of divination. Description The wor ...
) in the form of a unitary operator ''Uω'' that acts as follows: :\begin U_\omega , x\rang = -, x\rang & \text x = \omega \text f(x) = 1, \\ U_\omega , x\rang = , x\rang & \text x \ne \omega \text f(x) = 0. \end This uses the N-dimensional
state space A state space is the set of all possible configurations of a system. It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory. For instance, the t ...
\mathcal, which is supplied by a register with n = \lceil \log_ N \rceil
qubit In quantum computing, a qubit () or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, ...
s. This is often written as :U_\omega, x\rang = (-1)^, x\rang. Grover's algorithm outputs ''ω'' with probability at least ''1/2'' using O(\sqrt) applications of ''Uω''. This probability can be made arbitrarily large by running Grover's algorithm multiple times. If one runs Grover's algorithm until ''ω'' is found, the expected number of applications is still O(\sqrt), since it will only be run twice on average.


Alternative oracle definition

This section compares the above oracle U_\omega with an oracle U_f. ''Uω'' is different from the standard quantum oracle for a function ''f''. This standard oracle, denoted here as ''Uf'', uses an ancillary qubit system. The operation then represents an inversion ( NOT gate) on the main system conditioned by the value of ''f''(''x'') from the ancillary system: :\begin U_f , x\rang , y\rang = , x\rang , \neg y\rang & \text x = \omega \text f(x) = 1, \\ U_f , x\rang , y\rang = , x\rang , y\rang & \text x \ne \omega \text f(x) = 0, \end or briefly, : U_f , x\rang , y\rang = , x\rang , y \oplus f(x)\rang. These oracles are typically realized using
uncomputation Uncomputation is a technique, used in reversible circuits, for cleaning up temporary effects on ancilla bits so that they can be re-used. Uncomputation is a fundamental step in quantum computing Quantum computing is a type of computation who ...
. If we are given ''Uf'' as our oracle, then we can also implement ''Uω'', since ''Uω'' is ''Uf'' when the ancillary qubit is in the state , -\rang = \frac1\big(, 0\rang - , 1\rang\big) = H, 1\rang: : \begin U_f \big( , x\rang \otimes , -\rang \big) &= \frac1 \left( U_f , x\rang , 0\rang - U_f , x\rang , 1\rang \right)\\ &= \frac1 \left(, x\rang , f(x)\rang - , x\rang , 1 \oplus f(x)\rang \right)\\ &= \begin \frac1 \left(-, x\rang , 0\rang + , x\rang , 1\rang\right) & \text f(x) = 1, \\ \frac1 \left( , x\rang , 0\rang - , x\rang , 1\rang \right) & \text f(x) = 0 \end \\ &= (U_\omega , x\rang) \otimes , -\rang \end So, Grover's algorithm can be run regardless of which oracle is given. If ''Uf'' is given, then we must maintain an additional qubit in the state , -\rang and apply ''Uf'' in place of ''Uω''.


Algorithm

The steps of Grover's algorithm are given as follows: # Initialize the system to the uniform superposition over all states
, s\rangle = \frac \sum_^ , x\rangle. # Perform the following "Grover iteration" r(N) times: ## Apply the operator U_\omega ## Apply the ''Grover diffusion'' operator U_s = 2 \left, s\right\rangle \left\langle s\ - I # Measure the resulting quantum state in the computational basis. For the correctly chosen value of r, the output will be , \omega\rang with probability approaching 1 for ''N'' ≫ 1. Analysis shows that this eventual value for r(N) satisfies r(N) \leq \Big\lceil\frac\sqrt\Big\rceil. Implementing the steps for this algorithm can be done using a number of gates linear in the number of qubits. Thus, the gate complexity of this algorithm is O(\log(N)r(N)), or O(\log(N)) per iteration.


Geometric proof of correctness

There is a geometric interpretation of Grover's algorithm, following from the observation that the quantum state of Grover's algorithm stays in a two-dimensional subspace after each step. Consider the plane spanned by , s\rang and , \omega\rang; equivalently, the plane spanned by , \omega\rang and the perpendicular
ket Kentucky Educational Television (KET) is a state network of PBS member television stations serving the U.S. Commonwealth of Kentucky. It is operated by the Kentucky Authority for Educational Television, an agency of the Kentucky state governm ...
\textstyle , s'\rang = \frac\sum_ , x\rang. Grover's algorithm begins with the initial ket , s\rang, which lies in the subspace. The operator U_ is a reflection at the hyperplane orthogonal to , \omega\rang for vectors in the plane spanned by , s'\rang and , \omega\rang, i.e. it acts as a reflection across , s'\rang. This can be seen by writing U_\omega in the form of a Householder reflection: : U_\omega = I - 2, \omega\rangle\langle \omega, . The operator U_s = 2 , s\rangle \langle s, - I is a reflection through , s\rang. Both operators U_s and U_ take states in the plane spanned by , s'\rang and , \omega\rang to states in the plane. Therefore, Grover's algorithm stays in this plane for the entire algorithm. It is straightforward to check that the operator U_s U_ of each Grover iteration step rotates the state vector by an angle of \theta = 2\arcsin\tfrac . So, with enough iterations, one can rotate from the initial state , s\rang to the desired output state , \omega\rang. The initial ket is close to the state orthogonal to , \omega\rang: : \lang s', s\rang = \sqrt. In geometric terms, the angle \theta/2 between , s\rang and , s'\rang is given by : \sin \frac = \frac. We need to stop when the state vector passes close to , \omega\rang; after this, subsequent iterations rotate the state vector ''away'' from , \omega\rang, reducing the probability of obtaining the correct answer. The exact probability of measuring the correct answer is : \sin^2\left( \Big( r + \frac \Big)\theta\right), where ''r'' is the (integer) number of Grover iterations. The earliest time that we get a near-optimal measurement is therefore r \approx \pi \sqrt / 4.


Algebraic proof of correctness

To complete the algebraic analysis, we need to find out what happens when we repeatedly apply U_s U_\omega. A natural way to do this is by eigenvalue analysis of a matrix. Notice that during the entire computation, the state of the algorithm is a linear combination of s and \omega. We can write the action of U_s and U_\omega in the space spanned by \ as: : U_s : a , \omega \rang + b , s \rang \mapsto \omega \rang \, , s \rang\begin -1 & -2/\sqrt \\ 0 & 1 \end\begina\\b\end. So in the basis \ (which is neither orthogonal nor a basis of the whole space) the action U_sU_\omega of applying U_\omega followed by U_s is given by the matrix : U_sU_\omega = \begin -1 & 0 \\ 2/\sqrt & 1 \end \begin -1 & -2/\sqrt \\ 0 & 1 \end = \begin 1 & 2/\sqrt \\ -2/\sqrt & 1-4/N \end. This matrix happens to have a very convenient Jordan form. If we define t = \arcsin(1/\sqrt), it is : U_sU_\omega = M \begin e^ & 0 \\ 0 & e^\end M^ where M = \begin-i & i \\ e^ & e^ \end. It follows that ''r''-th power of the matrix (corresponding to ''r'' iterations) is : (U_sU_\omega)^r = M \begin e^ & 0 \\ 0 & e^\end M^. Using this form, we can use trigonometric identities to compute the probability of observing ''ω'' after ''r'' iterations mentioned in the previous section, :\left, \begin\lang\omega, \omega\rang & \lang\omega, s\rang\end(U_sU_\omega)^r \begin0 \\ 1\end \^2 = \sin^2\left( (2r+1)t\right). Alternatively, one might reasonably imagine that a near-optimal time to distinguish would be when the angles 2''rt'' and −2''rt'' are as far apart as possible, which corresponds to 2rt \approx \pi/2, or r = \pi/4t = \pi/4\arcsin(1/\sqrt) \approx \pi\sqrt/4. Then the system is in state : \omega \rang \, , s \rang(U_sU_\omega)^r \begin0\\1\end \approx \omega \rang \, , s \rangM \begin i & 0 \\ 0 & -i\end M^ \begin0\\1\end = , \omega \rang \frac - , s \rang \frac. A short calculation now shows that the observation yields the correct answer ''ω'' with error O\left (\frac \right).


Extensions and variants


Multiple matching entries

If, instead of 1 matching entry, there are ''k'' matching entries, the same algorithm works, but the number of iterations must be \frac instead of \frac. There are several ways to handle the case if ''k'' is unknown. A simple solution performs optimally up to a constant factor: run Grover's algorithm repeatedly for increasingly small values of ''k'', e.g., taking ''k'' = ''N'', ''N''/2, ''N''/4, ..., and so on, taking k = N/2^t for iteration ''t'' until a matching entry is found. With sufficiently high probability, a marked entry will be found by iteration t = \log_2(N/k) + c for some constant ''c''. Thus, the total number of iterations taken is at most : \frac \Big(1 + \sqrt + \sqrt + \cdots + \sqrt\Big) = O\big(\sqrt\big). A version of this algorithm is used in order to solve the collision problem.


Quantum partial search

A modification of Grover's algorithm called quantum partial search was described by Grover and Radhakrishnan in 2004. In partial search, one is not interested in finding the exact address of the target item, only the first few digits of the address. Equivalently, we can think of "chunking" the search space into blocks, and then asking "in which block is the target item?". In many applications, such a search yields enough information if the target address contains the information wanted. For instance, to use the example given by L. K. Grover, if one has a list of students organized by class rank, we may only be interested in whether a student is in the lower 25%, 25–50%, 50–75% or 75–100% percentile. To describe partial search, we consider a database separated into K blocks, each of size b = N/K. The partial search problem is easier. Consider the approach we would take classically – we pick one block at random, and then perform a normal search through the rest of the blocks (in set theory language, the complement). If we don't find the target, then we know it's in the block we didn't search. The average number of iterations drops from N/2 to (N-b)/2. Grover's algorithm requires \frac\sqrt iterations. Partial search will be faster by a numerical factor that depends on the number of blocks K. Partial search uses n_1 global iterations and n_2 local iterations. The global Grover operator is designated G_1 and the local Grover operator is designated G_2. The global Grover operator acts on the blocks. Essentially, it is given as follows: #Perform j_1 standard Grover iterations on the entire database. #Perform j_2 local Grover iterations. A local Grover iteration is a direct sum of Grover iterations over each block. #Perform one standard Grover iteration. The optimal values of j_1 and j_2 are discussed in the paper by Grover and Radhakrishnan. One might also wonder what happens if one applies successive partial searches at different levels of "resolution". This idea was studied in detail by
Vladimir Korepin Vladimir E. Korepin (born 1951) is a professor at the C. N. Yang Institute of Theoretical Physics of the Stony Brook University. Korepin made research contributions in several areas of mathematics and physics. Educational background Korepin c ...
and Xu, who called it binary quantum search. They proved that it is not in fact any faster than performing a single partial search.


Optimality

Grover's algorithm is optimal up to sub-constant factors. That is, any algorithm that accesses the database only by using the operator ''Uω'' must apply ''Uω'' at least a 1-o(1) fraction as many times as Grover's algorithm. The extension of Grover's algorithm to ''k'' matching entries, (''N''/''k'')1/2/4, is also optimal. This result is important in understanding the limits of quantum computation. If the Grover's search problem was solvable with ''N'' applications of ''Uω'', that would imply that NP is contained in
BQP In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.Michael Nielsen and Isa ...
, by transforming problems in NP into Grover-type search problems. The optimality of Grover's algorithm suggests that quantum computers cannot solve
NP-Complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
problems in polynomial time, and thus NP is not contained in BQP. It has been shown that a class of non-local hidden variable quantum computers could implement a search of an N-item database in at most O(\sqrt steps. This is faster than the O(\sqrt) steps taken by Grover's algorithm.


See also

*
Amplitude amplification Amplitude amplification is a technique in quantum computing which generalizes the idea behind the Grover's search algorithm, and gives rise to a family of quantum algorithms. It was discovered by Gilles Brassard and Peter Høyer in 1997, and ind ...
*
Shor's algorithm Shor's algorithm is a quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. On a quantum computer, to factor an integer N , Shor's algorithm runs in polynomial ...
(for factorization) * Brassard–Høyer–Tapp algorithm (for solving the collision problem)


Notes


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 * 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. * Grover L.K.

''The Sciences'', July/August 1999, pp. 24–30. * Nielsen, M.A. and Chuang, I.L. ''Quantum computation and quantum information''. Cambridge University Press, 2000. Chapter 6.
What's a Quantum Phone Book?
Lov Grover, Lucent Technologies


External links

* * * * * * * {{DEFAULTSORT:Grover's Algorithm Quantum algorithms Search algorithms Post-quantum cryptography>\omega \rang \, , s \rang\begin -1 & 0 \\ 2/\sqrt & 1 \end\begina\\b\end. : U_\omega : a , \omega \rang + b , s \rang \mapsto \omega \rang \, , s \rang\begin -1 & -2/\sqrt \\ 0 & 1 \end\begina\\b\end. So in the basis \ (which is neither orthogonal nor a basis of the whole space) the action U_sU_\omega of applying U_\omega followed by U_s is given by the matrix : U_sU_\omega = \begin -1 & 0 \\ 2/\sqrt & 1 \end \begin -1 & -2/\sqrt \\ 0 & 1 \end = \begin 1 & 2/\sqrt \\ -2/\sqrt & 1-4/N \end. This matrix happens to have a very convenient Jordan form. If we define t = \arcsin(1/\sqrt), it is : U_sU_\omega = M \begin e^ & 0 \\ 0 & e^\end M^ where M = \begin-i & i \\ e^ & e^ \end. It follows that ''r''-th power of the matrix (corresponding to ''r'' iterations) is : (U_sU_\omega)^r = M \begin e^ & 0 \\ 0 & e^\end M^. Using this form, we can use trigonometric identities to compute the probability of observing ''ω'' after ''r'' iterations mentioned in the previous section, :\left, \begin\lang\omega, \omega\rang & \lang\omega, s\rang\end(U_sU_\omega)^r \begin0 \\ 1\end \^2 = \sin^2\left( (2r+1)t\right). Alternatively, one might reasonably imagine that a near-optimal time to distinguish would be when the angles 2''rt'' and −2''rt'' are as far apart as possible, which corresponds to 2rt \approx \pi/2, or r = \pi/4t = \pi/4\arcsin(1/\sqrt) \approx \pi\sqrt/4. Then the system is in state : \omega \rang \, , s \rang(U_sU_\omega)^r \begin0\\1\end \approx \omega \rang \, , s \rangM \begin i & 0 \\ 0 & -i\end M^ \begin0\\1\end = , \omega \rang \frac - , s \rang \frac. A short calculation now shows that the observation yields the correct answer ''ω'' with error O\left (\frac \right).


Extensions and variants


Multiple matching entries

If, instead of 1 matching entry, there are ''k'' matching entries, the same algorithm works, but the number of iterations must be \frac instead of \frac. There are several ways to handle the case if ''k'' is unknown. A simple solution performs optimally up to a constant factor: run Grover's algorithm repeatedly for increasingly small values of ''k'', e.g., taking ''k'' = ''N'', ''N''/2, ''N''/4, ..., and so on, taking k = N/2^t for iteration ''t'' until a matching entry is found. With sufficiently high probability, a marked entry will be found by iteration t = \log_2(N/k) + c for some constant ''c''. Thus, the total number of iterations taken is at most : \frac \Big(1 + \sqrt + \sqrt + \cdots + \sqrt\Big) = O\big(\sqrt\big). A version of this algorithm is used in order to solve the collision problem.


Quantum partial search

A modification of Grover's algorithm called quantum partial search was described by Grover and Radhakrishnan in 2004. In partial search, one is not interested in finding the exact address of the target item, only the first few digits of the address. Equivalently, we can think of "chunking" the search space into blocks, and then asking "in which block is the target item?". In many applications, such a search yields enough information if the target address contains the information wanted. For instance, to use the example given by L. K. Grover, if one has a list of students organized by class rank, we may only be interested in whether a student is in the lower 25%, 25–50%, 50–75% or 75–100% percentile. To describe partial search, we consider a database separated into K blocks, each of size b = N/K. The partial search problem is easier. Consider the approach we would take classically – we pick one block at random, and then perform a normal search through the rest of the blocks (in set theory language, the complement). If we don't find the target, then we know it's in the block we didn't search. The average number of iterations drops from N/2 to (N-b)/2. Grover's algorithm requires \frac\sqrt iterations. Partial search will be faster by a numerical factor that depends on the number of blocks K. Partial search uses n_1 global iterations and n_2 local iterations. The global Grover operator is designated G_1 and the local Grover operator is designated G_2. The global Grover operator acts on the blocks. Essentially, it is given as follows: #Perform j_1 standard Grover iterations on the entire database. #Perform j_2 local Grover iterations. A local Grover iteration is a direct sum of Grover iterations over each block. #Perform one standard Grover iteration. The optimal values of j_1 and j_2 are discussed in the paper by Grover and Radhakrishnan. One might also wonder what happens if one applies successive partial searches at different levels of "resolution". This idea was studied in detail by
Vladimir Korepin Vladimir E. Korepin (born 1951) is a professor at the C. N. Yang Institute of Theoretical Physics of the Stony Brook University. Korepin made research contributions in several areas of mathematics and physics. Educational background Korepin c ...
and Xu, who called it binary quantum search. They proved that it is not in fact any faster than performing a single partial search.


Optimality

Grover's algorithm is optimal up to sub-constant factors. That is, any algorithm that accesses the database only by using the operator ''Uω'' must apply ''Uω'' at least a 1-o(1) fraction as many times as Grover's algorithm. The extension of Grover's algorithm to ''k'' matching entries, (''N''/''k'')1/2/4, is also optimal. This result is important in understanding the limits of quantum computation. If the Grover's search problem was solvable with ''N'' applications of ''Uω'', that would imply that NP is contained in
BQP In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.Michael Nielsen and Isa ...
, by transforming problems in NP into Grover-type search problems. The optimality of Grover's algorithm suggests that quantum computers cannot solve
NP-Complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
problems in polynomial time, and thus NP is not contained in BQP. It has been shown that a class of non-local hidden variable quantum computers could implement a search of an N-item database in at most O(\sqrt steps. This is faster than the O(\sqrt) steps taken by Grover's algorithm.


See also

*
Amplitude amplification Amplitude amplification is a technique in quantum computing which generalizes the idea behind the Grover's search algorithm, and gives rise to a family of quantum algorithms. It was discovered by Gilles Brassard and Peter Høyer in 1997, and ind ...
*
Shor's algorithm Shor's algorithm is a quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. On a quantum computer, to factor an integer N , Shor's algorithm runs in polynomial ...
(for factorization) * Brassard–Høyer–Tapp algorithm (for solving the collision problem)


Notes


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 * 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. * Grover L.K.

''The Sciences'', July/August 1999, pp. 24–30. * Nielsen, M.A. and Chuang, I.L. ''Quantum computation and quantum information''. Cambridge University Press, 2000. Chapter 6.
What's a Quantum Phone Book?
Lov Grover, Lucent Technologies


External links

* * * * * * * {{DEFAULTSORT:Grover's Algorithm Quantum algorithms Search algorithms Post-quantum cryptography>\omega \rang \, , s \rang\begin -1 & -2/\sqrt \\ 0 & 1 \end\begina\\b\end. So in the basis \ (which is neither orthogonal nor a basis of the whole space) the action U_sU_\omega of applying U_\omega followed by U_s is given by the matrix : U_sU_\omega = \begin -1 & 0 \\ 2/\sqrt & 1 \end \begin -1 & -2/\sqrt \\ 0 & 1 \end = \begin 1 & 2/\sqrt \\ -2/\sqrt & 1-4/N \end. This matrix happens to have a very convenient Jordan form. If we define t = \arcsin(1/\sqrt), it is : U_sU_\omega = M \begin e^ & 0 \\ 0 & e^\end M^ where M = \begin-i & i \\ e^ & e^ \end. It follows that ''r''-th power of the matrix (corresponding to ''r'' iterations) is : (U_sU_\omega)^r = M \begin e^ & 0 \\ 0 & e^\end M^. Using this form, we can use trigonometric identities to compute the probability of observing ''ω'' after ''r'' iterations mentioned in the previous section, :\left, \begin\lang\omega, \omega\rang & \lang\omega, s\rang\end(U_sU_\omega)^r \begin0 \\ 1\end \^2 = \sin^2\left( (2r+1)t\right). Alternatively, one might reasonably imagine that a near-optimal time to distinguish would be when the angles 2''rt'' and −2''rt'' are as far apart as possible, which corresponds to 2rt \approx \pi/2, or r = \pi/4t = \pi/4\arcsin(1/\sqrt) \approx \pi\sqrt/4. Then the system is in state : \omega \rang \, , s \rang\begin -1 & -2/\sqrt \\ 0 & 1 \end\begina\\b\end. So in the basis \ (which is neither orthogonal nor a basis of the whole space) the action U_sU_\omega of applying U_\omega followed by U_s is given by the matrix : U_sU_\omega = \begin -1 & 0 \\ 2/\sqrt & 1 \end \begin -1 & -2/\sqrt \\ 0 & 1 \end = \begin 1 & 2/\sqrt \\ -2/\sqrt & 1-4/N \end. This matrix happens to have a very convenient Jordan form. If we define t = \arcsin(1/\sqrt), it is : U_sU_\omega = M \begin e^ & 0 \\ 0 & e^\end M^ where M = \begin-i & i \\ e^ & e^ \end. It follows that ''r''-th power of the matrix (corresponding to ''r'' iterations) is : (U_sU_\omega)^r = M \begin e^ & 0 \\ 0 & e^\end M^. Using this form, we can use trigonometric identities to compute the probability of observing ''ω'' after ''r'' iterations mentioned in the previous section, :\left, \begin\lang\omega, \omega\rang & \lang\omega, s\rang\end(U_sU_\omega)^r \begin0 \\ 1\end \^2 = \sin^2\left( (2r+1)t\right). Alternatively, one might reasonably imagine that a near-optimal time to distinguish would be when the angles 2''rt'' and −2''rt'' are as far apart as possible, which corresponds to 2rt \approx \pi/2, or r = \pi/4t = \pi/4\arcsin(1/\sqrt) \approx \pi\sqrt/4. Then the system is in state : \omega \rang \, , s \rang(U_sU_\omega)^r \begin0\\1\end \approx \omega \rang \, , s \rangM \begin i & 0 \\ 0 & -i\end M^ \begin0\\1\end = , \omega \rang \frac - , s \rang \frac. A short calculation now shows that the observation yields the correct answer ''ω'' with error O\left (\frac \right).


Extensions and variants


Multiple matching entries

If, instead of 1 matching entry, there are ''k'' matching entries, the same algorithm works, but the number of iterations must be \frac instead of \frac. There are several ways to handle the case if ''k'' is unknown. A simple solution performs optimally up to a constant factor: run Grover's algorithm repeatedly for increasingly small values of ''k'', e.g., taking ''k'' = ''N'', ''N''/2, ''N''/4, ..., and so on, taking k = N/2^t for iteration ''t'' until a matching entry is found. With sufficiently high probability, a marked entry will be found by iteration t = \log_2(N/k) + c for some constant ''c''. Thus, the total number of iterations taken is at most : \frac \Big(1 + \sqrt + \sqrt + \cdots + \sqrt\Big) = O\big(\sqrt\big). A version of this algorithm is used in order to solve the collision problem.


Quantum partial search

A modification of Grover's algorithm called quantum partial search was described by Grover and Radhakrishnan in 2004. In partial search, one is not interested in finding the exact address of the target item, only the first few digits of the address. Equivalently, we can think of "chunking" the search space into blocks, and then asking "in which block is the target item?". In many applications, such a search yields enough information if the target address contains the information wanted. For instance, to use the example given by L. K. Grover, if one has a list of students organized by class rank, we may only be interested in whether a student is in the lower 25%, 25–50%, 50–75% or 75–100% percentile. To describe partial search, we consider a database separated into K blocks, each of size b = N/K. The partial search problem is easier. Consider the approach we would take classically – we pick one block at random, and then perform a normal search through the rest of the blocks (in set theory language, the complement). If we don't find the target, then we know it's in the block we didn't search. The average number of iterations drops from N/2 to (N-b)/2. Grover's algorithm requires \frac\sqrt iterations. Partial search will be faster by a numerical factor that depends on the number of blocks K. Partial search uses n_1 global iterations and n_2 local iterations. The global Grover operator is designated G_1 and the local Grover operator is designated G_2. The global Grover operator acts on the blocks. Essentially, it is given as follows: #Perform j_1 standard Grover iterations on the entire database. #Perform j_2 local Grover iterations. A local Grover iteration is a direct sum of Grover iterations over each block. #Perform one standard Grover iteration. The optimal values of j_1 and j_2 are discussed in the paper by Grover and Radhakrishnan. One might also wonder what happens if one applies successive partial searches at different levels of "resolution". This idea was studied in detail by
Vladimir Korepin Vladimir E. Korepin (born 1951) is a professor at the C. N. Yang Institute of Theoretical Physics of the Stony Brook University. Korepin made research contributions in several areas of mathematics and physics. Educational background Korepin c ...
and Xu, who called it binary quantum search. They proved that it is not in fact any faster than performing a single partial search.


Optimality

Grover's algorithm is optimal up to sub-constant factors. That is, any algorithm that accesses the database only by using the operator ''Uω'' must apply ''Uω'' at least a 1-o(1) fraction as many times as Grover's algorithm. The extension of Grover's algorithm to ''k'' matching entries, (''N''/''k'')1/2/4, is also optimal. This result is important in understanding the limits of quantum computation. If the Grover's search problem was solvable with ''N'' applications of ''Uω'', that would imply that NP is contained in
BQP In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.Michael Nielsen and Isa ...
, by transforming problems in NP into Grover-type search problems. The optimality of Grover's algorithm suggests that quantum computers cannot solve
NP-Complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
problems in polynomial time, and thus NP is not contained in BQP. It has been shown that a class of non-local hidden variable quantum computers could implement a search of an N-item database in at most O(\sqrt steps. This is faster than the O(\sqrt) steps taken by Grover's algorithm.


See also

*
Amplitude amplification Amplitude amplification is a technique in quantum computing which generalizes the idea behind the Grover's search algorithm, and gives rise to a family of quantum algorithms. It was discovered by Gilles Brassard and Peter Høyer in 1997, and ind ...
*
Shor's algorithm Shor's algorithm is a quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. On a quantum computer, to factor an integer N , Shor's algorithm runs in polynomial ...
(for factorization) * Brassard–Høyer–Tapp algorithm (for solving the collision problem)


Notes


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 * 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. * Grover L.K.

''The Sciences'', July/August 1999, pp. 24–30. * Nielsen, M.A. and Chuang, I.L. ''Quantum computation and quantum information''. Cambridge University Press, 2000. Chapter 6.
What's a Quantum Phone Book?
Lov Grover, Lucent Technologies


External links

* * * * * * * {{DEFAULTSORT:Grover's Algorithm Quantum algorithms Search algorithms Post-quantum cryptography>\omega \rang \, , s \rang(U_sU_\omega)^r \begin0\\1\end \approx \omega \rang \, , s \rang\begin -1 & -2/\sqrt \\ 0 & 1 \end\begina\\b\end. So in the basis \ (which is neither orthogonal nor a basis of the whole space) the action U_sU_\omega of applying U_\omega followed by U_s is given by the matrix : U_sU_\omega = \begin -1 & 0 \\ 2/\sqrt & 1 \end \begin -1 & -2/\sqrt \\ 0 & 1 \end = \begin 1 & 2/\sqrt \\ -2/\sqrt & 1-4/N \end. This matrix happens to have a very convenient Jordan form. If we define t = \arcsin(1/\sqrt), it is : U_sU_\omega = M \begin e^ & 0 \\ 0 & e^\end M^ where M = \begin-i & i \\ e^ & e^ \end. It follows that ''r''-th power of the matrix (corresponding to ''r'' iterations) is : (U_sU_\omega)^r = M \begin e^ & 0 \\ 0 & e^\end M^. Using this form, we can use trigonometric identities to compute the probability of observing ''ω'' after ''r'' iterations mentioned in the previous section, :\left, \begin\lang\omega, \omega\rang & \lang\omega, s\rang\end(U_sU_\omega)^r \begin0 \\ 1\end \^2 = \sin^2\left( (2r+1)t\right). Alternatively, one might reasonably imagine that a near-optimal time to distinguish would be when the angles 2''rt'' and −2''rt'' are as far apart as possible, which corresponds to 2rt \approx \pi/2, or r = \pi/4t = \pi/4\arcsin(1/\sqrt) \approx \pi\sqrt/4. Then the system is in state : \omega \rang \, , s \rang(U_sU_\omega)^r \begin0\\1\end \approx \omega \rang \, , s \rangM \begin i & 0 \\ 0 & -i\end M^ \begin0\\1\end = , \omega \rang \frac - , s \rang \frac. A short calculation now shows that the observation yields the correct answer ''ω'' with error O\left (\frac \right).


Extensions and variants


Multiple matching entries

If, instead of 1 matching entry, there are ''k'' matching entries, the same algorithm works, but the number of iterations must be \frac instead of \frac. There are several ways to handle the case if ''k'' is unknown. A simple solution performs optimally up to a constant factor: run Grover's algorithm repeatedly for increasingly small values of ''k'', e.g., taking ''k'' = ''N'', ''N''/2, ''N''/4, ..., and so on, taking k = N/2^t for iteration ''t'' until a matching entry is found. With sufficiently high probability, a marked entry will be found by iteration t = \log_2(N/k) + c for some constant ''c''. Thus, the total number of iterations taken is at most : \frac \Big(1 + \sqrt + \sqrt + \cdots + \sqrt\Big) = O\big(\sqrt\big). A version of this algorithm is used in order to solve the collision problem.


Quantum partial search

A modification of Grover's algorithm called quantum partial search was described by Grover and Radhakrishnan in 2004. In partial search, one is not interested in finding the exact address of the target item, only the first few digits of the address. Equivalently, we can think of "chunking" the search space into blocks, and then asking "in which block is the target item?". In many applications, such a search yields enough information if the target address contains the information wanted. For instance, to use the example given by L. K. Grover, if one has a list of students organized by class rank, we may only be interested in whether a student is in the lower 25%, 25–50%, 50–75% or 75–100% percentile. To describe partial search, we consider a database separated into K blocks, each of size b = N/K. The partial search problem is easier. Consider the approach we would take classically – we pick one block at random, and then perform a normal search through the rest of the blocks (in set theory language, the complement). If we don't find the target, then we know it's in the block we didn't search. The average number of iterations drops from N/2 to (N-b)/2. Grover's algorithm requires \frac\sqrt iterations. Partial search will be faster by a numerical factor that depends on the number of blocks K. Partial search uses n_1 global iterations and n_2 local iterations. The global Grover operator is designated G_1 and the local Grover operator is designated G_2. The global Grover operator acts on the blocks. Essentially, it is given as follows: #Perform j_1 standard Grover iterations on the entire database. #Perform j_2 local Grover iterations. A local Grover iteration is a direct sum of Grover iterations over each block. #Perform one standard Grover iteration. The optimal values of j_1 and j_2 are discussed in the paper by Grover and Radhakrishnan. One might also wonder what happens if one applies successive partial searches at different levels of "resolution". This idea was studied in detail by
Vladimir Korepin Vladimir E. Korepin (born 1951) is a professor at the C. N. Yang Institute of Theoretical Physics of the Stony Brook University. Korepin made research contributions in several areas of mathematics and physics. Educational background Korepin c ...
and Xu, who called it binary quantum search. They proved that it is not in fact any faster than performing a single partial search.


Optimality

Grover's algorithm is optimal up to sub-constant factors. That is, any algorithm that accesses the database only by using the operator ''Uω'' must apply ''Uω'' at least a 1-o(1) fraction as many times as Grover's algorithm. The extension of Grover's algorithm to ''k'' matching entries, (''N''/''k'')1/2/4, is also optimal. This result is important in understanding the limits of quantum computation. If the Grover's search problem was solvable with ''N'' applications of ''Uω'', that would imply that NP is contained in
BQP In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.Michael Nielsen and Isa ...
, by transforming problems in NP into Grover-type search problems. The optimality of Grover's algorithm suggests that quantum computers cannot solve
NP-Complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
problems in polynomial time, and thus NP is not contained in BQP. It has been shown that a class of non-local hidden variable quantum computers could implement a search of an N-item database in at most O(\sqrt steps. This is faster than the O(\sqrt) steps taken by Grover's algorithm.


See also

*
Amplitude amplification Amplitude amplification is a technique in quantum computing which generalizes the idea behind the Grover's search algorithm, and gives rise to a family of quantum algorithms. It was discovered by Gilles Brassard and Peter Høyer in 1997, and ind ...
*
Shor's algorithm Shor's algorithm is a quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. On a quantum computer, to factor an integer N , Shor's algorithm runs in polynomial ...
(for factorization) * Brassard–Høyer–Tapp algorithm (for solving the collision problem)


Notes


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 * 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. * Grover L.K.

''The Sciences'', July/August 1999, pp. 24–30. * Nielsen, M.A. and Chuang, I.L. ''Quantum computation and quantum information''. Cambridge University Press, 2000. Chapter 6.
What's a Quantum Phone Book?
Lov Grover, Lucent Technologies


External links

* * * * * * * {{DEFAULTSORT:Grover's Algorithm Quantum algorithms Search algorithms Post-quantum cryptography>\omega \rang \, , s \rangM \begin i & 0 \\ 0 & -i\end M^ \begin0\\1\end = , \omega \rang \frac - , s \rang \frac. A short calculation now shows that the observation yields the correct answer ''ω'' with error O\left (\frac \right).


Extensions and variants


Multiple matching entries

If, instead of 1 matching entry, there are ''k'' matching entries, the same algorithm works, but the number of iterations must be \frac instead of \frac. There are several ways to handle the case if ''k'' is unknown. A simple solution performs optimally up to a constant factor: run Grover's algorithm repeatedly for increasingly small values of ''k'', e.g., taking ''k'' = ''N'', ''N''/2, ''N''/4, ..., and so on, taking k = N/2^t for iteration ''t'' until a matching entry is found. With sufficiently high probability, a marked entry will be found by iteration t = \log_2(N/k) + c for some constant ''c''. Thus, the total number of iterations taken is at most : \frac \Big(1 + \sqrt + \sqrt + \cdots + \sqrt\Big) = O\big(\sqrt\big). A version of this algorithm is used in order to solve the collision problem.


Quantum partial search

A modification of Grover's algorithm called quantum partial search was described by Grover and Radhakrishnan in 2004. In partial search, one is not interested in finding the exact address of the target item, only the first few digits of the address. Equivalently, we can think of "chunking" the search space into blocks, and then asking "in which block is the target item?". In many applications, such a search yields enough information if the target address contains the information wanted. For instance, to use the example given by L. K. Grover, if one has a list of students organized by class rank, we may only be interested in whether a student is in the lower 25%, 25–50%, 50–75% or 75–100% percentile. To describe partial search, we consider a database separated into K blocks, each of size b = N/K. The partial search problem is easier. Consider the approach we would take classically – we pick one block at random, and then perform a normal search through the rest of the blocks (in set theory language, the complement). If we don't find the target, then we know it's in the block we didn't search. The average number of iterations drops from N/2 to (N-b)/2. Grover's algorithm requires \frac\sqrt iterations. Partial search will be faster by a numerical factor that depends on the number of blocks K. Partial search uses n_1 global iterations and n_2 local iterations. The global Grover operator is designated G_1 and the local Grover operator is designated G_2. The global Grover operator acts on the blocks. Essentially, it is given as follows: #Perform j_1 standard Grover iterations on the entire database. #Perform j_2 local Grover iterations. A local Grover iteration is a direct sum of Grover iterations over each block. #Perform one standard Grover iteration. The optimal values of j_1 and j_2 are discussed in the paper by Grover and Radhakrishnan. One might also wonder what happens if one applies successive partial searches at different levels of "resolution". This idea was studied in detail by
Vladimir Korepin Vladimir E. Korepin (born 1951) is a professor at the C. N. Yang Institute of Theoretical Physics of the Stony Brook University. Korepin made research contributions in several areas of mathematics and physics. Educational background Korepin c ...
and Xu, who called it binary quantum search. They proved that it is not in fact any faster than performing a single partial search.


Optimality

Grover's algorithm is optimal up to sub-constant factors. That is, any algorithm that accesses the database only by using the operator ''Uω'' must apply ''Uω'' at least a 1-o(1) fraction as many times as Grover's algorithm. The extension of Grover's algorithm to ''k'' matching entries, (''N''/''k'')1/2/4, is also optimal. This result is important in understanding the limits of quantum computation. If the Grover's search problem was solvable with ''N'' applications of ''Uω'', that would imply that NP is contained in
BQP In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.Michael Nielsen and Isa ...
, by transforming problems in NP into Grover-type search problems. The optimality of Grover's algorithm suggests that quantum computers cannot solve
NP-Complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
problems in polynomial time, and thus NP is not contained in BQP. It has been shown that a class of non-local hidden variable quantum computers could implement a search of an N-item database in at most O(\sqrt steps. This is faster than the O(\sqrt) steps taken by Grover's algorithm.


See also

*
Amplitude amplification Amplitude amplification is a technique in quantum computing which generalizes the idea behind the Grover's search algorithm, and gives rise to a family of quantum algorithms. It was discovered by Gilles Brassard and Peter Høyer in 1997, and ind ...
*
Shor's algorithm Shor's algorithm is a quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. On a quantum computer, to factor an integer N , Shor's algorithm runs in polynomial ...
(for factorization) * Brassard–Høyer–Tapp algorithm (for solving the collision problem)


Notes


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 * 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. * Grover L.K.

''The Sciences'', July/August 1999, pp. 24–30. * Nielsen, M.A. and Chuang, I.L. ''Quantum computation and quantum information''. Cambridge University Press, 2000. Chapter 6.
What's a Quantum Phone Book?
Lov Grover, Lucent Technologies


External links

* * * * * * * {{DEFAULTSORT:Grover's Algorithm Quantum algorithms Search algorithms Post-quantum cryptography