⚛️ quantum physics

Exact Quantum Circuit Optimization is co-NQP-hard

This paper demonstrates that the problem of exactly optimizing quantum circuits to minimize resources such as gate count, depth, or specific gate types (including non-Clifford, superposition, and entanglement gates) is co-NQP-hard, thereby placing it outside the Polynomial Hierarchy unless the hierarchy collapses.

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

Published 2026-02-27

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master chef trying to perfect a recipe for a quantum dish. You have a complex, messy recipe (a quantum circuit) that works, but it uses too many ingredients, takes too long to cook, or creates too much "noise" in the kitchen. Your goal is to rewrite the recipe so it tastes exactly the same but uses fewer resources.

This paper is about a team of computer scientists who discovered a terrifying truth about this task: Finding the perfect, most efficient quantum recipe is likely impossible to solve quickly, no matter how powerful our computers become.

Here is the breakdown of their discovery using simple analogies.

1. The Problem: The "Quantum Kitchen" Bottleneck

Right now, quantum computers are like fragile, expensive kitchens. They make mistakes easily (high error rates) and have very few ingredients (scarce resources). To make them useful, we need to optimize their circuits—basically, making them smaller, faster, and cleaner.

The scientists asked a simple question: "If I give you a circuit that works on a specific set of inputs, can you find a simpler circuit that does the exact same thing?"

They looked at four specific ways to measure "simplicity":

Total Size: How many steps are in the recipe?
Special Ingredients: How many "non-Clifford" gates (the fancy, hard-to-make spices like the T-gate) are used?
Superposition: How many times do we create a "both-at-once" state (like a coin spinning)?
Entanglement: How many times do we link two particles together so they act as one?

2. The Discovery: The "Magic Mirror" Trap

The researchers proved that solving this optimization problem is co-NQP-hard.

That sounds like gibberish, but here is the translation:

The Complexity Class: Imagine a hierarchy of difficulty. At the bottom is "easy" (things a normal computer can solve quickly). At the top is "impossible." This paper says the problem sits so high up that it is likely outside the entire hierarchy of problems we think are solvable in a reasonable time.
The "Magic Mirror" (The Promise Problem): To prove this, they created a thought experiment. Imagine a black box (a circuit) and a specific input.
- Scenario A: The box is a perfect mirror. You put in a ball, and it bounces back exactly the same.
- Scenario B: The box is a chaotic blender. You put in a ball, and it explodes into a superposition of many balls, linked in a weird, non-linear way.

The scientists proved that telling the difference between "Perfect Mirror" and "Chaotic Blender" is incredibly hard. If you could easily find the simplest circuit to replicate the box's behavior, you could easily solve this "Mirror vs. Blender" test. But since the test is nearly impossible to solve, the optimization problem is also nearly impossible.

3. The "Deutsch-Josza Gadget": The Trick Question

How did they prove this? They built a clever little machine (a "gadget") based on an old algorithm called Deutsch-Josza.

Think of this gadget as a trick question in a game show:

The host asks: "Is this function balanced (50/50) or constant (all the same)?"
In the quantum world, there is a special way to answer this instantly.
The researchers built a circuit where the answer to this game show question determines whether the circuit acts like a Mirror or a Blender.

They showed that if you could easily optimize the circuit to make it smaller, you could also easily solve the game show question. Since the game show question is known to be a "hard nut to crack" for quantum computers, the optimization task must be just as hard.

4. Why This Matters

You might think, "Okay, but maybe we just need better algorithms."

The paper argues that this isn't just a lack of good algorithms; it's a fundamental law of nature for these types of problems.

The Gap: Previous research showed the problem was at least "NP-hard" (very hard). This paper pushes the difficulty up a massive notch to "co-NQP-hard" (extremely, likely impossibly hard).
The Implication: We cannot expect to build a "magic wand" that automatically shrinks any quantum circuit to its perfect size. We will likely have to rely on heuristics (good guesses) and manual engineering, rather than perfect mathematical solutions.

The Takeaway

In the race to build a practical quantum computer, we are trying to shrink our circuits to save energy and reduce errors. This paper puts a giant "STOP" sign on the idea that we can mathematically guarantee finding the smallest possible circuit.

It's like trying to find the absolute shortest path through a maze that changes its walls every time you blink. The math says: Don't bother looking for the perfect solution; it's likely hidden in a realm of complexity that our computers can't reach. We will have to settle for "good enough" solutions instead of "perfect" ones.

1. Problem Statement

The paper addresses the fundamental challenge of exact quantum circuit optimization. Given a quantum circuit $C$ defined over a specific gate set $A$ , the goal is to find an equivalent circuit $C'$ defined over a (possibly different) gate set $B$ that minimizes specific resource metrics while maintaining exact equivalence on a desired subspace of input states.

The authors focus on four specific optimization objectives:

Total Gate Count/Depth: Minimizing the total number of gates or circuit depth.
Non-Clifford Gate Count/Depth: Minimizing resources like $T$ or $TOF$ gates, which are essential for quantum universality.
Superposition Gate Count/Depth: Minimizing gates that generate superposition (e.g., Hadamard $H$ ).
Entanglement Gate Count/Depth: Minimizing gates that generate entanglement (e.g., $CX$ or $TOF$).

