Amplitude amplification

Amplitude amplification is a technique in quantum computing which generalizes the idea behind 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 independently rediscovered by Lov Grover in 1998. In a quantum computer, amplitude amplification can be used to obtain a quadratic speedup over several classical algorithms. The derivation presented here roughly follows the one given by Brassard et al. in 2000. Assume we have an -dimensional Hilbert space representing the state space of a quantum system, spanned by the orthonormal computational basis states . Furthermore assume we have a Hermitian projection 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 and 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.