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 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.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Mathematics

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2021

Author dc:creator

• Abrahamsen, Nilin

Advisor dc:contributor.advisor

• Shor, Peter W.

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/139241

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/139241