arxiv: quant-ph/0005055 · v1 · submitted 2000-05-15 · 🪐 quant-ph

Recognition: 2 theorem links

· Lean Theorem

Quantum Amplitude Amplification and Estimation

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)

Authors on Pith no claims yet

Pith reviewed 2026-05-16 03:39 UTC · model grok-4.3

classification 🪐 quant-ph

keywords amplitude amplificationGrover algorithmquantum searchamplitude estimationapproximate countingquadratic speedupquantum algorithm

0 comments

The pith

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

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

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.

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

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.

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.

Where Pith is reading between the lines

These are 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.

Load-bearing premise

The initial algorithm A is unitary and performs no measurements.

What would settle it

A direct simulation or experiment for small known values of a that shows the number of applications of A needed to produce a good x scales linearly with 1/a instead of 1/sqrt(a) would falsify the claim.

read the 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

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

read the letter

The main thing to know is that Brassard, Hoyer, Mosca and Tapp give a clean generalization of Grover's algorithm called amplitude amplification. It finds a marked item after an expected O(1/sqrt(a)) applications of any unitary A that produces good states with probability a, even when a is unknown in advance. They also combine the idea with phase estimation to estimate a itself, which yields optimal quantum algorithms for approximate counting of the number of good x in X. Both results follow directly from the geometry of the two-dimensional good/bad subspace and the rotation induced by the operator Q = -A S0 A^{-1} S_chi. The derivations are explicit and the paper states the unitary, measurement-free assumption on A up front, so there is no hidden circularity. The same framework applies to any search problem that already has a decent classical heuristic A, which is a useful practical point. The math checks out from standard quantum mechanics and the citation pattern to Grover and Shor is appropriate for the time. The only soft spot worth noting is that the paper stays at the level of asymptotic bounds and explicit operator constructions; it does not work out concrete gate counts or discuss how to realize a given heuristic A as a unitary in a real circuit. That is minor for a foundational algorithms paper. Readers who care about quantum query complexity, search, or early applications of phase estimation will get direct value from the explicit algorithms and the counting results. The work is coherent on its own terms and the central claims hold once the stated assumptions are granted. I would send it to peer review without hesitation.

Referee Report

0 major / 2 minor

Summary. The manuscript introduces quantum amplitude amplification as a generalization of Grover's search algorithm. Given a unitary operator A producing a superposition with good-element probability a, it shows that a good x can be found after an expected O(1/sqrt(a)) applications of A and A^{-1} (whether or not a is known in advance). When a is known, a worst-case O(1/sqrt(a)) bound is obtained. The paper further combines the technique with quantum phase estimation to perform amplitude estimation of a and applies the result to optimal quantum approximate counting.

Significance. If the central claims hold, the work supplies a parameter-free quadratic speedup for a broad family of search problems that admit classical heuristics and yields optimal quantum algorithms for counting. The derivations rest on standard unitary operator properties and phase estimation without fitted parameters or circularity, providing reusable building blocks for later quantum algorithms.

minor comments (2)

The definition of the composite operator Q = -A S_0 A^{-1} S_chi and the geometric argument that it rotates by 2 theta (with sin^2 theta = a) would benefit from an explicit one-paragraph recap in the main text immediately after the abstract, to aid readers who skip the full derivation.
In the amplitude-estimation section, the precision analysis for the phase-estimation subroutine (number of ancillary qubits and controlled applications of Q) is stated but could be cross-referenced to the exact equation numbers used for the rotation angle.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and the positive assessment of the manuscript. We are gratified that the work is viewed as supplying reusable building blocks for quantum algorithms and that the recommendation is to accept.

Circularity Check

0 steps flagged

Derivation self-contained from unitary operator geometry

full rationale

The paper constructs the amplification operator Q explicitly from the given unitary A and the reflection operators S_0 and S_chi. The two-dimensional good/bad subspace rotation by 2 theta (with sin^2 theta = a) follows directly from the definition of these operators and the assumption that A is unitary with no intermediate measurements. No parameters are fitted to data, no self-citations carry the central claim, and the O(1/sqrt(a)) bound is obtained by counting applications of Q. The argument is internally consistent once the unitary assumption is granted and does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No new free parameters or entities; builds on existing quantum algorithms.

axioms (1)

standard math Unitary evolution of quantum states
Relies on standard quantum computing model.

pith-pipeline@v0.9.0 · 7869 in / 752 out tokens · 229744 ms · 2026-05-16T03:39:06.064896+00:00 · methodology

discussion (0)

Forward citations

Cited by 18 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Accelerating quantum Gibbs sampling without quantum walks
quant-ph 2026-04 unverdicted novelty 8.0

