Research papers

The list that follows includes all of my research papers. Please note that the linked pdf files are not necessarily the published versions of these papers — in some cases they are manuscript versions, and in a few cases they include revisions made after the papers were published (in which case the date of the revision is indicated).

• Soumik Ghosh and John Watrous. Complexity limitations on one-turn quantum refereed games. Theory of Computing Systems 67(2): 383–412, 2023. [pdf, arXiv:2002.01509]
• John Bostanci and John Watrous. Quantum game theory and the complexity of approximating quantum Nash equilibria. Quantum 6: 882, 2022. [pdf, arXiv:2102.00512]
• Mark Girard, Debbie Leung, Jeremy Levick, Chi-Kwong Li, Vern Paulsen, Yiu Tung Poon, and John Watrous. On the mixed-unitary rank of quantum channels. Communications in Mathematical Physics 394(2): 919–951, 2022. [pdf, arXiv:2003.14405]
• Bryan Coutts, Mark Girard, and John Watrous. Certifying optimality for convex quantum channel optimization problems. Quantum 5: 448, 2021. [pdf, arXiv:1810.13295]
• Anne Broadbent, Zhengfeng Ji, Fang Song, John Watrous. Zero-knowledge proof systems for QMA. SIAM Journal on Computing 49(2): 245–283, 2020. (A preliminary version appeared in Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, pages 31–40, 2016.) [pdf, arXiv:1604.02804]
• Colin Do-Yan Lee and John Watrous. Detecting mixed-unitary quantum channels is NP-hard. Quantum 4: 253, 2020. [pdf, arXiv:1902.03164]
• Abel Molina and John Watrous. Revisiting the simulation of quantum Turing machines by quantum circuits. Proceedings of the Royal Society A 475(2226): 20180767, 2019. [pdf, arXiv:1808.01701]
• Sanketh Menda and John Watrous. Oracle separations for quantum statistical zero-knowledge. Manuscript, 2018. [pdf, arXiv:1801.08967]
• Yuan Su and John Watrous. Time-reversal of rank-one quantum strategy functions. Quantum 2: 98, 2018. [pdf, arXiv:1801.08491]
• Vincent Russo and John Watrous. Extended nonlocal games from quantum-classical games. Chicago Journal of Theoretical Computer Science 2018: 4, 2018. [pdf, arXiv:1709.01837]
• Daniel Puzzuoli and John Watrous. Ancilla dimension in quantum channel discrimination. Annales Henri Poincaré 18(4): 1153–1184, 2017. [pdf, arXiv:1604.08197]
• Debbie Leung and John Watrous. On the complementary quantum capacity of the depolarizing channel. Quantum 1: 28, 2017. [pdf, arXiv:1510.01366]
• Thomas Vidick and John Watrous. Quantum proofs. Foundations and Trends in Theoretical Computer Science 11(1&2): 1–215, 2016. [pdf, arXiv:1610.01664]
• Nathaniel Johnston, Rajat Mittal, Vincent Russo, and John Watrous. Extended nonlocal games and monogamy-of-entanglement games. Proceedings of the Royal Society A 472(2189): 20160003, 2016. [pdf, arXiv:1510.02083]
• Tom Cooney, Christoph Hirche, Ciara Morgan, Jonathan Olson, Kaushik Seshadreesan, John Watrous, and Mark Wilde. Operational meaning of quantum measures of recovery. Physical Review A 94(2): 022310, 2016. [pdf, arXiv.org 1512.05324]
• Somshubhro Bandyopadhyay, Alessandro Cosentino, Nathaniel Johnston, Vincent Russo, John Watrous, and Nengkun Yu. Limitations on separable measurements by convex optimization. IEEE Transactions on Information Theory 61(6): 3593–3604, 2015. [pdf, arXiv:1408.6981]
• Marco Piani and John Watrous. Necessary and sufficient quantum information characterization of Einstein-Podolsky-Rosen steering. Physical Review Letters 114(6): 060404, 2015. [pdf, arXiv:1406.0530]
• Debbie Leung, Benjamin Toner, and John Watrous. Coherent state exchange in multi-prover quantum interactive proof systems. Chicago Journal of Theoretical Computer Science 2013: 11, 2013. [pdf, arXiv:0804.4118]
• John Watrous. Simpler semidefinite programs for completely bounded norms. Chicago Journal of Theoretical Computer Science 2013: 8, 2013. [pdf, arXiv:1207.5726]
• Abel Molina, Thomas Vidick, and John Watrous. Optimal counterfeiting attacks and generalizations for Wiesner’s quantum money. Proceedings of the 7th Conference on Theory of Quantum Computation, Communication, and Cryptography, volume 7582 of Lecture Notes in Computer Science, pages 45–64, 2013. [pdf, arXiv:1202.4010]
• Abel Molina and John Watrous. Hedging bets with correlated quantum strategies. Proceedings of the Royal Society A 468(2145): 2614–2629, 2012. [pdf, arXiv:1104.1140]
• Tsuyoshi Ito, Hirotada Kobayashi, and John Watrous. Quantum interactive proofs with weak error bounds. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 266–275, 2012. [pdf, arXiv:1012.4427]
• Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. QIP = PSPACE. Journal of the ACM 58(6): 30, 2011. (A preliminary version appeared in Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010.) [pdf, arXiv:0907.4737]
• John Watrous. An introduction to quantum information and quantum circuits. ACM SIGACT News 42(2): 52–67, 2011. [pdf]
• Salman Beigi, Peter Shor, and John Watrous. Quantum interactive proofs with short messages. Theory of Computing 7: 101–117, 2011. [pdf, arXiv:1004.0411]
• William Matthews, Marco Piani, and John Watrous. Entanglement in channel discrimination with restricted measurements. Physical Review A 82(3): 032302, 2010. [pdf, arXiv:1004.0888]
• Aram Harrow, Avinatan Hassidim, Debbie Leung, and John Watrous. Adaptive versus non-adaptive strategies for quantum channel discrimination. Physical Review A 81(3): 032339, 2010. [pdf, arXiv:0909.0256]
• Richard Jozsa, Barbara Kraus, Akimasa Miyake, and John Watrous. Matchgate and space-bounded quantum computations are equivalent. Proceedings of the Royal Society A 466(2115): 809–830, 2010. [pdf, arXiv:0908.1467]
• Rahul Jain, Sarvagya Upadhyay, and John Watrous. Two-message quantum interactive proofs are in PSPACE. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pages 534–543, 2009. [pdf, arXiv:0905.1300]
• John Watrous. Semidefinite programs for completely bounded norms. Theory of Computing 5: 217–238, 2009. [pdf, arXiv:0901.4709]
• Marco Piani and John Watrous. All entangled states are useful for channel discrimination. Physical Review Letters 102(25): 250501, 2009. [pdf, arXiv:0901.2118]
• John Watrous. Zero-knowledge against quantum attacks. SIAM Journal on Computing 39(1): 25–58, 2009. (A preliminary version appeared in Proceedings of the 38th ACM Symposium on Theory of Computing, pages 296–305, 2006.) [pdf, arXiv:0511020]
• Scott Aaronson and John Watrous. Closed timelike curves make quantum and classical computing equivalent. Proceedings of the Royal Society A 465(2102): 631–647, 2009. [pdf, arXiv:0808.2669]
• Rahul Jain and John Watrous. Parallel approximation of non-interactive zero-sum quantum games. Proceedings of the 24th Annual IEEE Conference on Computational Complexity, pages 243–253, 2009. [pdf, arXiv:0808.2775]
• John Watrous. Mixing doubly stochastic quantum channels with the completely depolarizing channel. Quantum Information and Computation 9(5&6): 406–413, 2009. [pdf, arXiv:0807.2668]
• John Watrous. Quantum computational complexity. Encyclopedia of Complexity and System Science, Springer, 2009. [pdf, arXiv:0804.3401]
• John Watrous. Distinguishing quantum operations having few Kraus operators. Quantum Information and Computation 8(9): 819–833, 2008. [pdf, arXiv:0710.0902]
• Gus Gutoski and John Watrous. Toward a general theory of quantum games. Proceedings of the 39th ACM Symposium on Theory of Computing, pages 565–574, 2007. [pdf]
• John Watrous. Bipartite subspaces having no bases distinguishable by local operations and classical communication. Physical Review Letters 95(8): 080505, 2005. [pdf]
• Bill Rosgen and John Watrous. On the hardness of distinguishing mixed-state quantum computations. Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pages 344–354, 2005. [pdf]
• Chris Marriott and John Watrous. Quantum Arthur-Merlin games. Computational Complexity 14(2): 122–152, 2005. (A preliminary version appeared in Proceedings of the 19th Annual IEEE Conference on Computational Complexity, pages 275–285, 2004.) [pdf]
• Gus Gutoski and John Watrous. Quantum interactive proofs with competing provers. Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, volume 3404 of Lecture Notes in Computer Science, pages 605–616, Springer-Verlag, 2005. [pdf]
• John Watrous. Notes on super-operator norms induced by Schatten norms. Quantum Information and Computation 5(1): 58–68, 2005. [pdf]
• Eric Bach, Susan Coppersmith, Marcel Paz Goldschen, Robert Joynt, and John Watrous. One-dimensional quantum walks with absorbing boundaries. Journal of Computer and System Sciences 69(4): 562–592, 2004. [pdf]
• John Watrous. Many copies may be required for entanglement distillation. Physical Review Letters 93(1): 010502, 2004. [pdf]
• Richard Cleve, Peter Høyer, Benjamin Toner, and John Watrous. Consequences and limits of nonlocal strategies. Proceedings of the 19th Annual IEEE Conference on Computational Complexity, pages 236–249, 2004. [pdf]
• John Watrous. On the complexity of simulating space-bounded quantum computations. Computational Complexity 12(1–2): 48–84, 2003. (A preliminary version appeared with the title “Quantum and classical space-bounded processes with algebraic transition amplitudes” in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pages 341–351, 1999.) [pdf]
• Heath Gerhardt and John Watrous. Continuous-time quantum walks on the symmetric group. Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science, 2003. [pdf]
• John Watrous. PSPACE has constant-round quantum interactive proof systems. Theoretical Computer Science 292(3): 575–588, 2003. (A preliminary version appeared in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pages 112–119, 1999.) [pdf]
• John Watrous. Limits on the power of quantum statistical zero-knowledge. Manuscript, 2003. (A preliminary version appeared in Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 459–468, 2002.) [pdf]
• Niel de Beaudrap, Richard Cleve, and John Watrous. Sharp quantum vs. classical query complexity separations. Algorithmica 34(4): 449–461, 2002. [pdf]
• Andris Ambainis and John Watrous. Two-way finite automata with quantum and classical states. Theoretical Computer Science 287(1): 299–311, 2002. [pdf]
• Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Physical Review Letters 87(16): 167902, 2001. [pdf]
• John Watrous. Quantum algorithms for solvable groups. Proceedings of the 33rd ACM Symposium on Theory of Computing, pages 60–67, 2001. [pdf]
• Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, and John Watrous. One-dimensional quantum walks. Proceedings of the 33rd ACM Symposium on Theory of Computing, pages 37–49, 2001. [pdf]
• John Watrous. Quantum simulations of classical random walks and undirected graph connectivity. Journal of Computer and System Sciences 62(2): 376–391, 2001. (A preliminary version appeared in Proceedings of the 14th Annual IEEE Conference on Computational Complexity, pages 180–187, 1999.) [pdf]
• John Watrous. Succinct quantum proofs for properties of finite groups. Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, pages 537–546, 2000. [pdf]
• Richard Cleve and John Watrous. Fast parallel circuits for the quantum Fourier transform. Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, pages 526–536, 2000. [pdf]
• Alexei Kitaev and John Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. Proceedings of the 32nd ACM Symposium on Theory of Computing, pages 608–617, 2000. [pdf]
• John Watrous. Space-bounded quantum complexity. Journal of Computer and System Sciences 59(2): 281–326, 1999. (A preliminary version appeared with the title “Relationships between quantum and classical space-bounded complexity classes” in Proceedings of the 13th Annual IEEE Conference on Computational Complexity, pages 210–227, 1998.) [pdf]
• Attila Kondacs and John Watrous. On the power of quantum finite state automata. Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, pages 66–75, 1997. [pdf]
• John Watrous. On one-dimensional quantum cellular automata. Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pages 528–537, 1995. [pdf]
• John Watrous. A polynomial-time algorithm for the Artin-Whaples approximation theorem. Number Theory: Fourth Conference of the Canadian Number Theory Association, pages 397–407, 1995.