Exact-success amplitude amplification query cost

In the nontrivial branch $0<a<1$, $m\le \pi \mathrm{/}(4\theta )+1\mathrm{/}2$. Since $\sqrt{a}=\sin \theta \le \theta$ by [F5] and $a\le 1$, $m\le (\pi \mathrm{/}4+1\mathrm{/}2)\mathrm{/}\sqrt{a}$. The direct $a=1$ branch uses a constant number of calls.

The initial $A^{\mathrm{\prime }}$ contributes one forward $A$, two flag calls and one controlled flag rotation. Each of the $m$ iterates contains one $A^{\mathrm{\prime }}$ and one $A^{\mathrm{\prime }†}$, contributing one forward and one inverse $A$, four flag calls and two controlled rotations. Thus these parts contribute $m+1$ forward $A$, $m$ inverse $A^{†}$, $4m+2$ flag calls and $2m+1$ rotations. Each constructed good reflection contributes two further flag calls and one $CZ$, giving $6m+2$ flag calls and $m$ $CZ$ gates. Direct good-reflection access instead contributes $m$ calls of its own coordinate and leaves the flag total $4m+2$.

Each constructed zero reflection uses one controlled-$S_0$, two Toffolis and four $X$ gates; $m$ repetitions give $m,2m,4m$, respectively. Direct zero-reflection access instead uses $m$ direct $S_0^{\mathrm{\prime }}$ calls. The same external clean scratch is reused, since the exact reflection constructions return it to zero. The optional terminal construction uses two flag calls and two Toffolis around one bit measurement, with a second external bit, so its addition gives the stated $6m+4$ or $4m+4$ flag total. No other step invokes $C_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}$; the separately supplied terminal mode has no constituent flag count inferred.

The bounds in steps 1.1–1.3 are $O(a^{-1\mathrm{/}2})$. By [F2]–[F4], they count only the declared query and access coordinates; exact arithmetic, synthesis, preparation, measurement, and any final verifier retain their separate costs. The success guarantee is [F1] together with Exact success for known positive amplitude with explicit dilution.