UC Berkeley

Quantum entanglement, and the resulting peculiar non-classical correlations are one of the most counter-intuitive aspects of quantum mechanics.

The formalism of interactive games from computational complexity theory provides a useful framework in which to understand the power of entanglement. In an interactive game, a verifier interacts with a number of infinitely powerful provers who are allowed to share quantum entanglement but otherwise can't communicate. The ability of the verifier to extract useful information from the provers, whom he does not trust, provides an interesting measure of the ability of the provers to coordinate using their shared entanglement. Two particular interactive games we'll look at are Magic Square and 3SAT.

The Magic Square game is the iconic example of a game where two classical provers cannot perfectly coordinate their strategies using shared randomness, but quantum provers with shared entanglement can win with probability 1. We show that by adding an extra prover, we disallow perfect cheating. For 3SAT with three provers we also show that perfect cheating is not possible.

We then generalize the results for Magic Square and 3SAT by looking at non-commuting provers, a superset of entangled provers (communication is allowed, but operators applied by different provers must commute). Using this method, we obtain a generalized Tsirelson inequality that we apply to the Magic Square. Hence, we are able to give provably optimal strategies for the general Magic Square with n players. We also recover a similar result for 3SAT as with entangled provers, and we improve on it by showing that the gap is inverse exponential in the input size.

The no-signaling principle, which forbids faster than light communication, is a fundamental constraint on the non-local correlations resulting from quantum entanglement. However, no-signaling allows distributions that are more general than those arising from quantum mechanics. In particular, using a specific "unit" of general non-local correlation (the Popescu-Rohlich box), we show that there are classes that are equal to NEXP classically, but collapse to AM once such correlations are allowed. We also show that MIP where the verifier only looks at the XOR of the answers collapses to PSPACE. For the second approach, we show that by writing general non-local correlations as linear constraints, MIP is included in EXP under such correlations (vs NEXP classically).

We can extend these results to entangled quantum provers, by formulating an artificial MIP-like class built on a promise problem, that classically is equal to NEXP, but that also collapses to AM when quantum correlations are present.