Exact Quantum Circuit Optimization is co-NQP-hard
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911471089221632 |
|---|---|
| author | Kjelstrøm, Adam Husted Pavlogiannis, Andreas van de Pol, Jaco |
| author_facet | Kjelstrøm, Adam Husted Pavlogiannis, Andreas van de Pol, Jaco |
| contents | As quantum computing resources remain scarce and error rates high, minimizing the resource consumption of quantum circuits is essential for achieving practical quantum advantage. Here we consider the natural problem of, given a circuit $C$, computing a circuit $C'$ which behaves equivalently on a desired subspace, and that minimizes a quantum resource type, expressed as the count or depth of (i) arbitrary gates, or (ii) non-Clifford gates, or (iii) superposition gates, or (iv) entanglement gates. We show that, when $C$ is expressed over any gate set that can implement the H and TOF gates exactly, each of the above optimization problems is hard for $\text{co-NQP}$, and hence outside the Polynomial Hierarchy, unless the Polynomial Hierarchy collapses. This complements recent results in the literature which established an $\text{NP}$-hardness lower bound when equivalence is over the full state space, and tightens the gap to the corresponding $\text{NP}^{\text{NQP}}$ upper bound known for cases (i)-(iii) over Clifford+T and (i)-(iv) over H+TOF circuits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_16420 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Exact Quantum Circuit Optimization is co-NQP-hard Kjelstrøm, Adam Husted Pavlogiannis, Andreas van de Pol, Jaco Quantum Physics Computational Complexity As quantum computing resources remain scarce and error rates high, minimizing the resource consumption of quantum circuits is essential for achieving practical quantum advantage. Here we consider the natural problem of, given a circuit $C$, computing a circuit $C'$ which behaves equivalently on a desired subspace, and that minimizes a quantum resource type, expressed as the count or depth of (i) arbitrary gates, or (ii) non-Clifford gates, or (iii) superposition gates, or (iv) entanglement gates. We show that, when $C$ is expressed over any gate set that can implement the H and TOF gates exactly, each of the above optimization problems is hard for $\text{co-NQP}$, and hence outside the Polynomial Hierarchy, unless the Polynomial Hierarchy collapses. This complements recent results in the literature which established an $\text{NP}$-hardness lower bound when equivalence is over the full state space, and tightens the gap to the corresponding $\text{NP}^{\text{NQP}}$ upper bound known for cases (i)-(iii) over Clifford+T and (i)-(iv) over H+TOF circuits. |
| title | Exact Quantum Circuit Optimization is co-NQP-hard |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2510.16420 |