Peter Shor on the genesis of Shor’s algorithm

Interview by David Zierler. Adapted and annotated by Ryan Dahn.

In the early 1990s, the field now known as quantum information science was a minor subdiscipline comprising a handful of theoretical physicists, mathematicians, and computer scientists. It was often viewed as an esoteric backwater with no real-world applications because no one had demonstrated a scenario in which quantum computers—which at that time were purely theoretical—would be markedly more efficient than their classical counterparts.

That all changed in 1994, when Peter Shor outlined one of the first algorithms that could make a problem that rapidly became intractable on a classical computer practical on a quantum one. The algorithm attracted extra attention because it found the prime factors of large numbers and so had serious implications for information security: A crucial assumption underlying several important digital cryptography schemes, many of which are still in use today, was that factoring large numbers on a computer would take an unfeasibly long time.

Shor’s paper kicked off a wave of interest in quantum computing from both scientists and policymakers. Today, universities, governments, and private corporations have invested billions of dollars in the sprawling field of quantum information science.

Shor sat for an oral history with David Zierler of the American Institute of Physics (which publishes Physics Today) in 2020. The following is an abridged, annotated, and lightly edited excerpt from the transcript.

ZIERLER: What are the origins of Shor’s algorithm? What were you working on that led you to realize you had come upon this?

SHOR: Theoretical computer science in the US had, and I guess still has, two main conferences. They’re called STOC [Symposium on Theory of Computing], which happens in the spring, and FOCS [Symposium on Foundations of Computer Science], which happens in the fall. In those days, these were really the Physical Review Letters of people in theoretical computer science. It was really very good for your career to get lots of papers into STOC and FOCS.

So, before the program committee[s] met [to select papers for the conferences], people went around the country giving talks on their results. Umesh Vazirani had a paper in STOC in spring of 1993.¹ He came and gave a talk at Bell Labs sometime before that conference, so it must have been late fall or early winter of 1992. I saw that talk, and I thought it sounded really interesting.

So, after he left, I started thinking about this, and I went to the Bell Labs library and looked up a lot of early papers on quantum computing, like [Richard] Feynman’s , and [David] Deutsch’s , and Deutsch and [Richard] Jozsa’s . There were not that many.

Anyway, I read them, and I started thinking about what a quantum computer would be good for. Of course, this was such a crazy, far-out idea, I didn’t tell anybody about it.

So, for the next STOC, I happened to be on the program committee, and Dan Simon had submitted a paper on what is now known as Simon’s algorithm.² That was really a very good paper, but the STOC committee rejected it.

ZIERLER: What was their reasoning? Why did the committee reject it?

SHOR: It was an incremental improvement on [Ethan] Bernstein and Vazirani , and do we really want another of these crazy quantum computing papers in our conference?

ZIERLER: Crazy, meaning what? Why would they be labeled as crazy?

SHOR: They’re far out. They’re completely impractical. It’s a completely theoretical model which has nothing to do with real life, and nobody understood it. I always regret not bringing it up and jumping up and down and saying, “We have to take this.” But I didn’t. I should have, obviously.

Anyway, we rejected it. So, I started thinking about the paper, and this paper uses periodicity to find an algorithm to solve Simon’s problem much faster than a classical computer could. I knew that periodicity was very important for the discrete log problem,³ and periodicity was used in Simon’s algorithm. So, I started thinking about this, and I came up with a quantum Fourier transform that I thought could be used for discrete log, and I solved a special case of the discrete log, which was actually doable in polynomial time⁴ on a regular computer, which I thought showed real promise. Then, I eventually got to the real discrete log problem.

ZIERLER: How far developed was quantum computing at this point? When you’re talking about things that could not be accomplished on a classical computer, how far along was quantum computing where you know that this would be doable?

SHOR: We didn’t know this was doable. For the first few years after the factoring algorithm, everybody was completely convinced that it was not doable. Anyway, I managed to get a discrete log algorithm in polynomial time.

At first, I didn’t tell very many people about it. I told Jeff Lagarias, and he found a minor bug, which I fixed in my paper. Then I told my boss David Johnson and a couple other colleagues, and then I gave a talk in Henry Landau’s seminar on a Tuesday [in April 1994]. That weekend, I was at home with a cold, and I got a call from Vazirani saying, “I heard you know how to factor on a quantum computer. Tell me about it.”

ZIERLER: Where would he have heard this news?

SHOR: Well, this is a game of telephone. I gave a talk on Tuesday about how to solve the discrete log problem, because I had not figured out how to factor yet. So, somebody at the talk told somebody else, who told somebody else, who told Umesh Vazirani that I knew how to factor on a quantum computer. So, if you look at discrete log and factoring, they’re similar problems, and they’re both used for public key crypto systems. Anytime someone has found an algorithm for factoring, there is a parallel algorithm for discrete log, and vice versa. So when I announced that I had an algorithm for discrete log and explained it at the Tuesday talk, somebody told somebody told somebody told Umesh that I had an algorithm for factoring.

I explained the factoring algorithm to Umesh over the telephone, and then I was invited to give a talk at the Algorithmic Number Theory Symposium at Cornell University in early May. I guess I was invited about a week before it happened, so that was the very end of April, and I flew up and gave a talk. And then, later, Santa Fe Institute had a conference on quantum computing. For some reason, I couldn’t go, so [Umesh] gave a talk on it there. At some point, the science writers started hearing about it, and the news spread very rapidly.

ZIERLER: From your vantage point, what was so exciting about this? Why were people paying attention? What were the promises being offered by this breakthrough?

SHOR: I guess before this, computer scientists were absolutely convinced of the extended Church–Turing thesis, which says, basically, anything any computer can do in polynomial time, a Turing machine⁵ can do in polynomial time. This showed that it might not be true. So, this really shook the very foundations of computer science. Of course, it doesn’t affect any of the real work in computer science going on right now, but computer scientists thought it was interesting for that reason. I guess physicists thought it was interesting because now quantum mechanics might have yet another application. Cryptographers thought it was interesting because factoring is the basis of all the security on the internet, and if somebody can break it, we’re going to have to scramble and replace all these cryptographic protocols.

ZIERLER: What new applications were there for quantum mechanics? Can you explain that a little more?

SHOR: Well, computing. I mean, if using quantum mechanics, you can build a computer that can do things that classical computers cannot. That’s a very important application of quantum mechanics.

ZIERLER: To what extent has that excitement been realized?

SHOR: I guess people are still very excited about quantum computers. I mean, there are not that many problems that can be solved by quantum computers that can’t be solved by classical computers. At least, we haven’t discovered that many yet, but there do seem to be a few—I mean, for molecules, materials design, and actual computing properties of systems that are actually quantum mechanical, they really seem like they’re going to work better once we build larger machines. If you look at what fraction of the world’s computing power the pharmaceutical industry uses in simulating molecules—which the big difficulty of simulating molecules is they obey the rules of quantum mechanics—it’s a fairly large fraction of all the computer power used in the world today. So, if you’re able to do better with quantum computers, then you have a huge market.

This article was originally published online on 7 March 2025.