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

Oxford University Press eBooks

Quantum Computing II

Muhammad Suhail Zubairy

Published May 7, 2020• 1 citation
Publisher

Abstract

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.

DOI
10.1093/oso/9780198854227.003.0016

Related papers

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 Computing Algorithms for Solving Complex Mathematical Problems

Et al. Lalit Mohan Trivedi

The power of quantum mechanics, that is too complex for conventional computers, can be solved by an innovative model of computing known as quantum computing. Quantum algorithms can provide exponential speedups for some types of problems, such as many difficult mathematical ones. In this paper, we review some of the most important quantum algorithms for hard mathematical problems. When factoring large numbers, Shor's algorithm is orders of magnitude faster than any other known classical algorithm. The Grover's algorithm, which searches unsorted databases much more quickly than conventional algorithms, is then discussed.

International Journal on Recent and Innovation Trends in Computing and Communication•Nov 7, 2023•2 citations

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 Factoring Algorithm and the Quantum Fourier Transform

Alice Flarend, Robert Hilborn

Abstract Expanding on the factoring and periodicity in Chapter 14, the Shor algorithm is explained in detail, with a warning that this is one of the toughest chapters in the book. While the steps of Shor algorithm may look just like the RSA in reverse, the quantum computer is needed to find the periodicity of the factors and thereby the prime factors themselves. Fourier analysis is the tool for this. The quantum Fourier transform is described, including the quantum circuit, after first showing what the classical Fourier transform accomplishes. Extensive examples of all the steps are given.

Oxford University Press eBooks•Jul 9, 2026•0 citations

Shor's algorithm and Grover's algorithm in quantum computing.

Chris Valle

In this paper we will analyse two quantum algorithms that sparked interest in the potential of quantum computers. The first is Lov Grover's algorithm which may be used to conduct a type of database search. The second is Peter Shor's algorithm which may be used to factor large numbers and provides an exponential speed up over the best current classical algorithms. In the context of these two algorithms we will discuss the benefits and weaknesses of quantum computation. We will show that in exchange for a quantum computer's greater speed we must accept an inherent level of uncertainty in our results.

•Jan 1, 2011•1 citation

Shor's algorithm

Nežka Rugelj

In this diploma paper we present the Shor’s algorithm for factorising numbers, which runs on quantum computers. \nInitially, we explain the basics of quantum computing. Afterwards, we present a general review of the Fourier and the discrete Fourier transform, from which we derive the quantum Fourier transform. \nIn the last part, we first give a short introduction to modular arithmetics. Later on, we describe the concept of factorization that is used in Shor’s algorithm. Diploma thesis ends with a detailed review of how the algorithm works on quantum computers and a simple example. \n

•Jan 1, 2017•0 citations
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.
The power of quantum mechanics, that is too complex for conventional computers, can be solved by an innovative model of computing known as quantum computing. Quantum algorithms can provide exponential speedups for some types of problems, such as many difficult mathematical ones. In this paper, we review some of the most important quantum algorithms for hard mathematical problems. When factoring large numbers, Shor's algorithm is orders of magnitude faster than any other known classical algorithm. The Grover's algorithm, which searches unsorted databases much more quickly than conventional algorithms, is then discussed.
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.
Abstract Expanding on the factoring and periodicity in Chapter 14, the Shor algorithm is explained in detail, with a warning that this is one of the toughest chapters in the book. While the steps of Shor algorithm may look just like the RSA in reverse, the quantum computer is needed to find the periodicity of the factors and thereby the prime factors themselves. Fourier analysis is the tool for this. The quantum Fourier transform is described, including the quantum circuit, after first showing what the classical Fourier transform accomplishes. Extensive examples of all the steps are given.
In this paper we will analyse two quantum algorithms that sparked interest in the potential of quantum computers. The first is Lov Grover's algorithm which may be used to conduct a type of database search. The second is Peter Shor's algorithm which may be used to factor large numbers and provides an exponential speed up over the best current classical algorithms. In the context of these two algorithms we will discuss the benefits and weaknesses of quantum computation. We will show that in exchange for a quantum computer's greater speed we must accept an inherent level of uncertainty in our results.
In this diploma paper we present the Shor’s algorithm for factorising numbers, which runs on quantum computers. \nInitially, we explain the basics of quantum computing. Afterwards, we present a general review of the Fourier and the discrete Fourier transform, from which we derive the quantum Fourier transform. \nIn the last part, we first give a short introduction to modular arithmetics. Later on, we describe the concept of factorization that is used in Shor’s algorithm. Diploma thesis ends with a detailed review of how the algorithm works on quantum computers and a simple example. \n