Shor's algorithm is a quantum algorithm for factoring an integer N in O((log N)³) time and O(log N) space, named after Peter Shor. The Bloch sphere is a representation of a qubit, the fundamental building block of quantum computers. ... In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ... “Prime decomposition” redirects here. ... For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ... Peter Shor Peter W. Shor (born August 14, 1959) is an American theoretical computer scientist most famous for his work on quantum computation, in particular for devising a quantum algorithm for factoring exponentially faster than the best currently-known algorithm running on a classical computer (see Shors algorithm). ...

A common public-key cryptography method known as RSA is based on the assumption that it is computationally infeasible to factor a large integer. For this reason a quantum computer with sufficiently many quantum bits could "break" RSA. RSA uses a public key, N, which is the product of two large prime numbers. One way to crack RSA encryption is by factoring N, but with classical algorithms, factoring becomes increasingly time-consuming as N grows large; more specifically, no classical algorithm is known that can factor in time which is polynomial in log N. A big random number is used to make a public-key pair. ... This article is about an algorithm for public-key encryption. ... This article is about an algorithm for public-key encryption. ... In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. ... In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ...

Like many quantum computer algorithms, Shor's algorithm is probabilistic. Furthermore, it gives the correct answer with constant bounded probability. A proposed answer can be easily verified by dividing the RSA key by the alleged factor and looking for a remainder. By running the algorithm multiple times a correct answer can be obtained with exponentially small error. The word probability derives from the Latin probare (to prove, or to test). ...

Shor's algorithm was discovered in 1994 by Peter Shor, but the classical part was known before; it is credited to G. L. Miller. Seven years later, in 2001, it was demonstrated by a group at IBM, which factored 15 into 3 and 5, using a quantum computer with 7 qubits. [1] This be the Danster with a few new trickoms ahahahahahahahahahahahahah Hace fun life life // January 1 - NAFTA goes into effect. ... Peter Shor Peter W. Shor (born August 14, 1959) is an American theoretical computer scientist most famous for his work on quantum computation, in particular for devising a quantum algorithm for factoring exponentially faster than the best currently-known algorithm running on a classical computer (see Shors algorithm). ... Year 2001 (MMI) was a common year starting on Monday (link displays the 2001 Gregorian calendar). ... International Business Machines Corporation (IBM, or colloquially, Big Blue) (NYSE: IBM) (incorporated June 15, 1911, in operation since 1888) is headquartered in Armonk, New York, USA. The company manufactures and sells computer hardware, software, and services. ... To meet Wikipedias quality standards and make it more accessible, this article needs a better explanation of technical details or more context regarding applications or importance to make it more accessible to a general audience, or at least to technical readers outside this specialty. ...

Two research groups, independently of each other, one led by Andrew White at the University of Queensland in Brisbane, Australia, and the other by Chao-Yang Lu of the University of Science and Technology of China, in Hefei, have built rudimentary laser-based quantum computers that can implement Shor's algorithm in 2007.

Procedure

The problem we are trying to solve is that, given an integer N, we try to find another integer p between 1 and N that divides N. The integers are commonly denoted by the above symbol. ...

Shor's algorithm consists of two parts:

1. A reduction of the factoring problem to the problem of order-finding, which can be done on a classical computer.
2. A quantum algorithm to solve the order-finding problem.

In group theory, the term order is used in two closely related senses: the order of a group is its cardinality, i. ...

Classical part

1. Pick a random number a < N
2. Compute gcd(a, N). This may be done using the Euclidean algorithm.
3. If gcd(a, N) ≠ 1, then there is a nontrivial factor of N, so we are done.
4. Otherwise, use the period-finding subroutine (below) to find r, the period of the following function:

   ,

   i.e. the smallest integer r for which f(x + r) = f(x).
5. If r is odd, go back to step 1.
6. If a ^{r /2} ≡ -1 (mod N), go back to step 1.
7. gcd(a^r/2 ± 1, N) is a nontrivial factor of N. We are done.

In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder. ... In number theory, the Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (GCD) of two elements of any Euclidean domain (for example, the integers). ... In mathematics, a periodic function is a function that repeats its values after some definite period has been added to its independent variable. ...

