Publications by J. Watrous

J. Watrous, Bipartite subspaces having no bases distinguishable by local operations and classical communication, Physical Review Letters 95(8): 080505 (4 pp.), 18 August 2005.

C. Marriott and J. Watrous, Quantum arthur-merlin games, Computational Complexity 14(2): 122 - 152, 15 June 2005, arXiv.org:cs/0506068v1.

C. Marriott and J. Watrous, Quantum Arthur-Merlin games, Computational Complexity 14(2): 122 - 152, 13 June 2005. (A preliminary version appeared in Proceedings of the 19th Annual Conference on Computational Complexity, pages 275-285, 2004).

J. Watrous, Notes on super-operator norms induced by Schatten norms, Quantum Information and Computation 5(1): 58 - 68, 1 January 2005, arXiv.org:quant-ph/0411077.

E. Bach, S. Coppersmith, M. Goldschen, R. Joynt and J. Watrous, One-dimensional quantum walks with absorbing boundaries, Journal of Computer and System Sciences 69(4): 562 - 592, 1 December 2004, arXiv.org:quant-ph/0207008.

J. Watrous, Many copies may be required for entanglement distillation, Physical Review Letters 93(1): 010502 (4 pp.), 1 July 2004.

J. Watrous, PSPACE has constant-round quantum interactive proof systems, Theoretical Computer Science 292(3): 575-588, 31 January 2003. A preliminary version appeared in Proceedings of the 40th Annual Symposium on Foundations of Computer Science.

J. Watrous, On the complexity of simulating space-bounded quantum computations, Computational Complexity 12: 48 - 84, 1 January 2003.

J. N. de Beaudrap, R. Cleve and J. Watrous, Sharp quantum vs. classical query complexity separations, Algorithmica 34(4): 449 - 461, 1 November 2002, arXiv.org:quant-ph/0011065. A preliminary version appeared as Quantum Fourier transforms for extracting hidden linear structures in finite fields (2000)..

A. Ambainis and J. Watrous, Two-way finite automata with quantum and classical states, Theoretical Computer Science 287(1): 299 - 311, 25 September 2002, arXiv.org:cs.CC/9911009.

H. Buhrman, R. Cleve, J. Watrous and R. de Wolf, Quantum fingerprinting., Physical Review Letters 87(16): 167902 (4 pp.), 26 September 2001, arXiv.org:quant-ph/0102001.

J. Watrous, Quantum simulations of classical random walks and undirected graph connectivity, Journal of Computer and System Sciences 62(2): 376 - 391, 1 March 2001.

J. Watrous, Space-bounded quantum complexity, Journal of Computer and System Sciences 59(2): 281-326, 1 October 1999.

D. Leung, B. Toner and J. Watrous, Coherent state exchange in multi-prover quantum interactive proof systems, arXiv.org:0804.4118, 25 April 2008.

J. Watrous, Bipartite subspaces having no LOCC-distinguishable bases, arXiv.org:quant-ph/0503092, 18 March 2005.

J. Watrous, Many copies may be required for entanglement distillation, arXiv.org:quant-ph/0312123, 31 May 2004.

R. Cleve and J. Watrous, Fast parallel circuits for the quantum Fourier transform, arXiv.org:quant-ph/0006004, 1 June 2000.

A. Molina, T. Vidick and J. Watrous, Optimal counterfeiting attacks and generalizations for Wiesner's quantum money, 1 January 2013, Lecture Notes in Computer Science 7582, Proceedings of The Seventh Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC2012), K. Iwama, Y. Kawano and M Murao, eds., The University of Tokyo, Tokyo, Japan, 17 May 2012 - 19 May 2012, arXiv.org:1202.4010 (ISBN 978-3-642-35655-1).

A. Molina and J. Watrous, Hedging bets with correlated quantum strategies, Proceedings of The Royal Society of London Series A. Mathematical, Physical and Engineering Sciences, 1 September 2012 468(2145): 2614 - 2629, arXiv.org:1104.1140.

R. Jain, Z. Ji, S. Upadhyay and J. Watrous, QIP = PSPACE, 6 June 2010, Proceedings of 42nd Annual ACM Symposium on Theory of Computing (STOC 2010): 573 - 581, Cambridge, Massachusetts, 6 Jun 2010 - 8 Jun 2010.

G. Gutoski and J. Watrous, Toward a general theory of quantum games, 13 June 2007, Proceedings of The 39th ACM Symposium on Theory of Computing (STOC 2007): 565 - 574, San Diego, California, 11 Jun 2007 - 13 Jun 2007, arXiv.org:quant-ph/0611234.

