Tata Institute of Fundamental Research
QIP = PSPACE
Seminar
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)
(Scan to add to calendar)
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.
| 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) |
(Scan to add to calendar)
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.
Winner of the Best Paper Award STOC 2010.