Transcriber: Clementine SALVI-OFFER Reviewer: David DeRuwe
Thanks!
I wanted to tell you
about quantum computing and the limits of the efficiently computable.
So Richard Feynman was famous for his contempt for authority,
but it's ironic that if you listened to most of the talks today,
you might have gotten the impression that Feynman himself
was an infallible authority on everything.
I mean physics, nanotech, even molecular biology.
He sort of had it covered,
and you know, he also lived in sort of a heroic era for science
that, let's face it, many of us wish we could have been a part of.
So it raises a question: will any of us ever discover anything
that would not have been dopily obvious to this man?
(Laughter)
And if not, then you know, maybe we should just quit science
and take up, I don't know, bongo drumming instead -
Oh wait, wait, he had that covered too.
(Laughter)
Okay, but I see one ray of hope here,
and this is that Feynman never really appreciated pure math.
Okay, you heard about that before,
(Laughter) (Applause)
you know, in the story about Professor Case.
There's also a famous quote attributed to him all over the Internet,
although I've been unable to find proof that he actually said it,
"Math is to physics as masturbation is to sex."
An immediate question that raised in my mind is
where that left my own field of theoretical computer science.
(Laughter)
I'll leave you to speculate about that.
To give an example of his attitude toward math,
in his famous storybook "Surely You're Joking,"
he tells about how when he was a grad student at Princeton,
he loved to taunt the math grad students by saying,
"Give me any mathematical assertion that I can understand,
and I will instantly tell you whether it's true or false,"
without proof of course.
You know, Feynman is the one telling the story -
not surprisingly, he comes out pretty well from this contest.
When I read this, I couldn't help thinking,
"Well, look, this is really not fair to him, I mean he's no longer with us,
but, man, you know, I could have cleaned his clock at that contest."
I mean, you know, it's trivial to come up with mathematical questions
that neither Feynman nor anyone else can really guess the answers to,
a priori.
Just to pick one random example
from my own field of computational complexity,
consider the question,
"What is the fastest algorithm to multiply two nxn matrices?
So the one that uses the fewest number of arithmetic operations.
OK, if you just do the obvious thing,
so you go row by row and column by column,
then that will take on the order of n cubed operations.
The obvious lower bound would be n squared
just because that is the size of the output.
OK, amazingly, to this day, no one has been able to prove
that more than, on the order of n squared operations,
are needed to solve this problem.
So there's a gap.
OK, and this is not just a technical thing
because, in fact, there is a very surprising algorithm that's known
which can multiply two nxn matrices using a number of steps,
which is something like n to the 2.376 power -
I'm sorry that's transposed.
So here's my question:
If math or computer science
were just intellectual masturbation or were not really science, right,
where would anyone have guessed 2.376 as opposed to some other number?
So, I mean, it just seems clear to me that in these fields, as in physics,
we're confronting something external to ourselves
that we're trying to interact with and to understand better.
You might say, all right, but multiplying two nxn matrices -
that's sort of a technical issue -
can you give me something bigger, something of undisputed importance?
Ah! Well, indeed, I can.
So computer science's million-dollar question -
I mean that literally;
if you solve it, you get a million dollars from the Clay Math Foundation -
is called: "Does P = NP?"
OK, so here, "P" stands for polynomial time,
while "NP" stands for non-deterministic polynomial time.
See, this is the difference between computer science and physics.
The physicists also have these terms that they popularized
that no one else really understands, but at least they give them sexy names,
like squark, supersymmetry.
You know, we're stuck with P and NP.
(Laughter)
But it really is just as interesting.
(Laughter)
So how can I explain in plain English what this question is asking?
All right, so let me try ...
So basically what it says is this:
If you have a fast computer program
that can recognize the solution to some mathematical problem,
then is there also a fast computer program to find a solution?
Now, all of our ordinary experience would suggest
that the answer should be "No"
because if you consider, let's say, solving a jigsaw puzzle or a sudoku,
or breaking a cryptographic code,
or for that matter coming up with a scientific theory,
well, it seems much, much harder to come up with the answer yourself
than to verify an answer that someone else has come up with.
Just because, if you're coming up with it on yourself, where do you start?
There's an astronomical number of possibilities to try.
But amazingly, to this day, no one has been able to rule out
the possibility of a fast algorithm for solving all of these problems.
So that's the P versus NP question.
So, you know, it's a prime time question,
it's done cameos on both "The Simpsons" and "Futurama" as you can see.
Much less importantly, as I mentioned before,
it's one of the seven Clay Millennium problems,
alongside the Riemann hypothesis, other famous math problems.
In my opinion, it's sort of manifestly the most important of all seven problems.
It's the most important mathematical problem today,
and my argument for that is,
well, suppose P were equal to NP.
In other words, that there was a fast algorithm to solve these problems.
In that case, you would've solved not only the P vs. NP problem,
but also the other six
because you could just program your computer to find the answers for you.
(Laughter)
So this is a profound question.
Now, according to a famous computer scientist, Leonid Levin,
he once told me that he tried once
to explain the P vs. NP problem to Richard Feynman,
and Feynman had enormous difficulty
accepting that is was even an open problem at all.
His attitude was basically,
"Well, of course you may need to do an exhaustive search
and try all the possibilities.
Next question!"
(Laughter)
Indeed, I often point out that if we, computer scientists, had been physicists,
we would've long ago declared P not equal to NP,
or the non-existence of a fast algorithm for these problems,
to be a law of nature, you know, just like the second law,
or the impossibility of faster-than-light signaling,
and we would've been done with it.
There would've been Nobel Prizes all around.
(Laughter)
In fact, there have been countless mistaken claims over the years
to have proved P not equal to NP.
Because of a blog that I write, I get one in my inbox every week or so.
Sometimes they've been accompanied
by death threats if I don't publicize them.
The most recent serious claim was by Vinay Deolaliker.
It actually made the "New York Times" and a bunch of other places,
and the publicity got to the point
where I controversially offered $200,000 at infinite odds -
I had no [offer] taker -
if the proof was correct.
That may have been wise, may have been unwise.
You know, people said, "Could you even afford to pay $200,000?"
My answer was, "No, I can't, but I won't have to."
(Laughter)
As, indeed, I didn't.
So even though it would merely confirm what we already believe,
I personally think that a correct proof of P not equal to NP
would be one of the biggest advances
in human understanding that hasn't happened yet.
Why do I say this?
You may think, all right, this is sort of a strange field,
why do we obsess
with proving these limitations of computers
that most of us already believe anyway?
I think that nothing better illustrates the need to actually prove
what the limitations of computers are
better than the field of quantum computing that we already heard something about.
This is a dream many of us have of exploiting the exponentiality,
which is inherent in our description of the quantum world,
in order to solve certain problems dramatically faster
than we know how to solve them using any computer today.
Or as I like to describe quantum computing,
"It's the power of 2 to the n complex numbers working for you!"
So to give one example, it seems obvious that, let's say,
if you want to factor an integer into prime numbers,
like, I don't know - three, five, one -
(Laughter)
(Applause)
then that's much, much harder than multiplying them, right?
Except that in 1994, Peter Shor discovered
that if you have a quantum computer that's no longer true.
There actually is an algorithm that factors numbers
quantum mechanically, very quickly.
Now, I see this as one of the more exciting scientific discoveries
of the last 20 years.
So you know, Feynman, sadly, didn't live to see this and related discoveries,
but he did famously anticipate them in his lecture, in 1982,
on physics and computers that you already heard about.
I would say Feynman also understood much more clearly than his contemporaries
what I'll call the modern understanding of quantum mechanics.
The quantum mechanics
is basically just a generalization of probability theory,
where instead of using probabilities,
which are these non-negative real numbers,
you use these numbers called amplitudes, which can also be negative.
Everything else that people go on about -
the uncertainty principle, the wave particle duality, yada yada -
they're all just consequences of that one thing.
OK, there's the secret. I'm sorry if I spilled it.
(Laughter)
Quantum mechanics is actually, contrary to its reputation,
unbelievably simple once you take all the physics out.
(Laughter)
(Applause)
OK, so you might ask me now,
"Well, if quantum computers are so great,
then how come they haven't been built yet?"
The first answer to that question is, "But they have!"
You know, quantum computers have even been used
to prove that 15 = 3 x 5 with high probability.
(Laughter)
It's possible that factoring 21 could be on the technological horizon.
But OK, what about building a scaleable quantum computer?
Well, that turns out to be an incredibly hard problem
because of something called decoherence,
which is basically the unwanted interaction
between the quantum computer and its external environment.
I should mention there's been lots of pioneering research here at Caltech
over the last decade on how to surmount that problem.
However, I would say that we might be, still today,
be roughly in the situation of Charles Babbage in the 1830s.
OK, we know the basic principles of quantum computing,
it ought to work,
but it might take many decades, or who knows, even a century,
for the technology to catch up with the idea.
Now, so far, known obstacles are technological,
but there are a few people,
including famous physicists such as Gerard 't Hooft,
who have even gone further
and have said they believe there will be a fundamental physical obstacle
that will prevent quantum computers from ever being built.
My only response to that is, "Well I hope they're right!"
because that would be way more exciting than building a quantum computer.
So you build one, so you have a computer, great.
But if you could prove
that it's impossible to build a quantum computer,
then you've overthrown quantum mechanics.
(Laughter)
OK.
So as I see it, maybe the main challenge today is -
well, short of building a universal, quantum computer, since that's too hard,
do some quantum mechanical experiments,
like the ones we were hearing about before,
but for which one can give serious formal evidence
that this experiment is doing something
that cannot be efficiently simulated by a classical computer.
So this was actually the motivation
for a recent work of myself and my student, Alex Arkhipov,
on the computational complexity of certain optical experiments,
where we showed how to do a sort of - build a rudimentary quantum computer
that solves some sampling problem
that a classical computer could not efficiently solve
under some plausible assumptions.
OK?
So one of Feynman's most famous sayings,
was "I think I can safely say that nobody understands quantum mechanics."
Basically, it's well known this theory works spectacularly well,
but it's insane.
It has this one set of rules, as long as you're not looking,
and then as soon as you look,
there's a completely different rule that goes into effect.
What's up with that?
(Laughter)
I was asked to make a "wild prediction" by the TED organizers so -
deep breath -
here's my prediction:
I predict that the effort to build quantum computers
and to understand their capabilities and limitations
will lead to a major conceptual advance in our understanding of quantum mechanics
beyond the modest advances that have happened already.
And you'll be able to recognize that advance when it comes
because it will look like science, not philosophy.
It won't just be putting lipstick on a pig.
OK, thank you!
(Applause)
(Cheers)