REVIEW
(A Variant of) Clifford Circuit Synthesis is NP-Complete
Quantum Physics · Submitted 1 Oct 2026 · 42 references
Pith's verdict: Genuinely new NP-hardness for Clifford synthesis with primitive CZ; the gate-set boundary is real but honestly scoped, and the proof chain survives re-derivation.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
The paper proves that finding the shortest-depth Clifford circuit is NP-complete when the gate set includes CZ as a primitive one-layer gate, via an exact equivalence between circuit depth and edge coloring of cubic graphs.
The reading
What carries the argument
The load-bearing objects are the unitary U_G that places one CZ gate on every edge of a graph G, and the equality D_elem(U_G) = D_CZ(U_G) for 3-regular G. The CZ-only half uses the fact that CZ gates commute and square to the identity, so a CZ circuit is fully described by the parities of its gate occurrences; each edge of G must occur an odd number of times, which turns layer labels into a proper edge coloring. The no-shortcuts half uses X/Z product bases (joint eigenbases built from X and Z on each qubit), a lemma that a single Hadamard-free layer never maps one such basis to a different one, conjugation identities that convert conjugated CNOT and CZ gates into other gates of Gelem, a CNOT normal form that removes middle-layer CNOTs and leaves identical outer-layer CNOTs, and a Pauli-weight contradiction showing such a remaining CNOT would require weight 4 on a 3-regular graph while direct propagation gives at most 3. A final counting argument then forces any depth-three realization to contain exactly 3n/2 CZ gates and nothing else.
Extended reading notes
Core claim
The central claim is Theorem 2: for the elementary gate set Gelem = {X, Y, Z, H, S, S†, CNOT, CZ}, deciding the optimal depth of an n-qubit Clifford circuit is NP-hard, and the decision version — does a given Clifford unitary admit a circuit of depth at most d? — is NP-complete. The reduction is exact: for every 3-regular graph G, with U_G = ∏_{uv∈E(G)} CZ_{uv}, the paper proves D_elem(U_G) = D_CZ(U_G) = χ'(G). Since the edge-chromatic number of a cubic graph is always 3 or 4, a cubic graph is 3-edge-colorable precisely when U_G can be implemented in three layers, even when Hadamard, phase, and CNOT gates are available. The proof shows that in any depth-≤3 realization, Hadamards must pair up and either cancel or conjugate into gates already in Gelem, that CNOTs can be pushed into a normal form with identical outer layers that then forces them to vanish on 3-regular graphs, and that a counting argument then leaves room for exactly the required CZ gates and nothing else.
Load-bearing premise
The load-bearing premise is that a CZ gate counts as a primitive depth-one gate in the gate set; if CZ had to be decomposed into H, S, and CNOT gates, the depth accounting and the counting argument behind the no-shortcuts conclusion would collapse, and the authors explicitly say the reduction would require modification in such a library.
Editorial extensions
If this is right
- Unless P = NP, no polynomial-time algorithm can produce depth-optimal Clifford circuits for general Clifford unitaries over Gelem.
- The decision problem is exactly NP-complete, not merely NP-hard: a candidate circuit can be verified in polynomial time using Clifford equivalence checking, matching the known SAT-based containment in NP.
- For 3-regular graphs, Clifford synthesis reduces to edge coloring at zero overhead: optimal graph-coloring solvers produce optimal CZ circuits whose depth equals χ'(G), and vice versa.
- Heuristic approaches that encode Clifford synthesis as SAT or graph coloring are not artificially inflating the difficulty; they target a problem that is genuinely NP-hard.
- The Hadamard and CNOT elimination results are tailored to circuits of depth at most three, so closing the same gap for longer circuits or other gate sets requires new techniques.
Reading between the lines
- If the Hadamard and CNOT normal-form reasoning extends to constant-depth circuits with d > 3, the correspondence between extra Clifford gates and CZ-only depth would likely survive for each fixed small d, giving hardness for deciding depth-d synthesis; the paper does not claim this extension.
- The authors suggest an analogue for matchgate circuits: if matchgate synthesis admits a similar normal-form elimination, a matching NP-hardness proof for optimal matchgate synthesis would follow; this is an extension they propose, not a proven result.
- A direct test of the mechanism: take the Petersen graph, a cubic graph with edge-chromatic number 4, and exhaustively search for a depth-3 circuit over Gelem that implements its associated unitary U_G; Proposition 5 predicts the search finds nothing.
- The result is sensitive to the gate set: under a library without primitive CZ, the uniform cost-one layer for CZ disappears and the identical correspondence would fail in its present form, a gate-set dependence the authors explicitly acknowledge.
Original 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.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s1 | This is a central problem in both quantum and classical hardware design. | background 1.00 | 0.03 | 0.01 | asserted 1.00 |
| s2 | 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. | gap 0.79 | 0.04 | 0.01 | asserted 0.99 |
| s3 | We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. | background 0.95 | 0.06 | 0.03 | asserted 0.98 |
| s4 | Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. | result 0.92 | 0.96 | 0.97 | asserted 1.00 |
| s5 | 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. | method 0.99 | 0.93 | 0.09 | asserted 1.00 |
| s6 | 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. | interpretation 0.57 | 0.85 | 0.50 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.