**A Fast Deterministic Algorithm for Solving Quantum Games** - Gus Gutoski

A game can be modelled as an exchange of messages between two competing
players and a referee, after which the referee chooses a winner. In a
quantum game the players and referee may perform quantum computations and
exchange quantum messages. In this talk we examine the problem of deciding,
given a fixed quantum referee, which of the two players has a winning
quantum strategy. We give a deterministic algorithm that decides quantum
games in time exponential in the number of qubits exchanged throughout the
game between the referee and players.
Our algorithm subsumes previously known algorithms for solving classical
games. Moreover, it implies that the quantum games model of computation is
no more powerful than its classical counterpart. In terms of complexity
classes, we have QRG = RG = EXP, offering a rare quantum characterization of
a classical complexity class.