Gus Gutoski, Institute for Quantum Computing
Abstract:
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.