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

• URL: http://arxiv.org/abs/2607.28598v1
• Date: Thu, 30 Jul 2026 17:48:15 GMT
• Title: Explicit Matrices over $\mathbb Z_2$ with CNOT and Row Complexity $4n-\mathrm{o}(n)$ and Local Logic Gates
• Abstract summary: We present an explicit family of invertible $ntimes n$ matrices over $mathbb Zn$ whose CNOT and row complexity is at least $4n-texto(n)$.<n>The same complexity lower bound holds in the stronger computational model where the CNOT gates are replaced by arbitrary local linear logic gates.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 [0.0]
  The CNOT-complexity of an invertible matrix over $mathbbF$ is the minimum number of CNOT gates needed to synthesize the corresponding linear reversible operator.<n>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.
  arXiv  Detail & Related papers  (2026-07-24T12:31:18Z)
• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  Matrix chain multiplication is a problem in scientific computing, machine learning, and graph analysis.<n>We present emphTwo-Tower Matrix, a quantum subroutine that encodes the product $mathcalW$ of the $K$ matrices into a quantum state in circuit depth.
  arXiv  Detail & Related papers  (2026-07-14T18:42:40Z)
• Minimal Permutation-Invariant Qudit Codes from Edge-Colorings of Complete Graphs [4.297070083645049]
  We study permutation-invariant quantum codes in the symmetric subspace $mathrmSymn(mathbbCq) $ of $n$ qudits of local dimension $q$.<n>Four physical qudits suffice to encode one logical qudit with distance two in the symmetric sector for every local dimension.
  arXiv  Detail & Related papers  (2026-05-21T13:08:38Z)
• Time evolution of quantum gates and the necessity of complex numbers [0.0]
  We describe a simple scheme in which the effect of a quantum gate is described by the action of an effective Hamiltonian acting for some characteristic time.<n>The role of the complex phase in bringing about the entanglement of two qubits is also highlighted.<n>We investigate the endomorphism of real vector spaces of dimension $N = 2n$, where $n in mathbbZ+$, suitable for the modelling of $n-1$ qubits.
  arXiv  Detail & Related papers  (2026-04-18T17:47:56Z)
• Group Representational Position Encoding [66.33026480082025]
  We present GRAPE, a unified framework for positional encoding based on group actions.<n>Two families of mechanisms: (i) multiplicative rotations (Multiplicative GRAPE) in $mathrmSO(d)$ and (ii) additive logit biases (Additive GRAPE) arising from unipotent actions in the general linear group $mathrmGL$.
  arXiv  Detail & Related papers  (2025-12-08T18:39:13Z)
• An Efficient Computational Framework for Discrete Fuzzy Numbers Based on Total Orders [41.99844472131922]
  We introduce algorithms that exploit the structure of total (admissible) orders to compute the $textitpos$ function.<n>The proposed approach achieves a complexity of $mathcalO(n2 m log n)$, which is quadratic in the size of the underlying chain.<n>The results demonstrate that this formulation substantially reduces computational cost.
  arXiv  Detail & Related papers  (2025-11-21T09:35:07Z)
• High-Rank Irreducible Cartesian Tensor Decomposition and Bases of Equivariant Spaces [48.465738895704455]
  We construct path matrices for decomposition of Cartesian tensors up to rank $n=9$ with reduced and affordable complexity.<n>Our method avoids the RREF algorithm and maintains a fully analytical derivation of each ICT decomposition matrix.<n>We extend our result to the arbitrary tensor product and direct sum spaces, enabling free design between different spaces while keeping symmetry.
  arXiv  Detail & Related papers  (2024-12-24T08:25:38Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Scaling of symmetry-restricted quantum circuits [42.803917477133346]
  In this work, we investigate the properties of $mathcalMSU(2N)$, $mathcalM$-invariant subspaces of the special unitary Lie group $SU(2N)$.
  arXiv  Detail & Related papers  (2024-06-14T12:12:15Z)
• Polyadic sigma matrices [0.0]
  We generalize $sigma$-matrices to higher arities using the polyadization procedure proposed by the author. The presentation of $n$-ary $SUleft( 2right) $ in terms of full $Sigma$-matrices is done using the Hadamard product.
  arXiv  Detail & Related papers  (2024-03-28T12:19:46Z)
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  We propose quantum algorithms, purely quantum in nature, for calculating the determinant and inverse of an $(N-1)times (N-1)$ matrix.<n>The basic idea is to encode each row of the matrix into a pure state of some quantum system.
  arXiv  Detail & Related papers  (2024-01-29T23:23:27Z)
• Quantum Complexity of Permutations [0.0]
  We study quantum complexity of permutations in $S_n$ using $sigma, tau, tau-1$ as logic gates. We show that almost all permutations in $S_n$ have quadratic quantum complexity lower bound when $nrightarrow infty$.
  arXiv  Detail & Related papers  (2022-07-21T23:18:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.