John Watrous (computer scientist)
John Harrison Watrous | |
|---|---|
 | |
| Alma mater | University of Wisconsin–Madison State University of New York at Stony Brook |
| Scientific career | |
| Fields | Computer Science, Quantum Computing |
| Institutions | University of Calgary University of Waterloo Institute for Quantum Computing Perimeter Institute for Theoretical Physics |
| Doctoral advisor | Eric Bach |
John Harrison Watrous is the Technical Director of IBM Quantum Education at IBM and was a professor of computer science at the David R. Cheriton School of Computer Science at the University of Waterloo, a member of the Institute for Quantum Computing, an affiliate member of the Perimeter Institute for Theoretical Physics and a Fellow of the Canadian Institute for Advanced Research.[1][2] He was a faculty member in the Department of Computer Science at the University of Calgary from 2002 to 2006 where he held a Canada Research Chair in quantum computing.[1]
He is an editor of the journal Theory of Computing[3] and former editor for the journal Quantum Information & Computation.[4] His research interests include quantum information and quantum computation. He is well known for his work on quantum interactive proofs, and the quantum analogue of the celebrated result IP = PSPACE: QIP = PSPACE.[5][6][7] This was preceded by a series of results, showing QIP can be constrained to 3 messages,[8] QIP is contained in EXP,[9] and the 2-message version of QIP is in PSPACE.[10] He has also published important papers on quantum finite automata[11] and quantum cellular automata.[12] With Scott Aaronson, he showed that certain forms of time travel can make quantum and classical computation equivalent: together, the authors showed that quantum effects do not offer advantages for computation if computers can send information to the past through a type of closed timelike curve proposed by the physicist David Deutsch.[13]
He obtained his Ph.D. in 1998 at the University of Wisconsin–Madison under the supervision of Eric Bach.[14][15]
References
[edit]- ^ a b John Watrous at the Canadian Institute for Advanced Research website.
- ^ John Watrous Archived 2011-07-06 at the Wayback Machine at the QuantumWorks website.
- ^ List of editors of Theory of Computing.
- ^ List of editors of Quantum Information & Computation.
- ^ Lance Fortnow (2009-07-29). "QIP = PSPACE". Computational Complexity. Retrieved 2009-12-30.
- ^ Dave Bacon (2009-07-28). "OMG QIP=PSPACE!". The Quantum Pontiff. Archived from the original on 2010-01-05. Retrieved 2009-12-30.
- ^ Rahul Jain; Zhengfeng Ji; Sarvagya Upadhyay; John Watrous (2009). "QIP = PSPACE". arXiv:0907.4737 [quant-ph].
- ^ Watrous, John (2003). "PSPACE has constant-round quantum interactive proof systems". Theor. Comput. Sci. 292 (3). Essex, UK: Elsevier Science Publishers Ltd.: 575–588. doi:10.1016/S0304-3975(01)00375-9. ISSN 0304-3975.
- ^ Kitaev, Alexei; Watrous, John (2000). "Parallelization, amplification, and exponential time simulation of quantum interactive proof systems". STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing. ACM. pp. 608–617. ISBN 978-1-58113-184-0.
- ^ Rahul Jain; Sarvagya Upadhyay; John Watrous (2009). "Two-message quantum interactive proofs are in PSPACE". arXiv:0905.1300 [cs.CC].
- ^ Kondacs, A.; Watrous, J. (1997). "On the power of quantum finite state automata". Proceedings of the 38th Annual Symposium on Foundations of Computer Science. pp. 66–75.
- ^ Watrous, John (1995). "On one-dimensional quantum cellular automata". Proc. 36th Annual Symposium on Foundations of Computer Science (Milwaukee, WI, 1995). Los Alamitos, CA: IEEE Comput. Soc. Press. pp. 528–537. doi:10.1109/SFCS.1995.492583. ISBN 0-8186-7183-1. MR 1619103..
- ^ Lisa Zyga (2008-11-20). "How Time-Traveling Could Affect Quantum Computing". PhysOrg. Retrieved 2009-12-30.
- ^ John Watrous at the Mathematics Genealogy Project.
- ^ John Watrous at the Institute for Quantum Computing directory.
