[Please remove <h1>]

---

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