Shor’s Algorithm and Quantum Supremacy
What's Better About Quantum Computers?
Peter W. Shor
Henry Adams Morss & Henry Adams Morss, Jr. Professor of Applied Mathematics
MIT
Sponsored by PSW Science Members Erica & Bruce Kane
About the Lecture
Shortly after quantum mechanics was first formulated around 1930, it became evident that it was a strange theory. It took many years, however, before anybody suggested putting this strangeness to use. It turns out that this strangeness can be used to accomplish tasks with quantum information processing that are not possible classically. One example of this, and the one that really drew attention to this phenomenon, was Peter’s discovery that quantum computers could factor large numbers into primes in manageable time frames, something that would take digital computers billions of years. This lecture will recount how Peter discovered the quantum factoring algorithm, and briefly explain the principles behind how it works.
Among the first responses to the development of the quantum factoring algorithm was the claim that it could never possibly work — that errors in quantum mechanical computation are inevitable, because experiments could never be performed to the precision necessary for the algorithms to succeed, and because there were no-go theorems saying that you could never correct errors on quantum computers. In fact, the quantum computer gates are still not very precise. However, we have developed a theory of quantum error correcting codes that in theory lets you correct errors on quantum computers. We will recount the early development of this research area and explain some of the progress that has been made since then.
Selected Reading & Media References
https://www.ibm.com/think/topics/quantum-computing
About the Speaker
Peter W. Shor is the Morss Professor of Applied Mathematics, in the Department of Mathematics at the Massachusetts Institute of Technology. Previously he was a Bell Labs Fellow at Bell Laboratories and at AT&T Shannon Laboratories.
Peter is well known for inventing “Shor’s Algorithm”: a polynomial-time quantum algorithm for factoring integers, which demonstrated the potential power of quantum computers. He also produced foundational work in quantum error-correcting codes, including the first quantum code capable of correcting arbitrary single-qubit errors. These and other contributions Peter made helped launch the modern field of quantum computing.
Peter’s research focuses on quantum computation, quantum information theory, and complexity theory. His interests include the development of efficient quantum algorithms for problems that are classically intractable, such as factoring and discrete logarithms. He also investigates the theoretical limits of quantum communication and computation. He has worked extensively on fault-tolerant quantum computation and the foundational aspects of quantum mechanics in computation. And more broadly, he is interested in the interface between mathematics, computer science, and physics.
Peter is an author on more than 100 peer-reviewed publications.
Among numerous honors and awards, he has received the Breakthrough Prize in Fundamental Physics, the Dirac Medal of the ICTP, the Gödel Prize, the Nevanlinna Prize (now the IMU Abacus Medal), and the BBVA Foundation Frontiers of Knowledge Award. He is a member of the National Academy of Sciences, the American Academy of Arts and Sciences, and a Fellow of the American Mathematical Society and the ACM.
Peter earned a BA in Mathematics at Caltech and a PhD in Applied Mathematics at MIT.
Wikipedia: https://en.wikipedia.org/wiki/Peter_Shor
Webpage(s): https://math.mit.edu/~shor/
Minutes
On September 19, 2025, Members of the Society and guests joined the speaker for a reception and dinner at 5:45 PM in the Members’ Dining Room at the Cosmos Club. Thereafter they joined other attendees in the Powell Auditorium for the lecture proceedings. In the Powell Auditorium of the Cosmos Club in Washington, D.C., President Larry Millstein called the lecture portion of the 2,521st meeting of the Society to order at 8:06 p.m. ET. He began by welcoming attendees, thanking sponsors for their support, announcing new members, and inviting guests to join the society. Scott Mathews then read the minutes of the previous meeting which included the lecture by Will Marshall, titled “Revolutionizing Earth Observation with SmallSats and AI”. The minutes were approved as read.
President Millstein then introduced the speaker for the evening, Peter Shor, of MIT. His lecture was titled “Shor’s Algorithm and Quantum Supremacy”.
The speaker began by discussing some aspects of quantum mechanics, saying “From its conception, quantum mechanics has been recognized as a strange theory.” He went on to describe some examples of “quantum weirdness”. These included the double slit experiment, (where a single particle acts as though it passed through both slits), the superposition principle (where a quantum system must be treated as a combination of mutually exclusive states), and entanglement (where quantum states are strongly correlated).
Shor described qubits; quantum systems with two distinguishable states, like the polarization of a photon. He showed some of the mathematics related to representing a photon’s polarization as the superposition of two unit vectors; one for vertical polarization, and one for horizontal polarization. He discussed the fact that, before observation, the polarization of the photon must be represented as a linear combination of the two distinguishable states. Shor said that a system composed of n qubits constitutes a 2n-dimensional vector space, and that the potentially “huge size of this vector space is one of the places that quantum computing gets its power.”
The speaker then gave a brief history of quantum computing, starting with the 1981 Conference on Physics and Computation, held at MIT, where Richard Feynman gave the keynote address, titled “Simulating Physics with Computers”. In this lecture, Feynman said that it was exponentially hard to simulate quantum physics using classical computers and suggested that quantum computers might provide a solution. Shor mentioned several of the seminal papers in the field, including: a 1985 paper by Deutsch, a 1992 paper by Deutsch and Jozsa, a 1993 paper by Bernstein and Vazirani, and Shor’s 1994 paper on a quantum algorithm for finding the prime factors of an integer. Shor also proposed other quantum algorithms for solving the factoring problem, the discrete logarithm problem, and the period finding problem.
Shor described the physical implementation of a quantum computer and techniques for creating and manipulating qubits. These included: cold ion traps, superconducting qubits, photonic qubits, and neutral atoms. He defined “quantum supremacy” as the demonstration of a quantum computer solving a problem that is practically impossible to solve on a classical computer. Shor described some of the problems in determining when quantum supremacy is actually achieved. These included the fact that computer scientists regularly find new mathematical tricks or approximations which speed up classical computation, and the fact that a practical quantum computer requires the implementation of quantum error correction. This error correction dramatically increases the number of qubits required. Shor said that factoring a sufficiently large number would be a believable claim of quantum supremacy, but he predicted that it was at least a decade away.
The speaker then described some of the details of quantum error correction. He indicated that a quantum computer is both a digital computer and an analog computer, at the same time. He said that the digital aspects of a quantum computer allow the implementation of quantum error correction, but that the Heisenberg uncertainty principle and the “no-cloning” theorem make it difficult. He described how a quantum repetition code can correct for both bit-flip errors and phase errors, but that such a code requires a minimum of 9 copies of the qubit. Shor showed some of the mathematics associated with implementing these error codes.
Shor described the difference between error correction codes and fault tolerance, where fault tolerance is the system-level property of continuing to operate correctly despite faults. He discussed two techniques for implementing fault tolerance: surface codes, which require a minimum of 49 qubits, and LDPC codes, which, although requiring fewer qubits, require higher connectivity and are therefore more difficult to physically implement in an actual quantum computer.
The speaker ended his talk by listing future developments in quantum computing that would be desirable. These included: new quantum algorithms for solving different problems, improvement of existing quantum algorithms, and finding better ways to implement quantum fault tolerance.
The lecture was followed by a Question and Answer session.
A guest asked the speaker “Do you believe in quantum computing, and if all it can do is factor numbers, why bother?” Shor responded that many of the most useful algorithms implemented on classical computers would not have been discovered if people were not experimenting on classical computers.
A member asked about the optimal organization of a quantum computer, as compared to classical computers. Shor responded that classical computers are not organized in an optimal configuration for computation, but rather are organized “in a way we can easily reason about and program with”. He said that optimized classical computation required programming with machine code.
A guest asked if there were any other algorithms that did not involve solving the factoring problem that could break RSA encryption. Shor responded “To break RSA without factoring seems really, incredibly, unlikely.”
After the question and answer period, President Millstein thanked the speaker and presented him with a PSW rosette, a signed copy of the announcement of his talk, and a signed copy of Volume 17 of the PSW Bulletin. He then announced speakers of up-coming lectures and made a number of housekeeping announcements. He adjourned the 2,521th meeting of the society at 9:58 pm ET.
Temperature in Washington, DC: 23.9° Celsius
Weather: Mostly cloudy
Audience in the Powell auditorium: 145
Viewers on the live stream: 50
For a total of 195 viewers
Views of the video in the first two weeks: 1065
Respectfully submitted, Scott Mathews: Recording Secretary