Peter W. Shor

Zierler:

Okay, this is David Zierler, Oral Historian for the American Institute of Physics. It is August 28th, 2020. It's my great pleasure to be here with Professor Peter W. Shor. Peter, thank you so much for joining me today.

Shor:

Yes, well I'm happy to be here.

Zierler:

Okay. So, to start, would you please tell me your title and institutional affiliation?

Shor:

I'm in the Department of Mathematics at MIT, and I always say my title is the Morss Professor of Applied Math. If you really want to look up the full title, it's on my webpage, and it's two lines long. The Henry Adams Morss and Henry Adams Morss Jr. Professor of Applied Math. I think that's too long to actually put in print.

Zierler:

I can do it right here, because I have your page pulled up.

Shor:

And you should spell Morss right, at least.

Zierler:

And then Committee Chair of Quantum Computation and Quantum Information, or are those your research disciplines as it's listed there?

Shor:

Those are my research disciplines. I am the Committee Chair of the Applied Math Committee, which essentially means I'm the sub-department head for a third of the math department. There are two sub-divisions, pure math and applied math, and I'm the chair of applied math.

Zierler:

Who was Morss? Do you have a special connection with that name?

Shor:

No, this was someone who funded a chair at MIT, and they gave me this chair when I got to MIT because it was available.

Zierler:

I see. Peter, let's go all the way back to the beginning. Let's start with your parents first. Tell me about them and where they're from.

Shor:

Okay. Well, my father was Williston Shor. He was in the Navy for 30 years. He joined the Navy, I guess—he started his education at Harvard, but after two years, he transferred to the Naval Academy, and he became an officer in World War II. After the war, he became-- No, he started working in the Navy as an engineer, and he helped design—the thing that he was proudest of doing was helping design the first nuclear submarines and helping build them. He stayed in the Navy for 30 years, and he was only a captain. There's a rule that after 30 years in the Navy, if you're captain, you have to retire. So, he retired, and he went to work for Bechtel Corporation, working on power plants.

Zierler:

Where did he grow up?

Shor:

That's a good question. His father—I think his family moved all over the Northeast. My grandparents had a vacation house in Westchester—not Westchester—in Putnam County, New York, where they retired to. That's where I know them from, but I think his father was a newspaper editor, and he worked in Philadelphia for a while, I think in New York City for a while, and he actually grew up—gosh, where did he grow up? Where did my grandfather grow up? He grew up in Worcester, Massachusetts, of course.

Zierler:

What was your father's technical education? Did he basically learn on the job in terms of engineering, or did he have formal training?

Shor:

He got a master’s degree, I believe, from MIT, in naval engineering, or something like that. And while he was working at the Brooklyn Navy yard, he took night classes at NYU—I think it was NYU—in, I guess, probability and statistics. I don't know if he actually got a degree there, but he certainly learned a lot.

Zierler:

Was his style as a father and a parent, did he involve you in his work? Did you get a sense about math and science and engineering at all?

Shor:

Well, he used to give me math problems to solve. I'm not sure he actually gave my sister math problems, which shows some kind of this implicit--

Zierler:

Gender bias.

Shor:

Gender bias, yeah. He told me a little bit about his job, but not all that much about it. Actually, when we were in Washington, DC, he was not allowed to talk about his job, and I still don't know exactly what he was doing. My impression was some kind of missile system. He was deeply unhappy working on it—I don't know if deeply unhappy is the right word. He did not want to be working on it. So, the things he did in the Navy were nuclear submarines, sonar, and this top-secret project. The top-secret project was not his favorite thing. My mother told me that he really did not like working on it.

Zierler:

Tell me about your mom, Peter. Where is your mom from?

Shor:

She is from Decatur, Illinois, and her father was an automobile dealer for American Motors. When she was growing up, she went to Wellesley College during World War II. Apparently, she never told me about this, but apparently, she had a summer job defusing, disassembling bombs, which obviously was at least somewhat risky. She learned to fly small planes, and then she went to University of Illinois in Urbana-Champagne and became a psychologist. She worked as a psychologist-- Well, she taught college after that. She got a PhD in psychology and taught at several colleges. I should know which ones, but she was working at a college in Connecticut when she met my father. She quit working, had children, and raised them, and became a housewife.

Zierler:

Where did your parents meet?

Shor:

My father saw an article on her in the newspaper, and so he called her up and asked her on a date. At the time, she was working for—she was doing consulting for various-- I don't know what kind of consulting. Some kind of psychology consulting for various towns. She thought Williston Shore was yet another town that had a job for her. But, no, he wanted to go on a date, and she went on a date, and they eventually got married.

Zierler:

Peter, where did you grow up? Where did you spend your formative years, would you say?

Shor:

Everywhere. Okay, so, I was born in New York City, and we lived in Brooklyn. Do you want anecdotes from when I lived in Brooklyn?

Zierler:

Absolutely. Where in Brooklyn?

Shor:

Okay. I was a short child, and I could not reach the button in the elevator that was the 14th floor. One of my earliest memories was my sister and I, she was probably one and a half or two at the time, and I was three and a half. We were betting on which of the two elevators in the apartment building would come down. Mine came down first, and I stepped in, and Molly refused to get in. So, the doors shut, and of course, I couldn't reach the 14th floor button. I was obviously not quick enough to think to push the door open button. So, I was trapped in an elevator with no way to get where I wanted to go. I don't know what happened after that. My mom says I showed up a few minutes later at the door of our apartment.

She also said that nobody could understand me when I talked, which was more or less true, because I had horrible enunciation, and I think I had a very strong New York accent, which of course, my parents were not used to. I had a babysitter from New York, who was fairly—who took care of me a lot of the time. I must have picked up my accent from her. So, that's the story. I think what must have happened was someone who could reach the 14th floor button got in the elevator with me, and I managed to make myself understood, and he pushed the button for me. So, a few years after we moved to Washington, DC, I was walking to school, and somebody stopped and asked me a question about something or other, maybe directions, and after I said something, he said, "Are you from New York?" And I had no clue as to how he knew. Obviously, it was my accent.

Zierler:

How long were you in New York for?

Shor:

Anyway, we moved to Washington, DC when I was four, and my father worked there until I was 14, when he had to retire from the Navy, when he'd been in it 30 years. So, then, we moved to--

Zierler:

And it was during this time that he was working on the top-secret project?

Shor:

Well, the first part of the time in Washington, DC, he was working on sonar. The second part of the time, he was working on the top-secret project, and I don't know whether there's more—I don't know whether it was just two projects during those 10 years, or there were more of them.

Zierler:

Where in DC was your family? Where did you grow up?

Shor:

Northwest DC. I went to Lafayette Elementary School, which will narrow it down a little bit. They were like, in a very segregated part in DC. There was one black kid in my class the entire time I was in elementary school, and he was the son of the Kenyan Ambassador. But I had black teachers. In fact, I think it was first grade. Anyway, one of those years, my mom went to the school and was absolutely amazed to find that my teacher was black, because I'd never mentioned it. I don't know whether I thought it was unimportant, or I thought she obviously already knew, but it was—what else was I going to say?

