All Abstracts | Poster Abstracts | Talk Abstracts | Tutorial Abstracts

QIP = PSPACE

John Watrous, University of Waterloo

(Session 7 : Saturday from 1:15-2:00)

Abstract. The interactive proof system model of computation is a cornerstone of complexity theory, and its quantum computational variant has been a topic of study in quantum complexity theory for the past decade. In this talk I will present 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 QIP = PSPACE, or in other words that the collection of computational problems having quantum interactive proof systems consists precisely of those problems solvable in polynomial space with an ordinary classical Turing machine. 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.