Quantum Counting¶

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

Overview¶

Estimates the number \(t\) of marked elements in a search space of size \(N=2^n\). Quantum counting is not a separate circuit but a direct application of amplitude estimation (same Brassard framework, arXiv:quant-ph/0005055): on a uniform superposition the good-state probability is exactly \(a=t/N\); run standard amplitude estimation and multiply \(N\) back:

\[ \hat t = N\cdot\hat a. \]

This repository registers it as a gallery entry (quantum_counting in applications/gallery.py) that reuses the amplitude_estimation entry point.

Interface and input model¶

There is no separate entry function; the recipe is:

operation = amplitude_estimation(uniform_state(n), marked, precision=p)

uniform_state(n): uniform state preparation (SP), making \(a=t/N\).
marked: the set of integer indices of the marked basis states, \(t=|M|\).
precision: the number of phase-register bits, range 1..63.

The returned object’s registers and attributes are the same as in amplitude estimation (target/work/phase, decoder is "sin(pi*phase/2**precision)**2"): after reading out phase, decode via amplitude_from_phase and multiply by \(2^n\) to get \(\hat t\). The gallery instance takes \(n=2\), marked=(3,), precision=4 (\(t=1\), \(a=1/4\)).

Implementation notes¶

Circuit generation is identical to QAE; the difference is entirely in the classical-side decoding (multiplying by \(N\)). \(\hat t\) need not be an integer, and rounding it into a legal range is the host’s decision; the estimation precision is set by the QAE grid density (precision), and the point estimate is exact when \(t/N\) lands exactly on the grid.

Validation approach¶

Category C3 (acceptance criterion in docs/development/validation-plan.md §2). Quantum counting is registered in docs/development/validation-coverage.md under the estimation.py row (the algorithm column includes “quantum counting”), with no separate witness entry:

Structure: tests/core/test_algorithm_expansion.py:AlgorithmExpansionTests.
Numerical: the circuit witness is QAE’s AlgorithmExpansionTests.test_amplitude_estimation_half_probability (see amplitude estimation); the gallery instance is demonstrated by the quantum_counting entry of applications/gallery.py (“multiply the amplitude estimate by 4 to estimate the number of marked items”).
Binding: the module row registers “—“.

Known gaps and planned stages¶

Same as QAE: the confidence-interval claim is unwitnessed (only the point estimate is verified), and the error propagation of multiplying the point estimate by \(N\) is likewise not cross-checked; the estimation.py module is at stage V2.

Numerical validation¶

Experiment design: \(n=3\) (\(N=8\)), marked \(=\{1,5,7\}\) (\(t=3\), \(a=3/8\)), precision \(=4\) (grid \(M=16\)). Following the recipe above, amplitude_estimation(uniform_state(3), marked, precision=4) is generated, and the full distribution of the phase register is read out on the four backend paths (reference, rir-pysparq, adapter-pysparq, originir-ext), compared against an independent Dirichlet-kernel reference (a QPE grid convolution over the eigenphases \(\pm\theta/\pi\), \(\theta=\arcsin\sqrt{3/8}\)), and the count is decoded as \(\hat t=N\sin^2(\pi y/M)\).

Case	Scale	Paths	Metric	Value
quantum-counting-n3-t3	N=8, t=3, M=16	4 paths	phase-distribution TVD	5.7e-15
same	same	same	peak estimate \(\hat t\) (error)	2.4693 (0.531, ≤ 1 grid step)
same	same	same	central grid mass (QAE lower bound \(8/\pi^2\))	0.8529 (≥ 0.8106)

The true value \(\theta M/\pi\approx3.357\) lies between grid points 3 and 4; the bimodal distribution (\(y=3,13\), each about 0.325) matches the theoretical positions; the point-estimate precision is set by the grid density, consistent with the stated convention that “\(\hat t\) need not be an integer”.

Reproduction command:

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

Artifacts: out/verification/search_walks.json (case quantum-counting-n3-t3).