quantum algorithms:
constructive mathematics, realizability, computability
propositions as types, proofs as programs, computational trinitarianism
A prime factorization algorithm for quantum computers.
Due to:
Peter W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press: 124-134 (1994) [doi:10.1109/SFCS.1994.365700]
Daniel R. Simon, On the power of quantum computation, SIAM Journal on Computing 26 5 (1997) [doi:10.1137/S0097539796298637, pdf]
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:
See also:
Wikipedia, Shor’s algorithm
Wikipedia, Simon’s problem
On compiling Shor’s algorithm to su(2)-anyon braid quantum gates (i.e. implementation in topological quantum computation):
Last revised on September 27, 2022 at 04:40:17. See the history of this page for a list of all contributions to it.