Hacker News new | ask | show | jobs
by 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.
2 comments

/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.