Explicit Matrices over ${\mathbb{Z}}_2$ with CNOT and Row Complexity $4n-\mathrm{o}(n)$ and Local Logic Gates

Abstract

In this article, we present an explicit family of invertible $n\times n$ matrices over ${\mathbb{Z}}_2$ whose CNOT and row complexity is at least $4n-\text{o}(n)$; equivalently, reducing these matrices to the identity requires at least $4n-\text{o}(n)$ elementary row operations. Moreover, the same complexity lower bound holds in the stronger computational model where the CNOT gates are replaced by arbitrary local linear logic gates, namely arbitrary invertible linear transformations acting on pairs of coordinates. Let $G_n$ denote the permutation group generated by local logic gates acting on the set of binary strings of length $n$. We prove that $G_n$ is naturally isomorphic to the group of all invertible affine transformations of the vector space ${\mathbb{Z}}_2^n$, thus reducing the problem of estimating the quantum complexity of permutations in $G_n$ to the row reduction complexity of invertible matrices over ${\mathbb{Z}}_2$. As an application, we show that the permutations associated with our explicit matrices have quantum complexity at least $4n-\text{o}(n)$.

Topics & keywords