Lower bounds for the CNOT-complexity of linear reversible operators

2026/07/24 by Søren Fuglede Jørgensen
#quant-ph

paper · pdf

Abstract

The CNOT-complexity of an invertible matrix over \mathbbF₂ 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 Θ(n² / 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 ∈ GL_n(\mathbbF₂), n = 17167, whose CNOT-complexity exceeds that of the cyclic permutation on n symbols.

Related

• Explicit Matrices over \mathbb Z₂ with CNOT and Row Complexity 4n-o(n) and Local Logic Gates
• On Synthesis of Reversible Circuits with Small Number of Additional Inputs Consisting of NOT, CNOT and 2-CNOT Gates
• General Upper Bounds for Gate Complexity and Depth of Reversible Circuits Consisting of NOT, CNOT and 2-CNOT Gates
• On Asymptotic Gate Complexity and Depth of Reversible Circuits Without\n Additional Memory
• On additive complexity of a sequence of matrices