Shor's Factoring Algorithm and Modular Exponentiation Operators

Understand

These are pedagogical notes on Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time.

• In contrast, all known classical algorithms for the factoring problem take an exponential time to factor large numbers.
• In these notes, we assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing.
• The literature is thick with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation.