Amplitude Estimation

Amplitude estimation returns a classical estimate of the success probability

$$a=\langle\psi|\Pi_G|\psi\rangle$$

of a licensed coherent preparation $|\psi\rangle=\mathcal A|0\rangle$. Direct Bernoulli sampling uses $O(1/\epsilon^2)$ preparations to reach additive accuracy $\epsilon$ at fixed confidence. The standard coherent algorithm uses the conjugate eigenphases of an amplitude-amplification iterate and reaches the query scale $O(1/\epsilon)$. Neither expression is automatically a gate count, runtime, or end-to-end advantage.

The improvement requires more than samples: it needs $\mathcal A$, $\mathcal A^\dagger$, two reflections, a fixed unitary representative of the Grover iterate, and controlled powered access. Amplitude Amplification owns the two-reflection geometry; Quantum Phase Estimation owns the general eigenphase circuit and Fourier decoder. This page owns their amplitude-specific composition, the two-branch probability law, the $\sin^2$ fold, precision and confidence, expectation encodings, and the full access-sensitive resource comparison.

Required background. Amplitude Amplification supplies the good–bad plane and exact iterate. Quantum Phase Estimation supplies controlled powers and inverse-Fourier phase decoding. Quantum Oracles supplies the distinction among ordinary, inverse, controlled, and powered access.

Helpful background. The Quantum Algorithms and Complexity guide supplies the chapter claim discipline. Algorithmic Primitives organizes the composition into access, processing, interference, and readout. Query Complexity owns general lower-bound methods, while Grover Search owns uniform marked-item recovery and search optimality.

The Coherent Amplitude-Estimation Problem

Work in a finite-dimensional Hilbert space with a normalized reference state $|0\rangle$. A measurement-free unitary $\mathcal A$ and an orthogonal projector $\Pi_G$ define

$$|\psi\rangle=\mathcal A|0\rangle, \qquad a=\langle\psi|\Pi_G|\psi\rangle\in[0,1].$$

For $0<a<1$, normalize the two projected components:

$$|G\rangle = \frac{\Pi_G|\psi\rangle}{\sqrt a}, \qquad |B\rangle = \frac{(I-\Pi_G)|\psi\rangle}{\sqrt{1-a}}.$$

They are orthonormal because $\Pi_G(I-\Pi_G)=0$, and the prepared state is

$$|\psi\rangle = \sqrt a\,|G\rangle + \sqrt{1-a}\,|B\rangle = \sin\theta\,|G\rangle + \cos\theta\,|B\rangle,$$

where

$$\theta=\arcsin\sqrt a\in(0,\pi/2).$$

The endpoint cases must be handled without dividing by a vanishing norm. If $a=0$, the prepared state is entirely bad. If $a=1$, it is entirely good. Both cases have well-defined phase-estimation behavior, derived below, even though one of the normalized vectors is unnecessary.

For declared $\epsilon>0$ and $0<\delta<1$, the output is a classical random variable $\widetilde a\in[0,1]$ with a statement of the form

$$\Pr\!\left(|\widetilde a-a|\le\epsilon\right)\ge1-\delta.$$

This is an estimation task, not a search task. It does not return a good witness, expose every basis amplitude, or leave $a$ encoded as a reusable exact quantum number. Additive and relative error are different contracts, and a one-run constant-confidence theorem is different from a protocol whose failure probability is chosen by the user.

The Ten-Field Amplitude-Estimation Claim Record

An amplitude-estimation claim is meaningful only when all ten fields below refer to the same problem and cost model.

1. Problem family and size. Identify the family of preparations and good projectors, the parameter tending to infinity, and the quantity whose accuracy is being varied.
2. Promise and instance. State the allowed range of $a$, any lower bound or endpoint promise, the values of $\epsilon$ and $\delta$, and the finite instance under discussion.
3. Access and encoding. Declare $\mathcal A$, $\mathcal A^\dagger$, $\Pi_G$, both reflections, the chosen representative of $Q$, controlled powers, registers, arithmetic, loading, and cleanup.
4. Output and use. Specify the classical estimate or interval, its error convention, and the downstream computation that consumes it.
5. Success and error. Give a finite probability statement, endpoint conditions, implementation-error metric, and any confidence-amplification rule.
6. Algorithmic idea. Name the conjugate Grover eigenphases, the phase schedule, the $\sin^2$ fold, and whether Fourier, likelihood, or adaptive inference is used.
7. Executable procedure. List preparation, controlled or uncontrolled iterates, measurements, repetitions, stopping conditions, and classical postprocessing in runnable order.
8. Resource ledger. Count forward and inverse preparations, each reflection, base and powered queries, coherent depth, qubits, gates, synthesis, measurements, inference, error correction, and physical time.
9. Classical comparator. Match the encoded quantity, input access, output, accuracy, confidence, loading, and total-cost currency before comparing against sampling or another classical method.
10. Evidence and limits. Distinguish theorem, exact finite audit, simulation, noise-model study, and experiment, then state what the evidence does not establish.

The record blocks several silent substitutions: a sampler for an invertible preparation, an uncontrolled iterate for a controlled one, Fisher information for a finite upper bound, and a query reduction for a practical runtime advantage.

Licensed Preparation, Reflections, and Controlled Iterates

The standard construction starts from four coherent components:

$$\mathcal A, \qquad \mathcal A^\dagger, \qquad S_G=I-2\Pi_G, \qquad S_0=I-2|0\rangle\langle0|.$$

Their ordered product defines the exact amplitude-amplification iterate

$$Q=-\mathcal A S_0\mathcal A^\dagger S_G.$$

The leading minus sign fixes a unitary representative, not merely a ray. It is irrelevant when a fixed number of uncontrolled iterates is followed by a measurement, because it then produces only an overall phase. It becomes a relative phase when $Q$ is applied conditionally, so standard amplitude estimation must preserve it.

The primary phase-estimation implementation chooses $M=2^m$ and requires controlled $Q^{2^j}$ for $j=0,\ldots,m-1$. These are separate capabilities:

