⚛️ quantum physics

On the Hardness of Approximate Quantum Circuit Membership and Optimization

This paper demonstrates that the problem of determining whether a quantum circuit is approximately close to a set of target unitaries (such as the identity, Clifford gates, or permutation matrices) is PP-hard across various distance metrics and gate sets, thereby establishing that quantum circuit optimization is significantly harder than its promise-based QMA-complete counterpart.

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

Published 2026-11-04

📖 6 min read🧠 Deep dive

CC BY 4.0

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

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 author. For technical accuracy, refer to the original paper. Read full disclaimer

Quantum computers promise to solve problems that would take today's machines thousands of years to crack, but they are notoriously fragile. To make them work, engineers must build circuits—sequences of operations that manipulate tiny particles of information. These circuits are often bloated with unnecessary steps, and every extra step introduces noise that can ruin the calculation. To fix this, software tools try to optimize these circuits, stripping away redundant parts to make them shorter, faster, and more reliable. However, there is a fundamental question lurking behind this optimization: how hard is it to know if a circuit can be simplified, or if it is already as good as it gets? This is not just a matter of engineering efficiency; it touches on the very limits of what computers, classical or quantum, can ever calculate.

A team of researchers at Aarhus University has now answered this question with a definitive and surprising result. They investigated the difficulty of determining whether a given quantum circuit is close enough to a "free" or "costless" operation, such as doing nothing at all, or performing a simple transformation that requires no special resources. In the world of quantum computing, some operations are cheap and easy to perform, while others are expensive and prone to errors. The researchers asked: if you hand them a complex circuit, can they efficiently decide if it is essentially equivalent to one of these cheap operations, allowing them to delete the expensive parts? Their findings show that for a vast range of scenarios, this question is not just difficult; it is PP-hard. This classification places the problem far beyond the reach of efficient polynomial-time algorithms, implying that no such algorithm exists unless the complexity class P equals PP. While this does not rule out exponential-time solutions or methods for specific instances, it indicates that the task is fundamentally intractable for general cases.

The researchers focused on three specific ways to measure how different two quantum operations are. One method looks at the average difference between the two, another looks at the worst-case difference, and a third accounts for the fact that quantum states can be shifted in time without changing their physical meaning. They tested these measurements against different sets of "cheap" operations. In some cases, the cheap operations were just the identity (doing nothing). In others, they included a broader class of operations known as Clifford gates, which are powerful but still relatively easy to handle. In a third case, they looked at operations that do not create superpositions, meaning they behave more like classical logic gates.

The study proved that for all these combinations, the problem of deciding if a circuit is close enough to a cheap operation is "PP-hard." This is a specific classification in computer science that places the problem far beyond the reach of efficient algorithms. It means that even if you allow the computer to make mistakes or use randomness, and even if you only ask for an approximate answer within a small margin of error, the task remains intractable for general inputs. The researchers showed that this hardness holds true even when the circuit is built from standard, widely available quantum gates. In fact, they demonstrated that the problem is so hard that it remains difficult even if you restrict the circuit to use only classical, reversible gates—operations that do not use the unique quantum property of superposition at all.

This result has a direct and sobering implication for the future of quantum software. Optimization tools, which are essential for making quantum computers practical, are facing a wall. The researchers proved that finding the best possible simplified version of a circuit is not just a matter of writing better code; the problem itself is fundamentally too complex to solve quickly in the general case. Whether you are trying to minimize the total number of steps, the number of expensive gates, or the depth of the circuit, the task of finding the optimal solution is as hard as the most difficult problems in the known hierarchy of computational complexity.

The team also explored how this difficulty changes depending on how close you need the approximation to be. They found that for many of the metrics they studied, the problem is hard for almost any non-zero tolerance. If you ask the computer to find a circuit that is even slightly different from the original, the task becomes impossible to solve efficiently in the general case. The only time the problem becomes easy is when you allow the answer to be so loose that it accepts almost any circuit as a valid match. This suggests that the "sweet spot" for optimization, where we want a good balance between accuracy and simplicity, is exactly where the computational difficulty is at its peak.

One of the most striking aspects of their work is that this hardness persists even when the quantum resources are stripped away. They showed that the problem remains difficult even when the circuit is restricted to operations that cannot create quantum superpositions. This indicates that the difficulty is not a unique feature of the strange, counterintuitive nature of quantum mechanics, but rather a deep structural property of how these operations relate to one another. The researchers also confirmed that their results apply to a wide variety of distance measures used by engineers, meaning that no matter how you choose to define "closeness" between two circuits, the optimization problem remains stubbornly hard.

