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.28598

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

Sherry Gong, Andrew Yu

quant-phmath.COSubmitted Jul 30, 2026• Announced Jul 31, 2026• 2 citations
arXivHTMLPDF

Abstract

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)$.

Related papers

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•4 citations

Quantum complexity of permutations

Andrew T. Yu

Let $S_n$ be the symmetric group of all permutations of $\{1, \cdots, n\}$ with two generators: the transposition switching $1$ with $2$ and the cyclic permutation sending $k$ to $k+1$ for $1\leq k\leq n-1$ and $n$ to $1$ (denoted by $σ$ and $τ$). In this article, we study quantum complexity of permutations in $S_n$ using $\{σ, τ, τ^{-1}\}$ as logic gates. We give an explicit construction of permutations in $S_n$ with quadratic quantum complexity lower bound $\frac{n^2-2n-7}{4}$. We also prove that all permutations in $S_n$ have quadratic quantum complexity upper bound $3(n-1)^2$. Finally, we show that almost all permutations in $S_n$ have quadratic quantum complexity lower bound when $n\rightarrow \infty$.

arXiv:2207.14102•Pure and Applied Mathematics Quarterly•Jan 1, 2023•1 citation

On the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates

Dmitry Vladimirovich Zakablukov

Abstract The paper is concerned with the problem of complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates. For a reversible circuit implementing a map f : Z 2 n → Z 2 n $f: \mathbb Z_2^n\, \to\, \mathbb Z_2^n$ we define the Shannon complexity function L ( n , q ) as a function of n and the number q of additional inputs in the circuit. We prove the lower estimate L ( n , q ) ⩾ 2 n ( n − 2 ) 3 log 2 ⁡ ( n + q ) − n 3 $L(n,q)\, \geqslant\, \displaystyle\frac{2^n(n-2)}{3\log_2(n+q)} - \frac{n}{3}$ for the complexity of a reversible circuit and derive the upper estimate L ( n , 0) ⩽ 48 n 2 n (1 + o (1)) / log 2 n if there are no additional inputs. The asymptotic upper estimate for the complexity is shown to be L ( n , q 0 ) ≲ 2 n with q 0 ∽ n 2 n − o ( n ) additional inputs.

arXiv:1412.2662•Discrete Mathematics and Applications•Feb 1, 2017•6 citations

Asymptotic bounds of depth for a reversible circuit consisting of NOT, CNOT and 2-CNOT gates

Dmitry Vladimirovich Zakablukov

The paper discusses the asymptotic depth of a reversible circuit consisting of NOT, CNOT and 2-CNOT gates. Reversible circuit depth function $D(n, q)$ for a circuit implementing a transformation $f\colon \mathbb Z_2^n \to \mathbb Z_2^n$ is introduced as a function of $n$ and the number of additional inputs $q$. It is proved that for the case of implementing a permutation from $A(\mathbb Z_2^n)$ with a reversible circuit having no additional inputs the depth is bounded as $D(n, 0) \gtrsim 2^n / (3\log_2 n)$. It is proved that for the case of implementing a transformation $f\colon \mathbb Z_2^n \to \mathbb Z_2^n$ with a reversible circuit having $q_0 \sim 2^n$ additional inputs the depth is bounded as $D(n, q_0) \lesssim 3n$.

arXiv:1501.04344•Jan 18, 2015•0 citations

Vanilla Exact Synthesis of CNOT Circuits is NP-hard

