skip to content

The computational complexity of entanglement detection

Presented by: 
P Hayden Stanford University
Thursday 12th December 2013 - 16:00 to 17:00
INI Seminar Room 1
In quantum information, theorists and experimentalists alike are often acutely concerned with whether a given physical system is entangled or not. Recently, string theorists have acquired a similar morbid fascination because of catastrophic violations of monogamy of entanglement that seem to be caused by black holes. In this talk, I will explain how various formulations of the entanglement detection problem provide natural complete problems for a host of complexity classes including NP, BQP, QMA, QMA(2), QSZK and QIP. Moreover, entanglement detection provides a natural candidate for the first nontrivial complete problem for QIP(2). In some cases, the complexity depends subtly on the distance measure used, specifically the trace distance versus the 1-way LOCC distance. To conclude, I'll sketch how the difficulty of performing entanglement detection may help string theorists to sleep better at night. The talk will be based on joint work with Gus Gutoski, Daniel Harlow, Kevin Milner and Mark Wilde in the articles 1308.5788, 1301.4504 and 1211.6120.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons