Reversible Computation, Ancillas, and Coherent Oracles

In the clean case, for every $w\in {\mathcal{H}}_R\otimes {\mathcal{H}}_D$, write $w$ as a finite sum of elementary tensors. The clean identity in [F1] and the tensor-map rule [F2] give $(I_R\otimes U)(w\otimes \mathrm{\mid }{0}_A⟩)=((I_R\otimes V)w)\otimes \mathrm{\mid }{0}_A⟩$.

For any linear map $A$ with adjoint and vectors $u,v$, conjugate symmetry and the defining adjoint relation give $⟨A^{†}q,v{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}=\overline{⟨v,A^{†}q{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}}=\overline{⟨Av,q{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}}=⟨q,Av{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}$ for every $q$. Hence $A{R}_{u,v}{A}^{†}=R_{Au,Av}$. By [F3], $R_{w,z}\otimes P_0=R_{w\otimes \mathrm{\mid }{0}_A⟩,z\otimes \mathrm{\mid }{0}_A⟩}$. Apply the rank-one identity with $A=I_R\otimes U$, $u=e_i\otimes \mathrm{\mid }{0}_A⟩$, and $v=e_j\otimes \mathrm{\mid }{0}_A⟩$, where $e_i,e_j$ range over the product orthonormal basis of $R\otimes D$. Step 1.1 gives the clean conjugation formula for each $R_{e_i,e_j}\otimes P_0$. Every matrix $X$ on $R\otimes D$ equals ${\sum }_{i,j}⟨X{e}_j,e_i{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}{R}_{e_i,e_j}$, since the right side agrees with $X$ on each basis vector; hence these matrix units span and linearity proves the clean identity for every $X$.

In the dirty case, [F1] and [F2] give $I_R\otimes U=I_R\otimes V\otimes I_A$ on every elementary tensor and hence on the whole product space. The product inner product [F3] makes its adjoint $I_R\otimes V^{†}\otimes I_A$: this follows first on elementary tensors from the defining adjoint relation for $V$, then on all vectors because they span by [F4]. Substitution yields the dirty identity for every matrix $Y$, including every density matrix; for a product $Y=Z_{RD}\otimes S_A$, the output is $((I_R\otimes V)Z_{RD}(I_R\otimes V^{†}))\otimes S_A$, so the dirty factor remains unchanged and uncorrelated in this product case.

The matrix in [F5] sends $\mathrm{\mid }t⟩$ to $\mathrm{\mid }t\oplus 1⟩$. Applying it twice sends $t$ to $t\oplus 1\oplus 1=t$, so $X^2=I$.

By [F1], applying CNOT twice sends $\mathrm{\mid }a,t⟩$ to $\mathrm{\mid }a,t\oplus a\oplus a⟩=\mathrm{\mid }a,t⟩$, so ${\mathrm{CNOT}}^2=I$.

Applying $T$ twice leaves $a,b$ unchanged and sends $t$ to $t\oplus ab\oplus ab=t$. Thus $T^2=I$.

When the Fredkin control is $0$, each application fixes $(a,b)$. When it is $1$, each application swaps $a,b$ and leaves the control unchanged. In either case two applications restore all three bits, so $F^2=I$.

The four maps permute the ordered orthonormal computational basis by [F1]–[F5]. A permutation of an orthonormal basis preserves inner products, so each linear extension is unitary; by Steps 1.1–1.4 each is its own inverse.

Apply the gates chronologically as prescribed by [F6] to $\mathrm{\mid }c,a,b⟩$. After CNOT$(a,b)$ the last two bits are $(a,b\oplus a)$. If $c=0$, Toffoli does nothing and the last CNOT restores $(a,b)$. If $c=1$, Toffoli changes its target to $a\oplus (b\oplus a)=b$, and the last CNOT changes the other bit to $(b\oplus a)\oplus b=a$. Thus the output is $\mathrm{\mid }c,a,b⟩$ for $c=0$ and $\mathrm{\mid }c,b,a⟩$ for $c=1$, exactly the Fredkin action.

