Dear quanta,
Vazirani is speaking this Friday in the Harvard/MIT/MSR CS theory reading
group; details below.
-aram
---------- Forwarded message ---------
From: Madhu Sudan <madhusudan(a)g.harvard.edu>
Date: Mon, Sep 18, 2017 at 1:26 PM
Subject: [Theory-reading-group] Reading Group this Friday with Umesh
Vazirani
To: <theory-reading-group(a)csail.mit.edu>
All
Our speaker this Friday will be Umesh Vazirani who'll walk us through a
1-dimensional quantum system and show us how to compute its ground state in
polynomial time. For the deterministic/probabablistic analog of this
problem, a simple dynamic program would solve the 1-d problem, but for
quantum systems many technical barriers need to be overcome; and Umesh will
explain the math behind this!
As usual talk will be from 1:15-4:15, pizza at 1, break around 2:30. Talk
is in 20 Garden Street
<https://maps.google.com/?q=20+Garden+Street&entry=gmail&source=g> (in
Cambridge obviously!): After you enter the building take the stairwell one
floor down to the ground level and use your nose to find the pizza!
Madhu
*Friday, September 22, 2017 at 20 Garden Street: Speaker: Umesh Vazirani
<https://people.eecs.berkeley.edu/%7Evazirani/> (Berkeley) * Topic: Rigorous
RG algorithms for simulating 1D quantum systems.
Computing low energy states of quantum many body systems is a central
challenge in condensed matter physics. From a computational complexity
viewpoint these are 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. A priori it is
not even clear whether such eigenstates 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 an efficient classical algorithm for computing them.
The algorithm provides a new perspective on the well known Renormalization
Group (RG) formalism within condensed matter physics.
Over the last quarter century the famous Density Matrix Renormalization
Group (DMRG) algorithm has been widely used as a numerical heuristic for
identifying ground and low energy states of 1D quantum systems. A recent
implementation of our algorithm shows promise for outperforming DMRG in
hard cases with high ground space degeneracy or near criticality.
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://theory.csail.mit.edu/reading-group
_______________________________________________
qip mailing list
qip(a)mit.edu
http://mailman.mit.edu/mailman/listinfo/qip