{"id":"arxiv/2607.22248","url":"https://arxiv.org/abs/2607.22248","tags":["quant-ph"],"score":0,"title":"Lower bounds for the CNOT-complexity of linear reversible operators","domain":"quant-ph","source":"arxiv","authors":["Søren Fuglede Jørgensen"],"reviews":0,"subject":"quant-ph","summary":"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 $Θ(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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-07-24","reactions":{}}