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.
[ Parent
| on HN ]
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.