Hacker News new | ask | show | jobs
by Robotbeat 3060 days 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.
1 comments
frostburg 3060 days ago
We 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.
link
Robotbeat 3060 days ago
/Proven/, sure. Hence the parenthetical "(etc)". As far as we know, however, factorization is not in P.
link
gji 3060 days ago
Your first statement isn't quite true. See, for example, 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.

link