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

Birkhäuser Boston eBooks

An Introduction to Quantum Computing Algorithms

A. O. Pittenger

Published Jan 1, 2000• 148 citations
Publisher

Abstract

In 1994 Peter Shor [65] published a factoring algorithm for a quantum computer that finds the prime factors of a composite integer N more efficiently than is possible with the known algorithms for a classical com­ puter. Since the difficulty of the factoring problem is crucial for the se­ curity of a public key encryption system, interest (and funding) in quan­ tum computing and quantum computation suddenly blossomed. Quan­ tum computing had arrived. The study of the role of quantum mechanics in the theory of computa­ tion seems to have begun in the early 1980s with the publications of Paul Benioff [6]' [7] who considered a quantum mechanical model of computers and the computation process. A related question was discussed shortly thereafter by Richard Feynman [35] who began from a different perspec­ tive by asking what kind of computer should be used to simulate physics. His analysis led him to the belief that with a suitable class of "quantum machines" one could imitate any quantum system.

DOI
10.1007/978-1-4612-1390-1

Related papers

An introduction to quantum computing for non-physicists

Eleanor Gilbert Rieffel, Wolfgang Polak

Richard Feynman's observation that certain quantum mechanical effects cannot be simulated efficiently on a computer led to speculation that computation in general could be done more efficiently if it used these quantum effects. This speculation proved justified when Peter Shor described a polynomial time quantum algorithm for factoring intergers. In quantum systems, the computational space increases exponentially with the size of the system, which enables exponential parallelism. This parallelism could lead to exponentially faster quantum algorithms than possible classically. The catch is that accessing the results, which requires measurement, proves tricky and requires new nontraditional programming techniques. The aim of this paper is to guide computer scientists through the barriers that separate quantum computing from conventional computing. We introduce basic principles of quantum mechanics to explain where the power of quantum computers comes from and why it is difficult to harness. We describe quantum cryptography, teleportation, and dense coding. Various approaches to exploiting the power of quantum parallelism are explained. We conclude with a discussion of quantum error correction.

arXiv:quant-ph/9809016•ACM Computing Surveys•Sep 1, 2000•476 citations

Quantum Computing

Susan Loepp, William K. Wootters

In an ordinary computer, information is stored in a collection of tiny circuits each of which is designed to have two stable and easily distinguishable configurations: each represents a bit. In our study of quantum cryptography, we have seen how it can be useful to express information not in ordinary bits but in qubits. Whereas a bit can have only two values, say 0 and 1, a qubit can be in any quantum superposition of ∣0〉 and ∣1〉. Moreover, a qubit can be entangled with other qubits. Thus one might wonder whether a quantum computer, in which the basic elements for storing and processing information are qubits, can outperform an ordinary (classical) computer in certain ways. This question was addressed by researchers starting in the 1980s. In terms of practical consequences, perhaps the most dramatic answer has been given by Peter Shor in his 1994 factoring algorithm for a quantum computer, an algorithm that is exponentially faster than any known classical algorithm. As we have seen in Chapter 1, the difficulty of factoring a product of two large primes is the basis of the security of the RSA cryptosystem. So if one could build a large enough quantum computer – and there is no reason in principle why this could not be done – the RSA system would be rendered ineffective. In this chapter we present the basics of quantum computation and then focus on Shor's factoring algorithm.

Cambridge University Press eBooks•Jul 10, 2006•0 citations

Quantum Complexity

Stefan Heinrich

A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.

Cambridge University Press eBooks•Mar 25, 2004•2 citations

A critical overview on Quantum Computing

Saptarshi Sahoo, Amit Kumar Mandal, Pijus Kanti Samanta +2 more

Quantum Computing and Quantum Information Science seem very promising and developing rapidly since its inception in early 1980s by Paul Benioff with the proposal of quantum mechanical model of the Turing machine and later By Richard Feynman and Yuri Manin for the proposal of a quantum computers for simulating various problems that classical computer could not. Quantum computers have a computational advantage for some problems, over classical computers and most applications are trying to use an efficient combination of classical and quantum computers like Shor’s factoring algorithm. Other areas that are expected to be benefitted from quantum computing are Machine Learning and deep learning, molecular biology, genomics and cancer research, space exploration, atomic and nuclear research and macro-economic forecasting. This paper represents a brief overview of the state of art of quantum computing and quantum information science with discussions of various theoretical and experimental aspects adopted by the researchers.

Journal of quantum computing•Jan 1, 2020•18 citations

Fundamental Structure of Shor’s Quantum Algorithm for Factoring Integers

Turgut Hanoymak, Akram Chehrazi

One of the most well known mathematically hard problems in number theory is the integer factorization problem, roughly stated that decomposition of a composite number into its prime factors. In modern cryptography, RSA encryption algorithm whose security is based on integer factorization problem is highly practical, widespread and up to date no classical algorithm having polynomial running time for the factorization of large numbers is known. In 1994, Peter Shor proposed an efficient algorithm on quantum computer. In this paper, we  mention about the fundamentals of  Shor's quantum algorithm illustrating a concrete example.

Turkish Journal of Mathematics and Computer Science•Dec 31, 2019•0 citations

Guest Column: Quantum Finite Automata: From Theory to Practice

Carlo Mereghetti, Beatrice Palano

