Reversible Arithmetic and Oracle Conversion

On each computational-basis input $\mathrm{\mid }x⟩\mathrm{\mid }y⟩$, the defined action leaves $x$ fixed and changes $y$ to $y\oplus f(x)$. Applying it twice changes the target to $(y\oplus f(x))\oplus f(x)=y$, since each bit toggled twice returns to its original value. Hence the action is involutive on every basis vector.

The displayed action is exactly the total Boolean XOR oracle in [F1], so [F1] gives its unitarity. Because the action retains each address $x$ and only translates its target by $f(x)$, it does not require distinct addresses to have distinct function values; no injectivity assumption is needed.

For each basis vector $\mathrm{\mid }x⟩$, the coefficient $(-1{)}^{f(x)}$ is either $1$ or $-1$. Therefore $P_f$ maps the ordered basis to scalar multiples of itself and preserves each basis vector's norm.

Distinct basis vectors remain orthogonal because their images are scalar multiples of the same distinct basis vectors; the diagonal coefficients have modulus one. By [F4] these vectors form an orthonormal basis, so the linear extension preserves the inner product on a basis and hence on every vector; it is unitary in finite dimension.

Applying $P_f$ twice to $\mathrm{\mid }x⟩$ gives $(-1{)}^{2f(x)}\mathrm{\mid }x⟩=\mathrm{\mid }x⟩$. The basis spans the register by [F4], so $P_f^2=I$ on the whole register.

If $f(x)=0$, the query leaves the target bits unchanged, so it fixes $\mathrm{\mid }x⟩\mathrm{\mid }-⟩$. If $f(x)=1$, it swaps the target basis vectors and sends $(\mathrm{\mid }0⟩-\mathrm{\mid }1⟩)\mathrm{/}\sqrt{2}$ to $(\mathrm{\mid }1⟩-\mathrm{\mid }0⟩)\mathrm{/}\sqrt{2}=-\mathrm{\mid }-⟩$. Therefore in both cases the target returns unchanged and the scalar is $(-1{)}^{f(x)}$.

By [F2], the address factor in step 1.1 is exactly $P_f\mathrm{\mid }x⟩$. Any address vector is a finite linear combination ${\sum }_x{\alpha }_x\mathrm{\mid }x⟩$ by [F4]; linearity of $U_f$ gives ${\sum }_x{\alpha }_x(-1{)}^{f(x)}\mathrm{\mid }x⟩\mathrm{\mid }-⟩=(P_f{\sum }_x{\alpha }_x\mathrm{\mid }x⟩)\otimes \mathrm{\mid }-⟩$. Hence the target is unchanged and the identity holds on every superposition.

From [F4], after the first gate the target is $X\mathrm{\mid }0⟩=\mathrm{\mid }1⟩$, and after the second it is $H\mathrm{\mid }1⟩=\mathrm{\mid }-⟩$. The chronological order is therefore $HX\mathrm{\mid }0⟩$, not $XH\mathrm{\mid }0⟩$.

Apply the standard query once. The phase-kickback theorem [F3], using the query action [F1] and the target established in step 1.1, gives $P_f$ on the address and returns the target to $\mathrm{\mid }-⟩$. By [F2] this address action is exactly the defined phase query.

The preparation has one $X$ and one $H$, hence two nonoracle gates by [F5]–[F6], and the oracle is invoked once by [F1]. These counts are separate; the construction makes no generic state-preparation call.

Fix $x$. By [F1] and [F3], the controlled phase call acts on the output qubit by $\mathrm{diag}(1,(-1{)}^{f(x)})$. If $f(x)=0$, this is $I$; if $f(x)=1$, it is $\mathrm{diag}(1,-1)$.

The two possible output operators after the surrounding Hadamards are $HIH=I$ and $H\mathrm{diag}(1,-1)H=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)=X$, using the matrix in [F4]. Thus for both $y=0$ and $y=1$ the output bit becomes $y\oplus f(x)$, while $x$ is unchanged. By [F7], these computational states form a basis, so the equality extends by linearity to every input superposition, which is exactly [F2].

