Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer 1: The Quantum Fourier Transform Circuit Computes A_q up to Bit ReversalResearch Paper
Shor's factoring and discrete logarithm algorithms (Shor 1997) reduce both problems to sampling from the output of a quantum Fourier transform: a register holding a superposition with a hidden period is transformed, then measured, and the measured value carries information about the period. The whole speed-up rests on one engineering fact: for the …