10 ms·
Problem is, practically any special purpose can probably be done more cost effectively by brute forcing with conventional computing.
by moffkalast 4y ago
Problem is, practically any special purpose can probably be done more cost effectively by brute forcing with conventional computing.
- nine_k 4y agoCost of brute-forcing certain things (like NP-hard^W^W NP-complete problems) on regular computers quickly exceeds the cost of building and operating a quantum computer. Hence all the trying to make these contraptions work on non-toy problems.
- brnaftr361 4y agoJust make an Amoeboa computer?
- moffkalast 4y agoAt least it would be something new
- tsimionescu 4y agoWe 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?
- 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.