On the Hardness of Approximate Quantum Circuit Membership and Optimization

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

Nov 3, 2026arXiv:2611.04381v1

quant-phcs.CC

Scorecard· 16/16

6.0/10 impact

Solid, comprehensive complexity-theoretic generalization of known hardness results for quantum circuit optimization, with clean proofs but limited practical effect and a natural technique.

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 Impact Assessments

(1 model)

Core Contribution

The paper studies the approximate membership problem: given a circuit C, is it within distance ε of some unitary in a fixed set S? It also studies the corresponding optimization problems. It generalizes the Janzing–Wocjan–Beth QMA-completeness result for non-identity check in three directions:

It removes the promise gap.

It adds sets S of Clifford unitaries or generalized permutation matrices, alongside S={I}.

It covers three metrics: Sine (trace-based), spectral, and operator.

Over any gate set that implements Clifford+T exactly, the main result is PP-hardness for wide ranges of ε. For S={I} the range is all non-trivial ε, and for Sine with S⊆S_GP it is also all non-trivial ε. Because the cost functions reduce to membership with minimum cost 0, the hardness carries over to optimization of total, T-, and H-count or depth, and even to approximating the minimum cost within any factor. For the Sine metric with S={I}, hardness holds even for classical-reversible gate sets.

The technique is clean:

A reduction from AtMostSat uses a promise-scaling lemma.

The Sine case uses an oracle circuit whose trace is 2^{n+1}(1−γ).

The spectral and operator cases use a Grover-iterate squared, giving eigenangles {0, ±2θ} with sin²(θ/2)=γ. For the operator metric, tensor powers of this circuit control the shortest arc.

Clifford sets are handled by a triangle-inequality argument, using a lower bound of √2/2 on the minimal nonzero distance from I to any Clifford. That bound follows from stabilizer overlaps for the Sine metric, from the Pauli normalizer argument for the operator metric, and from the Z[1/√2,i] ring argument for the spectral metric.

Generalized permutations are handled by direct closed-form distance calculations: a φ-controlled (HZ)^⊗ℓ for Sine, and Lemma 9 for the spectral and operator metrics.

Methodological Rigor

The proofs look sound and careful. Specific points in favour:

The modular structure (Lemma 3 as a generic reduction template) is clean.

Ancilla restoration is handled explicitly.

P-time computability of thresholds is tracked.

The authors state that the AI-generated drafts of Lemma 9 and Theorem 5 were checked line by line.

I did not find an error. The Sine closed form is straightforward. The Grover-based construction is standard. The Lemma 9 case analysis (L non-identity versus identity) is somewhat intricate but seems correct. The paper also notes one tight case: ApproxId(Sine, √2/2) is PP-complete, since d² is a quantum acceptance probability.

Limitations:

No upper bounds in general.

The Clifford range (0, √2/4) and the spectral/operator range for S_GP are not shown to be tight.

The hardness is for the unconstrained decision problem over circuits with exponentially close-to-threshold behavior, because the construction encodes a satisfying fraction in the distance. This is a worst-case result.

Potential Impact

This is a theoretical result with limited direct practical effect. It gives rigorous complexity-theoretic justification that no efficient general-purpose exact optimizer or approximate-identity checker exists unless PP-collapse-type events occur. Pruning circuits near the identity, peephole optimization, and T-count minimization all inherit PP-hardness. This strengthens the Van de Wetering–Amy NP-hardness result (extending its ε range and the metrics covered), and improves on the Janzing et al. QMA-completeness by showing that the promise-free version is PP-hard. It also sharpens the authors' own prior co-NQP-hardness result for the exact case.

Practitioners already use heuristics, so the hardness will not change practice. The main value is as a reference for the complexity of compilation problems and as a technical toolkit. The reusable pieces are the gadget lemmas, the Clifford gap bound, and the promise-scaling lemma. The transfer to derived measures (Bures, average gate fidelity) broadens coverage.

Timeliness & Relevance

Circuit optimization and compilation are central to both NISQ and fault-tolerant efforts. T-count and non-Clifford resource minimization are major bottlenecks. A clear statement of the hardness landscape for approximate optimization is timely. It is also a natural follow-on to recent exact-optimization hardness results.

Strengths

It is comprehensive: three metrics, three classes of S, a wide ε range, and the full non-trivial range in several cases.

It is robust: the hardness holds for classical-reversible gates in one case, for any approximation factor, and for derived metrics.

It is mathematically clean and well organized, with a reduction diagram.

It identifies a tight PP-completeness case.

Limitations

The result is incremental in conceptual terms: PP-hardness from a satisfying-fraction reduction is a fairly natural technique once the right gadgets are found.

The hardness is worst-case and gives no hint about average-case or structured instances.

It has no upper bounds beyond one case.

The arXiv date is odd (2611), but that does not matter for the assessment.

The audience is niche (quantum complexity and compilation theory).

Other Observations

Reproducibility is high for a theory paper, since the proofs are fully specified. There is no empirical component, so reproducibility, surprisingness, and related empirical dimensions are not strongly applicable. PP-hardness is expected given that the promise version is QMA-complete and promise-free versions are typically harder, so the results are moderately unsurprising. The paper does tighten a prior NP-hardness bound, giving some refutation or replication-style value, though it does not contest any prior claim.

Rating:6/ 10

Significance 5.5Rigor 8Novelty 5.5Clarity 7.5

Generated Nov 4, 2026

Comparison History (0)

No comparisons yet.

Scorecard· 16/16

6.0/10 impact

Solid, comprehensive complexity-theoretic generalization of known hardness results for quantum circuit optimization, with clean proofs but limited practical effect and a natural technique.