Zierler:

Peter, at what point did you start to exhibit gifts in math and science? Was it early on?

Shor:

It was early on. I read all sorts of—I read a lot of science fiction and fantasy, but I also read a lot of popular science books. In elementary school, I remember Asimov's science books very much. There were others, too. Anyway, I was interested in math back then. When I got to high school in California, I took this math exam that the AMS—I think it was the AMS; maybe it was the MAA. Anyway, there's this annual math exam, and people who do well on it are invited to take another exam, and people who do well on that are invited to go to the International Math Olympiad training program, and the top six people are on the US team at the International Math Olympics. I was, I guess, as a junior in high school, I got invited to take the second test, and then I got invited to the training program, and as a senior, I made the team. I was actually interested in math from a fairly young age.

Zierler:

Peter, can you describe how teachers or parents would know that you have mathematical gifts that are sort of beyond being just ahead of your classmates? How would that play out? How would they understand that you were going to be able to go beyond the normal course of education at a regular school?

Shor:

Well, I don't really know if they noticed. I mean, certainly in high school they noticed when I took the-- Yeah, I don't know if they noticed.

Zierler:

But you felt it.

Shor:

Well, I actually was very surprised when I got invited to the US team, because I didn't realize how good I was. I always knew I liked math, and I wanted to go into some area of math or science when I grew up, but I didn't have any idea that I would be on the US International Math Olympiad team, or that I would become really famous for discovering Shor's algorithm.

Zierler:

Do you believe that testing is an accurate means of quantifying mathematical ability?

Shor:

It has some correlation. There's this Putnam exam, which is given in colleges, and many people who do well on the Putnam exam go on to become great mathematicians. Many people who do well on the Putnam exam aren't able to become great mathematicians, and many people who don't do well on the Putnam exam go on and become great mathematicians. So, there is some correlation, but it's not perfect correlation.

Zierler:

Did you know that you wanted to be a mathematician from an early age?

Shor:

Well, I knew I wanted to be a scientist. I guess, when I got to Caltech, I majored in math because it was the easiest thing to do. I was thinking of majoring in physics, but you had to take this lab course, which seemed like a lot of work.

Zierler:

What schools did you apply to for undergraduate?

Shor:

Which schools did I apply to? I applied to Harvard, Caltech, UC Berkeley, a bunch of others. Harvard, Caltech, and UC Berkeley were the three ones I was deciding between.

Zierler:

And why did you choose Caltech?

Shor:

It was small, it was closer to my parents than Harvard, and it seemed good.

Zierler:

When you thought, as a high school student, that you wanted to be a scientist, did you differentiate in your mind being a mathematician versus being a scientist? Were those different fields, or different paths, as you saw it?

Shor:

Well, I mean, actually when I say scientist, I probably mean physics or chemistry. I was sure I did not want to be a biologist, and I knew these were three different disciplines. I don't know that I saw mathematics and physics as more different than physics and chemistry.

Zierler:

So, you landed on mathematics sort of by default when you got to Caltech.

Shor:

Yeah, I did. I did take a number of physics courses. I took the one-year physics course that you needed to do if you were a student at Caltech; I took statistical mechanics, I took the solid state quantum mechanics course—I think that's it.

Zierler:

Many physicists that I speak to started out in math, and when math got too abstract, that's when they switched over to physics. Did math ever get too abstract for you, not in terms of ability, but in terms of interest?

Shor:

Well, I went into applied math/computer science rather than pure math when I was in graduate school. I applied to the math department in combinatorics, which was then and still is a subfield of applied math at MIT. Then, I went on and took some computer science courses, went to a computer science conference, solved a few computer science problems, and decided to write a PhD in what was essentially computer science, although I also solved an open problem in probability at the same time.

Zierler:

Was there a senior thesis at Caltech?

Shor:

No. At least, I didn't write one.

Zierler:

By the time you had graduated from Caltech, how well-defined were your interests? Did you know that you wanted to pursue a more applied track in mathematics?

Shor:

No, no I didn't. I was interested in combinatorics. I had actually done a summer undergraduate research fellowship at Caltech, where I solved a problem in combinatorics, and published my first paper.

Zierler:

I'm not familiar with that word. What is that?

Shor:

Combinatorics?

Zierler:

Yes.

Shor:

Well, it's basically the parts of discrete math that don't fit into another discipline of mathematics. So, you have graph theory, you have enumeration, you have probabilistic combinatorics. So, properties of random graphs would be in probabilistic combinatorics. How many edges do you need to add to a random graph before most of the nodes are connected is one of the foundational results in that area? And we also had graph theory and algebraic combinatorics. In the 1970s and 1980s, combinatorics was kind of seen as a stepchild of mathematics, an inferior discipline.

I remember attending the International Congress of Mathematicians in 1986, when I was doing a postdoc at Berkeley, which was where it was held. I was in the auditorium listening to a lecture on graph theory by either Paul Seymour or Neil Robertson, his collaborator. Anyway, one of the two people in front of me said to his companion, "This is the first nontrivial result in graph theory I've ever seen." For many, many years, Princeton had an assistant professor in combinatorics, who would never have gotten tenure, and they used him or her to teach the combinatorics courses. Then, after three or four years at Princeton, they were denied a promotion, and Princeton found another assistant professor in combinatorics. They finally hired a combinatorist, who was Paul Seymour. He was the person who gave that lecture at the International Congress of Mathematicians, that was the first non-trivial result in graph theory that the mathematician in front of me had seen.

Zierler:

Peter, how big a deal were computers as an undergraduate at Caltech? Were people talking about the possibilities of computers in mathematics, or was it too early at that point?

Shor:

I don't really remember. I'm sure people were talking about it back then, but as an undergrad, I didn't hear anything about it.

Zierler:

Did that change for your graduate work?

Shor:

Well, the proof of the four color theorem, which—when was that? The proof of the four color theorem was in 1976, when I was in high school. So, obviously, that was when people started thinking about using computers in mathematics.

Zierler:

Why MIT? Did you give any thought to staying on at Caltech? Were you given advice that it was good to go elsewhere?

Shor:

Well, MIT was the best place in the country for combinatorics. So, I went there. Most places, combinatorics was treated as an unimportant subfield in mathematics, and there were only one or two combinatorists there. At Princeton, for example, which was probably one of the more extreme examples. But at MIT, there were three professors in combinatorics, and a bunch of tenure track assistant professors, and post docs, and graduate students, and a lot people there. So, if I wanted to go into combinatorics, it was the obvious place to go.

Zierler:

Being the best place, did you have a particular professor in mind that you wanted to work with?

Shor:

Well, maybe Richard Stanley.

Zierler:

What was his research? What was he working on at that time?

Shor:

