betaFeedback

WorksPhysics and Astronomy

Quantum Amplitude Amplification and Estimation

Abstract

Consider a Boolean function χ:X→{0,1}χ: X \to \{0,1\} that partitions set XX between its good and bad elements, where xx is good if χ(x)=1χ(x)=1 and bad otherwise. Consider also a quantum algorithm A\mathcal A such that A∣0⟩=∑x∈Xαx∣x⟩A |0\rangle= \sum_{x\in X} α_x |x\rangle is a quantum superposition of the elements of XX, and let aa denote the probability that a good element is produced if A∣0⟩A |0\rangle is measured. If we repeat the process of running AA, measuring the output, and using χχ to check the validity of the result, we shall expect to repeat 1/a1/a times on the average before a solution is found. Amplitude amplification is a process that allows to find a good xx after an expected number of applications of AA and its inverse which is proportional to 1/a1/\sqrt{a}, assuming algorithm AA makes no measurements. This is a generalization of Grover's searching algorithm in which AA was restricted to producing an equal superposition of all members of XX and we had a promise that a single xx existed such that χ(x)=1χ(x)=1. Our algorithm works whether or not the value of aa is known ahead of time. In case the value of aa is known, we can find a good xx after a number of applications of AA and its inverse which is proportional to 1/a1/\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 aa. We apply amplitude estimation to the problem of approximate counting, in which we wish to estimate the number of x∈Xx\in X such that χ(x)=1χ(x)=1. We obtain optimal quantum algorithms in a variety of settings.

Paper details

vlnc:W_nwngvjr2
Version
v1 · latest
Published
Added
License
LicenseRef-arXiv-undeclared
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…