New de Finetti theorems and the quantum PCP conjecture

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

• Aram Harrow (MIT)
• Tuesday 26 March 2013, 14:00-15:00
• MR14, Centre for Mathematical Sciences.

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.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR14, Centre for Mathematical Sciences
• bld31

Note that ex-directory lists are not shown.