Amplitude amplification is a technique 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. Though ...
which generalizes the idea behind
the
Grover's search algorithm, and gives rise to a family of
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 sequ ...
s.
It was discovered by
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 Unive ...
and
Peter Høyer in 1997,
[
]
and independently rediscovered by
Lov Grover
Lov Kumar Grover (born 1961) is an Indian- American computer scientist. He is the originator of the Grover database search algorithm used in quantum computing. Grover's 1996 algorithm won renown as the second major algorithm proposed for qu ...
in 1998.
[
]
In a quantum computer, amplitude amplification can be used to obtain a
quadratic speedup over several classical algorithms.
Algorithm
The derivation presented here roughly follows the one given in.
[
]
Assume we have an N-dimensional
Hilbert space
In mathematics, Hilbert spaces (named after David Hilbert) allow generalizing the methods of linear algebra and calculus from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise natural ...
representing the
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 toy ...
of our quantum system, spanned by the
orthonormal computational basis states
.
Furthermore assume we have a
Hermitian {{Short description, none
Numerous things are named after the French mathematician Charles Hermite (1822–1901):
Hermite
* Cubic Hermite spline, a type of third-degree spline
* Gauss–Hermite quadrature, an extension of Gaussian quadrature m ...
projection operator
In linear algebra and functional analysis, a projection is a linear transformation P from a vector space to itself (an endomorphism) such that P\circ P=P. That is, whenever P is applied twice to any vector, it gives the same result as if it wer ...
.
Alternatively,
may be given in terms of a
Boolean
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 word '' ...
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