Tutte seminar - John Watrous

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. Our proof of this characterization is based on a parallel algorithm for approximately solving a special class of semidefinite optimization problems.