3 ms·
OMG QIP=PSPACE
- kragen 17y agoArticle author hasn't read the proof yet, but explains what it means if it's correct.
- amichail 17y agoTheoreticians 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.
- leif 17y agoneaterrific
- henning 17y agoThey will call this... year zero! Even after reading TFA I have no idea how important this is.
- teilo 17y agoSo, 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?
- fh 17y agoWhat 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.