Capped randomized amplitude amplification preserves a flagged output

If $p=1$, the direct flag outcome is good. If $0<p<1$, put $u=\sqrt{1-p}$, $v=\sqrt{p}$, $z=u+iv$, and $\xi =z^2=a+i\beta$, so $a=1-2p$ and $\beta =2\sqrt{p(1-p)}$. The orthonormal vectors $\mathrm{\mid }B⟩=(I-\mathrm{\Pi })\mathrm{\mid }\psi ⟩\mathrm{/}u$ and $\mathrm{\mid }G⟩=\mathrm{\Pi }\mathrm{\mid }\psi ⟩\mathrm{/}v$ give $\mathrm{\mid }\psi ⟩=u\mathrm{\mid }B⟩+v\mathrm{\mid }G⟩$. In this ordered basis the reflection about $\mathrm{\mid }\psi ⟩$ is $\left(\begin{array}{cc}a& \beta \\ \beta & -a\end{array}\right)$ and $I-2\mathrm{\Pi }=\mathrm{diag}(1,-1)$, so one Grover iteration has matrix $\left(\begin{array}{cc}a& -\beta \\ \beta & a\end{array}\right)$. It multiplies the complex coordinate $u+iv$ by $\xi$, hence after $j$ iterations the good amplitude is $\mathrm{Im}({\xi }^{j}z)=\mathrm{Im}(z^{2j+1})$.

If $p_{\mathrm{l}\mathrm{o}\mathrm{w}}<1\mathrm{/}2$, then $K\ge 2$ and minimality of $b=\lceil {\log }_{2}K\rceil$ gives $K\mathrm{/}{2}^b\ge 1\mathrm{/}2$. Conditional on $J<K$, the draw is uniform on $0,\dots ,K-1$. For $p\le 1\mathrm{/}2$, $(\mathrm{Im}w{)}^2=(1-\mathrm{Re}(w^2))\mathrm{/}2$ and the finite geometric sum of ${\xi }^{2j+1}$ give $\frac{1}{K}{\sum }_{j=0}^{K-1}(\mathrm{Im}(z^{2j+1}){)}^2=\frac{1}{2}-\frac{\mathrm{Im}({\xi }^{2K})}{4K\beta }\ge \frac{1}{2}-\frac{1}{4K\beta }\mathrm{.}$ Here $\beta =2\sqrt{p(1-p)}\ge \sqrt{2p}$ and $K\ge 1\mathrm{/}\sqrt{p_{\mathrm{l}\mathrm{o}\mathrm{w}}}$, so $K\beta \ge \sqrt{2}$ and the conditional mean success exceeds $1\mathrm{/}8$. Multiplication by $\mathrm{Pr}(J<K)\ge 1\mathrm{/}2$ gives randomized-branch success at least $1\mathrm{/}16$. For $p>1\mathrm{/}2$ the direct flag succeeds with probability greater than $1\mathrm{/}2$.

If $p\le 1\mathrm{/}2$, the direct-then-randomized round succeeds with probability at least $1\mathrm{/}16$ by step 2.1; if $p>1\mathrm{/}2$ or $p_{\mathrm{l}\mathrm{o}\mathrm{w}}\ge 1\mathrm{/}2$, its direct flag succeeds with probability at least $1\mathrm{/}2$. Independent fresh rounds therefore fail altogether with probability at most $(15\mathrm{/}16{)}^N\le \rho$ by the exact cap test. The comparison loop terminates because $(16\mathrm{/}15{)}^N=(1+1\mathrm{/}15{)}^N\ge 1+N\mathrm{/}15$ by the binomial theorem, so $(15\mathrm{/}16{)}^N\le 15\mathrm{/}(15+N)\to 0$. If $N>1$, minimality gives $(15\mathrm{/}16{)}^{N-1}>\rho$; applying the increasing logarithm and using $\ln ((16\mathrm{/}15{)}^{N-1})=(N-1)\ln (16\mathrm{/}15)$, with $\ln (16\mathrm{/}15)>0$, gives $N-1<\ln (1\mathrm{/}\rho )\mathrm{/}\ln (16\mathrm{/}15)$. The same asymptotic bound holds for $N=1$, so $N=O(1+\ln (1\mathrm{/}\rho ))$. Since $K=O(p_{\mathrm{l}\mathrm{o}\mathrm{w}}^{-1\mathrm{/}2})$, the stated call bound follows.

Every successful branch is passed through the supplied flag-only instrument, so its returned state is the normalized good projection of that branch's input and no score, label, or work register is measured. Step 1.1 shows that each amplified good component is a scalar multiple of $\mathrm{\mid }G⟩$; direct success has the same good ray. Thus every successful return is $\mathrm{\Pi }V\mathrm{\mid }0⟩\mathrm{/}\sqrt{p}$ up to global phase. Each round uses at most $K-1$ Grover iterations, one direct preparation, at most one amplified preparation, and $b$ random bits; multiplying by $N$ proves the stated call and random-bit bounds, with each controlled, inverse, reflection, verifier, and output cost charged.