(gentle solemn music begins)
- 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
which seemed to run faster on a Quantum Turing machine
than on a classical computer.
So that really intrigued me.
And I started thinking about whether there were
any 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.
So, Simon's problem was given a function like this,
which we only can access as an oracle, find a period.
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 a similar thing holds for factoring.
If you can factor large numbers rapidly,
you can break the RSA cryptosystem.
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 exponentially large period.
And then I figured out how to apply it
to swagat discrete look.
And there's a very embarrassing thing here
which is that I had seen Simon's paper
when I was on the program committee.
We rejected Simon's paper from the conference,
and then before it actually appeared,
I realized I could use the idea.
So, I called Simon and got him to send my paper.
And 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 once I'd solved the Discrete Log Problem,
I gave a talk about it at Bell Labs
which has a very active audience.
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.
Actually it went very well.
And then I went back to work
and I managed to solve the factoring problem,
a few days later.
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."
I told him that I,
how to factor large numbers on a quantum computer.
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,
whispers something to the next,
whispers something to the next.
And it completely changed by the time it gets around
to the first person.
Well, I had
told everyone I 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.
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 Smolin 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.
The next thing was I gave a conference
at the Cornell Algorithmic Number Theory Symposium,
which I think was the first of a annual conference.
And so I flew up and gave my talk.
And there was someone from the NSA there
who came up and asked me questions about it afterwards.
You know, I was deluged for,
by requests for my paper.
I got interviewed by a bunch of magazines
and both Simon's paper and my paper got accepted to Fox
and I presented the end result there.
(gentle solemn music ends)