Starting with $t=0$, $X(t)$ sets it to $1$ and the following CNOT changes it to $1\oplus a$. Both gates target only $t$, so $a$ is unchanged; [F5] supplies their gate unitarity.

For the second sequence, the final target is $0\oplus a\oplus b\oplus ab$. For $(a,b)=(0,0),(0,1),(1,0),(1,1)$ these values are $0,1,1,1$, respectively, which are exactly $a\vee b$. The two CNOTs and Toffoli have controls only on $a,b$, so neither source changes; [F5] supplies their gate unitarity.

Since $t=0$, Toffoli sets $t$ to $0\oplus ab=ab$. The four control cases $00,01,10,11$ give target values $0,0,0,1$, respectively, and the controls are unchanged.

CNOT from this work bit to the disjoint target changes $y$ to $y\oplus ab$ and leaves $a,b,t$ otherwise unchanged. The final Toffoli toggles $t$ by the same $ab$, returning it to $ab\oplus ab=0$; by [F2] it is the inverse compute gate. Thus each basis input has the stated output and clean work.

The vectors $\mathrm{\mid }a,b,y,0⟩$, as $(a,b,y)$ ranges over its eight values, form a basis of the input subspace with the work factor fixed to $\mathrm{\mid }0⟩$, by [F7]–[F8]. Every gate is linear, so the basis-vector identity in Step 2.1 extends to every superposition in that subspace. The tensor-map rule [F6] makes each gate act factorwise on the ordered wires, preserving the displayed register order.

On a basis input, the forward computation gives $\mathrm{\mid }x,g(x),r(x)⟩$. Since $Y$ is disjoint, bitwise CNOT from the designated $g(x)$ subregister changes an arbitrary target $y$ to $y\oplus g(x)$ and leaves $XW$ unchanged. The intermediate state is therefore $\mathrm{\mid }x,y\oplus g(x),g(x),r(x)⟩$, with $g(x),r(x)$ together occupying $W$; [F12] supplies the CNOT gate unitarity.

Applying $C^{-1}$ to $XW$ returns $\mathrm{\mid }x,g(x),r(x)⟩$ to $\mathrm{\mid }x,0_W⟩$ by the assumed forward basis action and [F6]. The inverse is supplied on $XW$ by the Given clause, so the disjoint target $Y$ is untouched and remains $y\oplus g(x)$. This proves the displayed basis action and exact restoration of all work required by the clean-ancilla contract [F1].

By [F7]–[F11], the ordered basis vectors $\mathrm{\mid }x,y,0_W⟩$ form a basis of the subspace with work fixed to zero. Step 2.1 therefore extends by linearity to every superposition in that subspace, with data action $V\mathrm{\mid }x,y⟩=\mathrm{\mid }x,y\oplus g(x)⟩$. This data map is an involutive permutation of its orthonormal computational basis, since applying it twice restores $y$; hence $V$ is unitary. The complete compute-copy-inverse operation thus satisfies the clean identity in [F1], and [F2] extends it to every finite reference register and matrix. The tensor-map and chronological-circuit conventions [F4]–[F5] preserve the ordered factors in these extensions.

Let $q$ be the number of two-port nodes whose two ports name the same source. Each non-input node uses at most three evaluation gates: at most one for a constant, two for NOT, one for AND, and three for OR. Each repeated-source node adds one CNOT copy and one uncopy, so the forward pass uses at most $3S+2q$ gates. Since each such node accounts for two of the $E$ port uses, $q\le E$, and the forward bound is at most $3S+2E$. It uses $S$ value bits and $q\le E$ temporary bits.

The $m$ output ports are copied by $m$ CNOTs into distinct target bits. Reversing the complete node-evaluation list uses at most another $3S+2E$ gates. By [F6], each gate is its own inverse; reversing both order and gate sequence therefore implements the inverse computation and returns every value and temporary bit to zero. The total is at most $2(3S+2E)+m=6S+4E+m$ gate occurrences. A serial execution assigns each occurrence its own explicit layer, so the depth has the same bound by [F13]; [F11] specifies the chronological operator product.