Quantum part: Period-finding subroutine

The quantum circuits used for this algorithm are custom designed for each choice of N and the random a used in f(x) = a^x mod N. Given N, find Q = 2^q such that , which implies Q / r > N. The input and output qubit registers need to hold superpositions of values from 0 to Q − 1, and so have q qubits each. Using what might appear to be twice as many qubits as necessary guarantees that there are at least N different x which produce the same f(x), even as the period r approaches N/2. To meet Wikipedias quality standards and make it more accessible, this article needs a better explanation of technical details or more context regarding applications or importance to make it more accessible to a general audience, or at least to technical readers outside this specialty. ...

Proceed as follows:

1. Initialize the registers to

   

   where x runs from 0 to Q − 1. This initial state is a superposition of Q states.
2. Construct f(x) as a quantum function and apply it to the above state, to obtain

   .

   This is still a superposition of Q states.
3. Apply the quantum Fourier transform to the input register. This transform (operating on a superposition of power-of-two Q = 2^q states) uses a Q^th root of unity such as ω = e^{2πi / Q} to distribute the amplitude of any given state equally among all Q of the states, and to do so in a different way for each different x:

   .

   This leads to the final state

   .

   This is a superposition of many more than Q states, but many fewer than Q² states. Although there are Q² terms in the sum, the state can be factored out whenever x₀ and x produce the same value. Let

   ω = e^{2πi / Q} be a Q^th root of unity,

   r be the period of f,

   x₀ be the smallest of a set of x which yield the same given f(x) (we have x₀ < r), and

   b run from 0 to so that x₀ + rb < Q.

   Then ω^ry is a unit vector in the complex plane (ω is a root of unity and r and y are integers), and the coefficient of in the final state is

   .

   Each term in this sum represents a different path to the same result, and quantum interference occurs — constructive when the unit vectors ω^ryb point in nearly the same direction in the complex plane, which requires that ω^ry point along the positive real axis.
4. Perform a measurement. We obtain some outcome y in the input register and f(x₀) in the output register. Since f is periodic, the probability of measuring some pair y and f(x₀) is given by

   .

   Analysis now shows that this probability is higher, the closer unit vector ω^ry is to the positive real axis, or the closer yr/Q is to an integer.
5. Turn y/Q into an irreducible fraction, and extract the denominator r′, which is a candidate for r.
6. Check if f(x) = f(x + r′). If so, we are done.
7. Otherwise, obtain more candidates for r by using values near y, or multiples of r′. If any candidate works, we are done.
8. Otherwise, go back to step 1 of the subroutine.

The quantum Fourier transform is the discrete Fourier transform with a particular decomposition into a product of simpler unitary matrices. ... In mathematics, the nth roots of unity, or de Moivre numbers, are all the complex numbers which yield 1 when raised to a given power n. ... In mathematics, the imaginary unit (or sometimes the Latin or the Greek iota, see below) allows the real number system to be extended to the complex number system . ... Interference of two circular waves - Wavelength (decreasing bottom to top) and Wave centers distance (increasing to the right). ... An irreducible fraction (or fraction in lowest terms) is a vulgar fraction in which the numerator and denominator are smaller than those in any other equivalent fraction. ...

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.

I. Obtaining factors from period

The integers less than N and coprime with N form a finite group under multiplication modulo N. By the end of step 3, we have an integer a in this group. Since the group is finite, a must have a finite order r, the smallest positive integer such that Coprime - Wikipedia /**/ @import /skins-1. ... This picture illustrates how the hours on a clock form a group under modular addition. ... Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ...

Therefore, N | (a ^r − 1 ). Suppose we are able to obtain r, and it is even. Then In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ...

r is the smallest positive integer such that a ^r ≡ 1, so N cannot divide (a ^{r / 2} − 1). If N also does not divide (a ^{r / 2} + 1), then N must have a nontrivial common factor with each of (a ^{r / 2} − 1) and (a ^{r / 2} + 1).