The circuit uses the explicitly granted controlled phase call once and has two $H$ occurrences. By [F5]–[F6] these are two separately charged nonoracle gates; no uncontrolled call is promoted to controlled access.

On basis input $\mathrm{\mid }x⟩\mathrm{\mid }{0}^b⟩\mathrm{\mid }{0}^w⟩\mathrm{\mid }y⟩$, the first circuit $V$ produces $\mathrm{\mid }x⟩\mathrm{\mid }f(x)⟩\mathrm{\mid }{0}^w⟩\mathrm{\mid }y⟩$ by the assumed evaluator identity. The output register is a separate factor from the fresh target.

Applying one CNOT from each output bit to its corresponding target bit leaves $x$, $f(x)$, and the zero workspace unchanged, and changes $y$ to $y\oplus f(x)$ by [F3].

Apply $V^{-1}$ to the address, value, and workspace factors. Since $V^{-1}V=I$ on those factors and does not act on the target, the result is $\mathrm{\mid }x⟩\mathrm{\mid }{0}^b⟩\mathrm{\mid }{0}^w⟩\mathrm{\mid }y\oplus f(x)⟩$. This is the standard query action [F4] with clean work [F1]. The gate count is $G+b+G=2G+b$ by [F2] and [F7].

The basis vectors with value and work initially zero span the allowed input subspace by [F8]. The composed circuit is linear, so step 3.1 extends to every superposition in that subspace. Thus the standard query action and clean-work identity hold for all allowed vector inputs.

The finite Boolean-DAG procedure [F5] already includes its own output copy and reverse pass. Therefore its complete elementary gate-occurrence bound for implementing the XOR action is the supplier bound [F6], not an additional application of the generic $2G+b$ construction. The stated asymptotic forms follow by dividing the exact bound by the indicated parameter relation $E=O(S)$ when that relation holds.

Every integer $r$ has the form $r=2q+\epsilon$ for some $q\in \mathbb{Z}$ and $\epsilon \in \{0,1\}$. For $r\ge 0$, induction starts with $0=2\cdot 0+0$; from $r=2q$ obtain $r+1=2q+1$, and from $r=2q+1$ obtain $r+1=2(q+1)+0$. For $r<0$, apply the nonnegative case to $-r=2q+\epsilon$: if $\epsilon =0$, then $r=2(-q)$, and if $\epsilon =1$, then $r=2(-q-1)+1$. By [F3], $r\equiv \epsilon (\mathrm{m}\mathrm{o}\mathrm{d}2)$, so [F1] gives $[r{]}_2=[\epsilon {]}_2$. Hence every quotient class is one of $[0{]}_2,[1{]}_2$.

The classes $[0{]}_2$ and $[1{]}_2$ are distinct: equality would give $0\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}2)$ by [F1], hence $2\mid -1$ by [F3], which is impossible because no integer $q$ satisfies $-1=2q$. Together with step 1.1, this proves that the quotient has exactly the two listed classes.

Applying [F2] to representatives $0$ and $1$ gives the addition table $[0]+[0]=[0]$, $[0]+[1]=[1]$, $[1]+[0]=[1]$, $[1]+[1]=[0]$, and the multiplication table $[0][0]=[0]$, $[0][1]=[1][0]=[0]$, $[1][1]=[1]$. Since steps 1.1 and 2.1 show that these are all quotient classes, the tables are exhaustive; both operations take values in this carrier and are exactly the quotient operations.

For bits $u,v\in \{0,1\}$, the four cases give $u\wedge v=uv$. Thus $[a_i\wedge x_i{]}_2=[a_i{]}_2[x_i{]}_2$ for each coordinate by [F2] and [F4].

