0:00:07.287,0:00:08.287
Thanks!

0:00:08.287,0:00:09.292
I wanted to tell you

0:00:09.292,0:00:12.561
about quantum computing and the limits[br]of the efficiently computable.

0:00:12.654,0:00:17.561
So Richard Feynman was famous[br]for his contempt for authority,

0:00:17.561,0:00:20.961
but it's ironic that if you listened [br]to most of the talks today,

0:00:21.094,0:00:23.894
you might have gotten the impression[br]that Feynman himself

0:00:23.894,0:00:26.889
was an infallible authority on everything.

0:00:27.380,0:00:31.419
I mean physics, nanotech,[br]even molecular biology.

0:00:31.419,0:00:33.435
He sort of had it covered,

0:00:33.936,0:00:37.172
and you know, he also lived[br]in sort of a heroic era for science

0:00:37.172,0:00:40.319
that, let's face it, many of us wish [br]we could have been a part of.

0:00:40.319,0:00:44.552
So it raises a question: [br]will any of us ever discover anything

0:00:44.552,0:00:47.679
that would not have been[br]dopily obvious to this man?

0:00:47.679,0:00:48.806
(Laughter)

0:00:48.810,0:00:52.610
And if not, then you know,[br]maybe we should just quit science

0:00:52.610,0:00:55.410
and take up, I don't know,[br]bongo drumming instead -

0:00:55.410,0:00:58.280
Oh wait, wait, he had that covered too.

0:00:58.291,0:01:00.530
(Laughter)

0:01:00.530,0:01:03.912
Okay, but I see one ray of hope here,[br]

0:01:03.912,0:01:08.500
and this is that Feynman[br]never really appreciated pure math.

0:01:08.590,0:01:10.660
Okay, you heard about that before,

0:01:10.660,0:01:12.179
(Laughter) (Applause)

0:01:12.191,0:01:15.411
you know, in the story[br]about Professor Case.

0:01:15.411,0:01:18.971
There's also a famous quote[br]attributed to him all over the Internet,

0:01:18.971,0:01:22.021
although I've been unable[br]to find proof that he actually said it,

0:01:22.021,0:01:24.718
"Math is to physics [br]as masturbation is to sex."

0:01:24.718,0:01:27.018
An immediate question [br]that raised in my mind is

0:01:27.018,0:01:29.879
where that left my own field[br]of theoretical computer science.

0:01:29.879,0:01:30.879
(Laughter)

0:01:30.879,0:01:32.759
I'll leave you to speculate about that.

0:01:35.842,0:01:38.532
To give an example[br]of his attitude toward math,

0:01:39.122,0:01:42.072
in his famous storybook[br]"Surely You're Joking,"

0:01:42.072,0:01:45.322
he tells about how when[br]he was a grad student at Princeton,

0:01:45.322,0:01:49.012
he loved to taunt [br]the math grad students by saying,

0:01:49.272,0:01:52.602
"Give me any mathematical [br]assertion that I can understand,

0:01:52.602,0:01:55.982
and I will instantly tell you [br]whether it's true or false,"

0:01:56.210,0:01:57.930
without proof of course.

0:01:58.277,0:02:00.527
You know, Feynman[br]is the one telling the story -

0:02:00.527,0:02:03.691
not surprisingly, he comes out [br]pretty well from this contest.

0:02:04.627,0:02:06.937
When I read this,[br]I couldn't help thinking,

0:02:07.027,0:02:12.435
"Well, look, this is really not fair[br]to him, I mean he's no longer with us,

0:02:12.435,0:02:16.618
but, man, you know, I could have[br]cleaned his clock at that contest."

0:02:17.634,0:02:22.164
I mean, you know, it's trivial[br]to come up with mathematical questions

0:02:22.164,0:02:26.914
that neither Feynman nor anyone else [br]can really guess the answers to,

0:02:26.914,0:02:28.209
a priori.

