paper / johnwatrous / Jul 15
John Watrous has published a 498-page structured course on quantum computing theory (arXiv:2507.11536v1), spanning 16 lessons with both video and written components. The course provides end-to-end coverage from foundational quantum information primitives through advanced topics including fault-tolerant computation and the toric code. It represents a rigorous, self-contained pedagogical resource targeting the theoretical underpinnings of quantum computation, authored by one of the field's leading researchers.
quantum-computingquantum-informationquantum-algorithmsquantum-error-correctionarxivcourse-materialtheoretical-computer-science
“The course consists of exactly 16 lessons, each with both a video and a written component.”
paper / johnwatrous / Jan 31
This paper demonstrates that finding approximate Nash equilibria in quantum games, like in classical games, falls within the PPAD complexity class. The key technical contribution is extending computational game theory methods to strategy spaces defined by semidefinite programs. This research is significant for understanding the computational limits of analyzing strategic interactions in quantum information processing.
quantum-game-theorycomputational-complexitynash-equilibriaquantum-informationsemidefinite-programming
“The computational problem of finding an approximate Nash equilibrium in a broad class of quantum games is PPAD-complete.”
paper / johnwatrous / Mar 31
This paper investigates the mixed-unitary rank (N) and Choi rank (r) of mixed-unitary quantum channels. It establishes a new upper bound for N in terms of r and presents the first known instances where N exceeds r, specifically for channels with Choi rank d+1 and mixed-unitary rank 2d.
quantum-informationquantum-channelsquantum-physicsmathematical-physicsmixed-unitary-rank
“For any mixed-unitary channel, the mixed-unitary rank N is less than or equal to r^2 - r + 1, where r is the Choi rank.”
paper / johnwatrous / Feb 4
This paper investigates the complexity classes of one-turn quantum refereed games (QRGs). It establishes tighter containment bounds for restricted variants of QRGs, specifically when one player sends classical states or the referee's measurement process is sequential. These results refine our understanding of the computational power of different QRG configurations.
quantum-computingcomputational-complexityquantum-informationcomplexity-theoryquantum-algorithms
“The complexity class QRG(1) trivially contains QMA U co-QMA.”