Let $p_0=0$ and $p_{k+1}=p_k\oplus (a_k\wedge x_k)$ for $0\le k<n$. The base case has $[p_0{]}_2=[0{]}_2$, the empty sum. If $[p_k{]}_2$ is the left-to-right sum of the first $k$ coordinate products, the addition table in [F2] and the coordinate identity in step 1.1 give $[p_{k+1}{]}_2=[p_k{]}_2+[a_k{]}_2[x_k{]}_2$. Hence the identity holds at every $k\le n$ by finite induction, including $n=0$.

At $k=n$, $p_n$ is the defined XOR fold $a\cdot x$, so step 2.1 proves that its residue class is the sum of the coordinate products in the quotient operations. No field axiom is used.

Before any Toffoli gate, $r=0$, which is the empty parity $p_0$.

If after processing coordinates $0,\dots ,i-1$ the work bit is $p_i={⨁}_{j<i}(a_j\wedge x_j)$, the next Toffoli leaves the controls unchanged and changes $r$ to $p_i\oplus (a_i\wedge x_i)=p_{i+1}$ by [F3]. Thus the forward invariant holds for every $i\le n$.

At the end of the forward loop, $r=p_n=a\cdot x$ by [F2]. This includes $n=0$, for which step 1.1 is already the final state.

The CNOT now changes $z$ to $z\oplus r=z\oplus (a\cdot x)$ and leaves $a,x,r$ unchanged by [F4].

In the reverse loop, define $q_i$ to be the accumulator after the gates for coordinates $n-1,n-2,\dots ,i$ have been applied. Before any reverse gate, $q_n=p_n$. If $q_{i+1}=p_{i+1}$, the next Toffoli toggles $q_{i+1}$ by $a_i\wedge x_i$, so $q_i=p_{i+1}\oplus (a_i\wedge x_i)=p_i$. Descending through $i=n-1,\dots ,0$ therefore ends at $q_0=p_0=0$. The reverse gates do not change $a,x,z$, so the work bit is clean.

The input basis map is the claimed map by steps 3.1 and 4.1. Every gate is linear, and the computational basis spans the finite joint register by [F6], so the same identity holds on every superposition. The forward and reverse loops each have $n$ Toffoli occurrences and there is one CNOT, giving the exact stated nonoracle gate-occurrence count; the algorithm has no branch and makes no oracle call.

Since $f(x)=c$ for every address $x$, [F1] gives $P_f\mathrm{\mid }x⟩=(-1{)}^c\mathrm{\mid }x⟩$ on a basis; hence $P_f=(-1{)}^{c}I$.

Under [A1], the controlled block is $I$ if $c=0$. If $c=1$, it is $\mathrm{diag}(I,-I)$ by [F3]. Applying these blocks to $\mathrm{\mid }+⟩\mathrm{\mid }{0}^a⟩$ gives respectively $\mathrm{\mid }+⟩\mathrm{\mid }{0}^a⟩$ and $(\mathrm{\mid }0⟩-\mathrm{\mid }1⟩)\mathrm{\mid }{0}^a⟩\mathrm{/}\sqrt{2}=\mathrm{\mid }-⟩\mathrm{\mid }{0}^a⟩$. This is the $\theta =\pi$, $U=I$ relative-phase instance of [F6]; the controlled identity is the identity operation and the other block is the explicitly granted controlled phase call.

The scalar has modulus one. Applying [F2] to any normalized address state shows that the standalone call preserves every finite POVM outcome law. This verifies the statement even when $c=1$ and the vector acquires a minus sign.

The explicit vectors $\mathrm{\mid }+⟩=(\mathrm{\mid }0⟩+\mathrm{\mid }1⟩)\mathrm{/}\sqrt{2}$ and $\mathrm{\mid }-⟩=(\mathrm{\mid }0⟩-\mathrm{\mid }1⟩)\mathrm{/}\sqrt{2}$ have unit norm and inner product zero by [F5]. The two control outputs therefore give opposite deterministic outcomes when measured in that basis, proving distinguishability. The proof uses the explicitly controlled operation [A1] and makes no claim from uncontrolled access alone.