QIP = PSPACE

Details QIP = PSPACE QIP = PSPACE

2009-07-27

arxiv.org/abs/0907.4737v2

Physics

Quantum Physics

21 pages; v2 includes corrections and minor revisions

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

QIP = PSPACE does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with QIP = PSPACE, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and QIP = PSPACE will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-246711