Caltech Logo

IQIM Postdoctoral and Graduate Student Seminar

Friday, March 15, 2019
12:00pm to 1:00pm
Add to Cal
East Bridge 114
Algorithms and Lower Bounds for Entangled XOR Games
Anand Natarajan, IQIM Postdoctoral Scholar, Vidick Group,

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).

For more information, please contact Marcia Brown by phone at 626-395-4013 or by email at