He worked on algebraic combinatorics. There was also Dan Kleitman, who worked on graph theory and probabilistic combinatorics. He was another professor I would have been perfectly willing to work with.

Zierler:

What's the curriculum like for this program? Is there required coursework before you get into your dissertation, or do you really start right into the research?

Shor:

You mean, MIT?

Zierler:

Correct.

Shor:

At that time, you had to take 11 courses, but basically you spent your first year taking courses. You were expected to take three each term, so that ended up being six. What was I doing? It must have been Danny Kleitman, one of the combinatorists, encouraged me to take some computer science courses, the very mathematical side of computer science, theoretical computer science. I did, and I liked them, and then I went to Washington, DC to see one of the two annual theoretical science conferences. I saw a talk there which had an open problem in it which I could solve.

The third thing was, at that time, Bell Labs had a very good relationship with Danny Kleitman, and they took, I guess, combinatoric students as summer interns. I went to Bell Labs, and I solved a combinatorics problem there, but I also saw there were people there working on bin packing, which was, what do you call it, a computer science problem. I started working on it, and that became my thesis. My advisor was Tom Leighton, who was a coauthor of some of these bin packing papers. I ended up doing theoretical computer science.

Zierler:

Was Bell Laboratories a good experience for you?

Shor:

Yeah, it was a great experience.

Zierler:

I know from the physics side of things Bell is famous for supporting basic science that had nothing to do with its own corporate interests. I'm curious what its interests were for supporting mathematics.

Shor:

Well, they also supported basic mathematics in fields which were at least adjacent to their interests like, well, they had two number theorists there. Number theory is very much related to error correcting codes, which are essential for communication, and also related to cryptography. They had a bunch of combinatorists there, some great combinatorists there, too, and they had probability theorists. So, when I was there, the system was that you have an annual review, and you were expected in your annual review to either have done some great research, or to have done something that was worthwhile for the company, or both. If you were there, and you were working on basic research, and you didn't get any amazing results for a year or two, they would try to push you gently towards working on something that was more relevant to the company. If you didn't do that, you were let go. I know at least one person who was let go for those reasons, but they got a good job at a university, and presumably are perfectly happy.

Zierler:

Where did you fall on the spectrum of that kind of talk?

Shor:

I was mostly doing great research that, actually, some of it might have been relevant for the company. With Ken Clarkson, I discovered a very—what do I want to call it? I discovered a way of finding algorithms for constructing geometric objects, which was very widely applicable. I just got the test of time award for the symposium of computational geometry for my papers with Ken Clarkson on that. This was the first Test of Time Award, and it was split between my paper with Ken Clarkson, and another paper by two other people. So, my work was presumably seen as one of the two best results in computational geometry that appeared in this annual computational geometry conference, which has most of the best work in the field, I guess, in the first few years of the conference. That work was definitely very widely applicable. I don't know if Bell Labs used it specifically, but it's a widely applicable algorithm. It's not specifically for a problem that arose at Bell Labs.

Zierler:

Peter, can you talk a little bit about how you went about developing your dissertation topic, in terms of identifying issues in the field that were both relevant to many people, and personally interesting to you? How do you go about developing a topic and making an identity for yourself in the field, through your dissertation?

Shor:

Well, I went to a conference. I went to a whole bunch of talks. There was this one talk on bin packing, which was—now, I'm trying to remember the order. I had been at Bell Labs the previous summer, where some other people, including Tom Leighton—who was visiting from MIT—and some, I guess, interns in the computer science center of Bell Labs—rather than the math center of Bell Labs—were working on bin packing. I ate lunch with them, so I learned about it. Then, I went to this conference where they presented their results, and I saw the paper, and I started thinking about it and working on it, and solved this bin packing problem, which also happened to solve this open problem in probability theory, that it just happened that a professor at MIT had done some previous work in. Of course, you pick any problem in probability theory, there's possibly some professor at MIT who has done some related work.

Zierler:

What is it about probability theory that would suggest that so many people in the field have touched on it?

Shor:

Well, it's very widely useful. This is a problem in computer science that looks—you have a random distribution of item sizes that are uniform between zero and one, and you want to pack them in bins of size one, and the questions are: how much is left over? How many extra bins do you need? So, total volume of the items in the optimal packing, and how many extra bins do you need in the optimal packing? You can ask these questions, and it turns out—well, I said, for the optimal packing, and then what are good algorithms that come close to the optimal packing? Some easy algorithms do very, very well. Just put the item in the bin that it fits best in. That's related to this open problem in probability theory, which I didn't actually know was an open problem until I had solved it.

Zierler:

Who was on your thesis committee?

Shor:

Well, Tom Leighton, Charles Leiserson, and I don't remember. So, of the three people who started out on my thesis committee, Tom Leighton was-- My thesis is on my webpage, so I can look it up. Why don't I do that? Okay, so the three people on my thesis committee Dan Kleitman, Tom Leighton, and Charles Leiserson. I started out with a thesis committee of Mike Sipser, Gary Miller, and Tom Leighton, but by the time that I defended my thesis, Gary Miller was no longer at MIT, having failed to get promoted. I don't know why Mike Sipser wasn't on the thesis committee, because he's still at MIT. So, it was Dan Kleitman, who was one of the two combinatorics professors I was thinking of working with when I got to MIT, and Tom Leighton was my advisor, and Charles Leiserson, who was a last-minute replacement for Gary Miller, because Gary Miller had left.

Zierler:

Peter, at this time, what were some of the most exciting promises that computers held for mathematics? Or was it the other way around? Was the idea that mathematics was going to improve computers, or computers were going to improve mathematics?

Shor:

Well, so what I worked on in my thesis and after my thesis was using mathematics to design good algorithms for solving problems on computers.

Zierler:

What kind of problems? What were you thinking about?

Shor:

Well, I had a post doc at Bell Labs—not Bell Labs. I had a post doc at UC Berkeley, and this was at the Mathematical Sciences Research Institute, which is a little bit like KITP [Kavli Institute for Theoretical Physics] for math. They had a year-long program on computational geometry, which I was a post doc at.

There is something called a Delaunay triangulation, which is a triangulation with triangles with nice angles—there is a much more technical definition—but we found an algorithm for computing the Delaunay triangulation of a convex polygon quickly. Also, we found an N+M time algorithm for finding the maximum entry in an N by M matrix, which has a special monotone property, which is the best possible, and algorithms for finding convex halls in computational geometry, and algorithms for-- I mean, I know I did some work on algorithms for routing problems, but I don't remember exactly what happened with them. I can look on my webpage. Okay, so mainly computational geometry problems.

Zierler:

How long were you at Berkeley for the post doc?

Shor:

One year. Just for that single year program at Mathematical Sciences Research Institute.

Zierler:

Right. And were you thinking at that point—to foreshadow to AT&T, did you specifically want to work in that kind of environment? Were you considering academic appointments as well?

Shor:

I considered academic appointments, yeah. I applied to a whole bunch of universities, but I worked at Bell Labs for a summer, so I went there.

