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 )
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 |