• an ordinary circuit for $Q$ does not automatically license controlled $Q$;
• controlled $Q$ does not automatically make $Q^{2^j}$ a unit-cost primitive;
• a native powered oracle and $2^j$ repetitions of a base iterate have different query and depth ledgers;
• a measurement-based sampler does not automatically provide $\mathcal A^\dagger$ or coherent workspace cleanup.

If a controlled reflection about $|\psi\rangle$ is compiled as

$$\mathcal A\,\mathrm C(S_0)\,\mathcal A^\dagger,$$

the unconditional outer pair cancels on the control-zero branch, while the controlled reference reflection acts on the control-one branch. A controlled $S_G$ and the controlled phase associated with the leading minus sign remain necessary. Other valid compilations may distribute controls differently, but their component costs must be stated rather than hidden inside the symbol $\mathrm C(Q)$.

The standard access record also includes an $m$-qubit phase register, an inverse Quantum Fourier Transform, one control-register measurement, and classical evaluation of $\sin^2(\pi Y/M)$. Approximate reflections, arithmetic, synthesized rotations, garbage registers, and measurement noise require separate error entries.

Grover Eigenphases Encode the Success Probability

Conjugating the reference reflection gives

$$\mathcal A S_0\mathcal A^\dagger = I-2|\psi\rangle\langle\psi|.$$

In the ordered basis $\{|G\rangle,|B\rangle\}$, multiplication by $S_G$ and the leading minus sign yields

$$Q = \begin{pmatrix} 1-2a & 2\sqrt{a(1-a)}\\ -2\sqrt{a(1-a)} & 1-2a \end{pmatrix} = \begin{pmatrix} \cos2\theta & \sin2\theta\\ -\sin2\theta & \cos2\theta \end{pmatrix}.$$

Thus $Q$ is a rotation through $-2\theta$ in real coordinate convention. Its complex eigenvectors are

$$|\psi_\pm\rangle = \frac{|G\rangle\pm i|B\rangle}{\sqrt2},$$

and direct multiplication gives

$$Q|\psi_\pm\rangle = e^{\pm2i\theta}|\psi_\pm\rangle.$$

The prepared state has equal squared overlap with the two eigenvectors:

$$|\psi\rangle = \frac{-i}{\sqrt2} \left( e^{i\theta}|\psi_+\rangle - e^{-i\theta}|\psi_-\rangle \right).$$

Writing an eigenvalue as $e^{2\pi i\phi}$ therefore produces the conjugate phases

$$\phi_+=\frac{\theta}{\pi}, \qquad \phi_-=1-\frac{\theta}{\pi}\pmod1.$$

These phases encode the same probability because $\sin^2(\pi\phi_+)=\sin^2(\pi\phi_-)=a$. Replacing $Q$ by $-Q$ instead shifts both phases by $1/2$. For even $M$, the output distribution is translated by $M/2$ modulo $M$, and the decoded random estimate is complemented: $\widetilde a\mapsto1-\widetilde a$. On an exact-grid instance, the wrong representative therefore returns exactly $1-a$.

Standard QPE-Based Amplitude Estimation

Take $M=2^m$. Prepare the control register uniformly and the work register as $|\psi\rangle$:

$$\frac1{\sqrt M} \sum_{j=0}^{M-1}|j\rangle|\psi\rangle.$$

The controlled-power stage implements $|j\rangle|\xi\rangle\mapsto|j\rangle Q^j|\xi\rangle$. Substituting the eigenvector decomposition gives

$$\frac{-i}{\sqrt{2M}} \sum_{j=0}^{M-1}|j\rangle \left( e^{i(2j+1)\theta}|\psi_+\rangle - e^{-i(2j+1)\theta}|\psi_-\rangle \right).$$

Each orthogonal work-register branch carries the ordinary phase gradient for $\phi_+$ or $\phi_-$. Apply the inverse Fourier transform to the control register and measure

$$Y\in\{0,1,\ldots,M-1\}.$$

The amplitude-specific classical decoder is

$$\widetilde a = \sin^2\!\left(\frac{\pi Y}{M}\right).$$

The circuit is not a new derivation of general phase estimation: its special content is the equal conjugate-phase mixture and the nonlinear fold from phase to probability. The algorithm returns one random classical estimate after measurement. Retaining the control register coherently would require a new output and error contract.

Exact Output Law and the sin² Decoder

For a single eigenphase $\phi$, define the finite Fourier kernel

$$\begin{aligned} D_M(y;\phi) &= \frac1{M^2} \left| \sum_{j=0}^{M-1}e^{2\pi i j(\phi-y/M)} \right|^2 \\ &= \frac{ \sin^2\!\big(\pi M(\phi-y/M)\big) }{ M^2\sin^2\!\big(\pi(\phi-y/M)\big) }. \end{aligned}$$

When numerator and denominator vanish together, the value is the limiting value one. Unitarity of the inverse Fourier transform gives $\sum_yD_M(y;\phi)=1$.

The kernel follows directly from a finite geometric series. Its numerator measures the failure of the phase gradient to close after $M$ terms, while its denominator measures the separation between the true phase and the candidate grid point. This interpretation is useful but does not turn the distribution into a continuous density: $Y$ remains a discrete outcome, and the removable singularity must be assigned before numerical evaluation.

The two work-register eigenvectors are orthogonal. Tracing out that register therefore removes cross terms rather than adding amplitudes from the two branches. The exact measured law is

$$\Pr(Y=y) = \frac12 \left[ D_M\!\left(y;\frac\theta\pi\right) + D_M\!\left(y;1-\frac\theta\pi\right) \right].$$

The identities

$$D_M(y;1-\phi)=D_M(M-y;\phi)$$

and

$$\sin^2\!\left(\pi\frac{M-y}{M}\right) = \sin^2\!\left(\pi\frac yM\right)$$

show both the mirror symmetry of the distribution and why one decoder handles the two phases. Indices in the first identity are taken modulo $M$.

The factors $1/2$ are quantum overlap weights, not an extra classical coin inserted by the algorithm. A hypothetical preparation of one Grover eigenvector would give one kernel, but $\mathcal A|0\rangle$ has equal support on both. Conversely, adding the two kernel amplitudes before squaring would be wrong because their work-register labels are orthogonal.

