Exact QSD CNOT Upper Bound

Split off the first wire and recurse on the remaining contiguous wire interval. Apply [F1] to split an $n$-qubit unitary into a central multiplexed $R_y$ and two block-diagonal factors. Apply [F2] to each side factor: each produces two recursive $(n-1)$-qubit unitaries and one diagonal two-block factor, which is a multiplexed $R_z$. Thus the recursive stage contains four $(n-1)$-qubit calls and three multiplexed rotations, interpreted with exact chronological composition [F6] and the declared no-ancilla width [F7].

Each of the three multiplexed rotations has $n-1$ select bits, so [F3] uses at most $2^{n-1}$ CNOTs per rotation. With $c_2=3$ from [F4], the recurrence is $c_n\le 4c_{n-1}+3\cdot 2^{n-1}$ for $n\ge 3$. Induction gives the unoptimized bound $c_n\le (9\mathrm{/}16)4^n-(3\mathrm{/}2)2^n$: it equals $3$ at $n=2$, and substituting the expression for $c_{n-1}$ into the recurrence gives the expression for $c_n$. The counts are gate occurrences in [F7].

For the central multiplexed $R_y$, use the Gray traversal of [F3] with controlled-$Z$ in place of CNOT. Indeed $Z{R}_y(t)Z=R_y(-t)$ by [F5], so the same Walsh angles give branch sign $(-1{)}^{p_j\cdot x}$ at mask $p_j$ and the final cyclic edge restores the accumulated $Z$ parity. This is exactly the desired multiplexed rotation. Each controlled-$Z$ costs one CNOT: $CZ=(I\otimes R_y(-\pi \mathrm{/}2))CNOT(I\otimes R_y(\pi \mathrm{/}2))$, since the active block is $R_y(-\pi \mathrm{/}2)X{R}_y(\pi \mathrm{/}2)=Z$; [F8]–[F9] justify the CNOT matrix and unitarity. Take the last Gray edge as a terminal controlled-$Z$ and absorb it into the neighboring generic block-diagonal factor before demultiplexing that factor. In its first-wire control blocks it multiplies the lower-register branch by $I$ or by the single-wire $Z$ on its select wire. Both branches remain arbitrary unitaries, so [F2] still gives four recursive children and two multiplexed $R_z$ factors. The full block identity is $LMR=(L{E}_r)TR=\mathrm{diag}(L_0,L_1{Z}_r)TR$ by [F10], where $M=E_{r}T$ and $T$ omits the terminal controlled-$Z$. Thus one CNOT is saved at each nonterminal recursive node. There are $(4^{n-2}-1)\mathrm{/}3$ such nodes, zero when $n=2$. Subtracting this from step 2.1 gives $c_n\le \frac{13}{24}{4}^n-\frac{3}{2}{2}^n+\frac{1}{3}$.

Each recursive call removes the first wire of its contiguous interval, so all $N=4^{n-2}$ terminal slots act on the same last two wires. Every nonterminal multiplexed rotation targets a wire strictly before these two. Its select operations preserve the computational labels of the last two wires: branch by branch in those labels, its rotations and controlled-$X$ or controlled-$Z$ gates act on other wires. Products of these separator operations therefore have exactly the block form required by [A1]. The preceding controlled-$Z$ absorption only changes the arbitrary child matrices before their recursive decomposition and does not change this target/select invariant. Apply [A1] to the complete ordered slot list: the first $N-1$ slots now use two CNOTs, and the last uses three, instead of three in every slot. No diagonal is synthesized separately and no wire is added. The additional saving is $N-1=4^{n-2}-1$. Consequently $c_n\le (\frac{13}{24}-\frac{1}{16})4^n-\frac{3}{2}{2}^n+\frac{1}{3}+1=\frac{23}{48}{4}^n-\frac{3}{2}{2}^n+\frac{4}{3}$. When $n=2$, $N=1$, so there is no migration or saving and the formula is the three-CNOT base case.

For $n=1$, the unitary is itself one allowed one-qubit gate and uses zero CNOTs. For $n=0$, [F11] permits no gate occurrence, so every layer is empty and [F6] makes every circuit denote $1$ on $\mathbb{C}$. Conversely, the empty circuit realizes $1$. Thus an arbitrary scalar unitary has an exact zero-wire circuit precisely when it equals $1$. The bound for $n\ge 2$ follows from step 4.1; these gate counts imply no arithmetic or precision bound.