Hacker News new | past | comments | ask | show | jobs | submit login
PDQP/qpoly = ALL (scottaaronson.com)
34 points by weinzierl on May 20, 2018 | hide | past | favorite | 7 comments



Is it my impression or this result go against the yellow text at the banner?


In addition to the sibling comments, it's worth noting that this would neither be instantaneous nor does quantum computing work by "trying all the solutions at once."

Some examples of refutations of this myth:

https://www.smbc-comics.com/comic/the-talk-3 (comic)

https://www.quora.com/How-does-quantum-computer-consider-all...


Thanks, those were very informative.


Advice-bearing complexity classes are somewhat artificial. To quote the author in the comments:

"Adding advice always gives you the ability to solve some undecidable problems (since now you can decide an uncountable infinity of languages, rather than only a countable infinity). It’s just that normally, you’re highly constrained in which undecidable problems you can solve (e.g., you could solve the halting problem, but only if the input machine were encoded in unary notation). The surprise about /rpoly and /qpoly is that sometimes—it’s hard to predict where—they boost a complexity class up to solving undecidable problems with no constraints."

It's highly unlikely that we can actually forge a /qpoly class. Worse, the class PDQP is totally theoretical, in that it presumes a feature of quantum computers (non-collapsing measurements) which is totally theoretical and not expected to be realizeable with a physical machine.


It's sort of like "quantum computers plus a little magic (but only a little!) can solve every problem quickly". — While the regular physical kind still don't. :-)


It seems to be discussing, not the usual variety of quantum computation mentioned in the yellow text, but quantum computation plus a couple of hypothetical enhancements.


How would one make “non-collapsing measurements”?




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

Search: