A Binary-Shadow Method for Wire Permutations and the Exact CNOT Cost of n-Qubit Cyclic SWAP Gates

We develop the binary-shadow method for exact CNOT counting and apply it to arbitrary wire permutations. The Heisenberg evolution of rotated local Z observables converts every CNOT gate into an elementary transvection over F2, and for a wire permutation, the resulting binary shadow is rigid: it must equal the associated permutation matrix. This reduces the exact CNOT cost of a wire permutation in the CNOT+local model to the transvection length of its permutation matrix. The remaining problem is classical. The relevant mathematical input is the transvection-length theory of permutation matrices, or equivalently, the CNOT-only synthesis of permutation circuits. Combining the binary-shadow reduction with the graph-theoretic link-middle-cut theorem for cycle matrices yields an exact formula: if σ∈Sn has c(σ) disjoint cycles, then CNOT-cost(Wσ)=ℓtr(Pσ)=3n−c(σ). The novelty is therefore not the CNOT-only permutation formula by itself, but the transfer of that exact lower bound to the CNOT+local model: arbitrary one-qubit gates may rotate the local Pauli axes, but they cannot reduce the CNOT count of a wire permutation. In particular, the n-qubit cyclic SWAP gate Sn|x1⟩1|x2⟩2⋯|xn⟩n=|xn⟩1|x1⟩2⋯|xn−1⟩n requires exactly 3(n−1) CNOT gates, even when arbitrary one-qubit gates are allowed at zero cost. Thus, the exact values for n=2,3,4,5,6,… are 3,6,9,12,15,…. We also give explicit optimal factorizations for n=4 and n=5, and show more generally that each additional wire in a cyclic shift costs exactly three more CNOT gates.