Gus Gutoski, Institute for Quantum Computing
Abstract
I will present material from http://arxiv.org/abs/1011.2787. The abstract at that link is included below. Essentially, the result is a strengthening of the QIP=PSPACE result of Jain, Ji, Upadhyay, and Watrous from 2009. A goal of this talk is to clarify the statement and meaning of the multiplicative weights update method and illustrate how it can be used to prove space bounds in quantum complexity theory.
Abstract from 1011.2787:
This paper studies short quantum games, which are zero-sum games played by two competing quantum players in which each player answers a question from a referee, who then declares payoffs to the players. In
the games we consider the referee may process one player's answer before preparing the other player's question. We prove that optimal strategies for short quantum games can be found by an efficient parallel algorithm based on the matrix multiplicative weights update method. If the referee is specified succinctly by quantum circuits then our algorithm can be used to find optimal strategies in polynomial space. This algorithm is optimal in that it is already known to be PSPACE-hard to approximate the value of a game, even for the special case of classical games with simultaneous questions. It follows from our work that the two competing-provers complexity classes SQG and QRG(2) induced by short quantum games with sequential and simultaneous questions, respectively, are both equal to PSPACE.