Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2510.16420

Exact Quantum Circuit Optimization is co-NQP-hard

Adam Husted Kjelstrøm, Andreas Pavlogiannis, Jaco van de Pol

Published Oct 18, 2025• 0 citations
arXivHTMLPDF

Abstract

As quantum computing resources remain scarce and error rates high, minimizing the resource consumption of quantum circuits is essential for achieving practical quantum advantage. Here we consider the natural problem of, given a circuit $C$, computing a circuit $C'$ that behaves equivalently on a desired subspace, and that minimizes a quantum resource type, expressed as the count or depth of (i) arbitrary gates, or (ii) non-Clifford gates, or (iii) superposition gates, or (iv) entanglement gates. We show that, when $C$ is expressed over any gate-set that can implement the H and TOF gates exactly, a standard property of approximately universal gate-sets, each of the above optimization problems is hard for co-NQP, and hence outside the Polynomial Hierarchy, unless the Polynomial Hierarchy collapses. This complements a recent result of Van de Wetering and Amy (arXiv, 2023) which establishes an NP-hardness lower bound when equivalence is over the full state space, and tightens the gap to the corresponding $\text{NP}^\text{NQP}$ upper bound known for cases (i)-(iii) over Clifford+T and (i)-(iv) over H+TOF circuits. Our result also generalizes a result by Tanaka (Int. J. Quantum Inf., 2010) to other gate-sets and quantum resources.

DOI
10.48550/arxiv.2510.16420

Related papers

(A Variant of) Clifford Circuit Synthesis is NP-Complete

Luna Lima Keller, Richard Kueng

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.

quant-pharXiv:2610.02029•Oct 2, 2026•0 citations

Optimising quantum circuits is generally hard

John van de Wetering, Matthew Amy

In order for quantum computations to be done as efficiently as possible it is important to optimise the number of gates used in the underlying quantum circuits. In this paper we find that many gate optimisation problems for approximately universal quantum circuits are NP-hard. In particular, we show that optimising the T-count or T-depth in Clifford+T circuits, which are important metrics for the computational cost of executing fault-tolerant quantum computations, is NP-hard by reducing the problem to Boolean satisfiability. With a similar argument we show that optimising the number of CNOT gates or Hadamard gates in a Clifford+T circuit is also NP-hard. Again varying the same argument we also establish the hardness of optimising the number of Toffoli gates in a reversible classical circuit. We find an upper bound to the problems of T-count and Toffoli-count of $\text{NP}^{\text{NQP}}$. Finally, we also show that for any non-Clifford gate $G$ it is NP-hard to optimise the $G$-count over the Clifford+$G$ gate set, where we only have to match the target unitary within some small distance in the operator norm.

arXiv:2310.05958•Sep 12, 2023•0 citations

Exact Non-Identity Check and Gate-Teleportation-Based Indistinguishability Obfuscation are NP-hard for Low-T-Depth Quantum Circuits

Joshua Nevin

In 2021, Broadbent and Kazmi developed a gate-teleportation-based protocol for computational indistinguishability obfuscation of quantum circuits. This protocol is efficient for Clifford+T circuits with logarithmically many T-gates, where the limiting factor in the efficiency of the protocol is the difficulty, on input a quantum circuit $C$, of the classical task of producing a description of the unitary obtained by conjugating a Pauli $P$ (corresponding to a Bell-measurement outcome) by $C$, where this description only depends on the input-output functionality of $CPC^{\dagger}$. The task above, in turn, is at least as hard as the problem of determining whether two $n$-qubit quantum circuits are perfectly equivalent up to global phase. In 2009, Tanaka defined the corresponding decision problem Exact Non-Identity Check (ENIC) and showed that ENIC is NQP-complete and thus NP-hard as well. Motivated by the 2021 protocol, we consider in this work what happens when we pass from low T-count to low T-depth. We show that, for Clifford+T-circuits of T-depth $O(\log(n))$, deciding ENIC remains NP-hard. In particular, we show this by relating certain decision problems on Pauli coefficients of Clifford+T unitaries to well-known hardness results for codeword weights in binary linear codes. This effectively rules out the possibility, for Clifford+T-circuits of logarithmic T-depth, of either efficient ENIC or efficient gate-teleportation based computational indistinguishability obfuscation, unless P=NP. It also provides a new, independent proof of the hardness of ENIC, even at low T-depth. Along the way, we prove the NP-hardness of some related circuit problems.

quant-pharXiv:2511.17856•IEEE Transactions on Information Theory•Nov 25, 2025•0 citations

Clifford synthesis is NP-complete

Søren Fuglede Jørgensen

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. Specifically, we study synthesis of a given Clifford operator using single-qubit Clifford gates and two-qubit Clifford gates, with full qubit connectivity and no additional ancilla qubits. With single-qubit gates free and CNOT as the only two-qubit gate, we show that deciding whether a given target admits an implementation using at most a specified number of CNOT gates is NP-complete, and we show that the problem remains NP-complete when any two-qubit Clifford gate is allowed and the budget counts all such gates. Moreover, we show that both results continue to hold when SWAP gates may be inserted for free, and when single-qubit gates are also considered part of the budget. In each case, we build on recent work by Li and Guan and show that there are polynomial-time reductions from Hamiltonian path in grid graphs to these decision problems, using a number of qubits quadratic in the number of grid vertices.

