(A Variant of) Clifford Circuit Synthesis is NP-Complete
Abstract
Optimal circuit synthesis is the problem of finding the shortest-depth circuit representation of a given functionality with respect to a pre-specified elementary gate set. This is a central problem in both quantum and classical hardware design. While the classical version is very well understood -- both in terms of heuristics and rigorous hardness assertions -- much less is known about optimal quantum circuit synthesis. We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. The proof proceeds in two parts: (i) reduce 3-edge colorability on 3-regular graphs to a circuit synthesis problem that only involves CZ gates, (ii) prove that the availability of additional elementary Clifford gates -- most notably: Hadamard, phase and CNOT -- cannot lead to further improvements of the optimal circuit depth. Our work sharpens the complexity-theoretic understanding of Clifford circuits: simulation and equivalence checking are in P, whereas deciding whether a Clifford unitary admits an implementation within a prescribed depth is NP-complete.
Related
- Link-middle-cut lower bounds for Clifford circuit synthesis
- Clifford synthesis is NP-complete
- A Complete and Natural Rule Set for Multi-Qudit Clifford Circuits in All Odd Prime Dimensions
- Complexity separations for optimal matchgate-Clifford synthesis
- Approximate synthesis of general single-qubit unitaries over the Clifford+√T gate set
BibTeX
@misc{keller2026variant,
title = {{(A Variant of) Clifford Circuit Synthesis is NP-Complete}},
author = {Luna Lima Keller and Richard Kueng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02029},
eprint = {2610.02029},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02029},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - (A Variant of) Clifford Circuit Synthesis is NP-Complete
AU - Luna Lima Keller
AU - Richard Kueng
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02029
UR - https://arxiv.org/abs/2610.02029
AB - Optimal circuit synthesis is the problem of finding the shortest-depth circuit representation of a given functionality with respect to a pre-specified elementary gate set. This is a central problem in both quantum and classical hardware design. While the classical version is very well understood -- both in terms of heuristics and rigorous hardness assertions -- much less is known about optimal quantum circuit synthesis. We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. The proof proceeds in two parts: (i) reduce 3-edge colorability on 3-regular graphs to a circuit synthesis problem that only involves CZ gates, (ii) prove that the availability of additional elementary Clifford gates -- most notably: Hadamard, phase and CNOT -- cannot lead to further improvements of the optimal circuit depth. Our work sharpens the complexity-theoretic understanding of Clifford circuits: simulation and equivalence checking are in P, whereas deciding whether a Clifford unitary admits an implementation within a prescribed depth is NP-complete.
ER -