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:2611.04381

On the Hardness of Approximate Quantum Circuit Membership and Optimization

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

quant-phcs.CCSubmitted Nov 3, 2026• Announced Nov 4, 2026• 0 citations
arXivHTMLPDF

Abstract

Quantum circuit optimization is an indispensable component of the quantum software stack, used to reduce noise, maximize performance, alleviate costs of quantum error correction, or target specific hardware. A related problem is approximate membership: for a fixed set of unitaries $S$, decide whether a given circuit $C$ is within distance $\varepsilon$ of a unitary in $S$ under some metric $m$. Membership is a special case of optimization, where $S$ is a set of unitaries implementable at no cost (e.g., with noise-minimal circuits, or without magic states). Janzing, Wocjan, and Beth (Int. J. Quantum Inf., 2005) showed that, for the operator metric, the case $S=\{I\}$ (approximate identity) is QMA-complete when $C$ is promised to be either close to the identity or far from it. We generalize this setting in three directions: (i) promise-free inputs, (ii) besides $S=\{I\}$, sets $S$ containing only Clifford unitaries, or only generalized permutation matrices (i.e., no superposition), and (iii) the trace-based, spectral, and operator metrics. We show that, in all cases, approximate membership is PP-hard for wide ranges of $\varepsilon$, provided $C$'s gate-set can implement Clifford+T, as the gate-sets of standard hardware do. If $S=\{I\}$, or if $S$ contains only generalized permutation matrices, $I\in S$, and $m$ is a trace-based distance, PP-hardness holds for all non-trivial $\varepsilon$. If $S=\{I\}$ and $m$ is a trace-based distance, PP-hardness holds even for circuits over classical-reversible gate-sets. Our results indicate that approximate membership is harder over promise-free inputs than the QMA-complete promise version, and that this hardness persists across quantum resources (any gates, non-Clifford, superposition) and distance metrics. They directly imply PP-hardness of circuit optimization when minimizing total, non-Clifford, or superposition gate depth or count.

AI Summary

The paper studies promise-free approximate circuit membership: given a circuit $C$, decide whether its unitary lies within a fixed tolerance $\varepsilon$ of some element of a free set $S$. It considers identity, Clifford-only, and generalized-permutation free sets, using trace-based Sine distance, spectral norm distance, and spectral distance minimized over global phase. Unlike standard QMA-complete non-identity check, no separation gap around the decision threshold is promised. For gate sets that exactly implement Clifford+$T$, membership is PP-hard for every polynomial-time-computable tolerance in the following ranges. For $S=\{I\}$, the ranges are $0<\varepsilon<1$ for Sine distance and $0<\varepsilon<2$ for spectral and phase-invariant operator distance—the entire nontrivial ranges. For any $I\in S\subseteq\mathrm{Clifford}$, hardness holds for $0<\varepsilon<\sqrt{2}/4$ under all three metrics. For any $I\in S$ consisting of generalized permutation matrices, it holds up to $1$ for Sine distance and $\sqrt{2}$ for the other metrics. Identity testing in Sine distance remains PP-hard for classical-reversible circuits. Reductions encode Boolean satisfying-assignment fractions into traces or Grover-iterate eigenangles. Clifford membership follows from a constant separation between identity and nontrivial Cliffords; generalized-permutation membership uses dedicated nearest-unitary bounds. Setting the optimization budget to zero transfers hardness to total, non-Clifford, and superposition gate-count/depth optimization, including multiplicative approximation. The paper leaves larger-tolerance Clifford and spectral/operator generalized-permutation cases unresolved, along with matching upper bounds except for one PP-complete trace-distance identity case. The results concern exact threshold decisions, not inverse-polynomial-gap variants.

No sign of AI-generated textAI use disclosed
An initial draft of the proofs of~\cref{lemma:spectral_GP_distance} and~\cref{theorem:hardness_approx_non_superpos_sp_op} were generated using Claude Opus 5.5 and subsequently checked line by line and rewritten by the authors.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
26 pages, 4 figures

Related papers

Exact Quantum Circuit Optimization is co-NQP-hard

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

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) all 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.

arXiv:2510.16420•Oct 18, 2025•6 citations

