The rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete
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_ | 1866914014285529088 |
|---|---|
| author | Nelson, Jon Gottesman, Daniel |
| author_facet | Nelson, Jon Gottesman, Daniel |
| contents | In this work, we study a variant of the local Hamiltonian problem where we restrict to Hamiltonians that live on a lattice and are invariant under translations and rotations of the lattice. In the one-dimensional case this problem is known to be QMA$_{\rm EXP}$-complete. On the other hand, if we fix the lattice length then in the high-dimensional limit the ground state becomes unentangled due to arguments from mean-field theory. We take steps towards understanding this complexity spectrum by studying a problem that is intermediate between these two extremes. Namely, we consider the regime where the lattice dimension is arbitrary but fixed and the lattice length is scaled. We prove that this rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete answering an open question of [Gottesman, Irani 2013]. This characterizes a broad parameter range in which these rotation-invariant Hamiltonians have high computational complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_00161 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete Nelson, Jon Gottesman, Daniel Quantum Physics Computational Complexity In this work, we study a variant of the local Hamiltonian problem where we restrict to Hamiltonians that live on a lattice and are invariant under translations and rotations of the lattice. In the one-dimensional case this problem is known to be QMA$_{\rm EXP}$-complete. On the other hand, if we fix the lattice length then in the high-dimensional limit the ground state becomes unentangled due to arguments from mean-field theory. We take steps towards understanding this complexity spectrum by studying a problem that is intermediate between these two extremes. Namely, we consider the regime where the lattice dimension is arbitrary but fixed and the lattice length is scaled. We prove that this rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete answering an open question of [Gottesman, Irani 2013]. This characterizes a broad parameter range in which these rotation-invariant Hamiltonians have high computational complexity. |
| title | The rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2509.00161 |