Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

CRC Press eBooks

Quantum Integral Transforms

Mikio Nakahara

Published Mar 11, 2008• 0 citations
Publisher

Abstract

We demonstrated in the previous chapter that there are some quantum algorithms superior to their classical counterparts. It is, however, rather difficult to find any practical use of these algorithms. There are two quantum algorithms, known to date, which are potentially useful: Grover’s search algorithm and Shor’s prime number factorization algorithm. Both of them depend on quantum integral transforms, which will be introduced in the present chapter. We mainly follow [1] in our presentation.

DOI
10.1201/9781420012293-12

Related papers

Advanced Algorithms: Unstructured Search and Integer Factorization with Grover and Shor

Vladimir Silva

This chapter brings two algorithms that have generated excitement about the possibilities of practical quantum computation:

Apress eBooks•Dec 18, 2023•2 citations

Quantum Computing II

Muhammad Suhail Zubairy

This chapter deals with some of the most prominent successes of quantum computing. The most well-known quantum computing algorithm, Shor’s algorithm for factoring a number in its prime factors, is discussed in details. The key to Shor’s algorithm is the quantum Fourier transform that is explained with the help of simple examples. The role of quantum entanglement is also discussed. The next important quantum computing algorithm is Grover’s algorithm that helps in searching an item in an unsorted database. This algorithm is motivated by first discussing a quantum shell game in which a pea hidden under one of the four shells is found in one measurement with certainty each time. This amazing result is then generalized to an arbitrary number of objects and Grover’s algorithm.

Oxford University Press eBooks•May 7, 2020•1 citation

Early quantum algorithms

Riccardo Manenti, Mário Motta

Abstract This chapter presents early quantum algorithms. We first describe Deutsch’s and Bernstein-Vazirani, some of the first quantum algorithms that showed a query advantage over their classical counterparts. We then present Grover’s algorithm, a quantum algorithm that finds an item in an unstructured database with a quadratic speed-up over classical algorithms. We explain the quantum Fourier transform, an important subroutine in various quantum algorithms. The chapter concludes with a detailed presentation of two of the most prominent applications of the quantum Fourier transform: the period finding algorithm and Shor’s algorithm for prime factorization.

Oxford University Press eBooks•Aug 25, 2023•0 citations

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 eBooks•Jan 1, 2021•1 citation

Quantum algorithms

In this chapter, we focus on quantum algorithms and the techniques underlying their construction. These algorithms take advantage of the basic properties of quantum mechanics, from the superposition principle to entanglement and interference effects, to solve certain computational problems much more efficiently than a classical computer. This includes basic problems of computer science: from the search of a marked item in an unstructured database (Grover’s algorithm) to integer factoring (Shor’s algorithm). The latter case provides a striking exponential speedup over the best known classical algorithms. After that, we discuss a third relevant class of quantum algorithms, the simulation of physical systems.

WORLD SCIENTIFIC eBooks•Dec 1, 2018•0 citations

Shor’s Factorization Algorithm

Mikio Nakahara

Shor’s factorization algorithm is one of the prime examples in which a quantum computer demonstrates enormous power surpassing its classical counterpart [1, 2]. Although the factorization algorithm may be carried out with a classical computer, it takes an exponentially longer time (i.e., practically impossible) compared to Shor’s quantum algorithm. Shor’s algorithm is almost identical with the classical one; it consists of a sequence of classical steps with one exception, which is replaced by a quantum algorithm. Our presentation here closely follows [3] and [4].

CRC Press eBooks•Mar 11, 2008•0 citations
We demonstrated in the previous chapter that there are some quantum algorithms superior to their classical counterparts. It is, however, rather difficult to find any practical use of these algorithms. There are two quantum algorithms, known to date, which are potentially useful: Grover’s search algorithm and Shor’s prime number factorization algorithm. Both of them depend on quantum integral transforms, which will be introduced in the present chapter. We mainly follow [1] in our presentation.
This chapter deals with some of the most prominent successes of quantum computing. The most well-known quantum computing algorithm, Shor’s algorithm for factoring a number in its prime factors, is discussed in details. The key to Shor’s algorithm is the quantum Fourier transform that is explained with the help of simple examples. The role of quantum entanglement is also discussed. The next important quantum computing algorithm is Grover’s algorithm that helps in searching an item in an unsorted database. This algorithm is motivated by first discussing a quantum shell game in which a pea hidden under one of the four shells is found in one measurement with certainty each time. This amazing result is then generalized to an arbitrary number of objects and Grover’s algorithm.
Abstract This chapter presents early quantum algorithms. We first describe Deutsch’s and Bernstein-Vazirani, some of the first quantum algorithms that showed a query advantage over their classical counterparts. We then present Grover’s algorithm, a quantum algorithm that finds an item in an unstructured database with a quadratic speed-up over classical algorithms. We explain the quantum Fourier transform, an important subroutine in various quantum algorithms. The chapter concludes with a detailed presentation of two of the most prominent applications of the quantum Fourier transform: the period finding algorithm and Shor’s algorithm for prime factorization.
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.
In this chapter, we focus on quantum algorithms and the techniques underlying their construction. These algorithms take advantage of the basic properties of quantum mechanics, from the superposition principle to entanglement and interference effects, to solve certain computational problems much more efficiently than a classical computer. This includes basic problems of computer science: from the search of a marked item in an unstructured database (Grover’s algorithm) to integer factoring (Shor’s algorithm). The latter case provides a striking exponential speedup over the best known classical algorithms. After that, we discuss a third relevant class of quantum algorithms, the simulation of physical systems.
Shor’s factorization algorithm is one of the prime examples in which a quantum computer demonstrates enormous power surpassing its classical counterpart [1, 2]. Although the factorization algorithm may be carried out with a classical computer, it takes an exponentially longer time (i.e., practically impossible) compared to Shor’s quantum algorithm. Shor’s algorithm is almost identical with the classical one; it consists of a sequence of classical steps with one exception, which is replaced by a quantum algorithm. Our presentation here closely follows [3] and [4].