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

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

Chris Valle

Published Jan 1, 2011• 1 citation
OpenAlex

Abstract

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.

Related papers

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 a decade after shor

Andris Ambainis

In 1994, Peter Shor discovered a polynomial time quantum algorithm for factoring and discrete logarithm. Two years later, in 1996, Lov Grover discovered a search algorithm which is quadratically better than conventional search. By now, each of the two algorithms has developed into a line of research which goes well beyond the original algorithm. Shor's algorithm has inspired the study of quantum Fourier sampling which has resulted in more quantum algorithms for number-theoretic and group-theoretic problems. Grover's algorithm has developed into the area of quantum query algorithms.I will survey the developments in quantum query algorithms. The topics will include: applications of Grover's algorithm to element distinctness and other problems, lower bounds on quantum algorithms and the use of quantum random walks to design better search algorithm. I will also describe how some of techniques in this area can be used as "quantum black boxes" in an otherwise classical algorithm.

ACM Symposium on Theory of Computing (STOC)•Jun 13, 2004•1 citation

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

Introduction to quantum algorithms

Peter W. Shor

These notes discuss the quantum algorithms we know of that can solve problems significantly faster than the corresponding classical algorithms.So far, we have only discovered a few techniques which can produce speed up versus classical algorithms.It is not clear yet whether the reason for this is that we do not have enough intuition to discover more techniques, or that there are only a few problems for which quantum computers can significantly speed up the solution.In the first section of these notes, I try to explain why the recent results about quantum computing have been so surprising.This section comes from a talk I have been giving for several years now, and discusses the history of quantum computing and its relation to the mathematical foundations of computer science.In Sections 2 and 3, I talk about the quantum computing model and its relationship to physics.These sections rely heavily on two of my papers [SIAM J. Comp.26 (1997), 1484-1509; Doc.Math.Extra Vol.ICM I (1998), 467-486].Sections 4 and 5 illustrate the general technique of using quantum Fourier transforms to find periodicity.Section 4 contains an algorithm of Dan Simon showing that quantum computers are likely to be exponentially faster than classical computers for some problems.Section 5 discusses my factoring algorithm, which was inspired in part by Dan Simon's paper.In the final section, I discuss Lov Grover's search algorithm, which illustrates a different technique for speeding up classical algorithms.These techniques for constructing faster algorithms for classical problems on quantum computers are the only two significant ones which have been discovered so far.

Proceedings of symposia in applied mathematics•Jan 1, 2002•56 citations

Quantum Search Algorithm

The quantum search algorithm was discovered by L. K. Grover in 1997, and is called Grover’s algorithm after his name. Let us consider how to find elements marked by a certain symbol out of a database consisting of N elements (say, multi-million elements). This problem is similar to how to find the name of the person from a telephone book knowing only his/her telephone number. This search takes by far more time than finding the phone number from the name of the person. The difference comes from the structure of the telephone book. In the telephone book, the names are arranged in the alphabetical order and constitute the structured database, while phone numbers do not form any structure in the telephone book. In classical computers, when we search one target element from the database with N elements, we need N/ 2 trials on average. Grover showed using the quantum search algorithm that N trials will be enough on average to find the target element from the database with N elements. Shor’s quantum computation algorithm was an epoch-making algorithm which made possible to solve the factorization problem in polynomial time, while the classical computers need exponentially increasing time to solve it. In comparison, Grover’s algorithm makes the data search possible by O ( N ) computation time, while it takes O ( N ) computation time by the classical computers. Concerning the reduction of computing time, Grover’s algorithm may look less powerful than Shor’s algorithm. However, it has good potentiality of application in the wide area such as NP-complete problems and structured databases.

WORLD SCIENTIFIC eBooks•Sep 24, 2020•0 citations

Exploring the Evolution of Quantum Computing: A Comparative Study of Grover’s Algorithm and Conventional Binary Search

Wheeler S, N Putta, Jakka VR

The focus of this literature review is to examine the foundational principles and current advancements in the field of quantum computing, showcasing its potential to address challenges faced by traditional systems. This study concentrates on key concepts like superposition and entanglement, leading to an exploration of various quantum algorithms, such as Grover’s algorithm and Shor’s algorithm. By comparing Grover’s Search algorithm with binary search, the study aims to demonstrate quantum computing’s advantages in terms of efficiency and speed, especially for large datasets and unsorted databases. The comparison reveals the current state of quantum hardware and its limitations. Despite the challenges associated with hardware requirements, IBM has developed a quantum machine with a 456- qubit quantum processor, marking a milestone and showcasing rapid evolution in this field. Insights gained from this comparison include the potential for algorithms to handle scaled datasets, various applications in data science, and the capability to solve complex problems.

