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

arXiv:quant-ph/0005003

Introduction to Quantum Algorithms

Peter W. Shor

Published Apr 29, 2000• 100 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/0005003

Related papers

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 algorithms for algebraic problems

Andrew M. Childs, Wim van Dam

Quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup over classical computation and, in particular, on problems with an algebraic flavor.

arXiv:0812.0380•Reviews of Modern Physics•Jan 15, 2010•379 citations

Evolving quantum computer algorithms

Lee C. Spector

Computer science will be radically transformed if ongoing efforts to build large-scale quantum computers eventually succeed and if the properties of these computers meet optimistic expectations. Nevertheless, computer scientists still lack a thorough understanding of the power of quantum computing, and it is not always clear how best to utilize the power that is understood. This dilemma exists because quantum algorithms are difficult to grasp and even more difficult to write. Despite large-scale international efforts, only a few important quantum algorithms are documented, leaving many essential questions about the potential of quantum algorithms unanswered. These unsolved problems are ideal challenges for the application of automatic programming technologies. Genetic programming techniques, in particular, have already produced several new quantum algorithms and it is reasonable to expect further discoveries in the future. These methods will help researchers to discover how additional practical problems can be solved using quantum computers, and they will also help to guide theoretical work on both the power and limits of quantum computing. This tutorial will provide an introduction to quantum computing and an introduction to the use of evolutionary computation for automatic quantum computer programming. No background in physics or in evolutionary computation will be assumed. While the primary focus of the tutorial will be on general concepts, specific results will also be presented, including human-competitive results produced by genetic programming. Follow-up material is available from the presenter's book, Automatic Quantum Computer Programming: A Genetic Programming Approach, published by Springer and Kluwer Academic Publishers.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 8, 2009•0 citations

Quantum algorithms

Bilha Segev

I review a few of the most famous quantum algorithms, and discuss them from a practical perspective. What should a quantum system be able to do, in principle, to qualify as a quantum computer for which these algorithms work? The role of superposition, parallelism, and entanglement is discussed.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Jul 31, 2002•0 citations

Comparative Study between Quantum and Classical Methods: Few Observations from Portfolio Optimization Problem

Saswati Soumya Tripathy, Neerja Koul, Hemil Patel

Classical computers have a limitation in solving NP-hard (nondeterministic polynomial) problems, which cannot be solved in polynomial time. However, the Quantum Computing paradigm is inherently capable of solving such types of problems. One of the major milestones inclined to a quantum -ready era is a relative comparison of execution speed and overall efficiency of current classical versus quantum models. In our approach, we are initiating the foremost step towards addressing the above milestone by performing a comparative study between quantum optimization techniques (available on both gate-model as well as quantum annealers) versus classical by solving a finance domain problem, that is, portfolio optimization using Markowitz mean-variance optimization. Historical market data from Jan’2011 till Dec’2016 of 48 NSE stocks were considered to build the portfolio by optimizing the mean-variance based on Harry Markowitz’s Modern Portfolio Theory. We approach this first classically and then on gate-model based quantum computer using Qiskit SDK, followed by D-wave solvers to build efficient portfolio and compare which among these frameworks are mature enough in this NISQ era to solve portfolio optimization problem related to the finance domain. Our results are comparable and from our experimentation performed on D-wave annealers and gate-model simulators, we observed that implementations using quantum methods were faster than the corresponding implementation of classical methods.

International Conference on Trends in Quantum Computing and Emerging Business Technologies (TQCEBT)•Oct 13, 2022•12 citations

Why haven't more quantum algorithms been found?

Peter W. Shor

I examine the question of why so few classes of quantum algorithms have been discovered. I give two possible explanations for this, and some thoughts about what lines of research might lead to the discovery of more quantum algorithms.

Journal of the ACM•Jan 1, 2003•97 citations
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.
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.
Quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup over classical computation and, in particular, on problems with an algebraic flavor.
Computer science will be radically transformed if ongoing efforts to build large-scale quantum computers eventually succeed and if the properties of these computers meet optimistic expectations. Nevertheless, computer scientists still lack a thorough understanding of the power of quantum computing, and it is not always clear how best to utilize the power that is understood. This dilemma exists because quantum algorithms are difficult to grasp and even more difficult to write. Despite large-scale international efforts, only a few important quantum algorithms are documented, leaving many essential questions about the potential of quantum algorithms unanswered. These unsolved problems are ideal challenges for the application of automatic programming technologies. Genetic programming techniques, in particular, have already produced several new quantum algorithms and it is reasonable to expect further discoveries in the future. These methods will help researchers to discover how additional practical problems can be solved using quantum computers, and they will also help to guide theoretical work on both the power and limits of quantum computing. This tutorial will provide an introduction to quantum computing and an introduction to the use of evolutionary computation for automatic quantum computer programming. No background in physics or in evolutionary computation will be assumed. While the primary focus of the tutorial will be on general concepts, specific results will also be presented, including human-competitive results produced by genetic programming. Follow-up material is available from the presenter's book, Automatic Quantum Computer Programming: A Genetic Programming Approach, published by Springer and Kluwer Academic Publishers.
Classical computers have a limitation in solving NP-hard (nondeterministic polynomial) problems, which cannot be solved in polynomial time. However, the Quantum Computing paradigm is inherently capable of solving such types of problems. One of the major milestones inclined to a quantum -ready era is a relative comparison of execution speed and overall efficiency of current classical versus quantum models. In our approach, we are initiating the foremost step towards addressing the above milestone by performing a comparative study between quantum optimization techniques (available on both gate-model as well as quantum annealers) versus classical by solving a finance domain problem, that is, portfolio optimization using Markowitz mean-variance optimization. Historical market data from Jan’2011 till Dec’2016 of 48 NSE stocks were considered to build the portfolio by optimizing the mean-variance based on Harry Markowitz’s Modern Portfolio Theory. We approach this first classically and then on gate-model based quantum computer using Qiskit SDK, followed by D-wave solvers to build efficient portfolio and compare which among these frameworks are mature enough in this NISQ era to solve portfolio optimization problem related to the finance domain. Our results are comparable and from our experimentation performed on D-wave annealers and gate-model simulators, we observed that implementations using quantum methods were faster than the corresponding implementation of classical methods.