J. Watrous, Zero-knowledge against quantum attacks, 21 May 2006, Proceedings of 38th ACM Symposium on Theory of Computing (STOC '06), Seattle, United States of America, 21 May 2006 - 23 May 2006, Published by Association for Computing Machinery, New York, United States of America, arXiv.org:quant-ph/0511020 (ISBN 1-59593-134-1).

J. Watrous, Zero-knowledge against quantum attacks, 21 May 2006, Proceedings of 38th ACM Symposium on Theory of Computing (STOC '06): 296 - 305, Seattle, United States of America, 21 May 2006 - 23 May 2006, Published by ACM, New York (ISBN 1-59593-134-1).

B. Rosgen and J. Watrous, On the hardness of distinguishing mixed-state quantum computations, 12 June 2005, Proceedings of 20th Annual IEEE Conference on Computational Complexity (CCC 2005): 344 - 354, San Jose, California, 12 Jun 2005 - 15 Jun 2005, Published by IEEE Comput. Soc., Los Alamitos, United States of America, arXiv.org:cs/0407056.

G. Gutoski and J. Watrous, Quantum interactive proofs with competing provers, 26 February 2005, Lecture Notes in Computer Science 3404: 605 - 616, Proceedings of 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS 2005), Stuttgart, Germany, 24 Feb 2005 - 26 Feb 2005, Published by Springer, Berlin, Germany, arXiv.org:cs.CC/0412102.

R. Cleve, P. Høyer, B. Toner and J. Watrous, Consequences and limits of nonlocal strategies, 24 August 2004, Proceedings of 19th Annual Computational Complexity Conference (CCC 2004): 236 - 249, Amherst, MA, 21 Jun 2004 - 24 Jun 2004, Published by IEEE Comput. Soc., Los Alamitos, United States of America, arXiv.org:quant-ph/0404076.

C. Marriott and J. Watrous, Quantum Arthur-Merlin games, 21 June 2004, Proceedings of 19th Annual Computational Complexity Conference (CCC 2004): 275 - 285, Amherst, MA, 21 Jun 2004 - 24 Jun 2004 (ISBN 0 7695 2120 7).

R. Cleve, P. Høyer, B. Toner and J. Watrous, Consequences and limits of nonlocal strategies, Computational Complexity, 21 June 2004, Proceedings of 19th IEEE Annual Conference on Computational Complexity (IEEE CCC 2004): 236 - 249, Amherst, 21 Jun 2004 - 24 Jun 2004, arXiv.org:quant-ph/0404076 (ISBN 0-7695-2120-7).

H. Gerhardt and J. Watrous, Continuous-time quantum walks on the symmetric group, 1 December 2003, Lecture Notes in Computer Science 2764: 845 - 859, Proceedings of 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 2003), Princeton University, NY, USA, 24 Aug 2003 - 26 Aug 2003, Published by Springer-Verlag, Berlin, Germany, arXiv.org:quant-ph/0305182 (ISBN 3-540-40770-7).

H. Gerhardt and J. Watrous, Continuous-time quantum walks on the symmetric group, 26 August 2003. Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM).

J. Watrous, Limits on the power of quantum statistical zero-knowledge, 19 November 2002, Proceedings of Symposium on Foundations of Computer Science (FOCS 2002): 459 - 468, Vancouver, 16 Nov 2002 - 19 Nov 2002. Manuscript (2003)..

A. Ambainis, E. Bach, A. Nayak, A. Vishwanath and J. Watrous, One-dimensional quantum walks, 6 July 2001, Proceedings of 33rd ACM Symposium on Theory of Computing (STOC 2001): 37 - 49, Creta, 6 Jul 2001 - 8 Jul 2001.

J. Watrous, Quantum algorithms for solvable groups, 6 July 2001, Proceedings of 33rd ACM Symposium on Theory of Computing (STOC 2001): 60 - 67, Creta, 6 Jul 2001 - 8 Jul 2001, arXiv.org:quant-ph/0011023.

R. Cleve and J. Watrous, Fast parallel circuits for the quantum Fourier transform, 14 November 2000, Proceedings of 41st Annual Symposium on Foundations of Computer Science (ASFCS 2000): 526 - 536, Redondo Beach, 12 Nov 2000 - 14 Nov 2000.

J. Watrous, Succinct quantum proofs for properties of finite groups, 14 November 2000, Proceedings of 41st Annual Symposium on Foundations of Computer Science (ASFCS 2000): 526 - 536, Redondo Beach, 12 Nov 2000 - 14 Nov 2000.

A. Kitaev and J. Watrous, Parallelization, amplification, and exponential time simulation of quantum interactive proof systems, 21 May 2000, Proceedings of 32nd ACM Symposium on Theory of Computing (STOC 2000): 608 - 617, Portalnd, OR, 21 May 2000 - 23 May 2000.

J. Watrous, On quantum and classical space-bounded processes with algebraic transition amplitudes, 18 October 1999, Proceedings of 40th Annual Symposium on Foundations of Computer Science (FOCS 1999): 341 - 351, New York City, 17 Oct 1999 - 19 Oct 1999, arXiv.org:cs.CC/9911008. Proceedings of the 40th Annual Symposium on Foundations of Computer Science.

J. Watrous, Quantum simulations of classical random walks and undirected graph connectivity, 6 May 1999, Proceedings of 14th Annual IEEE Conference on Computational Complexity (CCC 1999): 180 - 187, Atlanta, 4 May 1999 - 6 May 1999.

J. Watrous, Relationships between quantum and classical space-bounded complexity classes, 15 June 1998, Proceedings of 13th Annual IEEE Conference on Computational Complexity (CCC 1998): 210 - 227, Buffalo, 15 Jun 1998 - 18 Jun 1998, Published by IEEE.

A. Kondacs and J. Watrous, On the power of quantum finite state automata, 20 October 1997, Proceedings of Symposium on Foundations of Computer Science (FOCS 1997): 66 - 75, Miami Beach, 20 Oct 1997 - 22 Oct 1997.

J. Watrous, On one-dimensional quantum cellular automata, 23 October 1995, Proceedings of Symposium on Foundations of Computer Science (FOCS 1995): 528 - 537, Milwaukee, 23 Oct 1995 - 25 Oct 1995.

J. Watrous, Space-Bounded Quantum Computation (PhD Thesis), 1 January 1998. University of Wisconsin - Madison..

J. Watrous, A polynomial-time algorithm for the Artin-Whaples approximation theorem 15: 397 - 407, Published by AMS, 1 September 1995 (ISBN 0-8218-0312-3). Book Title - Number Theory. Fourth Conference of the Canadian Number theory Association.