# Amplitude Estimation
**English** · 简体中文
> Category C3 · Module [`oracq.algorithms.common.estimation`](../../api/algorithms/common/estimation.rst) · 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](https://arxiv.org/abs/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
```python
amplitude_estimation(preparation, marked, *, precision=3)
amplitude_from_phase(value, precision)
```
API entry points: {obj}`amplitude_estimation `, {obj}`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 {obj}`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 {obj}`Operation ` with registers `target`, `work`, and `phase`. Module attributes:
| Attribute | Meaning |
|---|---|
| `algorithm` | `"amplitude_estimation"` |
| `readout_register` | `"phase"` |
| `decoder` | `"sin(pi*phase/2**precision)**2"` |
After reading out `phase`, call {obj}`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 → {obj}`phase_estimation(grover_iterate(preparation, marked)) `: the Grover iteration is assembled by `search.py`'s {obj}`grover_iterate ` (marks come from the phase oracle generated by {obj}`phase_marks `, see [Grover search](grover.md)); for phase estimation see [quantum phase estimation](qpe.md).
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 {obj}`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.
## Related links
- Source: `src/oracq/algorithms/common/estimation.py`
- Tutorial: [Search for an element and estimate the success probability](../../tutorials/search-and-estimation.md)
- API reference: [Phase, amplitude, and overlap estimation](../../api/algorithms/common/estimation.rst)
- Same-group pages: [quantum phase estimation](qpe.md), [quantum counting](quantum-counting.md), [Grover search](grover.md), [amplitude amplification](amplitude-amplification.md), [Hadamard test](hadamard-test.md), [SWAP test](swap-test.md)
- Validation matrix: [Validation coverage matrix](../../development/validation-coverage.md)
## 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 {obj}`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:
```bash
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-`).