Zierler:

Did you ever consider, even briefly, pursuing a career in industry? As computer companies were ramping up, places like Apple, did you ever think about pursuing that kind of a career?

Shor:

Not really. I was pretty happy at Bell Labs.

Zierler:

How did that opportunity come together for you?

Shor:

You mean, Bell Labs?

Zierler:

Correct.

Shor:

I guess, they offered me a job and I took it. I mean, they knew I was on the market, because I'd been there. IBM Research also offered me a job, and I guess Bell Labs seemed better. And then a whole bunch of, well maybe not a whole bunch, at least one or two universities offered me a job. But actually, at the time, theoretical computer science was not seen by either people at universities or people in industry as anything practical. So, people who were writing programming languages, or developing graphics, artificial intelligence, all looked down on theory at universities. Of course, this attitude was completely reversed after Google, using theoretical computer science, found its searching algorithm, and became an enormous company. But, in the early days of computer science, and still, even in the 1980s, the perception of theory was these people are proving theorems, but not actually doing anything practical. I guess Bell Labs knew this was absolutely wrong, because the theorists of Bell Labs actually worked on helping develop practical algorithms.

Zierler:

Practical in what capacity?

Shor:

Okay, so I'll tell you a problem that I helped on—suppose you want to route optical fibers to the houses, and optical fibers are expensive, and maybe not everyone is going to pay for it. Maybe some neighborhoods have more rich people in them who would be more willing to pay for optical fibers than others. What's the best way to hook the optical fiber to them? This is a very practical problem, and it's related to network flow, which is an area in which a lot of theoretical computer scientists have worked, and found very good algorithms for solving—well, maybe not for solving the exact same problem as the problem that Bell Labs wanted solved, but solving very similar problems.

The theoretical algorithms that can be proved to work for these theoretical problems will actually work really well for these practical problems, even if they can't be proved to work well. So, that's one thing. I guess, another thing is back then we had a phone network, and every so often someone with a backhoe would go out and cut one of our main cables. What we would like is, if this cable is cut, to be able to very quickly reroute all the calls, and not have a long outage. So, maybe we drop a few calls, but ideally, we wouldn't drop any calls, even though someone cuts one of these main fiber backbones in the country. How do you do that? Well, theoretical computer science helps.

Zierler:

Can you describe your research agenda when you started? Did you essentially work on the issues that you wanted to, or did you plug into extent projects, and you were expected to contribute in that way?

Shor:

Well, both. I mainly worked on the projects I wanted to, but occasionally someone with a real problem would come up, and a bunch of us would sit down and talk with them and try to figure out exactly what kind of algorithm they wanted, which isn't always easy. I wasn't the best person at getting the algorithm specifications out of the practical people, but there were other people I worked with who were really good at this. Once we got it out, we tried to figure out which of our tools that we knew about would help solve it and apply it. Some people actually wrote software in the math center, but I managed not to have to do that. I wrote programs for exploring—what do you call it? I wrote programs for exploring, I guess, mathematical problems, but I didn't actually write any software that—I don't know if anybody at the math center wrote any software that would be used in production, but they did write prototypes. I never had to do that.

Zierler:

Peter, over the course of your tenure, the growth of computational power was exponential. I'm curious how this might have influenced your work, or the kinds of things you were able to accomplish.

Shor:

Well, it really—what do I want to say? It wasn't like A.I. where all of a sudden you go past some thresholding computer power, and suddenly you can do things which were totally hopeless five years before, which happened with deep learning and A.I, but it definitely affected it. The growth in computer power was so gradual that you didn't even really notice it, like this proverbial frog being boiled.

But people look back every so often and there was one—you can look back and there was one time I remember—linear programming is a very powerful tool. Someone had done an analysis of the improvement of linear programming, and faster computers had sped up the time to solve linear programs by a factor of a million over the last however many years, but the algorithms had also improved it, and had sped it up by another factor of a million. So, this shows that theoretical computer science isn't actually useless. There was really-- When I got my PhD people in computer science departments really were not all that enthralled with theoretical computer science because it was seen as not practical, which a lot of it isn't, but there's a lot of it that is.

Zierler:

On that latter point, was there a particular project or breakthrough that turned people around to recognizing the usefulness of theoretical computer science?

Shor:

I think it was Google.

Zierler:

This happened during your time. You saw this happen in real time.

Shor:

Yeah. I don't remember when Google was started, but it was certainly during my career. People are absolutely convinced of the usefulness of theory now. The same thing happened to combinatorics. Combinatorics was seen as a backwater of mathematics that wasn't all that exciting, where people were playing with, I don't want to say insignificant problems, but problems that were, maybe some problems that weren't very deep, and they weren't in the central mainstream of mathematics, so they wouldn't affect mathematics that much. But now, combinatorics is seen as part of the mainstream of mathematics. Part of it is that deep combinatorial results actually have turned out to be important for mathematicians and it is not the case anymore that if a mathematician has a combinatorics problem, they can just solve it. On the way to proving their great mathematical theorems, they may actually need some really powerful tools from combinatorics to do this.

Zierler:

Peter, what are the origins of Shor's algorithm? What were you working on that led you to realize you had come upon this?

Shor:

I was working on Shor's algorithm. I set down to figure out how to solve the discrete log problem on a quantum computer, and I did it. That was Shor's algorithm. You probably want to know the background of why I set out to do that.

Zierler:

Yes.

Shor:

You're familiar with BB84 and Charles Bennett.

Zierler:

Sure.

Shor:

So, Charles Bennett gave a talk at Bell Labs sometime during the 1980s, I think, on BB84. I went to it, and I was interested enough that I looked up some of the relevant papers, but I didn't see any way to prove the security of BB84. So, I stopped working on it, and then sometime in 1992—I'm going to have to Google something to get the timeline right.

Zierler:

Sure, please.

Shor:

Okay, so theoretical computer science in the US had, and I guess still has, two main conferences. They're called STOC, which happens in the spring, and FOCS, which happens in the fall. You can tell which is which by the initials. STOC is spring, and FOCS is fall. Anyway, in those days, these were really the Phys Rev Letters of people in theoretical computer science. People in physics departments—the story is that they determined tenure by counting how many Phys Rev Letters you have. I don't know if I believe that—in fact, I certainly don’t. STOC and FOCS were the equivalent things 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 met, 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. So, I saw that paper, and 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 Feynman’s, and Deutsch's, and Deutsch and Jozsa. There were not that many of them.

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. I always regret—I could have jumped up and down--

Zierler:

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

Shor:

