# Amplitude amplification and estimation require inverses

arXiv: https://arxiv.org/abs/2507.23787 · HTML: https://mlsanity.com/paper/2507.23787/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2025.

## Built on by (most cited first, 6 of 6)

- [Learning the structure of open quantum systems](https://mlsanity.com/paper/2606.30358/) (2026)
- [Optimal algorithmic complexity of inference in quantum kernel methods](https://mlsanity.com/paper/2604.15214/) (2026)
- [Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit](https://mlsanity.com/paper/2510.06925/) (2025)
- [The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)](https://mlsanity.com/paper/2602.01054/) (2026)
- [Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries](https://mlsanity.com/paper/2609.38403/) (2026)
- [Hamiltonian locality testing and certification do not achieve the Heisenberg limit](https://mlsanity.com/paper/2610.03205/) (2026)

## Abstract (arXiv)

We prove that the generic quantum speedups for brute-force search and counting only hold when the process we apply them to can be efficiently inverted. The algorithms speeding up these problems, amplitude amplification and amplitude estimation, assume the ability to apply a state preparation unitary U and its inverse U^dagger; we give problem instances based on trace estimation where no algorithm which uses only U beats the naive, quadratically slower approach. Our proof of this is simple and goes through the compressed oracle method introduced by Zhandry. Since these two subroutines are responsible for the ubiquity of the quadratic "Grover" speedup in quantum algorithms, our result explains why such speedups are far harder to come by in the settings of quantum learning, metrology, and sensing. In these settings, U models the evolution of an experimental system, so implementing U^dagger can be much harder -- tantamount to reversing time within the system. Our result suggests a dichotomy: without inverse access, quantum speedups are scarce; with it, quantum speedups abound.