Proof: For simplicity, denote (a ^{r / 2} − 1) and (a ^{r / 2} + 1) by u and v respectively. N | uv, so kN = uv for some integer k. Suppose gcd(u, N) = 1; then mu + nN = 1 for some integers m and n (this is a property of the greatest common divisor.) Multiplying both sides by v, we find that mkN + nvN = v, so N | v. By contradiction, gcd(u, N) ≠ 1. By a similar argument, gcd(v, N) ≠ 1. In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder. ...

This supplies us with a factorization of N. If N is the product of two primes, this is the only possible factorization.

II. Finding the period

Shor's period-finding algorithm relies heavily on the ability of a quantum computer to be in many states simultaneously. Physicists call this behaviour a "superposition" of states. To compute the period of a function f, we evaluate the function at all points simultaneously. The Bloch sphere is a representation of a qubit, the fundamental building block of quantum computers. ... Quantum superposition is the application of the superposition principle to quantum mechanics. ...

Quantum physics does not allow us to access all this information directly, though. A measurement will yield only one of all possible values, destroying all others. But for the No cloning theorem, we could first measure f(x) without measuring x, and then make a few copies of the resulting state (which is a superposition of states all having the same f(x)). Measuring x on these states would provide different x values which give the same f(x), 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. The framework of quantum mechanics requires a careful definition of measurement, and a thorough discussion of its practical and philosophical implications. ... The no cloning theorem is a result of quantum mechanics which forbids the creation of identical copies of an arbitrary unknown quantum state. ... Quantum cloning is the process that takes an arbitrary, unknown quantum state and makes an exact copy without altering the original state in any way. ... The quantum Fourier transform is the discrete Fourier transform with a particular decomposition into a product of simpler unitary matrices. ...

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 gates that is polynomial in logN. A quantum gate or quantum logic gate is a rudimentary quantum circuit operating on a small number of qubits. ... In mathematics, a polynomial is an expression that is constructed from one or more variables and constants, using only the operations of addition, subtraction, multiplication, and constant positive whole number exponents. ...

1. Create a superposition of states. This can be done by applying Hadamard gates to all qubits in the input register. Another approach would be to use the quantum Fourier transform (see below).
2. Implement the function f as a quantum transform. To achieve this, Shor used repeated squaring 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.
3. Perform a quantum Fourier transform. By using controlled rotation gates and Hadamard gates Shor designed a circuit for the quantum Fourier transform (with Q = 2^q) that uses just q(q − 1) / 2 = O((logQ)²) gates. arXiv:quant-ph/9508027v2 p. 14

After all these transformations a measurement will yield an approximation to the period r. For simplicity assume that there is a y such that yr/Q is an integer. Then the probability to measure y is 1. To see that we notice that then The Hadamard transform (Hadamard transformation, also known as the Walsh-Hadamard transformation) is an example of a generalized class of Fourier transforms. ... Exponentiating by squaring is an algorithm used for the fast computation of large integer powers of a number. ...

e ^{− 2πibyr / Q} = 1

for all integers b. Therefore the sum whose square gives us the probability to measure y will be Q/r since b takes roughly Q/r values and thus the probability is 1 / r². There are r y such that yr/Q is an integer and also r possibilities for f(x₀), so the probabilities sum to 1.

Note: another way to explain Shor's algorithm is by noting that it is just the quantum phase estimation algorithm in disguise.

Modifications to Shor's Algorithm

There have been many modifications to Shor's algorithm. For example, whereas, an order of twenty to thirty runs are required on a quantum computer in the case of Shor's original algorithm, and with some of the other modifications, in the case of the modification done by David McAnally at the University of Queensland an order of only four to eight runs on the quantum computer is required. [2] The University of Queensland (UQ) is the longest-established university in the state of Queensland, Australia, and a member of Australias Group of Eight. ...

References

• arXiv:quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor

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"). This preprint was eventually published as SIAM J.Sci.Statist.Comput. 26 (1997) 1484.

• Quantum Computation and Quantum Information, Michael A. Nielsen, Isaac L. Chuang, Cambridge University Press, 2000.

A general textbook on quantum computing.

