The Signal
Søren Fuglede Jørgensen Reports Proof That Clifford Gate-Budget Synthesis Is NP-Complete
Søren Fuglede Jørgensen proves that deciding whether a Clifford operator can be implemented within a specified gate budget is NP-complete across several resource models. The reductions connect grid-graph Hamiltonian paths to gate-count limits, with implications for exact circuit optimization.

Clifford circuits can be synthesized for large qubit systems, but finding the shortest circuit under a gate budget is a different problem: Søren Fuglede Jørgensen proves that the decision version is NP-complete. His result targets exact resource minimization, not the ability to produce a working circuit. The distinction matters for compilers that trade gate count against the time and effort required to search for a better implementation.
Source arxiv.org
Submitted to arXiv on October 29, the paper establishes hardness across several gate-cost models, including circuits built from CNOT gates and circuits that may use any two-qubit Clifford gate. The reductions start from Hamiltonian path in grid graphs, encoding whether a path exists as a question about whether a Clifford operator can be implemented within a specified gate budget.
Finding a circuit is not finding the shortest one
Clifford operations are central to quantum error correction and magic-state distillation, and compilers also replace Clifford subcircuits to reduce the resources used by larger programs. Existing synthesis methods cover a wide range: some handle large qubit counts efficiently but may produce circuits with high gate counts or depth, while exact methods seek optimal circuits in smaller or intermediate cases. Jørgensen’s result concerns the cost of guaranteeing the best answer, not whether a compiler can generate an equivalent circuit.
“We show that the problem of synthesizing a quantum circuit for a given Clifford operator using at most a specified amount of resources is NP-complete for several resource models of practical interest.”
Søren Fuglede Jørgensen, author of the paper
A grid path becomes a gate budget
The proof builds on earlier work showing hardness for CNOT-only synthesis. A Hamiltonian path must visit every vertex in a graph exactly once; in the reduction, moves between adjacent grid vertices map to CNOT updates. Additional “recorder” qubits preserve information about the path in the circuit’s final transformation, while a carefully chosen gate budget rules out implementations that skip the required sequence.
Jørgensen extends the construction to full Clifford circuits, where single-qubit gates could otherwise offer shortcuts around the intended CNOT sequence. The paper’s abstract states that the reductions use a number of qubits quadratic in the number of grid vertices. Its main theorem also identifies a restricted class of targets for which the hardness already holds: operators represented by lower-unitriangular matrices satisfying a specific algebraic condition.
Hardness holds across several cost models
The result assumes full connectivity: any pair of qubits may interact. It also excludes additional ancilla qubits. In the central model, single-qubit Clifford gates are free and the budget counts CNOTs; the proof then extends to budgets counting arbitrary two-qubit Clifford gates, to models that charge for single-qubit gates, and to models where SWAP gates are free.
Those variants make the theorem relevant beyond a single hardware-specific gate list, but they do not establish that every practical optimization instance is difficult. NP-completeness concerns worst-case instances and the decision question—whether a circuit within the given budget exists. A proposed circuit can be checked efficiently, and algorithms can still produce useful, non-optimal circuits without solving the exact minimum problem.
Gate count adds to a separate depth result
The paper distinguishes its result from work by Luna Lima Keller and Richard Kueng, which establishes NP-completeness for a Clifford synthesis problem bounded by circuit depth. Depth measures how many sequential gate layers a circuit needs; Jørgensen studies gate count. The two papers therefore address different optimization targets, rather than contradicting one another.
That distinction gives compiler designers two separate worst-case limits to account for: minimizing the number of gates and minimizing the number of layers. For Jørgensen’s gate-count result, the concrete construction begins with a grid-graph Hamiltonian-path instance and turns it into a Clifford target with a specified gate budget.
Sources
Related stories
- Shmueli Ties Indefinite Causal Order to Computation Beyond BQP
- PRX paper bounds entanglement growth and its spectrum
- Researchers synthesize four-circuit fault-tolerant ancilla preparation
- LLM-guided search produces fault-tolerant circuit designs
- Study reports higher simulated Max-Cut ratios with cat-qubit QAOA