|
|
0907.4737[abs pdf]
- Title:
QIP = PSPACE
Authors:
Rahul Jain,
Zhengfeng Ji,
Sarvagya Upadhyay,
John Watrous
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.
|