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

Sherry Gong, Andrew Yu

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, reduc…