  In a nonlocal game, two noncommunicating players cooperate to convince a
referee that they possess a strategy that does not violate the rules of the
game. Quantum strategies allow players to optimally win some games by
performing joint measurements on a shared entangled state, but computing these
strategies can be challenging. We develop a variational algorithm for computing
strategies of nonlocal games and show that it can yield optimal strategies for
small examples of both convex and non-convex games. We show that our algorithm
is capable of generating a short-depth circuit that implements an optimal
quantum strategy for a graph coloring game. Moreover, we describe how this
technique can be run on quantum computers and argue that such circuits will be
useful for benchmarking because of their sensitivity to 2-qubit gate noise and
application to self-testing. Finally, we demonstrate the use of these
strategies experimentally on 11 IBM quantum computers.
