© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Quantum Reports

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

B Zhang

Published Jun 22, 2026• 0 citations

Abstract

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.

DOI: 10.3390/quantum8020055

Related papers

Link-middle-cut lower bounds for Clifford circuit synthesis

Søren Fuglede Jørgensen

Minimizing the number of CNOT gates required to synthesize a Clifford operator is a central problem in quantum circuit optimization. We extend the link--middle--cut (LMC) framework for linear reversible circuits to Clifford operators represented by binary symplectic tableaux. By introducing block-support connectivity graphs and determinantal invariants, we obtain efficiently computable lower bounds on ancilla-free CNOT complexity. We prove that these bounds are tight for qubit permutations: a permutation of $n$ qubits with $k$ cycles requires exactly $3(n-k)$ CNOT gates, even when arbitrary one-qubit Clifford gates are available. We also derive efficiently computable bounds for synthesis up to a permutation of the output qubits, corresponding to free qubit relabeling. Finally, we further demonstrate the utility of the bound by using it as an admissible heuristic for $A^*$-based Clifford synthesis and show that, on benchmark instances, the resulting search can prove optimality beyond what was possible with earlier SAT-based methods, and that it may be used in combination with earlier $A^*$ heuristics to improve the CNOT counts obtained through heuristic search.

quant-pharXiv:2609.16208•Sep 16, 2026•0 citations

Realization of permutation groups by quantum circuit

Junchi Liu, Yangyang Ren, Yan Cao +2 more

In this paper, we exclusively utilize CNOT gates for implementing permutation groups generated by more than two elements. In Lemma 1, we recall that three CNOT gates are both necessary and sufficient to execute a two-qubit swap gate operation. Subsequently, in Lemma 2, we show that the maximum number of CNOT gates needed to carry out an n-qubit substitution operation is 3(n-1). Moving forward, our analysis in Section 3 reveals that utilizing five or fewer CNOT gates is insufficient for implementing a three-qubit swap gate corresponding to the permutation element (123). Hence six CNOT gates are both necessary and sufficient for implementing (123). This is done by employing a graph-theoretic approach to rigorously validate the results in terms of at most five CNOT gates. Using computational tools, we exhaustively explore all valid circuit diagrams containing exactly six CNOT gates to successfully execute the swap gate for (123), by explaining the equivalence classes in Remark 6 and Table 2. We conclude them in Theorem 7.To extend our analysis to the multiqubit scenario, we present the reducible and irreducible permutation elements in Definition 8. We clarify the equivalence between rows in the multi-qubit space and provide an approximate upper bound for multi-qubits to perform the aforementioned operations in Theorem 9. The comprehensive exploration of this paper aims to pave the way for further advancements in understanding quantum circuit optimization via multiple use of a specific two-qubit gate.

arXiv:2406.01350•Jun 3, 2024•1 citation

Lower bounds for the CNOT-complexity of linear reversible operators

Søren Fuglede Jørgensen

The CNOT-complexity of an invertible matrix over $\mathbb{F}_2$ is the minimum number of CNOT gates needed to synthesize the corresponding linear reversible operator. While the maximum CNOT-complexity over all $n \times n$ matrices is known to be $Θ(n^2 / \log n)$, no explicit family of matrices requiring a superlinear number of CNOT gates is known, and until now the hardest explicitly known family has been the cyclic permutations, with CNOT-complexity $3(n-1)$. We show that lower bounds for the additive complexity of not-necessarily-reversible linear operators can be lifted to the reversible setting with only a small loss. As an application, we use this to describe an explicit family of matrices, constructed from parity-check matrices of error-correcting codes, with CNOT-complexity at least $4n - o(n)$, asymptotically surpassing the cyclic permutations. Moreover, this construction yields an explicit matrix $A \in \mathrm{GL}_{n}(\mathbb{F}_2)$, $n = 17167$, whose CNOT-complexity exceeds that of the cyclic permutation on $n$ symbols.

quant-pharXiv:2607.22248•Jul 27, 2026•0 citations

Optimal Layout-Aware CNOT Circuit Synthesis with Qubit Permutation

Irfansha Shaik, Jaco van de Pol

CNOT optimization plays a significant role in noise reduction for Quantum Circuits. Several heuristic and exact approaches exist for CNOT optimization. In this paper, we investigate more complicated variations of optimal synthesis by allowing qubit permutations and handling layout restrictions. We encode such problems into Planning, SAT, and QBF. We provide optimization for both CNOT gate count and circuit depth. For experimental evaluation, we consider standard T-gate optimized benchmarks and optimize CNOT sub-circuits. We show that allowing qubit permutations can further reduce up to 56% in CNOT count and 46% in circuit depth. In the case of optimally mapped circuits under layout restrictions, we observe a reduction up to 17% CNOT count and 19% CNOT depth.

