[quantum-info] IQC Colloquium Mon 16 Sept

[Matthew Fries]

Colloquium

Institute for Quantum Computing

Monday, 16 September 2013 at 2:30PM

QNC 0101

Quantum interactive proofs and the complexity of entanglement detection

Gus Gutoski

The Perimeter Institute

We identify a formal connection between physical problems related to entanglement detection and complexity classes in theoretical computer science. In particular, we show that to nearly every quantum interactive proof complexity class (including BQP, QMA, QMA(2), QSZK, and QIP), there corresponds a natural entanglement or correlation detection problem that is complete for that class. In this sense, we can say that an entanglement or correlation detection problem captures the expressive power of each quantum interactive proof complexity class. We also show that the difficulty of entanglement detection depends on whether the distance measure used is the trace distance or the one-way LOCC distance.