[quantum-info] PIQuDos seminar on Wed May 14: Thomas Vidick

[Gus Gutoski]

Please join us on Wednesday, May 14 at 4pm in the Time room for a quantum
information seminar by Thomas Vidick.

Title:  *A polynomial-time algorithm for the ground state of 1D gapped
local Hamiltonians*
Speaker: *Thomas Vidick* (UC Berkeley)

Abstract: 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.

Date: Wednesday, May 14, 2014.
Time: 16:00
Location: Time Room (294)

-Gus
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.uwaterloo.ca/pipermail/quantum-info/attachments/20140507/d0d4e6a9/attachment.html>