Lower bounds for the CNOT-complexity of linear reversible operators

• URL: http://arxiv.org/abs/2607.22248v1
• Date: Fri, 24 Jul 2026 12:31:18 GMT
• Title: Lower bounds for the CNOT-complexity of linear reversible operators
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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

• CNOT-Distance is NP-complete under all-to-all connectivity [0.69670060449041]
  We show that $A$ can be implemented by at most $K$ CNOT gates on fixed labelled wires with all-to-all connectivity.<n>We prove that this problem is NP-complete.
  arXiv  Detail & Related papers  (2026-08-04T15:34:26Z)
• Explicit Matrices over $\mathbb Z_2$ with CNOT and Row Complexity $4n-\mathrm{o}(n)$ and Local Logic Gates [0.0]
  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.
  arXiv  Detail & Related papers  (2026-07-30T17:48:15Z)
• 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)
• The tetrahedral Horn problem and asymptotics of U(n) 6j symbols [2.2633707287259868]
  Horn's problem is concerned with characterizing the eigenvalues $(a,b,c,d,e,f)$ of Hermitian matrices $(A,B,C,D,E,F)$.<n>This paper aims to characterize the tetrashedra eigenvalues $(a,b,c,d,e,f)$ of Hermitian matrices $(A,B,C,D,E,F)$ forming the edges of a tetrahedron.
  arXiv  Detail & Related papers  (2025-10-06T15:00:25Z)
• New Hardness Results for Low-Rank Matrix Completion [2.7624021966289605]
  The paper presents new $mathsfNP $-hardness results for low-rank matrix completion problems.<n>We show that for every sufficiently large integer $d$ and any real number $varepsilon in [ 2-O(d),frac17]$, given a partial matrix $A$ with exposed values of magnitude at most $1$ that admits a positive semi-definite completion of rank $d$, it is $mathsfNP$-hard to find a positive semi-definite matrix.<n>Our proofs involve a
  arXiv  Detail & Related papers  (2025-06-23T09:22:28Z)
• Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
  We give a new algorithm for decomposing an $n_times n times n_3$ tensor as the sum of a minimal number of rank-1 terms.<n>We show that an even more general class of degree-$d$s cannot surpass rank $Cn$ for a constant $C = C(d)$.
  arXiv  Detail & Related papers  (2024-11-21T17:41:09Z)
• 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)
• Word Linear Complexity of sequences and Local Inversion of maps over finite fields [0.0]
  This paper develops the notion of vector valued sequences over finite fields $ff$ as an extension of Linear Complexity$ of their ensembles. It shows that the matrix minimal can be used with iteratively generated vector valued by maps $F:ffn at a given $ffn$ in $ffn$ for solving the unique local inverse $x$ in $ffn$ when the sequence is periodic.
  arXiv  Detail & Related papers  (2023-11-11T14:06:23Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• Low-rank Matrix Recovery With Unknown Correspondence [62.634051913953485]
  We show that it is possible to recover $M$ via solving a nuclear norm minimization problem under a proper low-rank condition on $M$, with provable non-asymptotic error bound for the recovery of $M$. Experiments on simulated data, the MovieLens 100K dataset and Yale B database show that $textM3textO achieves state-of-the-art performance over several baselines and can recover the ground-truth correspondence with high accuracy.
  arXiv  Detail & Related papers  (2021-10-15T09:27:50Z)
• On Fast Johnson-Lindernstrauss Embeddings of Compact Submanifolds of $\mathbb{R}^N$ with Boundary [0.4125187280299246]
  We consider the probability that a random matrix $A in mathbbRm times N$ will serve as a bi-Lipschitz function $A: mathcalM rightarrow mathbbRm$ with bi-Lipschitz constants close to one. We present a new class of highly structured distributions for embedding sufficiently low-dimensional submanifolds of $mathbbRN$.
  arXiv  Detail & Related papers  (2021-10-08T15:27:52Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Algebraic and geometric structures inside the Birkhoff polytope [0.0]
  Birkhoff polytope $mathcalB_d$ consists of all bistochastic matrices of order $d$. We prove that $mathcalL_d$ and $mathcalF_d$ are star-shaped with respect to the flat matrix.
  arXiv  Detail & Related papers  (2021-01-27T09:51:24Z)

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.