0:02:28.209,0:02:30.414
Just to pick one random example

0:02:30.414,0:02:34.354
from my own field[br]of computational complexity,

0:02:34.684,0:02:36.042
consider the question,

0:02:36.647,0:02:41.632
"What is the fastest algorithm [br]to multiply two nxn matrices?

0:02:41.632,0:02:45.459
So the one that uses the fewest number[br]of arithmetic operations.

0:02:45.569,0:02:47.329
OK, if you just do the obvious thing, [br]

0:02:47.329,0:02:49.449
so you go row by row and column by column,

0:02:49.709,0:02:52.509
then that will take on the order [br]of n cubed operations.

0:02:53.845,0:02:56.373
The obvious lower bound would be n squared

0:02:56.373,0:02:58.483
just because that[br]is the size of the output.

0:02:58.483,0:03:01.779
OK, amazingly, to this day,[br]no one has been able to prove

0:03:01.779,0:03:04.929
that more than, on the order[br]of n squared operations,

0:03:04.929,0:03:06.994
are needed to solve this problem.

0:03:06.994,0:03:08.108
So there's a gap.

0:03:08.108,0:03:10.278
OK, and this is not just a technical thing

0:03:10.278,0:03:14.748
because, in fact, there is a very[br]surprising algorithm that's known

0:03:14.748,0:03:19.058
which can multiply two nxn matrices [br]using a number of steps,

0:03:19.062,0:03:23.322
which is something[br]like n to the 2.376 power -

0:03:23.322,0:03:25.212
I'm sorry that's transposed.

0:03:27.311,0:03:28.911
So here's my question: [br]

0:03:29.771,0:03:33.892
If math or computer science

0:03:33.892,0:03:38.570
were just intellectual masturbation[br]or were not really science, right,

0:03:38.681,0:03:44.271
where would anyone have guessed 2.376[br]as opposed to some other number?

0:03:44.807,0:03:48.334
So, I mean, it just seems clear to me[br]that in these fields, as in physics,

0:03:48.516,0:03:52.230
we're confronting something [br]external to ourselves

0:03:52.696,0:03:56.817
that we're trying to interact with [br]and to understand better.

0:03:58.916,0:04:02.356
You might say, all right,[br]but multiplying two nxn matrices -

0:04:02.356,0:04:04.106
that's sort of a technical issue -

0:04:04.106,0:04:08.814
can you give me something bigger,[br]something of undisputed importance?

0:04:09.086,0:04:11.006
Ah! Well, indeed, I can.

0:04:12.066,0:04:15.638
So computer science's[br]million-dollar question -

0:04:15.638,0:04:16.746
I mean that literally;

0:04:16.746,0:04:20.453
if you solve it, you get a million dollars[br]from the Clay Math Foundation -

0:04:20.453,0:04:23.486
is called: "Does P = NP?"

0:04:23.600,0:04:26.700
OK, so here, "P" stands[br]for polynomial time,

0:04:26.995,0:04:30.432
while "NP" stands for[br]non-deterministic polynomial time.

0:04:30.485,0:04:33.526
See, this is the difference[br]between computer science and physics.

0:04:33.819,0:04:37.556
The physicists also have these terms [br]that they popularized

0:04:37.556,0:04:41.665
that no one else really understands,[br]but at least they give them sexy names,

0:04:41.815,0:04:44.285
like squark, supersymmetry.

0:04:44.285,0:04:46.315
You know, we're stuck with P and NP.

0:04:46.315,0:04:48.620
(Laughter)

0:04:48.620,0:04:50.765
But it really is just as interesting. [br]

0:04:50.765,0:04:53.531
(Laughter)

0:04:53.531,0:04:58.063
So how can I explain in plain English[br]what this question is asking?

0:04:58.153,0:04:59.503
All right, so let me try ...

0:04:59.753,0:05:02.003
So basically what it says is this: [br]