This book was recommended (includes "a complete review of Shor’s algorithm") in the discussion of Aaronson's blog article (see below).

• Efficient Networks for Quantum Factoring, David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni, and John Preskill, Phys. Rev. A 54, 1034–1063 (1996).

• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance

Lieven M. K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood & Isaac L. Chuang, Nature 414, 883–887 (20 Dec 2001). abstract

An implementation of Shor's Algorithm that factorizes the number 15.

• arXiv:quant-ph/0308171v3 Implementing Shor's algorithm on Josephson Charge Qubits

Juha J. Vartiainen, Antti O. Niskanen, Mikio Nakahara, Martti M. Salomaa

12 pages, submitted to Phys. Rev. A

• arXiv:quant-ph/0402196v1 Implementation of Shor's Algorithm on a Linear Nearest Neighbour Qubit Array

Austin G. Fowler, Simon J. Devitt, Lloyd C. L. Hollenberg

Quant. Info. Comput. 4, 237-251 (2004)

• arXiv:quant-ph/0112055v4 A Refinement of Shor's Algorithm

David McAnally. 45 pages. A refinement of Shor's Algorithm for determining order is introduced, which determines a divisor of the order after any one run of a quantum computer with almost absolute certainty. The information garnered from each run is accumulated to determine the order, and for any k greater than 1, there is a guaranteed minimum positive probability that the order will be determined after at most k runs. The probability of determination of the order after at most k runs exponentially approaches a value negligibly less than one, so that the accumulated information determines the order with almost absolute certainty. The probability of determining the order after at most two runs is more than 60%, and the probability of determining the order after at most four runs is more than 90%.

"Submitted to J. Phys A." according to the author's Professional Publications page.

David Beckman (Born June 8, 1938) is a former Canadian Football League head coach. ... Prof. ...

External links

• "Explanation for the man in the street" by Scott Aaronsen, "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."). Aaronsen suggests the following 12 sites as further reading (out of "the 10¹⁰⁵⁰⁰⁰ quantum algorithm tutorials that are already on the web."):

1. arXiv quant-ph/9508027 Shor's revised paper. See above for details.
2. Quantum Computing and Shor's Algorithm, Matthew Hayward, 2005-02-17, imsa.edu, LaTeX2HTML version of the original 2750 line LaTeX document, also available as a 61 page PDF or postscript document.
3. Quantum Computation and Shor's Factoring Algorithm, Ronald de Wolf, CWI and University of Amsterdam, January 12, 1999, 9 page postscript document.
4. Shor's Factoring Algorithm, Notes from Lecture 9 of Berkeley CS 294-2, dated 4 Oct 2004, 7 page postscript document.
5. Chapter 6 Quantum Computation, 91 page postscript document, Caltech, Preskill, PH229.
6. Quantum computation: a tutorial by Samuel L. Braunstein.
7. The Quantum States of Shor's Algorithm, by Neal Young, Last modified: Tue May 21 11:47:38 1996.
8. A now-circular reference via the Wikipedia copy of this article; clearly Aaronsen's link originally reached the 20 Feb 2007 version.
9. 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.
10. arXiv quant-ph/0303175 Shor's Algorithm for Factoring Large Integers. C. Lavor, L.R.U. Manssur, R. Portugal. Submitted on 29 Mar 2003. This work is a tutorial on Shor's factoring algorithm by means of a worked out example. Some basic concepts of Quantum Mechanics and quantum circuits are reviewed. It is intended for non-specialists which have basic knowledge on undergraduate Linear Algebra. 25 pages, 14 figures, introductory review.
11. arXiv quant-ph/0010034 Shor's Quantum Factoring Algorithm, Samuel J. Lomonaco, Jr, Submitted on 9 Oct 2000, This paper is a written version of a one hour lecture given on Peter Shor's quantum factoring algorithm. 22 pages.
12. Chapter 20 Quantum Computation, from Computational Complexity: A Modern Approach, Draft of a book: Dated January 2007, Comments welcome!, Sanjeev Arora and Boaz Barak, Princeton University.

• A demonstration of Shor's algorithm in PHP