quant-pharXiv:2610.40886•Nov 2, 2026

Depth-Optimal Synthesis of Clifford Circuits with SAT Solvers

Tom Peham, Nina Brandl, Richard Kueng +2 more

Circuit synthesis is the task of decomposing a given logical functionality into a sequence of elementary gates. It is (depth-)optimal if it is impossible to achieve the desired functionality with even shorter circuits. Optimal synthesis is a central problem in both quantum and classical hardware design, but also plagued by complexity-theoretic obstacles. Motivated by fault-tolerant quantum computation, we consider the special case of synthesizing blocks of Clifford unitaries. Leveraging entangling input stimuli and the stabilizer formalism allows us to reduce the Clifford synthesis problem to a family of poly-size satisfiability (SAT) problems - one for each target circuit depth. On a conceptual level, our result showcases that the Clifford synthesis problem is contained in the first level of the polynomial hierarchy (NP), while the classical synthesis problem for logical circuits is known to be complete for the second level of the polynomial hierarchy (Σp2). Based on this theoretical reduction, we formulate a SAT encoding for depth-optimal Clifford synthesis. We then employ SAT solvers to determine a satisfying assignment or to prove that no such assignment exists. From that, the shortest depth for which synthesis is still possible (optimality) as well as the actual circuit (synthesis) can be obtained. Empirical evaluations show that the optimal synthesis approach yields a substantial depth improvement for random Clifford circuits and Clifford+T circuits for Grover search.

arXiv:2305.01674•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•15 citations

CS-count-optimal quantum circuits for arbitrary multi-qubit unitaries

Priyanka Mukhopadhyay

Abstract In quantum computing there are quite a few universal gate sets, each having their own characteristics. In this paper we study the Clifford+CS universal fault-tolerant gate set. The CS gate is used is many applications and this gate set is an important alternative to Clifford+T. We introduce a generating set in order to represent any unitary implementable by this gate set and with this we derive a bound on the CS-count of arbitrary multi-qubit unitaries. Analysing the channel representation of the generating set elements, we infer $${\mathcal {J}}_n^{CS}\subset {\mathcal {J}}_n^T$$ J n CS ⊂ J n T , where $${\mathcal {J}}_n^{CS}$$ J n CS and $${\mathcal {J}}_n^T$$ J n T are the set of unitaries exactly implementable by the Clifford+CS and Clifford+T gate sets, respectively. We develop CS-count optimal synthesis algorithms for both approximately and exactly implementable multi-qubit unitaries. With the help of these we derive a CS-count-optimal circuit for Toffoli, implying $${\mathcal {J}}_n^{Tof}={\mathcal {J}}_n^{CS}$$ J n Tof = J n CS , where $${\mathcal {J}}_n^{Tof}$$ J n Tof is the set of unitaries exactly implementable by the Clifford+Toffoli gate set. Such conclusions can have an important impact on resource estimates of quantum algorithms.

