Chapter 8: Quantum Search Algorithms

Chapter 8 introduces quantum algorithms for solving so-called search problems such as database search. Quantum search algorithms are said to be computationally less expensive and faster than classical search algorithms, where computational complexity is defined as the number of times a function called oracle is accessed. In this chapter, the oracle is explained first, followed by a detailed description of Grover’s algorithm, one of the most important examples of quantum search algorithms.

• 8-1. oracle
  • What is an oracle?
  • Reference
• 8-2. Grover’s algorithm
  • Algorithm Flow
    • 1. prepare a superposition state of all states \(|s\rangle = \frac{1}{\sqrt{N}}\sum_x |x\rangle\).
    • 2. Apply the oracle \(U_w\) (reversal operation on the solution)
    • 3. Applying the inversion operation \(U_s\) with \(|s\rangle\) as the axis of symmetry
    • 4. Repeat steps 2 and 3 \(k\) times
    • 5. Take a measurement
  • Geometric Explanation
    • Definition of a two-dimensional plane
    • Two inversion operations \(U_s U_w\) = rotation in a two-dimensional plane
    • Estimating the optimal \(k\).
  • Example Implementation
    • Checking the operation
  • Appendix
  • Reference