Parallel approximation of min-max problems with applications to classical and quantum zero-sum games

Details Parallel approximation of min-max problems with applications to classical and quantum zero-sum games Parallel approximation of min-max problems with applications to classical and quantum zero-sum games

2010-11-11

arxiv.org/abs/1011.2787v2

Physics

Quantum Physics

27 pages; New results and more comments on related work added

Scientific paper

This paper presents an efficient parallel algorithm for a new class of min-max problems based on the matrix multiplicative weight (MMW) 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 and demonstrates for the first time the existence of a parallel algorithm for \emph{any} game (classical or quantum) in which one player reacts adaptively to the other. A special case of our result is a parallel approximation scheme for a new class of semidefinite programs whose feasible region consists of $n$-tuples of semidefinite matrices that satisfy a certain 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 $\cls{QIP}=\cls{PSPACE}$. It is noteworthy that our algorithm establishes a new way, called the \emph{min-max} approach, to solve SDPs in contrast to the \emph{primal-dual} approach to SDPs used in the original proof of $\cls{QIP}=\cls{PSPACE}$. It also follows from our work that several competing-provers complexity classes collapse to $\cls{PSPACE}$ such as $\cls{QRG}(2)$, $\cls{SQG}$ and two new classes called $\cls{DIP}$ and $\cls{DQIP}$.

Affiliated with

Also associated with

No associations

Rating

Parallel approximation of min-max problems with applications to classical and quantum zero-sum games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Parallel approximation of min-max problems with applications to classical and quantum zero-sum games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel approximation of min-max problems with applications to classical and quantum zero-sum games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-203184