Scientific Reports•Jun 17, 2024•2 citations
As quantum computing resources remain scarce and error rates high, minimizing the resource consumption of quantum circuits is essential for achieving practical quantum advantage. Here we consider the natural problem of, given a circuit CCC, computing a circuit C′C'C′ that behaves equivalently on a desired subspace, and that minimizes a quantum resource type, expressed as the count or depth of (i) arbitrary gates, or (ii) non-Clifford gates, or (iii) superposition gates, or (iv) entanglement gates. We show that, when CCC is expressed over any gate-set that can implement the H and TOF gates exactly, a standard property of approximately universal gate-sets, each of the above optimization problems is hard for co-NQP, and hence outside the Polynomial Hierarchy, unless the Polynomial Hierarchy collapses. This complements a recent result of Van de Wetering and Amy (arXiv, 2023) which establishes an NP-hardness lower bound when equivalence is over the full state space, and tightens the gap to the corresponding NPNQP\text{NP}^\text{NQP}NPNQP upper bound known for cases (i)-(iii) over Clifford+T and (i)-(iv) over H+TOF circuits. Our result also generalizes a result by Tanaka (Int. J. Quantum Inf., 2010) to other gate-sets and quantum resources.
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.
In order for quantum computations to be done as efficiently as possible it is important to optimise the number of gates used in the underlying quantum circuits. In this paper we find that many gate optimisation problems for approximately universal quantum circuits are NP-hard. In particular, we show that optimising the T-count or T-depth in Clifford+T circuits, which are important metrics for the computational cost of executing fault-tolerant quantum computations, is NP-hard by reducing the problem to Boolean satisfiability. With a similar argument we show that optimising the number of CNOT gates or Hadamard gates in a Clifford+T circuit is also NP-hard. Again varying the same argument we also establish the hardness of optimising the number of Toffoli gates in a reversible classical circuit. We find an upper bound to the problems of T-count and Toffoli-count of NPNQP\text{NP}^{\text{NQP}}NPNQP. Finally, we also show that for any non-Clifford gate GGG it is NP-hard to optimise the GGG-count over the Clifford+GGG gate set, where we only have to match the target unitary within some small distance in the operator norm.
In 2021, Broadbent and Kazmi developed a gate-teleportation-based protocol for computational indistinguishability obfuscation of quantum circuits. This protocol is efficient for Clifford+T circuits with logarithmically many T-gates, where the limiting factor in the efficiency of the protocol is the difficulty, on input a quantum circuit CCC, of the classical task of producing a description of the unitary obtained by conjugating a Pauli PPP (corresponding to a Bell-measurement outcome) by CCC, where this description only depends on the input-output functionality of CPC†CPC^{\dagger}CPC†. The task above, in turn, is at least as hard as the problem of determining whether two nnn-qubit quantum circuits are perfectly equivalent up to global phase. In 2009, Tanaka defined the corresponding decision problem Exact Non-Identity Check (ENIC) and showed that ENIC is NQP-complete and thus NP-hard as well. Motivated by the 2021 protocol, we consider in this work what happens when we pass from low T-count to low T-depth. We show that, for Clifford+T-circuits of T-depth O(log⁡(n))O(\log(n))O(log(n)), deciding ENIC remains NP-hard. In particular, we show this by relating certain decision problems on Pauli coefficients of Clifford+T unitaries to well-known hardness results for codeword weights in binary linear codes. This effectively rules out the possibility, for Clifford+T-circuits of logarithmic T-depth, of either efficient ENIC or efficient gate-teleportation based computational indistinguishability obfuscation, unless P=NP. It also provides a new, independent proof of the hardness of ENIC, even at low T-depth. Along the way, we prove the NP-hardness of some related circuit problems.
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. Specifically, we study synthesis of a given Clifford operator using single-qubit Clifford gates and two-qubit Clifford gates, with full qubit connectivity and no additional ancilla qubits. With single-qubit gates free and CNOT as the only two-qubit gate, we show that deciding whether a given target admits an implementation using at most a specified number of CNOT gates is NP-complete, and we show that the problem remains NP-complete when any two-qubit Clifford gate is allowed and the budget counts all such gates. Moreover, we show that both results continue to hold when SWAP gates may be inserted for free, and when single-qubit gates are also considered part of the budget. In each case, we build on recent work by Li and Guan and show that there are polynomial-time reductions from Hamiltonian path in grid graphs to these decision problems, using a number of qubits quadratic in the number of grid vertices.
Circuit synthesis is the task of decomposing a given logical functionality into a sequence of elementary gates. It is (depth-)optimal if it is impossible to achieve the desired functionality with even shorter circuits. Optimal synthesis is a central problem in both quantum and classical hardware design, but also plagued by complexity-theoretic obstacles. Motivated by fault-tolerant quantum computation, we consider the special case of synthesizing blocks of Clifford unitaries. Leveraging entangling input stimuli and the stabilizer formalism allows us to reduce the Clifford synthesis problem to a family of poly-size satisfiability (SAT) problems - one for each target circuit depth. On a conceptual level, our result showcases that the Clifford synthesis problem is contained in the first level of the polynomial hierarchy (NP), while the classical synthesis problem for logical circuits is known to be complete for the second level of the polynomial hierarchy (Σp2). Based on this theoretical reduction, we formulate a SAT encoding for depth-optimal Clifford synthesis. We then employ SAT solvers to determine a satisfying assignment or to prove that no such assignment exists. From that, the shortest depth for which synthesis is still possible (optimality) as well as the actual circuit (synthesis) can be obtained. Empirical evaluations show that the optimal synthesis approach yields a substantial depth improvement for random Clifford circuits and Clifford+T circuits for Grover search.
Abstract In quantum computing there are quite a few universal gate sets, each having their own characteristics. In this paper we study the Clifford+CS universal fault-tolerant gate set. The CS gate is used is many applications and this gate set is an important alternative to Clifford+T. We introduce a generating set in order to represent any unitary implementable by this gate set and with this we derive a bound on the CS-count of arbitrary multi-qubit unitaries. Analysing the channel representation of the generating set elements, we infer JnCS⊂JnT{\mathcal {J}}_n^{CS}\subset {\mathcal {J}}_n^TJnCS​⊂JnT​ J n CS ⊂ J n T , where JnCS{\mathcal {J}}_n^{CS}JnCS​ J n CS and JnT{\mathcal {J}}_n^TJnT​ J n T are the set of unitaries exactly implementable by the Clifford+CS and Clifford+T gate sets, respectively. We develop CS-count optimal synthesis algorithms for both approximately and exactly implementable multi-qubit unitaries. With the help of these we derive a CS-count-optimal circuit for Toffoli, implying JnTof=JnCS{\mathcal {J}}_n^{Tof}={\mathcal {J}}_n^{CS}JnTof​=JnCS​ J n Tof = J n CS , where JnTof{\mathcal {J}}_n^{Tof}JnTof​ J n Tof is the set of unitaries exactly implementable by the Clifford+Toffoli gate set. Such conclusions can have an important impact on resource estimates of quantum algorithms.