John Harrison Watrous is a professor of

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...

at the David R. Cheriton School of Computer Science at the

University of Waterloo The University of Waterloo (UWaterloo, UW, or Waterloo) is a public research university with a main campus in Waterloo, Ontario, Canada. The main campus is on of land adjacent to "Uptown" Waterloo and Waterloo Park. The university also operates ...

, a member of the

Institute for Quantum Computing The Institute for Quantum Computing (IQC) is an affiliate scientific research institute of the University of Waterloo located in Waterloo, Ontario with a multidisciplinary approach to the field of quantum information processing. IQC was founde ...

, an affiliate member of the

Perimeter Institute for Theoretical Physics Perimeter Institute for Theoretical Physics (PI, Perimeter, PITP) is an independent research centre in foundational theoretical physics located in Waterloo, Ontario, Canada. It was founded in 1999. The institute's founding and major benefactor i ...

and a Fellow of the

Canadian Institute for Advanced Research The Canadian Institute for Advanced Research (CIFAR) is a Canadian-based global research organization that brings together teams of top researchers from around the world to address important and complex questions. It was founded in 1982 and is s ...

.John Watrous
at the

website. He was a faculty member in the Department of Computer Science at the

University of Calgary The University of Calgary (U of C or UCalgary) is a public research university located in Calgary, Alberta, Canada. The University of Calgary started in 1944 as the Calgary branch of the University of Alberta, founded in 1908, prior to being ins ...

from 2002 to 2006 where he held a

Canada Research Chair Canada Research Chair (CRC) is a title given to certain Canadian university research professors by the Canada Research Chairs Program. Program goals The Canada Research Chair program was established in 2000 as a part of the Government of Canada ...

in quantum computing. He is an editor of the journal Theory of Computing and former editor for the journal '' Quantum Information & Computation''. His research interests include

quantum information Quantum information is the information of the state of a quantum system. It is the basic entity of study in quantum information theory, and can be manipulated using quantum information processing techniques. Quantum information refers to both t ...

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 In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...

, QIP equals PSPACE. This was preceded by a series of results, showing QIP can be constrained to 3 messages, QIP is contained in

EXP Exp may stand for: * Exponential function The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the pos ...

, and the 2-message version of QIP is in PSPACE. He has also published important papers on quantum finite automata and quantum cellular automata. With

Scott Aaronson Scott Joel Aaronson (born May 21, 1981) is an American theoretical computer scientist and David J. Bruton Jr. Centennial Professor of Computer Science at the University of Texas at Austin. His primary areas of research are quantum computing a ...

, he showed that certain forms of

time travel Time travel is the concept of movement between certain points in time, analogous to movement between different points in space by an object or a person, typically with the use of a hypothetical device known as a time machine. Time travel is a ...

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 In mathematical physics, a closed timelike curve (CTC) is a world line in a Lorentzian manifold, of a material particle in spacetime, that is "closed", returning to its starting point. This possibility was first discovered by Willem Jacob van St ...

proposed by the physicist

David Deutsch David Elieser Deutsch ( ; born 18 May 1953) is a British physicist at the University of Oxford. He is a Visiting Professor in the Department of Atomic and Laser Physics at the Centre for Quantum Computation (CQC) in the Clarendon Laboratory of ...

. He obtained his

Ph.D. A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: or ') is the most common degree at the highest academic level awarded following a course of study. PhDs are awarded for programs across the whole breadth of academic fields. Because it is ...

in 1998 at the

University of Wisconsin–Madison A university () is an institution of higher (or tertiary) education and research which awards academic degrees in several academic disciplines. Universities typically offer both undergraduate and postgraduate programs. In the United Stat ...

under the supervision of Eric Bach..John Watrous
at the

directory.

References

{{DEFAULTSORT:Watrous, John Living people University of Waterloo faculty University of Wisconsin–Madison alumni Theoretical computer scientists Cellular automatists Canada Research Chairs Year of birth missing (living people) Quantum information scientists