Finite amplification from a supplied success lower bound

Input a finite-register coherent preparation $U$ with good projection $P$, as in Prepared unitary and success subspace for amplitude amplification, and represented rational parameters $0<p_0\le 1$ and $0<\beta <1$. The success promise is $p:=\mathrm{\parallel }PU\mathrm{\mid }0⟩{\mathrm{\parallel }}^2\ge p_0$. Supply $U^{†}$ under Inverse Unitary Access, the reflections $S_0=I-2\mathrm{\mid }0⟩⟨0\mathrm{\mid }$ and $S_g=I-2P$ under Orthogonal-Projector Reflection and Access Contract, and the controlled versions of all operations used under Controlled Unitary Access. The good/bad instrument is the projective measurement $\{P,I-P\}$ of Finite projective measurements. It may be supplied directly or implemented by preparing an ancillary control in $\mathrm{\mid }+⟩$, applying controlled $S_g$, applying a Hadamard to the control and measuring it, with outcome $1$ designated good. These implementations and register initialization have their actual declared costs.

By exact rational comparisons compute the least power of two $M$ satisfying $M^2{p}_0\ge 4$, and the least positive integer $R$ satisfying $(3\mathrm{/}4{)}^R\le \beta$. Set $b={\log }_{2}M$. More general exact parameter representations are allowed only when they support these finite comparisons.

For trials $1,\dots ,R$, carry out the following instructions, stopping at the first return.

1. Prepare $U\mathrm{\mid }0⟩$ on a fresh register and perform the good/bad instrument. On a good outcome, return that register. On a bad outcome, discard it.
2. Draw exactly $b$ fresh independent unbiased random bits, interpret them as an integer $j\in \{0,\dots ,M-1\}$, and prepare $U\mathrm{\mid }0⟩$ on a fresh register. Apply exactly $j$ iterates $Q=-U{S}_0{U}^{†}{S}_g$ of Amplitude amplification with a fixed integer iteration count, then perform the good/bad instrument. On a good outcome, return that register. On a bad outcome, discard it and proceed to the next trial.

If all $R$ trials fail, return an explicit failure symbol. Preparations, bits and instruments are fresh between attempts. A classical-output specialization may additionally measure and verify the returned output, charging this work separately; it does not replace the good/bad projective instrument when a conditional quantum state is requested.