Seminar, Nilin Abrahamsen (MIT), Classical Algorithm for Ground States of Spin Trees

Date: 

Thursday, February 27, 2020, 11:00am

Location: 

Lyman 338

Title: Classical Algorithm for Ground States of Spin Trees

Abstract: We prove that the ground states of a local Hamiltonian satisfy an area law and can be computed in polynomial time when the interaction graph is a tree with discrete fractal dimension less than 2. This condition is met for generic trees in the plane and for established models of hyperbranched polymers in 3D. This work is the first to prove an area law and exhibit a provably polynomial-time classical algorithm for local Hamiltonian ground states beyond the case of spin chains. Our results hold for polynomially degenerate and frustrated ground states, matching the state of the art for local Hamiltonians on a line.