Open Access Journal of Data Science and Artificial Intelligence•Jan 1, 2024•0 citations
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.
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 1994, Peter Shor discovered a polynomial time quantum algorithm for factoring and discrete logarithm. Two years later, in 1996, Lov Grover discovered a search algorithm which is quadratically better than conventional search. By now, each of the two algorithms has developed into a line of research which goes well beyond the original algorithm. Shor's algorithm has inspired the study of quantum Fourier sampling which has resulted in more quantum algorithms for number-theoretic and group-theoretic problems. Grover's algorithm has developed into the area of quantum query algorithms.I will survey the developments in quantum query algorithms. The topics will include: applications of Grover's algorithm to element distinctness and other problems, lower bounds on quantum algorithms and the use of quantum random walks to design better search algorithm. I will also describe how some of techniques in this area can be used as "quantum black boxes" in an otherwise classical algorithm.
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.
These notes discuss the quantum algorithms we know of that can solve problems significantly faster than the corresponding classical algorithms.So far, we have only discovered a few techniques which can produce speed up versus classical algorithms.It is not clear yet whether the reason for this is that we do not have enough intuition to discover more techniques, or that there are only a few problems for which quantum computers can significantly speed up the solution.In the first section of these notes, I try to explain why the recent results about quantum computing have been so surprising.This section comes from a talk I have been giving for several years now, and discusses the history of quantum computing and its relation to the mathematical foundations of computer science.In Sections 2 and 3, I talk about the quantum computing model and its relationship to physics.These sections rely heavily on two of my papers [SIAM J. Comp.26 (1997), 1484-1509; Doc.Math.Extra Vol.ICM I (1998), 467-486].Sections 4 and 5 illustrate the general technique of using quantum Fourier transforms to find periodicity.Section 4 contains an algorithm of Dan Simon showing that quantum computers are likely to be exponentially faster than classical computers for some problems.Section 5 discusses my factoring algorithm, which was inspired in part by Dan Simon's paper.In the final section, I discuss Lov Grover's search algorithm, which illustrates a different technique for speeding up classical algorithms.These techniques for constructing faster algorithms for classical problems on quantum computers are the only two significant ones which have been discovered so far.
The quantum search algorithm was discovered by L. K. Grover in 1997, and is called Grover’s algorithm after his name. Let us consider how to find elements marked by a certain symbol out of a database consisting of N elements (say, multi-million elements). This problem is similar to how to find the name of the person from a telephone book knowing only his/her telephone number. This search takes by far more time than finding the phone number from the name of the person. The difference comes from the structure of the telephone book. In the telephone book, the names are arranged in the alphabetical order and constitute the structured database, while phone numbers do not form any structure in the telephone book. In classical computers, when we search one target element from the database with N elements, we need N/ 2 trials on average. Grover showed using the quantum search algorithm that N trials will be enough on average to find the target element from the database with N elements. Shor’s quantum computation algorithm was an epoch-making algorithm which made possible to solve the factorization problem in polynomial time, while the classical computers need exponentially increasing time to solve it. In comparison, Grover’s algorithm makes the data search possible by O ( N ) computation time, while it takes O ( N ) computation time by the classical computers. Concerning the reduction of computing time, Grover’s algorithm may look less powerful than Shor’s algorithm. However, it has good potentiality of application in the wide area such as NP-complete problems and structured databases.
The focus of this literature review is to examine the foundational principles and current advancements in the field of quantum computing, showcasing its potential to address challenges faced by traditional systems. This study concentrates on key concepts like superposition and entanglement, leading to an exploration of various quantum algorithms, such as Grover’s algorithm and Shor’s algorithm. By comparing Grover’s Search algorithm with binary search, the study aims to demonstrate quantum computing’s advantages in terms of efficiency and speed, especially for large datasets and unsorted databases. The comparison reveals the current state of quantum hardware and its limitations. Despite the challenges associated with hardware requirements, IBM has developed a quantum machine with a 456- qubit quantum processor, marking a milestone and showcasing rapid evolution in this field. Insights gained from this comparison include the potential for algorithms to handle scaled datasets, various applications in data science, and the capability to solve complex problems.