[iasmath-semru] Theoretical Computer Science/Discrete Math Seminars -- Week of September 18, 2017

[Anthony Pulido]

INSTITUTE FOR ADVANCED STUDY
School of Mathematics
Princeton, NJ 08540

Theoretical Computer Science/Discrete Math Seminars
Week of September 18, 2017


Monday, September 18

Computer Science/Discrete Mathematics Seminar I
Topic: 		Rigorous RG: a provably efficient and possibly practical algorithm for simulating 1D quantum systems
Speaker: 	Umesh Vazirani, University of California, Berkeley
Time/Room: 	11:00am - 12:15pm/S-101
Abstract Link:	http://www.math.ias.edu/seminars/abstract?event=132408

Rigorous RG: a provably efficient and possibly practical algorithm for 
simulating 1D quantum systems
    Umesh Vazirani

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.

http://www.math.ias.edu/seminars/abstract?event=132408

Computer Science/Discrete Math Seminars can be found on our web page:

http://www.math.ias.edu/csdm
http://www.math.ias.edu