Physics in the 21st century: toiling in Feynman's shadow | Scott Aaronson | TEDxCaltech

Scott Aaronson is an associate professor of electrical engineering and computer science at MIT. Scott's research interests center around fundamental limits on what can efficiently be computed in the physical world. This has entailed studying quantum computing, the most powerful model of computation we have, based on known physical theory.

His talk was part of a TEDx program, hosted by CalTech to honor Richard Feynman, Nobel Laureate, Caltech physics professor, iconoclast, visionary, and all-around "curious character."

Scott Aaronson writes a popular blog, http://www.scottaaronson.com/blog, and is the creator of the Complexity Zoo, an online encyclopedia of computational complexity theory.

This talk was given at a TEDx event using the TED conference format but independently organized by a local community. Learn more at http://ted.com/tedx

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)