Key Constraint: The equivalence is "exact" and restricted to a specific subspace (defined by an input bit-string $x$ ), rather than the full Hilbert space. This distinguishes the problem from approximate optimization or full-state equivalence.

2. Methodology

The authors employ a complexity-theoretic approach, specifically utilizing Karp reductions to establish hardness lower bounds.

A. Complexity Classes

The paper targets the complexity class co-NQP (complement of Nondeterministic Quantum Polynomial time).

NQP is defined as problems solvable by a Quantum Turing Machine where acceptance occurs if the final state has non-zero amplitude.
It is known that co-NQP = C=P (the class of problems where the number of accepting paths equals the number of rejecting paths).
Crucially, C=P is not contained in the Polynomial Hierarchy (PH) unless PH collapses. Therefore, proving a problem is co-NQP-hard implies it is likely outside PH, making it significantly harder than NP-hard problems.

B. The Intermediate Promise Problem

To prove the hardness of optimization, the authors first define a promise problem called Promise-IsIdentity(A):

Input: An $n$ -qubit circuit $C$ over gate set $A$ and a bit-string $x$ .
Promise: Either $U_C|x\rangle = |x\rangle$ (Identity) OR $U_C|x\rangle$ is a superposition state exhibiting non-affine correlation.
Question: Is $U_C|x\rangle = |x\rangle$ ?

C. The Deutsch-Josza Gadget

The core of the reduction relies on a novel circuit gadget, $Q(G, \phi)$ , constructed using the Deutsch-Josza algorithm:

Components: The gadget uses a Boolean formula $\phi$ and an arbitrary circuit $G$ . It utilizes $n$ ancilla qubits and a controlled- $G$ operation ( $\Lambda^n G$ ).
Mechanism:
- If $\phi$ is balanced, the gadget acts as the identity on the input state $|1^n\rangle|x\rangle$ .
- If $\phi$ is not balanced, the gadget applies $G$ to the input state $|x\rangle$ (scaled by a non-zero amplitude $\beta_\phi$ ).
Properties: The gadget is constructed such that if $\phi$ is not balanced, the output state exhibits superposition and non-affine measurement correlations (a property impossible to generate with Clifford gates alone).

3. Key Contributions

Hardness Proof for Subspace Optimization: The paper establishes that exact quantum circuit optimization is co-NQP-hard for any gate set capable of exactly implementing the Hadamard ( $H$ ) and Toffoli ($TOF$) gates. This includes standard sets like Clifford+T.
Generalization of Resource Minimization: Unlike previous work that focused on minimizing specific gate counts (e.g., T-count) over the full state space (which was shown to be NP-hard), this work proves hardness for minimizing four distinct classes of resources (Total, Non-Clifford, Superposition, Entanglement) over subspaces.
Tightening Complexity Bounds: The result significantly narrows the gap between the known lower bound (NP-hardness) and the upper bound (NPNQP) for these problems. It demonstrates that these optimization problems are likely outside the Polynomial Hierarchy, suggesting they are intractable even for powerful classical complexity classes.
Simplicity of Reduction: The authors demonstrate that this high level of hardness arises from a small, simple gadget based on standard quantum operations (Deutsch-Josza), implying that such hardness is prevalent in practical quantum circuit synthesis.

4. Results

The main theorem and its corollaries are as follows:

Theorem 1: For any gate set $A$ that can implement $H$ and $TOF$ exactly, the problem Promise-IsIdentity(A) is co-NQP-hard.
Corollary 1: The Exact-Optimization problem is co-NQP-hard for minimizing:
- (i) Non-identity gates (Total size/depth).
- (ii) Non-Clifford gates (e.g., T-count).
- (iii) Superposition gates (e.g., H-count).
- (iv) Entanglement gates (e.g., CX-count).
- Condition: The optimization is performed over a subspace defined by an input string $x$ , and the gate set $A$ supports $H$ and $TOF$.

Implication for T-Count: Specifically, minimizing the T-count over Clifford+T circuits with respect to subspace equivalence is co-NQP-hard.

5. Significance

Theoretical Impact: This work elevates the understanding of quantum circuit optimization from "NP-hard" to "likely outside the Polynomial Hierarchy." This suggests that no efficient classical algorithm (even with access to NP oracles) can solve exact optimization for these resources unless the Polynomial Hierarchy collapses.
Practical Relevance: As quantum hardware remains scarce and error-prone, minimizing resources (especially non-Clifford gates like $T$ , which are expensive to implement fault-tolerantly) is critical. The results imply that finding the optimal exact circuit is computationally infeasible for general cases.
Guidance for Heuristics: Since exact optimization is intractable, the results reinforce the necessity of relying on approximate methods, heuristics, or restricted search spaces in practical quantum compiler design.
Foundational Insight: The paper highlights that the difficulty stems from the fundamental properties of quantum mechanics (superposition and non-affine correlations) rather than just the combinatorial explosion of gate sequences.

In summary, the paper provides a rigorous proof that exact quantum circuit optimization is a fundamentally hard problem, belonging to a complexity class significantly higher than NP, thereby setting a strong theoretical limit on what can be achieved by automated circuit synthesis tools.