[quantum-info] Fwd: Today's Lunch Colloquium: Gus Gutoski 12:30 in room 2009 of RAC1

[William Matthews]

Hello - a quick message to let you know about the lunch colloquium today at IQC,
which may be of interest. Apologies for the lack of updates of late - normal service
will be resumed this week.
Will

Begin forwarded message:
> 
> Gus Gutoski, IQC
> Short quantum games characterize PSPACE
> 
> 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.
> 
> Today: Monday Jan 17, RAC1 2009, 12:30pm to 1:30pm