Use [F9]–[F10] to identify each ordered bit string with its unique basis vector. Induct along the supplied topological order. A constant-$0$ node leaves its zero bit unchanged and a constant-$1$ node uses [F8]; NOT and OR nodes receive the outputs in [F3], and AND nodes receive the output in [F4]. If a two-port node repeats a source value $c$, its fresh scratch bit is set to $c$ by CNOT; the two distinct physical control wires then both hold $c$, so AND gives $c\wedge c=c$ and OR gives $c\vee c=c$. The scratch is immediately uncomputed by the same CNOT. Thus every value bit equals its Boolean node value and all temporary bits are zero before the output copy. The $m$ output CNOTs produce $y\oplus f(x)$; reversing the node list then restores every work bit without touching the input or target registers, whose order is fixed by [F7]. Since applying $y\mapsto y\oplus f(x)$ twice returns $y$, the target action is a permutation of the ordered basis and is unitary by [F12]; the compiled gate list is unitary by [F6] and [F11].

The basis identity in Step 3.1 extends by linearity to every input vector, so it is the clean-ancilla identity required by [F5]. The lemma then extends it to every finite reference register and every matrix, hence to density matrices. The construction uses only the supplied finite list; no choice principle is used.

For a source wire used $r\ge 1$ times in one DAG layer, start with that wire as one leaf and in each round apply CNOT from each current leaf to at most one fresh zero target. After $j$ rounds there are at least $\min (r,2^j)$ distinct leaves, so at most $\lceil {\log }_2(r+1)\rceil \le L$ rounds suffice. The tree needs $r-1$ CNOTs, and summing $r-1$ over source wires and layers gives at most $E$ copies. By [F4], each leaf carries the source's basis value and each CNOT leaves its control unchanged. The rounds are successive explicit layers in the order specified by [F9], counted by [F10].

Fix a DAG layer and suppose each source wire at its start holds its Boolean circuit value. Fan out every source to private leaves by Step 1.1. Each non-input node has a distinct fresh zero value bit. A constant-$0$ node leaves that bit unchanged, and a constant-$1$ node flips it by [F5]. For NOT, the two sublayers in [F7] write $1\oplus a$; for AND, [F6] writes $ab$; for OR, [F7] writes $a\oplus b\oplus ab=a\vee b$. Repeated logical sources have distinct physical leaves, and every gate preserves its leaves. Targets are distinct between nodes, so each of these at most three gate sublayers has disjoint supports. Reversing the fan-out trees restores all private leaves to zero, since the evaluation gates did not change them; [F8] supplies the inverse CNOTs. By [F9] these are chronological sublayers, and [F10] counts them. The layer therefore takes at most $L+3+L=2L+3$ depth.

If a non-input node $u$ feeds a node $v$, every longest path ending at $u$ extends by that edge, so the layer index of $u$ is strictly smaller than the layer index of $v$. Induct on the layer index. At the first layer all non-input predecessors are absent; at a later layer every non-input predecessor has its correct value by induction. Step 2.1 then writes the Boolean value of each node in the current layer and clears its temporary leaves. Thus after all $D$ layers every value bit equals its node's Boolean evaluation, including when two ports use the same source, and all fan-out leaves are zero.

For each output source selected $r$ times, use Step 1.1 to produce $r$ private leaves in at most $L_m$ rounds. Copy each leaf into its distinct target bit in one layer, then reverse the tree in at most $L_m$ rounds. Summing $r-1$ over output sources gives at most $m$ temporary targets, and the output stage has depth at most $2L_m+1$. This also covers repeated output ports and output sources that are input wires. The chronological composition is the one in [F9], and [F10] counts the explicit layers.

