arXiv:2610.02029
(A Variant of) Clifford Circuit Synthesis is NP-Complete
Luna Lima Keller, Richard Kueng
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.
AI Summary
The paper asks whether depth-optimal Clifford synthesis remains computationally hard despite efficient classical simulation and equivalence checking. It proves NP-hardness for the fixed elementary gate set $\{X,Y,Z,H,S,S^\dagger,\mathrm{CNOT},\mathrm{CZ}\}$, with gates on disjoint qubits executed in parallel. Together with known NP membership, this makes the corresponding depth-bounded decision problem NP-complete. The reduction maps a graph $G$ to the diagonal Clifford unitary $U_G=\prod_{uv\in E(G)}\mathrm{CZ}_{uv}$. For CZ-only implementations, optimal depth equals the edge-chromatic number $\chi'(G)$: an edge coloring supplies a schedule, while any implementation must contain each graph-edge CZ an odd number of times, allowing a coloring to be extracted. The central result is that, for 3-regular graphs, allowing the additional elementary Clifford gates does not reduce depth: $D_{\mathrm{elem}}(U_G)=D_{\mathrm{CZ}}(U_G)=\chi'(G)\in\{3,4\}$. Thus deciding whether depth three suffices captures NP-complete 3-edge-colorability. The no-shortcut argument analyzes depth-three circuits. Tracking computational and $X/Z$ product bases eliminates Hadamards; constraints on the induced binary linear maps yield a CNOT normal form. Pauli-support growth then excludes CNOTs for cubic graphs, and quadratic-phase counting forces a CZ-only implementation. The result depends on the specified primitive gate library and its depth convention. The paper does not establish the analogous result without primitive CZ gates or when arbitrary one- and two-qubit Cliffords count as single gates. Extensions to these libraries and to matchgate synthesis remain open.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 9 pages, 1 figure