3 ms·
D-Wave computers are quantum annealers, not machines capable of running, for example, Grover’s or Shor’s algorithm. And even these algorithms can help asymptot
by stochastic_monk 9y ago
D-Wave computers are quantum annealers, not machines capable of running, for example, Grover’s or Shor’s algorithm.
And even these algorithms can help asymptotic complexity, but not solve an NP complete problem in polynomial time.
(Even AES256 is pretty much safe against a quantum attack, since a quantum computer effectively square roots the time complexity, and that just leaves key-exchange protocols, of which several QR-variants exist.)
Personally, I think the hype far outweighs the value, even compared to Big Data/IoT.
- taejo 9y ago> And even these algorithms can help asymptotic complexity Is this a theorem or conjecture?
- stochastic_monk 9y agoExisting quantum algorithms have not yet been found which have reduced NP-complete problems to polynomial time. (See [0] for a pretty comprehensive list.) IE, I was talking about quantum algorithms we have, none of which have done so, not stating the impossibility of such an algorithm. I am not aware of a proof that comments on whether or not such an algorithm is impossible, however. [0]: https://math.nist.gov/quantum/zoo/ https://math.nist.gov/quantum/zoo/