It was an incremental improvement on 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. So, I regret not—at the end of the meeting there was a chance to bring up papers that we might have rejected by mistake. 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 discrete logs—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—not the quantum Fourier transform that we teach today, but 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. I'll get to that later. It was pure blue sky back then. Anyway, I managed to get the factoring algorithm on in poly—a discrete log algorithm in polynomial time. Now, maybe, I should tell you the story of what happened. I did this sometime in April of 1994. I don't believe I have any records of exactly when I did this, because I only sent a small amount of my computer files to MIT, and I'm not at all sure that any of them actually had the record for when I discovered it. Anyway, I certainly discovered it after April 1st, because on April 1st that year, there was an April fool’s joke that appeared on, I think, netnews, about Russia having built a quantum computer. It was based on the many worlds theory, that they tried a random factor, and if it didn't work, they exploded a nuclear bomb on Moscow. So, in the only world where Moscow survived, the quantum computer had factored. So, it was after April 1st, and it was certainly before the end of April, because everybody knew about it by the end of April.

Anyway, on a Tuesday in April, I gave a talk about it. 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, a couple other colleagues, and then I gave talk in Henry Landau's seminar. So, Henry Landau ran a seminar at Bell Labs every Tuesday, and I gave a talk on a Tuesday. That weekend, I was at home with a cold, and I got a call from Umesh 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? This was just buzzing around at this point.

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 anytime someone has come up with—they're both used for cryptographic, public key crypto systems. Anytime someone has found an algorithm for factoring, there is a parallel algorithm for discrete log, and vice versa. It turns out that there's not a recipe for going from one to the other. You have to go back and look at the algorithms, and look at the techniques, and apply them to discrete logs, and vice versa. So, they're very similar problems. Factoring is the most famous of them, of course. 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. So, I have no idea how it mutated.

Zierler:

Word was definitely spreading.

Shor:

Word was definitely spreading. Anyway, I explained the factoring algorithm to Umesh over the telephone, and then I was invited to give a talk at the ANTS, the Algorithmic Number Theory Symposium at Cornell University in early May, and I can figure out exactly when that was. Okay, the conference was in Cornell, May 6th-9th, and I heard about it—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. I should say that before this, quantum computing was a field where there were only a couple dozen researchers. Everybody else thought they were crazy, and some of them really were crazy. There was a talk at the Santa Fe conference, at the Santa Fe Institute, where Umesh Vazirani gave a talk about my algorithm sometime that summer. For some reason, I couldn't go, so he 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.

Zierler:

When you say, “might not,” what's the difference between might not and definitely not?

Shor:

Well, we don't have a quantum computer yet. There are computer scientists who still believe in the extended Church-Turing thesis and say that this proves that quantum computers are going to fail. At least—there are computer scientists convinced that quantum computers are going to fail, and I am just assigning this reasoning to them without any real evidence—I'm sure they would say, this is not their reasoning, but it probably is at some level. So, quantum computers-- This was a blow to the basic foundations of computer science, which of course, 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.

Zierler:

Yeah. Just so we have our terms straight, if the idea is that most classical computers can do the things that quantum computers can do, what exactly is the difference between the two, practically?

Shor:

Well, if there are any problems that quantum computers can do that classical computers can't, and if there are people who will pay large amounts of money for solving these problems, then quantum computers have an enormous—could possibly make you an enormous profit.

Zierler:

Possibly, though. That has not been realized yet.

Shor:

That has not been realized. We don't have quantum computers yet. We have prototype computers. For a real quantum computer, you would probably need thousands of logical qubits. To get thousands of logical qubits, you would need hundreds of thousands of physical qubits, because you need to-- Quantum computers have the problem that any small amount of noise in the quantum mechanical components can completely disrupt the computation. So, you need to make sure that they're error corrected. I should tell you about that at some point, but right now, if you want to do fault-tolerant quantum computation, we theoretically know how to do it, but there's an enormous overhead involved for the size of problems that we want to solve.

For every logical qubit, you need hundreds or thousands of physical qubits. So, the biggest quantum computer built so far has, I believe, 53 qubits, which isn't even enough to make one logical error corrected qubit. The biggest quantum computer we have so far is very noisy. So, we have to actually get something that works. We have to reduce the noise by one or two orders of magnitude, and we have to increase the number of qubits from 50 to thousands. If we do that, well that's still what they call noisy intermediate scale—I cannot remember this acronym. Okay, so the acronym is NISQ, and I think it stands for Noisy Intermediate Scale Quantum computers.

We have algorithms that we believe will work on large-scale quantum computers, which have good error correction, but we're still looking for algorithms that will work and are useful for these Noisy Intermediate Scale Quantum computers. Maybe, we can say we have NISQ machines now, but I would really have to call them still prototypes. They're not going to do anything useful until you get at least a few hundred qubits, and much less noisy. Even then, they probably won't do that much that's useful.

Zierler:

So, the barriers to true quantum computing, it sounds like it's really all of the above. There are theoretical limitations, there are budgetary limitations, there must be political limitations, in terms of simply to support the cost of this endeavor requires the government to be involved. What would the cost be on something like this, to achieve true quantum computing?

Shor:

Probably billions of dollars.

Zierler:

Right. So, on the order of an SSC, or an International Space Station; a major, major project.

Shor:

Right. But, you know, the US government is putting a lot of money into quantum computing right now, probably for cryptographic reasons, but possibly for other reasons as well.

Zierler:

So, the theoretical barriers, obviously, those are not insurmountable. Otherwise, the government would not be pouring these resources in, if this was not achievable.

Shor:

Right now, we don't see any insurmountable theoretical barriers. It's possible that we could come across some later, but maybe not.

Zierler:

How energy intensive is quantum computing? What do you need, in terms of just the power required to run these machines?

Shor:

Okay, well, the main energy cost is going to be the refrigeration. So, you're going to be doing stuff—well, if you're doing a superconducting quantum computer, you'll need a dilution refrigerator. Dilution refrigerators work pretty well, but if you are generating heat in a dilution refrigerator, it requires an enormous amount of power to cool it. I actually should know the factor, but if your quantum computer is in a dilution refrigerator, and it generates milliwatts of heating, you need several orders of magnitude more power to cool this. So, dilution refrigerators, just taking an object and cooling it down to within fraction so of a kelvin of absolute zero, dilution refrigerators can do that without that much energy cost. But, if the object you're trying to cool down is generating heat, then you have to expel all this heat. Each milliwatt of heat requires an enormous factor of watts to actually cool it. I don't have a handle on what the fraction is, and it's also quite possible that we'll get better dilution refrigerators which have smaller multipliers.

The other thing is, as far we know, there's no real fundamental reason to believe that there is an absolute—well, there's an absolute minimum for the amount of energy it does to do computation, but that's many orders of magnitude less than the amount that our chips are taking right now. So, this is something that's really unknown. But, certainly, we hope that the amount of energy taken for a quantum computer will be much less than the amount of energy taken for the LHC.

Zierler:

Peter, you mentioned cryptography. I wonder, what about other sectors, like healthcare? Certainly, quantum computing would do wonderful things for healthcare, no?

Shor:

