John Watrous (computer scientist)
Encyclopedia
John Harrison Watrous is an associate 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
. 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
and 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
equals PSPACE
, QIP equals PSPACE. This was preceded by a series of results, showing QIP can be constrained to 3 rounds, QIP is contained in EXP
, and the 2-round version of QIP is in PSPACE. He has also published important papers on quantum finite automata
and quantum cellular automata
. With Scott Aaronson
, he showed that time travel
makes quantum and classical computation equivalent.
He obtained his Ph.D.
in 1998 at the University of Wisconsin–Madison
under the supervision of Eric Bach
.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
at the David R. Cheriton School of Computer Science
David R. Cheriton School of Computer Science
The David R. Cheriton School of Computer Science is the School of Computer Science at the University of Waterloo. Part of the Faculty of Mathematics, the school comprises 77 faculty members, nearly 300 graduate students, approximately 2100 undergraduates, and 55 staff members.-History:In 1965,...
at the University of Waterloo
University of Waterloo
The University of Waterloo is a comprehensive public university in the city of Waterloo, Ontario, Canada. The school was founded in 1957 by Drs. Gerry Hagey and Ira G. Needles, and has since grown to an institution of more than 30,000 students, faculty, and staff...
, a member of the Institute for Quantum Computing
Institute for Quantum Computing
The Institute for Quantum Computing, or IQC, located in Waterloo, Canada, is an affiliate research institute of the University of Waterloo with a multidisciplinary approach to the field of quantum information processing.-IQC's Mission:...
, an affiliate member of the Perimeter Institute for Theoretical Physics
Perimeter Institute for Theoretical Physics
Perimeter Institute for Theoretical Physics is an independent, resident-based research institute devoted to foundational issues in theoretical physics located in Waterloo, Ontario, Canada. Perimeter Institute was founded in 1999 by Mike Lazaridis...
and a Fellow of the Canadian Institute for Advanced Research
Canadian Institute for Advanced Research
The Canadian Institute for Advanced Research enables Canadian researchers to work on international research teams that are custom built to transform their fields of study...
. He was a faculty member in the Department of Computer Science at the University of Calgary
University of Calgary
The University of Calgary is a public research university located in Calgary, Alberta, Canada. Founded in 1966 the U of C is composed of 14 faculties and more than 85 research institutes and centres.More than 25,000 undergraduate and 5,500 graduate students are currently...
from 2002 to 2006 where he held a Canada Research Chair in quantum computing.
He is an editor of the journal Theory of Computing
Theory of Computing (journal)
Theory of Computing is an online open access journal dedicated to theoretical computer science. The journal was founded in 2005 amidst growing concerns about the financial difficulties of university libraries around the world faced with rising costs in subscriptions to scientific journals owned by...
and Quantum Information & Computation. His research interests include quantum information
Quantum information
In quantum mechanics, quantum information is physical information that is held in the "state" of a quantum system. The most popular unit of quantum information is the qubit, a two-level quantum system...
and quantum computation. He is well known for his work on quantum interactive proofs, and the quantum analogue of the celebrated result IP
IP (complexity)
In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. The concept of an interactive proof system was first introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985...
equals PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
, QIP equals PSPACE. This was preceded by a series of results, showing QIP can be constrained to 3 rounds, QIP is contained in EXP
Exp
Exp may stand for:* Exponential function, in mathematics* Expiry date of organic compounds like food or medicines* Experience points, in role-playing games* EXPTIME, a complexity class in computing* Ford EXP, a car manufactured in the 1980s...
, and the 2-round version of QIP is in PSPACE. He has also published important papers on quantum finite automata
Quantum finite automata
In quantum computing, quantum finite automata or QFA are a quantum analog of probabilistic automata. They are related to quantum computers in a similar fashion as finite automata are related to Turing machines. Several types of automata may be defined, including measure-once and measure-many automata...
and quantum cellular automata
Quantum cellular automata
Quantum Cellular Automata refers to models of quantum computation, which have been devised in analogy to conventional models of cellular automata introduced by von Neumann...
. With Scott Aaronson
Scott Aaronson
Scott Joel Aaronson is a theoretical computer scientist and faculty member in the Electrical Engineering and Computer Science department at the Massachusetts Institute of Technology.-Education:...
, he showed that time travel
Time travel
Time travel is the concept of moving between different points in time in a manner analogous to moving between different points in space. Time travel could hypothetically involve moving backward in time to a moment earlier than the starting point, or forward to the future of that point without the...
makes quantum and classical computation equivalent.
He obtained his Ph.D.
Ph.D.
A Ph.D. is a Doctor of Philosophy, an academic degree.Ph.D. may also refer to:* Ph.D. , a 1980s British group*Piled Higher and Deeper, a web comic strip*PhD: Phantasy Degree, a Korean comic series* PhD Docbook renderer, an XML renderer...
in 1998 at the University of Wisconsin–Madison
University of Wisconsin–Madison
The University of Wisconsin–Madison is a public research university located in Madison, Wisconsin, United States. Founded in 1848, UW–Madison is the flagship campus of the University of Wisconsin System. It became a land-grant institution in 1866...
under the supervision of Eric Bach
Eric Bach
Eric Bach is an American computer scientist who has made contributions to computational number theory. Bach did his undergraduate studies at the University of Michigan, Ann Arbor, and got his Ph.D. in computer science from the University of California, Berkeley, in 1984 under the supervision of...
.