If $M\phi$ is an integer, the corresponding branch occupies one exact bin. Off the grid, the Dirichlet-shaped kernel spreads over all bins. The nonlinear decoder then generally has finite-$M$ bias; no theorem below says that $\mathbb E[\widetilde a]=a$. The exact law, not an asymptotic normal approximation, is the appropriate object for checking small instances.

Precision, Confidence, and Endpoint Cases

The amplitude-estimation theorem of Brassard, Høyer, Mosca, and Tapp states that, for every positive integer $k$,

$$|\widetilde a-a| \le \frac{2\pi k\sqrt{a(1-a)}}{M} + \frac{\pi^2k^2}{M^2}$$

with probability at least $8/\pi^2$ for $k=1$, and with probability strictly greater than

$$1-\frac1{2(k-1)}$$

for integer $k\ge2$. Here $k$ enlarges the accepted phase window in one run; it is not a repetition count.

To connect phase and probability carefully, fold the measured phase into $[0,\pi/2]$:

$$\widetilde\theta = \pi\min\!\left\{\frac YM,1-\frac YM\right\}.$$

Then $\widetilde a=\sin^2\widetilde\theta$. On the circular phase-window event associated with either conjugate branch, $|\widetilde\theta-\theta|\le\Delta$. Taylor’s theorem applied to $f(x)=\sin^2x$, with $f'(\theta)=\sin2\theta$ and $|f''(x)|\le2$, gives

$$\begin{aligned} |\widetilde a-a| &\le |\sin2\theta|\,\Delta+\Delta^2 \\ &= 2\sqrt{a(1-a)}\,\Delta+\Delta^2. \end{aligned}$$

Taking $\Delta=\pi k/M$ produces the stated bound. Since $\sqrt{a(1-a)}\le1/2$, the uniform one-run error is at most $\pi/M+\pi^2/M^2$ for $k=1$, which establishes the fixed-confidence scale $M=\Theta(1/\epsilon)$.

The endpoints are exact only under their stated grid conditions. At $a=0$, $Q$ has phase zero on the prepared state, so $Y=0$ and $\widetilde a=0$ with certainty. At $a=1$, the phase is $1/2$; the decoder returns one with certainty when $M$ is even, including every primary power-of-two construction with $m\ge1$. For odd $M$, phase $1/2$ lies between bins and the endpoint is not exact.

To reach a chosen confidence, repeat an odd number $R$ of independent runs that each meet the same error target and return their median. With $p_0=8/\pi^2$,

$$\Pr(\text{median fails}) \le \exp\!\left[-2R\left(p_0-\frac12\right)^2\right].$$

Thus this elementary construction uses $O((1/\epsilon)\log(1/\delta))$ base iterates. It is rigorous, but it is not a claim that this confidence dependence is optimal among all variants.

Implementation error needs a compatible norm. Suppose the initial prepared state has vector-norm error at most $\eta_A$, every implemented controlled base iterate has operator-norm error at most $\eta_Q$, and the implemented inverse-QFT unitary has operator-norm error at most $\eta_F$. If $T=M-1$ iterates are used, telescoping and contractivity give the conservative premeasurement bound

$$\eta_A+T\eta_Q+\eta_F.$$

Measurement noise must be priced separately in a declared channel, trace-distance, or total-variation metric. The bound is a worst-case coherent budget, not a stochastic-noise model, and keeping it constant as $M$ grows requires the per-iterate error to decrease with $M$.

Query Scaling and the Classical Sampling Comparator

For a matched direct-sampling baseline, prepare and measure independent Bernoulli variables $X_i\in\{0,1\}$ with $\mathbb E X_i=a$. Hoeffding’s inequality gives

$$\Pr\!\left(|\overline X_n-a|\ge\epsilon\right) \le 2e^{-2n\epsilon^2},$$

so it is sufficient to take

$$n \ge \frac{\log(2/\delta)}{2\epsilon^2}.$$

This is a theorem about independent samples from the declared Bernoulli experiment. It is not a lower bound on every classical algorithm for a structured application. The coherent comparison grants stronger access and must charge for that access.

For the primary $M=2^m$ repeated-base construction, the exact component ledger is:

Resource	Count in one run
phase-register qubits	$m=\log_2M$
controlled-power blocks	$m$
repeated base $Q$ applications	$1+2+\cdots+2^{m-1}=M-1$
longest coherent power	$Q^{M/2}$
forward $\mathcal A$	$M$
inverse $\mathcal A^\dagger$	$M-1$
good reflection $S_G$	$M-1$
reference reflection $S_0$	$M-1$
inverse Fourier transforms	$1$
measurements and decoders	$1$ each

The forward count includes the initial preparation. The remaining $M-1$ forward calls and all inverse/reflection calls arise from the repeated iterate decompositions. If $Q^{2^j}$ is instead a primitive, report $m$ powered queries and the physical cost of those powers; do not also call them $M-1$ unit-cost primitive queries.

Total query count and maximum coherent depth answer different questions. The standard controlled-power stage preserves one coherent phase register through the longest $Q^{M/2}$ block, so the repeated-base realization has sequential oracle depth of order $M$ even though it contains only $m$ labeled power blocks. Shot-based variants may distribute some circuits across independent runs, but then pay in total calls and classical inference.

At fixed nontrivial success probability, Nayak and Wu’s Boolean-mean lower bound makes the worst-case $\Theta(1/\epsilon)$ quantum-query dependence optimal for families large enough to support the requested precision, for example $N=\Omega(1/\epsilon)$. A fixed finite $N$ saturates rather than supporting an arbitrarily small-$\epsilon$ asymptotic. This lower bound belongs to the Boolean-query regime, not to every encoding of a real-world expectation.

Query counts still omit two-qubit gates, ancillas, coherent depth, arithmetic, rotation synthesis, loading, uncomputation, repetitions, inference, routing, error correction, and physical spacetime. Those quantities decide whether the query advantage survives as an end-to-end advantage.

QFT-Free and Iterative Variants

The standard construction is primary because its finite distribution and error theorem are explicit. Several alternatives change the circuit and inference contract; “QFT-free” does not mean “access-free” or “proof-free.”

