REVIEW 2 minor 49 cited by
Quantum Amplitude Amplification and Estimation
T0 review · 0 major / 2 minor · reviewed 2026-05-16 · grok-4.3
Pith's one-line read Amplitude amplification finds a good element after a number of steps proportional to one over the square root of its initial probability.
desk verdict This paper generalizes Grover search to arbitrary unitaries and unknown success probabilities while adding amplitude estimation for optimal counting. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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.
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
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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
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
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.
Assumptions & free parameters
assumptions (1)
- standard math Unitary evolution of quantum states
Cite this review
Pith. "Pith review of Quantum Amplitude Amplification and Estimation." pith.science (2026). https://pith.science/paper/YZXB4G6T
@misc{pith2026quant-ph0005055,
author = {Pith},
title = {Pith review of: Quantum Amplitude Amplification and Estimation},
year = {2026},
howpublished = {\url{https://pith.science/paper/YZXB4G6T}},
note = {Machine review of arXiv:quant-ph/0005055}
}
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.
Forward citations
Cited by 49 Pith papers
-
Improved Quantum Algorithms for Subset Sum and $k$-SUM
A quantum walk over randomly sampled subset pairs yields a worst-case O~(n^{2k/7}) algorithm for k-SUM and an O^*(2^{2n/7}) algorithm for Subset Sum.
-
Quantum Pattern Matching with Wildcards
A quantum algorithm solves wildcard pattern matching in O~(sqrt(n) sqrt(k)) time when the total number of wildcards k is at least sqrt(n).
-
Quantum Approximate Counting, Simplified
Quantum approximate counting can match the optimal query complexity without the quantum Fourier transform, using only Grover iterations and classic coin-estimation analysis.
-
Quantum algorithm for estimating volumes of convex bodies
A quantum algorithm estimates the volume of an n-dimensional convex body within error epsilon using O-tilde(n^3 + n^2.5/epsilon) membership queries, the first quantum speedup for this task.
-
Faster Algorithms for Multimarginal Optimal Transport
New algorithms approximate multimarginal optimal transport with near-linear classical time and sublinear quantum time in the tensor dimension, plus matching query lower bounds.
-
A Paturi Theorem for Signed Subcube Representations
For symmetric Boolean functions, approximate signed-subcube weight is 2^Theta(D) and sparsity is 2^Theta(D) log n up to log factors, where D is the deepest transition depth.
-
Faster quantum linear system solver beyond the condition number
Two quantum linear system solvers are presented with query complexity independent of the condition number, scaling instead with an effective condition number or a solution-norm ratio.
-
Faster Exponential-Time Approximate Counting via Bounded Self-Reductions
A reusable enumerate-or-sample framework turns recursion-tree upper bounds into O*(sqrt(b))-time approximate counters, improving bases for five counting problems.
-
On estimating operator norm distance, with optimal trace distance estimation when one state is pure
Rank-independent quantum estimators achieve Θ(1/ε) queries for operator-norm (and trace) distance when one state is pure, and Õ(1/ε^{3/2}) queries for general states, proving BQP-completeness.
-
A Quantum Collocation Approach to One-Dimensional Boundary Value Problems with Coherent Amplitude Amplification
Quantum collocation framework for 1D linear and nonlinear BVPs that uses a residual-threshold oracle on joint spatial-parameter registers to produce coherent superposition of spatially conditioned amplitude amplificat...
-
Explicit Quantum Circuit Simulation of Nonlinear 1-Dimensional Fluid with Carleman-linearized Boltzmann Method
Explicit quantum-circuit simulation of nonlinear 1D fluid via second-order Carleman-linearized Boltzmann equation and QSVD Taylor ODE solver, with logarithmic scaling analysis.
-
Quantum Divide-and-Conquer for the Traveling Salesman Problem: Surpassing the $2^n$ Barrier
Quantum divide-and-conquer with structured set-partition state preparation solves general TSP in O*(1.866^n) time, the first quantum algorithm claimed to beat the classical O*(2^n) barrier.
-
Quantum Solvers for Nonlinear Matrix Equations in Quantum Chemistry
Quantum algorithm block-encodes Riccati solutions for m-particle m-hole RPA using Riesz projectors and QSVT, claiming linear system-size scaling under sparsity and polynomial cost in excitation rank m.
-
Measuring Less to Learn More: Quadratic Speedup in learning Nonlinear Properties of Quantum Density Matrices
A quantum algorithm estimates Tr(ρ^k O) with O(√k) queries to a purification-preparing unitary, quadratically faster than sample-based methods, with a claimed matching lower bound.
-
Matrix Inversion by Quantum Walk
A quantum matrix-inversion algorithm that uses only Hamiltonian evolution of a weakly coupled embedding, removing phase estimation from HHL.
-
Quantum simulation of scattering amplitudes and interferences in perturbative QCD
A quantum circuit encodes QCD colour factors and diagram interferences in a measurement probability, with permuted identical-particle diagrams generated by swap sorting networks.
-
Creation of Wave Packets for Quantum Chromodynamics on Quantum Computers
A quantum algorithm based on Haag-Ruelle theory and LCU proposes to prepare hadron wave packets from the vacuum in 3D lattice QCD, with a success probability that shrinks polynomially with lattice spacing, energy, and...
-
A shortcut to an optimal quantum linear system solver
The paper gives a QLSS with query complexity (1+O(ε))κ ln(2√2/ε) using one kernel reflection when ||x|| is known, or O(κ log(1/ε)) overall, with explicit bound 56κ + 1.05κ ln(1/ε).
-
Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
Any n-qubit unitary can be implemented approximately with Õ(2^{n/2}) oracle queries or exactly with Õ(2^{n/2}) circuit depth via Grover search reductions, with matching lower bounds for certain implementations.
-
Span Programs and Quantum Space Complexity
Unitary quantum space complexity is lower bounded by log approximate span program size, and an explicit function requires (log n)^(2-o(1)) space for monotone phase estimation algorithms.
-
Optimal fidelity estimation when one state is pure via algorithmic Uhlmann transform
When at least one of two quantum states is pure, the Uhlmann fidelity can be estimated with Θ(1/ε) queries and Θ(1/ε²) samples without knowing which state is pure, matching the optimal lower bounds.
-
QuantumMind: Constraint-Grounded Agentic Reasoning for Speedup Analysis in Quantum Computing
A structured AI agent with typed steps and deterministic checks beats prompting and agentic baselines for producing auditable quantum-speedup hypotheses, scoring 53.1 versus 35.8 mean ODS on 582 tasks.
-
High-level quantum structured programs as quantum registers compositions
A formal framework for structured quantum programming where operations act on entire quantum registers, demonstrated by a quantum SMT solver prototype.
-
Closed Timelike Curve Decoding on Quantum Hardware
Routing a Deutsch-CTC loop state to a dump register makes the induced map the replacement channel σ ↦ ρ_M with unique fixed point ρ_M; IBM single-qubit data characterize the post-selected decoder branch.
-
Structure-Aware Variational State Preparation for Quantum Basket Option Pricing
A basket-CDF-based variational loader cuts quantum state-preparation depth from exponential to linear for basket option pricing, at few-percent simulated pricing error.
-
Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth
A two-layer quantum circuit encodes the product of K matrices into a state in depth O(polylog), independent of K, under QRAM state preparation.
-
Quantum ring all-reduce: communication and privacy advantages for distributed learning
Quantum ring all-reduce halves per-link communication via superdense coding and enables composable ε-secure aggregation at 2x GHZ overhead, plus quantum advantages in gradient conflict detection.
-
Quantum Algorithms for Modulated Circulant Matrix Vector Multiplication
Defines the Modulated Quantum Fourier Transform (MQFT) as a quantum primitive for modulated circulant matrix-vector multiplication.
-
Efficient and Expressive Boundary Conditions in Quantum Lattice Boltzmann Methods
New boundary condition approach for QLBM using one coherent operation on the full boundary, claimed to use fewer resources asymptotically and practically for bounce-back and specular reflection.
-
Quantum algorithms for density functional theory with minimal readout
Qubit-efficient quantum algorithm for KS-DFT computes occupied orbitals simultaneously and evaluates total energy via Harris functional without density readout, with a second multi-copy method for self-consistency.
-
Introduction to Generalized Symmetries
Vector-norm Trotter error bounds cut the time-step count by exponential-in-n factors for quantum solvers of anisotropic convection and diffusion equations versus operator-norm analyses.
-
Fourier extensions for matrix-function block encodings with error-independent subnormalization bounds
Fourier-extension-based LCU approximates non-unitary operators with exponential accuracy and subnormalization growing only double-logarithmically in inverse error.
-
A Grover-compatible manifold optimization algorithm for quantum search
A Riemannian gradient-ascent method with oracle/diffusion-only 'Grover-compatible' retractions converges to the marked state in O(√N log(1/ε)) iterations, matching Grover's quadratic speedup.
-
Heisenberg limited quantum algorithm for estimating the fidelity susceptibility
A quantum algorithm estimates fidelity susceptibility in O~(1/epsilon) queries using a resolvent reformulation, achieving Heisenberg-limited precision.
-
Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities
Quantum algorithms for bandits with knapsacks achieve improved regret and time complexity by replacing classical sampling with quantum Monte Carlo and approximate quantum LP solving.
-
Benincasa-Dowker-Glaser causal set actions by quantum counting
Presents an asymptotically optimal Õ(n²)-time quantum algorithm for the BDG causal set action via uniform superposition over causal set encodings and two-stage quantum counting.
-
Beyond Worst-Case Branching: Quantum Tree Search via Amplitude Amplification
Amplitude amplification constructs dynamic search trees of depth m with query complexity √(b_avg^m), outperforming worst-case assumptions and quantum backtracking for problems lacking natural backtracking structure.
-
Tuning Quantum MPS
Two-stage CMA-ES optimization plus circuit-feature ranking model for MPS hyperparameter tuning, recovering part of the offline optimum gain on circuit families.
-
Automatic De-Quantization of Quantum Programs Using Constant Propagation
Hybrid quantum-classical constant propagation reduces multi-qubit quantum operations by propagating constants between quantum and classical program states.
-
QuantFPFlow: Quantum Amplitude Estimation for Fokker--Planck Policy Optimisation in Continuous Reinforcement Learning
QuantFPFlow uses quantum amplitude estimation in a Fokker-Planck RL framework to achieve O(1/ε) partition function estimation and reports improved global optimum discovery plus better scaling in continuous control tasks.
-
Offline dedicated quantum attacks on block cipher constructions based on two parallel permutation-based pseudorandom functions
By separating XOR-type functions into secret and public halves, quantum key-recovery on TPP-PRF block cipher constructions becomes offline and reduces Q2 oracle queries from O(2^{(n+t)/2}(n-t)) to O(2^t(n-t)).
-
Circuit-Efficient Randomized Quantum Simulation of Non-Unitary Dynamics with Observable-Driven and Symmetry-Aware Designs
A randomized compilation of LCHS for non-unitary dynamics, with an observable-driven variant and a symmetry-aware sampler, claims reduced ancilla and circuit depth at the cost of more repetitions.
-
The Input Problem: A Permanent Bottleneck for Quantum Machine Learning
Preparing a generic classical data vector as a quantum state provably costs Θ(N) gates, so algorithms that claim O(polylog N) total time on classical data are dominated by their own input stage.
-
Nested Grover's Algorithm for Tree Search
A nested Grover algorithm for tree search claims cost O(m*2^(m/4)) using partial candidate solutions, but the speedup relies on an unexamined assumption that the candidate set contains the solution.
-
Efficient Maximum Clique Detection via Grover's Algorithm with Real-time Global Size Tracking
A proposed Grover-based maximum clique solver claims O(sqrt(2^n)) iterations and O(1) measurements by pre-encoding the clique size, but the pre-encoding itself costs exponentially many gates and is excluded from the h...
-
A Quantum Path to Partial Differential Equations
Lecture notes that organize quantum PDE algorithms around block encodings of finite-difference and finite-element operators, tracking discretization, preparation, normalization, postselection, and measurement costs.
-
An Information-Theoretic Characterization of Optimal Value-Readout in Response-Register Quantum Oracles
For finite Abelian response groups, the optimal single-query value-readout probability equals the normalized Rényi-1/2 effective Fourier support of the response state.
-
Quantum algorithms for the simulation of QCD processes in the perturbative regime
Quantum circuits for the colour algebra of perturbative QCD are presented and validated on a simulator, matching analytic colour factors for example diagrams.
-
A Rigorous and Self--Contained Proof of the Grover--Rudolph State Preparation Algorithm
The Grover–Rudolph correctness proof is formally redone, but the claimed error bound and bit/shots rule are only in the abstract, and the Gray-code ladder proof has a false step.
Reference graph
Works this paper leans on
-
[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]
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]
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
Show all 15 references
-
[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
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
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
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>
1995 arXiv
-
[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
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
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
1997
Reviewed May 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.