Lemma: Conditional fixed-gate implementation of the last step

Suppose a unitary preparation $V$, preserving a classical input, uses $g_V$ frozen-alphabet gates on $w\ge 1$ workspace qubits, and has a success flag of probability exactly $1/4$. Suppose every successful basis output is correct. Then one amplification step gives probability-one correct output using at most

gates and at most $w-1$ extra clean scratch qubits.

Proof. The success sign is $S^2$ on its flag, costing two gates. The reflection about $V|0⟩$ is implemented, up to a global minus sign, by $V$, a sign flip on the all-zero workspace, and $V^{-1}$.

For the zero test, negate all $w$ workspace bits, compute their conjunction by a Toffoli chain, apply $S^2$, uncompute, and undo the negations. For $w\ge 2$, this costs

gates and $w-1$ clean scratch qubits. For $w=1$, use $X{S}^{2}X$, also of cost four. All scratch returns to zero.

Counting the initial preparation and the two preparations in the reflection gives three uses of $V$ or $V^{-1}$. Lemma lem:amplification proves correctness. No input-dependent rotation is used.