Right. Drug design is something which it almost certainly would be very useful in. I don't think it's going to solve all of our problems instantly, but it will certainly make them much more tractable. You may not actually need that large quantum computers to figure out what makes high-temperature superconductivity work, and if you figure out what makes high-temperature superconductivity work, maybe you could design better high-temperature superconductors, because right now we have no clue as to—you can guess the physical equations that a high-temperature superconductor operates on, and now you have these equations of state. You want to say, well, these are the properties of these equations of state that will make the materials superconducting. We have no idea how to get from the equations of state to whether something is superconducting right now. Maybe we could do that if we have a quantum computer.

Zierler:

Do you think you'll see true quantum computing in your lifetime?

Shor:

Well, it depends on what my lifetime is. If I live to be 100, I think there's a pretty good chance that I will be. If I only live to 75, then probably not.

Zierler:

When that happens, do you think it's going to be a gradual change, or is there going to be one big day that's headline news. We've done it. Here it is. Quantum computing.

Shor:

It's going to be a gradual change. First, we'll get quantum computers that are large enough to do something useful, but won't break RSA, and will only help marginally in drug design. A few years later, we'll get larger quantum computers, which will do better with drug design. At some point, quantum computers are going to start breaking RSA cryptosystems, but the first time it happens, it might take days on a quantum computer to break one code. So, I'm sure the NSA has one large number that they would pay, I don't know, a billion dollars to factor. But then they also have millions of other large numbers that they'd like to factor, too. If you factor one a day, it's going to take you a very long time to get through that list. But, of course, as quantum computers get cheaper and bigger, they'll do better at breaking codes.

Zierler:

Peter, when did you decide that you wanted to return to academia?

Shor:

When Bell Labs started falling apart. I actually—well, I guess my daughter was about to go into kindergarten then, and I thought back at my own life, how moving around from New York to Washington, DC—well, basically moving from Washington, DC to California was not all that fun. So, I thought maybe we should move and leave Bell Labs before she starts school. And, well, I guess we did.

Zierler:

You saw the writing on the wall at Bell Labs before the actual breakup started.

Shor:

Well, I left AT&T Labs in 2003. AT&T Labs did not actually—I would say the year AT&T Labs completely fell apart was when my former boss, David Johnson, was fired—or let go, I should say. He was only six months from being able to retire with his full pension then, and I'm sure he got a very good retirement payout, but he—what was I trying to say? Yeah, so I left nine years before it totally fell apart. I could have stayed longer, but I figured this was the right time to leave.

Zierler:

Other than the bigger problems affecting the company, you were happy there. It was still a good environment to do your work.

Shor:

It was still a good environment when I left, yeah. But I could see the writing on the wall. I actually thought it would fall apart much earlier than it did. I left nine years before I absolutely had to. I thought it would only last four or five more years, but I was wrong.

Zierler:

Did you feel, over the course of your time there, that you were still pretty well integrated within the academic mathematical community?

Shor:

Yeah, I was. I went to math conferences; I went to computer science conferences. I actually advised two graduate students at NYU. I wasn't their official advisor, but their official advisor had left for Israel, and there was no one there doing computational geometry. I took over, and they both got great theses and good jobs, so I'm pretty happy with that. A lot of this was due their former advisor and due to them, but I'm pretty happy with how everything went.

Zierler:

You must have been recruited over the course of your tenure at AT&T to come work at a university.

Shor:

Yeah, I was.

Zierler:

And this process continued until you decided to take it seriously at some point.

Shor:

Well, yeah.

Zierler:

The work that was going on at MIT, I assume, was compelling to you. Was that one of the factors that convinced you to join MIT?

Shor:

I think location was a big thing, and I don't know. I mean, my choices were between Princeton, NYU, Yale, and MIT, and I think they all would have been good choices.

Zierler:

So, why MIT in the end?

Shor:

Well, I think MIT had good quantum computing people, and I don't know. I like Boston. I don't know if I particularly would have liked New Haven, Connecticut, or whatever.

Zierler:

Peter, were you looking forward to the prospect of teaching? Had you done much teaching before this?

Shor:

I hadn't done much teaching, and it took me a while to get the hang of it. I'm still not a great teacher. I didn't think that teaching was all that bad. I thought teaching wouldn't be all that bad, and I actually like teaching. Maybe I don't like teaching every single term, but I certainly would like teaching at least once a year.

Zierler:

In general, do you prefer teaching undergraduate or graduate courses?

Shor:

Good question. I like them both.

Zierler:

They're very different, though.

Shor:

They're very different, yeah.

Zierler:

What are your favorite courses to teach undergraduates?

Shor:

I haven't taught that many different courses. I like teaching the first quantum computing course, which is a beginning graduate course, which a lot of undergrads take. I like teaching the seminar in information theory. MIT has some courses which are designed to teach the undergraduates how to communicate, so in the seminar in information theory, they give half the lectures. I really like teaching that one. The other courses I teach are discrete math, which are more low-level than either of those and not as much fun. Is that it? I must have taught other courses. That's more or less it.

Zierler:

Are most of the students you teach looking to use their mathematics education and apply it in a more industry or business kind of career, or are most of them interested in pursuing these questions at the graduate and professional level?

Shor:

Some of each. Maybe the majority of them are interested in some kind of industry or business career, but a lot of them are going on to graduate school.

Zierler:

Who have been some of your most successful graduate students during your tenure at MIT?

Shor:

Good question. Let's see. A lot of them have been in the physics department, where I wasn't their actual official advisor. Matt Coudron was my advisee, and he is doing very well. Let's see, I'm trying to think. There are a whole bunch of Physics department students who I essentially co-advised, who are doing great. So, these are Daniel Nagaj, and David Gosset, and Stephen Jordan. Yeah.

Zierler:

When you moved over to MIT, did you see this as an opportunity to take on new research projects, or were you looking to continue on what you had been doing previously.

Shor:

I was more or less looking to continue on what I was doing previously.

Zierler:

In terms of an intellectual environment, did it matter much to you where you were?

Shor:

I like MIT better. There are many more people who are interested in what I'm doing here than there were at AT&T Labs.

Zierler:

What's the culture like in terms of collaboration? Just because there are people that are doing things that are interesting to you, what's the culture in terms of interacting with them? Is it informal? Is it lunchtime kind of meetings? It is papers and presentations? How do you go about interacting with your colleagues at MIT?

Shor:

It's mainly papers and presentations; some lunchtime meetings, I guess that's—yeah.

Zierler:

Peter, I don't want to talk about every single one of the awards. That would take quite a bit of time. I am curious, though, particularly with the Dirac Award in 2017. Can you reflect a little on how you work has advanced theoretical physics, and perhaps, looking the other way, how have advances in theoretical physics been useful to your work?

Shor:

