dorsal/arxiv
View SchemaQuantum Amplitude Amplification and Estimation
| Authors | Gilles Brassard, Peter Hoyer, Michele Mosca, Alain Tapp |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0005055 |
| URL | https://arxiv.org/abs/quant-ph/0005055 |
| DOI | 10.1090/conm/305/05215 |
| Journal | Quantum Computation and Quantum Information, Samuel J. Lomonaco, Jr. (editor), AMS Contemporary Mathematics, 305:53-74, 2002 |
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 |0\rangle= \sum_{x\in X} \alpha_x |x\rangle$ is a quantum superposition of the elements of $X$, and let $a$ denote the probability that a good element is produced if $A |0\rangle$ 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.
{
"annotation_id": "6404f03e-1bdb-4ab7-a926-6fc7560c13f5",
"date_created": "2026-03-02T18:01:38.736000Z",
"date_modified": "2026-03-02T18:01:38.736000Z",
"file_hash": "09ab5fd5541fefdb015f189e82ee122742daae51369ff2bf85ce23a2ec6685f0",
"private": false,
"record": {
"abstract": "Consider a Boolean function $\\chi: X \\to \\{0,1\\}$ that partitions set $X$\nbetween its good and bad elements, where $x$ is good if $\\chi(x)=1$ and bad\notherwise. Consider also a quantum algorithm $\\mathcal A$ such that $A\n|0\\rangle= \\sum_{x\\in X} \\alpha_x |x\\rangle$ is a quantum superposition of the\nelements of $X$, and let $a$ denote the probability that a good element is\nproduced if $A |0\\rangle$ is measured. If we repeat the process of running $A$,\nmeasuring the output, and using $\\chi$ to check the validity of the result, we\nshall expect to repeat $1/a$ times on the average before a solution is found.\n*Amplitude amplification* is a process that allows to find a good $x$ after an\nexpected number of applications of $A$ and its inverse which is proportional to\n$1/\\sqrt{a}$, assuming algorithm $A$ makes no measurements. This is a\ngeneralization of Grover\u0027s searching algorithm in which $A$ was restricted to\nproducing an equal superposition of all members of $X$ and we had a promise\nthat a single $x$ existed such that $\\chi(x)=1$. Our algorithm works whether or\nnot the value of $a$ is known ahead of time. In case the value of $a$ is known,\nwe can find a good $x$ after a number of applications of $A$ and its inverse\nwhich is proportional to $1/\\sqrt{a}$ even in the worst case. We show that this\nquadratic speedup can also be obtained for a large family of search problems\nfor which good classical heuristics exist. Finally, as our main result, we\ncombine ideas from Grover\u0027s and Shor\u0027s quantum algorithms to perform amplitude\nestimation, a process that allows to estimate the value of $a$. We apply\namplitude estimation to the problem of *approximate counting*, in which we wish\nto estimate the number of $x\\in X$ such that $\\chi(x)=1$. We obtain optimal\nquantum algorithms in a variety of settings.",
"arxiv_id": "quant-ph/0005055",
"authors": [
"Gilles Brassard",
"Peter Hoyer",
"Michele Mosca",
"Alain Tapp"
],
"categories": [
"quant-ph"
],
"doi": "10.1090/conm/305/05215",
"journal_ref": "Quantum Computation and Quantum Information, Samuel J. Lomonaco,\n Jr. (editor), AMS Contemporary Mathematics, 305:53-74, 2002",
"title": "Quantum Amplitude Amplification and Estimation",
"url": "https://arxiv.org/abs/quant-ph/0005055"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "5520c27e-7aff-4e07-882a-416737fba6b3",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}