0:05:02.313,0:05:04.613
If you have a fast computer program

0:05:04.613,0:05:08.702
that can recognize the solution [br]to some mathematical problem,

0:05:08.702,0:05:12.390
then is there also a fast [br]computer program to find a solution?

0:05:12.853,0:05:15.772
Now, all of our ordinary[br]experience would suggest

0:05:15.772,0:05:17.222
that the answer should be "No"

0:05:17.222,0:05:21.742
because if you consider, let's say,[br]solving a jigsaw puzzle or a sudoku,

0:05:21.742,0:05:24.092
or breaking a cryptographic code,[br]

0:05:24.092,0:05:26.852
or for that matter coming up with [br]a scientific theory,

0:05:27.132,0:05:31.512
well, it seems much, much harder [br]to come up with the answer yourself

0:05:31.562,0:05:34.841
than to verify an answer[br]that someone else has come up with.

0:05:35.093,0:05:38.642
Just because, if you're coming up [br]with it on yourself, where do you start?

0:05:38.642,0:05:41.850
There's an astronomical number [br]of possibilities to try.

0:05:44.346,0:05:47.406
But amazingly, to this day,[br]no one has been able to rule out

0:05:47.406,0:05:51.204
the possibility of a fast algorithm [br]for solving all of these problems.

0:05:51.546,0:05:53.916
So that's the P versus NP question.

0:05:54.244,0:05:57.554
So, you know, it's a prime time question,

0:05:57.554,0:06:02.094
it's done cameos on both "The Simpsons"[br]and "Futurama" as you can see.

0:06:02.544,0:06:05.314
Much less importantly, [br]as I mentioned before,

0:06:05.314,0:06:08.254
it's one of the seven [br]Clay Millennium problems,

0:06:08.254,0:06:11.974
alongside the Riemann hypothesis, [br]other famous math problems.

0:06:11.974,0:06:17.034
In my opinion, it's sort of manifestly [br]the most important of all seven problems.

0:06:18.110,0:06:20.904
It's the most important[br]mathematical problem today,

0:06:20.904,0:06:23.540
and my argument for that is,

0:06:23.540,0:06:26.140
well, suppose P were equal to NP.

0:06:26.442,0:06:29.863
In other words, that there was a fast [br]algorithm to solve these problems.

0:06:29.870,0:06:33.634
In that case, you would've solved[br]not only the P vs. NP problem,

0:06:33.634,0:06:35.168
but also the other six

0:06:35.168,0:06:38.768
because you could just program[br]your computer to find the answers for you.

0:06:38.768,0:06:40.898
(Laughter)

0:06:40.898,0:06:44.108
So this is a profound question.

0:06:44.519,0:06:48.709
Now, according to a famous[br]computer scientist, Leonid Levin,

0:06:48.899,0:06:51.694
he once told me that he tried once

0:06:51.694,0:06:55.483
to explain the P vs. NP problem[br]to Richard Feynman,

0:06:55.483,0:06:57.809
and Feynman had enormous difficulty

0:06:57.809,0:07:00.340
accepting that is was even [br]an open problem at all.

0:07:00.576,0:07:02.576
His attitude was basically,

0:07:02.576,0:07:05.464
"Well, of course you may need[br]to do an exhaustive search

0:07:05.464,0:07:07.134
and try all the possibilities.

0:07:07.347,0:07:08.527
Next question!"

0:07:09.289,0:07:10.869
(Laughter)

0:07:11.701,0:07:16.741
Indeed, I often point out that if we,[br]computer scientists, had been physicists,

0:07:16.741,0:07:20.501
we would've long ago declared[br]P not equal to NP,

0:07:20.501,0:07:23.387
or the non-existence[br]of a fast algorithm for these problems,

0:07:23.583,0:07:26.951
to be a law of nature,[br]you know, just like the second law,

0:07:26.951,0:07:29.551
or the impossibility[br]of faster-than-light signaling,

