School of Technology and Computer Science Seminars

QIP = PSPACE

by Dr. Rahul Jain (National University of Singapore, Singapore)

Wednesday, July 14, 2010 from to (Asia/Kolkata)
at Colaba Campus ( A-212 )
Description
We prove that the complexity class QIP, which consists of all problems having quantum interactive proof systems, is contained in PSPACE. This containment is proved by applying a parallelized form of the matrix multiplicative weights update method to a class of semidefinite programs that captures the computational power of quantum interactive proofs. As the containment of PSPACE in QIP follows immediately from the well-known equality IP = PSPACE, the equality QIP = PSPACE follows (joint work with Zhengfeng Ji, Sarvagya Upadhyay and John Watrous).

Winner of the Best Paper Award STOC 2010.
Organised by John Barretto