University of Cambridge > > CQIF Seminar > New de Finetti theorems and the quantum PCP conjecture

New de Finetti theorems and the quantum PCP conjecture

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Ashley Montanaro.

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.

This talk is part of the CQIF Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2021, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity