2026/07/30 by Sherry Gong, Andrew Yu
Mathematics · Physics and Astronomy · #math.CO #quant-ph
In this article, we present an explicit family of invertible n× n matrices over \mathbb Z2 whose CNOT and row complexity is at least 4n-o(n); equivalently, reducing these matrices to the identity requires at least 4n-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 Gn denote the permutation group generated by local logic gates acting on the set of binary strings of length n. We prove that Gn is naturally isomorphic to the group of all invertible affine transformations of the vector space \mathbb Z2n, thus reducing the problem of estimating the quantum complexity of permutations in Gn to the row reduction complexity of invertible matrices over \mathbb Z2. As an application, we show that the permutations associated with our explicit matrices have quantum complexity at least 4n-o(n).