Pith. Sign in

REVIEW

Quantum Amplitude Amplification and Estimation

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Gilles Brassard (1), Peter Hoyer (2), Michele Mosca (3), Alain Tapp (3) ((1) DIRO Universite de Montreal, (2) BRICS University of Aarhus, (3) CACR University of Waterloo)

Quantum Physics · Submitted 15 May 2000 · 15 references

Pith's verdict: This paper generalizes Grover search to arbitrary unitaries and unknown success probabilities while adding amplitude estimation for optimal counting.

T0 · AI review

How this review was made: An AI referee (grok-4.3) read the paper on May 16, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 2 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv IDquant-ph/0005055 (version 1)
Pith IDYZXB4G6T, Pith's permanent record of this paper and its review
Citation(2) BRICS University of Aarhus, (3) CACR University of Waterloo), Alain Tapp (3) ((1) DIRO Universite de Montreal, Gilles Brassard (1), Michele Mosca (3), Peter Hoyer (2). "Quantum Amplitude Amplification and Estimation." arXiv:quant-ph/0005055 (2000). https://pith.science/paper/YZXB4G6T
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Amplitude amplification finds a good element after a number of steps proportional to one over the square root of its initial probability.

The reading

This paper introduces amplitude amplification, a quantum process that finds an element x satisfying a Boolean condition chi after an expected number of applications of a given unitary algorithm A and its inverse that scales as 1 over the square root of a, where a is the probability that A produces a good x upon measurement. It generalizes Grover's algorithm, which was limited to uniform superpositions and a single promised solution, to arbitrary initial superpositions produced by any measurement-free A. The method works whether or not a is known in advance, and when a is known it succeeds in a fixed number of steps with high probability. The authors further combine the amplification idea with phase estimation to perform amplitude estimation, which estimates the value of a itself to high precision, and apply this to obtain optimal quantum algorithms for approximate counting of the number of good elements in X.

What carries the argument

The amplitude amplification operator constructed from A, its inverse, and reflections based on the condition chi, which rotates the state vector to increase the amplitude of good outcomes.

Extended reading notes

Core claim

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 a

Load-bearing premise

The initial algorithm A is unitary and performs no measurements.

Editorial extensions

If this is right

  • Any search problem whose good elements have probability a under a unitary preparation algorithm can be solved with quadratic speedup over classical repetition.
  • When the success probability a is known, a fixed number of applications suffices to find a solution with high probability.
  • The same quadratic speedup applies to search problems equipped with good classical heuristics that can be turned into a unitary algorithm A.
  • Amplitude estimation yields optimal quantum query complexity for approximate counting of the number of solutions to chi(x)=1.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The technique supplies a general primitive that can be substituted for classical repetition sampling in any quantum algorithm whose analysis depends on estimating or boosting success probabilities.
  • It opens the door to quantum versions of heuristic search methods in which the initial distribution produced by A is biased toward promising regions rather than uniform.
  • Because amplitude estimation recovers a with precision scaling as the square root of the number of queries, it can replace classical Monte Carlo estimation in hybrid quantum-classical pipelines.
Original 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.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 7,995 input tokens.

What the abstract itself states, as probabilities: claims first 0.06 · states limitation 0.36 · human participants 0.01 · controlled comparison 0.06 · randomized assignment 0.02 · states quantitative result 0.94 · compares with prior results 0.92 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; .

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.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 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. background 0.99 0.07 0.01 asserted 0.90
s1 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. background 0.88 0.14 0.02 asserted 0.93
s2 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. background 0.44 0.42 0.08 asserted 0.83
s3 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$. background 0.67 0.20 0.03 asserted 1.00
s4 Our algorithm works whether or not the value of $a$ is known ahead of time. contribution 0.65 0.84 0.04 asserted 0.99
s5 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. result 0.78 0.81 0.05 asserted 0.82
s6 We show that this quadratic speedup can also be obtained for a large family of search problems for which good classical heuristics exist. result 0.56 0.88 0.05 asserted 0.99
s7 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$. contribution 0.93 0.93 0.93 asserted 1.00
s8 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$. contribution 0.77 0.91 0.05 asserted 0.97
s9 We obtain optimal quantum algorithms in a variety of settings. result 0.94 0.89 0.09 asserted 1.00

What kind of paper the classifier reports this is: method or tool 0.97 · evidence from proof or derivation 0.99.

What was examined, and what was not

sources read
  • arXiv listing abstract v1
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References
How later papers used it

396 later papers cite it

Evidence: substantial. 393 of the citing papers share no author with it, and 186 of those carry a confident label from Pith's citation classifier.

Pith read 40 of the 757 citing sentences, choosing only those whose citation markers point at this paper alone, and wrote the paraphrases from them. The summary, the counts, the evidence level, the links and the quotes come from code; the summary counts the papers listed below. A later paper is listed under a label when Pith's citation classifier gives one of its sentences that label at probability 0.8 or more (0.95 for support), Pith's reading finds that the citing paper itself did it, and a second check confirms the paraphrase against the sentence. This section lists uses only. It does not list criticism or disagreement, so their absence here says nothing about how the paper has been received. Papers that share an author with this one are listed apart, under "By the same authors". A quote is the citing authors' own sentence, shown when their paper's licence is CC BY, CC BY-SA or CC0. JSON

Uses its method or tool 17 of 175 papers with this label
Compares with it 1 of 13 papers with this label
How the literature uses it

193 arXiv papers cite this in 360 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers whose main result relates to this one's

Found among the papers closest to this one by title and main claim. Pith's classifier compared each pair's main results and a second model family confirmed the relation; checked against two further families, shown conflicts agreed 118 times in 120 and shown same results 218 times in 239. The quoted sentence is the other paper's main claim.

States the same result 1 paper
  • Finally, as our main result, we combine ideas from Grover's and Shor's quantum algorithms to perform approximate counting, which can be seen as an amplitude estimation process.

    Quantum Counting · 0.92

Papers citing it · 178 sentences without a confident label

Builds on it 2 papers
Uses its method or tool 95 papers
Compares with it 4 papers
Cites it as background 43 papers
  • The quantum analogue of classical MCI is known as Quantum Monte Carlo Integration (QMCI) [ref] , and this quantum algorithm utilises the Quantum Amplitude Estimation [ref] (QAE) algorithm as a key subroutine, providing a quadratic speed-up in root mean-squared error (RMSE) convergence with respect to classical MCI.

    A general approach to quantum integration of cross sections in high-energy physics · Introduction · 0.86

  • Grover's search provides a quadratic speed-up of $𝒪(√(N))$ over classical methods [ref] ; it uses an oracle $O$ to mark states representing search solutions by flipping their amplitude signs [ref] ; then, an iterative amplitude amplification increases the probability of measuring the correct result [ref] .

    Quantum-Enhanced Weight Optimization for Neural Networks Using Grover's Algorithm · Deep Learning and Quantum Computing · 0.94

  • Quantum amplitude estimation and related quantum mean estimation algorithms reduce the sampling complexity of expectation estimation from $𝒪(ϵ^-2)$ to $𝒪(ϵ^-1)$, thereby providing a quadratic speedup over classical Monte Carlo methods [ref] .

    Quantum Derivative Pricing for SPDEs via BDSDE Representation · Introduction · 0.80

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.