betaFeedback

WorksPhysics and Astronomy

On the Hardness of Approximate Quantum Circuit Membership and Optimization

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 SS, decide whether a given circuit CC is within distance ε\varepsilon of a unitary in SS under some metric mm. Membership is a special case of optimization, where SS 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\} (approximate identity) is QMA-complete when CC 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\}, sets SS 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 CC's gate-set can implement Clifford+T, as the gate-sets of standard hardware do. If S={I}S=\{I\}, or if SS contains only generalized permutation matrices, I∈SI\in S, and mm is a trace-based distance, PP-hardness holds for all non-trivial ε\varepsilon. If S={I}S=\{I\} and mm 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.

Introduction

Optimizing quantum circuits, that is, given a circuit CC, obtaining an (approximately) equivalent circuit C′C' that minimizes an objective function, is a standard task to improve the performance of quantum computers, thus producing circuits that are tailored to a given quantum run-time environment. By picking different objective functions, optimization can target both NISQ and error-corrected platforms by minimizing, e.g., the number of multi-qubit gates or non-Clifford resources. Permitting a bit of slack, i.e., allowing an output circuit that is a close (but not necessarily exact) match, is typical [1, 2, 3, 4, 5, 6, 7, 8, 9]. This is partly because it gives the optimizer more freedom, which may yield better results, and partly because it is often unavoidable: for finite gate-sets such as Clifford+TT, universality holds only approximately, so most unitaries cannot be implemented exactly. Circuit optimization is often phrased as a decision problem given a circuit CC and budget kk. It is parameterized by a cost function ff, a metric mm, a tolerance ε≥0\varepsilon\ge0, and a gate-set G\mathcal{G}, where dm(C,C′)d_m(C,C') denotes the distance between the unitaries of CC and C′C' under mm:

ApproxOpt(f,m,ε,Gf,m,\varepsilon,\mathcal{G})

Input: A circuit CC over G\mathcal{G} and an integer k≥0k \ge0.

