Researchers have established a new lower bound for the complexity of row reduction operations in binary matrices and the complexity of quantum logic gates. They have identified an explicit family of invertible $n \times n$ matrices over the field $\mathbb Z_2$ that require at least $4n-\text{o}(n)$ elementary row operations to be reduced to the identity matrix. This result is significant as it sets a strict lower bound for the efficiency with which certain types of quantum information can be manipulated.

The study also extends this lower complexity bound to a more powerful computational model. In this model, CNOT (Control-NOT) gates, fundamental in quantum computing, are replaced by arbitrary local linear logic gates. These gates are invertible linear transformations acting on pairs of coordinates, making them more general than CNOTs. Despite this increased flexibility, the $4n-\text{o}(n)$ lower bound still holds, highlighting the inherent difficulty of these operations.

As an application of their findings, the researchers demonstrated that the group $G_n$, generated by these local logic gates acting on binary strings of length $n$, is isomorphic to the group of all invertible affine transformations of the vector space $\mathbb Z_2^n$. This equivalence allows the problem of estimating the quantum complexity of permutations in $G_n$ to be translated into the problem of row reduction complexity for invertible matrices over $\mathbb Z_2$. On this basis, the permutations associated with the explicit matrices presented have a quantum complexity of at least $4n-\text{o}(n)$.