Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2607.22248

Lower bounds for the CNOT-complexity of linear reversible operators

Søren Fuglede Jørgensen

quant-phSubmitted Jul 24, 2026• Announced Jul 27, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Related papers

Explicit Matrices over $\mathbb Z_2$ with CNOT and Row Complexity $4n-\mathrm{o}(n)$ and Local Logic Gates

Sherry Gong, Andrew Yu

In this article, we present an explicit family of invertible $n\times n$ matrices over $\mathbb Z_2$ whose CNOT and row complexity is at least $4n-\text{o}(n)$; equivalently, reducing these matrices to the identity requires at least $4n-\text{o}(n)$ elementary row operations. Moreover, the same complexity lower bound holds in the stronger computational model where the CNOT gates are replaced by arbitrary local linear logic gates, namely arbitrary invertible linear transformations acting on pairs of coordinates. Let $G_n$ denote the permutation group generated by local logic gates acting on the set of binary strings of length $n$. We prove that $G_n$ is naturally isomorphic to the group of all invertible affine transformations of the vector space $\mathbb Z_2^n$, thus reducing the problem of estimating the quantum complexity of permutations in $G_n$ to the row reduction complexity of invertible matrices over $\mathbb Z_2$. As an application, we show that the permutations associated with our explicit matrices have quantum complexity at least $4n-\text{o}(n)$.

quant-pharXiv:2607.28598•Jul 31, 2026•0 citations

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

CNOT-Distance is NP-complete under all-to-all connectivity

Antonio Acuaviva, Arturo Acuaviva, Pablo Acuaviva

Given $A\in\operatorname{GL}(N,2)$ and an integer $K$, we ask whether $A$ can be implemented by at most $K$ CNOT gates on fixed labelled wires with all-to-all connectivity. We prove that this problem is NP-complete. From a finite simple graph $G=(V,E)$, we construct an upper-unitriangular matrix $A_G\in\operatorname{GL}(2|V|+|E|+1,2)$ satisfying $\ell_{\mathrm{CNOT}}(A_G)=2|V|+2|E|+τ(G)$, where $τ(G)$ is the minimum vertex-cover size. Each target matrix has $O(N)$ nonzero entries and row Hamming weight at most four. The lower bound unfolds an arbitrary CNOT circuit into an XOR directed acyclic graph and applies projection--contraction operations, allowing cancellation and unrestricted reuse of intermediate parities. For this family, the optimum is unchanged by any finite number of clean or borrowed ancillary wires that must be restored. A polynomial-time decoder further yields NP-hardness of approximation within every fixed additive constant and, through an L-reduction from Minimum Vertex Cover on cubic graphs, APX-hardness of the associated CNOT-circuit optimisation problem.

quant-pharXiv:2608.03825•Aug 5, 2026•0 citations

The exact lower bound of CNOT-complexity for fault-tolerant quantum Fourier transform

Qiqing Xia, Huiqin Xie, Yang, Li

The quantum Fourier transform (QFT) is a crucial subroutine in many quantum algorithms. In this paper, we study the exact lower bound problem of CNOT gate complexity for fault-tolerant QFT. First, we consider approximating the ancilla-free controlled-$R_k$ in the QFT logical circuit with a standard set of universal gates, aiming to minimize the number of T gates. Various single-qubit gates are generated in addition to CNOT gates when the controlled-$R_k$ is decomposed in different ways, we propose an algorithm that combines numerical and analytical methods to exactly compute the minimum T gate count for approximating any single-qubit gate with any given accuracy. Afterwards, we prove that the exact lower bound problem of T gate complexity for the QFT is NP-complete. Furthermore, we provide the transversal implementation of universal quantum gates and prove that it has the minimum number of CNOT gates and analyze the minimum CNOT count for transversally implementing the T gate. We then exactly compute the exact lower bound of CNOT gate complexity for fault-tolerant QFT with the current maximum fault-tolerant accuracy 10^{-2}. Our work can provide a reference for designing algorithms based on active defense in a quantum setting.

arXiv:2409.02506•Sep 4, 2024•0 citations

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

B Zhang

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.

Quantum Reports•Jun 22, 2026•0 citations

Qubit Routing for (Almost) Free

Arianne Meijer-van de Griend

In this paper, we give a mathematical proof that bounds the number of CNOT gates required to synthesize an $n$ qubit phase polynomial with $g$ terms to be at least $O(\frac{gn}{\max (\log g, 1)})$ and at most $O(gn)$. However, when targeting restricted hardware, not all CNOTs are allowed. If we were to use SWAP-based methods to route the qubits on the architecture such that the earlier synthesized gates are natively allowed, we increase the number of CNOTs by a routing overhead factor of $O(\log n) \leq α\leq O(n \log^2 n)$. However, if we only synthesize allowed gates, we do not need to route any qubits. Moreover, in that case the routing overhead factor is $1 \leq α\leq 4 \simeq O(1)$. Additionally, since phase polynomials and Hadamard gates together form a universal gate set, we get qubit routing for almost free.

