arXiv:2611.04381
On the Hardness of Approximate Quantum Circuit Membership and Optimization
Adam Husted Kjelstrøm, Jaco van de Pol, Andreas Pavlogiannis
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.
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