QIP = PSPACE

Speaker:
Rahul Jain National University of Singapore Department of Computer Science S15#04-01, 3 Science Drive 2 Singa
Date:
Wednesday, 14 Jul 2010 (all day)
Venue:
A-212 (STCS Seminar Room)
Category:
Abstract
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.