Relative estimation of a promised coherent success probability

Rounding mode. Select exact-cyclotomic (the original finite comparison mode below) or efficient-grid. In efficient-grid mode replace only RoundedAE output rounding: run Efficient coherent amplitude-grid rounding on the measured $k$-bit label $y$, with $M=2^k$, and return $a_M(y)\mathrm{/}{M}^2$. Its range is $[0,1]$, zero label returns zero, and absolute error is at most $3\mathrm{/}(4M^2)<M^{-2}$. All following thresholds, medians, caps and scale choices are unchanged. The helper supplies actual uniform polynomial-in-$\log M$ generation, elementary reversible gates and work, with actual inverse/control versions; use those costs in this mode.

Input. An arbitrary finite-dimensional amplitude-estimation instance from Amplitude estimation and counting input/output contract, with unitary sampler $A$, initial vector $\mathrm{\mid }0⟩$, supplied orthogonal success projection $\mathrm{\Pi }$, and unknown probability $p=\mathrm{\parallel }\mathrm{\Pi }A\mathrm{\mid }0⟩{\mathrm{\parallel }}^2$; rational parameters $0<p_{\min }\le 1$, $0<c<1\mathrm{/}4$, and $0<\beta <1$; and the promise $p=0$ or $p\ge p_{\min }$.

Use the repeated controlled-unitary access mode with $Q=-A{S}_0{A}^{\ast }{S}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$ from that task definition. Controlled $A$, controlled $A^{\ast }$, controlled $S_0$, controlled $S_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$, and the control phase are explicitly supplied or implemented with declared costs. An ordinary preparation $A\mathrm{\mid }0⟩$ is also available and charged. Ordinary uncontrolled sampler access alone does not supply these controlled capabilities.

Output. A rational estimate $\widehat{p}\in [0,1]$. The procedure uses independent fresh estimator workspaces, measures and discards them, and returns only classical data. Any subsequent use of a sampler starts a fresh execution from its declared initial vector.

Instructions. Set $M_j=4\cdot 2^j$. Determine the least integer $L\ge 0$ with $M_L^2{p}_{\min }\ge 1024$ by doubling and rational comparison. Set $\delta =\min \{1\mathrm{/}16,\beta \mathrm{/}(L+2)\}$. Choose the least positive odd integer $r$ with $(4\mathrm{/}5{)}^r\le \delta$, using rational multiplication and comparison.

For each dyadic integer $M\ge 4$, define the following two subprocedures.

1. $\mathrm{RoundedAE}(M)$ runs QFT-based amplitude estimation with label size $M$, obtaining the exact real cyclotomic output $z={\sin }^2(\pi y\mathrm{/}M)$. If $y=0$, return zero. Otherwise use Finite exact comparison of real cyclotomic values and binary search among the integers $0\le t\le M^2$ to find the largest $t$ with $t\mathrm{/}{M}^2\le z$, and return $t\mathrm{/}{M}^2$. Equality is decided by the same exact comparison procedure; $z=1$ returns $1$.
2. $\mathrm{MedAE}(M)$ runs $r$ independent copies of $\mathrm{RoundedAE}(M)$ and returns their middle order statistic, using rational comparisons.

For $j=0,\dots ,L$ in order, compute $b_j=\mathrm{MedAE}(M_j)$. If $b_j\ge 256\mathrm{/}{M}_j^2$, stop this loop at $J=j$, choose the least power of two $N\ge 16M_J\mathrm{/}c$, and return the output of a fresh $\mathrm{MedAE}(N)$. If no such detection occurs through $j=L$, return zero without a final estimation call.

Query, preparation, ordinary-gate, measurement and classical-bit costs are separate coordinates. All exact comparisons, cyclotomic encoding, rational arithmetic, sorting, and output writing are charged as classical bit operations under Classical bit-operation cost. The comparison supplier asserts termination, without a polynomial bit-cost bound.