0:07:29.551,0:07:31.171
and we would've been done with it.

0:07:31.171,0:07:33.341
There would've been [br]Nobel Prizes all around.

0:07:33.791,0:07:34.791
(Laughter)

0:07:35.292,0:07:39.222
In fact, there have been countless [br]mistaken claims over the years

0:07:39.222,0:07:41.232
to have proved P not equal to NP.

0:07:41.232,0:07:45.479
Because of a blog that I write,[br]I get one in my inbox every week or so.

0:07:45.734,0:07:47.353
Sometimes they've been accompanied

0:07:47.353,0:07:49.952
by death threats[br]if I don't publicize them.

0:07:49.952,0:07:55.423
The most recent serious claim[br]was by Vinay Deolaliker.

0:07:55.423,0:07:58.576
It actually made the "New York Times" [br]and a bunch of other places,

0:07:58.576,0:08:00.571
and the publicity got to the point

0:08:00.571,0:08:06.599
where I controversially[br]offered $200,000 at infinite odds -

0:08:06.599,0:08:08.298
I had no [offer] taker -

0:08:08.617,0:08:10.709
if the proof was correct.

0:08:14.804,0:08:17.854
That may have been wise, [br]may have been unwise.

0:08:17.854,0:08:22.774
You know, people said,[br]"Could you even afford to pay $200,000?"

0:08:23.174,0:08:26.503
My answer was, "No, I can't,[br]but I won't have to."

0:08:26.913,0:08:29.645
(Laughter)

0:08:29.824,0:08:31.256
As, indeed, I didn't.

0:08:33.850,0:08:37.490
So even though it would merely [br]confirm what we already believe,

0:08:37.490,0:08:41.900
I personally think that a correct proof [br]of P not equal to NP

0:08:41.900,0:08:44.224
would be one of the biggest advances

0:08:44.224,0:08:47.572
in human understanding[br]that hasn't happened yet.

0:08:48.340,0:08:49.950
Why do I say this?

0:08:50.898,0:08:54.078
You may think, all right,[br]this is sort of a strange field,

0:08:54.078,0:08:57.138
why do we obsess

0:08:57.138,0:09:00.852
with proving these[br]limitations of computers

0:09:00.958,0:09:03.542
that most of us already believe anyway?[br]

0:09:06.238,0:09:10.008
I think that nothing better illustrates [br]the need to actually prove

0:09:10.008,0:09:12.708
what the limitations of computers are

0:09:12.708,0:09:17.614
better than the field of quantum computing[br]that we already heard something about.

0:09:17.614,0:09:23.217
This is a dream many of us have[br]of exploiting the exponentiality,

0:09:23.330,0:09:27.150
which is inherent in our description[br]of the quantum world,

0:09:27.150,0:09:30.090
in order to solve certain problems[br]dramatically faster

0:09:30.090,0:09:33.280
than we know how to solve them[br]using any computer today.

0:09:33.440,0:09:35.839
Or as I like to describe [br]quantum computing,

0:09:35.839,0:09:39.813
"It's the power of 2 to the n[br]complex numbers working for you!"

0:09:42.618,0:09:46.985
So to give one example,[br]it seems obvious that, let's say,

0:09:46.985,0:09:50.031
if you want to factor [br]an integer into prime numbers,

0:09:50.096,0:09:52.529
like, I don't know - three, five, one -

0:09:53.649,0:09:56.645
(Laughter)

0:09:56.645,0:09:59.625
(Applause)

0:09:59.625,0:10:02.941
then that's much, much harder[br]than multiplying them, right?

0:10:02.941,0:10:06.260
Except that in 1994, Peter Shor discovered

0:10:06.260,0:10:09.689
that if you have a quantum computer[br]that's no longer true.

0:10:10.437,0:10:13.805
There actually is an algorithm [br]that factors numbers

