ON-LINE QLunch: Nilin Abrahamsen

Speaker: Nilin Abrahamsen from MIT

Title: Improved AGSP tools and sub-exponential algorithm for 2D frustration-free uniformly gapped spin systems

Abstract: We give an improved analysis of approximate ground space projectors 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 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 subvolume law of [Anshu, Arad, and Gosset ’20], generalizing the result to subexponentially degenerate ground spaces and 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.