{"id":"arxiv/2608.03825","url":"https://arxiv.org/abs/2608.03825","tags":["quant-ph","cs.CC"],"score":0,"title":"CNOT-Distance is NP-complete under all-to-all connectivity","domain":"quant-ph","source":"arxiv","authors":["Antonio Acuaviva","Arturo Acuaviva","Pablo Acuaviva"],"reviews":0,"subject":"quant-ph","summary":"Given $A\\in\\operatorname{GL}(N,2)$ and an integer $K$, we ask whether $A$ can be implemented by at most $K$ CNOT gates on fixed labelled wires with all-to-all connectivity. We prove that this problem is NP-complete. From a finite simple graph $G=(V,E)$, we construct an upper-unitriangular matrix $A_G\\in\\operatorname{GL}(2|V|+|E|+1,2)$ satisfying $\\ell_{\\mathrm{CNOT}}(A_G)=2|V|+2|E|+τ(G)$, where $τ(G)$ is the minimum vertex-cover size. Each target matrix has $O(N)$ nonzero entries and row Hamming weight at most four. The lower bound unfolds an arbitrary CNOT circuit into an XOR directed…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-08-04","reactions":{}}