Regime	Data collected	Licensed conclusion
Maximum-likelihood AE	Good/bad shots after selected $Q^r\mathcal A	0\rangle$, with probability$\sin^2((2r+1)\theta)$
Iterative AE	Adaptive powers and confidence intervals	Grinko et al. prove an additive interval guarantee without QPE. Under their theorem’s conditions, the midpoint has error at most $\epsilon$ with confidence $1-\alpha$, and the number of $Q$ applications obeys $N_{\rm oracle}<50\epsilon^{-1}\log[(2/\alpha)\log_2(\pi/(4\epsilon))]$.
Rigorous Grover-only estimation	Adaptive measurements of uncontrolled Grover iterates	Aaronson and Rall prove that the QFT is unnecessary for optimal approximate-counting scaling and give a rigorous amplitude-estimation extension. Their access and relative-error conventions must accompany the result.
Low-depth AE	Many shorter circuits whose largest sequential oracle depth is bounded	Giurgica-Tiron et al. establish total-query/depth tradeoffs. Their power-law result assumes the regularity needed for a Bernstein–von Mises theorem; their QoPrime construction has a separate fully rigorous proof for its discrete tradeoff family.

Maximum-likelihood inference can be valuable, but an asymptotic Cramér–Rao or Fisher-information lower bound on variance is not a correctness upper bound. Tanaka et al. analyze maximum-likelihood schedules under a specified noise model; those model-dependent and numerical results should not be promoted to unconditional hardware guarantees. Likewise, observed slopes from a finite simulation do not establish the asymptotic theorem for a new schedule.

All these methods still require coherent preparation, inverse access through the Grover iterate, success and reference reflections, long powers or an adaptive sequence of powers, measurements, and classical inference. Their resource currencies differ, so comparisons should report total calls and largest sequential depth separately.

Expectation Values, Applications, and Ownership Limits

A bounded expectation becomes an amplitude only through a reversible encoder. For a distribution $p_x$ and a real function $f(x)\in[0,1]$, a licensed preparation can have the form

$$\mathcal A|0\rangle = \sum_x\sqrt{p_x}\,|x\rangle \left( \sqrt{1-f(x)}\,|0\rangle + \sqrt{f(x)}\,|1\rangle \right),$$

with any work registers coherently cleaned or explicitly retained. Declaring the flag-one subspace good gives

$$a = \sum_xp_xf(x) = \mathbb E[f(X)].$$

For $f\in[L,U]$ with $L<U$, encode

$$g(x)=\frac{f(x)-L}{U-L}\in[0,1]$$

and multiply the final additive error by $U-L$. If $L=U$, the expectation is already known. This rescaling covers signed real functions. Complex functions or non-diagonal observables need an additional explicit reduction, such as separate real and imaginary tests; the word “expectation” alone supplies no circuit.

The ledger must include state preparation for $p_x$, reversible evaluation of $f$, finite-precision arithmetic, the controlled rotation, garbage cleanup, and every induced bias. An efficiently indexed classical table does not automatically have an efficient coherent loader and inverse. Montanaro’s quantum Monte Carlo results give rigorous query improvements under their access assumptions, whereas Herbert exhibits a state-preparation setting in which loading costs remove the advertised speedup. These are compatible statements because they analyze different complete interfaces.

Approximate counting is the specialization in which $f$ marks $t$ of $N$ uniform inputs. Then $a=t/N$ and $\widetilde t=N\widetilde a$ satisfies, at constant confidence,

$$|\widetilde t-t| \le \frac{2\pi\sqrt{t(N-t)}}{M} + \frac{\pi^2N}{M^2}.$$

For $t>0$, a relative-error scale

$$O\!\left( \frac1{\epsilon_{\rm rel}}\sqrt{\frac Nt} \right)$$

requires a rough scale or an adaptive counting protocol; an algorithm cannot insert the unknown $t$ into its own stopping rule. Grover Search retains marked-item recovery, while this page estimates the marked fraction.

Fixed-point amplification is also a different output problem: it monotonically raises success under a lower-bound promise rather than numerically estimating $a$. General phase estimation retains the single-eigenphase kernel, and the Mathematical Toolkit expectation-value page retains the classical probability formalism. Applications in finance, materials, normalization estimation, or risk analysis are licensed only after their encoders, comparators, depth, and total costs are supplied.

Two Reproducible Finite Audits

These audits are exact theorem checks, not random experiments or hardware evidence. The first isolates phase folding and the controlled-sign convention; the second displays an inexact-grid distribution and finite bias.

Exact-grid phase folding and controlled-sign audit

Take

$$\theta=\frac\pi8, \qquad a=\sin^2\frac\pi8=\frac{2-\sqrt2}{4}, \qquad M=8.$$

The iterate is

$$Q = \frac1{\sqrt2} \begin{pmatrix} 1&1\\ -1&1 \end{pmatrix}.$$

Its phases $1/8$ and $7/8$ are exactly on the grid, so

$y$	$\Pr(Y=y)$	$\widetilde a$
$1$	$1/2$	$(2-\sqrt2)/4$
$7$	$1/2$	$(2-\sqrt2)/4$

If the controlled circuit implements $-Q$, the phases become $5/8$ and $3/8$. The exact outcomes $5$ and $3$ decode to

$$\sin^2\frac{5\pi}{8} = \sin^2\frac{3\pi}{8} = \frac{2+\sqrt2}{4} = 1-a.$$

The audit record is:

1. Problem family and size. This is one two-eigenphase instance with an eight-point Fourier grid and a three-qubit phase register.
2. Promise and instance. The known audit value is $a=(2-\sqrt2)/4$, strictly between the endpoints, with exact-grid phase $\theta/\pi=1/8$.
3. Access and encoding. Exact $\mathcal A$, $\mathcal A^\dagger$, both reflections, the representative $Q$, controlled repeated powers, and an ideal inverse Fourier transform are licensed.
4. Output and use. The output is the classical folded estimate from one three-bit measurement; no good witness is requested.
5. Success and error. Correct access returns $a$ with certainty. Replacing $Q$ by $-Q$ returns $1-a$ with certainty, exposing a controlled-sign error rather than statistical uncertainty.
6. Algorithmic idea. Equal orthogonal eigenbranches occupy bins one and seven, which the $\sin^2$ decoder folds to the same probability.
7. Executable procedure. Prepare, apply controlled powers $Q,Q^2,Q^4$, inverse-transform, measure, and decode; repeat symbolically with $-Q$.
8. Resource ledger. There are three controlled-power blocks, seven base iterates, longest power $Q^4$, eight forward preparations, seven inverses, seven of each reflection, one inverse transform, one measurement, and one decoder.
9. Classical comparator. No sampling comparator is inferred from this exact-grid identity; it audits the coherent convention and component count.
10. Evidence and limits. Exact arithmetic verifies phases, probabilities, decoded quadratic numbers, sign complement, and ledger. It does not test approximate synthesis, noise, or asymptotic performance.

