Grover's Algorithm



Summary

Grover’s algorithm, also known as 'quantum search' and 'amplitude amplification', is a search algorithm for unstructured databases. It is provably optimal for quantum computers, and quadratically faster than the best classical algorithm. Lov Grover published his algorithm in “A fast quantum mechanical algorithm for database search” (1996)

This website tries to take a different approach to teaching quantum search, giving more specific contexts and problems that can then be generalised in later sections. We use lots of circuit diagrams and give a working example of quantum search as early as possible, hopefully this will help the student understand the potential uses of quantum search faster and understand how the reflections in the algorithm correspond to useful computations.


Contents

  1. Preamble
  2. Grover's Algorithm
  3. Using Grover's Algorithm (Example)
  4. More about Quantum Search
    • Search for Unknown Number of Solutions
  5. Exploiting Structure
    • Combining with Classical Algorithms
    • Nested Quantum Search