skip to content
 

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

Presented by: 
T Vidick Massachusetts Institute of Technology
Date: 
Wednesday 27th November 2013 - 15:00 to 16:00
Venue: 
INI Seminar Room 1
Abstract: 
Co-authors: Zeph Landau (UC Berkeley), Umesh Vazirani (UC Berkeley)

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.

Joint work with Zeph Landau and Umesh Vazirani.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons