Computer Science/Discrete Mathematics Seminar I

One of the great mysteries in computational condensed matter physics is the remarkable practical success of the Density Matrix Renormalization Group (DMRG) algorithm, since its invention a quarter century ago, for finding low energy states of 1D quantum systems (like the similarly successful simplex method for linear programming, DMRG takes exponential time in the worst case). From a computational complexity viewpoint, low energy states are simply near optimal solutions to (quantum) constraint satisfaction problems. Mathematically, the problem is specified by a succinctly described Hamiltonian - an exponentially large matrix, and the challenge is to find the eigenstates with small eigenvalues. Since the eigenstates live in an exponential dimensional space, it is a priori not even clear whether they can be succinctly described, let alone computed efficiently. In this talk I will describe novel combinatorial arguments showing that low energy states for systems of particles with nearest neighbor interactions in 1D can be described succinctly, leading to a provably efficient classical algorithm for computing them. A recent implementation of our algorithm shows promise for outperforming DMRG in hard cases with high ground space degeneracy or near criticality.One of the cornerstones in physics is the Renormalization Group (RG) formalism, which provides a sweeping approach towards managing complexity in the quantum world. Our algorithm may be viewed as a rigorously justified RG-like procedure, and provides a new perspective on the subject.The talk will be aimed at a broad audience of computer scientists and physicists, and I will not assume a background in quantum computing.Based on joint work with Itai Arad, Zeph Landau and Thomas Vidick.