Quantum computing is a prolific research area, halfway between physics and computer science [27, 29, 52]. Most likely, its origins may be dated back to 70's, when some works on quantum information began to appear (see, e.g., [34, 37]). In early 80's, R.P. Feynman suggested that the computational power of quantum mechanical processes might be beyond that of traditional computation models [25]. Almost at the same time, P. Benioff already proved that such processes are at least as powerful as Turing machines [9]. In 1985, D. Deutsch [22] proposed the notion of a quantum Turing machine as a physically realizable model for a quantum computer. From the point of view of structural complexity, E. Bernstein and U. Vazirani introduced in [20] the class BQP of problems solvable in polynomial time on quantum Turing machines, focusing attention on relations with the corresponding deterministic and probabilistic classes P and BPP, respectively. Several works in the literature explored classical issues in complexity theory from the quantum paradigm perspective (see, e.g., [7, 60, 61]).

ACM SIGACT News•Oct 17, 2021•4 citations
In 1994 Peter Shor [65] published a factoring algorithm for a quantum computer that finds the prime factors of a composite integer N more efficiently than is possible with the known algorithms for a classical com­ puter. Since the difficulty of the factoring problem is crucial for the se­ curity of a public key encryption system, interest (and funding) in quan­ tum computing and quantum computation suddenly blossomed. Quan­ tum computing had arrived. The study of the role of quantum mechanics in the theory of computa­ tion seems to have begun in the early 1980s with the publications of Paul Benioff [6]' [7] who considered a quantum mechanical model of computers and the computation process. A related question was discussed shortly thereafter by Richard Feynman [35] who began from a different perspec­ tive by asking what kind of computer should be used to simulate physics. His analysis led him to the belief that with a suitable class of "quantum machines" one could imitate any quantum system.
Richard Feynman's observation that certain quantum mechanical effects cannot be simulated efficiently on a computer led to speculation that computation in general could be done more efficiently if it used these quantum effects. This speculation proved justified when Peter Shor described a polynomial time quantum algorithm for factoring intergers. In quantum systems, the computational space increases exponentially with the size of the system, which enables exponential parallelism. This parallelism could lead to exponentially faster quantum algorithms than possible classically. The catch is that accessing the results, which requires measurement, proves tricky and requires new nontraditional programming techniques. The aim of this paper is to guide computer scientists through the barriers that separate quantum computing from conventional computing. We introduce basic principles of quantum mechanics to explain where the power of quantum computers comes from and why it is difficult to harness. We describe quantum cryptography, teleportation, and dense coding. Various approaches to exploiting the power of quantum parallelism are explained. We conclude with a discussion of quantum error correction.
In an ordinary computer, information is stored in a collection of tiny circuits each of which is designed to have two stable and easily distinguishable configurations: each represents a bit. In our study of quantum cryptography, we have seen how it can be useful to express information not in ordinary bits but in qubits. Whereas a bit can have only two values, say 0 and 1, a qubit can be in any quantum superposition of ∣0〉 and ∣1〉. Moreover, a qubit can be entangled with other qubits. Thus one might wonder whether a quantum computer, in which the basic elements for storing and processing information are qubits, can outperform an ordinary (classical) computer in certain ways. This question was addressed by researchers starting in the 1980s. In terms of practical consequences, perhaps the most dramatic answer has been given by Peter Shor in his 1994 factoring algorithm for a quantum computer, an algorithm that is exponentially faster than any known classical algorithm. As we have seen in Chapter 1, the difficulty of factoring a product of two large primes is the basis of the security of the RSA cryptosystem. So if one could build a large enough quantum computer – and there is no reason in principle why this could not be done – the RSA system would be rendered ineffective. In this chapter we present the basics of quantum computation and then focus on Shor's factoring algorithm.
A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.
Quantum Computing and Quantum Information Science seem very promising and developing rapidly since its inception in early 1980s by Paul Benioff with the proposal of quantum mechanical model of the Turing machine and later By Richard Feynman and Yuri Manin for the proposal of a quantum computers for simulating various problems that classical computer could not. Quantum computers have a computational advantage for some problems, over classical computers and most applications are trying to use an efficient combination of classical and quantum computers like Shor’s factoring algorithm. Other areas that are expected to be benefitted from quantum computing are Machine Learning and deep learning, molecular biology, genomics and cancer research, space exploration, atomic and nuclear research and macro-economic forecasting. This paper represents a brief overview of the state of art of quantum computing and quantum information science with discussions of various theoretical and experimental aspects adopted by the researchers.
One of the most well known mathematically hard problems in number theory is the integer factorization problem, roughly stated that decomposition of a composite number into its prime factors. In modern cryptography, RSA encryption algorithm whose security is based on integer factorization problem is highly practical, widespread and up to date no classical algorithm having polynomial running time for the factorization of large numbers is known. In 1994, Peter Shor proposed an efficient algorithm on quantum computer. In this paper, we  mention about the fundamentals of  Shor's quantum algorithm illustrating a concrete example.
Quantum computing is a prolific research area, halfway between physics and computer science [27, 29, 52]. Most likely, its origins may be dated back to 70's, when some works on quantum information began to appear (see, e.g., [34, 37]). In early 80's, R.P. Feynman suggested that the computational power of quantum mechanical processes might be beyond that of traditional computation models [25]. Almost at the same time, P. Benioff already proved that such processes are at least as powerful as Turing machines [9]. In 1985, D. Deutsch [22] proposed the notion of a quantum Turing machine as a physically realizable model for a quantum computer. From the point of view of structural complexity, E. Bernstein and U. Vazirani introduced in [20] the class BQP of problems solvable in polynomial time on quantum Turing machines, focusing attention on relations with the corresponding deterministic and probabilistic classes P and BPP, respectively. Several works in the literature explored classical issues in complexity theory from the quantum paradigm perspective (see, e.g., [7, 60, 61]).