Society for Industrial and Applied Mathematics eBooks

Chapter 3: Quantum Fourier transform and phase estimation

Giacomo Nannicini

Published Dec 17, 2025• 0 citations

Abstract

In this chapter we present two fundamental building blocks for quantum algorithms: the quantum Fourier transform, and one of its direct applications known as phase estimation. Both building blocks are used extensively in the rest of this book.

DOI: 10.1137/1.9781611978766.ch3

Related papers

Quantum Fourier Transform and Related Algorithms

Santanu Pattanayak

In this chapter, we will study the quantum Fourier transform and its application in different quantum algorithms. Problems such as factoring an integer into prime numbers or period finding are computationally intractable problems for a classical computer because of the exponentially large number of operations involved. Integer factoring and period finding can be efficiently solved using the quantum phase estimation algorithm that is heavily based on the quantum Fourier transform. Alternately, since quantum phase estimation aims to find the eigenvalue corresponding to an eigenvector of a unitary operator, it is backbone of important algorithms in optimization such as the HHL algorithm (named for Hassim, Harrow, and Lloyd), which serves as the matrix inversion routine in quantum computing. We start this chapter by revising our concepts of the Fourier transform and its discrete counterpart, the discrete Fourier transform , and then move on to the exciting domain of the quantum Fourier transform and the quantum phase estimation algorithm. We follow this up with a discussion and implementation of the few quantum Fourier transform–related algorithms such as factoring a number and period finding. At the end of the chapter, we briefly introduce the basics of group theory with an attempt to explain the hidden subgroup problem and how it relates to several of the Fourier transform–based algorithms.

Apress eBooksJan 1, 20210 citations

Quantum phase estimation and quantum amplitude estimation

Steven Herbert

Abstract This chapter introduces and analyses two of the most important quantum algorithmic primitives that are used in myriad applications, namely quantum phase estimation and quantum amplitude estimation (QAE). Quantum phase estimation (in the presentation covered in this chapter) uses the quantum Fourier transform, itself an extremely important quantum subroutine. In its original presentation, QAE combines quantum amplitude amplification (a generalisation of the circuit used in Grover’s algorithm) and quantum phase estimation to estimate the amplitude of a quantum state. However, more recent approaches achieve amplitude estimation without phase estimation, which is potentially practically advantageous. This chapter covers both, as well as some important applications of QAE such as quantum Monte Carlo integration and quantum counting.

Dec 8, 20250 citations

Quantum Fourier transform

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

This chapter covers the quantum Fourier transform, which is an essential quantum algorithmic primitive that efficiently applies a discrete Fourier transform to the amplitudes of a quantum state. It features prominently in quantum phase estimation and Shor’s algorithm for factoring and computing discrete logarithms.

Cambridge University Press eBooksApr 24, 20250 citations

Universal Quantum Algorithm

Avatar Tulsi

Quantum amplitude amplification and quantum phase estimation are two fundamental quantum algorithms. All known quantum algorithms are derived from these two algorithms. Even the adiabatic quantum algorithms can also be efficiently simulated using quantum phase estimation. We present a universal quantum algorithm which explains these two algorithms as special cases. An interesting result is that we do not need quantum fourier transform to do quantum phase estimation.

arXiv:1611.03472Nov 10, 20161 citation

Algorithms Using Quantum Fourier Transform

Robert Hundt

The quantum Fourier transform is another fundamental quantum algorithm. The section begins with a simple phase-kick circuit and expands to quantum phase estimation before detailing the quantum Fourier transform itself. A short section on arithmetic in the quantum domain introduces techniques that are used in a final detailed section on Shor’s famous algorithm for number factorization.

Cambridge University Press eBooksNov 20, 20250 citations

Quantum Fourier Transform and Phase Estimation in Qudit System

Ye Cao, Shi-Guo Peng, Chao Zheng +1 more

The quantum Fourier transform and quantum phase estimation are the key components for many quantum algorithms, such as order-finding, factoring, and etc. In this article, the general procedure of quantum Fourier transform and phase estimation are investigated for high dimensional case. They can be seen as subroutines in a main program run in a qudit quantum computer, and the quantum circuits are given.

Communications in Theoretical PhysicsMay 1, 201141 citations