QIP = PSPACE
cacm.acm.org
QIP = PSPACE
1–10 of 11 posts
Re: QIP = PSPACE
#2A link to the actual paper for those interested: http://www.cs.cmu.edu/~odonnell/hits09/jain-ji-upadhay-watro....
Re: QIP = PSPACE
#3People wondering how IP = PSPACE can delve further into the free draft of this great book on the subject: http://www.cs.princeton.edu/theory/index.php/Compbook/Draft
Re: QIP = PSPACE
#4Does this mean quantum computers can't do anything classical computers can't? Does it let the air out of quantum computing? Or am I misreading?
Re: QIP = PSPACE
#5Does this mean quantum computers can't do anything classical computers can't? Does it let the air out of quantum computing? Or am I misreading?
Crap, we're still going to be using C when we get our flying cars!
Re: QIP = PSPACE
#6Does this mean quantum computers can't do anything classical computers can't? Does it let the air out of quantum computing? Or am I misreading?
No. It means that, when solving harder problems (way beyond NP, as PSPACE is a really big class), it doesn't matter having a quantum computer.
Re: QIP = PSPACE
#7Does this mean quantum computers can't do anything classical computers can't? Does it let the air out of quantum computing? Or am I misreading?
No. It means that for the complexity class of interactive proofs quantum and classical are the same (when you ignore the number of rounds involved.) This doesn't tell us anything about whether quantum polynomial time equals classical polynomial time. The "IP" classes have problems that are very intractable...this basically says that for these very intractable problems quantum won't help (with the caveat that the quantum seems to allow fewer rounds in the interactive proof.)
Re: QIP = PSPACE
#8Does this mean quantum computers can't do anything classical computers can't? Does it let the air out of quantum computing? Or am I misreading?
No. It means that for the complexity class of interactive proofs quantum and classical are the same (when you ignore the number of rounds involved.) This doesn't tell us anything about whether quantum polynomial time equals classical polynomial time. The "IP" classes have problems that are very intractable...this basically says that for these very intractable problems quantum won't help (with the caveat that the quan…
the quantum seems to allow fewer rounds in the interactive proof
This seems important. What if IP -> QIP is like O(N) -> O(log N)?
Re: QIP = PSPACE
#9Earlier quoted context omitted.
No. It means that for the complexity class of interactive proofs quantum and classical are the same (when you ignore the number of rounds involved.) This doesn't tell us anything about whether quantum polynomial time equals classical polynomial time. The "IP" classes have problems that are very intractable...this basically says that for these very intractable problems quantum won't help (with the caveat that the quan…
the quantum seems to allow fewer rounds in the interactive proof This seems important. What if IP -> QIP is like O(N) -> O(log N)?
The result, IIRC, is that all of QIP can be done in three rounds, whereas if the same held in the classical world the polynomial hierarchy would collapse (which is considered about as likely as P=NP). Not of practical value, but it does point out that QIP is a slightly different beast than IP when you include the number of rounds.
Re: QIP = PSPACE
#10This news (although not this particular link) was posted over a year ago.