A factorization of the parent Hamiltonian into noncommutative first-order operators enables a walk-free QSVT algorithm with quadratic gap improvement for preparing purified Gibbs states under exact KMS detailed balance.
Tight Quantum Lower Bound for k-Distinctness
quant-ph 2026-04 unverdicted novelty 8.0

A new quantum lower bound framework proves a tight bound for k-Distinctness.
Quantum Causal Discovery via Amplitude Estimation of Kullback-Leibler Divergence
quant-ph 2026-04 unverdicted novelty 7.0

QKLA achieves quadratic query-complexity improvement for clipped KL estimation, yielding 2.7-7.4x fewer oracle queries than classical methods when embedded in the PC causal-discovery algorithm at moderate precision.
Generalized Complexity Distances and Non-Invertible Symmetries
hep-th 2026-04 unverdicted novelty 7.0

Non-invertible symmetries define quantum gates with generalized complexity distances, and simple objects in symmetry categories turn out to be computationally complex in concrete 4D and 2D QFT examples.
Exponential quantum advantage in processing massive classical data
quant-ph 2026-04 unverdicted novelty 7.0

A polylog-sized quantum computer achieves exponential advantage over classical machines in classification and dimension reduction of massive classical data using quantum oracle sketching combined with classical shadows.
A Digital Spreading Framework for Quantum Expectation Computation Without Rotation Gates or Arithmetic Circuits
quant-ph 2026-04 unverdicted novelty 7.0

Digital Spreading computes quantum expectations via integer comparisons on superposed states with a pruned Cuccaro architecture, reaching 0.0001% relative error in option pricing simulations.
Achieving double-logarithmic precision dependence in optimization-based quantum unstructured search
quant-ph 2026-03 unverdicted novelty 7.0

Riemannian modified Newton optimization on quantum search achieves quadratic convergence and O(√(N/M) log log(1/ε)) complexity when M/N is known.
Sample-Based Quantum Diagonalization with Amplitude Amplification
quant-ph 2026-05 conditional novelty 6.0

SQD-AA reduces total query complexity by more than 100x on model distributions and achieves the lowest T-gate counts with 3-4 orders shallower circuits than iQPE for molecular examples.
Finite Imaginary-Time Evolution for Polynomial Unconstrained Binary Optimization
quant-ph 2026-04 unverdicted novelty 6.0

FinITE gives an exact identity linking LCU success probability to ground-subspace fidelity for diagonal Pauli-Z Hamiltonians, yielding a closed-form imaginary-time threshold beta-star based on spectral gap and initial...
A Nested Amplitude Amplification Protocol for the Binary Knapsack Problem
quant-ph 2026-04 unverdicted novelty 6.0

A nested amplitude amplification protocol for knapsack performs partial amplification on initial variables via an Inner Iteration Finder before global GAS, reducing solution improvement costs versus baseline in simula...
Exponentially cheaper coherent phase estimation via uncontrolled unitaries
quant-ph 2026-03 conditional novelty 6.0

Uncontrolled unitaries plus controlled preparations replace controlled unitaries in phase estimation, cutting two-qubit gates exponentially when eigenstate preparation is known.
An HHL-Based Quantum-Classical Solver for the Incompressible Navier-Stokes Equations with Approximate QST
quant-ph 2026-03 unverdicted novelty 6.0

Hybrid quantum-classical solver using HHL for the Navier-Stokes pressure equation with approximate Chebyshev-based QST achieves accurate lid-driven cavity and Taylor-Green vortex simulations in Qiskit.
Quantum embedding of graphs for subgraph counting
quant-ph 2026-04 unverdicted novelty 5.0

A quantum adjacency state on 2 log N qubits plus ancilla enables subgraph count estimation via m-fold tensor product measurements, producing quantum logspace algorithms for motif counting.
Quantangle-SAT: A Quantum SAT Solver Based on Entanglement and Equivalence Checking
quant-ph 2026-04 unverdicted novelty 5.0

Quantangle-SAT is a quantum SAT solver using entanglement and equivalence checking that achieves expected O(1) time complexity for random Boolean functions without requiring prior knowledge of the solution count.
Distributed quantum-classical hybrid algorithm for solving K-SAT problem
quant-ph 2026-04 unverdicted novelty 5.0

A distributed hybrid quantum-classical algorithm for K-SAT that accelerates the exponential core, uses fewer qubits than prior work, and avoids quantum communication.
Unitaria: Quantum Linear Algebra via Block Encodings
quant-ph 2026-05 accept novelty 4.0

Unitaria is a new open-source Python library that provides a high-level, composable interface for block encodings in quantum computing, enabling automatic circuit generation and classical simulation-based verification.
Towards Quantum Optimised Malware Containment
quant-ph 2026-04 unverdicted novelty 4.0

