Abstract

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 , QSZK and QIP . Moreover, entanglement detection provides a natural candidate for the first nontrivial complete problem for QIP . 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.