Shor's algorithm | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (that is, non-quantum) algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future. Another concern is that noise in quantum circuits may undermine results, requiring additional qubits for quantum error correction. Shor proposed multiple similar algorithms solving the factoring problem, the discrete logarithm problem, and the period finding problem. "Shor's algorithm" usually refers to his algorithm solving factoring, but may also refer to each of the three. The discrete logarithm algorithm and the factoring algorithm are instances of the period finding algorithm, and all three are instances of the hidden subgroup problem. Shor's algorithm allows to factor an integer on a quantum computer in polylogarithmic time, meaning that the running time of the algorithm is polynomial in . Specifically, it takes quantum gates of order using fast multiplication, or even utilizing the asymptotically fastest multiplication algorithm currently known due to Harvey and Van Der Hoven, thus demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is consequently in the complexity class BQP. This is significantly faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time: . If a quantum computer with a sufficient number of qubits could operate without succumbing to quantum noise and other quantum-decoherence phenomena, then Shor's algorithm could be used to break public-key cryptography schemes, such as The RSA scheme The Finite Field Diffie-Hellman key exchange The Elliptic Curve Diffie-Hellman key exchange RSA is based on the assumption that factoring large integers is computationally intractable.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (31)

Related courses (14)

Related lectures (261)

COM-309: Introduction to quantum information processing

Information is processed in physical devices. In the quantum regime the concept of classical bit is replaced by the quantum bit. We introduce quantum principles, and then quantum communications, key d

COM-611: Quantum Information Theory and Computation

Today one is able to manipulate matter at the nanoscale were quantum behavior becomes important and possibly information processing will have to take into account laws of quantum physics. We introduce

CS-308: Introduction to quantum computation

The course introduces the paradigm of quantum computation in an axiomatic way. We introduce the notion of quantum bit, gates, circuits and we treat the most important quantum algorithms. We also touch

Shor's algorithm

Quantum logic gate

In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate (or simply quantum gate) is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits. Unlike many classical logic gates, quantum logic gates are reversible. It is possible to perform classical computing using only reversible gates.

Discrete logarithm

In mathematics, for given real numbers a and b, the logarithm logb a is a number x such that bx = a. Analogously, in any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a is an integer k such that bk = a. In number theory, the more commonly used term is index: we can write x = indr a (mod m) (read "the index of a to the base r modulo m") for rx ≡ a (mod m) if r is a primitive root of m and gcd(a,m) = 1. Discrete logarithms are quickly computable in a few special cases.

Trapped Ions: Quantum Gates PHYS-454: Quantum optics and quantum information

Covers the fundamentals of trapped ions in quantum information and the importance of geometric phases in quantum optics.

Quantum Random Number Generation PHYS-758: Advanced Course on Quantum Communication

Explores quantum random number generation, discussing the challenges and implementations of generating good randomness using quantum devices.

Quantum Algorithms: Shor Algorithm CS-308: Introduction to quantum computation

Covers the analysis of measurements in the context of the Shor algorithm.