John Watrous (computer scientist)

{{Short description|Theoretical computer scientist}}

{{Infobox scientist

| name = John Harrison Watrous

| image = John Watrous.jpg

| alt = Portrait of Professor John Watrous, taken in the University of Waterloo's Davis Centre in January 2019

| birth_date =

| birth_place =

| death_date =

| death_place =

| citizenship =

| nationality =

| ethnicity =

| field = Computer Science, Quantum Computing

| work_institution = University of Calgary
University of Waterloo
Institute for Quantum Computing
Perimeter Institute for Theoretical Physics

| alma_mater = University of Wisconsin–Madison
State University of New York at Stony Brook

| doctoral_advisor = Eric Bach

| doctoral_students =

| known_for =

| prizes =

| religion =

| footnotes =

}}

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.[https://www.cifar.ca/profiles/john-watrous/ John Watrous] {{Webarchive|url=https://web.archive.org/web/20170517162412/https://www.cifar.ca/profiles/john-watrous/ |date=2017-05-17 }} at the Canadian Institute for Advanced Research website.[http://www.quantumworks.ca/section/view/?fnode=72 John Watrous] {{webarchive|url=https://web.archive.org/web/20110706201915/http://www.quantumworks.ca/section/view/?fnode=72 |date=2011-07-06 }} at the QuantumWorks website. 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.

He is an editor of the journal Theory of Computing[http://theoryofcomputing.org/editors.html List of editors of Theory of Computing]. and former editor for the journal Quantum Information & Computation.[http://www.rintonpress.com/journals/qic/ List of editors of Quantum Information & Computation]. 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.{{cite web |url=http://blog.computationalcomplexity.org/2009/07/qip-pspace.html |title=QIP = PSPACE |author=Lance Fortnow |author-link=Lance Fortnow |date=2009-07-29 |work=Computational Complexity |accessdate=2009-12-30}}{{cite web |url=http://scienceblogs.com/pontiff/2009/07/omg_qippspace.php |title=OMG QIP=PSPACE! |author=Dave Bacon |date=2009-07-28 |work=The Quantum Pontiff |accessdate=2009-12-30 |url-status=dead |archiveurl=https://web.archive.org/web/20100105065455/http://scienceblogs.com/pontiff/2009/07/omg_qippspace.php |archivedate=2010-01-05 }}{{cite arXiv|eprint=0907.4737|author1=Rahul Jain|author2=Zhengfeng Ji|author3=Sarvagya Upadhyay|author4=John Watrous|title=QIP = PSPACE|class=quant-ph|year=2009}} This was preceded by a series of results, showing QIP can be constrained to 3 messages,{{Cite journal | last1=Watrous | first1=John | title=PSPACE has constant-round quantum interactive proof systems | publisher=Elsevier Science Publishers Ltd. | location=Essex, UK | year=2003 | journal=Theor. Comput. Sci. | issn=0304-3975 | volume=292 | issue=3 | pages=575–588 | doi=10.1016/S0304-3975(01)00375-9| doi-access=free }} QIP is contained in EXP,{{Cite book | last1=Kitaev | first1=Alexei | last2=Watrous | first2=John | title=STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing | publisher=ACM | isbn=978-1-58113-184-0 | year=2000 | chapter=Parallelization, amplification, and exponential time simulation of quantum interactive proof systems | pages=608–617}} and the 2-message version of QIP is in PSPACE.{{cite arXiv|eprint=0905.1300|author1=Rahul Jain|author2=Sarvagya Upadhyay|author3=John Watrous|title=Two-message quantum interactive proofs are in PSPACE|class=cs.CC|year=2009}} He has also published important papers on quantum finite automata{{Cite conference

| last1 = Kondacs | first1 = A.

| last2 = Watrous | first2 = J.

| contribution = On the power of quantum finite state automata

| pages = 66–75

| title = Proceedings of the 38th Annual Symposium on Foundations of Computer Science

| title-link = Symposium on Foundations of Computer Science

| year = 1997}} and quantum cellular automata.{{Cite book

| last = Watrous | first = John

| contribution = On one-dimensional quantum cellular automata

| doi = 10.1109/SFCS.1995.492583

| location = Los Alamitos, CA

| mr = 1619103

| pages = 528–537

| publisher = IEEE Comput. Soc. Press

| title = Proc. 36th Annual Symposium on Foundations of Computer Science (Milwaukee, WI, 1995)

| title-link = Symposium on Foundations of Computer Science

| year = 1995

| isbn = 0-8186-7183-1

}}. 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.{{cite web |url=http://www.physorg.com/news146398685.html |title=How Time-Traveling Could Affect Quantum Computing |author=Lisa Zyga |date=2008-11-20 |work=PhysOrg |accessdate=2009-12-30}}

He obtained his Ph.D. in 1998 at the University of Wisconsin–Madison under the supervision of Eric Bach.{{MathGenealogy|id=75330|title=John Watrous}}.[http://www.iqc.ca/people/person.php?id=306 John Watrous] at the Institute for Quantum Computing directory.