References for Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer
This informal paper lists online, free references which I have consulted in my quest to deeply comprehend Shor’s algorithm for using a quantum computer to factor large semiprime integers such as used for public key encryption.
This list of references was originally part of my informal paper Some Preliminary Questions About Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer, but I moved them here as a standalone paper since they have value separate from that specific paper.
First, some general notes. More specific or technical notes are given on specific reference citations.
- I won’t suggest that these references are an ideal roadmap for others seeking to comprehend Shor’s algorithm at a deep level, but they are decent jumping-off points depending on your particular interests.
- I haven’t found any of these references to be truly comprehensive. They each have bits and pieces of the overall algorithm, rarely the same bits and pieces, and always failing to present the entire, complete picture to a sufficient level of depth — for my tastes, at least.
- My goal is to gain a comprehensive, deep, and intuitive grasp of Shor’s algorithm, not simply a rote mechanical recitation of its steps as a recipe. Strong emphasis on intuition.
- I still have quite a few gaps in my comprehension of Shor’s algorithm, as detailed in my previously cited paper, Some Preliminary Questions About Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer. It’s not that I don’t have any knowledge for these gaps, but that I don’t have absolute 100% confidence and strong intuition for these gaps.
- Maybe to an expert in number theory the gaps between the bits and pieces are obvious, but I’m no expert in number theory.
- Actual implementations of Shor’s algorithm are included as well, especially when a GitHub repository is used.
- Derivatives of Shor’s original algorithm are also included. It is not uncommon for implementations to be based on derivatives rather than the original algorithm.
- Some alternatives to Shor’s algorithm are also listed, although that was not a priority here.
- The ultimate goal is Shor’s algorithm running on a physical quantum computer, but most of the efforts so far have used quantum simulators due to lack of qubits and insufficient coherence time. To the best of my knowledge the largest semiprimes factored to date on a physical quantum computer are 15 and 21, and these did not use the pure Shor’s algorithm as originally published.
- I don’t have any coverage for the second part of Shor’s original paper, computing discrete logarithms.
- Generally, textbooks and other books are not cited as references here since they tend not to be online (other than illegal, bootleg copies!) and free. I personally require online, free materials. But a brief list of books known to have relevant coverage of Shor’s algorithm is found after the main list of references.
- This list is not intended to necessarily be exhaustive or fully comprehensive, but reasonably thorough. I will add to it as I discover additional references.
- At present, the reference citations are in no particular order, typically chronologically in the order I added them.
My own, informal papers
First, my own, informal papers which relate to Shor’s algorithm:
- Some Preliminary Questions About Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer. Details of my own personal gaps of knowledge.
- Ingredients for Shor’s Algorithm for Cracking Strong Encryption Using a Quantum Computer. An approximation of a summary of Shor’s algorithm.
Now, the list of reference citations:
- Shor’s original paper — Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer — https://arxiv.org/abs/quant-ph/9508027.
- Wikipedia Shor’s algorithm article — https://en.wikipedia.org/wiki/Shor%27s_algorithm.
- Riemann’s Hypothesis and Tests for Primality by Miller (1976) — https://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi76.pdf. Referenced by Shor’s original paper — “It is known that using randomization, factorization can be reduced to finding the order of an element [Miller 1976]”. Assumes the Extended Riemann Hypothesis (ERH). This is really the heart and soul of the clever trick that make Shor’s algorithm work.
- MultiplicativeOrder by Wolfram — https://reference.wolfram.com/language/ref/MultiplicativeOrder.html. Multiplicative order is the more proper term for order finding, which is at the heart of Shor’s algorithm.
- Scott Aaronson’s blog post — Shor, I’ll do it — https://www.scottaaronson.com/blog/?p=208.
- Wikipedia Integer factorization article — https://en.wikipedia.org/wiki/Integer_factorization.
- Wikipedia Semiprime article — https://en.wikipedia.org/wiki/Semiprime.
- Wolfram MathWorld definition of Semiprime — http://mathworld.wolfram.com/Semiprime.html.
- Quantum Algorithm Zoo — https://math.nist.gov/quantum/zoo/.
- Wikipedia Chinese remainder theorem article — https://en.wikipedia.org/wiki/Chinese_remainder_theorem.
- Wikipedia Euler’s theorem article — https://en.wikipedia.org/wiki/Euler%27s_theorem.
- Wikipedia Euler’s totient function — https://en.wikipedia.org/wiki/Euler%27s_totient_function.
- What Has Quantum Mechanics to Do With Factoring? — Things I wish they had told me about Peter Shor’s algorithm by N. David Mermin — http://www.lassp.cornell.edu/mermin/factoring-princeton1.pdf.
- The Quantum States of Shor’s Algorithm by Neal Young of Dartmouth — http://www.cs.ucr.edu/~neal/1996/cosc185-S96/shor/high-level.html.
- Shor’s Algorithm for Factoring Large Integers by Lavor, Manssur, and Portugal — https://arxiv.org/abs/quant-ph/0303175.
- Shor’s Quantum Factoring Algorithm by Lomonaco — https://arxiv.org/abs/quant-ph/0010034.
- Computational Complexity: A Modern Approach — Chapter 20 Quantum Computation by Arora and Barak — http://theory.cs.princeton.edu/complexity/quantumchap.pdf.
- Quantum computation: a tutorial by Braunstein — https://www-users.cs.york.ac.uk/~schmuel/comp/comp.html.
- Circuit for Shor’s algorithm using 2n+3 qubits paper by Beauregard — https://arxiv.org/abs/quant-ph/0205095. One of the derivative algorithms.
- Fast Quantum Modular Exponentiation Architecture for Shor’s Factorization Algorithm paper by Pavlidis and Gizopoulos — https://arxiv.org/abs/1207.0511. Requires 9n + 3 qubits, but fewer gate executions. Another derivative algorithm.
- Quantum factorization of 56153 with only 4 qubits paper by Dattani and Bryans — https://arxiv.org/abs/1411.6758. An alternative algorithm.
- Shor’s order (period) finding algorithm and factoring — C/CS/Phys 191 11/01/05 — Fall 2005 Lecture 19 notes — https://inst.eecs.berkeley.edu/~cs191/fa05/lectures/lecture19_fa05.pdf.
- Shor’s Algorithm for Factoring Large Integers paper by Lavor, Manssur, and Portugal — https://arxiv.org/abs/quant-ph/0303175. “This work is a tutorial on Shor’s factoring algorithm by means of a worked out example. Some basic concepts of Quantum Mechanics and quantum circuits are reviewed. It is intended for non-specialists which have basic knowledge on undergraduate Linear Algebra.”
- Factoring Safe Semiprimes with a Single Quantum Query paper by Grosshans, Lawson, Morain, and Smith — https://arxiv.org/abs/1511.04385. “With just one call to QOFA [quantum order finding algorithm], our algorithm almost always factors safe semiprimes.” A variation on Shor’s algorithm, not a straight derivative but not a true alternative either — still uses the concept of order finding, which is at the heart of Shor’s algorithm.
- Alas, I am unable to give the Quantum Computation and Quantum Information book by Nielsen and Chuang as a reference for my work since I am limiting myself to online free material. See http://www.michaelnielsen.org/qcqi/ and https://www.amazon.com/Quantum-Computation-Information-10th-Anniversary/dp/1107002176.
- IBM Q Experience documentation — Shor’s algorithm — https://quantumexperience.ng.bluemix.net/proxy/tutorial/full-user-guide/004-Quantum_Algorithms/110-Shor's_algorithm.html.
- NIST Post-Quantum Cryptography effort — https://csrc.nist.gov/projects/post-quantum-cryptography.
- Wikipedia Post-quantum cryptography article — https://en.wikipedia.org/wiki/Post-quantum_cryptography.
- A quantum algorithm for greatest common divisor problem paper by Wang, Jiang, Mu, and Fan — https://arxiv.org/abs/1707.06430.
- Shor’s Algorithm presentation by Bäumer, Sobez, and Tessarini — https://qudev.phys.ethz.ch/content/QSIT15/Shors%20Algorithm.pdf.
- Shor’s Algorithm and the Quantum Fourier Transform by Fang Xi Lin of McGill University — http://www.math.mcgill.ca/darmon/courses/12-13/nt/projects/Fangxi-Lin.pdf. An alternative description of Shor’s algorithm, but still doesn’t answer most of my questions. I used it to try to understand the quantum Fourier transform a little better, but my questions persist.
- Scaling laws for Shor’s algorithm with a banded quantum Fourier transform by Nam and Blümel — https://arxiv.org/abs/1302.5844. An alternative description of Shor’s algorithm as well as an adaptation using a banded QFT for much better performance.
- Symmetry boosts quantum computer performance by Nam and Blümel — https://arxiv.org/abs/1601.07497. Yet another adaptation of Shor’s algorithm to boost performance.
- Quantum Computing Lecture Notes by Mark Oskin of University of Washington — https://homes.cs.washington.edu/~oskin/quantum-notes.pdf. Yet another description of Shor’s algorithm, order-finding, QFT, phase estimation, and quantum computing in general.
- CSE 599d — Quantum Computing — Shor’s Algorithm lecture notes by Dave Bacon, Department of Computer Science & Engineering, University of Washington — https://courses.cs.washington.edu/courses/cse599d/06wi/lecturenotes11.pdf.
- Experimental Realization of an Order-Finding Algorithm with an NMR Quantum Computer by Vandersypen, Steffen, Breyta, Yannoni, Cleve, and Chuang of IBM Almaden Research Center and Stanford — https://arxiv.org/abs/quant-ph/0007017. Early implementation (2000) of order-finding algorithm using a nuclear magnetic resonance (NMR) quantum computer. A custom molecule implemented a 5-qubit quantum computer.
- Quantum Algorithm Implementations for Beginners by Coles, Eidenbenz, Pakin, et al — https://arxiv.org/abs/1804.03719. Includes a reasonably succinct description of Shor’s algorithm including an implementation on the IBM ibmqx4 5-qubit quantum computer. Still leaves many questions unanswered. They factored 15 using a selected random number of 11. The raw algorithm required 12 qubits and 196 gates, so they used an optimized/compiled version which worked in 5 qubits and 11 gates. Seems like cheating, to me.
- A Re-evaluation of Shor’s Algorithm by Cooper — https://arxiv.org/pdf/quant-ph/0612077. Critical examination of Shor’s algorithm. But still leaves many questions and issues unanswered. Vintage 2006.
- Shor’s Algorithm in Pyquil by Alec Brickner — https://cs269q.stanford.edu/projects2019/Brickner_Y.pdf. Student project for CS 269Q: Quantum Computer Programming course at Stanford.
- Implementation of Shor’s algorithm in pyQuil by William Burton — https://cs269q.stanford.edu/projects2019/burton_Y.pdf. Student project for CS 269Q: Quantum Computer Programming course at Stanford.
- Realization of a scalable Shor algorithm by Monz, Nigg, Martinez, Brandl, Schindler, Rines, Wang, Chuang, and Blatt — https://science.sciencemag.org/content/351/6277/1068. Factored 15 using a trapped-ion quantum computer with seven qubits. Technically, this is a derivative of Shor’s algorithm, not the exact same algorithm as originally published by Shor.
- Variational Quantum Factoring by Anschuetz, Olson, Aspuru-Guzik, and Cao — https://arxiv.org/abs/1808.08927. An alternative approach using QAOA (Quantum Approximate Optimization Algorithm), which is not based on Shor’s approach. On December 11, 2019 Zapata Computing and IBM announced (via Twitter) that they had factored 1099551473989 (1048589 x 1048601) using three qubits with a solution found 30% of the time, but few details given — not clear if they used the same exact approach of that paper. A fresh paper on this effort is expected.
- Implementation of Variational Quantum Factoring algorithm by Stechly — https://github.com/mstechly/vqf. GitHub repository for an implementation of the algorithm described in Variational Quantum Factoring by Anschuetz, Olson, Aspuru-Guzik, and Cao. This is unrelated to Shor’s algorithm — it’s an alternative approach.
- NSF/DOE Quantum Science Summer School presentation by Scott Pakin, June 8, 2017 — http://qs3.mit.edu/images/pdf/QS3-2017---Pakin-Lecture.pdf. Two relevant slides. Still vague and incomplete, but does show some aspects well.
- O’Reilly Programming Quantum Computers: Essential Algorithms and Code Samples by Johnston, Harrigan, and Gimeno-Segovia — https://www.amazon.com/Programming-Quantum-Computers-Essential-Algorithms/dp/1492039683. Book is not freely available online (other than “Look Inside” using Amazon), but code examples in GitHub are freely accessible online and can be run directly online, including implementation of Shor’s algorithm — https://oreilly-qc.github.io/.
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits by Craig Gidney and Martin Ekerå, 2019. I haven’t read it in enough detail to come to a judgment.
- Shor’s quantum factoring algorithm on a photonic chip, by Alberto Politi, Jonathan C. F. Matthews, and Jeremy L. O’Brien, 2009. “… an integrated waveguide silica-on-silicon chip that guides four single-photon qubits through the computation to factor 15.”
- Realization of a scalable Shor algorithm by Thomas Monz, Daniel Nigg, Esteban A. Martinez, Matthias F. Brandl, Philipp Schindler, Richard Rines, Shannon X. Wang, Isaac L. Chuang, and Rainer Blatt, 2015. “… we report the realization of a fully scalable Shor algorithm as proposed by Kitaev. For this, we demonstrate factoring the number fifteen by effectively employing and controlling seven qubits and four “cache-qubits”, together with the implementation of generalized arithmetic operations, known as modular multipliers. The scalable algorithm has been realized with an ion-trap quantum computer exhibiting success probabilities in excess of 90%.”
Generally, textbooks and other books have not been cited as references here since they tend not to be online (other than illegal, bootleg copies!) and free. I personally require online, free materials. But here is a brief list of books known to have relevant coverage of Shor’s algorithm:
- Quantum Computation and Quantum Information: 10th Anniversary Edition by Nielsen and Chuang — https://www.amazon.com/Quantum-Computation-Information-10th-Anniversary/dp/1107002176. Popularly known as “Mike and Ike.”
- Quantum Computing: A Gentle Introduction by Rieffel and Polak — https://www.amazon.com/Quantum-Computing-Introduction-Engineering-Computation/dp/0262015064.
- Quantum Computer Science: An Introduction by Mermin — https://www.amazon.com/Quantum-Computer-Science-David-Mermin/dp/0521876583. Based on his lecture notes. Excerpt on Shor’s algorithm listed above in main references.
- O’Reilly Programming Quantum Computers: Essential Algorithms and Code Samples by Johnston, Harrigan, and Gimeno-Segovia — https://www.amazon.com/Programming-Quantum-Computers-Essential-Algorithms/dp/1492039683. Code examples in GitHub are freely accessible online, including implementation of Shor’s algorithm which can be run directly online.
- Dancing with Qubits: How quantum computing works and how it can change the world by Sutor — https://www.amazon.com/Dancing-Qubits-quantum-computing-change/dp/1838827366.
The lists in this paper will be updated as I become aware of additional references.
For more of my writing: List of My Papers on Quantum Computing.