QIP = PSPACE

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.

Authors

• Rahul Jain 0001
• Zhengfeng Ji
• Sarvagya Upadhyay
• John Watrous

Keywords

• matrix multiplicative weights update method
• quantum computation
• quantum interactive proof systems
• semidefinite programming