PDQP/qpoly = ALL

(scottaaronson.com)

34 points | by weinzierl 2168 days ago

2 comments

  • raverbashing 2168 days ago
    Is it my impression or this result go against the yellow text at the banner?
    • x1798DE 2168 days ago
      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...

      • raverbashing 2168 days ago
        Thanks, those were very informative.
    • myWindoonn 2168 days ago
      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.

      • schoen 2168 days ago
        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. :-)
    • rwallace 2168 days ago
      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.
  • QML 2167 days ago
    How would one make “non-collapsing measurements”?