Shor's algorithm is a
quantum computer algorithm for finding the
prime factor
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s of an integer. It was developed in 1994 by the American mathematician
Peter Shor
Peter Williston Shor (born August 14, 1959) is an American professor of applied mathematics at MIT. He is known for his work on quantum computation, in particular for devising Shor's algorithm, a quantum algorithm for factoring exponentially fa ...
.
On a quantum computer, to factor an integer
, Shor's algorithm runs in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
, meaning the time taken is polynomial in
, the size of the integer given as input. 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
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.
When the numbers are suf ...
problem can be efficiently solved on a quantum computer and is consequently in the
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
BQP. This is almost exponentially faster than the most efficient known classical factoring algorithm, the
general number field sieve
In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form
:\exp\left( ...
, which works in
sub-exponential time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
:
. The efficiency of Shor's algorithm is due to the efficiency of the
quantum Fourier transform
In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's ...
, and
modular exponentiation
Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie-Hellman Key Exchange and RSA public/private keys.
Modular ...
by
repeated squarings.
If a quantum computer with a sufficient number of
qubit
In quantum computing, a qubit () or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, ...
s could operate without succumbing to
quantum noise
Quantum noise is noise arising from the indeterminate state of matter in accordance with fundamental principles of quantum mechanics, specifically the uncertainty principle and via zero-point energy fluctuations. Quantum noise is due to the appa ...
and other
quantum-decoherence phenomena, then Shor's algorithm could be used to break
public-key cryptography
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
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. As far as is known, this assumption is valid for classical (non-quantum) computers; no classical algorithm is known that can factor integers in polynomial time. However, Shor's algorithm shows that factoring integers is efficient on an ideal quantum computer, so it may be feasible to defeat RSA by constructing a large quantum computer. It was also a powerful motivator for the design and construction of quantum computers, and for the study of new quantum-computer algorithms. It has also facilitated research on new cryptosystems that are secure from quantum computers, collectively called
post-quantum cryptography
In cryptography, post-quantum cryptography (sometimes referred to as quantum-proof, quantum-safe or quantum-resistant) refers to cryptographic algorithms (usually public-key algorithms) that are thought to be secure against a cryptanalytic attack b ...
.
In 2001, Shor's algorithm was demonstrated by a group at
IBM, who factored
into
, using an
NMR implementation of a quantum computer with
qubits.
After IBM's implementation, two independent groups implemented Shor's algorithm using
photonic
Photonics is a branch of optics that involves the application of generation, detection, and manipulation of light in form of photons through emission, transmission, modulation, signal processing, switching, amplification, and sensing. Though ...
qubits, emphasizing that multi-qubit
entanglement was observed when running the Shor's algorithm circuits.
In 2012, the factorization of
was performed with solid-state qubits. Later, in 2012, the factorization of
was achieved. In 2019 an attempt was made to factor the number
using Shor's algorithm on an IBM
Q System One, but the algorithm failed because of accumulating errors. Though larger numbers have been factored by quantum computers using other algorithms, these algorithms are similar to classical brute-force checking of factors, so unlike Shor's algorithm, they are not expected to ever perform better than classical factoring algorithms.
Procedure
The problem that we are trying to solve is, given a
composite number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
, to find a non-trivial
divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
of
(a divisor strictly between
and
). Before attempting to find such a divisor, if there's any doubt whether
is composite or prime, one can use relatively quick
primality-testing algorithms to verify that
is indeed composite, although this is not a part of Shor's algorithm.
Shor's algorithm consists of two parts:
# A reduction, which can be done on a classical computer, of the factoring problem to the problem of
order-finding.
# A quantum algorithm to solve the order-finding problem.
The aim of the algorithm is to find a non-trivial square root
of
modulo
that is different from
and
, because then
:
for a non-zero integer
that gives us two distinct non-trivial divisors
and
of
.
This idea is similar to other
factoring algorithms, such as the
quadratic sieve The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considerab ...
, and a more detailed explanation can be found in the
Explanation section below. Before starting the algorithm, it is imperative to check
to be odd (otherwise
is a divisor) and not to be any power of an integer (otherwise that integer is a divisor), so as to guarantee the existence of a non-trivial square root
of
modulo
.
In turn, finding such a
is reduced to finding an element
as a parameter in an integer function, such that the function has an even period with a certain additional property (as explained below, it is required that the condition of Step 6 of the classical part does not hold). The quantum algorithm is used for finding the period of randomly chosen elements
, as this is a difficult problem on a classical computer.
Classical part
For example: Given
,
, and
, i.e.,
we have
, where
and
. For
that is a product of two distinct primes,
and
,
, which for
is
, and
divides
.
Quantum part: period-finding subroutine
The quantum circuits used for this algorithm are custom designed for each choice of
and each choice of the random
which have the relationship
. Given value
, a value
is chosen such that
. Such a value of
implies that
. The input and output
qubit
In quantum computing, a qubit () or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, ...
registers will store
superpositions of values from
to
. Therefore, these registers have
qubits each. Using what might appear to be twice as many qubits as necessary guarantees that there are at least
different values of
that produce the same
, even as the period
approaches
. The following uses
bra-ket notation to denote quantum states.
Proceed as follows:
Explanation of the algorithm
The algorithm is composed of two parts. The first part of the algorithm turns the factoring problem into the problem of finding the period of a function and may be implemented classically. The second part finds the period using the quantum Fourier transform and is responsible for the quantum speedup.
Non-trivial square root of modulo N/h2>
Shor's algorithm hinges on finding a non-trivial square root of
modulo
In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation).
Given two positive numbers and , modulo (often abbreviated as ) is t ...
; That is, a solution to
:
where
.
If such
exists, we claim that
is a proper factor of
, i.e.,
. In fact, if
, then
divides
, so that
, which goes against the construction of
. If, on the other hand,
, then by
Bézout's identity
In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout, is the following theorem:
Here the greatest common divisor of and is taken to be . The integers and are called Bézout coefficients for ; they a ...
, there are integers
such that
:
Multiplying both sides by
, we obtain
:
As
divides
, we find that
divides
, so that
, again contradicting the construction of
.
Therefore,
is the required proper factor of
. Similarly, it can be proven that
is also a proper factor of
.
For such a non-trivial square root of
modulo
In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation).
Given two positive numbers and , modulo (often abbreviated as ) is t ...
to exist, notice that
, and for any power of an odd prime
, there is no non-trivial square root of
modulo
: For any
either
or
has to be a multiple of
.
Therefore, for Shor's algorithm to work, we need
to be odd (otherwise
is a divisor) and not to be any power of an odd prime (otherwise that prime is a divisor). We can check that there are no integer roots
for
, and if
is not a power of any integer, it is not a power of any odd prime. Here, the upper bound for the integer
that we need to check is determined by
, since for
to be odd,
cannot be
. This check, however, cannot rule out that
may be an odd prime itself, which can only be ruled out by
primality-testing algorithms.
Given that
is odd and not any power of an odd prime, based on the
fundamental theorem of arithmetic
In mathematics, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the ord ...
, we may assume that
is the product of two
coprime
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
integers greater than
(
and
). From the four combinations of choosing plus sign and minus sign in the integer equations
, based on the
Chinese remainder theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...
and
, there are at least four distinct square roots of
modulo
, and therefore at least two distinct non-trivial square roots exist. In fact, they are the solutions to
and
.
Obtaining factors from period
The integers less than
and
coprime
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
with
form the
multiplicative group of integers modulo , which is a finite abelian
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic iden ...
. The size of this group is given by
. By the end of step 3, we have an integer
in this group. As the group is finite,
must have a finite order
, which is the smallest positive integer such that
:
This is the order
of the finite
cyclic subgroup
In abstract algebra, a generating set of a group is a subset of the group set such that every element of the group can be expressed as a combination (under the group operation) of finitely many elements of the subset and their inverses.
In oth ...
⟨''a''⟩ of the
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic iden ...
, which is the smallest positive integer
for which
. Since
and
are
coprime
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
, by
Euler's totient theorem
In number theory, Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem) states that, if and are coprime positive integers, and \varphi(n) is Euler's totient function, then raised to the power \varphi(n) is congr ...
,
must exist, and divides
, where
denotes
Euler's totient function
In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...
.
Therefore,
divides
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
(also written
). Suppose that we are able to obtain
and that it is even. (If
is odd, then by step 5, we have to restart the algorithm with a different random number
) Now
is a square root of
modulo
that is different from
. This is because
is the order of
modulo
, so
, or else the order of
in this group would be
. If
, then by step 6, we have to restart the algorithm with a different random number
.
Eventually, we must hit an
of order
in
such that
. This is because such a
is a square root of
modulo
other than
and
, whose existence is guaranteed by the Chinese remainder theorem, as the odd number
is not a prime power.
Finding the period
Shor's period-finding algorithm relies heavily on the ability of a
quantum computer
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
to be in many states simultaneously.
Physicists call this behavior a "
superposition" of states. To compute the period of a function
, we evaluate the function at all points simultaneously.
Quantum physics does not allow us to access all this information directly, however. A
measurement
Measurement is the quantification of attributes of an object or event, which can be used to compare with other objects or events.
In other words, measurement is a process of determining how large or small a physical quantity is as compared ...
will yield only one of all possible values, destroying all others. If not for the
no-cloning theorem In physics, the no-cloning theorem states that it is impossible to create an independent and identical copy of an arbitrary unknown quantum state, a statement which has profound implications in the field of quantum computing among others. The theore ...
, we could first measure
without measuring
, and then make a few copies of the resulting state (which is a superposition of states all having the same
). Measuring
on these states would provide different
values which give the same
, leading to the period. Because we cannot
make exact copies of a quantum state, this method does not work. Therefore, we have to carefully transform the superposition to another state that will return the correct answer with high probability. This is achieved by the
quantum Fourier transform
In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's ...
.
Shor thus had to solve three "implementation" problems. All of them had to be implemented "fast", which means that they can be implemented with a number of
quantum 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, lik ...
s that is
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
in
.
# Create a superposition of states. This can be done by applying
Hadamard
Jacques Salomon Hadamard (; 8 December 1865 – 17 October 1963) was a French mathematician who made major contributions in number theory, complex analysis, differential geometry and partial differential equations.
Biography
The son of a teac ...
gates to all qubits in the input register. Another approach would be to use the quantum Fourier transform (see below).
# Implement the function
as a quantum transform. To achieve this, Shor used
repeated squaring
A rerun or repeat is a rebroadcast of an episode of a radio or television Broadcast programming, program. There are two types of reruns – those that occur during a Hiatus (television), hiatus, and those that occur when a program is Broadcast sy ...
for his modular exponentiation transformation. It is important to note that this step is more difficult to implement than the quantum Fourier transform, in that it requires ancillary qubits and substantially more gates to accomplish.
# Perform a quantum Fourier transform. By using controlled rotation gates and Hadamard gates, Shor designed a circuit for the quantum Fourier transform (with
) that uses just
gates.
After all these transformations, a measurement will yield an approximation to the period
. For simplicity assume that there is a
such that
is an integer. Then the probability to measure
is
. To see this, we notice that then
:
for all integers
. Therefore, the sum whose square gives us the probability to measure
will be
, as
takes roughly
values and thus the probability is
. There are
possible values of
such that
is an integer, and also
possibilities for
, so the probabilities sum to
.
The period-finding routine can be considered a variation of the more general
quantum phase estimation algorithm to determine the eigenvalue of a unitary corresponding to an eigenvector. In the case of the period-finding routine used in Shor's Algorithm, the unitary in question is modular multiplication by the chosen base mod
. While the computational basis
is not an eigenvector of this unitary, it is a uniform superposition of its
eigenvectors and thus the measurement will give the eigenvalue's phase for one of the eigenvectors. Since not all such phases can be used to extract the period, the retries of the subroutine may be necessary.
The bottleneck
The runtime bottleneck of Shor's algorithm is quantum
modular exponentiation
Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie-Hellman Key Exchange and RSA public/private keys.
Modular ...
, which is by far slower than the
quantum Fourier transform
In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's ...
and classical pre-/post-processing. There are several approaches to constructing and optimizing circuits for modular exponentiation. The simplest and (currently) most practical approach is to mimic conventional arithmetic circuits with
reversible gates, starting with
ripple-carry adders. Knowing the base and the modulus of exponentiation facilitates further optimizations. Reversible circuits typically use on the order of
gates for
qubits. Alternative techniques asymptotically improve gate counts by using
quantum Fourier transform
In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's ...
s, but are not competitive with fewer than 600 qubits owing to high constants.
Discrete logarithms
Given a group
with order
and generator
, suppose we know that
, for some
, and we wish to compute
, which is the
discrete logarithm
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...
:
. Consider the abelian group
, where each factor corresponds to modular addition of values. Now, consider the function
:
This gives us an abelian
hidden subgroup problem
The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science. The framework captures problems such as factoring, discrete logarithm, graph isomorphism, and the shortest vector problem. This makes it es ...
, as
corresponds to a
group homomorphism
In mathematics, given two groups, (''G'', ∗) and (''H'', ·), a group homomorphism from (''G'', ∗) to (''H'', ·) is a function ''h'' : ''G'' → ''H'' such that for all ''u'' and ''v'' in ''G'' it holds that
: h(u*v) = h(u) \cdot h(v)
wh ...
. The kernel corresponds to the multiples of
. So, if we can find the kernel, we can find
. A quantum algorithm for solving this problem exists. This algorithm is, like the factor-finding algorithm, due to Peter Shor and both are implemented by creating a superposition through using Hadamard gates, followed by implementing
as a quantum transform, followed finally by a quantum Fourier transform.
Due to this, the quantum algorithm for computing the discrete logarithm is also occasionally referred to as "Shor's Algorithm."
The order-finding problem can also be viewed as a hidden subgroup problem.
To see this, consider the group of integers under addition, and for a given
such that:
, the function
:
For any finite abelian group G, a quantum algorithm exists for solving the hidden subgroup for G in polynomial time.
See also
*
GEECM, a factorization algorithm said to be "often much faster than Shor's"
*
Grover's algorithm
In quantum computing, Grover's algorithm, also known as the quantum search algorithm, refers to a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output ...
References
Further reading
* .
* Phillip Kaye, Raymond Laflamme, Michele Mosca, ''An introduction to quantum computing'', Oxford University Press, 2007,
"Explanation for the man in the street"by
Scott Aaronson
Scott Joel Aaronson (born May 21, 1981) is an American theoretical computer scientist and David J. Bruton Jr. Centennial Professor of Computer Science at the University of Texas at Austin. His primary areas of research are quantum computing an ...
,
approved by Peter Shor. (Shor wrote "Great article, Scott! That’s the best job of explaining quantum computing to the man on the street that I’ve seen."). An alternate metaphor for the QFT was presented i
one of the comments Scott Aaronson suggests the following 12 references as further reading (out of "the 10
105000 quantum algorithm tutorials that are already on the web."):
* . Revised version of the original paper by Peter Shor ("28 pages, LaTeX. This is an expanded version of a paper that appeared in the Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, Nov. 20--22, 1994. Minor revisions made January, 1996").
Matthew Hayward'
Quantum Algorithms Page 2005-02-17, imsa.edu, LaTeX2HTML version of the origina
LaTeX document also available a
PDFo
postscriptdocument.
Quantum Computation and Shor's Factoring Algorithm Ronald de Wolf, CWI and University of Amsterdam, January 12, 1999, 9 page postscript document.
Shor's Factoring Algorithm Notes from Lecture 9 of Berkeley CS 294–2, dated 4 Oct 2004, 7 page postscript document.
Chapter 6 Quantum Computation 91 page postscript document, Caltech, Preskill, PH229.
b
Samuel L. Braunstein
by Neal Young, Last modified: Tue May 21 11:47:38 1996.
III. Breaking RSA Encryption with a Quantum Computer: Shor's Factoring Algorithm Lecture notes on Quantum computation, Cornell University, Physics 481–681, CS 483; Spring, 2006 by N. David Mermin. Last revised 2006-03-28, 30 page PDF document.
*
* This paper is a written version of a one-hour lecture given on Peter Shor's quantum factoring algorithm. 22 pages.
Chapter 20 Quantum Computation from ''Computational Complexity: A Modern Approach'', Draft of a book: Dated January 2007, Sanjeev Arora and Boaz Barak, Princeton University. Published as Chapter 10 Quantum Computation of Sanjeev Arora, Boaz Barak, "Computational Complexity: A Modern Approach", Cambridge University Press, 2009,
A Step Toward Quantum Computing: Entangling 10 Billion Particles from "Discover Magazine", Dated January 19, 2011.
Josef Gruska - ''Quantum Computing Challenges''also i
Mathematics unlimited: 2001 and beyond Editors Björn Engquist, Wilfried Schmid, Springer, 2001,
External links
* Version 1.0.0 o
libquantum contains a C language implementation of Shor's algorithm with their simulated quantum computer library, but the width variable in shor.c should be set to 1 to improve the runtime complexity.
*
PBS Infinite Series created two videos explaining the math behind Shor's algorithm,
How to Break Cryptography and
Hacking at Quantum Speed with Shor's Algorithm.
{{DEFAULTSORT:Shor's Algorithm
Quantum algorithms
Integer factorization algorithms
Post-quantum cryptography