Quantum Amplitude Amplification and Estimation

Gilles Brassard, Peter Høyer, Michele Mosca, Alain Tapp · 2002 · AMS Contemporary Mathematics 305:53-74

| 编号 QAPP002 | 主题 应用 | 链接 arXiv:quant-ph/0005055 |

摘要

摘要保留原文（英文）

摘要取自 arXiv / 出版方元数据，未作翻译，以保证与原文一致。

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|0⟩={\sum }_{x\in X}{\alpha }_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 $\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.

本站词条在引用该文献时，会以 wikilink（sources/QAPP002）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。