nLab Shor's algorithm



Quantum systems

quantum logic

quantum physics

quantum probability theoryobservables and states

quantum information

quantum computation


quantum algorithms:

quantum sensing

quantum communication

Constructivism, Realizability, Computability



A prime factorization algorithm for quantum computers.


Due to:

Early review:

Further review:

  • Daniel Simon, Exploring Simon’s Algorithm with Daniel Simon (Oct 2021)

    A bit of amusing history: I submitted my algorithm to a theoretical computer science conference (STOC 1993), but it was rejected. However, Peter Shor was on the program committee for that conference, and immediately saw the potential (that I had had absolutely no inkling of, to be honest) for applying the same general algorithm structure to concrete problems like factoring and discrete logarithms. After trying unsuccessfully to persuade the committee to accept my paper, he got to work on his own, and submitted it to the next major theoretical computer science conference (FOCS 1993)—in parallel with mine, resubmitted. We had in fact agreed to merge the papers if only his was accepted, but the committee fortunately agreed to accept them both, giving us each credit for our respective portions of the resulting achievement.”

  • Renato Portugal, Basic Quantum Algorithms [arXiv:2201.10574]

Textbook account:

Lecture notes:

Implementation in Quipper:

  • Safat Siddiqui, Mohammed Jahirul Islam, Omar Shehab, §4.3, §4.5 in: Five Quantum Algorithms Using Quipper [arXiv:1406.4481]

See also:

On compiling Shor’s algorithm to su(2)-anyon braid quantum gates (i.e. implementation in topological quantum computation):

category: people

Last revised on August 17, 2023 at 15:22:11. See the history of this page for a list of all contributions to it.