The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



The computational complexity of entanglement detection

Hayden, P (Stanford University)
Thursday 12 December 2013, 16:00-17:00

Seminar Room 1, Newton Institute


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.

Back to top ∧