Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I think the odds are 0 in general, but perhaps higher for many actually "useful" algorithms.

Take grover's algorithm (basically find an item in a list or bruteforce something in O(sqrt(n)) time). The current best classical algorithm to bruteforce something is try every possibility, taking about n/2 guesses on average. The quantum version takes O(sqrt(n)). We are never going to be able to bruteforce with a normal computer faster than guessing all possibilities.



Second edit: I just realized I am completely wrong in what I'm saying below. Grover's algorithm is indeed optimal, and there is no equivalent classical algorithm that can finish as fast. However, this has nothing to do with BPP vs BQP, since it is not doing any kind of exponential speed up - both Grover's algorithm and classical search are polynomial time algorithms.

While this seems very likely, it has not yet been proven that unstructured search (the problem that Grover's algorithm solves) can't be solved by a probabilistic Turing machine in the same complexity with the same error bounds (that is, it's not proven that BPP != BQP).

So even if this seems intuitively obvious, it has eluded any proof so far - which I think is interesting in itself.

Edit: wording


We are only talking about a polynomial speed up, so i dont think bqp vs bpp is relavent.


Yes, apologies, you are completely right and I amended my comment.




Consider applying for YC's Winter 2026 batch! Applications are open till Nov 10

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

Search: