Lower bounds for the CNOT-complexity of linear reversible operators

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