Grover's algorithm
In quantum computing, Grover's algorithm, also known as the quantum search algorithm, refers to a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just formula_1 evaluations of the function, where formula_2 is the size of the function's domain. It was devised by Lov Grover in 1996. The analogous problem in classical computation cannot be solved in fewer than formula_3 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, and Umesh Vazirani proved that any quantum solution to the problem needs to evaluate the function formula_1 times, so Grover's algorithm is asymptotically optimal. Since researchers generally believe that NP-complete problems are difficult because their search spaces have essentially no structure, the optimality of Grover's algorithm for unstructured search suggests (but does not prove) that quantum computers cannot solve NP-complete problems in polynomial time. 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 formula_2 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 2 iterations, or a 256-bit key in roughly 2 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, 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 is one such example. Generic constraint satisfaction problems 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, 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 formula_6 that can be evaluated on a quantum computer, Grover's algorithm allows us to calculate formula_7 when given formula_8. Consequently, Grover's algorithm gives broad asymptotic speed-ups to many kinds of brute-force attacks on symmetric-key cryptography, including collision attacks and pre-image  attacks. 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 data-base 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 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 formula_9. 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 (sometimes called an oracle) in the  form of a unitary operator "U" that acts as follows: This uses the formula_2-dimensional state space formula_12, which is supplied by a register with formula_13 qubits. This is often written as Grover's algorithm outputs "ω" with probability at least "1/2" using formula_1 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 formula_1, since it will only be run twice on average. Alternative oracle definition. This section compares the above oracle formula_17 with an  oracle formula_18. "U" is different from the standard quantum oracle for a function "f". This standard oracle, denoted here as "U", uses an ancillary qubit system. The operation then represents an inversion (NOT gate) conditioned by the value of "f"("x") on the main system: or briefly, These oracles are typically realized using uncomputation. If we are given "U" as our oracle, then we can also implement "U", since "U" is "U" when the ancillary qubit is in the state formula_21: So, Grover's algorithm can be run regardless of which oracle is given. If "U" is given, then we must  maintain an additional qubit in the state formula_23 and apply "U" in place of "U". Algorithm. The steps of Grover's algorithm are given as follows: For the correctly chosen value of formula_28, the output will be formula_29 with probability approaching 1 for "N" ≫ 1. Analysis shows that this eventual value for formula_25 satisfies formula_31. 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 formula_32, or formula_33 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 formula_34 and formula_29; equivalently, the plane spanned by formula_29 and the perpendicular ket formula_37. Grover's algorithm begins with the initial ket formula_34, which lies in the subspace. The operator formula_39 is a reflection at the hyperplane orthogonal to formula_29 for vectors in the plane spanned by formula_41 and formula_29, i.e. it acts as a reflection across formula_41. This can be seen by writing formula_17 in the form of a Householder reflection : The operator formula_46 is a reflection through formula_34. Both operators formula_48 and formula_39 take states in the plane spanned by formula_41 and formula_29 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 formula_52 of each Grover iteration step rotates the state vector by an angle of formula_53. So, with enough iterations, one can rotate from the initial state formula_34 to the desired output state formula_29. The initial ket is close to the state orthogonal to formula_29: In geometric terms, the angle formula_58 between formula_34  and formula_41 is given by We need to stop when the state vector passes close to formula_29; after this, subsequent iterations rotate the state vector "away" from formula_29, reducing the probability of obtaining the correct answer. The exact probability of measuring the correct answer is where "r" is the (integer) number of Grover iterations. The earliest time that we get a near-optimal measurement is therefore formula_65. Algebraic proof of correctness. To complete the algebraic analysis, we need to find out what happens when we repeatedly apply formula_66. 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 formula_67 and formula_68. We can write the action of formula_48 and formula_17 in the space spanned by formula_71 as: So in the basis formula_74 (which is neither orthogonal nor a basis of the whole space) the action formula_75 of applying formula_17 followed by formula_48 is given by the matrix This matrix happens to have a very convenient Jordan form. If we define formula_79, it is It follows that "r"-th power of the matrix (corresponding to "r" iterations) is Using this form, we can  use trigonometric identities to compute the probability of observing "ω" after "r" iterations mentioned in the previous section, 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 formula_84, or formula_85. Then the system is in state A short calculation now shows that the observation yields the correct answer "ω" with error formula_87. 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  formula_88instead of formula_89. 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 formula_90 for iteration "t" until a matching entry is found. With sufficiently high probability, a marked entry will be found by iteration formula_91 for some constant "c". Thus, the total number of iterations taken is at most 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 formula_93 blocks, each of size formula_94. 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 formula_95 to formula_96. Grover's algorithm requires formula_97 iterations. Partial search will be faster by a numerical factor that depends on the number of blocks formula_93. Partial search uses formula_99 global iterations and formula_100 local iterations. The global Grover operator is designated formula_101 and the local Grover operator is designated formula_102. The global Grover operator acts on the blocks. Essentially, it is given as follows: The optimal values of formula_103 and formula_104 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 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 formula_107 fraction as many times as Grover's algorithm. The extension of Grover's algorithm to "k" matching entries, ("N"/"k")/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, by transforming problems in NP into Grover-type search problems. The optimality of Grover's algorithm suggests that quantum computers cannot solve NP-Complete 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 formula_2-item database in at most formula_109 steps. This is faster than the formula_1 steps taken by Grover's algorithm. Grover's algorithm In