Well, I guess quantum information is actually starting to be used in sensing and various other things. The most accurate clocks are using some ideas from quantum information right now. There is also this black hole quantum information question. I think maybe the most significant use of quantum information in terms of black holes was the AMPS [Almheiri, Marolf, Polchinski, Sully] paper. You've heard of that. That used quantum information to show that Susskind's idea of complementarity wasn't really consistent with ideas of quantum information. So, that shows that the paradigm for how people thought information would get out of black holes and believed for the last however many years really had some problems. So, they started thinking about what to do about this, and I don't know if they have any solutions yet. It certainly also-- People in AdS/CFT are using quantum information all over the place, and I have no idea whether—I don't know how to evaluate their papers.

Zierler:

This does raise the question of the difference between quantum information and quantum computing. In the way you're speaking, it sounds like quantum computing is still in a prototypical stage, but quantum information is here in real time, so far.

Shor:

Yeah. Well, quantum information as a tool for investigating in theoretical physics has proved very useful.

Zierler:

How do we have quantum information without quantum computing?

Shor:

Supposedly there's a map. AdS/CFT is correspondence between a conformal field theory and an anti-de Sitter theory. A theory of gravity in an anti-de Sitter universe in one more dimension. So, there's a map between the CFT and the AdS theory. You can think of this map as a quantum channel, and you can use techniques that you have applied to quantum channels to, I guess, analyze what might be the properties of this map. You know some properties of this map, and you can use the theory of quantum channels to show that they imply other things about this map. People are doing that. Of course, this all depends on the AdS/CFT correspondence being correct in some sense. It's probably correct for some universe. I don't know whether it's our universe. This is telling us interesting things about the AdS/CFT theory, and what other things can you say about quantum information?

So, one thing about quantum information is the capacity of quantum channels. You can show that if you have entanglement, the capacity of the channel can be much larger than what you thought it would be classically. Just now, people have demonstrated experimentally that this is true. So, that's interesting. How can you use quantum information? Another possible use of quantum computation, something, is you can think of quantum computing as made up of a quantum circuit which has little quantum gates in it, and now you can ask—suppose you don't want to compute something, but you want to use these quantum gates to measure something—how would you use quantum computation and interference techniques to make better measurements on something? People are certainly looking at that and writing lots of papers about it. I don't really know where the state of the art is, but I think it's progressing faster than quantum computing in terms of getting practical results.

Zierler:

Peter, I'm struck by your phrasing, “our universe.” Might that suggest that you're open to the possibility that it might not be the only one?

Shor:

Well, I was thinking of an imaginary, hypothetical universe, as opposed to our universe. The AdS/CFT string theorists certainly have a universe in mind when they're talking about AdS/CFT, and CFT theory and quantum gravity. This presumably has some laws of physics, but nobody has ever figured out how these hypothetical laws of physics could actually be made to correspond to the laws of physics in our universe. I think it's very likely that they cannot be. All this AdS/CFT stuff is about purely hypothetical universes that exist in theory, but don't exist in practice. I wouldn't say it's a different universe in practice. I would say it's an imaginary universe.

Zierler:

Part of the criticism in that regard is that many people say that because of this, string theorists really belong more in math departments than in physics departments.

Shor:

They wouldn't survive in the math departments. They have to prove theorems. They don't prove theorems. Maybe they write things that they call theorems in their papers, but they're not real proofs.

Zierler:

What's the distinction? What makes a real theorem?

Shor:

Well, a real theorem doesn't have any hand waving in it.

Zierler:

Well said. Peter, just to bring the narrative up to the present day, what are some of the endeavors you've been working on in recent years?

Shor:

The thing I'm working on right now is—one of the things I've been working on is that I posted a paper to the archive that has made absolutely no impact on the string theorists. I shouldn't say string theorists, the people who investigate this AdS/CFT area, is a paper, which I think shows if outside of the event horizon, or outside of the stretched events horizon. In other words, if more than a few microns away from a black hole, the laws of physics look like the laws of physics we know about, then the strong scrambling conjecture for black holes has to be wrong. So, physicists believe that black holes scramble information. So, if you throw a dictionary into a black hole, the contents soon get dissipated all through the black hole, and they cannot be recovered. They cannot be recovered locally from the spot where you threw the dictionary in.

I have a paper which I posted to the archive and would like to eventually write up and submit to a journal, that says if you believe that physics, as we know it holds, except for really close to the event horizon, then the scrambling time, or the time for, I would say, strong scrambling, is much larger than their conjectures. There's something called weak scrambling and strong scrambling, and they don't really distinguish between them, and they seem to think that the strong scrambling time is small, and I think all they've shown is there's evidence that the weak scrambling time is small. Not many people have paid that much attention to my paper.

Another thing I'm working on right now is a cryptographic protocol for quantum money. Quantum money would be quantum state which you can verify. So, if somebody hands you this quantum state, and you have a quantum computer, you can put your quantum state in the quantum computer, and say, yes, this is a valid quantum money state. But without knowing the secret that the person who made the quantum state used to make it, you cannot duplicate it. So, if you have a dollar bill quantum state, then you could verify that it really is a dollar bill, but you cannot make two states which will pass this test. So, I'm working on this new quantum money protocol. I wrote a paper which came up with the first quantum money protocol that hasn't been broken so far, but this new one is going to be based on lattice problems, which are much more strongly believed to be secure than the hard problem with my original quantum paper, which was kind of an ad hoc problem about knot invariants, which nobody has broken yet, but there's no theoretical reason that it couldn't be broken.

Zierler:

This is a feasible goal, you think?

Shor:

Yes, I actually think I have—well, it's completely infeasible until we develop quantum computers that can hold—I should say, it's completely infeasible for use as quantum money until we can develop quantum computers that can hold quantum states for more than a few hours. But it's a feasible goal to come up with this theoretical protocol. In fact, I think I have the theoretical protocol. All I have to do is a bunch more calculations to show that it has the properties I claim it has, and I'm writing this paper right now.

Zierler:

Peter, for the last part of our discussion, I'd like to ask you a few broadly retrospective questions about your career and contributions, and then we can end with some forward-facing questions. First, I'd like to ask you, are the questions you have asked over the course of your career, have they changed, or have they more or less stayed the same, the kinds of things that you're interested in?

Shor:

They've changed, I guess.

Zierler:

In what ways?

Shor:

Let's see. Well, when I started working on quantum computing, one of the things I did was look at the field of classical information theory and start working on the corresponding quantum problems. So, how much information can you send over a quantum channel, and what extra resources could you have that will help you send it? The questions in the field of information theory are really quite different than the questions in fields of math, or questions in fields of computing. So, this was some kind of change. If you're asking whether-- Mathematicians tend to group themselves into problem solvers and theory builders, and I've turned from more of a problem solver to more of a theory builder.

Zierler:

What do you think accounts for this transition?

Shor:

Good question.

Zierler:

Is it age? Is it wisdom? Is it energy? What do you think makes for this transition?

Shor:

I think part of it is age and wisdom, and also the field I'm working in has more room for theory building than the ones I was working in earlier.

Zierler:

Are there some questions that remain as open as when you began your investigations at the beginning of your career? Either theoretically or technologically, are the question marks in certain areas still what they were 30 or 40 years ago?

Shor:

