CoChat

Quantum amplitude amplification and estimation

Open access
Brassard, Gilles, Høyer, Peter, Mosca, Michele, Tapp, Alain · 2002 · Contemporary Mathematics

The 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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1090/conm/305/05215

Cites

20 of 20 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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?

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

Show all 20 references

Research works printed but not linked: 1

  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

See all 1,680

Metadata

Authors
Brassard, G., Høyer, P., Mosca, M., & Tapp, A.
Affiliations
  • Aarhus University (DK)
  • University of Waterloo (CA)
Venue
Contemporary Mathematics
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
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.