The derivation presented here roughly follows the one given in. Assume we have an N-dimensional Hilbert space representing the state space of our quantum system, spanned by the orthonormal computational basis states. Furthermore assume we have a Hermitianprojection operator. Alternatively, may be given in terms of a Boolean oracle function and an orthonormal operational basis in which case can be used to partition into a direct sum of two mutually orthogonal subspaces, the good subspace and the bad subspace : In other words, we are defining a "good subspace" via the projector. The goal of the algorithm is then to evolve some initial state into a state belonging to. Given a normalized state vector with nonzero overlap with both subspaces, we can uniquely decompose it as where, and and are the normalized projections of into the subspaces and, respectively. This decomposition defines a two-dimensional subspace , spanned by the vectors and. The probability of finding the system in a good state when measured is. Define a unitary operator where flips the phase of the states in the good subspace, whereas flips the phase of the initial state. The action of this operator on is given by Thus in the subspace corresponds to a rotation by the angle : Applying times on the state gives rotating the state between the good and bad subspaces. After iterations the probability of finding the system in a good state is.
The probability is maximized if we choose Up until this point each iteration increases the amplitude of the good states, hence the name of the technique.
Applications
Assume we have an unsorted database with N elements, and an oracle function which can recognize the good entries we are searching for, and for simplicity. If there are good entries in the database in total, then we can find them by initializing a quantum register with qubits where into a uniform superposition of all the database elements such that and running the above algorithm. In this case the overlap of the initial state with the good subspace is equal to the square root of the frequency of the good entries in the database,. If, we can approximate the number of required iterations as Measuring the state will now give one of the good entries with high probability. Since each application of requires a single oracle query, we can find a good entry with just oracle queries, thus obtaining a quadratic speedup over the best possible classical algorithm. If we set the size of the set to one, the above scenario essentially reduces to the original Grover search.
