Chapter 2: Introduction to Quantum Algorithms

A quantum computer can process \(2^n\) states simultaneously using \(n\) qubits through quantum mechanical superposition. However, this alone does not imply speedup over classical computation. This is because when we observe the result after the computation, only one of the \(2^n\) states is obtained at random. Therefore, it is essential to have a special algorithm for quantum computers designed to obtain the desired answer with high probability. Such an algorithm is called a quantum algorithm. Famous examples of quantum algorithms include Shor’s prime factorization algorithm and Grover’s search algorithm.

In this chapter, we will learn the rudiments of quantum algorithms. First, we will see that quantum algorithms can be divided into two main types: algorithms that can be (or are thought to be) executed on quantum computers that will be realized in the next few years = “NISQ devices”, and algorithms that can be executed only on true quantum computers with error correction that will be realized in more than a decade from now. Next, we will learn the simplest quantum algorithm, the Hadamard test. After that, we will learn about the quantum Fourier transform and its development, the phase estimation algorithm, which is the most important quantum algorithm when considering applications of quantum computers. (Incidentally, both the quantum Fourier transform and the phase estimation algorithm are classified as long-term algorithms, since it is considered difficult to run a practical size problem on a NISQ device.)

• 2-1. NISQ algorithm and long-term algorithm
  • NISQ Algorithm
    • What is NISQ?
    • NISQ Algorithm Overview
  • Long-Term Algorithm
  • To learn more :
• 2-2. Hadamard test
  • Implementation in SymPy
• 2-3. Quantum Fourier transform
  • Definition
  • Circuit Configuration
  • Implementation using SymPy
  • Column: About Computational Power
    • Note on the order notation \(\mathcal{O}\).
• 2-4. Phase Estimation Algorithm（Introductory）
  • Introduction: Improving the Hadamard Test
  • Phase Estimation Algorithm: Overview
  • Phase Estimation Algorithm: Configuration
  • SymPy example
  • Column: Prime Factorization and Phase Estimation (somewhat difficult)
  • Summary of Chapter 2