On the Complexity of the Succinct State Local Hamiltonian Problem
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_ | 1866909005599735808 |
|---|---|
| author | Waite, Gabriel Lin, Karl |
| author_facet | Waite, Gabriel Lin, Karl |
| contents | We study the computational complexity of the Local Hamiltonian problem under the promise that its ground state is succinctly represented. We show that the Succinct State 2-Local Hamiltonian problem, for qubit Hamiltonians, is (promise) MA-complete. The approach combines a systematic characterisation of succinct quantum states, defined through arithmetic over specific number fields, with a refined reduction that lowers the locality of Feynman-Kitaev circuit-Hamiltonians from 6 to 2, without increasing particle dimension. This reveals a complexity phase transition, parameterised by locality, and extends the scope of previously known MA-complete problem instances. Our results further clarify how succinctness behaves under circuit-based constructions, and progresses toward a better understanding of the boundary between efficiently describable and efficiently verifiable quantum systems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_25821 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Complexity of the Succinct State Local Hamiltonian Problem Waite, Gabriel Lin, Karl Quantum Physics Computational Complexity We study the computational complexity of the Local Hamiltonian problem under the promise that its ground state is succinctly represented. We show that the Succinct State 2-Local Hamiltonian problem, for qubit Hamiltonians, is (promise) MA-complete. The approach combines a systematic characterisation of succinct quantum states, defined through arithmetic over specific number fields, with a refined reduction that lowers the locality of Feynman-Kitaev circuit-Hamiltonians from 6 to 2, without increasing particle dimension. This reveals a complexity phase transition, parameterised by locality, and extends the scope of previously known MA-complete problem instances. Our results further clarify how succinctness behaves under circuit-based constructions, and progresses toward a better understanding of the boundary between efficiently describable and efficiently verifiable quantum systems. |
| title | On the Complexity of the Succinct State Local Hamiltonian Problem |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2509.25821 |