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

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.

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.

Collection/Series:

Event Type:

Seminar

Speaker(s):

Event Date:

Wednesday, May 14, 2014 - 16:00 to 17:30

Location:

Time Room

Room #:

294

©2012 Perimeter Institute for Theoretical Physics