arXiv:2408.04349•Frontiers in artificial intelligence and applications•Oct 16, 2024•4 citations

Exact Clifford Optimality for Two-Sided Locally Randomized Classical Shadows

Xiaotian Nie, Tao Zhang, Yadong Wu +1 more

Entangling measurements can reduce the cost of learning many-body correlations. We consider classical shadows in which a fixed unitary on a $k$-qubit region is sandwiched between two layers of random single-qubit Clifford gates, and ask which middle unitary best estimates Pauli strings with full support on the region. Combining symplectic support counting with a constraint from operator-size parity, we prove that within this architecture the minimum squared shadow norm over all Clifford middle unitaries is $C_k^{\rm opt}=4\cdot 9^k/(3\cdot 5^k+3^k-6)$ for odd $k$ and $C_k^{\rm opt}=4\cdot 9^k/(3\cdot 5^k-3^k+2)$ for even $k$. A dual-axis rotation circuit $U_*$ attains this minimum for every $k$. Asymptotically $C_k^{\rm opt}\simeq(4/3)\cdot(9/5)^k$: the exponential base of Wu et al.'s contractive unitary is optimal, and the prefactor improves from $2$ to $4/3$. For $1\leq k\leq7$, exact certificates show that $U_*$ is optimal over the entire unitary group $\mathrm U(2^k)$, and we conjecture that this holds for every $k$.

quant-pharXiv:2610.04621•Oct 6, 2026•0 citations

A Cost-Effective Quantum Boolean-Phase SWAP Gate with Only Two CNOT Gates

Ali Al-Bayaty, Shanyan Chen, Steven A. Bleiler +1 more

A new Boolean-Phase swapping gate is presented with improved quantum generality and cost-effectiveness. Our swapping gate is termed the "p-SWAP gate", where p is the phase difference selected for a set of swapped qubits. The phase p is expressed in radians and $-π~{\leq}$ p ${\leq}~+π$. The generality of p-SWAP gate is demonstrated for Phase applications for selected values of p and for Boolean applications when the value of p is ignored. The cost-effectiveness of p-SWAP gate follows from the lower quantum cost and depth of its final realized (transpiled) quantum circuit, when compared to the standard SWAP gate composed of three Feynman (CNOT) gates. Specifically, our presented p-SWAP gate utilizes only two CNOT gates. The quantum circuit of the p-SWAP gate is visually designed using our previously developed Bloch sphere approach. Experimentally, after transpilation for an IBM quantum computer, the transpiled p-SWAP gate shows an approximate 23% quantum cost reduction and an approximate 26% depth minimization compared to the transpiled standard SWAP gate.

arXiv:2507.17164•Jul 23, 2025•1 citation

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.

Minimizing the number of CNOT gates required to synthesize a Clifford operator is a central problem in quantum circuit optimization. We extend the link--middle--cut (LMC) framework for linear reversible circuits to Clifford operators represented by binary symplectic tableaux. By introducing block-support connectivity graphs and determinantal invariants, we obtain efficiently computable lower bounds on ancilla-free CNOT complexity. We prove that these bounds are tight for qubit permutations: a permutation of

n

qubits with

k

cycles requires exactly

3(n-k)

CNOT gates, even when arbitrary one-qubit Clifford gates are available. We also derive efficiently computable bounds for synthesis up to a permutation of the output qubits, corresponding to free qubit relabeling. Finally, we further demonstrate the utility of the bound by using it as an admissible heuristic for

A^*

-based Clifford synthesis and show that, on benchmark instances, the resulting search can prove optimality beyond what was possible with earlier SAT-based methods, and that it may be used in combination with earlier

A^*

heuristics to improve the CNOT counts obtained through heuristic search.

