Vanilla Exact Synthesis of CNOT Circuits is NP-hard
Abstract
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 embedding translates graph vertices into circuit parities and edge traversals into CNOT updates. The central challenge is that Hamiltonian paths require intermediate vertex visits, whereas exact synthesis constrains only the final transformation. We bridge this gap with a replicated recorder qubits construction that encodes the required parities in the final outputs, together with a tight gate budget that forces every sufficiently short implementation to trace a Hamiltonian path. Crucially, this path structure is enforced by the construction rather than imposed as a restriction on the circuit. The result directly implies NP-hardness for shortest word problem and Cayley-graph distance computation over GL(n,2) with elementary transvections as generators, as well as fixed-width sequential XOR program minimization. For CNOT-minimal exact phase polynomial synthesis, it yields NP-hardness with a zero phase polynomial; extending the reduction to grid-graph Hamiltonian cycle problem establishes hardness even when the final linear transformation is the identity. These complementary results show that the linear and phase components each independently suffice for NP-hardness of exact phase polynomial synthesis.
Related
- Fast verification of fault tolerant magic state preparation circuits with the CNOT + T gate set
- Sampling hard circuits with verifiably high fidelity
- Exact quantum circuits for a Heisenberg triangle with Dzyaloshinskii-Moriya interaction
- Exact verification of Givens rotation circuits for efficient quantum phase estimation of iron-sulfur clusters
- Scalable Exact Non-Pauli Noise Simulation for Fault-Tolerant Quantum Circuits
BibTeX
@misc{li2026vanilla,
title = {{Vanilla Exact Synthesis of CNOT Circuits is NP-hard}},
author = {Chenjian Li and Ji Guan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.04160},
eprint = {2609.04160},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04160},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Vanilla Exact Synthesis of CNOT Circuits is NP-hard
AU - Chenjian Li
AU - Ji Guan
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2609.04160
UR - https://arxiv.org/abs/2609.04160
AB - 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 embedding translates graph vertices into circuit parities and edge traversals into CNOT updates. The central challenge is that Hamiltonian paths require intermediate vertex visits, whereas exact synthesis constrains only the final transformation. We bridge this gap with a replicated recorder qubits construction that encodes the required parities in the final outputs, together with a tight gate budget that forces every sufficiently short implementation to trace a Hamiltonian path. Crucially, this path structure is enforced by the construction rather than imposed as a restriction on the circuit. The result directly implies NP-hardness for shortest word problem and Cayley-graph distance computation over GL(n,2) with elementary transvections as generators, as well as fixed-width sequential XOR program minimization. For CNOT-minimal exact phase polynomial synthesis, it yields NP-hardness with a zero phase polynomial; extending the reduction to grid-graph Hamiltonian cycle problem establishes hardness even when the final linear transformation is the identity. These complementary results show that the linear and phase components each independently suffice for NP-hardness of exact phase polynomial synthesis.
ER -