(contemplative electronic music) - Hi. I'll be talking about some recollections about when I discovered
the factoring algorithm. But first, I thought we should go back and talk about where I was when this conference was being held. So in 1981, I was a senior at Caltech, which is the same place
Richard Feynman was. And so obviously, Feynman was preparing his keynote address when I was studying and
getting ready to graduate. But I didn't hear anything
about Feynman keynote address or quantum computation. What I did hear from Feynman
was a very interesting lecture that I went to called
negative probability, and I'll mention it because first, he says a few things
about negative probability in his keynote address. And second, I think it
sheds some light on Feynman. So in this lecture, Feynman said that he had been
looking at Bell's theorem. And Bell's theorem is
this proof that Bell had that shows that the EPR
paradox is unavoidable. That really, quantum mechanics can not be local and realistic. I won't tell you what realistic means, but that disturbed a number
of physicists apparently, including Feynman. So he looked very carefully
over all the hypotheses that went into Bell's theorem to see if there were
any hidden assumptions that he could look at. And he found one. The hidden assumption was
that all probabilities were between zero and one. So he asked himself, suppose we let the probabilities be any real numbers less
than zero or bigger than one. And we arrange things so that only when you
add up the probabilities to get the probability
of some observable event, it has to be between zero and one. So this was his idea. And well, he hadn't worked
it out when he gave the talk. And apparently, he never worked it out because he published a
paper a few years later called negative probability. And the very interesting
thing about this paper was that this motivation for
this negative probability work was absent from the paper. He didn't mention anything
about Bell's theorem. He mentioned as motivation, well, is there any way we
can avoid these infinities that appear in renormalization? And that's another big
paradox of quantum mechanics that nobody has done anything about. So I think this shows that Feynman was really careful
cultivating his mystique. He didn't mention the original
motivation in the paper because it would have been clear that he had been wrong about this and that he wasn't able to resolve the paradox of Bell's theorem. So he found another
motivation for this work, which didn't destroy this Feynman mystique of never making mistakes. And there's another interesting
thing about that too. It shows that Feynman
didn't take his own advice. In 1964 at a set of
lectures at MIT, he said, "I'm going to tell you
what nature behaves like. If you will simply admit that
she does behave like this, you will find her a
delightful, entrancing thing. But do not keep saying to yourself if you can possibly avoid it, but how can it be like that because you will get down
the drain into a blind alley from which nobody has ever escaped. Nobody knows how it can be like that." But you know, 15 years
after he gave that lecture, he then disobeyed his words and started worrying about
how could it be like that? And it was a blind alley
just like he predicted. Of course, maybe the advice he was giving wasn't to professors who are tenured, but for graduate students. I mean, the only graduate
student I know about who did a lot of, you know, had a successful thesis on the foundations of quantum mechanics and avoiding Bell's
theorem is Hugh Everett who proposed the many-worlds theory in his graduate PhD thesis. And he left academia after he graduated. So now, I want to skip ahead to the next. The first time I heard
about quantum computing, it was a talk that Charlie
Bennett gave at Bell Labs. And I don't remember the exact dates, but it was obviously after
Bell's theorem in 1986. And I think it must have been, or not Bell's theorem, it was after BB84 in 1984, but it must have been before Charlie built his QKD apparatus in 1991 because I don't remember the apparatus from the talk involved. Anyway, Charlie gave the BB84
key distribution protocol and he asked an open question, which was, is there any way of proving mathematically that this is secure? So I thought about it for a while, but I gave up because I
was completely stumped at how you would take the BB84 quantum key distribution protocol and turn it into rigorous mathematics, which is rather ironic because in 2000, John Preskill and I gave
the first simple proof of the security of BB84. Of course, that was after we'd learned all about quantum information, and quantum computation, and quantum error correction, and all of the stuff we've learned went into that simple proof. Okay. So I gave up on worrying
about proving the security of quantum key distribution. But then a few years later, in 1992, Umesh Vazirani came to Bell Labs and he gave his talk on
Bernstein and Vazirani, where he put quantum Turing machines into a mathematically rigorous framework and where he had a algorithm
for a contrived problem, the Bernstein-Vazirani problem, which seemed to run faster
on a quantum machine, Turing machine, than on
a classical computer. So that really intrigued me and I started thinking about whether there were or any more useful or more convincing problems that could be done on a quantum computer much more efficiently than
on a classical computer. I didn't get anywhere on this question until I saw a paper of Dan Simon's. And Simon was looking at this problem, find the period on the vertices of a high dimensional cube. So here's a three-dimensional cube, in which case the problem is trivial. But if you have a 500-dimensional cube, it suddenly gets very hard. So there's a function on the vertices. And this function is the property that if you go into the screen and then move horizontally, you will see a vertex of the same color. So that means that these colors of the
vertices are periodic because if you add a binary
vector to one of them, you will get another
one of the same color. So Simon's problem was
given a function like this, which we only can access as an oracle, find the period. And the way he did this was by applying what is essentially a Fourier transform over a binary vector space. So I looked at Simon's problem and I knew that Fourier transformers were very good at finding periodicity. And I knew that the discrete log problem was also very much related to periodicity. And the discrete log problem is one which if you look at
public-key cryptosystems, there are some public-key cryptosystems that the discrete log problem
is the key to breaking it. If you can solve the discrete log problem, you could break the cryptosystems. So a similar thing holds for factoring. If you can factor large numbers rapidly, you can break the RSA cryptosystem. But discrete log problem, you break the Diffie-Hellman cryptosystem, which is not as common, but which is still a
very important problem. So I started looking at whether you could solve
discrete log problem. And so for the discrete log problem, it looks very similar to Simon's problem. Now, the function is not
on a high dimensional cube, but on a very large torus. And there is a period there. So in this example, if you move two vertices to the right and one vertex down, you see another vertex
which is of the same color. And if you can find the period of this function on a large torus where you can only query the colors of the vertices by an oracle, you can solve discrete log. I knew that the Fourier transform was very important for finding periods. So I figured out how to
take the Fourier transform on a quantum computer over an
exponentially large period. And then I figured out how to apply it so I'd get a discrete log. And there's a very
embarrassing thing here, which is that I had seen Simon's paper when I was on the program
committee for STOC. So there's two big conferences
in computer science, STOC and FOCS. And papers in those conferences are treated kind of the way physicists treat Phys Rev paper. The story, which I don't think is
really true in either case, is that people count up the
number of STOC and FOCS papers. And if you have enough of
them, they give you tenure. Anyway, we rejected Simon's
paper from the conference. And then before it actually appeared, I realized I could use the idea to find, to come up with a discrete
log and factoring algorithm. So I called Simon and
got him to send my paper so I would have a legitimate copy. And then I went and wrote my paper. And Simon said that he never
would have figured this out, so he didn't really mind that. At least, I argued for
accepting Simon's paper. I obviously didn't argue
hard enough at board. I should have been jumping
up and down and say, "you absolutely have to take this paper," but I did argue for it and I guess theoretical
computer scientists didn't think highly of quantum computation so it got rejected. Once I had solved the
discrete log problem, I gave a talk about it at Bell Labs. So before the talk, I'd only told a handful
of people about it, including Jeff Lagarias, who found a very minor
error and we fixed it, and my boss, David Johnson. But the talk was in Henry Landau Seminar, which is an internal seminar at Bell Labs, which has a very active audience. You know, the speaker gets
constantly pelted by questions and there have been at
least one or two occasions when people have never
been able to get through more than the first two or
three of their transparencies because they got so many questions, they didn't manage to get
anywhere in their talk. But actually, it went very well. And then I went back to work and I managed to solve
the factoring problem a few days later. And that weekend, so five days after my talk, I got a call from Umesh Vazirani saying, "I hear you can factor
on a quantum computer. Tell me how it works." So there was a couple
of interesting things. First, the rumor mill must've spread the result very rapidly. And second, if you know the old
children's game of telephone, one person whispers something to the next, who whispers something to the next, who whispers something to the next. And it's completely changed by the time it gets around
to the first person. Well, I had told everyone
I'd solved discrete log and I don't think I told anyone other than maybe one or two people that I've been able to
solve factoring as well, but somehow the rumor changed
discrete log to factoring. Now, that's not too uncommon because there's an
interesting relationship between the problems of
discrete log and factoring. They can both be used to
get public-key cryptosystems and any time anyone has ever found an algorithm for one of them, some time later, maybe six months, maybe a couple of years, the techniques from that algorithm can be used to apply to the other one. However, it's not the case
that you can take any algorithm and with some kind of, you know, stick it in some kind of
machine and turn the crank and get an algorithm for discrete log out of the algorithm for
factoring or vice versa. It's just that they are
similar enough problems that one algorithm for one usually gives an algorithm for the other with enough thought. So yeah, when Umesh calls me, I told him that I knew how to factor large numbers on a quantum computer. And the news spread
very rapidly after that. So I think the first thing was, yeah. So Umesh Vazirani called me on the phone, but the first time I talked
about that with anybody was Charlie Bennett. There was a Columbia Theory Day, which was held twice a
year in New York City. And there was one in late April. And Charlie Bennett,
and John Smolan, and I arranged to get together at the Theory Day and I could talk about the
factoring algorithm to him. And then he explained
some interesting things about quantum puzzles and quantum information to me. And so that's there. The next thing was I gave a conference at the Cornell Algorithmic
Number Theory Symposium, which I think was the
first of annual conference. And I was invited at the last minute, this was the first few days in May. And so I flew up and gave my talk. And yeah, there was
someone from the NSA there who came up and asked me
questions about it afterwards. There was a conference at the
Santa Fe Institute in mid May, and I couldn't go, but Umesh Vazirani talked
about the factoring algorithm. And so a lot of people
heard about it from there. And let's see. I was deluged for my
requests for my paper. I got interviewed by a bunch of magazines. And I think the next big conference was a conference arranged
by NIST in Gaithersburg. And that was in August. And it was specially arranged because of the factoring algorithm. And despite the fact
that someone from the NSA asked me questions at the talk at Cornell, a lot of people from the NSA didn't know anything about the, or at least have told me
they didn't know anything about the factoring result
before the conference. And then after this, there was a conference
in Torino that Fall, there was a conference in Texas, which was the Physics and
Computation Conference, which was sort of a follow up to the 1981 Endicott House Conference I think that was called Physcop '94. And then there was FOCS, which I had submitted my paper to. And both Simon's paper and
my paper got accepted to FOCS and I presented the result there. So there was one big objection
to quantum computation. And Rolf Landauer apparently
already brought it up at the May conference at
the Santa Fe Institute, which is that you cannot correct errors on a quantum computer, or at least it looked like you could not correct errors
on a quantum computer. So, why can't you? Well, it's basically, there's
the no cloning theorem. There are a bunch of techniques for dealing with faults
on a digital computer. One of them is checkpointing where you take your
state of your computation and you write it down. So if the computation
gets derailed by an error after that point, you can go back to the checkpoint, and you don't have to go
back to the original thing. Another is error correcting codes. And error correcting codes
introduce a few redundant bits. So if you make one error in
the bits of a word in memory, you can use the redundant bits to fix it. And then finally, there
is massive redundancy where you keep many copies
of all your bits around and continually compare them and fix them by taking the majority. So it looked like none of these techniques could actually be used to correct errors on a quantum computer. I mean, checkpointing, what you do is you take your computation and you write it, the state of your computer down. That's making a copy. That's not allowed. For quantum error checking codes, you take your bits that you have in memory and you make parity check bits, which are essentially redundant copies. So that also looked
like it was no cloning, so that wasn't allowed either. And the final thing, massive redundancy. Well, if you have five copies
of your computation running and one of them derails, now, there's only four. Now, you want to take the four good copies and turn them into five good copies. That's cloning too. You're not allowed to take four
copies of the quantum state and turn it into five copies because it violates the non-cloning term. So it looks like you can not fix errors on a quantum computer. And if you can't fix errors, then you have to do your
computation perfectly. And if you have say, a billion
steps in your computation, which is what you need to factor a cryptographically important number, then you need to do each part, each step in your computation accurate to one part in a billion. And you ask experimental physicists and they'll tell you that's
absolutely impossible. So if you want to get an estimate for what the state of the art was, Jeff Kimball estimated that
the techniques at the time could do one two quantum bit
gate with around 80% accuracy, which is pretty pathetic if you want to do a billion gates with one part in a billion
accuracy for each of them. However, it turns out that
quantum error correcting codes don't actually need to clone things. So the simplest classical
error correcting code is you take zero and you
encode it by zero, zero, zero. You take one and you can
encode it by one, one, one. And you can do that on quantum bits too. You can encode zero by zero, zero, zero, and one by one, one, one. And this is not cloning because
if you take zero plus one, so a superposition of zero and one, you don't get three copies
of the superposition. You get the superposition
of the encoded zero and the encoded one. So this code corrects bit errors fine. So bit errors essentially behave the way that the bits in classical
error correcting codes work, but it does not correct phase errors. So if you make a phase error in one qubit, you actually make a phase
error for the encoding qubit. So that means that phase errors
are three times as likely because if you have some
rate of phase errors in your qubits, then the error error rate and your logical qubits
is three times as fast. Now, what I realized was
that there's a transformation that takes bit errors with phase errors and phase errors to bit errors. So you can apply that
transformation to the code. And now, it will correct any phase errors, but bit errors are
three times more likely. So, what do we do? I mean, we have the errors. It looks like you can
protect the bit errors. So squeeze the encoded qubit one way, but then the other kind of
error becomes more likely. So is this something that's unavoidable or can we fix this? Well, I realized that
there's a nine qubit code correcting any single qubit error. And it's formed just by
taking these two codes and concatenating them. First, doing code using the
phase error correcting code. And then you encode each qubit of the resulting three qubit code with the bit error correcting code, and you've encoded one
qubit into nine qubits and it cracks any single qubit error. So sometime after I wrote this. So it was too late to
include this in my paper that gave the nine qubit code and I never bothered
to publish it anywhere. I discovered that Asher Peres had actually discovered
the three qubit code that corrects bit errors much earlier. So in 1985, he wrote this paper called, "Reversible logic and quantum computers." And in it, he started worrying about
errors for quantum computers and he proposed this three qubit code. And you can see that this zero, zero, zero plus one, one, one, except he calls them
spin up and spin down, he's included this code. He didn't need to worry
about correcting phase errors because he was just worried about doing classical computations
on a quantum computer. And if you do classical
computations on a quantum computer, phase errors don't matter. So Perez discovered the three qubit code that corrects bit errors and actually said some
interesting things about it much earlier than my paper. After I wrote the nine qubit paper, I started thinking about maybe there are better quantum
error correcting codes. After all, the repetition code had been known for thousands
of years classically and nobody had invented the
better error cracking codes until the 1950s. So I started thinking, well, there should be some more efficient quantum error correcting
codes too because we know one, but it's the analog of the very inefficient
classical repetition code. So I started looking at repetition codes. Now, the classical Hamming code encodes four bits into seven bits and corrects one error, and this is probably the simplest classical error correcting code. It was discovered by Hamming around 1950. And well, you can do a
quantum Hamming code too. And playing around with
the classical Hamming code, I got the quantum Hamming code. And what this does is it encodes
one qubit into seven qubits and corrects one error. And you can see that it's just made by superimposing states of
the classical Hamming code. So I showed this to Rob
Calderbank who was also at AT&T and was an expert on
classical coding theory. And we generalized this
to a whole class of codes you can construct, which were CSS codes. And Andrew Steane discovered
the quantum Hamming code as well as this class at
approximately the same time. And so they're now called CSS codes after Steen, and Calderbank, and myself. And inspired by this, a bunch of groups start investigating more complicated codes. So what they did was they
put computers to work on trying to figure out codes. And two groups, one at
IBM and one at Los Alamos, discovered a code that encodes
one qubit into five qubits and corrects one error. And they actually discovered
two different codes, but it was easy to see that one could easily be
transformed into another. And in fact, this is
probably neither of them, but a transformation that
makes them look more symmetric. Anyway, I saw these papers and I said, well, there's obviously a lot of structure to the five qubit code, because you can look
at all the symmetries, and it has a ton of symmetries. So there must be some
reason that it exists, some way of systematically
discovering it and describing it. So I started looking around that. And I wanted to figure out what the symmetry group of this code was. So I asked Neil Sloane, who was another mathematician
working at Bell Labs, how would you find the
symmetry group of this code? So he said, well, you should
use the program Magma. And he gave me an example Magma program that he was working on a different problem that he had just run to compute the group of
symmetries of something else. So I put this code up on Magma and wrote a program. And it spit out the fact that the group has
5,160,960 elements in it. And this happened to be
exactly the same number as Neil Sloane had found. So we looked at it more closely and not only were they same size group, they were the same group. And in fact, there was a deep connection between packings in Grassmannian space, which is what Neil Sloane was looking at, and quantum error correcting codes. And that gave us the hint to figure out how this
code was constructed. It comes from additive codes over the field with four elements. And using this construction, we could find many, many,
many more quantum codes. And this is in fact the
theory of stabilizer codes, which were discovered and
named by Dan Gottesman, the same time that we had done our work. So I believe that's all I have time for and thank you very much for listening. I'm very happy to have been part of this 40th anniversary celebration of the original Endicott House Conference on Physics and Computation. And I hope to enjoy the rest of it.
Lol @ the huge cut at 16:50
Did I miss it, or is the term "Shor's Algorithm" never used in the video?