Quantum Amplitude Amplification and Estimation TeX

@misc{citeulike:759408, abstract = {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.}, archivePrefix = {arXiv}, author = {Brassard, Gilles and Hoyer, Peter and Mosca, Michele and Tapp, Alain}, citeulike-article-id = {759408}, comment = {provides a generalization of grover's agrorithm!!!}, eprint = {quant-ph/0005055}, keywords = {algorithms, amplification, amplitude, quantum}, month = {May}, posted-at = {2006-07-14 19:22:27}, priority = {5}, title = {Quantum Amplitude Amplification and Estimation}, url = {http://arxiv.org/abs/quant-ph/0005055}, year = {2000} }

TY - ELEC ID - citeulike:759408 L3 - citeulike-article-id:759408 N2 - 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. TI - Quantum Amplitude Amplification and Estimation KW - algorithms KW - amplification KW - amplitude KW - quantum N1 - provides a generalization of grover's agrorithm!!! AU - Brassard, Gilles AU - Hoyer, Peter AU - Mosca, Michele AU - Tapp, Alain PY - 2000/May/15/ UR - http://arxiv.org/abs/quant-ph/0005055 ER -