Rational inexact-grid kernel and finite bias

Now take

$$\theta=\frac\pi6, \qquad a=\frac14, \qquad M=4.$$

Substitution into the two-kernel law gives

$y$	$\Pr(Y=y)$	$\widetilde a$
$0$	$3/16$	$0$
$1$	$3/8$	$1/2$
$2$	$1/16$	$1$
$3$	$3/8$	$1/2$

The probabilities sum to one, but the decoded mean is

$$\mathbb E[\widetilde a] = \frac38\frac12 + \frac1{16} + \frac38\frac12 = \frac7{16} \ne \frac14.$$

The audit-specific decoded-error event $Y\in\{0,1,3\}$ has probability $15/16$, and every outcome in it obeys $|\widetilde a-a|\le1/4$. This is not the latent branch-conditioned $k=1$ phase-window event and does not replace the general Brassard–Høyer–Mosca–Tapp radius.

The audit record is:

1. Problem family and size. This is one inexact-grid instance with two conjugate kernels, four outcomes, and a two-qubit phase register.
2. Promise and instance. The checked value is $a=1/4$ with $\theta/\pi=1/6$, which is not a multiple of $1/4$.
3. Access and encoding. The same ideal standard interface is licensed, with powers $Q$ and $Q^2$ compiled from repeated controlled base iterates.
4. Output and use. One measurement returns $Y$, which is mapped to the classical estimate $0$, $1/2$, or $1$.
5. Success and error. The exact output law is $(3/16,3/8,1/16,3/8)$; the stated decoded-error event has probability $15/16$, and the estimator mean is $7/16$.
6. Algorithmic idea. The two mirrored finite kernels are mixed because their work-register eigenvectors are orthogonal, then folded by one decoder.
7. Executable procedure. Evaluate both exact kernels, average them, decode each bin, sum the expectation and event probability, and audit the repeated-base counts.
8. Resource ledger. There are two controlled-power blocks, three base iterates, longest power $Q^2$, four forward preparations, three inverses, three of each reflection, one inverse transform, one measurement, and one decoder.
9. Classical comparator. The finite table checks no asymptotic speedup; a sampling comparison requires the same accuracy, confidence, and encoded Bernoulli quantity.
10. Evidence and limits. Exact rational arithmetic verifies normalization, bias, the decoded-error event, and every count. It does not prove the general theorem or model implementation error.

One deterministic program reproduces both audits:

const assert = (condition, label) => {
  if (!condition) throw new Error(label);
};

const gcd = (a, b) => b === 0n ? (a < 0n ? -a : a) : gcd(b, a % b);
const rational = (n, d = 1n) => {
  const sign = d < 0n ? -1n : 1n;
  const divisor = gcd(n, d);
  return [sign * n / divisor, sign * d / divisor];
};
const addR = ([an, ad], [bn, bd]) => rational(an * bd + bn * ad, ad * bd);
const subR = ([an, ad], [bn, bd]) => rational(an * bd - bn * ad, ad * bd);
const mulR = ([an, ad], [bn, bd]) => rational(an * bn, ad * bd);
const equalR = ([an, ad], [bn, bd]) => an * bd === bn * ad;
const absR = ([n, d]) => [n < 0n ? -n : n, d];
const lessEqualR = ([an, ad], [bn, bd]) => an * bd <= bn * ad;

// Exact u + v sqrt(2), stored as (u + v sqrt(2)) / d.
const quad = (u, v, d = 1n) => ({ u, v, d });
const addQ = (x, y) => quad(
  x.u * y.d + y.u * x.d,
  x.v * y.d + y.v * x.d,
  x.d * y.d,
);
const mulQ = (x, y) => quad(
  x.u * y.u + 2n * x.v * y.v,
  x.u * y.v + x.v * y.u,
  x.d * y.d,
);
const negQ = (x) => quad(-x.u, -x.v, x.d);
const equalQ = (x, y) =>
  x.u * y.d === y.u * x.d && x.v * y.d === y.v * x.d;

// Audit 1: exact grid and the controlled-sign complement.
const aExact = quad(2n, -1n, 4n);
const aComplement = quad(2n, 1n, 4n);
assert(equalQ(addQ(aExact, aComplement), quad(1n, 0n)), 'a + complement');
const sineCosine = quad(0n, 1n, 2n);
assert(equalQ(
  addQ(mulQ(sineCosine, sineCosine), mulQ(sineCosine, sineCosine)),
  quad(1n, 0n),
), 'Q column norm');
assert(equalQ(
  addQ(mulQ(sineCosine, sineCosine),
    mulQ(negQ(sineCosine), sineCosine)),
  quad(0n, 0n),
), 'Q column orthogonality');
assert(equalQ(
  addQ(mulQ(sineCosine, sineCosine), mulQ(sineCosine, sineCosine)),
  quad(1n, 0n),
), 'Q determinant');

const exactPhases = [1n, 7n];
const cosinePiYOver4 = [
  quad(1n, 0n), quad(0n, 1n, 2n), quad(0n, 0n), quad(0n, -1n, 2n),
  quad(-1n, 0n), quad(0n, -1n, 2n), quad(0n, 0n), quad(0n, 1n, 2n),
];
const decoder8 = cosinePiYOver4.map((cosine) =>
  quad(cosine.d - cosine.u, -cosine.v, 2n * cosine.d));
