Key points are not available for this paper at this time.
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 A such that A |0= ₗ ₗ αₓ |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.
Brassard et al. (Mon,) studied this question.