Well, the big question in theoretical computer science is does NP=P? Suppose you have a question like finding the shortest tour that visits all these cities, so this is a traveling salesman problem. You can answer—suppose you ask is there a traveling salesman tour that is less than 3500 miles. So, this is a problem we have no idea how to solve on a computer in the worst case. So, in the worst case, we think it takes exponential time to solve it, but it's easy to check if someone gives you a traveling salesman tour, it's easy to compute that it really visits all those cities, and to compute its length.

Shor:

So, P problems are those you can find the solution of quickly, and NP are problems that you can check the solution quickly, but you cannot find a solution quickly. The big open question in theoretical and computer science, and has been since the 1970s, is: does NP=P? For every problem you can check, is there an efficient way of finding the answer? Everyone is completely convinced that the answer is no. There are problems that are easy to check, but very difficult to find a solution. Nobody has any clue as to how to prove it. We're still just as far from a proof as we were—rather, it seems like we're just as far from a proof as we were 50 years ago. Although, who knows. We're obviously 50 years closer to the proof in some sense, but we still have no idea how to go about proving it.

Zierler:

Do you believe in the concept of unsolvable problems in math? Are all problems solvable?

Shor:

No, there are some unsolvable problems. Gödel proved this. Every so often, a problem that we thought might be actually—every so often, somebody shows that a problem that looks quite innocuous is really unsolvable.

Zierler:

And that's true, even with real quantum computing, and we know that even without having quantum computing.

Shor:

Yes, that's right.

Zierler:

How do we know that?

Shor:

I guess, Turing wrote down the idea of taking a computer and formalizing it into a Turing machine. Quantum computers can do things exponentially faster than a Turing machine can, but quantum computers solve the exact same class of things that Turing machines can. You can show, and Turing did show, that there are problems that Turing machines cannot solve. Maybe the clearest one is you have a Turing machine, and you have an initial state in this Turing machine, and you let it run. Question is, does it ever stop? You cannot solve that, because if you could solve that, you could build a Turing machine that, if it stops, then it doesn't stop, and if it doesn't stop, then it stops. So, if you had an algorithm for figuring out whether a Turing machine halted, then you could come up with a contradiction. Rather, you could come up with a Turing machine which the algorithm would give the wrong answer to.

Zierler:

Peter, to flip that question on its head, in what areas do you feel greatest satisfaction that a problem that once seemed truly insurmountable is now truly understood?

Shor:

Are you asking about my own research, or about--

Zierler:

Both. Your research, but also as your work as a representative of the broader field.

Shor:

Okay. So, I guess my first introduction to quantum computers, or quantum information, was BB84, this cryptosystem that Charlie Bennet and Gilles Brassard invented. When I first saw Charlie give a talk about it, I had absolutely no idea how to prove that it was secure. I thought about it, and I couldn't go anywhere. Then, after two very long and complicated proofs of this algorithm that this cryptosystem was really secure. I looked at one of these proofs, and I extracted the essential information of this proof, and came up with a three-page proof. So, that, I think we really understand it now. Doing it required all the formalism of quantum error correcting codes which I helped invent between the time I first saw the BB84 cryptosystem, and the time that I proved it was secure. Let's see. I think I've seen a complete change in—if you look at the attitude of physics towards quantum mechanics, there was one big-- David Mermin expressed this attitude: shut up and calculate. Don't think about what quantum mechanics really means.

Zierler:

That sounds like Mermin.

Shor:

Yeah. Well, he did not espouse this philosophy, but he condensed other physicists' philosophy into this four word summary. Anyway, I think that quantum computing—I think one of the reasons quantum computing wasn't discovered earlier was this shut up and calculate attitude. Don't worry about what quantum mechanics really means, just use it as a tool to calculate probabilities and energies and all that stuff. I think quantum computing shows that thinking about what quantum mechanics really means is a good thing to do. I think people have this attitude much less than they used to. I think it's good, although it's still true that people working in the foundations of physics can—I mean, there are still people working on the foundations of physics and interpretations of quantum mechanics, who are doing research that may not actually go anywhere. But some people are working on other research in that area that seems to be going somewhere, and that's good.

Zierler:

Peter, if you could reflect on your overall contributions, do you tend to divide in your mind the research that you've done that has had, shall we say, purely academic value, and that which has had societal benefit, or positive impact in industry?

Shor:

I don't really divide them. When I do something that has positive impact, I think it's really good. I like having positive impact, but I don't think there's any real—I don't treat these two things separately.

Zierler:

When you're thinking about new projects to take on, do you tend to be motivated by one or the other in terms of gaining understanding strictly in an intellectual or a theoretical case, versus doing something that might actually have that benefit to society?

Shor:

Well, I like problems that are interesting intellectually. I'm not going to work on something that has a lot of benefit to society if it's not interesting intellectually. If I have a choice between working on something interesting intellectually that has benefit, or doesn't have benefit, I'd probably choose the one that has benefit.

Zierler:

Peter, for my last question, I want to ask you personally, what are you most excited about in the future, both in terms of what you'd like to accomplish yourself, and where you see the field headed, and what it might be capable of accomplishing?

Shor:

Okay, what would I like to accomplish in the future? Well, I'd really like to see quantum computers built and used for practical problems. What would I like to accomplish personally? Well, I started working on quantum money because it was a cryptographic protocol which could be done with a quantum computer, but which was completely impossible with a classical computer. I would like to work on more of these cryptographic protocols that can only be achieved with a quantum computer. I don't know if any of these are actually going to be of real, practical use for a long time. What else?

Zierler:

But you do think that eventually they will be of practical use?

Shor:

I don't think quantum money will ever be of practical use as money. It might be of practical use as subroutine for another quantum cryptographic protocol. Or the ideas for it might be usable for other quantum cryptographic protocols. So, what else? I guess, I'd like to understand this AdS/CFT, and its connection with quantum information better.

Zierler:

What's it going to take to get there?

Shor:

It's going to take a lot of work to get there.

Zierler:

In what regard? Understanding the problem better, applying more brain power to it? Are there technological limitations?

Shor:

Just understanding the framework better.

Zierler:

What's the end goal there for understanding this better?

Shor:

Well, I mean, it might say something about quantum gravity, or it might not.

Zierler:

If it does, with gravity, do you believe that would get us a little bit closer to a grand unified theory?

Shor:

Yeah, it would definitely get us closer. Actually, maybe it wouldn't. Maybe we could use it to show that AdS/CFT has nothing to do with our universe. That probably gets us closer to a real unified theory, because people will stop working on the wrong thing, and start working on something that might be better.

Zierler:

Well, Peter, on that note, it's been an absolute delight speaking with you today. I had a lot of fun. I learned a tremendous amount. This was a very unique and special opportunity to get a mathematical perspective on quantum mechanics, which I almost think about and talk to people who are more traditionally rooted in the physics department. So, I greatly appreciate the time you spent with me today.

Shor:

Alright, thank you.