const distributionFromExactBins = (size, bins) => {
  const distribution = Array.from({ length: size }, () => [0n, 1n]);
  bins.forEach((bin) => {
    distribution[Number(bin)] = addR(distribution[Number(bin)], [1n, 2n]);
  });
  return distribution;
};
const exactDistribution = distributionFromExactBins(8, exactPhases);
const expectedExactDistribution = [
  [0n, 1n], [1n, 2n], [0n, 1n], [0n, 1n],
  [0n, 1n], [0n, 1n], [0n, 1n], [1n, 2n],
];
assert(exactPhases.every((phase) => phase >= 0n && phase < 8n), 'exact bins');
assert(exactDistribution.every((p, y) => equalR(p, expectedExactDistribution[y])),
  'audit 1 distribution');
assert(equalR(exactDistribution.reduce(addR, [0n, 1n]), [1n, 1n]),
  'audit 1 normalization');
assert(exactPhases.every((phase) => equalQ(decoder8[Number(phase)], aExact)),
  'bins 1 and 7 decode a');

const wrongPhases = exactPhases.map((phase) => (phase + 4n) % 8n);
assert(wrongPhases[0] === 5n && wrongPhases[1] === 3n, 'phase shift modulo M');
const wrongDistribution = distributionFromExactBins(8, wrongPhases);
assert(equalR(wrongDistribution[3], [1n, 2n]) &&
  equalR(wrongDistribution[5], [1n, 2n]), 'wrong-sign distribution');
assert(equalR(wrongDistribution.reduce(addR, [0n, 1n]), [1n, 1n]),
  'wrong-sign normalization');
assert(wrongPhases.every((phase) =>
  equalQ(decoder8[Number(phase)], aComplement)),
  'bins 5 and 3 decode one minus a');
assert(!equalQ(aExact, aComplement), 'controlled-sign failure is visible');

const ledger8 = {
  powerBlocks: 3n, baseQ: 7n, longestPower: 4n,
  forwardA: 8n, inverseA: 7n, goodReflection: 7n,
  referenceReflection: 7n, inverseQft: 1n, measurement: 1n, decoder: 1n,
};
assert(ledger8.powerBlocks === 3n && ledger8.baseQ === 7n, 'M=8 powers');
assert(ledger8.longestPower === 4n, 'M=8 longest power');
assert(ledger8.forwardA === 8n && ledger8.inverseA === 7n, 'M=8 preparations');
assert(ledger8.goodReflection === 7n && ledger8.referenceReflection === 7n,
  'M=8 reflections');
assert(ledger8.inverseQft === 1n && ledger8.measurement === 1n &&
  ledger8.decoder === 1n, 'M=8 terminal ledger');

// Audit 2: exact rational inexact-grid law and finite bias.
const cosinePhase = [[1n, 2n], [-1n, 2n], [-1n, 1n]];
const quarterTurnCosines = [1n, 0n, -1n, 0n];
const probabilities = Array.from({ length: 4 }, (_, y) => {
  let numerator = [4n, 1n];
  for (let d = 1; d < 4; d += 1) {
    const gridCosine = quarterTurnCosines[(d * y) % 4];
    const coefficient = [2n * BigInt(4 - d) * gridCosine, 1n];
    numerator = addR(numerator, mulR(coefficient, cosinePhase[d - 1]));
  }
  return mulR(numerator, [1n, 16n]);
});
const cosineDoubleAngle = [1n, 0n, -1n, 0n];
const estimates = cosineDoubleAngle.map((cosine) => rational(1n - cosine, 2n));
const expectedEstimates = [[0n, 1n], [1n, 2n], [1n, 1n], [1n, 2n]];
const expectedProbabilities = [[3n, 16n], [3n, 8n], [1n, 16n], [3n, 8n]];
probabilities.forEach((p, y) => {
  assert(equalR(p, expectedProbabilities[y]), `audit 2 probability y=${y}`);
});
assert(equalR(probabilities.reduce(addR, [0n, 1n]), [1n, 1n]),
  'audit 2 normalization');
assert(estimates.every((value, y) => equalR(value, expectedEstimates[y])),
  'audit 2 decoded values');
const expectation = probabilities.reduce(
  (sum, p, y) => addR(sum, mulR(p, estimates[y])), [0n, 1n],
);
assert(equalR(expectation, [7n, 16n]), 'finite expectation');
const eventProbability = [0, 1, 3].reduce(
  (sum, y) => addR(sum, probabilities[y]), [0n, 1n],
);
assert(equalR(eventProbability, [15n, 16n]), 'decoded-error event');
assert([0, 1, 3].every((y) =>
  lessEqualR(absR(subR(estimates[y], [1n, 4n])), [1n, 4n])),
  'decoded-error tolerance');

const ledger4 = {
  powerBlocks: 2n, baseQ: 3n, longestPower: 2n,
  forwardA: 4n, inverseA: 3n, goodReflection: 3n,
  referenceReflection: 3n, inverseQft: 1n, measurement: 1n, decoder: 1n,
};
assert(ledger4.powerBlocks === 2n && ledger4.baseQ === 3n, 'M=4 powers');
assert(ledger4.longestPower === 2n, 'M=4 longest power');
assert(ledger4.forwardA === 4n && ledger4.inverseA === 3n, 'M=4 preparations');
assert(ledger4.goodReflection === 3n && ledger4.referenceReflection === 3n,
  'M=4 reflections');
assert(ledger4.inverseQft === 1n && ledger4.measurement === 1n &&
  ledger4.decoder === 1n, 'M=4 terminal ledger');

console.log('exact amplitude-estimation audits: PASS');

Common Amplitude-Estimation Failures

Starting from samples instead of coherent access. Classical samples do not supply an invertible unitary, reflections, or controlled powers. State the actual coherent interface before invoking the algorithm.

Dropping the leading minus sign. A global phase of an uncontrolled iterate becomes relative under control. For even $M$, this error complements the decoded estimate rather than leaving it unchanged.

Treating powered access as free. Standard QPE has $m$ controlled-power blocks but $M-1$ repeated base iterates. Quote the currency actually licensed.

Keeping only one eigenphase branch. The prepared state is not a Grover eigenstate. The output law is an equal mixture of conjugate kernels, not one kernel with coherent cross terms.

Calling the estimator unbiased. Exact-grid instances are unbiased because they are exact. Off the grid, nonlinear folding can produce finite bias, as the second audit shows.

