Lower bounds for the CNOT-complexity of linear reversible operators

Abstract:The CNOT-complexity of an invertible matrix over $\mathbb{F}_2$ is the minimum number of CNOT gates needed to synthesize the corresponding linear reversible operator. While the maximum CNOT-complexity over all $n \times n$ matrices is known to be $\Theta(n^2 / \log n)$, no explicit family of matrices requiring a superlinear number of CNOT gates is known, and until now the hardest explicitly known family has been the cyclic permutations, with CNOT-complexity $3(n-1)$. We show that lower bounds for the additive complexity of not-necessarily-reversible linear operators can be lifted to the reversible setting with only a small loss. As an application, we use this to describe an explicit family of matrices, constructed from parity-check matrices of error-correcting codes, with CNOT-complexity at least $4n - o(n)$, asymptotically surpassing the cyclic permutations. Moreover, this construction yields an explicit matrix $A \in \mathrm{GL}_{n}(\mathbb{F}_2)$, $n = 17167$, whose CNOT-complexity exceeds that of the cyclic permutation on $n$ symbols.

arXiv:2607.22248 [quant-ph]

(or arXiv:2607.22248v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2607.22248 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.