Ninefold nearest-neighbor multiplexor routing

Let $m=n-1$ be the number of controls and list them from nearest to farthest from the target. In a reflected Gray traversal, the nearest control is toggled at most $2^m$ times; the control at distance $k\ge 2$ is toggled at most $2^{m-k+1}=2^{n-k}$ times. To see the bound, recursively form the reflected list $G_m=(G_{m-1}0,\mathrm{rev}(G_{m-1})1)$ and add the final edge returning the last word to the first: each non-farthest coordinate's toggle count is at most twice its count at the preceding recursion level, while the farthest coordinate changes at most twice (once at the join and once on return). The bound holds at $m=1$ and induction gives the displayed powers. Each toggle is one CNOT between the toggled control and the target. The total number of original CNOTs is $2^m$ by [F1].

For a CNOT whose endpoints are $k\ge 2$ line edges apart, define $S_k$ to be the sequence of adjacent CNOTs along edges $0\to 1,1\to 2,\dots ,k-1\to k$, followed by the reverse sequence on edges $k-2\to k-1,\dots ,1\to 2$. It has $2k-2$ gates. Starting from bits $(x_0,\dots ,x_k)$, the forward sweep makes wire $j$ hold $x_j\oplus \cdots \oplus x_0$. The reverse sweep, in descending order, restores wires $2,\dots ,k-1$ to $x_j$ and leaves wire 1 as $x_1\oplus x_0$ and wire $k$ as $x_k\oplus \cdots \oplus x_0$. Applying the same sequence a second time restores every intermediate wire and changes only wire $k$, to $x_k\oplus x_0$. Thus $S_k{S}_k$ is the required remote CNOT and uses $4k-4$ adjacent CNOTs. For the opposite ordered orientation, reflect the wire labels $j\mapsto k-j$ in this construction; that reflection already reverses the physical orientation of each adjacent CNOT. Applying the same calculation to $(x_k,\dots ,x_0)$ shows that the mirrored square restores every intermediate wire and changes only the left endpoint target, to $x_0\oplus x_k$. Both directed adjacent orientations are permitted, and the mirrored network also uses $4k-4$ gates. The identities hold on every basis vector by [F2], hence as operators by linearity.

Leave every length-one CNOT unchanged and route each longer CNOT by step 2.1. Using the bounds in step 1.1, the routed count for one multiplexor is at most $2^{n-1}+{\sum }_{k=2}^{n-1}(4k-4)2^{n-k}=9\cdot 2^{n-1}-8n\le 9\cdot 2^{n-1}\mathrm{.}$ The original multiplexor has $2^{n-1}$ CNOTs by [F1], so the routed count is at most nine times its original count. By the contiguous recursive layout in [A1], every recursive block occupies a contiguous interval and each terminal two-qubit block is adjacent, so its CNOTs need no routing. Routing each multiplexor independently therefore preserves the factor-nine bound for the total CNOT count. This does not use any optimized QSD cancellation.

The local routing identity and count use the ordered-wire, chronological-denotation, and occurrence-count conventions in [A2]. The factor-nine estimate uses the locally stated unoptimized recurrence [A1]; the separate optimized terminal-count proof is not assumed.