Calling $k$ a repetition count. In the BHMT theorem, $k$ is a one-run phase-window parameter. Independent median repetitions use the separate symbol $R$ and a separate tail bound.

Confusing estimation with amplification. Fixed-point schedules increase success probability; they do not return a numerical confidence interval for $a$.

Using queries as runtime. Loading, reversible arithmetic, controlled compilation, maximum coherent depth, inference, noise tolerance, and physical resources remain outside a bare query count.

Exercises

1. Derive the eigenphases and folded decoder

Starting from the matrix for $Q$, derive its two normalized eigenvectors, decompose $|\psi\rangle$ into them, identify the phases $\theta/\pi$ and $1-\theta/\pi$, and prove that one $\sin^2$ decoder handles both branches.

Solution

For $c=\cos2\theta$ and $s=\sin2\theta$,

$$\begin{pmatrix}c&s\\-s&c\end{pmatrix} \begin{pmatrix}1\\ \pm i\end{pmatrix} = e^{\pm2i\theta} \begin{pmatrix}1\\ \pm i\end{pmatrix}.$$

Normalization gives $|\psi_\pm\rangle=(|G\rangle\pm i|B\rangle)/\sqrt2$. Solving for the real basis vectors and inserting $|\psi\rangle=\sin\theta|G\rangle+\cos\theta|B\rangle$ gives

$$|\psi\rangle = \frac{-i}{\sqrt2} \left(e^{i\theta}|\psi_+\rangle-e^{-i\theta}|\psi_-\rangle\right).$$

Thus each eigenbranch has weight $1/2$, with phases $\phi_+=\theta/\pi$ and $\phi_-=1-\theta/\pi$ modulo one. If outcomes near the branches are $y$ and $M-y$, then

$$\sin^2\!\left(\frac{\pi(M-y)}M\right) = \sin^2\!\left(\frac{\pi y}M\right),$$

so the decoder is branch-independent.

2. Derive the exact two-kernel law and endpoints

Derive the mixture distribution, prove mirror symmetry, and analyze $a=0$ and $a=1$ for even and odd $M$.

Solution

Conditioned on an eigenphase $\phi$, inverse-Fourier measurement has law $D_M(y;\phi)$. The work-register eigenstates are orthogonal, so tracing them out yields

$$\Pr(Y=y) = \frac12\left[D_M(y;\theta/\pi)+D_M(y;1-\theta/\pi)\right].$$

Replacing $y$ by $M-y$ interchanges the two kernels, proving mirror symmetry with indices modulo $M$. At $a=0$, the prepared state has eigenphase zero and the only outcome is $Y=0$, so the estimate is zero. At $a=1$, the phase is $1/2$. If $M$ is even, the exact bin is $M/2$ and the decoder returns one. If $M$ is odd, $M/2$ is not an integer; the finite kernel spreads over bins and the estimate is not deterministically one. The equal-mixture formula itself was derived for $0<a<1$; the endpoints follow directly from their one-dimensional prepared subspaces.

3. Reproduce the exact-grid sign audit

For $M=8$ and $\theta=\pi/8$, reproduce both correct outcomes and show why omitting the controlled leading minus sign returns $1-a$.

Solution

The two phases are $1/8$ and $7/8$, both grid points. QPE therefore returns $1$ or $7$ with branch weights $1/2$. In either case,

$$\widetilde a = \sin^2\frac\pi8 = \frac{2-\sqrt2}{4}.$$

Using $-Q$ shifts each phase by $1/2$. Hence the bins become $1+4=5$ and $7+4=3\pmod8$. They decode as

$$\sin^2\frac{5\pi}{8} = \sin^2\frac{3\pi}{8} = \cos^2\frac\pi8 = 1-a.$$

The failure is deterministic here because every phase is exactly representable. Three power blocks $Q,Q^2,Q^4$ contain seven base iterates and have longest coherent power $Q^4$.

4. Reproduce the rational finite-bias audit

For $a=1/4$ and $M=4$, verify the complete distribution, expectation, decoded-error event, and component ledger.

Solution

Here $\theta/\pi=1/6$. Substitution in the two Dirichlet kernels gives

$$(p_0,p_1,p_2,p_3) = \left(\frac3{16},\frac38,\frac1{16},\frac38\right).$$

The decoder gives $(0,1/2,1,1/2)$, so

$$\mathbb E[\widetilde a] = \frac38\frac12+\frac1{16}+\frac38\frac12 = \frac7{16}.$$

Outcomes $0,1,3$ each lie within $1/4$ of $a=1/4$, and their total probability is $3/16+3/8+3/8=15/16$. The powers $Q$ and $Q^2$ use three base iterates, so the complete counts are four forward preparations; three inverse preparations; three calls to each reflection; longest power $Q^2$; and one inverse transform, two-bit measurement, and decoder.

5. Derive the repeated-base and error ledgers

For $M=2^m$, derive every repeated-base component count and then prove the conservative coherent implementation-error bound.

Solution

The controlled powers have exponents $1,2,\ldots,2^{m-1}$, so their sum is

$$\sum_{j=0}^{m-1}2^j=M-1,$$

and the largest block is $Q^{M/2}$. Each base $Q$ contains one forward preparation, one inverse, and both reflections. Adding the initial preparation gives $M$ forward calls and $M-1$ of each other component.

Let the initial state error be at most $\eta_A$ in vector norm. Replace ideal controlled iterates one at a time; unitarity and the operator-norm bound $\eta_Q$ make each replacement contribute at most $\eta_Q$. Replacing the inverse QFT contributes at most $\eta_F$. The triangle inequality gives

$$\left\|\,|\widetilde\Psi\rangle-|\Psi\rangle\,\right\| \le \eta_A+(M-1)\eta_Q+\eta_F.$$

This is premeasurement coherent error. A noisy measurement needs a compatible channel or outcome-distribution metric rather than an unnamed term added to the vector norm.

6. Derive precision, confidence, and the matched baseline

Derive the probability-error inequality, its worst-case query scale, the median confidence boost, and the direct-sampling Hoeffding comparator.

Solution

For $h=\widetilde\theta-\theta$, Taylor’s theorem and $|d^2(\sin^2x)/dx^2|\le2$ give

