Lesson plan
Grover's algorithm
In quantum computing, Grover's algorithm, also known as the quantum search algorithm, is a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just O(\sqrt{N}) evaluations of the function, where N is the size of the function's domain. It was devised by an Indian-American computer scientist Lov Grover in 1996. The analogous problem in classical computation would have a query complexity O(N) (i.e., the function would have to be evaluated O(N) times: there is no better approach than trying out all input values one after the other, which, on average, takes N/2 steps). Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani proved that any quantum solution to the problem needs to evaluate the function \Omega(\sqrt{N}) times, so Grover's algorithm is asymptotically optimal. Since classical algorithms for NP-complete problems require exponentially many steps, and Grover's algorithm provides at most a quadratic speedup over the classical solution for unstructured search, this suggests that Grover's algorithm by itself will not provide polynomial-time solutions for NP-complete problems (as the square root of an exponential function is still an exponential, not a polynomial function).…
Article summary
In quantum computing, Grover's algorithm, also known as the quantum search algorithm, is a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just O(\sqrt{N}) evaluations of the function, where N is the size of the function's domain. It was devised by an Indian-American computer scientist Lov Grover in 1996. The analogous problem in classical computation would have a query complexity O(N) (i.e., the function would have to be evaluated O(N) times: there is no better approach than trying out all input values one after the other, which, on average, takes N/2 steps). Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani proved that any quantum solution to the problem needs to evaluate the function \Omega(\sqrt{N}) times, so Grover's algorithm is asymptotically optimal. Since classical algorithms for NP-complete problems require exponentially many steps, and Grover's algorithm provides at most a quadratic speedup over the classical solution for unstructured search, this suggests that Grover's algorithm by itself will not provide polynomial-time solutions for NP-complete problems (as the square root of an exponential function is still an exponential, not a polynomial function).…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.