Re:An Argument Against Quantum Computers
by frostburg on Wednesday February 07, 2018 @05:10PM
(#16328483)
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.
Re:An Argument Against Quantum Computers
by Robotbeat on Wednesday February 07, 2018 @05:33PM
(#16328615)
/Proven/, sure. Hence the parenthetical "(etc)". As far as we know, however, factorization is not in P.
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.
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.