4 ms·
We don't know of a single NP-hard problem where quantum computers would show any exponential speed-up (there may be some speed-up by using the O(sqrt(n)) brute
by tsimionescu 4y ago
We don't know of a single NP-hard problem where quantum computers would show any exponential speed-up (there may be some speed-up by using the O(sqrt(n)) brute search quantum algorithm instead of the classical O(n) search algo, but that will be quickly drowned out by the exponential factors).
Even worse, there is no reason to think that there will ever be - as far as we know, QCs only show an exponential advantage on problems with very very specific structures, while the whole problem of NP-hard problems is that they have no structure in general.
- nine_k 4y agoIndeed, 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.
- jeremyjh 4y agoI thought there were concerns about public key cryptography - factoring large numbers much faster with QC at least sounds plausible, but maybe it’s just speculation ?
- tsimionescu 4y agoThat is true, but integer factorization is not an NP-hard problem, as far as we know at least. A quantum algorithm, Shor's algorithm, is indeed known to be able to solve it in polynomial time if you have a QC. It is suspected to be NP but not even NP-complete, nevermind NP-hard. It is suspected not to be in P, but that is not yet proven.
- kragen 4y agoInteger factorization is obviously in NP, though as you say, whether it is in the P subset of NP is still an open question.
- tsimionescu 4y agoI was trying to be careful with my language specifically to avoid this mistake, but I still messed up...
- kragen 4y agoIt's tricky!
- PeterisP 4y agoWe're moving on to quantum-resistant public key cryptography, so unless some QC hardware breakthrough appears really soon, we'd expect quantum computers to be useless against public key cryptography because we won't rely on the difficulty of factoring large numbers as a security measure by the time large enough quantum computers appear.