Matt Hastings

One of the basic problems in physics is approximating the ground state energy of a quantum many-body system. For arbitrary choice of local interactions, this problem is extremely difficult, even in one dimension where Aharonov, Gottesman, and Kempe and Irani showed that this problem is QMA-complete. However, many of the quantum ground states encountered in practice have a limited amount of entanglement. As I will explain, this makes it possible to efficiently represent the ground state of these systems on a classical computer. In the important case that the Hamiltonian has a spectral gap, I will explain a recent proof of an "area law" which bounds the entanglement entropy. This result implies that a certain promise problem for approximating the ground state energy of gapped one-dimensional Hamiltonians is in NP, while a similar problem for approximating the adiabatic evolution of such systems is in P.

One of the basic problems in physics is approximating the ground state energy of a quantum many-body system. For arbitrary choice of local interactions, this problem is extremely difficult, even in one dimension where Aharonov, Gottesman, and Kempe and Irani showed that this problem is QMA-complete. However, many of the quantum ground states encountered in practice have a limited amount of entanglement. As I will explain, this makes it possible to efficiently represent the ground state of these systems on a classical computer. In the important case that the Hamiltonian has a spectral gap, I will explain a recent proof of an "area law" which bounds the entanglement entropy. This result implies that a certain promise problem for approximating the ground state energy of gapped one-dimensional Hamiltonians is in NP, while a similar problem for approximating the adiabatic evolution of such systems is in P. There are four different additivity conjectures in quantum information theory, all of which were shown to be equivalent by Shor in 2004. These include the additivity of the Holevo capacity for sending classical information over a quantum channel, and the additivity of the minimum output entropy of a quantum channel. These conjectures relate to whether or not entanglement between different inputs to a quantum channel is useful to increase classical capacity or reduce output entropy. I will present a counter-example to the minimum output entropy conjecture, which implies that all of these additivity conjectures are false. The counter-example is based on a random construction of a channel with a large environment dimension and an even larger system dimension. I will relate this channel to recent work on quantum expanders, and I will propose a slightly weaker additivity conjecture which would give us a two-letter formula for capacity of channels invariant under complex conjugation.