Tutorial on Shor's Quantum Factoring Algorithm
Miller [1976] gave a randomized polynomial-time reduction of the problem of
factoring a number N to the problem of determining the order of a random
element in the multiplicative group mod N. Shor's algorithm actually solves
the latter problem.
Here is a high-level description
of Shor's algorithm for the latter problem.
Two sections that could be added to this tutorial (volunteers?) are:
-
A description of Miller's reduction and its analysis.
-
A description of how the discrete Fourier transform is computed in
O(log N) time in the quantum computation model.
Neal Young <Neal.Young@dartmouth.edu>
Last modified: Tue Dec 16 00:04:02 EST 1997