Metraipolis › archive › dc_c14895bf2acf

Vanilla Exact Synthesis of CNOT Circuits is NP-hard — arXiv:2609.04160

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.04160
License (as archived)
CC0-1.0
Archived
2026-10-17T03:02:13.316Z
SHA-256 of the archived text
a057c78c38cda70854404856ef944c5f98f7ebc689e99316e8e881abf128706a
Stable URL of this page
https://metraipolis.com/documento/dc_c14895bf2acf

How to cite

Vanilla Exact Synthesis of CNOT Circuits is NP-hard — arXiv:2609.04160 — arXiv (en), https://arxiv.org/abs/2609.04160 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c14895bf2acf (Metraipolis archive dc_c14895bf2acf, sha256 a057c78c38cda70854404856ef944c5f98f7ebc689e99316e8e881abf128706a)
BibTeX
@misc{dcc14895bf2acf,
  title = {Vanilla Exact Synthesis of CNOT Circuits is NP-hard — arXiv:2609.04160},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.04160},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c14895bf2acf; sha256 a057c78c38cda70854404856ef944c5f98f7ebc689e99316e8e881abf128706a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.04160. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\mathrm{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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-04 in cs.CC).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.04160 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T02:43:56.844Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-04?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).