[QIP-Sem] QIP seminar, Mon 4/5, 4:30, 36-462, Irani,Sandy

[Peter Shor]

MIT Quantum Information Processing seminar
Monday 4/5 at 4:30 in 36-462
-------------------------------------------------

 Irani,Sandy (University of California, Irvine)

 Matrix Product States and Computational Complexity in 1D Quantum  Systems

Abstract:

DMRG has been an extremely successful method in practice for  computing ground energies in 1D quantum systems. In recent years,  DMRG has been recast as a method which heuristically minimizes  energy over the set of states which can be represented as Matrix  Product States. This suggests that there is a correspondence between  efficiently computable ground states and Matrix Product States - but  is there a provable connection? In this talk, we describe an  algorithm which finds an approximation of the lowest energy MPS for  a 1D quantum system. The algorithm runs in time that is polynomial  in the number of particles and the approximation error, but  exponential in D, the bond dimension of the Matrix Product State. It  implies a pseudo-polynomial algorithm for systems whose ground state  can be approximated by an MPS with logarithmic bond dimension. The  algorithm uses dynamic programming to find a state with low energy,  similar to the way that dynamic programming is used to
  solve a  classical constraint satisfaction problem on a line. This dynamic  programming approach can also be used to find ground states for 1D  commuting Hamiltonians.

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem