Reversible zero-completion of an N-address bit query

Input: An integer $N\ge 1$, a power of two $M=2^m$ with $N\le M<2N$, a padded address register $A_M$ with basis $\mathrm{\mid }j⟩$ for $0\le j<M$, a response bit, and the raw XOR oracle $O_x$ whose address input is the $N$-level register with basis $\mathrm{\mid }q⟩$ for $0\le q<N$. If $N=M$, identify $A_M$ with the raw address register. If $N<M$, supply a separate clean $N$-level raw-address register $Q_N$ initialized to $\mathrm{\mid }0⟩$, together with clean comparator and routing workspace.

Output: The zero-completed query action $\mathrm{\mid }j,b⟩\mapsto \mathrm{\mid }j,b\oplus {\tilde{x}}_j⟩$ on $A_M$ and the response bit, where ${\tilde{x}}_j=x_{j+1}$ for $j<N$ and ${\tilde{x}}_j=0$ for $j\ge N$, with every added register restored to its specified computational-basis zero state.

Instructions:

1. If $N=M$, call $O_x$ directly on $A_M$ and the response bit, then return. If $N<M$, continue with Steps 2--5.
2. Compute the validity bit $v=[j<N]$ into a clean bit by a reversible binary comparison. For most-significant-first address bits $j_r$ and the fixed binary digits $N_r$, initialize $E_0=1,L_0=0$ and update $E_{r+1}=E_r\wedge ((j_r\wedge N_r)\vee (\mathrm{\neg }{j}_r\wedge \mathrm{\neg }{N}_r)),L_{r+1}=L_r\vee (E_r\wedge \mathrm{\neg }{j}_r\wedge N_r)\mathrm{.}$ Implement this Boolean comparison into the validity bit with Reversible embedding of a Boolean circuit, leaving its comparison workspace clean. The raw query address is an $N$-level register, not an $m$-bit target. Route it as follows. For each $j=1,\dots ,N-1$, apply the basis transposition $(0j)$ to $Q_N$ conditioned on $A_M=j$ and $v=1$; apply no transposition for other control values. These mutually disjoint controlled permutations define a finite input-independent unitary $R_{N,M}$, with $R_{N,M}\mathrm{\mid }j{⟩}_{A_M}\mathrm{\mid }0{⟩}_{Q_N}\mathrm{\mid }v⟩=\mathrm{\mid }j{⟩}_{A_M}\mathrm{\mid }q(j,v){⟩}_{Q_N}\mathrm{\mid }v⟩,$ where $q(j,v)=j$ if $v=1$ and $j<N$, and $q(j,v)=0$ otherwise. In particular, on the computed validity bit it writes $j$ for valid padded addresses and $0$ for invalid ones. The operation is a finite basis permutation; its inverse is itself.
3. Allocate a fresh clean response bit $r$ in $\mathrm{\mid }0⟩$ and apply $H$ to prepare $\mathrm{\mid }+⟩=(\mathrm{\mid }0⟩+\mathrm{\mid }1⟩)\mathrm{/}\sqrt{2}$. Controlled on $v=1$, swap the caller's response bit with $r$ using Fredkin gates.
4. Make one ordinary call to $O_x$ on the $N$-level raw-address register $Q_N$ and response $r$.
5. Reverse the response swap, then apply $H$ to $r$ to return it to $\mathrm{\mid }0⟩$. Apply $R_{N,M}^{-1}$ to clear $Q_N$, and reverse the reversible comparison to restore $v$ and all comparison workspace to zero. Return the caller's padded address and response registers.

The address comparison, the finite basis-permutation routing operation, response preparation, controlled swaps, and cleanup are nonoracle operations and must be charged in a gate-cost coordinate. The procedure uses no controlled-oracle capability. For $N=1$, $M=1$ and the direct-call branch applies.