Abstract

The quantum de Finetti theorem states that subsystems of symmetric quantum states are close to mixtures of i.i.d. states. Depending on exactly how “close” is quantified, this theorem can have many applications to quantum information theory, quantum complexity theory, and even classical optimization algorithms. However, previous bounds scaled badly with either dimension or the number of systems. I’ll give an overview of why de Finetti theorems are useful, describe a way to use information theory to improve existing bounds, and discuss applications and open problems. One application of particular interest is finding k-body Hamiltonians whose ground-state energy can be approximately achieved by product states. This can be used to show that the problem of estimating the ground-state energy of a k-body Hamiltonian is in some cases contained in NP (thus providing evidence against the quantum PCP conjecture) and in other cases contained in P.

Based on joint work with Fernando Brandao, some unpublished, and some in 1210.6367.