Improved Tools for Local Hamiltonians
In this thesis we consider computational problems related to many-body spin systems with a structured energy operator, a local Hamiltonian. We begin with the most structured setting where the Hamiltonian has a spectral gap and spatial locality. This setting is widely studied using approximate gr...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/139241 |
| _version_ | 1826215523635953664 |
|---|---|
| author | Abrahamsen, Nilin |
| author2 | Shor, Peter W. |
| author_facet | Shor, Peter W. Abrahamsen, Nilin |
| author_sort | Abrahamsen, Nilin |
| collection | MIT |
| description | In this thesis we consider computational problems related to many-body spin systems with a structured energy operator, a local Hamiltonian.
We begin with the most structured setting where the Hamiltonian has a spectral gap and spatial locality. This setting is widely studied using approximate ground space projectors (AGSPs). In chapter 1 we give an improved analysis of AGSPs in the setting of local Hamiltonians with a degenerate ground space. This implies a direct generalization of the AGSP⇒entanglement bound implication of [Arad, Landau, and Vazirani ’12] from unique to degenerate ground states. We use the improved analysis to give a particularly simple algorithm for frustration-free spin systems provided an AGSP with structure as a matrix product operator. We apply our tools to a recent 2D area law of [Anshu, Arad, and Gosset ’21], giving a sub-exponential-time classical algorithm to compute the ground states. This time complexity cannot be improved beyond sub-exponential assuming the randomized exponential time hypothesis, even for the special case of classical constraint satisfaction problems on the 2D grid. In chapter 2 we consider frustrated systems and extend results for spin chains to certain trees with intrinsic dimension β < 2. This condition is met for generic trees in the plane and for certain models of hyperbranched polymers in 3D.
In chapter 3 we relax the conditions on the Hamiltonian and no longer require a spectral gap or geometric locality, and we consider an approximation problem for the spectrum of the local Hamiltonian. We give a simple proof of a Chernoff bound for the spectrum of a k-local Hamiltonian based on Weyl’s inequalities. The complexity of estimating the spectrum’s ϵ(n)-th quantile up to constant relative error thus exhibits the following dichotomy: For ϵ(n) = d −n the problem is NP-hard and maybe even QMA-hard, yet there exists constant a > 1 such that the problem is trivial for ϵ(n) = a −n. |
| first_indexed | 2024-09-23T16:33:12Z |
| format | Thesis |
| id | mit-1721.1/139241 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:33:12Z |
| publishDate | 2022 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1392412022-01-15T03:03:46Z Improved Tools for Local Hamiltonians Abrahamsen, Nilin Shor, Peter W. Massachusetts Institute of Technology. Department of Mathematics In this thesis we consider computational problems related to many-body spin systems with a structured energy operator, a local Hamiltonian. We begin with the most structured setting where the Hamiltonian has a spectral gap and spatial locality. This setting is widely studied using approximate ground space projectors (AGSPs). In chapter 1 we give an improved analysis of AGSPs in the setting of local Hamiltonians with a degenerate ground space. This implies a direct generalization of the AGSP⇒entanglement bound implication of [Arad, Landau, and Vazirani ’12] from unique to degenerate ground states. We use the improved analysis to give a particularly simple algorithm for frustration-free spin systems provided an AGSP with structure as a matrix product operator. We apply our tools to a recent 2D area law of [Anshu, Arad, and Gosset ’21], giving a sub-exponential-time classical algorithm to compute the ground states. This time complexity cannot be improved beyond sub-exponential assuming the randomized exponential time hypothesis, even for the special case of classical constraint satisfaction problems on the 2D grid. In chapter 2 we consider frustrated systems and extend results for spin chains to certain trees with intrinsic dimension β < 2. This condition is met for generic trees in the plane and for certain models of hyperbranched polymers in 3D. In chapter 3 we relax the conditions on the Hamiltonian and no longer require a spectral gap or geometric locality, and we consider an approximation problem for the spectrum of the local Hamiltonian. We give a simple proof of a Chernoff bound for the spectrum of a k-local Hamiltonian based on Weyl’s inequalities. The complexity of estimating the spectrum’s ϵ(n)-th quantile up to constant relative error thus exhibits the following dichotomy: For ϵ(n) = d −n the problem is NP-hard and maybe even QMA-hard, yet there exists constant a > 1 such that the problem is trivial for ϵ(n) = a −n. Ph.D. 2022-01-14T14:58:51Z 2022-01-14T14:58:51Z 2021-06 2021-05-25T12:46:31.101Z Thesis https://hdl.handle.net/1721.1/139241 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Abrahamsen, Nilin Improved Tools for Local Hamiltonians |
| title | Improved Tools for Local Hamiltonians |
| title_full | Improved Tools for Local Hamiltonians |
| title_fullStr | Improved Tools for Local Hamiltonians |
| title_full_unstemmed | Improved Tools for Local Hamiltonians |
| title_short | Improved Tools for Local Hamiltonians |
| title_sort | improved tools for local hamiltonians |
| url | https://hdl.handle.net/1721.1/139241 |
| work_keys_str_mv | AT abrahamsennilin improvedtoolsforlocalhamiltonians |