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)$.
Explicit Matrices over Z2 with CNOT and Row Complexity 4n−o(n) and Local Logic Gates
In this article, we present an explicit family of invertible n×n matrices over Z2 whose CNOT and row complexity is at least 4n−o(n); equivalently, reducing these matrices to the identity requires at least 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 Gn denote the permutation group generated by local logic gates acting on the set of binary strings of length n. We prove that Gn is naturally isomorphic to the group of all invertible affine transformations of the vector space Z2n, thus reducing the problem of estimating the quantum complexity of permutations in Gn to the row reduction complexity of invertible matrices over Z2. As an application, we show that the permutations associated with our explicit matrices have quantum complexity at least 4n−o(n).
The CNOT-complexity of an invertible matrix over F2 is the minimum number of CNOT gates needed to synthesize the corresponding linear reversible operator. While the maximum CNOT-complexity over all n×n matrices is known to be Θ(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). 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∈GLn(F2), n=17167, whose CNOT-complexity exceeds that of the cyclic permutation on n symbols.
Let Sn be the symmetric group of all permutations of {1,⋯,n} with two generators: the transposition switching 1 with 2 and the cyclic permutation sending k to k+1 for 1≤k≤n−1 and n to 1 (denoted by σ and τ). In this article, we study quantum complexity of permutations in Sn using {σ,τ,τ−1} as logic gates. We give an explicit construction of permutations in Sn with quadratic quantum complexity lower bound 4n2−2n−7. We also prove that all permutations in Sn have quadratic quantum complexity upper bound 3(n−1)2. Finally, we show that almost all permutations in Sn have quadratic quantum complexity lower bound when n→∞.
We investigate the groups generated by the sets of CP, CNOT and SWAPα (power-of-SWAP) quantum gate operations acting on n qubits. Isomorphisms to standard groups are found, and using techniques from representation theory, we are able to determine the invariant subspaces of the n−qubit Hilbert space under the action of each group. For the CP operation, we find isomorphism to the direct product of n(n−1)/2 cyclic groups of order 2, and determine 2n1-dimensional invariant subspaces corresponding to the computational state-vectors. For the CNOT operation, we find isomorphism to the general linear group of an n-dimensional space over a field of 2 elements, GL(n,2), and determine two 1-dimensional invariant subspaces and one (2n−2)-dimensional invariant subspace. For the SWAPα operation we determine a complex structure of invariant subspaces with varying dimensions and occurrences and present a recursive procedure to construct them. As an example of an application for our work, we suggest that these invariant subspaces can be used to construct simple formal verification procedures to assess the operation of quantum computers of arbitrary size.
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.
Exact CNOT synthesis seeks a minimum-size circuit implementing a given invertible binary linear transformation. We study its vanilla formulation: synthesis from the identity on fixed labeled qubits, without ancillas and with all-to-all connectivity. We prove that this problem is NP-hard and that its bounded decision version is NP-complete. Hardness persists even for unitriangular targets that are low-rank perturbations of the identity and under near-linear gate budgets. Our proof gives a polynomial-time reduction from the NP-complete Hamiltonian path problem on grid graphs. A unary hypercube embedding translates graph vertices into circuit parities and edge traversals into CNOT updates. The central challenge is that Hamiltonian paths require intermediate vertex visits, whereas exact synthesis constrains only the final transformation. We bridge this gap with a replicated recorder qubits construction that encodes the required parities in the final outputs, together with a tight gate budget that forces every sufficiently short implementation to trace a Hamiltonian path. Crucially, this path structure is enforced by the construction rather than imposed as a restriction on the circuit. The result directly implies NP-hardness for shortest word problem and Cayley-graph distance computation over GL(n,2) with elementary transvections as generators, as well as fixed-width sequential XOR program minimization. For CNOT-minimal exact phase polynomial synthesis, it yields NP-hardness with a zero phase polynomial; extending the reduction to grid-graph Hamiltonian cycle problem establishes hardness even when the final linear transformation is the identity. These complementary results show that the linear and phase components each independently suffice for NP-hardness of exact phase polynomial synthesis.
Given A∈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 AG∈GL(2∣V∣+∣E∣+1,2) satisfying ℓCNOT(AG)=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.