{"id":2382,"date":"2009-07-28T12:10:04","date_gmt":"2009-07-28T19:10:04","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=2382"},"modified":"2009-07-28T12:10:04","modified_gmt":"2009-07-28T19:10:04","slug":"omg-qippspace","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2009\/07\/28\/omg-qippspace\/","title":{"rendered":"OMG QIP=PSPACE!"},"content":{"rendered":"

Today on the arXiv an new paper appeared of great significance to quantum computational complexity: arXiv:0907.4737<\/a> (vote for it on scirate here)<\/p>\n

Title: QIP = PSPACE<\/b>
\nAuthors: Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous
\nWe 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.<\/p><\/blockquote>\n

This solves a long standing open problem (we can say long standing in quantum computing when we mean less than nine years because our field is so young.) It has always been known that PSPACE is in QIP, but prior to this result (assuming its correct: I just downloaded the paper and am starting to read it now) the best known inclusion in the other direction was that QIP is in EXP (this result is due to Kitaev and Watrous.) But wait a second, what the hell are all these letters representing?
\n
\nPSPACE is the class of decision problems decidable by a Turing machine using only a polynomial amount of memory (polynomial in the problem size) and an unlimited amount of time. This should be contrasted with P which is the class of decision problems decidable by a deterministic Turing machine using a polynomial amount of time (and hence a polynomial amount of memory.) While things in P are problems that can reasonably be called efficient, things in PSPACE are not. In other words PSPACE is thought to contain problems which are very much not tractable. This, of course, defies most physicists, who upon hearing this result mumble something about space and time and spacetime. Of course these physicists are wrong and have read way to much into the popular expression that “Einstein put space and time on equal footing.” Or maybe they are correct and there is a revolution waiting to happen (one would note, for instance that if one allows closed time like curves then BPP with close time like curves = PSPACE. Proven by Watrous and Aaronson here.)
\nOkay PSPACE seems like a reasonable complexity class to study. Sure it’s got probably intractable problems, but hey we should still study it! Now what about QIP. Well to be down with QIP you need to first be down with IP. IP is the complexity class known as “interactive proof systems.” In an interactive proof system there are two parties, a prover and a verifier. The verifier is assumed to computationally limited, i.e. he can only use resources (time,space) polynomial in the instance size (he is given access to randomness so that he can do things which are reasonably classically tractable.) The prover, on the other hand, is given god like powers and allowed unlimited computational power. These two parties interact by a polynomial number of rounds of communication. The idea here is that the prover is trying to prove that the problem instance is in the language and the verifier wants to make sure this is true. Thus on instances that are in the language the verifier should accept with greater than (say) 2\/3 probability (this is called completeness) and on instance that are not in the language the verifier should accept with less than (say) 1\/3 probability (this is called soundness.) Completeness tells us that the prover can convince us with high probability that the instance is in the language and soundness tells us that false statements cannot be proved (we can’t be fooled.) IP is the class of decision problems that admit an interactive proof system.
\nBack to the story at hand. One of the major results in computational complexity theory is that PSPACE, that beast which uses limited memory but unlimited time, is actually equal to IP. Proofs of this fact involve some cool tricks, among them the arithmetization: basically this is a method for transforming boolean formulas into many variable polynomials over some finite field. Reasoning about this later object then facilitates the proof of PSPACE contained in IP (the other direction, that IP is contained in PSPACE is a bit easier.) I believe this proof is also important because it doesn’t relativize (A note on attribution: I sometimes see two references attributed to this proof and sometimes only one. I don’t know the history behind this, but the papers are one by Lund, Fortnow, Karloff, and Nisan and the other by Shamir.)
\nOkay so what is the claim of the paper published today? Well QIP is like IP but now the verifier is assumed to be running a polynomial sized quantum algorithm and the messages exchanged between the parties are allowed to be quantum. QIP was first studied in detail by Watrous and then by Watrous and Kitaev. The classic papers are<\/p>\n

J. Watrous. PSPACE has constant-round quantum interactive proof systems. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pages 112-119, 1999. arXiv:cs\/9901015<\/a>
\nKitaev and J. Watrous. Parallelization, ampli\ufb01cation, and exponential time simu-
\nlation of quantum interactive proof system. In Proceedings of the 32nd Annual ACM
\nSymposium on Theory of Computing, pages 608-617, 2000. pdf here<\/p><\/blockquote>\n

As I mentioned above, these papers showed that QIP was contained in EXP (the class of problems solvable by a deterministic Turing machine in exponential time.) PSPACE is in QIP because we could always have not used the quantum part of the interactive proof and just made it classical. But a longstanding question is whether one could tighten the gap between PSPACE and EXP. Today’s paper shows that indeed QIP=PSPACE.
\nWhat does this say about the power of quantum computers? Well on the one hand, I’m not sure it does tell us too much (ask Scott, damnit!) since these complexity classes are, off the top, most interesting for the intractable problems they represent. On the other hand there is an impressive result about QIP. One can talk about the number of rounds in a QIP protocol. It turns out (this was proved by Watrous in the first paper listed above) that a QIP protocl with only three rounds has the power of all of QIP (i.e. with a polynomial number of rounds.) Such a result for IP does not hold unless the polynomial hierarchy collapses to AM (which, in complexity theorist talk is, quite blasphemous.) In other words one can be convinced of whether an instance of a problem is or is not in PSPACE quantumly using only three rounds of discussion, as opposed to in the classical world where the discussion can go on and on and on and on… Let it never be said that the quantum world is the blabber mouth in comparison to the classical world.
\nWell now it’s time to seal myself away and actually read the proof. Congrats to the authors and here’s hoping that the proof is correct and yet another major open problem has been put to its grave.
\nUpdate 6\/29\/09:<\/b> See the Computational Complexity for an outline<\/a> of the proof written by Steve Fenner.<\/p>\n","protected":false},"excerpt":{"rendered":"

Today on the arXiv an new paper appeared of great significance to quantum computational complexity: arXiv:0907.4737 (vote for it on scirate here) 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 … <\/p>\n

Continue reading “OMG QIP=PSPACE!”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[20,65],"tags":[],"class_list":["post-2382","post","type-post","status-publish","format-standard","hentry","category-computer-science","category-quantum-computing"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/2382","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/comments?post=2382"}],"version-history":[{"count":0,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/2382\/revisions"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/media?parent=2382"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/categories?post=2382"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/tags?post=2382"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}