2006/11/30 by Gus Gutoski, John Watrous · 1 citation
Physics and Astronomy · Computer Science · #quant-ph #cs.CC #cs.GT
paper · pdf · doi:10.1145/1250790.1250873
published as Proceedings of STOC 2007, pages 565-574 · 23 pages, 12pt font, single-column compilation of STOC 2007 final version
arxiv created 2007/04/02 · arxiv updated 2013/10/16
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ł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.