Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
OMG QIP=PSPACE (scienceblogs.com)
41 points by amichail on July 29, 2009 | hide | past | favorite | 6 comments


They will call this... year zero!

Even after reading TFA I have no idea how important this is.


Article author hasn't read the proof yet, but explains what it means if it's correct.


Theoreticians look at the authors to decide how likely a paper is to be correct.

In this case, the authors seem to have good credentials.

The author of the blog post probably thought this has a good chance of being correct.


So, from my completely layman's reading of this article, here's my take:

All that can be calculated on a Classic Turing-complete Computer can also be calculated on a Quantum Turing-complete Computer, and vice-versa. It will just take longer on a Classic Computer (sometimes a LOT longer).

Is this correct?


What you say is correct, but has been known for some time and has nothing to do with the thing proved being here. This new result is quite theoretical, and I fear that I can't explain all the relevant definitions in a few sentences. QIP = IP basically means that quantum computers are not much better than classical computers -- if both are attached to an implausible theorem prover.

Since those theorem provers don't exist, I'm not sure if there's any practical insight to be gained from this, but nevertheless it is a surprising result.


neaterrific




Consider applying for YC's Summer 2026 batch! Applications are open till May 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: