Metraipolis › archive › dc_d6026a293ade

Clifford synthesis is NP-complete — arXiv:2610.40886

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.40886
License (as archived)
CC0-1.0
Archived
2026-11-03T05:50:42.305Z
SHA-256 of the archived text
7b1c36107a96b23bd52a0644098636c874e4cdeefc44564952e5a54e696e6cf9
Stable URL of this page
https://metraipolis.com/documento/dc_d6026a293ade

How to cite

Clifford synthesis is NP-complete — arXiv:2610.40886 — arXiv (en), https://arxiv.org/abs/2610.40886 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d6026a293ade (Metraipolis archive dc_d6026a293ade, sha256 7b1c36107a96b23bd52a0644098636c874e4cdeefc44564952e5a54e696e6cf9)
BibTeX
@misc{dcd6026a293ade,
  title = {Clifford synthesis is NP-complete — arXiv:2610.40886},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.40886},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d6026a293ade; sha256 7b1c36107a96b23bd52a0644098636c874e4cdeefc44564952e5a54e696e6cf9},
  year = {2026}
}

Archived text

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

We show that the problem of synthesizing a quantum circuit for a given Clifford operator using at most a specified amount of resources is NP-complete for several resource models of practical interest. Specifically, we study synthesis of a given Clifford operator using single-qubit Clifford gates and two-qubit Clifford gates, with full qubit connectivity and no additional ancilla qubits. With single-qubit gates free and CNOT as the only two-qubit gate, we show that deciding whether a given target admits an implementation using at most a specified number of CNOT gates is NP-complete, and we show that the problem remains NP-complete when any two-qubit Clifford gate is allowed and the budget counts all such gates. Moreover, we show that both results continue to hold when SWAP gates may be inserted for free, and when single-qubit gates are also considered part of the budget. In each case, we build on recent work by Li and Guan and show that there are polynomial-time reductions from Hamiltonian path in grid graphs to these decision problems, using a number of qubits quadratic in the number of grid vertices.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2610.40886 — 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-11-03T05:35:16.983Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).