Boolean circuits compile exactly into the QC14 gate alphabet

For $a,b,c\in \{0,1\}$ set $d=a+b+c-(a\oplus b)-(a\oplus c)-(b\oplus c)+(a\oplus b\oplus c)$, with ordinary integer addition and subtraction. If exactly $k$ of $a,b,c$ equal $1$, then $d=0$ for $k=0,1,2$ and $d=4$ for $k=3$. Thus $d=4abc$.

Use one clean scratch bit $r$. Apply $T$ to each of the three data bits. For each of the three pair parities, compute that XOR into $r$ with two CNOTs, apply $T^{†}$ to $r$, and undo the same two CNOTs. Compute $a\oplus b\oplus c$ into $r$ with three CNOTs, apply $T$, and undo those three CNOTs. Each parity routine restores $r$ to zero and leaves the data bits unchanged. The total phase on $\mathrm{\mid }a,b,c⟩$ is ${\omega }^d=(-1{)}^{abc}$, so this circuit is CCZ; it uses seven $T$ or $T^{†}$ gates and eighteen CNOTs.

Conjugate this CCZ circuit by $H$ on the third data wire. If $ab=0$, CCZ is the identity on that wire; if $ab=1$, it applies $Z=T^4$, and direct multiplication of the displayed matrices gives $HZH=X$. The result is therefore $\mathrm{\mid }a,b,c⟩\mapsto \mathrm{\mid }a,b,c\oplus ab⟩$, the Toffoli action. The scratch wire is still zero, and the replacement uses $2+7+18=27$ QC14 gates.

Replace each $X$ in the reversible embedding by $H{T}^{4}H$, which equals $X$ because $T^4=Z$ and $HZH=X$; this uses six QC14 gates. Leave each CNOT unchanged and replace each Toffoli by step 3.1.

By [F2], the original macro list has at most $6S+4E+m$ occurrences. Each macro replacement has the same action on its data wires, returns the added scratch to zero, and uses at most $27$ gates, so the compiled list has at most $27(6S+4E+m)$ gates and at most $S+E+1$ clean work wires. The exact matrix identity on every computational-basis input extends by linearity to superpositions.

Traverse the explicit topological DAG once to produce the finite macro list of [F1], then replace each macro by its fixed gate sequence and fixed scratch-wire indices. Put each emitted gate in its own singleton layer, which satisfies the disjoint-support condition in [F4] and preserves the chronological product. Serialize this gate sequence using [F5], with the target wires as the ordered output tuple. The traversal and each replacement emit a constant number of records per node, port use, or output; every encoded wire index has $O(\log (n+S+E+m+2))$ bits. The unary wire header and all self-delimiting records consequently have polynomial total length and can be written in polynomial time. All gate-wire tuples have distinct entries, the input, target and work blocks are disjoint, and the output indices are distinct. Thus the singleton-layer circuit and its full-list code satisfy [F4]–[F5], with the action established in step 5.1.