Iterative no-QFT amplitude estimation by finite-grid likelihood

Input. An instance of the task Amplitude estimation and counting input/output contract with the same $H,\mathrm{\mid }0⟩,A,{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ supplied under the prepared-success-subspace access contract of Prepared unitary and success subspace for amplitude amplification. That contract supplies and charges the uncontrolled calls to $A,A^{\ast },S_0,S_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$. Additionally require supplied access to the good/bad projective measurement $\{{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}},I-{\mathrm{\Pi }}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\}$ of Finite projective measurements, with each use charged in the measurement coordinate and any implementation costs charged separately; no controlled access is used. Also require integers $K,S,J\ge 1$.

Set $m_0=0$ and $m_k=2^{k-1}$ for $1\le k\le K$. For each $k=0,\dots ,K$, perform $S$ repetitions: prepare a fresh $A\mathrm{\mid }0⟩$, apply exactly $m_k$ signed Grover iterates using Amplitude amplification with a fixed integer iteration count, measure the good/bad projective measurement, and record the outcome. Let $h_k$ be the number of good outcomes at scale $k$.

Set $s=2J$ and ${\zeta }_s=e^{2\pi i\mathrm{/}s}$. For an integer $q$, let ${\rho }_s(q)$ be its least residue in $\{0,\dots ,s-1\}$. For grid labels $j=0,\dots ,J$, put ${\theta }_j=j\pi \mathrm{/}(2J)$ and define the likelihood $L_j={\prod }_{k=0}^K{\sin }^{2h_k}((2m_k+1){\theta }_j){\cos }^{2(S-h_k)}((2m_k+1){\theta }_j),$ where every zeroth power is $1$. For each label $j$ and scale $k=0,\dots ,K$, set $r_{kj}={\rho }_s((2m_k+1)j),r_{kj}^{\mathrm{\prime }}={\rho }_s(-r_{kj}),$ and form the rational polynomials $U_{kj}(X)=\frac{2-X^{r_{kj}}-X^{r_{kj}^{\mathrm{\prime }}}}{4},V_{kj}(X)=\frac{2+X^{r_{kj}}+X^{r_{kj}^{\mathrm{\prime }}}}{4}\mathrm{.}$ Put $P_j(X)={\prod }_{k=0}^K{U}_{kj}(X{)}^{h_k}{V}_{kj}(X{)}^{S-h_k}$, treating every zeroth power as $1$. The polynomials $P_j$ are the exact comparison inputs for the likelihoods $L_j$: compare $P_i({\zeta }_s)$ and $P_j({\zeta }_s)$ using Finite exact comparison of real cyclotomic values, and choose the least label $\widehat{j}$ attaining the maximum.

Set $E_{\widehat{j}}(X)=(2-X^{\widehat{j}}-X^{{\rho }_s(-\widehat{j})})\mathrm{/}4$ and return $\tilde{a}=E_{\widehat{j}}({\zeta }_s)$, encoded by the pair $(s,E_{\widehat{j}})$. Each shot uses a fresh state and ordinary measurement. This is a finite-grid likelihood procedure, not a finite-sample $ϵ,\delta$ guarantee; no such guarantee is asserted here.