{"id":"arxiv/2610.02029","url":"https://arxiv.org/abs/2610.02029","tags":["quant-ph"],"score":0,"title":"(A Variant of) Clifford Circuit Synthesis is NP-Complete","domain":"quant-ph","source":"arxiv","authors":["Luna Lima Keller","Richard Kueng"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-01","reactions":{}}