2026/08/04 by Antonio Acuaviva, Arturo Acuaviva, Pablo Acuaviva · 1 voice
Computer Science · Physics and Astronomy · #acm:68Q12 #cs.CC #msc:68Q12 #quant-ph
arxiv created 2026/08/04 · arxiv published 2026/08/04 · arxiv updated 2026/08/05
Given A\inGL(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 AG\inGL(2|V|+|E|+1,2) satisfying ℓCNOT(AG)=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 acyclic graph and applies projection--contraction operations, allowing cancellation and unrestricted reuse of intermediate parities. For this family, the optimum is unchanged by any finite number of clean or borrowed ancillary wires that must be restored. A polynomial-time decoder further yields NP-hardness of approximation within every fixed additive constant and, through an L-reduction from Minimum Vertex Cover on cubic graphs, APX-hardness of the associated CNOT-circuit optimisation problem.