In the end, this work serves as a crucial reality check for the field. While quantum computers hold immense potential, the tools needed to make them run efficiently are hitting a theoretical ceiling. The researchers did not find a new algorithm to break this barrier; instead, they proved that such a barrier exists. They showed that the dream of automatically and perfectly optimizing any quantum circuit is likely unattainable. Instead, the field must rely on heuristics—smart guesses and approximations that work well in practice but cannot guarantee the best possible result. The path forward is not to find a faster way to solve the perfect optimization problem, but to accept that the perfect solution is out of reach and to design systems that can thrive with good-enough approximations.

Technical Summary: On the Hardness of Approximate Quantum Circuit Membership and Optimization

1. Problem Definition

The paper investigates the computational complexity of two fundamental problems in quantum circuit theory: Approximate Membership and Approximate Optimization.

Approximate Membership ( $\text{ApproxMember}$ ): Given a quantum circuit $C$ $C$ over a gate-set $G$ $G$ , a set of unitaries $S$ $S$ , a distance metric $m$ $m$ , and a tolerance $\epsilon$ $ϵ$ , decide whether there exists a unitary $U \in S$ $U \in S$ such that the distance $d_m(C, U) \le \epsilon$ $d_{m} (C, U) \leq ϵ$ .
- A special case is Approximate Identity ( $\text{ApproxId}$ ), where $S = \{I\}$ .
- The paper considers three specific sets for $S$ $S$ :
  1. $S = \{I\}$ (Identity).
  2. $S \subseteq S_{\text{Cliff}}$ (Unitaries implementable by Clifford circuits).
  3. $S \subseteq S_{\text{GP}}$ (Generalized Permutation matrices, i.e., unitaries that do not create superposition).