0:10:13.805,0:10:16.062
quantum mechanically, very quickly.

0:10:16.062,0:10:19.630
Now, I see this as one of the more[br]exciting scientific discoveries

0:10:19.630,0:10:21.197
of the last 20 years.

0:10:23.170,0:10:27.813
So you know, Feynman, sadly, didn't live[br]to see this and related discoveries,

0:10:27.813,0:10:32.356
but he did famously anticipate [br]them in his lecture, in 1982,

0:10:32.356,0:10:35.305
on physics and computers [br]that you already heard about.

0:10:36.943,0:10:41.629
I would say Feynman also understood[br]much more clearly than his contemporaries

0:10:41.629,0:10:44.966
what I'll call the modern understanding [br]of quantum mechanics.

0:10:45.214,0:10:46.259
The quantum mechanics

0:10:46.259,0:10:49.443
is basically just a generalization [br]of probability theory,

0:10:49.693,0:10:52.568
where instead of using probabilities,[br]

0:10:52.838,0:10:54.841
which are these non-negative real numbers,

0:10:54.841,0:10:58.369
you use these numbers called amplitudes,[br]which can also be negative.

0:10:59.014,0:11:00.997
Everything else that people go on about -

0:11:00.997,0:11:05.493
the uncertainty principle,[br]the wave particle duality, yada yada -

0:11:05.493,0:11:08.138
they're all just consequences [br]of that one thing.

0:11:08.238,0:11:11.259
OK, there's the secret.[br]I'm sorry if I spilled it.

0:11:11.472,0:11:13.382
(Laughter)

0:11:14.635,0:11:19.270
Quantum mechanics is actually, [br]contrary to its reputation,

0:11:19.270,0:11:22.255
unbelievably simple [br]once you take all the physics out.

0:11:22.255,0:11:25.262
(Laughter)

0:11:25.262,0:11:28.042
(Applause)

0:11:28.042,0:11:30.370
OK, so you might ask me now,

0:11:30.370,0:11:32.460
"Well, if quantum computers are so great,

0:11:32.465,0:11:34.779
then how come they[br]haven't been built yet?"

0:11:34.921,0:11:37.902
The first answer to that question[br]is, "But they have!"

0:11:37.902,0:11:40.141
You know, quantum computers [br]have even been used

0:11:40.141,0:11:43.983
to prove that 15 = 3 x 5 [br]with high probability.

0:11:43.983,0:11:45.624
(Laughter)

0:11:46.026,0:11:50.968
It's possible that factoring 21[br]could be on the technological horizon.

0:11:51.154,0:11:55.745
But OK, what about building [br]a scaleable quantum computer?

0:11:56.094,0:11:59.379
Well, that turns out[br]to be an incredibly hard problem

0:11:59.379,0:12:01.479
because of something called decoherence,

0:12:01.479,0:12:03.979
which is basically [br]the unwanted interaction

0:12:03.979,0:12:07.380
between the quantum computer[br]and its external environment.

0:12:07.676,0:12:11.641
I should mention there's been lots[br]of pioneering research here at Caltech

0:12:11.641,0:12:14.649
over the last decade[br]on how to surmount that problem.

0:12:15.030,0:12:18.410
However, I would say [br]that we might be, still today,

0:12:18.414,0:12:22.015
be roughly in the situation [br]of Charles Babbage in the 1830s.

0:12:22.117,0:12:24.882
OK, we know the basic principles [br]of quantum computing,

0:12:24.882,0:12:26.192
it ought to work,

0:12:26.192,0:12:30.921
but it might take many decades, [br]or who knows, even a century,

0:12:30.921,0:12:33.805
for the technology[br]to catch up with the idea.

0:12:35.598,0:12:38.336
Now, so far, known obstacles[br]are technological,

0:12:38.336,0:12:39.629
but there are a few people,

0:12:39.629,0:12:42.662
including famous physicists[br]such as Gerard 't Hooft,