A hybrid quantum approach is proposed to achieve quadratic speedups in influence estimation and edge removal optimization for malware containment modeled as a network influence minimisation problem.
Application of a Quantum Amplitude Redistribution Algorithm to the Data Filtering Problem
quant-ph 2026-04 unverdicted novelty 2.0

Modeling indicates a quantum amplitude redistribution algorithm can perform data filtering with results comparable to a classical median filter.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages · cited by 18 Pith papers · 1 internal anchor

[1]

Quantum lower bounds by polynomials

Beals, Robert, Harry Buhrman, Richard Cleve, Michele Mosca and Ronald de Wolf , “Quantum lower bounds by polynomials”, Proceed- ings of 39th Annual Symposium on Foundations of Computer Sci ence, November 1998, pp. 352 – 361

work page 1998
[2]

Notes on the history of reversible computatio n

Bennett, Charles H., “Notes on the history of reversible computatio n”, IBM Journal of Research and Development , 1988, Vol. 32, pp. 16 – 23

work page 1988
[3]

Tight bounds on quantum searching

Boyer, Michel, Gilles Brassard, Peter Høyer and Alain Tapp, “Tight bounds on quantum searching”, Fortschritte Der Physik , special issue on quantum computing and quantum cryptography, 1998, Vol. 46, pp. 493 – 505

work page 1998
[4]

An exact quantum polynomial- time algorithm for Simon’s problem

Brassard, Gilles and Peter Høyer, “An exact quantum polynomial- time algorithm for Simon’s problem”, Proceedings of Fifth Israeli Sym- posium on Theory of Computing and Systems , IEEE Computer Society Press, June 1997, pp. 12 – 23

work page 1997
[5]

Quantum count- ing

Brassard, Gilles, Peter Høyer and Alain Tapp, “Quantum count- ing”, Proceedings of 25th International Colloquium on Automata, Languages, and Programming , Lecture Notes in Computer Science, Vol. 1443, Springer-Verlag, July 1998, pp. 820 – 831

work page 1998
[6]

Quantum database searching by a sin- gle query

Chi, Dong–Pyo and Jinsoo Kim, “Quantum database searching by a sin- gle query”, Lecture at First NASA International Conference on Quan- tum Computing and Quantum Communications , Palm Springs, Febru- ary 1998. 31

work page 1998
[7]

Quantum algorithms revisited

Cleve, Richard, Artur Ekert, Chiara Macchiavello and Michele Mosca, “Quantum algorithms revisited”, Proceedings of the Royal So- ciety, London , Vol. A354, 1998, pp. 339 – 354

work page 1998
[8]

A fast quantum mechanical algorithm for database search

Grover, Lov K., “A fast quantum mechanical algorithm for database search”, Proceedings of 28th Annual ACM Symposium on Theory of Computing, May 1996, pp. 212 – 219

work page 1996
[9]

Quantum mechanics helps in searching for a needle i n a haystack

Grover, Lov K., “Quantum mechanics helps in searching for a needle i n a haystack”, Physical Review Letters , Vol. 79, July 1997, pp. 325 – 328

work page 1997
[10]

Quantum computers can search rapidly by using almost any transformation

Grover, Lov K., “Quantum computers can search rapidly by using almost any transformation”, Physical Review Letters, Vol. 80, May 1998, pp. 4329 – 4332

work page 1998
[11]

Conjugated operators in quantum algorithms

Høyer, Peter, “Conjugated operators in quantum algorithms”, Physical Review A, Vol. 59, May 1999, pp. 3280 – 3289

work page 1999
[12]

Quantum measurements and the Abelian Stabilizer Problem

Kitaev, A. Yu., “Quantum measurements and the Abelian stabilizer problem”, November 1995. Available at Los Alamos e-Print ar chive as <http:/ /arXiv.org/abs/quant-ph/9511026>

work page internal anchor Pith review Pith/arXiv arXiv 1995
[13]

Quantum searching and counting by eigenvector analysis

Mosca, Michele, “Quantum searching and counting by eigenvector analysis”, Proceedings of Randomized Algorithms, Satellite Workshop of 23rd International Symposium on Mathematical Foundations of Com- puter Science, Brno, Czech Republic, August 1998, pp. 90 – 10 0

work page 1998
[14]

The quantum query complexity of approximating the median and related statistics

Nayak, Ashwin and Felix Wu, “The quantum query complexity of approximating the median and related statistics”, Proceedings of 31st Annual ACM Symposium on Theory of Computing , May 1999, pp. 384 – 393

work page 1999
[15]

Polynomial-time algorithms for prime factoriz ation and discrete logarithms on a quantum computer

Shor, Peter W., “Polynomial-time algorithms for prime factoriz ation and discrete logarithms on a quantum computer”, SIAM Journal on Computing, Vol. 26, October 1997, pp. 1484 – 1509. 32

work page 1997