Pranab Sen School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road
Wednesday, 16 Sep 2009 (all day)
A-212 (STCS Seminar Room)
I propose to give a series of lectures explaining the recent paper by Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay and John Watrous showing that the class of problems having quantum interactive proofs is the same as the class of problems having classical deterministic
algorithms running in polynomial space. This was a decade long open problem in quantum computational complexity and is an excellent piece of work.

We shall refresh our memories on quantum computation and interactive proofs if needed. Earlier work showing that quantum interactive proofs need use at most three messages will also be briefly discussed. The first lecture will be a high level teaser of things to come.