Dr. Watrous' research focuses on the theory of quantum information
science and its applications to algorithms, complexity theory and
cryptography. He has recently solved a decade-old problem in
complexity, proving QIP=PSPACE.

Abstract: The interactive proof system model of computation is a
cornerstone of computational complexity theory, and its quantum
computational variant has been studied in quantum complexity theory
for the past decade. In this talk I will discuss an exact
characterization of the expressive power of quantum interactive proof
systems that I recently proved in collaboration with Rahul Jain,
Zhengfeng Ji, and Sarvagya Upadhyay. The characterization states that
the collection of computational problems having quantum interactive
proof systems consists precisely of those problems solvable with an
ordinary classical computer using a polynomial amount of memory usage
(or QIP = PSPACE in complexity-theoretic terminology). This
characterization implies the striking fact that quantum computing does
not provide an increase in computational power over classical
computing in the context of interactive proof systems.

Thursday, Jan 28, 2010
4 p.m.
Bricker Academic, Rm BA-110

Speaker: Professor John Watrous
Associate Professor, David R. Cheriton School of Computer Science,
University of Waterloo
Fellow, Canadian Institute for Advanced Research
Member, Institute for Quantum Computing

Title: QIP = PSPACE

For further details and abstract, consult the Laurier CSASM website at
http://www.mmcs.wlu.ca/csasm/