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/9903008

Classical computing, quantum computing, and Shor's factoring algorithm

Yuri I. Manin

Published Mar 2, 1999• 95 citations
arXivHTMLPDF

Abstract

This is an expository talk written for the Bourbaki Seminar. After a brief introduction, Section 1 discusses in the categorical language the structure of the classical deterministic computations. Basic notions of complexity icluding the P/NP problem are reviewed. Section 2 introduces the notion of quantum parallelism and explains the main issues of quantum computing. Section 3 is devoted to four quantum subroutines: initialization, quantum computing of classical Boolean functions, quantum Fourier transform, and Grover's search algorithm. The central Section 4 explains Shor's factoring algorithm. Section 5 relates Kolmogorov's complexity to the spectral properties of computable function. Appendix contributes to the prehistory of quantum computing.

DOI
10.48550/arxiv.quant-ph/9903008

Related papers

QUANTUM COMPUTATION

Dorit Aharonov

In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.

arXiv:quant-ph/9812037•WORLD SCIENTIFIC eBooks•Mar 1, 1999•139 citations

Quantum computing: an introduction

Tony Hey

The basic ideas of quantum computation are introduced by a brief discussion of Bennett (1973, 1982) and Fredkin's (1982, 1997) ideas of reversible computation. After some remarks about Deutsch's (1985) pioneering work on quantum complexity and Shor's (1996) factorisation algorithm, quantum logic gates, qubits and registers are discussed. The role of quantum entanglement is stressed and Grover's (1997) quantum search algorithm described in detail. The paper ends with a review of the current experimental status of quantum computers.

Computing & Control Engineering Journal•Jun 1, 1999•276 citations

An Introduction to Quantum Algorithms

Bhupendra Singh, Mohankumar Mylsamy, Thamaraimanalan Thangarajan

“An Introduction to Quantum Algorithms” provides an introduction to quantum algorithms, starting with the fundamentals of quantum computing. It covers the basics of quantum mechanics, the potential for quantum speedup, and the challenges and limitations of quantum computing. The chapter also highlights the key differences between classical and quantum computing, focusing on concepts such as bits and qubits, quantum measurement, superposition, and qubit properties, with a detailed explanation of qubit states on the Bloch sphere. Additionally, it explores quantum gates and algorithms, including single-qubit and multiple-qubit gates, the Quantum Fourier Transform (QFT), and important quantum algorithms such as Shor's algorithm for factoring, Grover's algorithm for searching, and Simon's algorithm for collision finding.

CRC Press eBooks•Nov 14, 2025•0 citations

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

Basics for Algorithms in Quantum Computing

Guillermo B. Morales-Luna

A short introduction to Quantum Computing, regarded as a paradigm of “parallel computing based on exterior algebras”, is presented from the point of view of its main algorithms including the primitive functions, the compositional schemes and the input and output data coding. In this study the Exterior Algebra notation is used in lieu of the more conventional Dirac’s ket notation. The basic notions of Exterior Algebra and Hilbert Spaces are sketched in order to show the qubits as points in the unit circle in the two‐dimensional complex Hilbert space H1, and any word consisting of qubits as a point in the unit sphere of a external product of H1. The computing procedure is illustrated through the classical Deutsch‐Josza’s algorithm, followed by the quantum algorithm to compute the Discrete Fourier Transform in linear time and the famous polynomial‐time Shor’s Algorithm for integer factorization. Finally, basic notions in Quantum Cryptography and Quantum Communication Complexity are discussed.

AIP conference proceedings•Jan 1, 2006•0 citations

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 is an expository talk written for the Bourbaki Seminar. After a brief introduction, Section 1 discusses in the categorical language the structure of the classical deterministic computations. Basic notions of complexity icluding the P/NP problem are reviewed. Section 2 introduces the notion of quantum parallelism and explains the main issues of quantum computing. Section 3 is devoted to four quantum subroutines: initialization, quantum computing of classical Boolean functions, quantum Fourier transform, and Grover's search algorithm. The central Section 4 explains Shor's factoring algorithm. Section 5 relates Kolmogorov's complexity to the spectral properties of computable function. Appendix contributes to the prehistory of quantum computing.
In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.
The basic ideas of quantum computation are introduced by a brief discussion of Bennett (1973, 1982) and Fredkin's (1982, 1997) ideas of reversible computation. After some remarks about Deutsch's (1985) pioneering work on quantum complexity and Shor's (1996) factorisation algorithm, quantum logic gates, qubits and registers are discussed. The role of quantum entanglement is stressed and Grover's (1997) quantum search algorithm described in detail. The paper ends with a review of the current experimental status of quantum computers.
“An Introduction to Quantum Algorithms” provides an introduction to quantum algorithms, starting with the fundamentals of quantum computing. It covers the basics of quantum mechanics, the potential for quantum speedup, and the challenges and limitations of quantum computing. The chapter also highlights the key differences between classical and quantum computing, focusing on concepts such as bits and qubits, quantum measurement, superposition, and qubit properties, with a detailed explanation of qubit states on the Bloch sphere. Additionally, it explores quantum gates and algorithms, including single-qubit and multiple-qubit gates, the Quantum Fourier Transform (QFT), and important quantum algorithms such as Shor's algorithm for factoring, Grover's algorithm for searching, and Simon's algorithm for collision finding.
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.
A short introduction to Quantum Computing, regarded as a paradigm of “parallel computing based on exterior algebras”, is presented from the point of view of its main algorithms including the primitive functions, the compositional schemes and the input and output data coding. In this study the Exterior Algebra notation is used in lieu of the more conventional Dirac’s ket notation. The basic notions of Exterior Algebra and Hilbert Spaces are sketched in order to show the qubits as points in the unit circle in the two‐dimensional complex Hilbert space H1, and any word consisting of qubits as a point in the unit sphere of a external product of H1. The computing procedure is illustrated through the classical Deutsch‐Josza’s algorithm, followed by the quantum algorithm to compute the Discrete Fourier Transform in linear time and the famous polynomial‐time Shor’s Algorithm for integer factorization. Finally, basic notions in Quantum Cryptography and Quantum Communication Complexity are discussed.
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