(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•2 citations

Optimising quantum circuits is generally hard

J.M.M. (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•40 citations

Approximate synthesis of general single-qubit unitaries over the Clifford+$\sqrt{T}$ gate set

Mathias Weiden, Jae Won Kim, Justin Kalloor +2 more

For the standard Clifford+$T$ gate set, deterministic, ancilla-free synthesis now attains the minimal $T$-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The $\sqrt{T}$ gate rotates by half the angle of $T$, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+$\sqrt{T}$ algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from $\varepsilon=10^{-3}$ to $10^{-8}$, the cost of Clifford+$\sqrt{T}$ circuits scales as $2.4\log_2(1/\varepsilon)$ compared to $3.0\log_2(1/\varepsilon)$ for $T$-count-optimal Clifford+$T$ circuits. Once a one-time catalyst state is amortized, the Clifford+$\sqrt{T}$ circuits are never costlier than their Clifford+$T$ counterparts.

quant-pharXiv:2609.16659•Sep 16, 2026•0 citations

Non-parametric Greedy Optimization of Parametric Quantum Circuits

Koustubh Phalak, Swaroop Ghosh

The use of Quantum Neural Networks (QNN) that are analogous to classical neural networks, has greatly increased in the past decade owing to the growing interest in the field of Quantum Machine Learning (QML). A QNN consists of three major components: (i) data loading/encoding circuit, (ii) Parametric Quantum Circuit (PQC), and (iii) measurement operations. Under ideal circumstances the PQC of the QNN trains well, however that may not be the case for training under quantum hardware due to presence of different kinds of noise. Deeper QNNs with high depths tend to degrade more in terms of performance compared to shallower networks. This work aims to reduce depth and gate count of PQCs by replacing parametric gates with their approximate fixed non-parametric representations. We propose a greedy algorithm to achieve this such that the algorithm minimizes a distance metric based on unitary transformation matrix of original parametric gate and new set of non-parametric gates. From this greedy optimization followed by a few epochs of re-training, we observe roughly 14% reduction in depth and 48% reduction in gate count at the cost of 3.33# reduction in inferencing accuracy. Similar results are observed for a different dataset as well with different PQC structure.

arXiv:2401.15442•International Symposium on Quality Electronic Design (ISQED)•Apr 3, 2024•3 citations

Approximation by Quantum Circuits

Emanuel H. Knill

In a recent preprint by Deutsch et al. [1995] the authors suggest the possibility of polynomial approximability of arbitrary unitary operations on $n$ qubits by 2-qubit unitary operations. We address that comment by proving strong lower bounds on the approximation capabilities of g-qubit unitary operations for fixed g. We consider approximation of unitary operations on subspaces as well as approximation of states and of density matrices by quantum circuits in several natural metrics. The ability of quantum circuits to probabilistically solve decision problem and guess checkable functions is discussed. We also address exact unitary representation by reducing the upper bound by a factor of n^2 and by formalizing the argument given by Barenco et al. [1995] for the lower bound. The overall conclusion is that almost all problems are hard to solve with quantum circuits.

arXiv:quant-ph/9508006•Aug 8, 1995•258 citations
Quantum circuit optimization is an indispensable component of the quantum software stack, used to reduce noise, maximize performance, alleviate costs of quantum error correction, or target specific hardware. A related problem is approximate membership: for a fixed set of unitaries SSS, decide whether a given circuit CCC is within distance ε\varepsilonε of a unitary in SSS under some metric mmm. Membership is a special case of optimization, where SSS is a set of unitaries implementable at no cost (e.g., with noise-minimal circuits, or without magic states). Janzing, Wocjan, and Beth (Int. J. Quantum Inf., 2005) showed that, for the operator metric, the case S={I}S=\{I\}S={I} (approximate identity) is QMA-complete when CCC is promised to be either close to the identity or far from it.
We generalize this setting in three directions: (i) promise-free inputs, (ii) besides S={I}S=\{I\}S={I}, sets SSS containing only Clifford unitaries, or only generalized permutation matrices (i.e., no superposition), and (iii) the trace-based, spectral, and operator metrics. We show that, in all cases, approximate membership is PP-hard for wide ranges of ε\varepsilonε, provided CCC's gate-set can implement Clifford+T, as the gate-sets of standard hardware do. If S={I}S=\{I\}S={I}, or if SSS contains only generalized permutation matrices, I∈SI\in SI∈S, and mmm is a trace-based distance, PP-hardness holds for all non-trivial ε\varepsilonε. If S={I}S=\{I\}S={I} and mmm is a trace-based distance, PP-hardness holds even for circuits over classical-reversible gate-sets.
Our results indicate that approximate membership is harder over promise-free inputs than the QMA-complete promise version, and that this hardness persists across quantum resources (any gates, non-Clifford, superposition) and distance metrics. They directly imply PP-hardness of circuit optimization when minimizing total, non-Clifford, or superposition gate depth or count.
The paper studies promise-free approximate circuit membership: given a circuit CCC, decide whether its unitary lies within a fixed tolerance ε\varepsilonε of some element of a free set SSS. It considers identity, Clifford-only, and generalized-permutation free sets, using trace-based Sine distance, spectral norm distance, and spectral distance minimized over global phase. Unlike standard QMA-complete non-identity check, no separation gap around the decision threshold is promised.
For gate sets that exactly implement Clifford+TTT, membership is PP-hard for every polynomial-time-computable tolerance in the following ranges. For S={I}S=\{I\}S={I}, the ranges are 0<ε<10<\varepsilon<10<ε<1 for Sine distance and 0<ε<20<\varepsilon<20<ε<2 for spectral and phase-invariant operator distance—the entire nontrivial ranges. For any I∈S⊆CliffordI\in S\subseteq\mathrm{Clifford}I∈S⊆Clifford, hardness holds for 0<ε<2/40<\varepsilon<\sqrt{2}/40<ε<2​/4 under all three metrics. For any I∈SI\in SI∈S consisting of generalized permutation matrices, it holds up to 111 for Sine distance and 2\sqrt{2}2​ for the other metrics. Identity testing in Sine distance remains PP-hard for classical-reversible circuits.
Reductions encode Boolean satisfying-assignment fractions into traces or Grover-iterate eigenangles. Clifford membership follows from a constant separation between identity and nontrivial Cliffords; generalized-permutation membership uses dedicated nearest-unitary bounds. Setting the optimization budget to zero transfers hardness to total, non-Clifford, and superposition gate-count/depth optimization, including multiplicative approximation.
The paper leaves larger-tolerance Clifford and spectral/operator generalized-permutation cases unresolved, along with matching upper bounds except for one PP-complete trace-distance identity case. The results concern exact threshold decisions, not inverse-polynomial-gap variants.
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) all 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.
Approximate synthesis of general single-qubit unitaries over the Clifford+T\sqrt{T}T​ gate set
For the standard Clifford+TTT gate set, deterministic, ancilla-free synthesis now attains the minimal TTT-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The T\sqrt{T}T​ gate rotates by half the angle of TTT, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+T\sqrt{T}T​ algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from ε=10−3\varepsilon=10^{-3}ε=10−3 to 10−810^{-8}10−8, the cost of Clifford+T\sqrt{T}T​ circuits scales as 2.4log⁡2(1/ε)2.4\log_2(1/\varepsilon)2.4log2​(1/ε) compared to 3.0log⁡2(1/ε)3.0\log_2(1/\varepsilon)3.0log2​(1/ε) for TTT-count-optimal Clifford+TTT circuits. Once a one-time catalyst state is amortized, the Clifford+T\sqrt{T}T​ circuits are never costlier than their Clifford+TTT counterparts.
The use of Quantum Neural Networks (QNN) that are analogous to classical neural networks, has greatly increased in the past decade owing to the growing interest in the field of Quantum Machine Learning (QML). A QNN consists of three major components: (i) data loading/encoding circuit, (ii) Parametric Quantum Circuit (PQC), and (iii) measurement operations. Under ideal circumstances the PQC of the QNN trains well, however that may not be the case for training under quantum hardware due to presence of different kinds of noise. Deeper QNNs with high depths tend to degrade more in terms of performance compared to shallower networks. This work aims to reduce depth and gate count of PQCs by replacing parametric gates with their approximate fixed non-parametric representations. We propose a greedy algorithm to achieve this such that the algorithm minimizes a distance metric based on unitary transformation matrix of original parametric gate and new set of non-parametric gates. From this greedy optimization followed by a few epochs of re-training, we observe roughly 14% reduction in depth and 48% reduction in gate count at the cost of 3.33# reduction in inferencing accuracy. Similar results are observed for a different dataset as well with different PQC structure.
In a recent preprint by Deutsch et al. [1995] the authors suggest the possibility of polynomial approximability of arbitrary unitary operations on nnn qubits by 2-qubit unitary operations. We address that comment by proving strong lower bounds on the approximation capabilities of g-qubit unitary operations for fixed g. We consider approximation of unitary operations on subspaces as well as approximation of states and of density matrices by quantum circuits in several natural metrics. The ability of quantum circuits to probabilistically solve decision problem and guess checkable functions is discussed. We also address exact unitary representation by reducing the upper bound by a factor of n^2 and by formalizing the argument given by Barenco et al. [1995] for the lower bound. The overall conclusion is that almost all problems are hard to solve with quantum circuits.