Approximate Optimization ( $\text{ApproxOpt}$ ): Given a circuit $C$ , a cost function $f$ , and a budget $k$ , decide if there exists an equivalent circuit $C'$ such that $d_m(C, C') \le \epsilon$ and $f(C') \le k$ . The cost function $f$ is characterized by its "free set" $S_f = \{U_{C'} \mid f(C') = 0\}$ .

The study focuses on promise-free inputs, contrasting with previous work (Janzing, Wocjan, and Beth, 2005) which established QMA-completeness for the "non-identity check" problem under a promise that the circuit is either close to or far from the identity. This work removes that promise, asking whether the problem remains hard when the input circuit's distance to the target set is unknown.

The authors analyze three standard metrics for measuring distance between unitaries:

Sine Metric: Based on the trace, capturing average-case differences ( $d_{\text{Sine}}$ ).
Spectral Metric: Based on the operator norm, capturing worst-case differences ( $d_{\text{sp}}$ ).
Operator Metric: The global-phase-invariant version of the spectral metric ( $d_{\text{op}}$ ).

2. Methodology

The authors establish hardness by reducing the complexity class PP (Probabilistic Polynomial time) to the approximate membership problem. The core of their methodology involves the following steps:

Source Problem: They utilize AtMostSat, a PP-hard problem asking whether a propositional formula $\phi$ is satisfied by at most a fraction $\beta$ of its assignments. They introduce a promise version, PromiseAtMostSat, where the fraction of satisfying assignments is promised to be at most $\kappa$ .
Promise-to-Approximate Reduction: They prove that PromiseApproxId (checking if a circuit is $\epsilon$ $ϵ$ -close to identity under the promise it is $\tau$ $τ$ -close) is PP-hard. This is achieved by constructing Clifford+T circuits $C$ $C$ from formulas $\phi$ $ϕ$ such that the distance $d_m(I, C)$ $d_{m} (I, C)$ is a strictly increasing function $g(\gamma(\phi))$ $g (γ (ϕ))$ of the satisfying fraction $\gamma(\phi)$ $γ (ϕ)$ .
- For the Sine metric, they construct a circuit implementing a controlled-XOR operation ( $|x\rangle|b\rangle \mapsto |x\rangle|b \oplus \phi(x)\rangle$ ).
- For the Spectral and Operator metrics, they utilize the Grover iterate to construct circuits with eigenangles dependent on $\gamma(\phi)$ . For the operator metric, they employ tensor products of these circuits to control the arc length of eigenangles on the unit circle.
Removing the Promise:
- Case $S = \{I\}$ : The hardness of the promise version directly implies the hardness of the promise-free version for the specific ranges of $\epsilon$ .
- Case $S \subseteq S_{\text{Cliff}}$ : They utilize a triangle inequality argument (Lemma 6). They show that for sufficiently small $\epsilon$ (specifically $\epsilon < \sqrt{2}/4$ ), if a circuit $C$ is promised to be close to $I$ , the only elements in $S_{\text{Cliff}}$ that can be $\epsilon$ -close to $C$ are those at distance 0 from $I$ (i.e., $I$ itself). This relies on lower-bounding the minimum non-zero distance between $I$ and any other Clifford unitary.
- Case $S \subseteq S_{\text{GP}}$ : They construct specific circuits where the distance to the set of generalized permutation matrices is exactly the distance to the identity for small $\gamma(\phi)$ , allowing a direct reduction from the promise problem. This reduction specifically applies when the identity $I$ is included in the set $S$ (i.e., $I \in S \subseteq S_{\text{GP}}$ ).

3. Key Contributions and Results

Main Theorem (Theorem 1)

The paper proves that ApproxMember is PP-hard for a wide range of parameters, provided the gate-set $G$ can exactly implement Clifford+T. The hardness holds for:

Sets $S$ : $S=\{I\}$ , $I \in S \subseteq S_{\text{Cliff}}$ , and $I \in S \subseteq S_{\text{GP}}$ .
Metrics: Sine, Spectral, and Operator metrics.
Tolerance $\epsilon$ :
- For $S=\{I\}$ and trace-based (Sine) metrics: PP-hard for all $0 < \epsilon < 1$ (the full diameter).
- For $S=\{I\}$ and Spectral/Operator metrics: PP-hard for all $0 < \epsilon < 2$ .
- For $I \in S \subseteq S_{\text{Cliff}}$ : PP-hard for $0 < \epsilon < \sqrt{2}/4 \approx 0.3536$ .
- For $I \in S \subseteq S_{\text{GP}}$ : PP-hard for $0 < \epsilon < 1$ (Sine) and $0 < \epsilon < \sqrt{2}$ (Spectral/Operator).

Corollary 1 (Optimization Hardness)

The results directly imply that ApproxOpt is PP-hard for minimizing total gate depth/count, non-Clifford gate depth/count, and superposition gate depth/count, within the corresponding $\epsilon$ ranges.

Specific Technical Findings

Hardness for Classical-Reversible Gates: Even when the gate-set $G$ consists only of classical-reversible gates (e.g., X, CNOT, Toffoli) which cannot create superposition, the ApproxId problem under the Sine metric remains PP-hard for all $0 < \epsilon < 1$ .
Robustness: The hardness results generalize to any distance measure derived from the Sine, Spectral, or Operator metrics via a strictly increasing function. Furthermore, the problems remain PP-hard even if the goal is only to approximate the minimum cost within any factor (constant or not), as the hardness holds when the optimal cost is 0.
Comparison to Prior Work: The paper strengthens the result of Janzing, Wocjan, and Beth (2005). While their result showed QMA-completeness for the promise problem of non-identity check, this work shows that the promise-free problem is PP-hard (a class believed to be strictly harder than QMA) for a broader set of metrics and sets $S$ .

4. Significance and Claims

The authors claim that their results demonstrate that approximate quantum circuit optimization is fundamentally harder over promise-free inputs compared to the QMA-completeness of the promise-based non-identity check.

Resource Independence: The hardness persists regardless of the quantum resources available (any gates, non-Clifford gates, or superposition).
Metric Independence: The hardness holds across various distance metrics (trace-based, spectral, and operator).
Practical Implications: Since standard hardware gate-sets (like Clifford+T) satisfy the conditions, these hardness results apply directly to real-world quantum compilation and optimization tasks. The results indicate that finding an approximately equivalent circuit with minimal cost (e.g., minimal T-count or depth) is intractable for classical computers, even when allowing for approximation errors, unless the error tolerance is trivially large (exceeding the diameter of the metric space).

The paper concludes by noting open problems regarding the complexity for larger values of $\epsilon$ (specifically $\epsilon \ge \sqrt{2}/4$ for Clifford sets and $\epsilon \ge \sqrt{2}$ for permutation sets) and matching upper bounds, though it notes that for algebraic gate-sets and the Sine metric at $\epsilon = \sqrt{2}/2$ , the problem is PP-complete.