John Watrous – QIP = PSPACE
The interactive proof system model of computation is a cornerstone of computational complexity theory, and its quantum computational variant has been a central topic of study in quantum complexity theory for the past decade. In this talk I will introduce the basic notions of both quantum computation and the interactive proof system model, and 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.
Location: DC 1302
Time: 4:15-5:00pm
David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
Tel: 519-888-4567 x33293
Fax: 519-885-1208
Contact | Feedback: cs-webmaster@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics
Last modified: Friday, 11-Sep-2009 09:47:25 EDT
