Gate, workspace, and serial-depth costs of reversible embedding

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.