See below for another talk by Vazirani, partly similar to the one he gave in our quantum info seminar, plus part on some work that I'm involved in. ---------- Forwarded message ---------- From: Madhu Sudan &lt;madhu(a)mit.edu&gt; Date: Wed, Jul 16, 2014 at 10:48 PM Subject: [Theory-reading-group] Fwd: [Toc-faculty] (2nd) Seminar at MSR: Umesh Vazirani on Area Laws and the complexity of quantum states To: theory-reading-group(a)csail.mit.edu Another talk by Umesh Vazirani next week. Madhu -------- Original Message -------- Subject: [Toc-faculty] (2nd) Seminar at MSR: Umesh Vazirani on Area Laws and the complexity of quantum states Date: Wed, 16 Jul 2014 17:48:10 -0400 From: Madhu Sudan &lt;madhu(a)MIT.EDU&gt; &lt;madhu(a)MIT.EDU&gt; To: toc-faculty &lt;toc-faculty(a)csail.mit.edu&gt; &lt;toc-faculty(a)csail.mit.edu&gt;du>, toc-students(a)csail.mit.edu, toc-visitors(a)csail.mit.edu Hi All Below is are the details of the second talk by Umesh Vazirani. This talk is aimed as a TCS audience. Madhu -------------------------------------------------------------------- Area Laws and the complexity of quantum states Umesh Vazirani (Berkeley) Thursday, July 24, 2014 from 3pm-4:30pm, Microsoft Research (Barton Room, 1st floor), One Memorial Drive. One of the great challenges posed by the laws of quantum mechanics is that the complexity of quantum states in general grows exponentially in the number of particles. This complexity is directly related to the phenomenon of quantum entanglement, the quantum analog of correlations. Finding an effective and succinct description for a quantum state may be compared to the analogous problem in machine learning of finding succinct and effective descriptions for probability distributions. Are there large classes of quantum states that do not suffer from exponential complexity? A sweeping conjecture, called the area law, asserts that states of special interest in condensed matter physics, ground states of gapped local Hamiltonians have limited entanglement. One might even very roughly say that this is what makes it possible to do quantum many body physics. Whereas the area law is rigorously proved for a one dimensional chain of particles, establishing it for two and three dimensional systems remains a central open question in quantum Hamiltonian complexity. At the other end of the spectrum is the generalized area law, where the interaction graph of the local Hamiltonian can be arbitrary - the generalized area law asserts that the entanglement entropy for a subset of vertices scales as its edge cut-set (the area) rather than the cardinality of the subset (volume). I will outline a recently discovered counter-example to the generalized area law. The construction is based on quantum expanders, and has a beautiful alternate description in terms of a very efficient communication complexity protocol. It is insightful to view the construction in the context of the proof of the area law in one dimension, which I will briefly sketch, leading to a discussion of prospects for two dimensional systems. I will aim to make the talk accessible to a computer science audience. Based on joint work with Itai Arad, Alexei Kitaev and Zeph Landau, and with Dorit Aharonov, Aram Harrow, Zeph Landau, Daniel Nagaj and Mario Szegedy. _______________________________________________ Toc-faculty mailing listToc-faculty@lists.csail.mit.eduhttps://lists.csail.mit.edu/mailman/listinfo/toc-faculty _______________________________________________ Theory-reading-group mailing list -http://theory.csail.mit.edu/reading-group Theory-reading-group(a)lists.csail.mit.edu <http://theory.csail.mit.edu/reading-groupTheory-reading-group@lists.csail.mit.edu> Manage subscriptions at https://lists.csail.mit.edu/mailman/listinfo/theory-reading-group _______________________________________________ qip mailing list qip(a)mit.edu http://mailman.mit.edu/mailman/listinfo/qip