Amplitude amplification and estimation require inverses

Ewin Tang; John Wright

arxiv: 2507.23787 · v2 · submitted 2025-07-31 · 🪐 quant-ph · cs.CC· cs.DS

Amplitude amplification and estimation require inverses

Ewin Tang , John Wright This is my paper

Pith reviewed 2026-05-19 01:29 UTC · model grok-4.3

classification 🪐 quant-ph cs.CCcs.DS

keywords amplitude amplificationamplitude estimationtrace estimationcompressed oracleGrover speedupquantum algorithmsquantum sensing

0 comments

The pith

Quantum speedups for search and counting require efficient inverse access to the state preparation unitary.

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

The paper establishes that amplitude amplification and amplitude estimation provide their generic quadratic speedups for brute-force search and counting only when both a state preparation unitary U and its inverse U dagger are available. It constructs concrete trace estimation problem instances where any algorithm restricted to forward applications of U alone performs no better than the classical method that is quadratically slower. The simple proof proceeds via the compressed oracle method. This accounts for the scarcity of such speedups in quantum learning, metrology, and sensing, where U models physical evolution and the inverse corresponds to reversing time in the system.

Core claim

What carries the argument

Access to both the forward state preparation unitary U and its inverse U dagger, which is necessary for amplitude amplification and estimation to deliver quadratic speedups, as shown by failure on trace estimation instances under the compressed oracle analysis.

If this is right

In quantum learning, metrology, and sensing, where U models the evolution of an experimental system, quadratic speedups become much harder to obtain because implementing U dagger is tantamount to reversing time.
A clear dichotomy holds: without inverse access quantum speedups are scarce, while with inverse access they abound.
The ubiquity of the Grover speedup in quantum algorithms rests on the assumption that efficient inversion is possible.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Quantum algorithm design for physical or experimental systems may need to prioritize methods that avoid dependence on time-reversal operations.
This separation could help classify which quantum speedups remain feasible when only forward evolution is controllable.

Load-bearing premise

The trace estimation problem instances are representative of the settings where amplitude amplification is typically applied, and the compressed oracle method correctly captures the power of algorithms that have only forward access to U.

What would settle it

An explicit algorithm that uses only forward applications of U and achieves a quadratic speedup over classical methods on the constructed trace estimation instances would disprove the central claim.

read the original abstract

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.

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 claims amplitude amplification and estimation need inverses, shown via compressed-oracle lower bounds on trace estimation instances, but the details of those instances will decide how far the limitation reaches.

read the letter

The main thing to know is that the authors argue the standard quadratic speedups from amplitude amplification and estimation only work when you have efficient access to the inverse of the state preparation unitary. They support this with trace estimation problem instances where forward-only use of U gives no improvement over the naive classical method, and they prove the bound using Zhandry's compressed oracle technique. This is positioned as an explanation for why Grover-style speedups remain rare in quantum sensing, metrology, and learning, where physical evolution makes time reversal difficult. The result frames a clean dichotomy: inverses enable the usual speedups, and without them they are scarce. That framing is the clearest contribution here. It takes an established lower-bound tool and applies it to a practical constraint rather than inventing new positive algorithms. The explicit instance construction avoids vague assumptions and keeps the claim tied to concrete oracles. The approach looks consistent with prior compressed-oracle work on oracle separations. The soft spot is the reliance on the specific trace estimation instances and the exact reduction steps. The abstract states that no forward-only algorithm beats the slower baseline, but without seeing how those instances are built or how the compressed oracle rules out every possible forward algorithm, it is difficult to judge whether the bound applies broadly or only to a narrow class of problems. If the instances turn out to be artificial or miss natural forward-only strategies that people actually use, the practical takeaway narrows. The same goes for whether the model accurately captures settings where inversion is truly unavailable rather than just inconvenient. This paper is aimed at quantum algorithm designers who work with physical oracles or who want to understand the boundaries of quadratic speedups. A reader already familiar with compressed oracles and amplitude amplification would get the most out of the limitation argument. It is worth sending for peer review so the reductions and instance constructions can be checked in full. The core claim is relevant enough that a referee should evaluate whether the evidence supports the stated scope.

