Physics – Quantum Physics
Scientific paper
2000-05-15
Physics
Quantum Physics
32 pages, no figures
Scientific paper
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 \ket{0} = \sum_{x\in X} \alpha_x \ket{x}$ is a quantum superposition of the elements of $X$, and let $a$ denote the probability that a good element is produced if $A \ket{0}$ 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.
Brassard Gilles
Hoyer Peter
Mosca Michele
Tapp Alain
No associations
LandOfFree
Quantum Amplitude Amplification and Estimation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum Amplitude Amplification and Estimation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Amplitude Amplification and Estimation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-103491