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• 78 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

Quantum algorithms know in advance 50 % of the solution they will find in the future

Quantum algorithms require less operations than classical algorithms. The exact reason of this has not been pinpointed until now. Our explanation is that quantum algorithms know in advance 50 % of the solution of the problem they will find in the future. In fact they can be represented as the sum of all the possible histories of a respective ”advanced information classical algorithm”. This algorithm, given the advanced information (50 % of the bits encoding the problem solution), performs the operations (oracle’s queries) still required to identify the solution. Each history corresponds to a possible way of getting the advanced information and a possible result of computing the missing information. This explanation of the quantum speed up has an immediate practical consequence: the speed up comes from comparing two classical algorithms, with and without advanced information, with no physics involved. This simplification could open the way to a systematic exploration of the possibilities of speed up. 1

•Jan 1, 2009•1 citation

Quantum computing

Siddhartha Kasivajhula

Computers today become faster by becoming smaller. By reducing the size of transistors, engineers are able to fit more of them on a given size microprocessor, thus increasing the processor's computational power. This process cannot continue forever. It has been estimated that sometime within the next two decades, at the current rate, engineers will be faced with the problem of building something that is smaller than an atom. This is as far as our current "classical" computing paradigm will take us. Quantum computing is a potential solution to this problem. This paradigm of computing seeks to directly exploit quantum mechanical phenomena to perform calculations or in some way boost computational efficiency. Some problems can theoretically be solved on a quantum computer exponentially faster than on a classical computer. An overview of the subject is provided here with emphasis on quantum information processing and physical realizations of a quantum computer. Included is a brief history of the subject, a discussion of quantum computing notions such as parallelism and entanglement and their use in quantum algorithms, and conjecture on the prospects and pitfalls of this theory.

ACM Southeast Regional Conference (ACMSE)•Mar 10, 2006•9 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•344 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•9 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.
Quantum algorithms require less operations than classical algorithms. The exact reason of this has not been pinpointed until now. Our explanation is that quantum algorithms know in advance 50 % of the solution of the problem they will find in the future. In fact they can be represented as the sum of all the possible histories of a respective ”advanced information classical algorithm”. This algorithm, given the advanced information (50 % of the bits encoding the problem solution), performs the operations (oracle’s queries) still required to identify the solution. Each history corresponds to a possible way of getting the advanced information and a possible result of computing the missing information. This explanation of the quantum speed up has an immediate practical consequence: the speed up comes from comparing two classical algorithms, with and without advanced information, with no physics involved. This simplification could open the way to a systematic exploration of the possibilities of speed up. 1
Computers today become faster by becoming smaller. By reducing the size of transistors, engineers are able to fit more of them on a given size microprocessor, thus increasing the processor's computational power. This process cannot continue forever. It has been estimated that sometime within the next two decades, at the current rate, engineers will be faced with the problem of building something that is smaller than an atom. This is as far as our current "classical" computing paradigm will take us. Quantum computing is a potential solution to this problem. This paradigm of computing seeks to directly exploit quantum mechanical phenomena to perform calculations or in some way boost computational efficiency. Some problems can theoretically be solved on a quantum computer exponentially faster than on a classical computer. An overview of the subject is provided here with emphasis on quantum information processing and physical realizations of a quantum computer. Included is a brief history of the subject, a discussion of quantum computing notions such as parallelism and entanglement and their use in quantum algorithms, and conjecture on the prospects and pitfalls of this theory.
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.