Referee Report

1 major / 0 minor

Summary. The paper claims that generic quantum speedups for brute-force search and counting via amplitude amplification and amplitude estimation require efficient access to the inverse of the state preparation unitary U. It constructs problem instances based on trace estimation for which no algorithm using only forward access to U outperforms the naive quadratically slower classical approach, with the proof proceeding via Zhandry's compressed oracle method. The result is positioned as explaining the scarcity of such speedups in quantum learning, metrology, and sensing, where U models system evolution and U† is tantamount to time reversal.

Significance. If the central claim holds, the result would clarify a fundamental prerequisite for quadratic quantum speedups, establishing a dichotomy between settings with and without inverse access. This has potential explanatory power for the relative difficulty of obtaining Grover-like advantages in experimental quantum information processing.

major comments (1)

Abstract: the central claim that trace-estimation instances exist on which forward-only algorithms using U cannot beat the naive approach rests on an explicit construction and a compressed-oracle lower bound whose details are not supplied; without these, it is impossible to verify that the instances are non-trivial, correctly model settings without efficient inversion, or rule out all forward-only speedups rather than a restricted class of algorithms.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their report and the opportunity to clarify our manuscript. We respond to the major comment below.

read point-by-point responses

Referee: Abstract: the central claim that trace-estimation instances exist on which forward-only algorithms using U cannot beat the naive approach rests on an explicit construction and a compressed-oracle lower bound whose details are not supplied; without these, it is impossible to verify that the instances are non-trivial, correctly model settings without efficient inversion, or rule out all forward-only speedups rather than a restricted class of algorithms.

Authors: The abstract provides a high-level summary of the result, as is standard. The full manuscript contains the explicit construction of the trace-estimation instances (which are chosen to be non-trivial and to model physical settings such as quantum sensing or metrology where efficient inversion of U is unavailable) together with the complete proof that applies Zhandry's compressed-oracle technique. This lower bound holds for arbitrary algorithms that have only forward access to U and rules out quadratic speedups in general, not merely for a restricted class. The construction and proof appear in the main body and appendices; we are happy to expand the abstract with a one-sentence pointer to the method if the referee believes that would improve clarity. revision: partial

Circularity Check

0 steps flagged

No circularity: proof uses external Zhandry compressed oracle method plus explicit instance construction

full rationale

The paper's derivation chain consists of constructing explicit trace-estimation problem instances and invoking Zhandry's prior compressed-oracle technique to bound forward-only algorithms. This is an external reference (Zhandry is not an author) and produces concrete counterexamples rather than fitting parameters or renaming results. No self-citation appears in the abstract, no equation reduces to its own input by construction, and the central claim remains independently verifiable against the cited external method. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the applicability of the compressed oracle method to the forward-only setting and on the trace-estimation instances being hard without the inverse; no new free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Zhandry's compressed oracle method correctly models the power of quantum algorithms with only forward access to a unitary.
The proof is stated to go through this method; its validity is taken from prior work.

pith-pipeline@v0.9.0 · 5684 in / 1177 out tokens · 19046 ms · 2026-05-19T01:29:38.587783+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

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.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 2 Pith papers

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

Strict Hierarchy for Quantum Channel Certification to Unitary
quant-ph 2026-04 unverdicted novelty 8.0

Optimal algorithms achieve query complexities Θ(d/ε²) for incoherent access, Θ(d/ε) for coherent access, and Θ(√d/ε) for source-code access in quantum channel certification to unitary, exactly matching prior lower bounds.
Efficient Learning of Structured Quantum Circuits via Pauli Dimensionality and Sparsity
quant-ph 2025-09 unverdicted novelty 7.0

A general framework and query-efficient algorithms for learning structured quantum unitaries based on Pauli spectrum support on small subgroups or sparsity, unifying prior results for multiple circuit classes.