Chenjian Li, Ji Guan

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 $\mathrm{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.

quant-pharXiv:2609.04160•Sep 4, 2026•3 citations

Arbitrary two-qubit computation in 23 elementary gates

Stephen S. Bullock, Igor L. Markov

We address the problem of constructing quantum circuits to implement an arbitrary two-qubit quantum computation. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least $17$ gates: $15$ one-qubit rotations and $2$ controlled-NOT (CNOT) gates. We also constructively prove a worst-case upper bound of $23$ elementary gates, of which at most four (CNOT gates) entail multiqubit interactions. Our analysis shows that synthesis algorithms suggested in previous work, although more general, entail larger quantum circuits than ours in the special case of two qubits. One such algorithm has a worst case of $61$ gates, of which $18$ may be CNOT gates.

arXiv:quant-ph/0211002•Physical Review A•Jul 22, 2003•60 citations
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).
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.
Let SnS_nSn​ be the symmetric group of all permutations of {1,⋯ ,n}\{1, \cdots, n\}{1,⋯,n} with two generators: the transposition switching 111 with 222 and the cyclic permutation sending kkk to k+1k+1k+1 for 1≤k≤n−11\leq k\leq n-11≤k≤n−1 and nnn to 111 (denoted by σσσ and τττ). In this article, we study quantum complexity of permutations in SnS_nSn​ using {σ,τ,τ−1}\{σ, τ, τ^{-1}\}{σ,τ,τ−1} as logic gates. We give an explicit construction of permutations in SnS_nSn​ with quadratic quantum complexity lower bound n2−2n−74\frac{n^2-2n-7}{4}4n2−2n−7​. We also prove that all permutations in SnS_nSn​ have quadratic quantum complexity upper bound 3(n−1)23(n-1)^23(n−1)2. Finally, we show that almost all permutations in SnS_nSn​ have quadratic quantum complexity lower bound when n→∞n\rightarrow \inftyn→∞.
Abstract The paper is concerned with the problem of complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates. For a reversible circuit implementing a map f : Z 2 n → Z 2 n f:Z2n → Z2nf: \mathbb Z_2^n\, \to\, \mathbb Z_2^nf:Z2n​→Z2n​ we define the Shannon complexity function L ( n , q ) as a function of n and the number q of additional inputs in the circuit. We prove the lower estimate L ( n , q ) ⩾ 2 n ( n − 2 ) 3 log 2 ⁡ ( n + q ) − n 3 L(n,q) ⩾ 2n(n−2)3log⁡2(n+q)−n3L(n,q)\, \geqslant\, \displaystyle\frac{2^n(n-2)}{3\log_2(n+q)} - \frac{n}{3}L(n,q)⩾3log2​(n+q)2n(n−2)​−3n​ for the complexity of a reversible circuit and derive the upper estimate L ( n , 0) ⩽ 48 n 2 n (1 + o (1)) / log 2 n if there are no additional inputs. The asymptotic upper estimate for the complexity is shown to be L ( n , q 0 ) ≲ 2 n with q 0 ∽ n 2 n − o ( n ) additional inputs.
The paper discusses the asymptotic depth of a reversible circuit consisting of NOT, CNOT and 2-CNOT gates. Reversible circuit depth function D(n,q)D(n, q)D(n,q) for a circuit implementing a transformation f ⁣:Z2n→Z2nf\colon \mathbb Z_2^n \to \mathbb Z_2^nf:Z2n​→Z2n​ is introduced as a function of nnn and the number of additional inputs qqq. It is proved that for the case of implementing a permutation from A(Z2n)A(\mathbb Z_2^n)A(Z2n​) with a reversible circuit having no additional inputs the depth is bounded as D(n,0)≳2n/(3log⁡2n)D(n, 0) \gtrsim 2^n / (3\log_2 n)D(n,0)≳2n/(3log2​n). It is proved that for the case of implementing a transformation f ⁣:Z2n→Z2nf\colon \mathbb Z_2^n \to \mathbb Z_2^nf:Z2n​→Z2n​ with a reversible circuit having q0∼2nq_0 \sim 2^nq0​∼2n additional inputs the depth is bounded as D(n,q0)≲3nD(n, q_0) \lesssim 3nD(n,q0​)≲3n.
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)\mathrm{GL}(n,2)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.
We address the problem of constructing quantum circuits to implement an arbitrary two-qubit quantum computation. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 171717 gates: 151515 one-qubit rotations and 222 controlled-NOT (CNOT) gates. We also constructively prove a worst-case upper bound of 232323 elementary gates, of which at most four (CNOT gates) entail multiqubit interactions. Our analysis shows that synthesis algorithms suggested in previous work, although more general, entail larger quantum circuits than ours in the special case of two qubits. One such algorithm has a worst case of 616161 gates, of which 181818 may be CNOT gates.