4 ms·
Is it my impression or this result go against the yellow text at the banner?
by raverbashing 9y ago
Is it my impression or this result go against the yellow text at the banner?
- rwallace 9y 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 9y ago[deleted]
- myWindoonn 9y 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 9y 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 9y 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 9y agoThanks, those were very informative.