An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911694030110720 |
|---|---|
| author | Mataraarachchi, Ranitha Gall, François Le Tamaki, Suguru |
| author_facet | Mataraarachchi, Ranitha Gall, François Le Tamaki, Suguru |
| contents | Low-energy estimation and state preparation for general $k$-local Hamiltonians are fundamental challenges in quantum complexity theory. For constant relative accuracy, Buhrman et al. (PRL 2025) recently broke the natural Grover bound $O(2^{n/2})$, where $n$ denotes the number of qubits, for both problems. In this paper, for any sufficiently small parameter $d\ge 0$, we present an even faster quantum algorithm that outputs a quantum state with energy bounded by the minimum energy over all depth-$d$ states (i.e., states obtained by applying a depth-$d$ circuit to the all-zero state), together with an estimate of this energy. For the class of Hamiltonians with depth-$d$ ground states, our algorithm furthermore achieves exactly the same energy guarantees as Buhrman et al. Our results also provide insight into the distinction between strongly entangled states and those admitting efficient classical descriptions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_18241 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians Mataraarachchi, Ranitha Gall, François Le Tamaki, Suguru Quantum Physics Computational Complexity Data Structures and Algorithms Low-energy estimation and state preparation for general $k$-local Hamiltonians are fundamental challenges in quantum complexity theory. For constant relative accuracy, Buhrman et al. (PRL 2025) recently broke the natural Grover bound $O(2^{n/2})$, where $n$ denotes the number of qubits, for both problems. In this paper, for any sufficiently small parameter $d\ge 0$, we present an even faster quantum algorithm that outputs a quantum state with energy bounded by the minimum energy over all depth-$d$ states (i.e., states obtained by applying a depth-$d$ circuit to the all-zero state), together with an estimate of this energy. For the class of Hamiltonians with depth-$d$ ground states, our algorithm furthermore achieves exactly the same energy guarantees as Buhrman et al. Our results also provide insight into the distinction between strongly entangled states and those admitting efficient classical descriptions. |
| title | An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians |
| topic | Quantum Physics Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.18241 |