Southwest Quantum Information and Technology

Area Laws and the complexity of quantum states

Umesh Vazirani, U.C. Berkeley

view abstract +

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. 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. 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. 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.