In this paper, we exclusively utilize CNOT gates for implementing permutation groups generated by more than two elements. In Lemma 1, we recall that three CNOT gates are both necessary and sufficient to execute a two-qubit swap gate operation. Subsequently, in Lemma 2, we show that the maximum number of CNOT gates needed to carry out an n-qubit substitution operation is 3(n-1). Moving forward, our analysis in Section 3 reveals that utilizing five or fewer CNOT gates is insufficient for implementing a three-qubit swap gate corresponding to the permutation element (123). Hence six CNOT gates are both necessary and sufficient for implementing (123). This is done by employing a graph-theoretic approach to rigorously validate the results in terms of at most five CNOT gates. Using computational tools, we exhaustively explore all valid circuit diagrams containing exactly six CNOT gates to successfully execute the swap gate for (123), by explaining the equivalence classes in Remark 6 and Table 2. We conclude them in Theorem 7.To extend our analysis to the multiqubit scenario, we present the reducible and irreducible permutation elements in Definition 8. We clarify the equivalence between rows in the multi-qubit space and provide an approximate upper bound for multi-qubits to perform the aforementioned operations in Theorem 9. The comprehensive exploration of this paper aims to pave the way for further advancements in understanding quantum circuit optimization via multiple use of a specific two-qubit gate.

The CNOT-complexity of an invertible matrix over

\mathbb{F}_2

is the minimum number of CNOT gates needed to synthesize the corresponding linear reversible operator. While the maximum CNOT-complexity over all

n \times n

matrices is known to be

Θ(n^2 / \log n)

, no explicit family of matrices requiring a superlinear number of CNOT gates is known, and until now the hardest explicitly known family has been the cyclic permutations, with CNOT-complexity

3(n-1)

. We show that lower bounds for the additive complexity of not-necessarily-reversible linear operators can be lifted to the reversible setting with only a small loss. As an application, we use this to describe an explicit family of matrices, constructed from parity-check matrices of error-correcting codes, with CNOT-complexity at least

4n - o(n)

, asymptotically surpassing the cyclic permutations. Moreover, this construction yields an explicit matrix

A \in \mathrm{GL}_{n}(\mathbb{F}_2)

,

n = 17167

, whose CNOT-complexity exceeds that of the cyclic permutation on

n

symbols.

CNOT optimization plays a significant role in noise reduction for Quantum Circuits. Several heuristic and exact approaches exist for CNOT optimization. In this paper, we investigate more complicated variations of optimal synthesis by allowing qubit permutations and handling layout restrictions. We encode such problems into Planning, SAT, and QBF. We provide optimization for both CNOT gate count and circuit depth. For experimental evaluation, we consider standard T-gate optimized benchmarks and optimize CNOT sub-circuits. We show that allowing qubit permutations can further reduce up to 56% in CNOT count and 46% in circuit depth. In the case of optimally mapped circuits under layout restrictions, we observe a reduction up to 17% CNOT count and 19% CNOT depth.

Entangling measurements can reduce the cost of learning many-body correlations. We consider classical shadows in which a fixed unitary on a

k

-qubit region is sandwiched between two layers of random single-qubit Clifford gates, and ask which middle unitary best estimates Pauli strings with full support on the region. Combining symplectic support counting with a constraint from operator-size parity, we prove that within this architecture the minimum squared shadow norm over all Clifford middle unitaries is

C_k^{\rm opt}=4\cdot 9^k/(3\cdot 5^k+3^k-6)

for odd

k

and

C_k^{\rm opt}=4\cdot 9^k/(3\cdot 5^k-3^k+2)

for even

k

. A dual-axis rotation circuit

U_*

attains this minimum for every

k

. Asymptotically

C_k^{\rm opt}\simeq(4/3)\cdot(9/5)^k

: the exponential base of Wu et al.'s contractive unitary is optimal, and the prefactor improves from

U_*

to

4/3

. For

1\leq k\leq7

, exact certificates show that

U_*

is optimal over the entire unitary group

\mathrm U(2^k)

, and we conjecture that this holds for every

k

.

A new Boolean-Phase swapping gate is presented with improved quantum generality and cost-effectiveness. Our swapping gate is termed the "p-SWAP gate", where p is the phase difference selected for a set of swapped qubits. The phase p is expressed in radians and

-π~{\leq}

p

{\leq}~+π

. The generality of p-SWAP gate is demonstrated for Phase applications for selected values of p and for Boolean applications when the value of p is ignored. The cost-effectiveness of p-SWAP gate follows from the lower quantum cost and depth of its final realized (transpiled) quantum circuit, when compared to the standard SWAP gate composed of three Feynman (CNOT) gates. Specifically, our presented p-SWAP gate utilizes only two CNOT gates. The quantum circuit of the p-SWAP gate is visually designed using our previously developed Bloch sphere approach. Experimentally, after transpilation for an IBM quantum computer, the transpiled p-SWAP gate shows an approximate 23% quantum cost reduction and an approximate 26% depth minimization compared to the transpiled standard SWAP gate.