Copy each output into its target, then reverse the layer computations. In reverse order the fan-out tree is first recreated, the node gates are inverted to clear their value bits, and the fan-out tree is then undone; [F8] makes these same CNOT, X, and Toffoli gates available as inverses. This costs at most another $D(2L+3)$ depth and returns every value bit and temporary copy to zero. Adding this reverse depth, the output stage from Step 4.1, and the forward depth from Steps 2.1–3.1 gives $2D(2L+3)+2L_m+1$. There are $S$ value bits, at most $E$ temporary input-copy bits, and at most $m$ output-copy bits, for $O(S+E+m)$ work. The input-copy trees and their reversals in both computation passes use at most $4E$ CNOTs, and the output-copy trees and their reversals use at most $2m$ CNOTs, output copying uses $m$ CNOTs, and Boolean evaluation and reversal use at most $6S$ gates, hence the total is $O(S+E+m)$. Since fan-in is at most two, $E\le 2S$. By Step 3.1 each output source holds its Boolean value, so Step 4.1 changes the target to $y\oplus f(x)$; reversing node computations restores the work without changing the input or target. This is the XOR embedding specified by [F1]. By [F11]–[F14], ordered bit strings identify the complete computational basis of the input, target, and work registers, including the zero-qubit case; the basis identity therefore extends by linearity to superpositions. The finite circuit denotes the chronological operator product [F9], its resource coordinates are counted by [F10], and fan-out CNOTs may entangle copies during computation, but reversing them restores each copy bit to zero, so no arbitrary unknown state is cloned.

Apply $O_f$ twice to a basis vector. The first application gives $\mathrm{\mid }x,y\oplus f(x)⟩$; the second gives $\mathrm{\mid }x,(y\oplus f(x))\oplus f(x)⟩=\mathrm{\mid }x,y⟩$ because every bit added modulo two twice is zero. The input $x$ is preserved throughout, so injectivity of $f$ is not needed.

By [F2]–[F6], the input and target strings label the entire finite orthonormal product basis in the declared order. Step 1.1 shows that the oracle map is a permutation of this basis, so its matrix has orthonormal columns and satisfies $O_f^{†}{O}_f=I$. Therefore it is unitary, and Step 1.1 gives its inverse as itself.

By [F4]–[F6], the $2^m$ target basis vectors are orthonormal and the encoding lists each exactly once; hence $\mathrm{\mid }{\chi }_s⟩$ has squared norm $2^m{2}^{-m}=1$. Applying the oracle termwise gives $2^{-m\mathrm{/}2}{\sum }_y(-1{)}^{s\cdot y}\mathrm{\mid }x,y\oplus f(x)⟩$. Set $z=y\oplus f(x)$. Then $y=z\oplus f(x)$ and $s\cdot y=s\cdot z\oplus s\cdot f(x)$, so the sum is $(-1{)}^{s\cdot f(x)}\mathrm{\mid }x⟩\mathrm{\mid }{\chi }_s⟩$.

By [F3]–[F6], the ordered input basis spans its register, so linearity gives the same phase action on every superposition ${\sum }_x{\alpha }_x\mathrm{\mid }x⟩$, with the target factor unchanged. When $m=1$ and $s=1$, multiplying the matrix in [F7] by $\mathrm{\mid }1⟩=(0,1{)}^T$ gives $H\mathrm{\mid }1⟩=(\mathrm{\mid }0⟩-\mathrm{\mid }1⟩)\mathrm{/}\sqrt{2}=\mathrm{\mid }-⟩$. Also $H^{\ast }H=\frac{1}{2}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)=I$, so this is a unitary target preparation. The unitary character of the oracle is supplied by [F2].

A phase oracle for a Boolean function $g$ means the diagonal map $P_g\mathrm{\mid }x⟩=(-1{)}^{g(x)}\mathrm{\mid }x⟩$, and a declared query contract counts each invocation of its named black box as one query. Thus a declared phase-oracle invocation is one phase query. If the supplied black box is instead the XOR map, [F2] gives the same phase action using exactly one XOR-oracle invocation; target-state preparation is a separate ordinary circuit operation, charged in the separate coordinates of [F6].

If the only input for $f$ is an explicit Boolean circuit, [F3] replaces each required function evaluation by its finite compiled gate list, so the listed gates, depth, and work are charged under the separate resource coordinates [F6]. There is no black-box invocation to count unless the contract separately supplies one. Likewise a controlled black-box call requires declared controlled access [F5]; and although $O_f^{-1}=O_f$ by [F4], each call made to apply it remains one query invocation.