Question: Is there a circuit C′C' over G\mathcal{G} s.t. dm(C,C′)≤εd_m(C,C') \le\varepsilon and f(C′)≤kf(C') \le k?

Another common computational problem is the (approximate) equivalence question: given two circuits CC and C′C', are their corresponding unitaries ε\varepsilon-close to each other, according to some metric mm? The equivalence question often serves as a subroutine of peephole optimization, whereby a subcircuit CC can be replaced by a circuit C′C' with a small cost f(C′)f(C'), provided that it encodes an equivalent computation. The case where C′C' is the empty circuit (asking whether CC is ε\varepsilon-close to the identity) has received special attention. Indeed, besides being theoretically fundamental, this question also underpins practical circuit-reduction techniques, whereby parts of a circuit are deleted if they are deemed to be close enough to the identity [10, 11, 12]. When CC comes with a promise that its distance from II in the operator metric is either ≤ε\le\varepsilon or ≥δ\ge\delta with δ−ε>n−O(1)\delta-\varepsilon> n^{-O(1)}, the resulting problem, known as non-identity check, is well known to be QMA-complete over gate-sets G\mathcal{G} of arbitrary one- and two-qubit gates [13]. On the other hand, insisting on ε=0\varepsilon=0 corresponds to exact non-identity check, which is NQP-complete for circuits CC over Clifford+TT [14, 15, 16].

A natural generalization of equivalence is the membership question. It is parameterized by a set of unitaries S\mathcal{S} that are considered to be of minimal cost. Instead of comparing with a single candidate circuit C′C', the task is to decide whether CC is approximately equivalent to any element of S\mathcal{S}.

ApproxMember(S,m,ε,G\mathcal{S},m,\varepsilon,\mathcal{G})

Input: A circuit CC over G\mathcal{G}.

Question: Is there a U∈SU \in\mathcal{S} s.t. dm(C,U)≤εd_m(C,U) \le\varepsilon?

Approximate equivalence with the empty circuit is the special case S={I}\mathcal{S}=\{\mathbb{I}\} of ApproxMember, which we call ApproxID. In this work, we consider two additional cases for S\mathcal{S}, namely, S⊆SCliff\mathcal{S} \subseteq\mathcal{S}_{\mathrm{Cliff}} and S⊆SGP\mathcal{S} \subseteq\mathcal{S}_{\mathrm{GP}}, where SCliff\mathcal{S}_{\mathrm{Cliff}} is the set of unitaries implemented by Clifford circuits and SGP\mathcal{S}_{\mathrm{GP}} is the set of generalized permutation matrices (which do not create superposition). We further require that I∈SI\in\mathcal{S}. Each case asks whether CC can be approximated to precision ε\varepsilon with restricted quantum resources: no gates at all (S={I}\mathcal{S}=\{I\}), only Clifford gates (S⊆SCliff\mathcal{S}\subseteq\mathcal{S}_{\mathrm{Cliff}}), or no superposition gates (S⊆SGP\mathcal{S}\subseteq\mathcal{S}_{\mathrm{GP}}).

We consider three standard metrics mm for defining the distance between two unitaries UU and VV. The Sine metric is defined as a function of the trace ∣Tr⁡(U†V)∣|\operatorname{Tr}(U^\dagger V)|, which captures the “average-case” difference between U∣ψ⟩U|\psi\rangle and V∣ψ⟩V|\psi\rangle. Related measures include the Bures angle, Bures metric [17], and average gate distance measures [18]. These have seen extensive use in quantum circuit synthesis [2, 3, 4, 5, 6, 7]. The spectral metric, induced by the operator norm, captures the “worst-case” difference between U∣ψ⟩U|\psi\rangle and V∣ψ⟩V|\psi\rangle. This is the metric in which the Solovay-Kitaev theorem is stated [1]; it is also used for quantum circuit optimization [8, 9]. The operator metric, also considered in [16], is given by the minimum of the spectral metric between UU and eiαVe^{i\alpha}V over α∈R\alpha\in\mathbb{R}. This is a natural choice as the global phase is physically irrelevant, potentially permitting better optimizations.

Our contributions. Our main result is that ApproxMember(S,m,ε,G)(\mathcal{S},m,\varepsilon,\mathcal{G}) is PP-hard for every set of unitaries S\mathcal{S}, metric mm, and tolerance ε\varepsilon covered by Table 1, where ε\varepsilon is P-time computable, i.e., computable to bb bits of precision in time bO(1)b^{O(1)}.

mmIdentityAny Clifford setAny generalized permutation set
Trace (Sine)(0,1)(0,1)(0,2/4)(0,\sqrt{2}/4)(0,1)(0,1)
Spectral(0,2)(0,2)(0,2/4)(0,\sqrt{2}/4)(0,2)(0,\sqrt{2})
Operator(0,2)(0,2)(0,2/4)(0,\sqrt{2}/4)(0,2)(0,\sqrt{2})

Table 1. The open interval of P-time computable ε\varepsilon for which Theorem 1 establishes PP-hardness for ApproxMember(S,m,ε,G)(\mathcal{S},m,\varepsilon,\mathcal{G}), per metric mm and set of unitaries S\mathcal{S}, where the columns cover S={I}\mathcal{S}=\{I\}, every S\mathcal{S} with I∈S⊆SCliffI\in\mathcal{S}\subseteq\mathcal{S}_{\mathrm{Cliff}}, and every S\mathcal{S} with I∈S⊆SGPI\in\mathcal{S}\subseteq\mathcal{S}_{\mathrm{GP}}, respectively. Boldface entries mark ranges equal to (0,Dm)(0,D_m), i.e., every ε\varepsilon strictly between 0 and the diameter DmD_m of the metric.

Theorem 1. Consider any gate-set G\mathcal{G} that exactly implements Clifford+T. For each combination of a set of unitaries S\mathcal{S}, metric mm, and P-time computable ε\varepsilon in the range given by the corresponding cell in Table 1, we have that ApproxMember(S,m,ε,G)(\mathcal{S},m,\varepsilon,\mathcal{G}) is PP-hard.

In the context of optimization, given some cost function ff, let Sf\mathcal{S}_f denote the set of unitaries UC′U_{C'} of circuits C′C' with f(C′)=0f(C')=0. Theorem 1 yields the following corollary.

Corollary 1. Consider any gate-set G\mathcal{G} that exactly implements Clifford+T. For each combination of a set of unitaries S\mathcal{S}, metric mm, and P-time computable ε\varepsilon in the range given by the corresponding cell in Table 1, and any ff for which Sf=S\mathcal{S}_f=\mathcal{S}, we have that ApproxOpt(f,m,ε,G)(f,m,\varepsilon,\mathcal{G}) is PP-hard.

A few consequences are worth highlighting, with ε\varepsilon P-time computable throughout. First, optimizing total gate depth or count is PP-hard under each of the three metrics for every ε\varepsilon strictly between 0 and the diameter of the metric. Second, the same holds for optimizing superposition gate depth or count, this time only for the Sine metric. Third, optimizing non-Clifford (e.g., T) gate depth or count is PP-hard for 0<ε<2/4≈0.35360<\varepsilon<\sqrt{2}/4\approx0.3536. This strengthens a result of Van de Wetering and Amy [16] who, under the operator metric, established NP-hardness for 0<ε<sin⁡(π/16)≈0.19510<\varepsilon<\sin(\pi/16)\approx0.1951, and also generalizes it to the other metrics. Fourth, ApproxId(Sine, ε\varepsilon, G\mathcal{G}), and ApproxOpt(ff, Sine, ε\varepsilon, G\mathcal{G}) for ff the total gate depth or count, remain PP-hard for all 0<ε<10 < \varepsilon< 1 even when G\mathcal{G} consists only of classical-reversible gates (e.g., X, CNOT, and TOF), which cannot create superposition; see Remark 1.

Our PP-hardness results also generalize in two ways. First, for any distance measure m2m_2 that is derivable from one of the considered metrics m1m_1, i.e., dm2(⋅,⋅)=g(dm1(⋅,⋅))d_{m_2}(\cdot,\cdot)=g(d_{m_1}(\cdot,\cdot)) for some strictly increasing function gg, the corresponding membership and optimization problems under m2m_2 are also PP-hard, for the respective approximation range obtained under gg (see Lemma 1). In particular, every Sine entry of Table 1 transfers to the Bures angle, the Bures metric, and the average gate distance at the correspondingly transformed threshold. This covers, for instance, the distance measures used in [4, 7], and shows that minimizing total depth or count to within any non-trivial (measure-specific) ε\varepsilon for any distance measure derived from the Sine metric is PP-hard. Second, the optimization problems remain PP-hard even to approximate the minimum cost within any factor (constant or not), because the hardness holds already when the minimum cost is 0 (i.e., the optimal circuit C′C' has f(C′)=0f(C')=0 and thus UC′∈SfU_{C'} \in\mathcal{S}_f); see Remark 2.

Paper organization and proof structure. The remainder of the paper is organized as follows. Section 2 fixes notation and recalls standard background on unitaries, quantum circuits, distance measures, and the class PP. Figure 1 shows the chain of reductions towards Theorem 1. We use AtMostSat as the source of PP-hardness, which asks whether a propositional formula φ\varphi is satisfied by at most a fraction β\beta of its assignments. In Section 3, Lemma 2 shows that AtMostSat remains PP-hard under the promise that at most a fraction κ\kappa of all assignments satisfy φ\varphi; we call this promise problem PromiseAtMostSat. We then use the PP-hardness of PromiseAtMostSat to establish the hardness of PromiseApproxId under all three metrics we consider (Theorem 2). In words, PromiseApproxId is a promise version of ApproxId, asking whether a circuit CC is ε\varepsilon-close to I under the promise that it is τ\tau-close to it. This naturally yields hardness for ApproxId (as the two problems agree on every circuit satisfying the promise), and thus completes the case S={I}\mathcal{S}=\{I\} of Theorem 1. In Section 4, we establish Theorem 1 for the cases I∈S⊆SCliffI \in\mathcal{S} \subseteq\mathcal{S}_{\mathrm{Cliff}} and I∈S⊆SGPI \in\mathcal{S} \subseteq\mathcal{S}_{\mathrm{GP}}. We show that the hard circuits CC for PromiseApproxId are also hard for ApproxMember(S\mathcal{S}) with I∈S⊆SCliffI \in\mathcal{S} \subseteq\mathcal{S}_{\mathrm{Cliff}}; intuitively,

Chain of reductions from AtMostSat to the three cases of Theorem 1

Figure 1. The chain of reductions. AtMostSat(β\beta) is by folklore PP-hard for every fixed efficiently computable 0<β<10 < \beta< 1, and each arrow is a Karp reduction, where an arrow into the bottom row reduces to ApproxMember(S,m,ε,G\mathcal{S},m,\varepsilon,\mathcal{G}) for the indicated S\mathcal{S}, with I∈SI \in\mathcal{S} throughout. Hardness for each S\mathcal{S} is obtained in one of three ways: via a reduction from a promise problem to its promise-free variant, as is the case for (∗)(*); via the triangle inequality argument of Lemma 6, which is the route taken for S⊆SCliff\mathcal{S} \subseteq\mathcal{S}_{\mathrm{Cliff}}; or via Lemma 3, as is the case for S⊆SGP\mathcal{S} \subseteq\mathcal{S}_{\mathrm{GP}}.

the promise that CC is always τ\tau-close to II, combined with the triangle inequality of the respective metric, implies that the only elements of SS that can be ϵ\epsilon-close to CC are those at distance 0 from II, and thus ApproxMember(S)(S) coincides with PromiseApproxId on circuits satisfying its promise, which is PP-hard by Theorem 2. The case of I∈S⊂SGPI \in S \subset S_{\mathrm{GP}} proceeds by reduction from PromiseAtMostSat: given φ\varphi, we construct circuits CC which are ϵ\epsilon-close to II when φ\varphi is satisfied by at most a fraction δ\delta of its assignments, and at a distance greater than ϵ\epsilon from SS otherwise (Theorems 4 and 5). We conclude in § 5 with open problems.

Preliminaries

In this section, we recall a number of standard definitions on unitary transformations, quantum circuits, metrics, and complexity theory.

Unitary Transformations and Quantum Circuits

Unitary Transformations. Throughout, we write U,V∈U(2n)U, V \in\mathcal{U}(2^n) for nn-qubit unitaries. A unitary (transformation) U∈C2n×2nU \in\mathbb{C}^{2^n \times2^n} satisfies UU†=U†U=IUU^{\dagger} = U^{\dagger}U = I. By the spectral theorem, UU admits a factorization as U=QDQ†U = QDQ^{\dagger}, where Q,D∈U(2n)Q, D \in\mathcal{U}(2^n) and DD is diagonal with the eigenvalues of UU on the diagonal. The eigenvalues of UU are of the form eiϕe^{i\phi} for real ϕ\phi; we call the set {ϕj}j\{\phi_j\}_j the eigenangles of UU.

References

  1. [1]Christopher M. Dawson and Michael A. Nielsen. “The Solovay-Kitaev algorithm”. Quantum Information & Computation 6, 81–95 (2006).
  2. [2]Vadym Kliuchnikov, Alex Bocharov, and Krysta M. Svore. “Asymptotically Optimal Topological Quantum Compiling”. Physical Review Letters 112 (2014).
  3. [3]Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. “Practical Approximation of Single-Qubit Unitaries by Single-Qubit Quantum Clifford and T Circuits”. IEEE Transactions on Computers 65, 161–172 (2016).DOI
  4. [4]Sumeet Khatri, Ryan LaRose, Alexander Poremba, Lukasz Cincio, Andrew T Sornborger, and Patrick J Coles. “Quantum-assisted quantum compiling”. Quantum 3, 140 (2019).DOI
  5. [5]Priyanka Mukhopadhyay. “Composability of global phase invariant distance and its application to approximation error management”. Journal of Physics Communications 5, 115017 (2021).DOI
  6. [6]Emil Géné­tay Johansen and Tapio Simula. “Fibonacci Anyons Versus Majorana Fermions: A Monte Carlo Approach to the Compilation of Braid Circuits in $SU(2)_k$ Anyon Models”. PRX Quantum 2 (2021).DOI
  7. [7]Vlad Gheorghiu, Michele Mosca, and Priyanka Mukhopadhyay. “T-count and T-depth of any multi-qubit unitary”. npj Quantum Information 8, 141 (2022).
  8. [8]Peter Selinger. “Efficient Clifford+T approximation of single-qubit operators”. Quantum Info. Comput. 15, 159–180 (2015).arxiv.org/abs/1212.6253
  9. [9]Neil J. Ross and Peter Selinger. “Optimal ancilla-free Clifford+T approximation of z-rotations”. Quantum Info. Comput. 16, 901–953 (2016).arxiv.org/abs/1403.2975
  10. [10]Adriano Barenco, Artur Ekert, Kalle-Antti Suominen, and Päivi Törmä. “Approximate quantum Fourier transform and decoherence”. Physical Review A 54, 139–146 (1996).DOI
  11. [11]Pau Escofet, Santiago Rodrigo, Rohit Sarma Sarkar, Carmen G. Almudéver, Eduard Alarcón, and Sergi Abadal. “Quantum Circuit Pruning: Improving Fidelity via Compilation-Aware Circuit Approximation”. In 2026 IEEE International Symposium on Circuits and Systems (ISCAS). Page 1521–1525. IEEE (2026).DOI
  12. [12]Christopher G. Yale, Rich Rines, Victory Omole, Bharath Thotakura, Ashlyn D. Burch, Matthew N.H. Chow, Megan Ivory, Daniel Lobser, Brian K. McFarland, Melissa C. Revelle, Susan M. Clark, and Pranav Gokhale. “Noise-aware circuit compilations for a continuously parameterized two-qubit gateset”. Physical Review Applied 24 (2025).
  13. [13]Dominik Janzing, Pawel Wocjan, and Thomas Beth. ““Non-identity-check” is QMA-complete”. International Journal of Quantum Information 3, 463–473 (2005).DOI
  14. [14]Yu Tanaka. “Exact non-identity check is NQP-complete”. International Journal of Quantum Information 8, 807–819 (2010).
  15. [15]Adam Husted Kjelstrøm, Andreas Pavlogiannis, and Jaco van de Pol. “Exact Quantum Circuit Optimization is co-NQP-hard” (2025). arXiv:2510.16420.
  16. [16]John van de Wetering and Matt Amy. “Optimising quantum circuits is generally hard” (2023). url: https://doi.org/10.48550/arXiv.2310.05958.
  17. [17]Zhihao Ma, Fu-Lin Zhang, and Jing-Ling Chen. “Fidelity induced distance measures for quantum states”. Physics Letters A 373, 3407–3409 (2009).DOI
  18. [18]Michael A Nielsen. “A simple formula for the average gate fidelity of a quantum dynamical operation”. Physics Letters A 303, 249–252 (2002).DOI
  19. [19]Michael A. Nielsen and Isaac L. Chuang. “Quantum Computation and Quantum Information: 10th Anniversary Edition”. Cambridge University Press. (2011).
  20. [20]John T. Gill. “Computational complexity of probabilistic Turing machines”. In Proceedings of the Sixth Annual ACM Symposium on Theory of Computing. Page 91–95. STOC ’74New York, NY, USA (1974). Association for Computing Machinery.
  21. [21]Richard P. Brent. “Fast Multiple-Precision Evaluation of Elementary Functions”. Journal of the ACM 23, 242–251 (1976).
  22. [22]Ker-I Ko. “Complexity Theory of Real Functions”. Progress in Theoretical Computer Science. Birkhäuser. Boston (1991).DOI
  23. [23]Janos Simon. “On Some Central Problems in Computational Complexity”. PhD thesis. Cornell University. (1975).
  24. [24]Seinosuke Toda. “PP is as Hard as the Polynomial-Time Hierarchy”. SIAM Journal on Computing 20, 865–877 (1991).DOI
  25. [25]Lov K. Grover. “A fast quantum mechanical algorithm for database search”. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. Page 212–219. STOC ’96 New York, NY, USA (1996). Association for Computing Machinery.arxiv.org/abs/quant-ph/9605043
  26. [26]Rafael Wagner, Filipa CR Peres, Emmanual Zambríni Cruzeiro, and Ernesto F Galvão. “Unitary-invariant method for witnessing nonstabilizerness in quantum processors”. Journal of Physics A: Mathematical and Theoretical 58, 285302 (2025).DOI
  27. [27]Héctor J. García, Igor L. Markov, and Andrew W. Cross. “On the geometry of stabilizer states”. Quantum Info. Comput. 14, 683–720 (2014).
  28. [28]Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. “Fast and Efficient Exact Synthesis of Single-Qubit Unitaries Generated by Clifford and T Gates”. Quantum Information & Computation 13, 607–630 (2013). arXiv:1206.5236.arxiv.org/abs/1206.5236
  29. [29]Tomoyuki Yamakami. “Analysis of Quantum Functions”. International Journal of Foundations of Computer Science 14, 815–852 (2003). arXiv:quant-ph/9909012.

Paper details

vlnc:W_n6azyms2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Claude Opus 5.5

View statement
Looking for related papers…
Contents