Quantum amplitude amplification and estimation
Open accessThe DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing paper
“a quantum algorithm due to Brassard, Høyer, Mosca and Tapp 22 can fi nd w such that f ( w ) = 1 with only O ð 1 = ffiffi ε p Þ uses of f , and failure probability arbitrarily close to 0, thus achieving a quadratic speedup.”
From Quantum algorithms: an overview (2016) · cites this paper as [22]
The cited source says what the claim attributes to it.
In the citing paper
“The success probability of QAA algorithm is known to have the same behaviors of Grover's algorithm [18].”
From Time–space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2 (2018) · cites this paper as [18]
The check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“First, by more sophisticated Trotter-Suzuki decompositions 261 , the approximation error can be made to depend on progressively-higher orders in τ 196,260,261 .”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [196]
Experimental — accuracy not yet measuredIn the citing paper
“For timedependent Hamiltonians, early works 196 focus on variants of Trotter-Suzuki formula, which are subsequently improved with black-box models 188 .”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [196]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306 · cited 5×
“Grover’s algorithm can find the x 0 such that f ( x 0 ) = 1 quadratically faster in the expected sense than the best possible classical algorithm provided the solution is known to be unique [8, 9].”
BackgroundMethodInfluentialCleve, R., Ekert, A., Macchiavello, C., & Mosca, M. (1998) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1998.0164 · Cited by 1,299 · cited 1×
“This approach can also be viewed as an eigenvalue estimation [12, 7] and is best analysed in the basis of eigenvectors of the operator at hand [13].”
BackgroundSelf-citation(1996) · Cited by 824
Quantum lower bounds by polynomials
Beals, R., Buhrman, H., Cleve, R., Mosca, M., & de Wolf, R. (2001) · Journal of the ACM · doi:10.1145/502090.502097 · Cited by 639
Self-citationQuantum Computers Can Search Rapidly by Using Almost Any Transformation
Grover, L. K. (1998) · Physical Review Letters · doi:10.1103/physrevlett.80.4329 · Cited by 616 · cited 1×
“Lemma 1 We have that It follows that the subspace H Ψ is stable under the action of Q , a property that was first observed by Brassard and Høyer [4] and rediscovered by Grover [10].”
BackgroundQuantum measurements and the Abelian Stabilizer ProblemPreprint
Kitaev, A. (1995) · arXiv (Cornell University) · Cited by 510
Notes on the history of reversible computation
Bennett, C. H. (1988) · IBM Journal of Research and Development · doi:10.1147/rd.321.0016 · Cited by 289
An exact quantum polynomial-time algorithm for Simon's problem
Brassard, G., & Hoyer, P. (2002) · Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems · doi:10.1109/istcs.1997.595153 · Cited by 250 · cited 3×
“The general concept of amplifying the amplitude of a subspace was discovered by Brassard and Høyer [4] as a generalization of the boosting technique applied by Grover in his original quantum searching paper [8].”
BackgroundMethodSelf-citation
Research works printed but not linked: 1
- [13][13] Mosca , Michele, 'Quantum searching and counting by eigenvector analysis', Proceedings of Randomized Algorithms , Satellite Workshop of 23rd International Symposium on Mathematical Foundations of Computer Science, Brno, Czech Republic, August 1998, pp. 90 - 100. -
Cited by
Quantum Algorithm for Linear Systems of Equations
Harrow, A. W., Hassidim, A., & Lloyd, S. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.150502 · Cited by 3,325
“Using amplitude amplification [14], we find thatOð Þ repetitions are sufficient.”
MethodQuantum Chemistry in the Age of Quantum Computing
Cao, Y., Romero, J., Olson, J. P., Degroote, M., Johnson, P. D., Kieferová, M., Kivlichan, I. D., Menke, T., Peropadre, B., Sawaya, N. P. D., et al. (2019) · Chemical Reviews · doi:10.1021/acs.chemrev.8b00803 · Cited by 1,560
Quantum algorithms: an overview
Montanaro, A. (2016) · npj Quantum Information · doi:10.1038/npjqi.2015.23 · Cited by 1,071
“[20] can find w such that f(w) = 1 with only O(1/ √ ) uses of f , and failure probability arbitrarily close to 0, thus achieving a quadratic speedup.”
Quantum Walk Algorithm for Element Distinctness
Ambainis, A. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447311 · Cited by 703
Efficient Variational Quantum Simulator Incorporating Active Error Minimization
Li, Y., & Benjamin, S. C. (2017) · Physical Review X · doi:10.1103/physrevx.7.021050 · Cited by 686
“Note that the value of 〈X〉 could be estimated more efficiently using quantum amplitude estimation [51] if error rates could be made low enough to allow a circuit of sufficient depth to function.”
Method
Metadata
- Authors
- Brassard, G., Høyer, P., Mosca, M., & Tapp, A.
- Affiliations
- Aarhus University (DK)
- University of Waterloo (CA)
- Venue
- Contemporary Mathematics
- Publisher
- American Mathematical Society
- Published
- 2002
- Pages
- 53-74
- ISSN
- 0271-4132 (ISSN-L)
- 1098-3627
- OpenAlex
- W2121981260
- Cited by
- 1,680
- References
- 19
- Citations by year
- 2026: 139 · 2025: 217 · 2024: 166 · 2023: 209 · 2022: 153 · 2021: 165 · 2020: 115 · 2019: 72 · 2018: 50 · 2017: 38 · 2016: 36 · 2015: 29 · 2014: 27 · 2013: 26 · 2012: 19
- Type
- other
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Contemporary mathematics - American Mathematical Society (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
- Keywords
- amplitude amplification, amplitude estimation, Grover's algorithm, Shor's algorithm, quantum search, approximate counting, quadratic speedup, quantum algorithms
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Quantum amplitude amplification and estimation. https://app.cochat.ai/papers/10.1090/conm/305/05215
- The paper
- Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002). Quantum amplitude amplification and estimation. Contemporary Mathematics. https://doi.org/10.1090/conm/305/05215
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.