Investigadores han establecido un nuevo límite inferior para la complejidad de las operaciones de reducción de filas en matrices binarias y la complejidad de las puertas lógicas cuánticas. Han identificado una familia explícita de matrices invertibles de $n \times n$ sobre el cuerpo $\mathbb Z_2$ que requieren al menos $4n-\text{o}(n)$ operaciones elementales de fila para ser reducidas a la matriz identidad. Este resultado es significativo porque establece una cota inferior estricta para la eficiencia con la que se pueden manipular ciertos tipos de información cuántica.

El estudio también extiende este límite inferior de complejidad a un modelo computacional más potente. En este modelo, las puertas CNOT (Control-NOT), fundamentales en la computación cuántica, son reemplazadas por puertas lógicas lineales locales arbitrarias. Estas puertas son transformaciones lineales invertibles que actúan sobre pares de coordenadas, lo que las hace más generales que las CNOT. A pesar de esta mayor flexibilidad, el límite inferior de $4n-\text{o}(n)$ se mantiene, lo que subraya la dificultad inherente de estas operaciones.

Como aplicación de sus hallazgos, los investigadores demostraron que el grupo $G_n$, generado por estas puertas lógicas locales que actúan sobre cadenas binarias de longitud $n$, es isomorfo al grupo de todas las transformaciones afines invertibles del espacio vectorial $\mathbb Z_2^n$. Esta equivalencia permite traducir el problema de estimar la complejidad cuántica de las permutaciones en $G_n$ al problema de la complejidad de reducción de filas de matrices invertibles sobre $\mathbb Z_2$. Con esta base, las permutaciones asociadas a las matrices explícitas presentadas tienen una complejidad cuántica de al menos $4n-\text{o}(n)$.