7 The quantum Fourier transform

 

This chapter covers

  • Periodic signals and periodic quantum states
  • Converting directions into magnitudes
  • Introducing the quantum Fourier transform and its inverse

The quantum Fourier transform (QFT) is an essential operation in quantum computing. The QFT is a crucial building block in numerous quantum algorithms, including some you may have already heard of, like Shor’s algorithm and quantum phase estimation. As a quantum computing developer, you need to understand the details of the QFT and the role it plays in other quantum algorithms. In this chapter, we will look closely at the structure and functionality of the QFT (see figure 7.1). Primarily, we will see how the QFT allows us to translate information encoded in amplitude directions (phases) into amplitude magnitudes. We will also see how the QFT can be performed efficiently on a quantum computer by taking advantage of quantum parallelism and interference. The efficiency of the QFT makes it a key tool in developing quantum solutions that perform better than their classical counterparts.

Figure 7.1 A dependency diagram of concepts introduced in this chapter
figure

7.1 Periodic patterns in sound waves and quantum states

7.1.1 Periodic patterns in sound waves

7.1.2 Periodic patterns in quantum states

7.1.3 Roots of unity and their geometric sequences

7.2 Converting from phase to magnitude encoding with the Hadamard gate

7.3 From classical to quantum Fourier transforms

7.3.1 The classical (discrete) Fourier transform

7.3.2 Introducing the QFT and IQFT

7.4 Quantum circuits for the QFT and IQFT

7.4.1 Understanding the effect of the IQFT on a geometric sequence state

Summary