3 ms·
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 algorith
by tsimionescu 4y ago
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
- bawolff 4y agoWe are only talking about a polynomial speed up, so i dont think bqp vs bpp is relavent.
- tsimionescu 4y agoYes, apologies, you are completely right and I amended my comment.