IQIM Postdoctoral and Graduate Student Seminar

Entangled games have had important applications to quantum complexity theory, quantum cryptography, and the foundations of quantum mechanics. Given a game, the basic computational problem is to compute its entangled value: the supremum success probability attainable by players sharing any entangled state, of arbitrary dimension. We study the complexity of computing the (commuting-operator) entangled value of entangled XOR games with any number of players. Our main result is an algorithm for symmetric games that decides in polynomial time whether the entangled value is equal to 1 or strictly less than 1, a task that was not previously known to be decidable by a Turing machine, together with a simple tensor-product strategy that achieves value 1 in the former case. Our algorithm is based on a "duality theory" for systems of operator equations, and can be viewed as a non-commutative generalization of Gaussian elimination. Our techniques yield several additional results including a proof of the existence of an unsatisfiable phase for random 3XOR games.

Joint work with Adam Bene Watts, Aram Harrow, and Gurtej Kanwar (MIT).