CNOT-Distance is NP-complete under all-to-all connectivity

Antonio Acuaviva, Arturo Acuaviva, Pablo Acuaviva

Given $A\in \mathrm{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 prov…