Computer Science/Discrete Mathematics Seminar I

One of the great challenges posed by the laws of quantum mechanics is that the number of parameters required to describe a quantum state 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. How is physics possible if it is exponentially hard to even describe the quantum state of a system? It turns out that quantum states of interest in condensed matter physics have additional structure - they are ground states (and low energy states) of local Hamiltonians. Or in complexity theory language, they are solutions to the quantum analog of constraint satisfaction problems (CSPs). A sweeping conjecture, called the area law, asserts that ground states of gapped local Hamiltonians have limited entanglement. A deeper understanding of area laws therefore holds the key to succinct classical description of such quantum states. 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. The talk will be pitched at 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.