1.2k citations · 3k across the 55 of their papers we have counts for
55 papers
Quantum game theory and the complexity of approximating quantum Nash equilibria
John Bostanci, John Watrous
This paper is concerned with complexity theoretic aspects of a general formulation of quantum game theory that models strategic interactions among rational agents that process and…
On the mixed-unitary rank of quantum channels
Mark Girard, Debbie Leung, Jeremy Levick +4
In the theory of quantum information, the mixed-unitary quantum channels, for any positive integer dimension , are those linear maps that can be expressed as a convex combinatio…
Complexity limitations on one-turn quantum refereed games
Soumik Ghosh, John Watrous
This paper studies complexity theoretic aspects of quantum refereed games, which are abstract games between two competing players that send quantum states to a referee, who perform…
Detecting mixed-unitary quantum channels is NP-hard
Colin Do-Yan Lee, John Watrous
A quantum channel is said to be a mixed-unitary channel if it can be expressed as a convex combination of unitary channels. We prove that, given the Choi representation of a quantu…
Certifying optimality for convex quantum channel optimization problems
Bryan Coutts, Mark Girard, John Watrous
We identify necessary and sufficient conditions for a quantum channel to be optimal for any convex optimization problem in which the optimization is taken over the set of all quant…
Revisiting the simulation of quantum Turing machines by quantum circuits
Abel Molina, John Watrous
Yao (1993) proved that quantum Turing machines and uniformly generated quantum circuits are polynomially equivalent computational models: steps of a quantum Turing machi…