Abstract :

We prove that QIP(2), the class of problems having two-message quantum interactive proof systems, is a subset of PSPACE. This relationship is obtained by means of an efficient parallel algorithm, based on the multiplicative weights update method, for approximately solving a certain class of semi-definite programs.

This is a joint work with Sarvagya Upadhyay and John Watrous.

Biography :

Prof. Rahul Jain received his Ph.D. in computer science from Tata Institute of Fundamental Research, Mumbai. He is currently an Assistant Professor of Computer Science Department and a Principal Investigator of Centre for Quantum Technologies (CQT) at National University of Singapore. His research interests include Information Theory, Quantum Computation, Communication Complexity, Complexity Theory and Cryptography.