Abstract
I will describe joint work with Zeph Landau and Umesh Vazirani (arXiv:1307.5143) in which we give a provably polynomial-time classical randomized algorithm for finding ground states of gapped local Hamiltonians in 1D. The algorithm is based on several ingredients, including the notions of boundary contraction and decoupling for matrix product states and a construction of approximate ground state projection (AGSP) based on random sampling. I will give a self-contained presentation of the algorithm that emphasizes these tools and their potential usefulness in the study of matrix product state representations.