Parallel depth of reversible Boolean embedding

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.