HackerPapers

arXiv:0907.4737quant-ph

QIP = PSPACE

Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

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.

arXiv comments
21 pages; v2 includes corrections and minor revisions
Journal reference
DOI
Subjects
quant-phQuantum Physics

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Aug 2009 to Aug 2009. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.