Exact Quantum Circuit Optimization is co-NQP-hard

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

Read Exact Quantum Circuit Optimization is co-NQP-hard by Adam Husted Kjelstrøm, Andreas Pavlogiannis, Jaco van de Pol (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-16420.txt.

Introduction

Adam Husted Kjelstrøm, Andreas Pavlogiannis, and Jaco van de Pol ask a hard question in a 2025 paper. Given a quantum circuit, can a computer find the smallest circuit that does the same job? A circuit is a set of steps that act on quantum bits. The team counts cost by gate count or depth, for four kinds of gates.

They prove the task is hard for a class called co-NQP, a high bar in computing. That puts it past the usual layers of hard tasks, unless those layers collapse. The proof holds for any gate set that can build two key gates exactly. The result tells builders not to expect a fast exact shortcut tool.

Catalog record

CREATORAdam Husted Kjelstrøm, Andreas Pavlogiannis, Jaco van de Pol
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE18 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-16420

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Exact Quantum Circuit Optimization is co-NQP-hard Adam Husted Kjelstrøm, Andreas Pavlogiannis, Jaco van de Pol 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 C , computing an equivalent circuit C ′ C^{\prime} 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 C is expressed over any gate set that can implement the H and TOF gates exactly, each of the above optimization problems is hard for co- ​ 𝐍𝐐𝐏 \text{co-}\mathbf{NQP} , and hence outside the Polynomial Hierarchy, unless the Polynomial Hierarchy collapses. This strengthens recent results in the literature which established an 𝐍𝐏 \mathbf{NP} -hardness lower bound, and tightens the gap to the corresponding 𝐍𝐏 𝐍𝐐𝐏 \mathbf{NP}^{\mathbf{NQP}} upper bound known for cases (i)-(iii) over Clifford+ T and (i)-(iv) over H + TOF circuits. 1 Introduction Despite rapid progress in quantum hardware, limited resources and high error rates remain fundamental bottlenecks, making the optimization of quantum circuits a key challenge on the path to quantum advantage [ Karuppasamy2025QuantumCircuitOptimization ] . Quantum computations rely on multiple types of resources, and depending on the underlying hardware, different resources (e.g., the total circuit size, or the number of a particular gate) can become the primary bottleneck by introducing noise or increasing execution time [ Muroya2025HardwareOptimal ] . In high-level, a circuit optimization problem is defined wrt a function f mapping a circuit C to a cost f(C) . Then, given some fixed gate set \mathcal{A} , the task is to find a circuit C^{\prime} over some gate-set \mathcal{B} (possibly different from \mathcal{A} ) such that C and C^{\prime} are equivalent, and f(C^{\prime}) is minimized. Here we focus on exact equivalence, written as C\equiv C^{\prime} , where C^{\prime} behaves identically to C on all inputs. Although quantum computation is often approximate [ Dawson2005solovay_kitaev_thrm , Nielsen_Chuang2010 ] , focusing on exact equivalence remains important: it is the direct quantum analogue of classical computing, and it is useful for canonicalizing circuits, i.e., building a database of the most efficient circuits [ Bravyi2022_6_qubit_optimal_Clifford_circuits ] , making fast peephole optimizations compositional (i.e., without the need to keep track of how approximation errors may accumulate). In complexity-theoretic terms, the optimization problem is typically phrased as a decision problem, where the input also specifies some budget k , and the task is to decide whether there exists an equivalent circuit C^{\prime} with f(C^{\prime})\leq k [ Wetering2023OptimisingQuantumCircuitsHard ] . In the classical reversible setting, the problem is in \mathbf{\Sigma}_{2}^{\mathbf{P}} (guess a circuit, then verify all inputs), under the reasonable assumption that f can be evaluated in polynomial time. Moving towards quantum circuits, the same problem over the Clifford gate-set is in \mathbf{NP} , since circuit equivalence is known to be in \oplus\mathbf{L}\subseteq\mathbf{P} [ Aaronson04sim_of_stabilizer_circuits ] . Interestingly, whether the problem is \mathbf{NP} -hard when f simply counts the size of the circuit is an open question, to our knowledge [ doi:10.1137/1.9781611975994.13 ] . To capture the full computational power of quantum computing, the circuit optimization problem has also been studied wrt (approximately) universal gate sets beyond the Clifford fragment. In [ Tanaka2010ExactNonIdentityCheckNQPComplete ] , it was shown that there are fixed gate-sets for which even deciding whether it equals identity (i.e., it can be implemented with 0 gates) is \text{co-}\mathbf{NQP} -hard under Karp reductions. More recently, the optimization problem was studied for fixed gate sets and wrt minimizing either the circuit size/depth or the count/depth of some particular gate G (from now on referred to as G -count/depth) [ Wetering2023OptimisingQuantumCircuitsHard ] . In particular, the optimization problem was shown to be \mathbf{NP} -hard, under \mathbf{P} -time Turing reductions, over the Clifford+ T and H + TOF gate sets, and where minimization is wrt the circuit size/depth or the H / CX / T -count/depth for the former, and the H / TOF -count/depth for the latter. The same work also showed that these problems are in \mathbf{NP}^{\mathbf{NQP}} , except for the case of CX gates, for which an upper bound is not known. As \mathbf{NQP} is believed to be outside the Polynomial Hierarchy \mathbf{PH} [ fenner1998determiningacceptancepossibilityquantum ] , there is a large gap between the \mathbf{NP}^{\mathbf{NQP}} upper bound and the \mathbf{NP} -hardness lower bound. How difficult is exact quantum circuit optimization? In this work, we consider the optimization problem in the following general form: the input is a circuit C that comes from a fixed gate set \mathcal{A} . The task is to implement C in some fixed gate set \mathcal{B} in a way that minimizes either (i) the number of all gates, or (ii) the number of non-Clifford gates (e.g., the T gates), or (iii) the number of gates that generate superposition (e.g., the H gates), or (iv) the number of gates that generate entanglement (e.g., the CX gates). While case (i) deals with the standard objective of minimizing circuit size, cases (ii), (iii) and (iv) deal with the minimization of various resources that are needed for universal quantum computation [ Aaronson04sim_of_stabilizer_circuits ] . Towards this, we prove a strong lower bound for a conceptually simpler promise problem , that unifies the hardness of the above optimization tasks. This promise problem is based on two semantic properties. We say that a circuit C generates superposition if C maps a basis state to a superposition of two or more basis states. Similarly, we say that C generates non-affine correlation if the measured value of one qubit is correlated with those of the others in a non-affine (e.g., quadratic) manner. We consider the following promise problem. Input: A circuit C over gate-set \mathcal{A} . Promise: Either C\equiv\text{I} or C generates both superposition and non-affine correlation. Question: Is it the case that C\equiv\text{I} ? \textbf{{Promise\text{-}IsIdentity}}\textbf{(}\mathcal{A}\textbf{)} Note that the identity circuit I does not generate superposition, nor non-affine correlation, meaning the promise indeed separates the two cases. In full generality, we prove the following theorem. Theorem 1 . For any gate-set \mathcal{A} that can implement H and TOF exactly, \textsc{Promise\text{-}IsIdentity}(\mathcal{A}) is \text{co-}\mathbf{NQP} -complete. In particular, the conditions of Theorem 1 are satisfied by the Clifford+ T gate set as well as the gate sets of common hardware platforms [ IBMQuantum2025_QPUInformation , IonQ2025_NativeGatesGuide , Quantinuum2025_H2_Data_Sheet ] . The \text{co-}\mathbf{NQP} upper bound follows from [ Tanaka2010ExactNonIdentityCheckNQPComplete ] , which showed that the check C\not\equiv\text{I} is in \mathbf{NQP} , thus our technical focus is on the lower bound of Theorem 1 . Clearly, any circuit that generates superposition must make use of at least one gate that generates superposition. Likewise, any circuit that generates non-affine correlation must make use of non-Clifford resources [ Nielsen_Chuang2010 ] . Furthermore, any circuit that generates non-affine correlation clearly generates correlation, while any non-identity circuit must make use of at least one non-identity gate. Thus, a potential algorithm for the minimization problem for any such type of gates could be used to solve \textsc{Promise\text{-}IsIdentity}(\mathcal{A}) , by specifying a budget k=0 . In particular, Theorem 1 yields the following corollary. Corollary 1 . Consider any specification gate set \mathcal{A} that can implement

Read the complete text