2000/05/15 by Gilles Brassard, Peter Hoyer, Michele Mosca +1 · 4 citations
Physics and Astronomy · #quant-ph
paper · pdf · doi:10.1090/conm/305/05215
published as Quantum Computation and Quantum Information, Samuel J. Lomonaco, Jr. (editor), AMS Contemporary Mathematics, 305:53-74, 2002 · 32 pages, no figures
arxiv created 2000/05/15 · arxiv updated 2021/03/23
Consider a Boolean function χ: X → \0,1\ that partitions set X between its good and bad elements, where x is good if χ(x)=1 and bad otherwise. Consider also a quantum algorithm \mathcal A such that A |0⟩= ∑x∈ X αx |x⟩ is a quantum superposition of the elements of X, and let a denote the probability that a good element is produced if A |0⟩ is measured. If we repeat the process of running A, measuring the output, and using χ 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/√(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 χ(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/√(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∈ X such that χ(x)=1. We obtain optimal quantum algorithms in a variety of settings.