$$|\sin^2(\theta+h)-\sin^2\theta| \le 2\sqrt{a(1-a)}|h|+h^2.$$

The $k=1$ phase event has $|h|\le\pi/M$ with probability at least $p_0=8/\pi^2$. Since $\sqrt{a(1-a)}\le1/2$, choosing $M=\Theta(1/\epsilon)$ gives uniform additive error $\epsilon$ at this fixed confidence. For odd $R$ independent runs, Hoeffding applied to their success indicators yields

$$\Pr(\text{median fails}) \le e^{-2R(p_0-1/2)^2},$$

so $R=O(\log(1/\delta))$ suffices. Direct Bernoulli sampling instead obeys $\Pr(|\bar X-a|\ge\epsilon)\le2e^{-2n\epsilon^2}$, requiring $n\ge\log(2/\delta)/(2\epsilon^2)$. The comparison concerns matched access to the same encoded quantity; it is not yet a total-runtime theorem.

7. Separate the amplitude-estimation variants

For each of standard QPE-based AE, maximum-likelihood AE, iterative AE, rigorous Grover-only estimation, and low-depth AE, state what is measured and what kind of guarantee is justified.

Solution

Standard AE coherently superposes controlled powers, inverse-Fourier measures the phase register, and has the exact two-kernel BHMT bound. Maximum-likelihood AE measures good/bad outcomes after selected uncontrolled powers and fits $\sin^2((2r+1)\theta)$; Fisher information and observed scaling do not alone give a finite correctness upper bound. Iterative AE adaptively chooses powers and updates confidence intervals; the Grinko theorem supplies an explicit additive-error, failure-probability, and query bound.

Aaronson–Rall-type Grover-only methods prove that optimal query scaling does not require a QFT, but their own access, adaptivity, and error conventions must be retained. Low-depth methods trade total calls against maximum sequential depth. Power-law guarantees need stated statistical regularity, while the QoPrime family has a separate rigorous proof. A noise-model likelihood study is evidence about that model, not an unconditional hardware theorem.

8. Repair an expectation-value speedup claim

Repair the claim: “Amplitude estimation always computes any expectation value quadratically faster.” Include loading, reversible arithmetic, a matched comparator, total cost, and evidence limitations.

Solution

A defensible replacement is the following complete record.

1. Problem family and size. Consider a declared family of distributions $p_x$ and bounded real functions $f_x$, with input size and target additive accuracy specified.
2. Promise and instance. Give finite bounds $L<U$, the requested $\epsilon,\delta$, and any promise controlling loading, arithmetic error, or the expectation’s scale.
3. Access and encoding. License coherent preparation of $p_x$, reversible evaluation and rescaling of $f_x$, the flag rotation, cleanup, inverse preparation, both reflections, and controlled or variant-specific powers.
4. Output and use. Return a classical estimate of $\mathbb E[f]=(U-L)a+L$ with its additive interval and intended downstream use; do not claim a witness or a coherent exact value.
5. Success and error. Combine statistical failure, finite-precision bias, coherent implementation error, and endpoint conditions in compatible metrics.
6. Algorithmic idea. Encode the rescaled expectation as a flag-one probability and estimate the conjugate Grover angle using the named standard, iterative, likelihood, or low-depth procedure.
7. Executable procedure. Load, evaluate, rotate, clean, apply the declared powers, measure, infer, rescale, and repeat or adapt until the stated stopping rule is met.
8. Resource ledger. Count preparation and inverse calls, reflections, oracle depth, loader and arithmetic gates, qubits, synthesis, measurements, inference, error correction, and physical time—not queries alone.
9. Classical comparator. Compare with the best relevant classical method under the same data access, output accuracy, confidence, preprocessing, and hardware-cost currency; direct sampling is only one possible comparator.
10. Evidence and limits. The ideal query theorem gives an $O(1/\epsilon)$ versus direct-sampling $O(1/\epsilon^2)$ accuracy dependence under coherent access. It does not prove that loading is efficient, that total runtime is quadratically smaller, or that a finite simulation or noise-model fit establishes practical advantage.

References

• S. Aaronson and P. Rall, “Quantum Approximate Counting, Simplified,” Proceedings of the 3rd Symposium on Simplicity in Algorithms, 24–32 (2020), doi:10.1137/1.9781611976014.5.
• G. Brassard, P. Høyer, M. Mosca, and A. Tapp, “Quantum Amplitude Amplification and Estimation,” Contemporary Mathematics 305, 53–74 (2002), doi:10.1090/conm/305/05215.
• T. Giurgica-Tiron, I. Kerenidis, F. Labib, A. Prakash, and W. Zeng, “Low Depth Algorithms for Quantum Amplitude Estimation,” Quantum 6, 745 (2022), doi:10.22331/q-2022-06-27-745.
• D. Grinko, J. Gacon, C. Zoufal, and S. Woerner, “Iterative Quantum Amplitude Estimation,” npj Quantum Information 7, 52 (2021), doi:10.1038/s41534-021-00379-1.
• S. Herbert, “No Quantum Speedup with Grover–Rudolph State Preparation for Quantum Monte Carlo Integration,” Physical Review E 103, 063302 (2021), doi:10.1103/PhysRevE.103.063302.
• W. Hoeffding, “Probability Inequalities for Sums of Bounded Random Variables,” Journal of the American Statistical Association 58, 13–30 (1963), doi:10.1080/01621459.1963.10500830.
• A. Montanaro, “Quantum Speedup of Monte Carlo Methods,” Proceedings of the Royal Society A 471, 20150301 (2015), doi:10.1098/rspa.2015.0301.
• A. Nayak and F. Wu, “The Quantum Query Complexity of Approximating the Median and Related Statistics,” in Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 384–393 (1999), doi:10.1145/301250.301349.
• Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera, and N. Yamamoto, “Amplitude Estimation without Phase Estimation,” Quantum Information Processing 19, 75 (2020), doi:10.1007/s11128-019-2565-2.
• T. Tanaka, Y. Suzuki, S. Uno, R. Raymond, T. Onodera, and N. Yamamoto, “Amplitude Estimation via Maximum Likelihood on Noisy Quantum Computer,” Quantum Information Processing 20, 293 (2021), doi:10.1007/s11128-021-03215-9.