3 ms·
> That they will remain infeasible for a long enough time for traditional computers to catch up to it. Doesn't work for things we know are exponentially faster
by Robotbeat 9y ago
> That they will remain infeasible for a long enough time for traditional computers to catch up to it.
Doesn't work for things we know are exponentially faster on quantum computers. Eventually, with enough (but not an absurd number) of bits, a decent quantum computer can solve problems that wouldn't be possible on a classical computer the size of the universe operating for billions of years.
Improvements in algorithms cuts both ways, too. And for some classes of problems, it's possible to prove (given P != NP, etc) that any classical algorithm is much worse than quantum.
- frostburg 9y agoWe don't know of any such thing. There is nothing proven to be NP-hard that can be done in polynomial time with a quantum algorithm. Factorization isn't proven to be NP-hard.
- deleted 9y ago[deleted]
- Robotbeat 9y ago/Proven/, sure. Hence the parenthetical "(etc)". As far as we know, however, factorization is not in P.
- gji 9y agoYour first statement isn't quite true. See, for example, https://www.scottaaronson.com/blog/?p=473 https://www.scottaaronson.com/blog/?p=473 In short, it's hard to classically model pretty simple quantum mechanical systems and sample the probability distribution of outcomes. Using a quantum computer to simulate the system and sample the probability distribution is easy.