Quantum Amplitude Amplification and Estimation

By Gilles Brassard, Peter Høyer, Michele Mosca, A. Montreal, B. U. O. Aarhus, Cacr University of Waterloo. 2000

2,053 citations recorded by the source corpus.

Consider a Boolean function $\chi: X \to \{0,1\}$ that partitions set $X$ between its good and bad elements, where $x$ is good if $\chi(x)=1$ and bad otherwise. Consider also a quantum algorithm $\mathcal A$ such that $A |0\rangle= \sum_{x\in X} \alpha_x |x\rangle$ is a quantum superposition of the elements of $X$, and let $a$ denote the probability that a good element is produced if $A |0\rangle$ is measured. If we repeat the process of running $A$, measuring the output, and using $\chi$ to check the validity of the result, we shall expect to repeat $1/a$ times on the average before a solution is found. *Amplitude amplification* is a process that allows to find a good $x$ after an expected number of applications of $A$ and its inverse which is proportional to $1/\sqrt{a}$, assuming algorithm $A$ makes no measurements. This is a generalization of Grover's searching algorithm in which $A$ was restricted to producing an equal superposition of all members of $X$ and we had a promise that a single $x$ existed such that $\chi(x)=1$. Our algorithm works whether or not the value of $a$ is known ahead of time. In case the value of $a$ is known, we can find a good $x$ after a number of applications of $A$ and its inverse which is proportional to $1/\sqrt{a}$ even in the worst case. We show that this quadratic speedup can also be obtained for a large family of search problems for which good classical heuristics exist. Finally, as our main result, we combine ideas from Grover's and Shor's quantum algorithms to perform amplitude estimation, a process that allows to estimate the value of $a$. We apply amplitude estimation to the problem of *approximate counting*, in which we wish to estimate the number of $x\in X$ such that $\chi(x)=1$. We obtain optimal quantum algorithms in a variety of settings.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/1184bdeb5ee727f9ba3aa70b1ffd5c225e521760

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Quantum machine learning: a classical perspective (2017, methodology): “[133] developed two algorithms to efficiently train an RBM based on amplitude amplification [134] and quantum Gibbs sampling.”
Quantum computing for finance: Overview and prospects (2018, methodology): “This algorithm can be adapted to solve optimization problems, such as finding a Minimum Spanning Tree [19], maximizing flow-like variables [20], and implementing Monte Carlo methods [9].”
Quantum walk algorithm for element distinctness (2003, methodology): “The naive way to find a marked vertex would be to use Grover’s qu antum search algorithm [26, 16 ].”
Quantum-enhanced machine learning (2016, methodology): “In both cases, we can thus use phase-kick back to amplitude-amplify [30] sequences of actions satisfying a desired criterion, and note that relative to most figures of merit, the expected reward of a sequence in the stochastic environment has the same operational meaning as the total reward in the m”
Quantum risk analysis (2018, methodology): “Amplitude estimation (AE) is a quantum algorithm used to estimate an unknown parameter and converges as O(M), which is a quadratic speed-up over classical algorithms like Monte Carlo.(12) It has already been shown how AE can be used to price financial derivatives with the Black–Scholes model.”
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2018, background): “Quadratic Singular value = square root of probability Grover search [27] Distinguishability of singular values Amplitude estimation [15] Singular values close to 1 are more useful Quantum walks [53]”
Search via quantum walk (2006, methodology): “This operator may then be used within amplitude amplification algorithms [16, 10, 17] for search.”
Tractability of Multivariate Problems (2008, background): “see Brassard, Høyer, Mosca and Tapp [18] and [113, 164].”
An introduction to quantum machine learning (2014, methodology): “In the same contribution, Wiebe, Kapoor and Svore also give a scheme for a (weighted) nearest-centroid algorithm based on the Euclidian distance evaluated by well-known algorithms from the toolbox of quantum information, the amplitude estimation algorithm [40] and Dürr and Høyer’s find minimum subro”
Quantum Walk Based Search Algorithms (2008, background): “Grover search [16], and in general amplitude amplification [ 11 ] are well known quantum procedures which are provably faster than their classical counterpart.”
Coins make quantum walks faster (2004, methodology): “Finally, to amplify the success probability we will use amplitude amplification [ BHMT02 ], which is a succession of steps consisting of reflection around the mean |�0i and a run of the algorithm.”
Quantum speedup of Monte Carlo methods (2015, background): “As is common in works based on quantum amplitude amplification and estimation [19], we also assume that we have the ability to execute the algorithm A−1, which is the inverse of the unitary part of A.”
Option Pricing using Quantum Computers (2019, background): “Several of these applications are based on the Amplitude Estimation algorithm [21] which can estimate a parameter with a convergence rate of 1/M , where M is the number of quantum samples used.”
Quantum Algorithm for Linear Differential Equations with Exponentially Improved Dependence on Precision (2017, methodology): “Using amplitude amplification [9], we can raise this probability to (1) with O(g) repetitions of the above procedure.”
Quantum algorithms: an overview (2015, neutral): “[20] can find w such that f(w) = 1 with only O(1/ √ ) uses of f , and failure probability arbitrarily close to 0, thus achieving a quadratic speedup.”