(A Variant of) Clifford Circuit Synthesis is NP-Complete
The paper proves that finding the shortest-depth realization for a Clifford circuit is NP-hard, even when using all standard Clifford gates. It achieves this by reducing graph edge coloring to circuit synthesis problems involving CZ gates. This means deciding if a Clifford unitary can be implemented within a certain depth is an NP-complete problem, showing it's at least as hard as any other problem in NP.