John Bostanci and John Watrous. Quantum game theory and the complexity of approximating quantum Nash equilibria. Manuscript, 2021. [pdf, arXiv:2102.00512]

Bryan Coutts, Mark Girard, and John Watrous. Certifying optimality for convex quantum channel optimization problems. Quantum 5: 448, 2021. [pdf, arXiv:1810.13295]

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. Manuscript, 2020. [pdf, arXiv:2003.14405]

Soumik Ghosh and John Watrous. Complexity limitations on one-turn quantum refereed games. Manuscript, 2020. [pdf, arXiv:2002.01509]

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): 0767, 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.
[html,
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, Sarvaghya Upadhyay, and John Watrous.
QIP = PSPACE.
*Journal of the ACM* 58(6): article 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* 446: 809–830,
2010.
[pdf,
arXiv:0908.1467]

Rahul Jain, Sarvaghya 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: 11, 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 Hoyer, 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: 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.

I am currently on leave from the University of Waterloo. I am not available to review papers, books, or proposals, and am not accepting new students or postdoctoral fellows at this time.