Zero-completed query simulation is exact and uses one raw query

If $N=M$, the procedure returns after one direct raw oracle call, which has the required action. Suppose $N<M$. The comparison recurrence maintains $E_r=1$ exactly when the first $r$ bits of $j$ and $N$ agree, and $L_r=1$ exactly when the first differing bit has $j$-bit $0$ and $N$-bit $1$. Induction on $r$ therefore gives $v=L_m=1$ iff $j<N$. The controlled transpositions in [F1] preserve $j$ and $v$ and send a clean $Q_N$ basis state $\mathrm{\mid }0⟩$ to $\mathrm{\mid }j⟩$ when $v=1$ and $j<N$, and leave it at $\mathrm{\mid }0⟩$ otherwise. Thus the raw query address is an $N$-level basis state that equals $j$ on valid padded addresses and $0$ on invalid ones.

In the $N<M$ branch, when $v=1$, [F4] swaps the caller's response $b$ into $r$; the raw oracle then changes it to $b\oplus x_{j+1}$, and reversing the swap returns exactly this bit to the caller and leaves $r=\mathrm{\mid }+⟩$, which the final $H$ maps to $\mathrm{\mid }0⟩$. When $v=0$, the route sets $q=0$, which is valid because $N\ge 1$, while $r=\mathrm{\mid }+⟩$; the raw query applies either $I$ or $X$ to $r$, both of which fix $\mathrm{\mid }+⟩$, and the caller's response is unchanged. The final $H$ again returns $r$ to $\mathrm{\mid }0⟩$.

The raw oracle preserves its address, so the inverse controlled routing permutation clears $Q_N$ after the response swap is undone. By step 1.2 the helper response is then $\mathrm{\mid }+⟩$, so the prescribed $H$ has returned it to $\mathrm{\mid }0⟩$. Reversing the comparison circuit clears $v$ and its work registers. In both branches the resulting action on each padded-address basis state is $\mathrm{\mid }j,b⟩\mapsto \mathrm{\mid }j,b\oplus x_{j+1}⟩$ for $j<N$ and $\mathrm{\mid }j,b⟩\mapsto \mathrm{\mid }j,b⟩$ for $j\ge N$; linearity gives the same zero-completed action on every superposition. Exactly one raw oracle call occurred in either branch, and no controlled call was used.