5 ms·
Indeed, NP-hard is wrong! NP-complete is the interesting class where quantum computers theoretically could help.
by nine_k 4y ago
Indeed, NP-hard is wrong! NP-complete is the interesting class where quantum computers theoretically could help.
- tsimionescu 4y agoFrom what I've read on Scott Aaronson's blogs, NP-complete is also wrong. The general suspicion seems to be that polynomial quantum algorithms (BQP) are separate from NP - they are suspected to be neither a subset nor a superset of NP. Some problems in BQP are suspected to be in NP (integer factorization, for which the best known classical algorithm is sub-exponential, but we have a polynomial time quantum algorithm), but there is no known NP-complete problem for which a quantum algorithm is known, or even suspected to exist. Edit - some links: [0] https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf - chapter 4 > If we interpret the space of 2n possible assignments to a Boolean formula φ as a “database,” and the satisfying assignments of φ as “marked items,” then Bennett et al.’s result says that any quantum algorithm needs at least ∼n/2 steps to find a satisfying assignment of φ with high probability, unless the algorithm exploits the structure of φ in a nontrivial way. In other words, there is no “brute-force” quantum algorithm to solve NP-complete problems in polynomial time, just as there is no brute-force classical algorithm. [1] https://youtu.be/0jrybODBUpA?t=30m28s https://youtu.be/0jrybODBUpA?t=30m28s "P versus NP"
- gaze 4y agoNo. Quantum computers are not known to provide any speed up to any NP problems.
- tsimionescu 4y agoThat is a bit too strong a claim (even taking "NP" to mean "NP - P", since all P problems are also in NP). First of all, while not proven, it is considered most likely that integer factorization is not in P, so potentially we already know of 1 NP-P problem which can have an exponential speed-up from a QC (Shor's algorithm). Secondly, there is one non-exponential speedup that can potentially apply to even NP-complete problems - using Grover's algorithm to find an element in an unordered list with complexity O(sqrt(n)) instead of the classical O(n).
- mirekrusin 4y agoIsn't the whole problem in there - as n - somehow this assumes that n-qubits can magically grow without a fuss - what if to entangle more quibits you need to cool the whole system down exponentially/using exponentially more energy? All those O(...) notations flip over, don't they?
- tsimionescu 4y agoAssuming the current version of Quantum Mechanics is correct, no. Given that we know QM is not compatible with General Relativity, which means one or both of them must be wrong, we could potentially discover some limitation of QM while investigating this. Ironically, if that were to happen, it would probably be a much more important boon for humanity than if we successfully build a working QC.
- edgyquant 4y agoThere isn’t actually any reason to believe one of them “is wrong” (we know they’re both approximations.) We just think that the macro and micro should follow the same fundamental laws because that’s how things have been thought to work so far. It could very well be that they are both great approximations and it’s actually the underlying information structure that shifts depending on scale. This doesn’t seem likely to us perhaps, but only because of existing intuition which we know is likely wrong at some level.
- tsimionescu 4y agoSure,"wrong" is a bit strong. I mean "wrong" in the same sense as Newtonian mechanics is wrong, which is exactly that it is an excellent approximation in some domains, but fails in others. > It could very well be that they are both great approximations and it’s actually the underlying information structure that shifts depending on scale. Right now, both QM and GR claim that they apply at any scale. If it turns out that the laws of physics change with scale, that means that both QM and GR are wrong, even though they may each be perfectly correct at the scale they have been seen to work so far.