9 Quantum phase estimation

 

This chapter covers

  • Estimating the frequency of a periodic quantum state
  • Eigenstates and eigenvalues
  • Estimating the angle of rotation of a quantum circuit
  • Quantum amplitude estimation and applications (quantum counting)

Now that we have learned about the QFT, we can implement one of the most useful quantum algorithms: quantum phase estimation (QPE). QPE is sometimes called the “Swiss army knife” of quantum computing. Many quantum algorithms use it as a building block. In particular, QPE plays an important role in Shor’s algorithm, a quantum computing algorithm that provides an exponential speedup over known classical algorithms for factoring integers, threatening to break the most common encryption methods used today, which involve factors of very large numbers.

Figure 9.1 shows the concepts introduced in this chapter. First we will review periodic quantum states and how to estimate the frequency of a period quantum state with measurement. Then we will learn about QPE. Finally, we will introduce another essential algorithm, quantum amplitude estimation, and look at example applications, specifically quantum counting.

Figure 9.1 A dependency diagram of concepts covered in this chapter
figure

9.1 Estimating the frequency of a periodic quantum state

9.1.1 Getting better angle estimates with more qubits

9.1.2 Reading between the ticks: Getting better estimates with interpolation

9.2 Quantum circuits as rotations with eigenstates and eigenvalues

9.3 The quantum phase estimation algorithm

9.4 Circuit-level implementation of the quantum phase estimation algorithm

9.5 An alternative implementation of the phase estimation circuit without qubit swaps

9.6 Amplitude estimation and quantum counting

9.6.1 Amplitude estimation

9.6.2 Estimating the number of good outcomes with quantum counting

9.6.3 Estimating the probability of good outcomes with amplitude estimation

Summary