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 S, decide whether a given circuit C is within distance ε 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 ε, 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∈ S, and m is a trace-based distance, PP-hardness holds for all non-trivial ε. 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.
Related
- Binary Optimization with Complex Constraints via Quantum Approximate Multi-Objective Optimization
- Depth analysis of the Quantum Approximate Optimization Algorithm with a Grover mixer
- Optimal FALQON for Quantum Approximate Optimization via Layer-wise Parameter Tuning
- The Overlap Gap Property: Separating Quantum and Quantum-Inspired Approximate Optimization Algorithms
- Quantum Approximate Optimization via Noise-Directed Adaptive Warm-Starting
BibTeX
@misc{kjelstrom2026hardness,
title = {{On the Hardness of Approximate Quantum Circuit Membership and Optimization}},
author = {Adam Husted Kjelstrøm and Jaco van de Pol and Andreas Pavlogiannis},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04381},
eprint = {2611.04381},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04381},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the Hardness of Approximate Quantum Circuit Membership and Optimization
AU - Adam Husted Kjelstrøm
AU - Jaco van de Pol
AU - Andreas Pavlogiannis
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04381
UR - https://arxiv.org/abs/2611.04381
AB - 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 ε 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 ε, 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∈ S, and m is a trace-based distance, PP-hardness holds for all non-trivial ε. 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.
ER -