A Note on the Complexity of the Spectral Gap Problem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910858644291584 |
|---|---|
| author | Yirka, Justin |
| author_facet | Yirka, Justin |
| contents | The problem of estimating the spectral gap of a local Hamiltonian is known to be contained in the class $P^{QMA[log]}$: polynomial time with access to a logarithmic number of QMA queries. The problem was shown to be hard for $P^{UQMA[log]}$, a weaker class, under Turing reductions by Gharibian and Yirka [arXiv:1606.05626].
I give a brief proof that the Spectral Gap problem is QMA-hard under a many-one (Karp) reduction. Consequently, the problem is $P^{QMA[log]}$-complete under truth-table reductions.
It remains open to characterize the complexity of the Spectral Gap problem under many-one reductions. I conjecture that the problem belongs to a strict subclass of $P^{QMA[log]}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_02747 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Note on the Complexity of the Spectral Gap Problem Yirka, Justin Quantum Physics Computational Complexity The problem of estimating the spectral gap of a local Hamiltonian is known to be contained in the class $P^{QMA[log]}$: polynomial time with access to a logarithmic number of QMA queries. The problem was shown to be hard for $P^{UQMA[log]}$, a weaker class, under Turing reductions by Gharibian and Yirka [arXiv:1606.05626]. I give a brief proof that the Spectral Gap problem is QMA-hard under a many-one (Karp) reduction. Consequently, the problem is $P^{QMA[log]}$-complete under truth-table reductions. It remains open to characterize the complexity of the Spectral Gap problem under many-one reductions. I conjecture that the problem belongs to a strict subclass of $P^{QMA[log]}$. |
| title | A Note on the Complexity of the Spectral Gap Problem |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2503.02747 |