quant-pharXiv:2604.19717•Apr 22, 2026•0 citations
The CNOT-complexity of an invertible matrix over F2\mathbb{F}_2F2​ is the minimum number of CNOT gates needed to synthesize the corresponding linear reversible operator. While the maximum CNOT-complexity over all n×nn \times nn×n matrices is known to be Θ(n2/log⁡n)Θ(n^2 / \log n)Θ(n2/logn), 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)3(n-1)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)4n - o(n)4n−o(n), asymptotically surpassing the cyclic permutations. Moreover, this construction yields an explicit matrix A∈GLn(F2)A \in \mathrm{GL}_{n}(\mathbb{F}_2)A∈GLn​(F2​), n=17167n = 17167n=17167, whose CNOT-complexity exceeds that of the cyclic permutation on nnn symbols.
Explicit Matrices over Z2\mathbb Z_2Z2​ with CNOT and Row Complexity 4n−o(n)4n-\mathrm{o}(n)4n−o(n) and Local Logic Gates
In this article, we present an explicit family of invertible n×nn\times nn×n matrices over Z2\mathbb Z_2Z2​ whose CNOT and row complexity is at least 4n−o(n)4n-\text{o}(n)4n−o(n); equivalently, reducing these matrices to the identity requires at least 4n−o(n)4n-\text{o}(n)4n−o(n) elementary row operations. Moreover, the same complexity lower bound holds in the stronger computational model where the CNOT gates are replaced by arbitrary local linear logic gates, namely arbitrary invertible linear transformations acting on pairs of coordinates. Let GnG_nGn​ denote the permutation group generated by local logic gates acting on the set of binary strings of length nnn. We prove that GnG_nGn​ is naturally isomorphic to the group of all invertible affine transformations of the vector space Z2n\mathbb Z_2^nZ2n​, thus reducing the problem of estimating the quantum complexity of permutations in GnG_nGn​ to the row reduction complexity of invertible matrices over Z2\mathbb Z_2Z2​. As an application, we show that the permutations associated with our explicit matrices have quantum complexity at least 4n−o(n)4n-\text{o}(n)4n−o(n).
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 nnn qubits with kkk cycles requires exactly 3(n−k)3(n-k)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∗A^*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∗A^*A∗ heuristics to improve the CNOT counts obtained through heuristic search.
Given A∈GL⁡(N,2)A\in\operatorname{GL}(N,2)A∈GL(N,2) and an integer KKK, we ask whether AAA can be implemented by at most KKK CNOT gates on fixed labelled wires with all-to-all connectivity. We prove that this problem is NP-complete. From a finite simple graph G=(V,E)G=(V,E)G=(V,E), we construct an upper-unitriangular matrix AG∈GL⁡(2∣V∣+∣E∣+1,2)A_G\in\operatorname{GL}(2|V|+|E|+1,2)AG​∈GL(2∣V∣+∣E∣+1,2) satisfying ℓCNOT(AG)=2∣V∣+2∣E∣+τ(G)\ell_{\mathrm{CNOT}}(A_G)=2|V|+2|E|+τ(G)ℓCNOT​(AG​)=2∣V∣+2∣E∣+τ(G), where τ(G)τ(G)τ(G) is the minimum vertex-cover size. Each target matrix has O(N)O(N)O(N) nonzero entries and row Hamming weight at most four. The lower bound unfolds an arbitrary CNOT circuit into an XOR directed acyclic graph and applies projection--contraction operations, allowing cancellation and unrestricted reuse of intermediate parities. For this family, the optimum is unchanged by any finite number of clean or borrowed ancillary wires that must be restored. A polynomial-time decoder further yields NP-hardness of approximation within every fixed additive constant and, through an L-reduction from Minimum Vertex Cover on cubic graphs, APX-hardness of the associated CNOT-circuit optimisation problem.
The quantum Fourier transform (QFT) is a crucial subroutine in many quantum algorithms. In this paper, we study the exact lower bound problem of CNOT gate complexity for fault-tolerant QFT. First, we consider approximating the ancilla-free controlled-RkR_kRk​ in the QFT logical circuit with a standard set of universal gates, aiming to minimize the number of T gates. Various single-qubit gates are generated in addition to CNOT gates when the controlled-RkR_kRk​ is decomposed in different ways, we propose an algorithm that combines numerical and analytical methods to exactly compute the minimum T gate count for approximating any single-qubit gate with any given accuracy. Afterwards, we prove that the exact lower bound problem of T gate complexity for the QFT is NP-complete. Furthermore, we provide the transversal implementation of universal quantum gates and prove that it has the minimum number of CNOT gates and analyze the minimum CNOT count for transversally implementing the T gate. We then exactly compute the exact lower bound of CNOT gate complexity for fault-tolerant QFT with the current maximum fault-tolerant accuracy 10^{-2}. Our work can provide a reference for designing algorithms based on active defense in a quantum setting.
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.
In this paper, we give a mathematical proof that bounds the number of CNOT gates required to synthesize an nnn qubit phase polynomial with ggg terms to be at least O(gnmax⁡(log⁡g,1))O(\frac{gn}{\max (\log g, 1)})O(max(logg,1)gn​) and at most O(gn)O(gn)O(gn). However, when targeting restricted hardware, not all CNOTs are allowed. If we were to use SWAP-based methods to route the qubits on the architecture such that the earlier synthesized gates are natively allowed, we increase the number of CNOTs by a routing overhead factor of O(log⁡n)≤α≤O(nlog⁡2n)O(\log n) \leq α\leq O(n \log^2 n)O(logn)≤α≤O(nlog2n). However, if we only synthesize allowed gates, we do not need to route any qubits. Moreover, in that case the routing overhead factor is 1≤α≤4≃O(1)1 \leq α\leq 4 \simeq O(1)1≤α≤4≃O(1). Additionally, since phase polynomials and Hadamard gates together form a universal gate set, we get qubit routing for almost free.