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.