{"id":"arxiv/2609.04160","url":"https://arxiv.org/abs/2609.04160","tags":["quant-ph","cs.CC"],"score":0,"title":"Vanilla Exact Synthesis of CNOT Circuits is NP-hard","domain":"quant-ph","source":"arxiv","authors":["Chenjian Li","Ji Guan"],"reviews":0,"subject":"quant-ph","summary":"Exact CNOT synthesis seeks a minimum-size circuit implementing a given invertible binary linear transformation. We study its vanilla formulation: synthesis from the identity on fixed labeled qubits, without ancillas and with all-to-all connectivity. We prove that this problem is NP-hard and that its bounded decision version is NP-complete. Hardness persists even for unitriangular targets that are low-rank perturbations of the identity and under near-linear gate budgets. Our proof gives a polynomial-time reduction from the NP-complete Hamiltonian path problem on grid graphs. A unary hypercube…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-03","reactions":{}}