0:12:42.662,0:12:44.072
who have even gone further

0:12:44.072,0:12:48.982
and have said they believe there [br]will be a fundamental physical obstacle

0:12:48.982,0:12:52.132
that will prevent quantum computers [br]from ever being built.

0:12:52.450,0:12:55.385
My only response to that is,[br]"Well I hope they're right!"

0:12:55.385,0:12:59.111
because that would be way more exciting [br]than building a quantum computer.

0:12:59.111,0:13:01.468
So you build one,[br]so you have a computer, great.

0:13:02.160,0:13:03.258
But if you could prove

0:13:03.258,0:13:05.588
that it's impossible [br]to build a quantum computer,

0:13:05.588,0:13:07.627
then you've overthrown quantum mechanics.

0:13:08.627,0:13:11.626
(Laughter)

0:13:11.770,0:13:12.770
OK.

0:13:12.770,0:13:16.178
So as I see it, maybe[br]the main challenge today is -

0:13:16.178,0:13:20.012
well, short of building a universal,[br]quantum computer, since that's too hard,

0:13:20.012,0:13:22.511
do some quantum mechanical experiments,

0:13:22.511,0:13:24.561
like the ones we[br]were hearing about before,

0:13:24.561,0:13:27.471
but for which one can give[br]serious formal evidence

0:13:27.471,0:13:29.904
that this experiment is doing something

0:13:29.906,0:13:33.910
that cannot be efficiently simulated [br]by a classical computer.

0:13:34.107,0:13:35.834
So this was actually the motivation

0:13:35.834,0:13:39.803
for a recent work of myself [br]and my student, Alex Arkhipov,

0:13:39.803,0:13:43.483
on the computational complexity[br]of certain optical experiments,

0:13:43.483,0:13:48.453
where we showed how to do a sort of - [br]build a rudimentary quantum computer

0:13:49.220,0:13:51.041
that solves some sampling problem

0:13:51.215,0:13:54.534
that a classical computer [br]could not efficiently solve

0:13:54.534,0:13:56.497
under some plausible assumptions.

0:13:57.022,0:13:58.022
OK?

0:13:58.387,0:14:00.695
So one of Feynman's most famous sayings,

0:14:00.695,0:14:05.067
was "I think I can safely say that nobody[br]understands quantum mechanics."

0:14:06.043,0:14:09.939
Basically, it's well known[br]this theory works spectacularly well,

0:14:09.939,0:14:11.339
but it's insane.

0:14:14.519,0:14:17.613
It has this one set of rules,[br]as long as you're not looking,

0:14:17.613,0:14:19.020
and then as soon as you look, [br]

0:14:19.020,0:14:22.103
there's a completely different rule [br]that goes into effect.

0:14:22.443,0:14:23.918
What's up with that?

0:14:23.918,0:14:24.918
(Laughter)

0:14:24.918,0:14:29.236
I was asked to make a "wild prediction"[br]by the TED organizers so -

0:14:29.356,0:14:30.606
deep breath -

0:14:30.606,0:14:32.032
here's my prediction:

0:14:32.262,0:14:34.795
I predict that the effort [br]to build quantum computers

0:14:34.874,0:14:37.522
and to understand[br]their capabilities and limitations

0:14:37.522,0:14:41.823
will lead to a major conceptual advance[br]in our understanding of quantum mechanics

0:14:42.076,0:14:45.512
beyond the modest advances [br]that have happened already.

0:14:45.512,0:14:48.368
And you'll be able to recognize [br]that advance when it comes

0:14:48.368,0:14:50.752
because it will look[br]like science, not philosophy.

0:14:50.752,0:14:53.073
It won't just be putting[br]lipstick on a pig.

0:14:53.073,0:14:54.175
OK, thank you!

0:14:54.178,0:14:57.184
(Applause)

0:14:57.184,0:15:00.179
(Cheers)