Metraipolis › archive › dc_73e37015f8ed

On the Hardness of Approximate Quantum Circuit Membership and Optimization — arXiv:2611.04381

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.04381
License (as archived)
CC0-1.0
Archived
2026-11-04T19:07:52.742Z
SHA-256 of the archived text
d54b15b875911cc5957ed2505ae2f8c8a8537fc671e408c3fc320db0653d1a11
Stable URL of this page
https://metraipolis.com/documento/dc_73e37015f8ed

How to cite

On the Hardness of Approximate Quantum Circuit Membership and Optimization — arXiv:2611.04381 — arXiv (en), https://arxiv.org/abs/2611.04381 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_73e37015f8ed (Metraipolis archive dc_73e37015f8ed, sha256 d54b15b875911cc5957ed2505ae2f8c8a8537fc671e408c3fc320db0653d1a11)
BibTeX
@misc{dc73e37015f8ed,
  title = {On the Hardness of Approximate Quantum Circuit Membership and Optimization — arXiv:2611.04381},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04381},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_73e37015f8ed; sha256 d54b15b875911cc5957ed2505ae2f8c8a8537fc671e408c3fc320db0653d1a11},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04381. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.04381 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:41:25.372Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).