This paper presents an efficient parallel algorithm for a new class of min-max problems based on the matrix multiplicative weights update method. Our algorithm can be used to find near-optimal strategies for competitive two-player classical or quantum games in which a referee exchanges any number of messages with one player followed by any number of additional messages with the other. This algorithm considerably extends the class of games which admit parallel solutions, demonstrating for the first time the existence of a parallel algorithm for a game in which one player reacts adaptively to the other. As a consequence, we prove that several competing-provers complexity classes collapse to PSPACE such as QRG(2), SQG and two new classes called DIP and DQIP. A special case of our result is a parallel approximation scheme for a new class of semi definite programs whose feasible region consists of lists of semi definite matrices that satisfy a ``transcript-like'' consistency condition. Applied to this special case, our algorithm yields a direct polynomial-space simulation of multi-message quantum interactive proofs resulting in a first-principles proof of QIP=PSPACE.

We study properties of quantum strategies, which are complete specifications of a given party's actions in any multiple-round interaction involving the exchange of quantum information with one or more other parties. In particular, we focus on a representation of quantum strategies that generalizes the Choi-Jamio{\l}kowski representation of quantum operations. This new representation associates with each strategy a positive semidefinite operator acting only on the tensor product of its input and output spaces. Various facts about such representations are established, and two applications are discussed: the first is a new and conceptually simple proof of Kitaev's lower bound for strong coin-flipping, and the second is a proof of the exact characterization QRG = EXP of the class of problems having quantum refereed games.

Refereed games are interactive proof systems with two competing provers: one that tries to convince the verifier to accept and another that tries to convince the verifier to reject. In quantum refereed games, the provers and verifier may perform quantum computations and exchange quantum messages. One may consider games with a bounded or unbounded number of rounds of messages between the verifier and provers. In this paper, we prove classical upper bounds on the power of both one-round and many-round quantum refereed games. In particular, we use semidefinite programming to show that many-round quantum refereed games are contained in NEXP. It then follows from the symmetric nature of these games that they are also contained in coNEXP. We also show that one-round quantum refereed games are contained in EXP by supplying a separation oracle for use with the ellipsoid method for convex feasibility.