Amplitude Estimation¶

Category C3 · Module oracq.algorithms.common.estimation · Stage V2

Overview¶

Estimates the good-subspace probability of a state preparation \(A\): given a marked set \(M\subset\{0,1\}^n\), \(a=\sum_{i\in M}|\langle i|A|0\rangle|^2\). Implementation basis: the amplitude amplification/estimation framework of Brassard et al. (arXiv:quant-ph/0005055; see also the Implementation basis section of the algorithm catalog): run phase estimation on the Grover iteration operator

\[ Q = A\,(2|0\rangle\langle 0|-I)\,A^\dagger\, S_{\mathrm{good}} \]

The eigenvalues of \(Q\) are \(e^{\pm 2i\theta}\), with \(\sin^2\theta = a\); after reading out the phase-grid value \(y\), decode as \(\hat a=\sin^2(\pi y/2^p)\). The query complexity is \(O(1/\varepsilon)\), a quadratic improvement over the \(O(1/\varepsilon^2)\) of classical Monte Carlo.

Interface and input model¶

amplitude_estimation(preparation, marked, *, precision=3)
amplitude_from_phase(value, precision)

API entry points: amplitude_estimation, amplitude_from_phase

preparation: a state preparation (SP) with zero input and a workspace uncomputed back to zero, which must support adjoint and controlled calls — the contract is checked at generation time via checked_state_preparation(adjoint=True, controlled=True).
marked: the set of integer indices of the good states in the target space.
precision: the number of phase-register bits, range 1..63.

Returns an Operation with registers target, work, and phase. Module attributes:

Attribute	Meaning
`algorithm`	`"amplitude_estimation"`
`readout_register`	`"phase"`
`decoder`	`"sin(piphase/2precision)*2"`

After reading out phase, call amplitude_from_phase(value, precision) to decode: it returns \(\sin^2(\pi\cdot\text{value}/2^p)\in[0,1]\), with value ranging over \(0..2^p-1\).

Implementation notes¶

The generation chain is preparation → phase_estimation(grover_iterate(preparation, marked)): the Grover iteration is assembled by search.py’s grover_iterate (marks come from the phase oracle generated by phase_marks, see Grover search); for phase estimation see quantum phase estimation.

Mirror symmetry: the eigenphases \(+2\theta\) and \(-2\theta\) correspond to the grid points \(y\) and \(2^p-y\), which decode to the same value — the phase readout itself does not distinguish them. A finite-precision readout may correspond to several approximate probabilities; sampling and statistical post-processing (including confidence intervals) are the host’s responsibility, which is the docstring’s explicit stance.

The integration module (Heinrich summation/integration in integration.py) uses this entry point as its readout core: a comparator construction makes the good-state probability exactly \(E[v]/2^w\), followed by standard amplitude estimation.

Validation approach¶

Category C3 (acceptance criterion in docs/development/validation-plan.md §2). The three layers of evidence match the estimation.py row of docs/development/validation-coverage.md:

Structure: construction and attribute assertions in tests/core/test_algorithm_expansion.py:AlgorithmExpansionTests; violations of the preparation’s zero-input / clean-uncomputation / adjoint / controlled contracts raise at generation time.
Numerical: AlgorithmExpansionTests.test_amplitude_estimation_half_probability — marking (1,) on uniform_state(1) (\(a=1/2\) lands exactly on the grid): the phase distribution puts all mass on the two points 2 and 6 (\(p(2)+p(6)=1\), places=10), and both amplitude_from_phase(2, 3) and amplitude_from_phase(6, 3) are exactly 0.5.
Binding: the module row registers “—“.

The witness technique is exact state-vector simulation taking the phase marginal distribution, cross-checked pointwise against the closed form (no sampling assertions).

Known gaps and planned stages¶

Consistent with docs/development/validation-coverage.md: the QAE confidence-interval claim is unwitnessed — the existing witness verifies only the point estimate (the grid-exact case \(a=1/2\)). validation-plan §2 lists “the estimate falls inside the theoretical confidence interval” as the standard witness technique for the QAE class; the error distribution of finite-precision phase readout and its cross-check against confidence intervals has not yet landed. The estimation.py module is therefore at stage V2; once the gap is filled, the coverage matrix must be synchronized.

Numerical validation¶

tests/verification/verify_estimation.py performs distribution-level numerical validation of this interface on a real backend (7 QAE cases in total, all passing). Experiment design:

Instances: uniform preparation with uniform_state (\(a=1/2\) lands exactly on the decoding grid; \(a=3/8\) does not) and non-uniform preparation with gate_state_prep (\(a=0.3\)), precision \(p=3..6\).
Classical reference: the phase distribution is compared against the Grover bimodal closed form \(P(y)=\tfrac12 D(y/2^p-\theta/\pi)+\tfrac12 D(y/2^p+\theta/\pi)\) (\(D\) the Dirichlet kernel, \(\sin^2\theta=a\), derived independently); the peak decoding error is compared against the Brassard bound \(|\hat a-a|\le 2\pi\sqrt{a(1-a)}/2^p+\pi^2/4^p\).
Backend paths: reference, rir-pysparq, adapter-pysparq, originir-ext; each path takes the phase marginal independently, and the paths are cross-checked pairwise.

Case	Scale	Paths	Metric values
\(a=1/2\) (grid-exact)	\(p=3,4,5\)	all four	bimodal peaks \(y=2^{p-2}\) and \(2^p-2^{p-2}\) each carry \(1/2\); decode_error \(=1.1\times10^{-16}\); max TVD \(\le 3.3\times10^{-15}\)
\(a=3/8\) (off-grid)	\(p=4,5,6\)	all four	decode_error \(=0.0663/0.0275/0.0201\), Brassard bound \(0.2287/0.1047/0.0499\); max TVD \(\le 1.9\times10^{-14}\)
\(a=0.3\) (non-uniform preparation)	\(p=5\)	all four	decode_error \(=0.00866\), bound \(0.0996\); peak probability \(0.4851\); max TVD \(=1.2\times10^{-15}\)

Reproduction command:

PYTHONPATH=src /home/agony/projects/qcfd-dev/quantum-cfd-software/.venv/bin/python tests/verification/verify_estimation.py

Artifact path: out/verification/estimation.json (case names prefixed qae-).