3 ms·
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
by frostburg 9y 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.
- 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.