QIP=PSPACE

The interactive proof system model of computation is a cornerstone of 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 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 (or QIP = PSPACE in complexity-theoretic terminology). This characterization implies the striking fact that quantum computing does not provide any increase in computational power over classical computing in the context of interactive proof systems.

I will not assume that the audience for this talk has any familiarity with either quantum computing or complexity theory; and to be true to the spirit of the interactive proof system model, I hope to make this talk as interactive as possible -- I will be happy to explain anything related to the talk that I can that people are interested in learning about.