A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians

Playing this video requires the latest flash player from Adobe.

Download link (right click and 'save-as') for playing in VLC or other compatible player.

Recording Details

PIRSA Number: 


Computing ground
states of local Hamiltonians is a fundamental problem in condensed matter
physics. We give the first randomized polynomial-time algorithm for finding
ground states of gapped one-dimensional Hamiltonians: it outputs an
(inverse-polynomial) approximation, expressed as a matrix product state (MPS)
of polynomial bond dimension. The algorithm combines many ingredients,
including recently discovered structural features of gapped 1D systems, convex
programming, insights from classical algorithms for 1D satisfiability, and new
techniques for manipulating and bounding the complexity of MPS. Our result
provides one of the first major classes of Hamiltonians for which computing
ground states is provably tractable despite the exponential nature of the
objects involved.