Hacker News new | past | comments | ask | show | jobs | submit login

Yes, you are. Quantum computers are only believed to be faster than classical computers for a handful of very specific problems. And even those are not 100% proven (we don't have a proof that a faster classical algorithm doesn't exist for any of them, except Grover's search, which is only a quadratic speedup, not an exponential one).



> only believed to be faster than classical computers for a handful of very specific problems

But aren't these problems all in the factorial and exponential classes?


I think they are believed to be, but the opposite is not true. There are a lot of exponential or factorial problems that have no efficient QC algorithm, and are not beleieved to be likely to have one.

Also, at least the most famous problem which has an efficient QC algorithm, integer factorization, has no proven lower complexity bound on classical computers. That is, while the best algorithm we know for it is exponential (or, technically, sub-exponential), it is not yet proven that no polynomial classical algorithm exists. The problem isn't even NP-complete, so it's not like finding an efficient algorithm would prove P=NP.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: