4 ms·
PDQP/qpoly = ALL
- raverbashing 8y agoIs it my impression or this result go against the yellow text at the banner?
- rwallace 8y agoIt 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.
- deleted 8y ago[deleted]
- myWindoonn 8y agoAdvice-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.
- schoen 8y agoIt'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. :-)
- x1798DE 8y agoIn 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 https://www.smbc-comics.com/comic/the-talk-3 (comic) https://www.quora.com/How-does-quantum-computer-consider-all-possibilities-simultaneously https://www.quora.com/How-does-quantum-computer-consider-all...
- raverbashing 8y agoThanks, those were very informative.
- QML 8y agoHow would one make “non-collapsing measurements”?