Scott Aaronson: Quantum Computing
物理与宇宙学技术与编程AI 与机器学习音乐与艺术哲学与宗教
📋 章节目录
暂无章节信息
🔑 关键词
quantumcomputerqubitsquestionsclassicalcomputerscomputingmachineerrordonfreepossibleamplitudesphilosophicaltryingalgorithmspeedproblemstalkingsupremacy
💬 精彩语录
暂无语录
🎙️ 完整对话（2057 条）
Lex Fridman (00:00.000)
The following is a conversation with Scott Aaronson,
Lex Fridman (00:03.160)
a professor at UT Austin,
Lex Fridman (00:04.920)
director of its Quantum Information Center,
Lex Fridman (00:07.200)
and previously a professor at MIT.
Lex Fridman (00:10.000)
His research interests center
Scott Aaronson (00:11.720)
around the capabilities and limits of quantum computers
Lex Fridman (00:14.580)
and computational complexity theory more generally.
Scott Aaronson (00:17.720)
He is an excellent writer
Lex Fridman (00:19.440)
and one of my favorite communicators
Scott Aaronson (00:21.100)
of computer science in the world.
Lex Fridman (00:23.300)
We only had about an hour and a half of this conversation,
Lex Fridman (00:26.480)
so I decided to focus on quantum computing.
Lex Fridman (00:29.160)
But I can see us talking again in the future
Scott Aaronson (00:30.920)
on this podcast at some point
Lex Fridman (00:33.240)
about computational complexity theory
Lex Fridman (00:35.640)
and all the complexity classes that Scott catalogs
Lex Fridman (00:38.480)
in his amazing Complexity Zoo Wiki.
Scott Aaronson (00:42.400)
As a quick aside,
Lex Fridman (00:43.640)
based on questions and comments I've received,
Scott Aaronson (00:46.020)
my goal with these conversations
Lex Fridman (00:48.200)
is to try to be in the background without ego
Lex Fridman (00:51.560)
and do three things.
Lex Fridman (00:53.400)
One, let the guests shine
Lex Fridman (00:55.240)
and try to discover together
Lex Fridman (00:56.960)
the most beautiful insights in their work
Lex Fridman (00:59.080)
and in their mind.
Lex Fridman (01:00.760)
Two, try to play devil's advocate
Scott Aaronson (01:02.960)
just enough to provide a creative tension
Lex Fridman (01:05.560)
in exploring ideas through conversation.
Lex Fridman (01:08.040)
And three, to ask very basic questions
Lex Fridman (01:11.760)
about terminology, about concepts, about ideas.
Scott Aaronson (01:16.360)
Many of the topics we talk about in the podcast
Lex Fridman (01:18.760)
I've been studying for years
Scott Aaronson (01:20.600)
as a grad student, as a researcher,
Lex Fridman (01:22.800)
and generally as a curious human who loves to read.
Lex Fridman (01:26.180)
But frankly, I see myself in these conversations
Lex Fridman (01:29.180)
as the main character
Scott Aaronson (01:30.360)
for one of my favorite novels by Dostoevsky
Lex Fridman (01:32.720)
called The Idiot.
Scott Aaronson (01:35.160)
I enjoy playing dumb.
Lex Fridman (01:36.920)
Clearly, it comes naturally.
Lex Fridman (01:39.080)
But the basic questions
Lex Fridman (01:40.200)
don't come from my ignorance of the subject
Lex Fridman (01:42.440)
but from an instinct that the fundamentals are simple.
Lex Fridman (01:45.800)
And if we linger on them
Scott Aaronson (01:47.060)
from almost a naive perspective,
Lex Fridman (01:49.020)
we can draw an insightful thread
Scott Aaronson (01:50.920)
from computer science to neuroscience
Lex Fridman (01:53.400)
to physics to philosophy
Lex Fridman (01:55.320)
and to artificial intelligence.
Lex Fridman (01:58.800)
This is the Artificial Intelligence Podcast.
Scott Aaronson (02:01.480)
If you enjoy it, subscribe on YouTube,
Lex Fridman (02:03.680)
give it five stars on Apple Podcast,
Scott Aaronson (02:05.660)
support it on Patreon,
Lex Fridman (02:07.000)
or simply connect with me on Twitter
Scott Aaronson (02:08.960)
at Lex Friedman, spelled F R I D M A N.
Lex Fridman (02:13.540)
As usual, I'll do one or two minutes of ads now
Lex Fridman (02:16.440)
and never any ads in the middle
Lex Fridman (02:17.880)
that can break the flow of the conversation.
Scott Aaronson (02:20.120)
I hope that works for you
Lex Fridman (02:21.520)
and doesn't hurt the listening experience.
Scott Aaronson (02:24.100)
Quick summary of the ads.
Lex Fridman (02:25.560)
Two supporters today.
Scott Aaronson (02:27.080)
First, get Cash App and use the code LEX PODCAST.
Lex Fridman (02:31.640)
Second, listen to the Tech Meme Ride Home podcast
Scott Aaronson (02:35.040)
for tech news.
Lex Fridman (02:36.300)
Search Ride Home, two words, in your podcast app.
Scott Aaronson (02:41.280)
This show is presented by Cash App,
Lex Fridman (02:43.440)
the number one finance app in the App Store.
Scott Aaronson (02:45.860)
When you get it, use code LEX PODCAST.
Lex Fridman (02:49.320)
Cash App lets you send money to friends,
Scott Aaronson (02:51.600)
buy Bitcoin, and invest in the stock market
Lex Fridman (02:54.120)
with as little as one dollar.
Scott Aaronson (02:56.000)
Broker services are provided by Cash App Investing,
Lex Fridman (02:59.040)
a subsidiary of Square, a member SIPC.
Scott Aaronson (03:03.040)
Since Cash App does fractional share trading,
Lex Fridman (03:05.360)
let me mention that the order execution algorithm
Scott Aaronson (03:08.200)
that works behind the scenes
Lex Fridman (03:09.760)
to create the abstraction of fractional orders
Scott Aaronson (03:12.520)
is an algorithmic marvel.
Lex Fridman (03:14.640)
So big props to the Cash App engineers
Scott Aaronson (03:16.940)
for solving a hard problem that in the end
Lex Fridman (03:19.440)
provides an easy interface that takes a step up
Scott Aaronson (03:22.260)
to the next layer of abstraction over the stock market,
Lex Fridman (03:25.140)
making trading more accessible for new investors
Lex Fridman (03:28.480)
and diversification much easier.
Lex Fridman (03:31.720)
So again, if you get Cash App from the App Store
Scott Aaronson (03:34.400)
or Google Play and use the code LEX PODCAST,
Lex Fridman (03:37.880)
you'll get $10 and Cash App will also donate $10 to FIRST,
Scott Aaronson (03:42.080)
one of my favorite organizations
Lex Fridman (03:44.120)
that is helping to advance robotics and STEM education
Scott Aaronson (03:47.360)
for young people around the world.
Lex Fridman (03:50.560)
This episode is also supported
Scott Aaronson (03:52.200)
by the Tech Meme Ride Home Podcast.
Lex Fridman (03:55.720)
It's a technology podcast I've been listening to
Scott Aaronson (03:57.760)
for a while and really enjoying.
Lex Fridman (04:00.280)
It goes straight to the point,
Scott Aaronson (04:01.720)
gives you the tech news you need to know
Lex Fridman (04:03.680)
and provides minimal but essential context.
Scott Aaronson (04:07.080)
It's released every day by 5 p.m. Eastern
Lex Fridman (04:10.080)
and is only about 15 to 20 minutes long.
Scott Aaronson (04:13.460)
For fun, I like building apps on smartphones,
Lex Fridman (04:16.240)
most on Android, so I'm always a little curious
Scott Aaronson (04:18.800)
about new flagship phones that come out.
Lex Fridman (04:21.120)
I saw that Samsung announced the new Galaxy S20
Lex Fridman (04:25.600)
and of course, right away, Tech Meme Ride Home
Lex Fridman (04:29.360)
has a new episode that summarizes all that I needed to know
Scott Aaronson (04:33.200)
about this new device.
Lex Fridman (04:35.520)
They've also started to do weekend bonus episodes
Scott Aaronson (04:38.560)
with interviews of people like AWOL founder Steve Case
Lex Fridman (04:42.020)
on investing and Gary Marcus on AI,
Scott Aaronson (04:45.600)
who I've also interviewed on this podcast.
Lex Fridman (04:48.680)
You can find the Tech Meme Ride Home Podcast
Scott Aaronson (04:51.600)
if you search your podcast app for Ride Home, two words.
Lex Fridman (04:56.680)
Then subscribe, enjoy, and keep up to date
Scott Aaronson (05:00.160)
with the latest tech news.
Lex Fridman (05:02.560)
And now, here's my conversation with Scott Aaronson.
Scott Aaronson (05:07.680)
I sometimes get criticism from a listener here and there
Lex Fridman (05:11.640)
that while having a conversation
Scott Aaronson (05:13.400)
with a world class mathematician, physicist,
Lex Fridman (05:16.200)
neurobiologist, aerospace engineer,
Scott Aaronson (05:18.200)
or a theoretical computer scientist like yourself,
Lex Fridman (05:21.740)
I waste time by asking philosophical questions
Scott Aaronson (05:24.680)
about free will, consciousness, mortality, love,
Lex Fridman (05:28.880)
nature of truth, super intelligence,
Scott Aaronson (05:31.920)
whether time travel is possible,
Lex Fridman (05:33.480)
whether space time is emergent and fundamental,
Scott Aaronson (05:36.840)
even the crazier questions like whether aliens exist,
Lex Fridman (05:39.400)
what their language might look like,
Lex Fridman (05:40.840)
what their math might look like,
Lex Fridman (05:43.020)
whether math is invented or discovered,
Lex Fridman (05:44.700)
and of course, whether we live in a simulation or not.
Lex Fridman (05:47.960)
So I try.
Scott Aaronson (05:48.800)
Out with it.
Lex Fridman (05:49.880)
Out with it.
Scott Aaronson (05:51.360)
I try to dance back and forth from the deep technical
Lex Fridman (05:55.460)
to the philosophical, so I've done that quite a bit.
Lex Fridman (05:59.040)
So you're a world class computer scientist,
Lex Fridman (06:01.680)
and yet you've written about this very point,
Scott Aaronson (06:04.120)
the philosophy is important for experts
Lex Fridman (06:06.720)
in any technical discipline,
Scott Aaronson (06:09.040)
though they somehow seem to avoid this.
Lex Fridman (06:11.140)
So I thought it'd be really interesting
Scott Aaronson (06:13.460)
to talk to you about this point.
Lex Fridman (06:15.100)
Why should we computer scientists, mathematicians,
Lex Fridman (06:17.740)
physicists care about philosophy, do you think?
Lex Fridman (06:20.780)
Well, I would reframe the question a little bit.
Scott Aaronson (06:23.020)
I mean, philosophy almost by definition
Lex Fridman (06:26.760)
is the subject that's concerned with the biggest questions
Lex Fridman (06:30.940)
that you could possibly ask, right?
Lex Fridman (06:33.160)
So the ones you mentioned, right?
Lex Fridman (06:35.740)
Are we living in a simulation?
Lex Fridman (06:38.440)
Are we alone in the universe?
Lex Fridman (06:41.720)
How should we even think about such questions?
Lex Fridman (06:44.360)
Is the future determined,
Lex Fridman (06:46.000)
and what do we even mean by it being determined?
Lex Fridman (06:49.560)
Why are we alive at the time we are
Lex Fridman (06:51.760)
and not at some other time?
Lex Fridman (06:55.320)
And when you sort of contemplate
Scott Aaronson (06:58.020)
the enormity of those questions,
Lex Fridman (06:59.560)
I think you could ask,
Lex Fridman (07:01.080)
well, then why be concerned with anything else, right?
Lex Fridman (07:04.560)
Why not spend your whole life on those questions?
Scott Aaronson (07:08.760)
I think in some sense,
Lex Fridman (07:10.120)
that is the right way to phrase the question.
Lex Fridman (07:13.800)
And actually, what we learned, I mean, throughout history,
Lex Fridman (07:19.240)
but really starting with the scientific revolution
Scott Aaronson (07:21.920)
with Galileo and so on,
Lex Fridman (07:24.000)
is that there is a good reason to focus
Scott Aaronson (07:26.840)
on narrower questions, more technical,
Lex Fridman (07:31.320)
mathematical or empirical questions.
Lex Fridman (07:33.600)
And that is that you can actually make progress on them,
Lex Fridman (07:36.520)
and you can actually often answer them.
Lex Fridman (07:39.260)
And sometimes they actually tell you something
Lex Fridman (07:41.760)
about the philosophical questions
Scott Aaronson (07:43.820)
that sort of maybe motivated your curiosity as a child.
Lex Fridman (07:48.500)
They don't necessarily resolve the philosophical questions,
Lex Fridman (07:51.760)
but sometimes they reframe
Lex Fridman (07:53.300)
your whole understanding of them, right?
Lex Fridman (07:55.120)
And so for me, philosophy is just the thing
Lex Fridman (07:58.120)
that you have in the background from the very beginning
Scott Aaronson (08:00.920)
that you want to, these are sort of the reasons
Lex Fridman (08:05.480)
why you went into intellectual life in the first place,
Lex Fridman (08:08.640)
at least the reasons why I did, right?
Lex Fridman (08:11.720)
But math and science are tools that we have
Scott Aaronson (08:15.200)
for actually making progress.
Lex Fridman (08:17.540)
And hopefully even changing our understanding
Scott Aaronson (08:21.480)
of these philosophical questions,
Lex Fridman (08:23.280)
sometimes even more than philosophy itself does.
Lex Fridman (08:26.400)
Why do you think computer scientists avoid these questions?
Lex Fridman (08:30.560)
We'll run away from them a little bit,
Scott Aaronson (08:31.880)
at least in a technical scientific discourse.
Lex Fridman (08:34.600)
Well, I'm not sure if they do so
Scott Aaronson (08:37.000)
more than any other scientists do.
Lex Fridman (08:39.200)
I mean, Alan Turing was famously interested
Lex Fridman (08:44.400)
and his most famous, one of his two most famous papers
Lex Fridman (08:49.760)
was in a philosophy journal mind.
Scott Aaronson (08:52.040)
It was the one where he proposed the Turing test.
Lex Fridman (08:55.640)
He took a Wittgenstein's course at Cambridge,
Scott Aaronson (08:59.920)
argued with him.
Lex Fridman (09:01.440)
I just recently learned that little bit
Lex Fridman (09:03.840)
and it's actually fascinating.
Lex Fridman (09:05.340)
I was trying to look for resources
Scott Aaronson (09:08.440)
in trying to understand where the sources of disagreement
Lex Fridman (09:12.400)
and debates between Wittgenstein and Turing were.
Scott Aaronson (09:15.720)
That's interesting that these two minds
Lex Fridman (09:17.480)
have somehow met in the arc of history.
Scott Aaronson (09:20.200)
Yeah, well, the transcript of the course,
Lex Fridman (09:25.200)
which was in 1939, right,
Scott Aaronson (09:26.880)
is one of the more fascinating documents that I've ever read
Lex Fridman (09:29.960)
because Wittgenstein is trying to say,
Scott Aaronson (09:33.560)
well, all of these formal systems
Lex Fridman (09:36.180)
are just complete irrelevancies, right?
Lex Fridman (09:41.680)
If a formal system is irrelevant, who cares?
Lex Fridman (09:44.560)
Why does that matter in real life, right?
Lex Fridman (09:46.880)
And Turing is saying, well, look,
Lex Fridman (09:49.000)
if you use an inconsistent formal system to design a bridge,
Lex Fridman (09:52.640)
the bridge may collapse, right?
Lex Fridman (09:55.160)
And so Turing, in some sense, is thinking decades ahead,
Scott Aaronson (09:58.900)
you know, I think, of where Wittgenstein is,
Lex Fridman (10:01.640)
to where the formal systems are actually going to be used
Scott Aaronson (10:05.040)
in computers, right, to actually do things in the world.
Lex Fridman (10:08.720)
You know, and it's interesting that Turing
Scott Aaronson (10:10.400)
actually dropped the course halfway through.
Lex Fridman (10:13.120)
Why?
Scott Aaronson (10:13.960)
Because he had to go to Bletchley Park
Lex Fridman (10:15.320)
and work on something of more immediate importance.
Scott Aaronson (10:18.240)
That's fascinating.
Lex Fridman (10:19.880)
Take a step from philosophy to actual,
Scott Aaronson (10:22.180)
like the biggest possible step to actual engineering
Lex Fridman (10:25.020)
with actual real impact.
Scott Aaronson (10:26.400)
Yeah, and I would say more generally, right,
Lex Fridman (10:30.360)
a lot of scientists are interested in philosophy,
Lex Fridman (10:35.100)
but they're also busy, right?
Lex Fridman (10:36.700)
And they have a lot on their plate,
Lex Fridman (10:39.460)
and there are a lot of sort of very concrete questions
Lex Fridman (10:42.760)
that are already not answered,
Lex Fridman (10:44.880)
but look like they might be answerable, right?
Lex Fridman (10:47.940)
And so then you could say, well, then why break your brain
Scott Aaronson (10:52.880)
over these metaphysically unanswerable questions
Lex Fridman (10:55.940)
when there were all of these answerable ones instead?
Lex Fridman (10:59.340)
So I think, you know, for me,
Lex Fridman (11:03.240)
I enjoy talking about philosophy.
Scott Aaronson (11:06.240)
I even go to philosophy conferences sometimes,
Lex Fridman (11:09.840)
such as the FQXI conferences.
Scott Aaronson (11:12.040)
I enjoy interacting with philosophers.
Lex Fridman (11:14.920)
I would not want to be a professional philosopher
Scott Aaronson (11:17.740)
because I like being in a field where I feel like,
Lex Fridman (11:20.880)
you know, if I get too confused
Scott Aaronson (11:25.400)
about the sort of eternal questions,
Lex Fridman (11:27.100)
then I can actually make progress on something.
Lex Fridman (11:30.060)
Can you maybe link on that for just a little longer?
Lex Fridman (11:32.840)
What do you think is the difference?
Lex Fridman (11:34.600)
So like the corollary of the criticism
Lex Fridman (11:37.640)
that I mentioned previously,
Scott Aaronson (11:40.120)
that why ask the philosophical questions
Lex Fridman (11:42.520)
of the mathematician is if you want
Scott Aaronson (11:44.960)
to ask philosophical questions,
Lex Fridman (11:46.220)
then invite a real philosopher on and ask them.
Lex Fridman (11:49.020)
So what's the difference between the way
Lex Fridman (11:51.200)
a computer scientist or mathematician
Scott Aaronson (11:52.920)
ponders a philosophical question
Lex Fridman (11:54.640)
and a philosopher ponders a philosophical question?
Scott Aaronson (11:57.280)
Well, I mean, a lot of it just depends
Lex Fridman (11:59.280)
on the individual, right?
Scott Aaronson (12:01.000)
It's hard to make generalizations about entire fields,
Lex Fridman (12:04.760)
but, you know, I think if we tried to,
Scott Aaronson (12:09.560)
if we tried to stereotype, you know,
Lex Fridman (12:11.440)
we would say that scientists very often
Scott Aaronson (12:16.440)
will be less careful in their use of words.
Lex Fridman (12:21.860)
You know, I mean, philosophers are really experts
Scott Aaronson (12:24.160)
in sort of, you know, like when I talk to them,
Lex Fridman (12:27.140)
they will just pounce if I, you know,
Scott Aaronson (12:28.820)
use the wrong phrase for something.
Lex Fridman (12:30.780)
Experts is a very nice word.
Scott Aaronson (12:32.540)
You could say sticklers.
Lex Fridman (12:34.060)
Sticklers, yeah, yeah, yeah, or, you know,
Scott Aaronson (12:35.980)
they will sort of interrogate my word choices,
Lex Fridman (12:39.140)
let's say, to a much greater extent
Lex Fridman (12:41.360)
than scientists would, right?
Lex Fridman (12:42.900)
And scientists, you know, will often,
Scott Aaronson (12:46.300)
if you ask them about a philosophical problem,
Lex Fridman (12:48.940)
like the hard problem of consciousness
Scott Aaronson (12:51.900)
or free will or whatever,
Lex Fridman (12:53.580)
they will try to relate it back to, you know,
Scott Aaronson (12:55.740)
recent research, you know, research about neurobiology
Lex Fridman (13:01.200)
or, you know, the best of all is research
Lex Fridman (13:03.880)
that they personally are involved with, right?
Lex Fridman (13:06.480)
And, you know, of course they will want to talk about that,
Scott Aaronson (13:10.160)
you know, and it is what they will think of, you know,
Lex Fridman (13:12.260)
and of course you could have an argument
Scott Aaronson (13:14.140)
that maybe, you know, it's all interesting as it goes,
Lex Fridman (13:17.300)
but maybe none of it touches the philosophical question,
Lex Fridman (13:20.100)
right?
Lex Fridman (13:20.940)
But, you know, but maybe, you know, a science,
Scott Aaronson (13:24.300)
you know, at least it, as I said,
Lex Fridman (13:26.600)
it does tell us concrete things.
Scott Aaronson (13:29.020)
And, you know, even if like a deep dive into neurobiology
Lex Fridman (13:33.520)
will not answer the hard problem of consciousness,
Scott Aaronson (13:36.580)
you know, maybe it can take us about as far as we can get
Lex Fridman (13:40.540)
toward, you know, expanding our minds about it,
Scott Aaronson (13:44.420)
you know, toward thinking about it in a different way.
Lex Fridman (13:48.760)
Well, I mean, I think neurobiology can do that,
Scott Aaronson (13:51.080)
but, you know, with these profound philosophical questions,
Lex Fridman (13:53.840)
I mean, also art and literature do that, right?
Scott Aaronson (13:56.940)
They're all different ways
Lex Fridman (13:58.020)
of trying to approach these questions that, you know,
Scott Aaronson (14:00.260)
we don't, for which we don't even know really
Lex Fridman (14:02.220)
what an answer would look like,
Scott Aaronson (14:03.700)
but, and yet somehow we can't help,
Lex Fridman (14:06.200)
but keep returning to the questions.
Lex Fridman (14:07.820)
And you have a kind of mathematical,
Lex Fridman (14:09.260)
beautiful mathematical way of discussing this
Scott Aaronson (14:11.260)
with the idea of Q prime.
Lex Fridman (14:12.740)
Oh, right.
Scott Aaronson (14:13.580)
You write that usually the only way to make progress
Lex Fridman (14:16.780)
on the big questions, like the philosophical questions
Scott Aaronson (14:20.060)
we're talking about now is to pick off smaller sub questions.
Lex Fridman (14:24.340)
Ideally sub questions that you can attack
Scott Aaronson (14:26.380)
using math, empirical observation, or both.
Lex Fridman (14:29.140)
You define the idea of a Q prime.
Lex Fridman (14:31.380)
So given an unanswerable philosophical riddle Q,
Lex Fridman (14:36.140)
replace it with a merely, in quotes, scientific
Scott Aaronson (14:39.700)
or mathematical question Q prime,
Lex Fridman (14:41.900)
which captures part of what people have wanted to know
Scott Aaronson (14:44.840)
when they first asked Q.
Lex Fridman (14:47.300)
Then with luck, one solves Q prime.
Lex Fridman (14:49.900)
So you described some examples of such Q prime sub questions
Lex Fridman (14:55.420)
in your long essay titled,
Lex Fridman (14:59.180)
Why Philosophers Should Care About Computational Complexity.
Lex Fridman (15:02.460)
So you catalog the various Q primes
Scott Aaronson (15:04.560)
on which you think theoretical computer science
Lex Fridman (15:07.140)
has made progress.
Lex Fridman (15:08.020)
Can you mention a few favorites, if any pop to mind,
Lex Fridman (15:12.260)
or do you remember some?
Scott Aaronson (15:13.100)
Well, yeah.
Lex Fridman (15:13.940)
So, I mean, I would say some of the most famous examples
Scott Aaronson (15:16.940)
in history of that sort of replacement were,
Lex Fridman (15:20.740)
I mean, to go back to Alan Turing, right?
Lex Fridman (15:23.240)
What he did in his computing machinery
Lex Fridman (15:26.460)
and intelligence paper was exactly,
Scott Aaronson (15:29.340)
he explicitly started with the question,
Lex Fridman (15:32.100)
can machines think?
Lex Fridman (15:33.820)
And then he said, sorry,
Lex Fridman (15:35.780)
I think that question is too meaningless,
Lex Fridman (15:38.020)
but here's a different question.
Lex Fridman (15:40.380)
Could you program a computer
Lex Fridman (15:42.140)
so that you couldn't tell the difference
Lex Fridman (15:43.620)
between it and a human, right?
Lex Fridman (15:45.220)
And yeah.
Lex Fridman (15:46.060)
So in the very first few sentences,
Scott Aaronson (15:47.940)
he in fact just formulates the Q prime question.
Lex Fridman (15:50.900)
He does precisely that.
Lex Fridman (15:52.600)
Or we could look at Gödel, right?
Lex Fridman (15:56.140)
Where you had these philosophers arguing for centuries
Lex Fridman (16:00.420)
about the limits of mathematical reasoning, right?
Lex Fridman (16:03.060)
The limits of formal systems.
Lex Fridman (16:04.660)
And then by the early 20th century,
Lex Fridman (16:08.740)
logicians, starting with Frege, Russell,
Lex Fridman (16:12.340)
and then most spectacularly Gödel,
Lex Fridman (16:15.480)
managed to reframe those questions as,
Scott Aaronson (16:18.100)
look, we have these formal systems.
Lex Fridman (16:19.840)
They have these definite rules.
Scott Aaronson (16:21.500)
Are there questions that we can phrase
Lex Fridman (16:23.480)
within the rules of these systems
Lex Fridman (16:25.740)
that are not provable within the rules of the systems?
Lex Fridman (16:28.220)
And can we prove that fact, right?
Lex Fridman (16:30.500)
And so that would be another example.
Lex Fridman (16:34.740)
You know, I had this essay called
Scott Aaronson (16:36.640)
The Ghost in the Quantum Turing Machine.
Lex Fridman (16:38.980)
That was one of the crazier things I've written,
Lex Fridman (16:41.900)
but I tried to do something,
Lex Fridman (16:44.740)
or to advocate doing something similar there for free will,
Scott Aaronson (16:48.740)
where instead of talking about is free will real,
Lex Fridman (16:53.220)
where we get hung up on the meaning of,
Lex Fridman (16:55.500)
what exactly do we mean by freedom?
Lex Fridman (16:57.500)
And can you have, can you be,
Scott Aaronson (16:59.740)
or do we mean compatibilist free will,
Lex Fridman (17:02.220)
libertarian free will?
Lex Fridman (17:03.660)
What do these things mean?
Lex Fridman (17:05.100)
You know, I suggested just asking the question,
Lex Fridman (17:08.200)
how well in principle, consistently with the laws of physics,
Lex Fridman (17:12.320)
could a person's behavior be predicted?
Scott Aaronson (17:15.100)
You know, without, so let's say,
Lex Fridman (17:16.620)
destroying the person's brain, you know,
Scott Aaronson (17:18.820)
taking it apart in the process of trying to predict them.
Lex Fridman (17:22.140)
And, you know, and that actually,
Scott Aaronson (17:24.620)
asking that question gets you into all sorts of meaty
Lex Fridman (17:27.700)
and interesting issues, you know, issues of,
Lex Fridman (17:31.100)
what is the computational substrate of the brain?
Lex Fridman (17:33.820)
You know, or can you understand the brain, you know,
Scott Aaronson (17:37.100)
just at the sort of level of the neurons, you know,
Lex Fridman (17:39.740)
at sort of the abstraction of a neural network,
Scott Aaronson (17:42.380)
or do you need to go deeper to the, you know,
Lex Fridman (17:44.940)
molecular level and ultimately even to the quantum level?
Scott Aaronson (17:48.060)
Right, and of course,
Lex Fridman (17:48.900)
that would put limits on predictability if you did.
Lex Fridman (17:52.700)
So you need to reduce,
Lex Fridman (17:53.940)
you need to reduce the mind to a computational device,
Scott Aaronson (17:58.580)
like formalize it so then you can make predictions
Lex Fridman (18:01.180)
about what, you know, whether you could predict the behavior
Scott Aaronson (18:03.860)
of the system. Well, if you were trying
Lex Fridman (18:04.700)
to predict a person, yeah, then presumably,
Lex Fridman (18:06.860)
you would need some model of their brain, right?
Lex Fridman (18:09.180)
And now the question becomes one of,
Lex Fridman (18:11.180)
how accurate can such a model become?
Lex Fridman (18:13.780)
Can you make a model that will be accurate enough
Lex Fridman (18:16.780)
to really seriously threaten people's sense of free will?
Lex Fridman (18:21.060)
You know, not just metaphysically, but like really,
Scott Aaronson (18:23.660)
I have written in this envelope
Lex Fridman (18:25.140)
what you were going to say next.
Lex Fridman (18:26.780)
Is accuracy the right term here?
Lex Fridman (18:28.940)
So it's also a level of abstraction has to be right.
Lex Fridman (18:32.620)
So if you're accurate at the, somehow at the quantum level,
Lex Fridman (18:39.060)
that may not be convincing to us at the human level.
Scott Aaronson (18:42.980)
Well, right, but the question is what accuracy
Lex Fridman (18:46.100)
at the sort of level of the underlying mechanisms
Lex Fridman (18:49.020)
do you need in order to predict the behavior, right?
Lex Fridman (18:52.180)
At the end of the day, the test is just,
Lex Fridman (18:54.300)
can you, you know, foresee what the person is going to do?
Lex Fridman (18:57.860)
Right, I am, you know, and in discussions of free will,
Scott Aaronson (19:03.340)
you know, it seems like both sides wanna, you know,
Lex Fridman (19:06.340)
very quickly dismiss that question as irrelevant.
Scott Aaronson (19:09.420)
Well, to me, it's totally relevant.
Lex Fridman (19:11.420)
Okay, because, you know, if someone says,
Scott Aaronson (19:14.300)
oh, well, you know, a Laplace demon
Lex Fridman (19:16.900)
that knew the complete state of the universe,
Scott Aaronson (19:19.900)
you know, could predict everything you're going to do,
Lex Fridman (19:22.140)
therefore you don't have free will.
Scott Aaronson (19:24.100)
You know, it doesn't trouble me that much because,
Lex Fridman (19:27.020)
well, you know, I've never met such a demon, right?
Scott Aaronson (19:29.820)
You know, and we, you know, we even have some reasons
Lex Fridman (19:34.140)
to think, you know, maybe, you know,
Scott Aaronson (19:35.180)
it could not exist as part of our world,
Lex Fridman (19:37.260)
you know, it's only an abstraction, a thought experiment.
Scott Aaronson (19:40.740)
On the other hand, if someone said,
Lex Fridman (19:42.540)
well, you know, I have this brain scanning machine,
Scott Aaronson (19:44.940)
you know, you step into it and then, you know,
Lex Fridman (19:47.180)
every paper that you will ever write, it will write,
Scott Aaronson (19:50.220)
you know, every thought that you will have, you know,
Lex Fridman (19:52.420)
even right now about the machine itself, it will foresee.
Scott Aaronson (19:55.740)
You know, well, if you can actually demonstrate that,
Lex Fridman (19:58.620)
then I think, you know, that sort of threatens
Lex Fridman (1:00:00.300)
but you briefly mentioned it,
Lex Fridman (1:00:02.620)
but let's maybe try to continue.
Lex Fridman (1:00:05.260)
So you said the definition of quantum supremacy
Lex Fridman (1:00:08.540)
is basically achieving a place
Scott Aaronson (1:00:12.380)
where much faster on a formal,
Lex Fridman (1:00:14.940)
that quantum computer is much faster
Scott Aaronson (1:00:16.460)
on a formal well defined problem
Lex Fridman (1:00:19.340)
that is or isn't useful.
Scott Aaronson (1:00:21.100)
Yeah, yeah, yeah, right, right.
Lex Fridman (1:00:22.300)
And I would say that we really want three things, right?
Scott Aaronson (1:00:25.260)
We want, first of all,
Lex Fridman (1:00:26.860)
the quantum computer to be much faster
Scott Aaronson (1:00:29.260)
just in the literal sense of like number of seconds,
Lex Fridman (1:00:31.980)
you know, it's a solving this, you know,
Scott Aaronson (1:00:34.540)
well defined, you know, problem.
Lex Fridman (1:00:36.940)
Secondly, we want it to be sort of, you know,
Scott Aaronson (1:00:40.540)
for a problem where we really believe
Lex Fridman (1:00:42.700)
that a quantum computer has better scaling behavior, right?
Lex Fridman (1:00:45.980)
So it's not just an incidental, you know,
Lex Fridman (1:00:48.780)
matter of hardware,
Lex Fridman (1:00:50.060)
but it's that, you know,
Lex Fridman (1:00:51.180)
as you went to larger and larger inputs,
Scott Aaronson (1:00:53.900)
you know, the classical scaling would be exponential
Lex Fridman (1:00:57.180)
and the scaling for the quantum algorithm
Scott Aaronson (1:00:59.660)
would only be polynomial.
Lex Fridman (1:01:01.500)
And then thirdly, we want the first thing,
Scott Aaronson (1:01:04.060)
the actual observed speed up
Lex Fridman (1:01:06.220)
to only be explainable in terms of the scaling behavior, right?
Scott Aaronson (1:01:10.620)
So, you know, I want, you know,
Lex Fridman (1:01:12.700)
a real world, you know, a real problem to get solved,
Scott Aaronson (1:01:16.460)
let's say by a quantum computer with 50 qubits or so,
Lex Fridman (1:01:20.460)
and for no one to be able to explain that in any way
Scott Aaronson (1:01:23.580)
other than, well, you know, this computer involved a quantum state
Lex Fridman (1:01:30.300)
with two to the 50th power amplitudes.
Scott Aaronson (1:01:33.180)
And, you know, a classical simulation,
Lex Fridman (1:01:35.180)
at least any that we know today,
Scott Aaronson (1:01:37.100)
would require keeping track of two to the 50th numbers.
Lex Fridman (1:01:40.460)
And this is the reason why it was faster.
Lex Fridman (1:01:42.380)
So the intuition is that then if you demonstrate on 50 qubits,
Lex Fridman (1:01:46.700)
then once you get to 100 qubits,
Scott Aaronson (1:01:48.300)
then it'll be even much more faster.
Lex Fridman (1:01:50.780)
Precisely, precisely.
Scott Aaronson (1:01:52.460)
Yeah, and, you know, and quantum supremacy
Lex Fridman (1:01:55.020)
does not require error correction, right?
Scott Aaronson (1:01:57.100)
We don't, you know, we don't have, you could say,
Lex Fridman (1:01:58.860)
true scalability yet or true, you know, error correction yet.
Lex Fridman (1:02:04.540)
But you could say quantum supremacy is already enough by itself
Lex Fridman (1:02:08.860)
to refute the skeptics who said a quantum computer
Scott Aaronson (1:02:12.140)
will never outperform a classical computer for anything.
Lex Fridman (1:02:15.260)
But one, how do you demonstrate quantum supremacy?
Lex Fridman (1:02:20.460)
And two, what's up with these news articles
Lex Fridman (1:02:23.740)
I'm reading that Google did so?
Scott Aaronson (1:02:25.820)
Yeah, all right, well, great, great questions,
Lex Fridman (1:02:28.860)
because now you get into actually, you know,
Scott Aaronson (1:02:31.900)
a lot of the work that I've, you know,
Lex Fridman (1:02:34.140)
I and my students have been doing for the last decade,
Scott Aaronson (1:02:36.940)
which was precisely about how do you demonstrate
Lex Fridman (1:02:41.020)
quantum supremacy using technologies that, you know,
Scott Aaronson (1:02:44.220)
we thought would be available in the near future.
Lex Fridman (1:02:47.100)
And so one of the main things that we realized around 2011,
Lex Fridman (1:02:53.740)
and this was me and my student, Alex Arkhipov at MIT at the time,
Lex Fridman (1:02:59.900)
and independently of some others,
Lex Fridman (1:03:03.180)
including Bremner, Joseph, and Shepherd, okay?
Lex Fridman (1:03:06.220)
And the realization that we came to was that
Scott Aaronson (1:03:10.940)
if you just want to prove that a quantum computer is faster,
Lex Fridman (1:03:14.860)
you know, and not do something useful with it,
Scott Aaronson (1:03:17.260)
then there are huge advantages to sort of switching
Lex Fridman (1:03:20.300)
your attention from problems like factoring numbers
Scott Aaronson (1:03:23.900)
that have a single right answer
Lex Fridman (1:03:26.060)
to what we call sampling problems.
Lex Fridman (1:03:28.540)
So these are problems where the goal is just to output
Lex Fridman (1:03:31.980)
a sample from some probability distribution,
Lex Fridman (1:03:35.420)
let's say over strings of 50 bits, right?
Lex Fridman (1:03:38.060)
So there are, you know, many, many,
Scott Aaronson (1:03:40.060)
many possible valid outputs.
Lex Fridman (1:03:42.060)
You know, your computer will probably never even produce
Scott Aaronson (1:03:44.540)
the same output twice, you know,
Lex Fridman (1:03:46.540)
if it's running as, even, you know,
Lex Fridman (1:03:50.620)
assuming it's running perfectly, okay?
Lex Fridman (1:03:52.780)
But the key is that some outputs are supposed
Scott Aaronson (1:03:55.660)
to be likelier than other ones.
Lex Fridman (1:03:57.740)
So, sorry, to clarify, is there a set of outputs
Scott Aaronson (1:04:01.980)
that are valid and set they're not,
Lex Fridman (1:04:03.740)
or is it more that the distribution
Scott Aaronson (1:04:07.980)
of a particular kind of output is more,
Lex Fridman (1:04:11.420)
is like there's a specific distribution
Lex Fridman (1:04:13.260)
of a particular kind of output?
Lex Fridman (1:04:14.860)
Yeah, there's a specific distribution
Lex Fridman (1:04:16.540)
that you're trying to hit, right?
Lex Fridman (1:04:17.980)
Or, you know, that you're trying to sample from.
Scott Aaronson (1:04:19.980)
Now, there are a lot of questions about this,
Lex Fridman (1:04:22.460)
you know, how do you do that, right?
Scott Aaronson (1:04:24.540)
Now, how you do it, you know,
Lex Fridman (1:04:27.660)
it turns out that with a quantum computer,
Scott Aaronson (1:04:30.220)
even with the noisy quantum computers
Lex Fridman (1:04:32.220)
that we have now, that we have today,
Lex Fridman (1:04:34.780)
what you can do is basically just apply
Lex Fridman (1:04:36.940)
a randomly chosen sequence of operations, right?
Lex Fridman (1:04:40.220)
So we, you know, in some of the, you know,
Lex Fridman (1:04:42.380)
that part is almost trivial, right?
Scott Aaronson (1:04:44.540)
We just sort of get the qubits to interact
Lex Fridman (1:04:47.260)
in some random way,
Scott Aaronson (1:04:48.540)
although a sort of precisely specified random way
Lex Fridman (1:04:51.580)
so we can repeat the exact same random sequence
Scott Aaronson (1:04:54.940)
of interactions again and get another sample
Lex Fridman (1:04:57.580)
from that same distribution.
Lex Fridman (1:04:59.500)
And what this does is it basically,
Lex Fridman (1:05:01.820)
well, it creates a lot of garbage,
Lex Fridman (1:05:04.060)
but, you know, very specific garbage, right?
Lex Fridman (1:05:06.620)
So, you know, of all of the,
Lex Fridman (1:05:09.100)
so we're gonna talk about Google's device
Lex Fridman (1:05:11.340)
that were 53 qubits there, okay?
Lex Fridman (1:05:14.060)
And so there were two to the 53 power possible outputs.
Lex Fridman (1:05:18.060)
Now, for some of those outputs,
Scott Aaronson (1:05:19.980)
you know, there was a little bit more
Lex Fridman (1:05:22.540)
destructive interference in their amplitude, okay?
Lex Fridman (1:05:25.660)
So their amplitudes were a little bit smaller.
Lex Fridman (1:05:28.060)
And for others, there was a little more
Scott Aaronson (1:05:29.500)
constructive interference.
Lex Fridman (1:05:31.180)
You know, the amplitudes were a little bit
Scott Aaronson (1:05:32.860)
more aligned with each other, you know,
Lex Fridman (1:05:35.180)
and so those were a little bit likelier, okay?
Scott Aaronson (1:05:38.860)
All of the outputs are exponentially unlikely,
Lex Fridman (1:05:42.140)
but some are, let's say, two times or three times,
Lex Fridman (1:05:45.340)
you know, unlikelier than others, okay?
Lex Fridman (1:05:47.740)
And so you can define, you know,
Scott Aaronson (1:05:50.700)
this sequence of operations that gives rise
Lex Fridman (1:05:53.500)
to this probability distribution.
Scott Aaronson (1:05:55.660)
Okay, now the next question would be,
Lex Fridman (1:05:58.700)
well, how do you, you know,
Scott Aaronson (1:05:59.660)
even if you're sampling from it,
Lex Fridman (1:06:01.020)
how do you verify that, right?
Lex Fridman (1:06:02.460)
How do you know?
Lex Fridman (1:06:04.060)
And so my students and I,
Lex Fridman (1:06:06.780)
and also the people at Google
Lex Fridman (1:06:09.260)
were doing the experiment,
Scott Aaronson (1:06:10.380)
came up with statistical tests
Lex Fridman (1:06:12.940)
that you can apply to the outputs
Scott Aaronson (1:06:15.900)
in order to try to verify, you know,
Lex Fridman (1:06:20.620)
what is, you know, that at least
Scott Aaronson (1:06:22.620)
that some hard problem is being solved.
Lex Fridman (1:06:25.900)
The test that Google ended up using
Scott Aaronson (1:06:28.620)
was something that they called
Lex Fridman (1:06:29.820)
the linear cross entropy benchmark, okay?
Lex Fridman (1:06:32.780)
And it's basically, you know,
Lex Fridman (1:06:34.220)
so the drawback of this test
Scott Aaronson (1:06:36.300)
is that it requires, like,
Lex Fridman (1:06:38.140)
it requires you to do a two to the 53 time calculation
Lex Fridman (1:06:43.020)
with your classical computer, okay?
Lex Fridman (1:06:44.860)
So it's very expensive to do the test
Scott Aaronson (1:06:47.740)
on a classical computer.
Lex Fridman (1:06:49.260)
The good news is...
Lex Fridman (1:06:49.900)
How big of a number is two to the 53?
Lex Fridman (1:06:51.660)
It's about nine quadrillion, okay?
Scott Aaronson (1:06:53.820)
That doesn't help.
Lex Fridman (1:06:55.100)
Well, you know,
Scott Aaronson (1:06:55.820)
it's, you want it in like scientific notation.
Lex Fridman (1:06:58.380)
No, no, no, what I mean is...
Scott Aaronson (1:06:59.660)
Yeah, it is just...
Lex Fridman (1:07:01.020)
It's impossible to run on a...
Scott Aaronson (1:07:02.860)
Yeah, so we will come back to that.
Lex Fridman (1:07:04.780)
It is just barely possible to run,
Scott Aaronson (1:07:07.420)
we think, on the largest supercomputer
Lex Fridman (1:07:09.260)
that currently exists on Earth,
Lex Fridman (1:07:10.940)
which is called Summit at Oak Ridge National Lab, okay?
Lex Fridman (1:07:15.340)
Great, this is exciting.
Scott Aaronson (1:07:16.780)
That's the short answer.
Lex Fridman (1:07:18.220)
So ironically, for this type of experiment,
Lex Fridman (1:07:21.900)
we don't want 100 qubits, okay?
Lex Fridman (1:07:24.300)
Because with 100 qubits, even if it works,
Lex Fridman (1:07:26.940)
we don't know how to verify the results, okay?
Lex Fridman (1:07:29.580)
So we want, you know, a number of qubits
Scott Aaronson (1:07:32.060)
that is enough that, you know,
Lex Fridman (1:07:33.100)
the biggest classical computers on Earth
Scott Aaronson (1:07:36.300)
will have to sweat, you know,
Lex Fridman (1:07:38.140)
and we'll just barely, you know,
Scott Aaronson (1:07:39.980)
be able to keep up with the quantum computer,
Lex Fridman (1:07:42.700)
you know, using much more time,
Lex Fridman (1:07:44.460)
but they will still be able to do it
Lex Fridman (1:07:46.540)
in order that we can verify the results.
Lex Fridman (1:07:48.300)
Which is where the 53 comes from for the number of qubits?
Lex Fridman (1:07:50.540)
Basically, well, I mean, that's also,
Scott Aaronson (1:07:53.180)
that's sort of, you know,
Lex Fridman (1:07:55.420)
I mean, that's sort of where they are now
Lex Fridman (1:07:58.780)
in terms of scaling, you know?
Lex Fridman (1:08:00.380)
And then, you know, soon, you know, that point will be passed.
Lex Fridman (1:08:03.660)
And then when you get to larger numbers of qubits,
Lex Fridman (1:08:06.780)
then, you know, these types of sampling experiments
Scott Aaronson (1:08:10.060)
will no longer be so interesting
Lex Fridman (1:08:12.140)
because we won't even be able to verify the results
Lex Fridman (1:08:14.860)
and we'll have to switch to other types of computation.
Lex Fridman (1:08:17.740)
So with the sampling thing,
Scott Aaronson (1:08:19.660)
you know, so the test that Google applied
Lex Fridman (1:08:22.460)
with this linear cross entropy benchmark
Scott Aaronson (1:08:24.700)
was basically just take the samples that were generated,
Lex Fridman (1:08:28.460)
which are, you know, a very small subset
Scott Aaronson (1:08:30.780)
of all the possible samples that there are.
Lex Fridman (1:08:32.940)
But for those, you calculate with your classical computer
Scott Aaronson (1:08:36.540)
the probabilities that they should have been output.
Lex Fridman (1:08:39.500)
And you see, are those probabilities
Lex Fridman (1:08:41.500)
like larger than the mean?
Lex Fridman (1:08:43.020)
You know, so is the quantum computer biased
Scott Aaronson (1:08:45.260)
toward outputting the strings that it's,
Lex Fridman (1:08:47.500)
you know, that you want it to be biased toward?
Scott Aaronson (1:08:50.300)
Okay, and then finally,
Lex Fridman (1:08:51.980)
we come to a very crucial question,
Scott Aaronson (1:08:54.220)
which is supposing that it does that.
Lex Fridman (1:08:56.140)
Well, how do we know that a classical computer
Lex Fridman (1:08:58.380)
could not have quickly done the same thing, right?
Lex Fridman (1:09:01.260)
How do we know that, you know,
Lex Fridman (1:09:02.380)
this couldn't have been spoofed by a classical computer, right?
Lex Fridman (1:09:05.500)
And so, well, the first answer is we don't know for sure
Scott Aaronson (1:09:09.820)
because, you know, this takes us
Lex Fridman (1:09:11.180)
into questions of complexity theory.
Scott Aaronson (1:09:13.740)
You know, I mean, questions of the magnitude
Lex Fridman (1:09:17.740)
of the P versus NP question and things like that, right?
Scott Aaronson (1:09:20.380)
You know, we don't know how to rule out definitively
Lex Fridman (1:09:23.500)
that there could be fast classical algorithms
Scott Aaronson (1:09:26.540)
for, you know, even simulating quantum mechanics
Lex Fridman (1:09:28.940)
and for, you know, simulating experiments like these,
Lex Fridman (1:09:32.300)
but we can give some evidence against that possibility.
Lex Fridman (1:09:36.140)
And that was sort of the, you know,
Scott Aaronson (1:09:37.980)
the main thrust of a lot of the work
Lex Fridman (1:09:40.140)
that my colleagues and I did, you know,
Scott Aaronson (1:09:42.540)
over the last decade,
Lex Fridman (1:09:43.660)
which is then sort of in around 2015 or so,
Lex Fridman (1:09:46.780)
what led to Google deciding to do this experiment.
Lex Fridman (1:09:49.900)
So is the kind of evidence here,
Scott Aaronson (1:09:52.540)
first of all, the hard P equals NP problem that you mentioned
Lex Fridman (1:09:55.820)
and the kind of evidence that you were looking at,
Scott Aaronson (1:10:00.780)
is that something you come to on a sheet of paper
Lex Fridman (1:10:03.740)
or is this something, are these empirical experiments?
Scott Aaronson (1:10:07.420)
It's math for the most part.
Lex Fridman (1:10:09.500)
I mean, you know, it's also, you know,
Scott Aaronson (1:10:12.700)
we have a bunch of methods
Lex Fridman (1:10:15.740)
that are known for simulating quantum circuits
Scott Aaronson (1:10:19.980)
or quantum computations with classical computers.
Lex Fridman (1:10:23.500)
And so we have to try them all out
Lex Fridman (1:10:25.260)
and make sure that, you know, they don't work,
Lex Fridman (1:10:27.500)
you know, make sure that they have exponential scaling
Scott Aaronson (1:10:30.220)
on, you know, these problems and not just theoretically,
Lex Fridman (1:10:34.140)
but with the actual range of parameters
Scott Aaronson (1:10:36.300)
that are actually, you know, arising in Google's experiment.
Lex Fridman (1:10:40.300)
Okay, so there is an empirical component to it, right?
Lex Fridman (1:10:43.340)
But now on the theoretical side,
Lex Fridman (1:10:47.100)
you know, basically what we know how to do
Scott Aaronson (1:10:49.740)
in theoretical computer science and computational complexity
Lex Fridman (1:10:53.580)
is, you know, we don't know how to prove
Scott Aaronson (1:10:56.060)
that most of the problems we care about are hard,
Lex Fridman (1:10:58.780)
but we know how to pass the blame to someone else, okay?
Scott Aaronson (1:11:01.900)
We know how to say, well, look, you know,
Lex Fridman (1:11:03.980)
I can't prove that this problem is hard,
Lex Fridman (1:11:06.300)
but if it is easy, then all these other things
Lex Fridman (1:11:08.860)
that, you know, you probably were much more confident
Lex Fridman (1:11:13.020)
or were hard, then those would be easy as well, okay?
Lex Fridman (1:11:16.780)
So we can give what are called reductions.
Scott Aaronson (1:11:19.660)
This has been the basic strategy in, you know,
Lex Fridman (1:11:22.700)
NP completeness, right, in all of theoretical computer science
Lex Fridman (1:11:27.420)
and cryptography since the 1970s, really.
Lex Fridman (1:11:31.020)
And so we were able to give some reduction evidence
Scott Aaronson (1:11:34.300)
for the hardness of simulating these sampling experiments,
Lex Fridman (1:11:40.140)
these sampling based quantum supremacy experiments.
Lex Fridman (1:11:43.100)
So reduction evidence is not as satisfactory as it should be.
Lex Fridman (1:11:47.260)
One of the biggest open problems in this area
Scott Aaronson (1:11:49.900)
is to make it better.
Lex Fridman (1:11:51.420)
But, you know, we can do something.
Scott Aaronson (1:11:53.260)
You know, certainly we can say that, you know,
Lex Fridman (1:11:56.700)
if there is a fast classical algorithm
Scott Aaronson (1:11:59.340)
to spoof these experiments, then it has to be very,
Lex Fridman (1:12:02.220)
very unlike any of the algorithms that we know.
Scott Aaronson (1:12:04.620)
TREVOR Which is kind of in the same kind
Lex Fridman (1:12:08.940)
of space of reasoning that people say P not equals NP.
Scott Aaronson (1:12:12.700)
BENJAMIN Yeah, it's in the same spirit.
Lex Fridman (1:12:17.500)
TREVOR Okay, so Andrew Yang, a very intelligent
Lex Fridman (1:12:22.220)
and a presidential candidate with a lot of interesting ideas
Lex Fridman (1:12:27.420)
in all kinds of technological fields, tweeted that
Scott Aaronson (1:12:31.980)
because of quantum computing, no code is uncrackable.
Lex Fridman (1:12:36.060)
Is he wrong or right?
Scott Aaronson (1:12:37.980)
BENJAMIN He was premature, let's say.
Lex Fridman (1:12:40.860)
So, well, okay, wrong.
Scott Aaronson (1:12:45.020)
Look, I'm actually, you know, I'm a fan of Andrew Yang.
Lex Fridman (1:12:49.500)
I like his ideas.
Scott Aaronson (1:12:51.580)
I like his candidacy.
Lex Fridman (1:12:53.820)
I think that, you know, he may be ahead of his time
Scott Aaronson (1:12:58.140)
with, you know, the universal basic income and so forth.
Lex Fridman (1:13:01.660)
And he may also be ahead of his time in that tweet
Scott Aaronson (1:13:04.700)
that you referenced.
Lex Fridman (1:13:05.980)
So regarding using quantum computers
Lex Fridman (1:13:09.420)
to break cryptography, so the situation is this, okay?
Lex Fridman (1:13:13.260)
So the famous discovery of Peter Shor, you know, 26 years ago
Scott Aaronson (1:13:18.940)
that really started quantum computing, you know,
Lex Fridman (1:13:21.340)
as an autonomous field was that if you built a full
Scott Aaronson (1:13:26.140)
scalable quantum computer, then you could use it
Lex Fridman (1:13:29.660)
to efficiently find the prime factors of huge numbers
Lex Fridman (1:13:35.180)
and calculate discrete logarithms and solve
Lex Fridman (1:13:38.860)
a few other problems that are very, very special
Lex Fridman (1:13:41.820)
in character, right?
Lex Fridman (1:13:42.860)
They're not NP complete problems.
Lex Fridman (1:13:44.780)
We're pretty sure they're not, okay?
Lex Fridman (1:13:46.460)
But it so happens that most of the public key cryptography
Scott Aaronson (1:13:52.060)
that we currently use to protect the internet
Lex Fridman (1:13:54.380)
is based on the belief that these problems are hard.
Scott Aaronson (1:13:57.660)
Okay, what Shor showed is that once you get
Lex Fridman (1:13:59.900)
scalable quantum computers, then that's no longer true, okay?
Lex Fridman (1:14:03.260)
But now, you know, before people panic,
Lex Fridman (1:14:06.860)
there are two important points to understand here.
Scott Aaronson (1:14:09.740)
Okay, the first is that quantum supremacy,
Lex Fridman (1:14:13.180)
the milestone that Google just achieved,
Scott Aaronson (1:14:15.740)
is very, very far from the kind of scalable quantum computer
Lex Fridman (1:14:19.660)
that would be needed to actually threaten
Scott Aaronson (1:14:21.900)
public key cryptography.
Lex Fridman (1:14:23.500)
Okay, so, you know, we touched on this earlier, right?
Lex Fridman (1:14:25.740)
But Google's device has 53 physical qubits, right?
Lex Fridman (1:14:29.740)
To threaten cryptography, you're talking, you know,
Scott Aaronson (1:14:33.020)
with any of the known error correction methods,
Lex Fridman (1:14:35.020)
you're talking millions of physical qubits.
Scott Aaronson (1:14:37.420)
Because error correction would be required
Lex Fridman (1:14:39.660)
to threaten cryptography.
Lex Fridman (1:14:40.860)
Yes, yes, yes, it certainly would, right?
Lex Fridman (1:14:46.860)
And, you know, how much, you know,
Lex Fridman (1:14:51.020)
how great will the overhead be from the error correction?
Lex Fridman (1:14:53.820)
That we don't know yet.
Lex Fridman (1:14:55.180)
But with the known codes, you're talking millions
Lex Fridman (1:14:58.860)
of physical qubits and of a much higher quality
Lex Fridman (1:15:01.580)
than any that we have now, okay?
Lex Fridman (1:15:03.260)
So, you know, I don't think that that is, you know,
Scott Aaronson (1:15:07.900)
coming soon, although people who have secrets
Lex Fridman (1:15:12.060)
that, you know, need to stay secret for 20 years,
Scott Aaronson (1:15:15.420)
you know, are already worried about this,
Lex Fridman (1:15:17.740)
you know, for the good reason that, you know,
Scott Aaronson (1:15:19.900)
we presume that intelligence agencies
Lex Fridman (1:15:22.620)
are already scooping up data, you know,
Scott Aaronson (1:15:25.260)
in the hope that eventually they'll be able to decode it
Lex Fridman (1:15:27.980)
once quantum computers become available, okay?
Lex Fridman (1:15:30.780)
So this brings me to the second point I wanted to make,
Lex Fridman (1:15:35.580)
which is that there are other public key cryptosystems
Scott Aaronson (1:15:39.420)
that are known that we don't know how to break
Lex Fridman (1:15:43.260)
even with quantum computers, okay?
Lex Fridman (1:15:45.420)
And so there's a whole field devoted to this now,
Lex Fridman (1:15:48.460)
which is called post quantum cryptography, okay?
Lex Fridman (1:15:51.660)
And so there is already, so we have some good candidates now.
Lex Fridman (1:15:56.300)
The best known being what are called
Scott Aaronson (1:15:58.460)
lattice based cryptosystems.
Lex Fridman (1:16:00.620)
And there is already some push to try to migrate
Scott Aaronson (1:16:03.500)
to these cryptosystems.
Lex Fridman (1:16:04.780)
So NIST in the US is holding a competition
Scott Aaronson (1:16:09.900)
to create standards for post quantum cryptography,
Lex Fridman (1:16:13.980)
which will be the first step in trying to get
Scott Aaronson (1:16:16.460)
every web browser and every router to upgrade,
Lex Fridman (1:16:20.380)
you know, and use, you know, something like SSL
Scott Aaronson (1:16:23.660)
that would be based on, you know,
Lex Fridman (1:16:26.220)
what we think is quantum secure cryptography.
Scott Aaronson (1:16:29.340)
But, you know, this will be a long process.
Lex Fridman (1:16:33.340)
But, you know, it is something that people
Scott Aaronson (1:16:35.180)
are already starting to do.
Lex Fridman (1:16:36.780)
And so, you know, I'm sure this algorithm
Scott Aaronson (1:16:40.300)
is sort of a dramatic discovery.
Lex Fridman (1:16:42.780)
You know, it could be a big deal
Scott Aaronson (1:16:44.220)
for whatever intelligence agency
Lex Fridman (1:16:46.220)
first gets a scalable quantum computer,
Scott Aaronson (1:16:48.780)
if no, at least certainly if no one else
Lex Fridman (1:16:51.260)
knows that they have it, right?
Lex Fridman (1:16:53.580)
But eventually we think that we could migrate
Lex Fridman (1:16:57.740)
the internet to the post quantum cryptography
Lex Fridman (1:17:00.380)
and then we'd be more or less back where we started.
Lex Fridman (1:17:03.340)
Okay, so this is sort of not the application
Scott Aaronson (1:17:06.060)
of quantum computing.
Lex Fridman (1:17:07.180)
I think that's really gonna change the world
Lex Fridman (1:17:09.340)
in a sustainable way, right?
Lex Fridman (1:17:10.860)
The big, by the way, the biggest practical application
Scott Aaronson (1:17:14.140)
of quantum computing that we know about by far,
Lex Fridman (1:17:17.340)
I think is simply the simulation
Scott Aaronson (1:17:19.420)
of quantum mechanics itself.
Lex Fridman (1:17:21.340)
In order to, you know, learn about chemical reactions,
Scott Aaronson (1:17:24.780)
you know, design maybe new chemical processes,
Lex Fridman (1:17:28.380)
new materials, new drugs, new solar cells,
Scott Aaronson (1:17:32.700)
new superconductors, all kinds of things like that.
Lex Fridman (1:17:35.660)
What's the size of a quantum computer
Scott Aaronson (1:17:38.700)
that would be able to simulate the,
Lex Fridman (1:17:41.820)
you know, quantum mechanical systems themselves
Scott Aaronson (1:17:44.700)
that would be impactful for the real world
Lex Fridman (1:17:46.780)
for the kind of chemical reactions
Lex Fridman (1:17:49.500)
and that kind of work?
Lex Fridman (1:17:50.540)
What scale are we talking about?
Scott Aaronson (1:17:51.900)
Now you're asking a very, very current question,
Lex Fridman (1:17:55.820)
a very big question.
Scott Aaronson (1:17:57.740)
People are going to be racing over the next decade
Lex Fridman (1:18:00.940)
to try to do useful quantum simulations
Scott Aaronson (1:18:04.780)
even with, you know, 100 or 200 qubit quantum computers
Lex Fridman (1:18:09.100)
of the sort that we expect to be able to build
Scott Aaronson (1:18:11.500)
over the next decade.
Lex Fridman (1:18:12.860)
Okay, so that might be, you know,
Scott Aaronson (1:18:15.580)
the first application of quantum computing
Lex Fridman (1:18:18.460)
that we're able to realize, you know,
Scott Aaronson (1:18:20.380)
or maybe it will prove to be too difficult
Lex Fridman (1:18:23.100)
and maybe even that will require fault tolerance
Scott Aaronson (1:18:26.060)
or, you know, will require error correction.
Lex Fridman (1:18:28.300)
So there's an aggressive race to come up
Scott Aaronson (1:18:30.460)
with the one case study kind of like Peter Schor
Lex Fridman (1:18:35.500)
with the idea that would just capture
Scott Aaronson (1:18:37.260)
the world's imagination of like,
Lex Fridman (1:18:38.860)
look, we can actually do something very useful here.
Scott Aaronson (1:18:41.820)
Right, but I think, you know, within the next decade,
Lex Fridman (1:18:44.140)
the best shot we have is certainly not,
Scott Aaronson (1:18:46.700)
you know, using Schor's algorithm to break cryptography,
Lex Fridman (1:18:50.860)
you know, just because it requires,
Scott Aaronson (1:18:53.020)
you know, too much in the way of error correction.
Lex Fridman (1:18:55.740)
The best shot we have is to do some quantum simulation
Scott Aaronson (1:18:59.820)
that tells the material scientists
Lex Fridman (1:19:02.300)
or chemists or nuclear physicists,
Scott Aaronson (1:19:05.500)
you know, something that is useful to them
Lex Fridman (1:19:07.340)
and that they didn't already know,
Scott Aaronson (1:19:08.940)
you know, and you might only need one or two successes
Lex Fridman (1:19:11.580)
in order to change some, you know,
Lex Fridman (1:19:12.940)
billion dollar industries, right?
Lex Fridman (1:19:14.620)
Like, you know, the way that people make fertilizer right now
Scott Aaronson (1:19:18.300)
is still based on the Haber Bosch process
Lex Fridman (1:19:20.700)
from a century ago.
Lex Fridman (1:19:22.140)
And it is some many body quantum mechanics problem
Lex Fridman (1:19:25.420)
that no one really understands, right?
Lex Fridman (1:19:27.260)
If you could design a better way to make fertilizer, right?
Lex Fridman (1:19:30.700)
That's, you know, billions of dollars right there.
Lex Fridman (1:19:33.180)
So those are sort of the applications
Lex Fridman (1:19:35.980)
that people are going to be aggressively racing toward
Scott Aaronson (1:19:38.620)
over the next decade.
Lex Fridman (1:19:40.060)
Now, I don't know if they're gonna realize it or not,
Scott Aaronson (1:19:42.460)
but, you know, they certainly at least have a shot.
Lex Fridman (1:19:46.140)
So it's gonna be a very, very interesting next decade.
Lex Fridman (1:19:48.780)
But just to clarify, what's your intuition?
Lex Fridman (1:19:51.980)
If a breakthrough like that comes with,
Scott Aaronson (1:19:53.980)
is it possible for that breakthrough to be on 50
Lex Fridman (1:19:56.620)
to 100 qubits or is scale a fundamental thing
Lex Fridman (1:20:01.020)
like 500, 1000 plus qubits?
Lex Fridman (1:20:04.220)
Yeah, so I can tell you what the current studies are saying.
Scott Aaronson (1:20:09.100)
You know, I think probably better to rely on that
Lex Fridman (1:20:12.060)
than on my intuition.
Scott Aaronson (1:20:13.900)
But, you know, there was a group at Microsoft
Lex Fridman (1:20:17.500)
had a study a few years ago that said
Scott Aaronson (1:20:20.780)
even with only about 100 qubits,
Lex Fridman (1:20:23.660)
you know, you could already learn something new
Scott Aaronson (1:20:26.060)
about the chemical reaction that makes fertilizer, for example.
Lex Fridman (1:20:30.780)
The trouble is they're talking about 100 qubits
Lex Fridman (1:20:34.460)
and about a million layers of quantum gates.
Lex Fridman (1:20:38.780)
Okay, so basically they're talking about
Scott Aaronson (1:20:40.700)
100 nearly perfect qubits.
Lex Fridman (1:20:42.940)
So the logical qubits, as you mentioned before.
Scott Aaronson (1:20:44.700)
Yeah, exactly, 100 logical qubits.
Lex Fridman (1:20:47.500)
And now, you know, the hard part for the next decade
Scott Aaronson (1:20:50.700)
is gonna be, well, what can we do
Lex Fridman (1:20:52.220)
with 100 to 200 noisy qubits?
Scott Aaronson (1:20:56.220)
Yeah, is there error correction breakthroughs
Lex Fridman (1:20:59.020)
that might come without the need to do
Lex Fridman (1:21:01.900)
thousands or millions of physical qubits?
Lex Fridman (1:21:04.940)
Yeah, so people are gonna be pushing simultaneously
Scott Aaronson (1:21:07.820)
on a bunch of different directions.
Lex Fridman (1:21:09.820)
One direction, of course,
Lex Fridman (1:21:11.020)
is just making the qubits better, right?
Lex Fridman (1:21:14.140)
And, you know, there is tremendous progress there.
Scott Aaronson (1:21:16.940)
I mean, you know, the fidelity is like
Lex Fridman (1:21:19.260)
the accuracy of the qubits has improved
Scott Aaronson (1:21:22.540)
by several orders of magnitude, you know,
Lex Fridman (1:21:24.540)
in the last decade or two.
Scott Aaronson (1:21:28.220)
Okay, the second thing is designing better error,
Lex Fridman (1:21:31.660)
you know, let's say lower overhead error correcting codes
Lex Fridman (1:21:36.060)
and even short of doing the full recursive error correction.
Lex Fridman (1:21:40.140)
You know, there are these error mitigation strategies
Scott Aaronson (1:21:43.340)
that you can use, you know, that may, you know,
Lex Fridman (1:21:47.020)
allow you to eke out a useful speed up in the near term.
Lex Fridman (1:21:52.300)
And then the third thing is just taking the quantum algorithms
Lex Fridman (1:21:56.140)
for simulating quantum chemistry or materials
Lex Fridman (1:21:59.900)
and making them more efficient.
Lex Fridman (1:22:01.740)
You know, and those algorithms
Scott Aaronson (1:22:03.180)
are already dramatically more efficient
Lex Fridman (1:22:05.580)
than they were, let's say, five years ago.
Lex Fridman (1:22:07.900)
And so when, you know, I quoted these estimates
Lex Fridman (1:22:10.460)
like, you know, circuit depth of one million.
Lex Fridman (1:22:13.260)
And so, you know, I hope that because people will care enough
Lex Fridman (1:22:16.700)
that these numbers are gonna come down.
Lex Fridman (1:22:18.860)
So you're one of the world class researchers in this space.
Lex Fridman (1:22:24.380)
There's a few groups like you mentioned,
Scott Aaronson (1:22:26.060)
Google and IBM working at this.
Lex Fridman (1:22:27.820)
There's other research labs, but you put also,
Scott Aaronson (1:22:32.140)
you have an amazing blog.
Lex Fridman (1:22:35.820)
You just, you put a lot, you paid me to say it.
Scott Aaronson (1:22:41.180)
You put a lot of effort sort of to communicating
Lex Fridman (1:22:44.060)
the science of this and communicating,
Scott Aaronson (1:22:47.900)
exposing some of the BS and sort of the natural,
Lex Fridman (1:22:52.060)
just like in the AI space, the natural charlatanism,
Scott Aaronson (1:22:56.700)
if that's a word in this, in the quantum mechanics in general,
Lex Fridman (1:23:00.940)
but quantum computers and so on.
Lex Fridman (1:23:02.860)
Can you give some notes about people or ideas
Lex Fridman (1:23:07.900)
that people like me or listeners in general
Scott Aaronson (1:23:10.220)
from outside the field should be cautious of
Lex Fridman (1:23:12.540)
when they're taking in news headings
Lex Fridman (1:23:15.820)
that Google achieved quantum supremacy?
Lex Fridman (1:23:19.340)
So what should we look out for?
Lex Fridman (1:23:21.420)
Where's the charlatans in the space?
Lex Fridman (1:23:23.020)
Where's the BS?
Scott Aaronson (1:23:23.980)
Yeah, so good question.
Lex Fridman (1:23:26.620)
Unfortunately, quantum computing is a little bit like
Scott Aaronson (1:23:29.900)
cryptocurrency or deep learning.
Lex Fridman (1:23:32.700)
Like there is a core of something
Scott Aaronson (1:23:34.220)
that is genuinely revolutionary and exciting.
Lex Fridman (1:23:37.260)
And because of that core, it attracts this sort of
Scott Aaronson (1:23:40.460)
vast penumbra of people making just utterly ridiculous claims.
Lex Fridman (1:23:47.260)
And so with quantum computing, I mean,
Scott Aaronson (1:23:50.860)
I would say that the main way that people go astray
Lex Fridman (1:23:54.860)
is by not focusing on sort of the question of,
Lex Fridman (1:23:59.100)
are you getting a speed up over a classical computer or not?
Lex Fridman (1:24:03.500)
And so people have like dismissed quantum supremacy
Lex Fridman (1:24:08.860)
because it's not useful, right?
Lex Fridman (1:24:10.620)
Or it's not itself, let's say, obviously useful for anything.
Scott Aaronson (1:24:14.860)
Okay, but ironically, these are some of the same people
Lex Fridman (1:24:18.300)
who will go and say, well, we care about useful applications.
Scott Aaronson (1:24:21.900)
We care about solving traffic routing
Lex Fridman (1:24:25.020)
and financial optimization and all these things.
Lex Fridman (1:24:28.620)
And that sounds really good, but their entire spiel
Lex Fridman (1:24:33.500)
is sort of counting on nobody asking the question,
Scott Aaronson (1:24:37.260)
yes, but how well could a classical computer
Lex Fridman (1:24:39.900)
do the same thing, right?
Scott Aaronson (1:24:42.700)
I really mean the entire thing is they say,
Lex Fridman (1:24:47.500)
well, a quantum computer can do this,
Scott Aaronson (1:24:49.180)
a quantum computer can do that.
Lex Fridman (1:24:50.700)
A quantum computer can do that, right?
Lex Fridman (1:24:52.380)
And they just avoid the question,
Lex Fridman (1:24:55.180)
are you getting a speed up over a classical computer or not?
Lex Fridman (1:24:58.780)
And if so, how do you know?
Lex Fridman (1:25:01.340)
Have you really thought carefully about classical algorithms
Lex Fridman (1:25:05.420)
to solve the same problem, right?
Lex Fridman (1:25:07.820)
And a lot of the application areas
Scott Aaronson (1:25:10.220)
that the companies and investors are most excited about
Lex Fridman (1:25:16.700)
that the popular press is most excited about
Scott Aaronson (1:25:19.900)
where quantum computers have been things
Lex Fridman (1:25:21.740)
like machine learning, AI, optimization, okay?
Lex Fridman (1:25:27.380)
And the problem with that is that since the very beginning,
Lex Fridman (1:25:31.820)
even if you have a perfect fault tolerant,
Scott Aaronson (1:25:35.980)
scalable quantum computer,
Lex Fridman (1:25:40.300)
we have known of only modest speed ups
Lex Fridman (1:25:43.100)
that you can get for these problems, okay?
Lex Fridman (1:25:46.420)
So there is a famous quantum algorithm
Lex Fridman (1:25:48.780)
called Grover's algorithm, okay?
Lex Fridman (1:25:50.860)
And what it can do is it can solve many,
Scott Aaronson (1:25:52.980)
many of the problems that arise in AI,
Lex Fridman (1:25:56.060)
machine learning, optimization,
Lex Fridman (1:25:58.180)
including NP complete problems, okay?
Lex Fridman (1:26:00.780)
But it can solve them in about the square root
Scott Aaronson (1:26:03.540)
of the number of steps that a classical computer would need
Lex Fridman (1:26:06.700)
for the same problems, okay?
Scott Aaronson (1:26:08.260)
Now a square root speed up is important, it's impressive.
Lex Fridman (1:26:12.340)
It is not an exponential speed up, okay?
Lex Fridman (1:26:15.140)
So it is not the kind of game changer
Lex Fridman (1:26:17.780)
that let's say Shor's algorithm for factoring is,
Scott Aaronson (1:26:20.820)
or for that matter that simulation of quantum mechanics is,
Lex Fridman (1:26:23.700)
okay, it is a more modest speed up.
Lex Fridman (1:26:26.260)
And let's say roughly, in theory,
Lex Fridman (1:26:28.780)
it could roughly double the size
Lex Fridman (1:26:30.380)
of the optimization problems that you could handle, right?
Lex Fridman (1:26:33.380)
And so because people found that I guess too boring
Scott Aaronson (1:26:39.300)
or too unimpressive, they've gone on to like invent
Lex Fridman (1:26:43.980)
all of these heuristic algorithms
Scott Aaronson (1:26:46.340)
where because no one really understands them,
Lex Fridman (1:26:49.380)
you can just project your hopes onto them, right?
Scott Aaronson (1:26:52.500)
That, well, maybe it gets an exponential speed up.
Lex Fridman (1:26:55.780)
You can't prove that it doesn't,
Lex Fridman (1:26:57.740)
and the burden is on you to prove
Lex Fridman (1:26:59.300)
that it doesn't get a speed up, right?
Lex Fridman (1:27:00.820)
And so they've done an immense amount of that kind of thing.
Lex Fridman (1:27:04.860)
And a really worrying amount of the case
Scott Aaronson (1:27:08.020)
for building a quantum computer has come to rest
Lex Fridman (1:27:10.740)
on this stuff that those of us in this field
Scott Aaronson (1:27:13.620)
know perfectly well is on extremely shaky foundations.
Lex Fridman (1:27:17.620)
So the fundamental question is,
Scott Aaronson (1:27:20.620)
show that there's a speed up over the classical.
Lex Fridman (1:27:23.500)
Absolutely.
Lex Fridman (1:27:24.340)
And in this space that you're referring to,
Lex Fridman (1:27:26.500)
which is actually really interesting,
Scott Aaronson (1:27:27.660)
it's the area that a lot of people excited about
Lex Fridman (1:27:30.100)
is machine learning.
Lex Fridman (1:27:31.340)
So your sense is, do you think it will,
Lex Fridman (1:27:34.700)
I know that there's a lot of smoke currently,
Lex Fridman (1:27:37.740)
but do you think there actually eventually
Lex Fridman (1:27:40.300)
might be breakthroughs where you do get exponential speed ups
Lex Fridman (1:27:45.020)
in the machine learning space?
Lex Fridman (1:27:46.580)
Absolutely, there might be.
Scott Aaronson (1:27:48.020)
I mean, I think we know of modest speed ups
Lex Fridman (1:27:50.700)
that you can get for these problems.
Scott Aaronson (1:27:52.700)
I think, you know, whether you can get bigger speed ups
Lex Fridman (1:27:55.540)
is one of the biggest questions for quantum computing theory,
Scott Aaronson (1:28:00.380)
you know, for people like me to be thinking about.
Lex Fridman (1:28:03.620)
Now, you know, we had actually recently
Scott Aaronson (1:28:06.740)
a really, you know, a super exciting candidate
Lex Fridman (1:28:11.020)
for an exponential quantum speed up
Scott Aaronson (1:28:13.620)
for a machine learning problem
Lex Fridman (1:28:15.220)
that people really care about.
Scott Aaronson (1:28:16.820)
This is basically the Netflix problem,
Lex Fridman (1:28:19.140)
the problem of recommending products to users
Scott Aaronson (1:28:22.420)
given some sparse data about their preferences.
Lex Fridman (1:28:25.580)
Karinidis and Prakash in 2016 had an algorithm
Scott Aaronson (1:28:29.540)
for sampling recommendations that was exponentially faster
Lex Fridman (1:28:33.700)
than any known classical algorithm, right?
Lex Fridman (1:28:35.980)
And so, you know, a lot of people were excited.
Lex Fridman (1:28:37.980)
I was excited about it.
Scott Aaronson (1:28:40.100)
I had an 18 year old undergrad by the name of Yilin Tang,
Lex Fridman (1:28:44.500)
and she was obviously brilliant.
Scott Aaronson (1:28:47.140)
She was looking for a project.
Lex Fridman (1:28:48.780)
I gave her as a project,
Lex Fridman (1:28:50.340)
can you prove that this speed up is real?
Lex Fridman (1:28:52.860)
Can you prove that, you know, any classical algorithm
Lex Fridman (1:28:55.580)
would need to access exponentially more data, right?
Lex Fridman (1:28:58.820)
And, you know, this was a case where if that was true,
Lex Fridman (1:29:01.660)
this was not like a P versus NP type of question, right?
Lex Fridman (1:29:04.660)
This might well have been provable,
Lex Fridman (1:29:07.060)
but she worked on it for a year.
Lex Fridman (1:29:09.100)
She couldn't do it.
Scott Aaronson (1:29:10.540)
Eventually she figured out why she couldn't do it.
Lex Fridman (1:29:13.340)
And the reason was that that was false.
Scott Aaronson (1:29:15.420)
There is a classical algorithm
Lex Fridman (1:29:18.140)
with a similar performance to the quantum algorithm.
Lex Fridman (1:29:20.820)
So Yilin succeeded in dequantizing
Lex Fridman (1:29:23.860)
that machine learning algorithm.
Lex Fridman (1:29:25.300)
And then in the last couple of years,
Lex Fridman (1:29:27.940)
building on Yilin's breakthrough,
Scott Aaronson (1:29:30.180)
a bunch of the other quantum machine learning algorithms
Lex Fridman (1:29:32.980)
that were proposed have now also been dequantized.
Scott Aaronson (1:29:36.180)
Yeah.
Lex Fridman (1:29:37.020)
Okay, and so I would say, yeah.
Scott Aaronson (1:29:37.860)
That's a kind of important backwards step.
Lex Fridman (1:29:40.100)
Yes.
Scott Aaronson (1:29:41.260)
Like a forward step for science,
Lex Fridman (1:29:43.580)
but a step for quantum machine learning
Scott Aaronson (1:29:46.940)
that precedes the big next forward step.
Lex Fridman (1:29:50.780)
Right, right, right.
Scott Aaronson (1:29:51.740)
If it's possible.
Lex Fridman (1:29:52.580)
Right, now some people will say,
Scott Aaronson (1:29:54.300)
well, you know, there's a silver lining in this cloud.
Lex Fridman (1:29:57.020)
They say, well, thinking about quantum computing
Scott Aaronson (1:29:59.260)
has led to the discovery
Lex Fridman (1:30:01.020)
of potentially useful new classical algorithms.
Scott Aaronson (1:30:03.860)
That's true.
Lex Fridman (1:30:04.700)
And so, you know, so you get these spinoff applications,
Lex Fridman (1:30:07.460)
but if you want a quantum speed up,
Lex Fridman (1:30:09.300)
you really have to think carefully about that.
Scott Aaronson (1:30:11.860)
You know, Yilin's work was a perfect illustration of why.
Lex Fridman (1:30:15.220)
Right, and I think that, you know, the challenge,
Lex Fridman (1:30:18.820)
you know, the field is now open, right?
Lex Fridman (1:30:22.340)
Find a better example,
Scott Aaronson (1:30:23.820)
find, you know, where quantum computers
Lex Fridman (1:30:26.580)
are going to deliver big gains for machine learning.
Scott Aaronson (1:30:29.420)
You know, I am, you know,
Lex Fridman (1:30:31.820)
not only do I ardently support,
Scott Aaronson (1:30:33.740)
you know, people thinking about that,
Lex Fridman (1:30:35.980)
I'm trying to think about it myself
Lex Fridman (1:30:37.660)
and have my students and postdocs think about it,
Lex Fridman (1:30:41.420)
but we should not pretend
Scott Aaronson (1:30:42.980)
that those speed ups are already established.
Lex Fridman (1:30:45.420)
And the problem comes when so many of the companies
Scott Aaronson (1:30:49.300)
and, you know, and journalists in this space
Lex Fridman (1:30:52.380)
are pretending that.
Scott Aaronson (1:30:54.700)
Like all good things, like life itself,
Lex Fridman (1:30:57.740)
this conversation must soon come to an end.
Scott Aaronson (1:31:00.540)
Let me ask the most absurdly philosophical last question.
Lex Fridman (1:31:04.620)
What is the meaning of life?
Lex Fridman (1:31:07.500)
What gives your life fulfillment, purpose,
Lex Fridman (1:31:11.540)
happiness, and yeah, meaning?
Scott Aaronson (1:31:15.500)
I would say, you know, number one,
Lex Fridman (1:31:18.860)
trying to discover new things about the world
Lex Fridman (1:31:22.420)
and share them and, you know, communicate
Lex Fridman (1:31:25.380)
and learn what other people have discovered.
Scott Aaronson (1:31:29.380)
You know, number two, you know, my friends,
Lex Fridman (1:31:33.540)
my family, my kids, my students,
Scott Aaronson (1:31:40.620)
you know, just the people around me.
Lex Fridman (1:31:43.780)
Number three, you know, trying, you know,
Scott Aaronson (1:31:46.780)
when I can to, you know, make the world better
Lex Fridman (1:31:50.740)
in some small ways.
Scott Aaronson (1:31:52.100)
And, you know, it's depressing that I can't do more
Lex Fridman (1:31:54.500)
and that, you know, the world is, you know,
Scott Aaronson (1:31:58.660)
facing crises over, you know, the climate
Lex Fridman (1:32:01.100)
and over, you know, sort of resurgent authoritarianism
Lex Fridman (1:32:04.460)
and all these other things, but, you know,
Lex Fridman (1:32:06.740)
trying to stand against the things
Scott Aaronson (1:32:10.580)
that I find horrible when I can.
Lex Fridman (1:32:13.180)
Let me ask you one more absurd question.
Lex Fridman (1:32:16.060)
What makes you smile?
Lex Fridman (1:32:18.740)
Well, yeah, I guess your question just did.
Scott Aaronson (1:32:20.660)
I don't know.
Lex Fridman (1:32:21.500)
I thought I tried that absurd one on you.
Scott Aaronson (1:32:25.740)
Well, it was a huge honor to talk to you.
Lex Fridman (1:32:28.580)
We'll probably talk to you for many more hours, Scott.
Scott Aaronson (1:32:30.740)
Thank you so much.
Lex Fridman (1:32:31.660)
Well, thank you.
Scott Aaronson (1:32:32.500)
Thank you.
Lex Fridman (1:32:33.340)
It was great.
Scott Aaronson (1:32:34.500)
Thank you for listening to this conversation
Lex Fridman (1:32:36.220)
with Scott Aaronson.
Lex Fridman (1:32:37.260)
And thank you to our presenting sponsor, Cash App.
Lex Fridman (1:32:40.340)
Download it, use code LexPodcast,
Scott Aaronson (1:32:42.900)
you'll get $10 and $10 will go to FIRST,
Lex Fridman (1:32:45.620)
an organization that inspires and educates young minds
Scott Aaronson (1:32:48.620)
to become science and technology innovators of tomorrow.
Lex Fridman (1:32:51.900)
If you enjoy this podcast, subscribe on YouTube,
Scott Aaronson (1:32:54.380)
give it five stars on Apple Podcast,
Lex Fridman (1:32:56.260)
support it on Patreon,
Scott Aaronson (1:32:57.580)
or simply connect with me on Twitter at Lex Friedman.
Lex Fridman (1:33:01.900)
Now, let me leave you with some words
Scott Aaronson (1:33:03.860)
from a funny and insightful blog post
Lex Fridman (1:33:06.220)
Scott wrote over 10 years ago
Scott Aaronson (1:33:08.500)
on the ever present Malthusianisms in our daily lives.
Lex Fridman (1:33:12.940)
Quote, again and again,
Scott Aaronson (1:33:14.860)
I've undergone the humbling experience
Lex Fridman (1:33:17.060)
of first lamenting how badly something sucks,
Scott Aaronson (1:33:19.780)
then only much later having the crucial insight
Lex Fridman (1:33:23.500)
that it's not sucking
Scott Aaronson (1:33:25.180)
wouldn't have been a Nash equilibrium.
Lex Fridman (1:33:29.260)
Thank you for listening.
Scott Aaronson (1:33:30.580)
I hope to see you next time.
Lex Fridman (20:01.620)
my internal sense of having free will
Scott Aaronson (20:04.380)
in a much more visceral way.
Lex Fridman (20:06.340)
You know, but now you notice that we're asking
Scott Aaronson (20:08.980)
a much more empirical question.
Lex Fridman (20:11.580)
We're asking, is such a machine possible or isn't it?
Scott Aaronson (20:14.700)
We're asking, if it's not possible,
Lex Fridman (20:16.260)
then what in the laws of physics
Scott Aaronson (20:18.380)
or what about the behavior of the brain,
Lex Fridman (20:21.180)
you know, prevents it from existing?
Lex Fridman (20:22.980)
So if you could philosophize a little bit
Lex Fridman (20:25.260)
within this empirical question,
Scott Aaronson (20:27.740)
where do you think would enter the,
Lex Fridman (20:31.420)
by which mechanism would enter the possibility
Lex Fridman (20:33.820)
that we can't predict the outcome?
Lex Fridman (20:35.580)
So there would be something
Scott Aaronson (20:37.220)
that would be akin to a free will.
Lex Fridman (20:38.860)
Yeah, well, you could say the sort of obvious possibility,
Scott Aaronson (20:42.460)
which was, you know, recognized by Eddington
Lex Fridman (20:45.660)
and many others about as soon as quantum mechanics
Scott Aaronson (20:48.020)
was discovered in the 1920s, was that if,
Lex Fridman (20:53.300)
you know, let's say a sodium ion channel,
Lex Fridman (20:56.180)
you know, in the brain, right?
Lex Fridman (21:00.500)
You know, its behavior is chaotic, right?
Scott Aaronson (21:03.980)
It's sort of, it's governed by these
Lex Fridman (21:06.340)
Hodgley–Huckskin equations in neuroscience, right?
Scott Aaronson (21:10.940)
Which are differential equations
Lex Fridman (21:12.500)
that have a stochastic component, right?
Scott Aaronson (21:14.780)
Now, where does, you know, and this ultimately governs,
Lex Fridman (21:17.100)
let's say whether a neuron will fire or not fire, right?
Lex Fridman (21:19.460)
So that's the basic chemical process
Lex Fridman (21:21.700)
or electrical process by which signals
Scott Aaronson (21:23.860)
are sent in the brain.
Lex Fridman (21:24.780)
Exactly, exactly.
Scott Aaronson (21:25.980)
And, you know, and so you could ask,
Lex Fridman (21:28.780)
well, where does the randomness in the process,
Scott Aaronson (21:31.380)
you know, that neuroscientists,
Lex Fridman (21:34.100)
or what neuroscientists would treat as randomness,
Lex Fridman (21:38.020)
where does it come from?
Lex Fridman (21:39.380)
You know, ultimately it's thermal noise, right?
Lex Fridman (21:41.700)
Where does thermal noise come from?
Lex Fridman (21:43.580)
But ultimately, you know,
Scott Aaronson (21:44.860)
there were some quantum mechanical events
Lex Fridman (21:46.780)
at the molecular level
Scott Aaronson (21:48.060)
that are getting sort of chaotically amplified
Lex Fridman (21:50.940)
by, you know, a sort of butterfly effect.
Lex Fridman (21:53.660)
And so, you know, even if you knew
Lex Fridman (21:57.220)
the complete quantum state of someone's brain,
Scott Aaronson (22:00.300)
you know, at best you could predict the probabilities
Lex Fridman (22:02.780)
that they would do one thing or do another thing, right?
Scott Aaronson (22:05.420)
I think that part is actually relatively uncontroversial,
Lex Fridman (22:08.500)
right?
Scott Aaronson (22:09.340)
The controversial question is whether any of it matters
Lex Fridman (22:13.340)
for the sort of philosophical questions that we care about.
Scott Aaronson (22:16.100)
Because you could say, if all it's doing
Lex Fridman (22:18.340)
is just injecting some randomness
Scott Aaronson (22:20.340)
into an otherwise completely mechanistic process,
Lex Fridman (22:23.700)
well, then who cares, right?
Lex Fridman (22:25.140)
And more concretely, if you could build a machine
Lex Fridman (22:28.460)
that, you know, could just calculate
Scott Aaronson (22:30.980)
even just the probabilities
Lex Fridman (22:33.540)
of all of the possible things that you would do, right?
Scott Aaronson (22:35.980)
And, you know, of all the things that said
Lex Fridman (22:39.940)
you had a 10% chance of doing,
Scott Aaronson (22:41.860)
you did exactly a 10th of them, you know,
Lex Fridman (22:43.980)
and so on and so on.
Lex Fridman (22:45.580)
And that somehow also takes away the feeling of free will.
Lex Fridman (22:48.180)
Exactly.
Scott Aaronson (22:49.020)
I mean, to me, it seems essentially just as bad
Lex Fridman (22:51.900)
as if the machine deterministically predicted you.
Scott Aaronson (22:54.860)
It seems, you know, hardly different from that.
Lex Fridman (22:57.340)
So then, but a more subtle question
Scott Aaronson (23:02.420)
is could you even learn enough
Lex Fridman (23:04.060)
about someone's brain to do that, okay?
Scott Aaronson (23:06.340)
Because, you know, another central fact
Lex Fridman (23:09.540)
about quantum mechanics is that making a measurement
Scott Aaronson (23:14.140)
on a quantum state is an inherently destructive operation.
Lex Fridman (23:18.060)
Okay, so, you know, if I want to measure the, you know,
Lex Fridman (23:21.660)
position of a particle, right?
Lex Fridman (23:23.500)
It was, well, before I measured,
Scott Aaronson (23:25.300)
it had a superposition over many different positions.
Lex Fridman (23:28.420)
As soon as I measure, I localize it, right?
Lex Fridman (23:30.980)
So now I know the position,
Lex Fridman (23:32.340)
but I've also fundamentally changed the state.
Lex Fridman (23:35.260)
And so you could say, well, maybe in trying to build
Lex Fridman (23:39.940)
a model of someone's brain that was accurate enough
Scott Aaronson (23:42.780)
to actually, you know, make, let's say,
Lex Fridman (23:44.700)
even well calibrated probabilistic predictions
Scott Aaronson (23:48.340)
of their future behavior,
Lex Fridman (23:49.980)
maybe you would have to make measurements
Scott Aaronson (23:51.740)
that were just so accurate
Lex Fridman (23:53.140)
that you would just fundamentally alter their brain, okay?
Scott Aaronson (23:56.180)
Or maybe not, maybe you only, you know,
Lex Fridman (23:59.580)
it would suffice to just make some nanorobots
Scott Aaronson (24:02.380)
that just measured some sort of much larger scale,
Lex Fridman (24:05.700)
you know, macroscopic behavior, like, you know,
Lex Fridman (24:09.300)
what is this neuron doing?
Lex Fridman (24:10.780)
What is that neuron doing?
Scott Aaronson (24:12.260)
Maybe that would be enough.
Lex Fridman (24:13.860)
See, but now, you know, what I claim is that
Scott Aaronson (24:16.940)
we're now asking a question, you know,
Lex Fridman (24:19.220)
in which, you know, it is possible to envision
Lex Fridman (24:22.660)
what progress on it would look like.
Lex Fridman (24:24.620)
Yeah, but just as you said,
Scott Aaronson (24:25.940)
that question may be slightly detached
Lex Fridman (24:28.900)
from the philosophical question in the sense
Scott Aaronson (24:31.740)
if consciousness somehow has a role
Lex Fridman (24:33.860)
to the experience of free will.
Scott Aaronson (24:36.060)
Because ultimately, when we're talking about free will,
Lex Fridman (24:38.340)
we're also talking about not just the predictability
Scott Aaronson (24:42.260)
of our actions, but somehow the experience
Lex Fridman (24:44.900)
of that predictability.
Scott Aaronson (24:46.340)
Yeah, well, I mean, a lot of philosophical questions
Lex Fridman (24:49.420)
ultimately, like, feedback to the hard problem
Scott Aaronson (24:52.260)
of consciousness, you know,
Lex Fridman (24:53.540)
and as much as you can try to sort of talk around it
Lex Fridman (24:56.660)
or not, right?
Lex Fridman (24:57.500)
And, you know, and there is a reason
Lex Fridman (24:59.980)
why people try to talk around it,
Lex Fridman (25:01.820)
which is that, you know,
Scott Aaronson (25:03.580)
Democritus talked about the hard problem of consciousness,
Lex Fridman (25:07.780)
you know, in 400 BC in terms that would be
Lex Fridman (25:11.180)
totally recognizable to us today, right?
Lex Fridman (25:13.900)
And it's really not clear if there's been progress since
Scott Aaronson (25:16.980)
or what progress could possibly consist of.
Lex Fridman (25:19.540)
Is there a Q prime type of subquestion
Lex Fridman (25:22.420)
that could help us get at consciousness?
Lex Fridman (25:24.380)
It's something about consciousness.
Scott Aaronson (25:25.660)
Well, I mean, well, I mean, there is the whole question
Lex Fridman (25:27.740)
of, you know, of AI, right?
Scott Aaronson (25:29.620)
Of, you know, can you build a human level
Lex Fridman (25:33.700)
or superhuman level AI?
Scott Aaronson (25:35.980)
And, you know, can it work in a completely different
Lex Fridman (25:39.140)
substrate from the brain?
Scott Aaronson (25:40.380)
I mean, you know, and of course,
Lex Fridman (25:41.580)
that was Alan Turing's point.
Scott Aaronson (25:43.460)
And, you know, and even if that was done,
Lex Fridman (25:45.500)
it's, you know, maybe people would still argue
Lex Fridman (25:47.660)
about the hard problem of consciousness, right?
Lex Fridman (25:49.940)
And yet, you know, my claim is a little different.
Scott Aaronson (25:53.100)
My claim is that in a world where, you know,
Lex Fridman (25:55.860)
there were, you know, human level AIs
Scott Aaronson (25:58.980)
or we'd been even overtaken by such AIs,
Lex Fridman (26:01.980)
the entire discussion of the hard problem of consciousness
Lex Fridman (26:05.940)
would have a different character, right?
Lex Fridman (26:07.660)
It would take place in different terms in such a world,
Scott Aaronson (26:10.420)
even if we hadn't answered the question.
Lex Fridman (26:12.740)
And my claim about free will would be similar, right?
Scott Aaronson (26:15.620)
That if this prediction machine that I was talking about
Lex Fridman (26:19.060)
could actually be built, well, now the entire discussion
Scott Aaronson (26:21.980)
of the, you know, of free will is sort of transformed
Lex Fridman (26:24.620)
by that, you know, even if in some sense
Scott Aaronson (26:27.380)
the metaphysical question hasn't been answered.
Lex Fridman (26:31.780)
Yeah, exactly, it transforms it fundamentally
Scott Aaronson (26:34.180)
because say that machine does tell you
Lex Fridman (26:35.900)
that it can predict perfectly
Lex Fridman (26:37.620)
and yet there is this deep experience of free will
Lex Fridman (26:40.100)
and then that changes the question completely.
Lex Fridman (26:43.100)
And it starts actually getting to the question
Lex Fridman (26:46.220)
of the AGI, the touring questions
Scott Aaronson (26:51.580)
of the demonstration of free will,
Lex Fridman (26:54.940)
the demonstration of intelligence,
Scott Aaronson (26:56.580)
the demonstration of consciousness,
Lex Fridman (26:58.500)
does that equal consciousness, intelligence and free will?
Lex Fridman (27:02.300)
But see, Alex, if every time I was contemplating a decision,
Lex Fridman (27:07.580)
you know, this machine had printed out an envelope,
Scott Aaronson (27:10.220)
you know, where I could open it
Lex Fridman (27:11.540)
and see that it knew my decision,
Scott Aaronson (27:13.220)
I think that actually would change
Lex Fridman (27:14.700)
my subjective experience of making decisions, right?
Scott Aaronson (27:18.180)
I mean, it would.
Lex Fridman (27:19.020)
Does knowledge change your subjective experience?
Scott Aaronson (27:20.860)
Well, you know, I mean, the knowledge
Lex Fridman (27:22.660)
that this machine had predicted everything I would do,
Lex Fridman (27:25.020)
I mean, it might drive me completely insane, right?
Lex Fridman (27:27.780)
But at any rate, it would change my experience
Scott Aaronson (27:30.740)
to act, you know, to not just discuss such a machine
Lex Fridman (27:33.820)
as a thought experiment, but to actually see it.
Scott Aaronson (27:37.140)
Yeah.
Lex Fridman (27:39.180)
I mean, you know, you could say at that point,
Scott Aaronson (27:41.740)
you know, you could say, you know,
Lex Fridman (27:43.380)
why not simply call this machine
Lex Fridman (27:45.900)
a second instantiation of me and be done with it, right?
Lex Fridman (27:49.180)
What, you know, why even privilege the original me
Lex Fridman (27:53.460)
over this perfect duplicate that exists in the machine?
Lex Fridman (27:56.940)
Yeah, or there could be a religious experience with it too.
Scott Aaronson (28:00.100)
It's kind of what God throughout the generations
Lex Fridman (28:02.460)
is supposed to have.
Scott Aaronson (28:03.780)
That God kind of represents that perfect machine,
Lex Fridman (28:06.860)
is able to, I guess, actually,
Scott Aaronson (28:10.780)
well, I don't even know what are the religious
Lex Fridman (28:14.340)
interpretations of free will.
Lex Fridman (28:17.660)
So if God knows perfectly everything in religion,
Lex Fridman (28:22.580)
in the various religions,
Lex Fridman (28:24.700)
where does free will fit into that?
Lex Fridman (28:26.580)
Do you know?
Scott Aaronson (28:27.420)
That has been one of the big things that theologians
Lex Fridman (28:30.220)
have argued about for thousands of years.
Scott Aaronson (28:32.100)
Yeah.
Lex Fridman (28:33.420)
You know, I am not a theologian,
Lex Fridman (28:35.260)
so maybe I shouldn't go there.
Lex Fridman (28:36.460)
So there's not a clear answer in a book like...
Scott Aaronson (28:38.940)
I mean, this is, you know, the Calvinists debated this,
Lex Fridman (28:41.940)
the, you know, this has been, you know,
Scott Aaronson (28:43.820)
I mean, different religious movements
Lex Fridman (28:46.180)
have taken different positions on that question,
Lex Fridman (28:48.180)
but that is how they think about it.
Lex Fridman (28:50.140)
You know, meanwhile, you know,
Scott Aaronson (28:51.660)
a large part of sort of what animates,
Lex Fridman (28:54.700)
you know, theoretical computer science,
Scott Aaronson (28:56.580)
you could say is, you know, we're asking sort of,
Lex Fridman (28:58.500)
what are the ultimate limits of, you know,
Lex Fridman (29:01.100)
what you can know or, you know, calculate or figure out
Lex Fridman (29:05.540)
by, you know, entities that you can actually build
Lex Fridman (29:08.180)
in the physical world, right?
Lex Fridman (29:09.740)
And if I were trying to explain it to a theologian,
Scott Aaronson (29:12.860)
maybe I would say, you know, we are studying, you know,
Lex Fridman (29:15.260)
to what extent, you know,
Scott Aaronson (29:16.460)
gods can be made manifest in the physical world.
Lex Fridman (29:19.820)
I'm not sure my colleagues would like that.
Lex Fridman (29:21.620)
So let's talk about quantum computers for a second.
Lex Fridman (29:25.660)
Yeah, sure, sure.
Scott Aaronson (29:27.340)
As you've said, quantum computing,
Lex Fridman (29:29.180)
at least in the 1990s, was a profound story
Scott Aaronson (29:32.300)
at the intersection of computer science,
Lex Fridman (29:33.940)
physics, engineering, math, and philosophy.
Lex Fridman (29:36.340)
So there's this broad and deep aspect to quantum computing
Lex Fridman (29:40.260)
that represents more than just the quantum computer.
Lex Fridman (29:42.820)
But can we start at the very basics?
Lex Fridman (29:45.180)
What is quantum computing?
Scott Aaronson (29:47.700)
Yeah, so it's a proposal for a new type of computation,
Lex Fridman (29:52.700)
or let's say a new way to harness nature to do computation
Scott Aaronson (29:56.580)
that is based on the principles of quantum mechanics.
Lex Fridman (29:59.700)
Okay, now the principles of quantum mechanics
Scott Aaronson (30:01.980)
have been in place since 1926.
Lex Fridman (30:05.500)
You know, they haven't changed.
Scott Aaronson (30:07.580)
You know, what's new is, you know, how we wanna use them.
Lex Fridman (30:10.620)
Okay, so what does quantum mechanics say about the world?
Scott Aaronson (30:15.140)
You know, the physicists, I think, over the generations,
Lex Fridman (30:18.060)
you know, convinced people
Scott Aaronson (30:19.060)
that that is an unbelievably complicated question
Lex Fridman (30:22.180)
and, you know, just give up on trying to understand it.
Scott Aaronson (30:25.420)
I can let you in, not being a physicist,
Lex Fridman (30:28.060)
I can let you in on a secret,
Scott Aaronson (30:29.460)
which is that it becomes a lot simpler
Lex Fridman (30:32.060)
if you do what we do in quantum information theory
Lex Fridman (30:35.300)
and sort of take the physics out of it.
Lex Fridman (30:37.460)
So the way that we think about quantum mechanics
Scott Aaronson (30:40.780)
is sort of as a generalization
Lex Fridman (30:42.820)
of the rules of probability themselves.
Scott Aaronson (30:45.300)
So, you know, you might say there was a 30% chance
Lex Fridman (30:50.300)
that it was going to snow today or something.
Scott Aaronson (30:52.620)
You would never say that there was a negative 30% chance,
Lex Fridman (30:55.500)
right, that would be nonsense.
Scott Aaronson (30:57.420)
Much less would you say that there was, you know,
Lex Fridman (30:59.260)
an I% chance, you know, square root of minus 1% chance.
Scott Aaronson (31:03.740)
Now, the central discovery
Lex Fridman (31:06.100)
that sort of quantum mechanics made
Scott Aaronson (31:09.460)
is that fundamentally the world is described by,
Lex Fridman (31:16.420)
or, you know, the sort of, let's say the possibilities
Scott Aaronson (31:18.780)
for, you know, what a system could be doing
Lex Fridman (31:21.860)
are described using numbers called amplitudes, okay,
Scott Aaronson (31:25.540)
which are like probabilities in some ways,
Lex Fridman (31:29.020)
but they are not probabilities.
Scott Aaronson (31:30.780)
They can be positive.
Lex Fridman (31:31.900)
For one thing, they can be positive or negative.
Scott Aaronson (31:34.540)
In fact, they can even be complex numbers.
Lex Fridman (31:37.140)
Okay, and if you've heard of a quantum superposition,
Scott Aaronson (31:39.980)
this just means some state of affairs
Lex Fridman (31:43.180)
where you assign an amplitude,
Scott Aaronson (31:45.380)
one of these complex numbers,
Lex Fridman (31:47.100)
to every possible configuration
Scott Aaronson (31:51.060)
that you could see a system in on measuring it.
Lex Fridman (31:53.340)
So for example, you might say that an electron
Scott Aaronson (31:56.700)
has some amplitude for being here
Lex Fridman (31:59.420)
and some other amplitude for being there, right?
Scott Aaronson (32:02.260)
Now, if you look to see where it is,
Lex Fridman (32:04.740)
you will localize it, right?
Scott Aaronson (32:06.460)
You will sort of force the amplitudes
Lex Fridman (32:09.140)
to be converted into probabilities.
Scott Aaronson (32:12.220)
That happens by taking their squared absolute value, okay,
Lex Fridman (32:15.300)
and then, you know, you can say
Scott Aaronson (32:19.460)
either the electron will be here or it will be there.
Lex Fridman (32:22.580)
And, you know, knowing the amplitudes,
Scott Aaronson (32:24.180)
you can predict at least the probabilities
Lex Fridman (32:26.540)
that you'll see each possible outcome, okay?
Lex Fridman (32:29.900)
But while a system is isolated
Lex Fridman (32:32.540)
from the whole rest of the universe,
Scott Aaronson (32:34.660)
the rest of its environment,
Lex Fridman (32:36.380)
the amplitudes can change in time
Scott Aaronson (32:38.820)
by rules that are different
Lex Fridman (32:41.380)
from the normal rules of probability
Lex Fridman (32:44.420)
and that are, you know, alien to our everyday experience.
Lex Fridman (32:47.540)
So anytime anyone ever tells you anything
Scott Aaronson (32:50.420)
about the weirdness of the quantum world,
Lex Fridman (32:52.620)
you know, or assuming that they're not lying to you, right,
Scott Aaronson (32:55.940)
they are telling you, you know,
Lex Fridman (32:57.780)
yet another consequence of nature
Scott Aaronson (33:00.140)
being described by these amplitudes.
Lex Fridman (33:03.060)
So most famously, what amplitudes can do
Lex Fridman (33:05.860)
is that they can interfere with each other, okay?
Lex Fridman (33:08.060)
So in the famous double slit experiment,
Lex Fridman (33:11.300)
what happens is that you shoot a particle,
Lex Fridman (33:13.580)
like an electron, let's say,
Scott Aaronson (33:15.300)
at a screen with two slits in it,
Lex Fridman (33:17.540)
and you find that there are, you know, on a second screen,
Scott Aaronson (33:21.020)
now there are certain places
Lex Fridman (33:22.660)
where that electron will never end up,
Scott Aaronson (33:25.020)
you know, after it passes through the first screen.
Lex Fridman (33:29.420)
And yet, if I close off one of the slits,
Lex Fridman (33:32.460)
then the electron can appear in that place, okay?
Lex Fridman (33:35.300)
So by decreasing the number of paths
Scott Aaronson (33:38.020)
that the electron could take to get somewhere,
Lex Fridman (33:40.540)
you can increase the chance that it gets there, okay?
Lex Fridman (33:43.260)
Now, how is that possible?
Lex Fridman (33:45.140)
Well, it's because, you know, as we would say now,
Lex Fridman (33:48.580)
the electron has a superposition state, okay?
Lex Fridman (33:51.620)
It has some amplitude for reaching this point
Scott Aaronson (33:54.860)
by going through the first slit.
Lex Fridman (33:57.620)
It has some other amplitude for reaching it
Scott Aaronson (33:59.660)
by going through the second slit.
Lex Fridman (34:01.500)
But now, if one amplitude is positive
Lex Fridman (34:03.820)
and the other one is negative,
Lex Fridman (34:05.540)
then, you know, I have to add them all up, right?
Scott Aaronson (34:07.860)
I have to add the amplitudes for every path
Lex Fridman (34:10.620)
that the electron could have taken to reach this point.
Lex Fridman (34:13.620)
And those amplitudes,
Lex Fridman (34:15.540)
if they're pointing in different directions,
Scott Aaronson (34:17.620)
they can cancel each other out.
Lex Fridman (34:19.540)
That would mean the total amplitude is zero
Lex Fridman (34:21.940)
and the thing never happens at all.
Lex Fridman (34:24.060)
I close off one of the possibilities,
Scott Aaronson (34:26.180)
then the amplitude is positive or it's negative,
Lex Fridman (34:28.620)
and now the thing can happen.
Scott Aaronson (34:30.300)
Okay, so that is sort of the one trick of quantum mechanics.
Lex Fridman (34:33.900)
And now I can tell you what a quantum computer is.
Scott Aaronson (34:36.620)
Okay, a quantum computer is a computer
Lex Fridman (34:41.060)
that tries to exploit, you know, exactly these phenomena,
Scott Aaronson (34:45.460)
superposition, amplitudes, and interference,
Lex Fridman (34:48.940)
in order to solve certain problems much faster
Scott Aaronson (34:52.060)
than we know how to solve them otherwise.
Lex Fridman (34:54.260)
So the basic building block of a quantum computer
Scott Aaronson (34:56.740)
is what we call a quantum bit or a qubit.
Lex Fridman (34:59.940)
That just means a bit that has some amplitude for being zero
Lex Fridman (35:03.460)
and some other amplitude for being one.
Lex Fridman (35:05.860)
So it's a superposition of zero and one states, right?
Lex Fridman (35:09.260)
But now the key point is that if I've got,
Lex Fridman (35:12.300)
let's say, a thousand qubits,
Scott Aaronson (35:14.740)
the rules of quantum mechanics are completely unequivocal
Lex Fridman (35:18.060)
that I do not just need one ampli...
Scott Aaronson (35:20.340)
You know, I don't just need amplitudes for each qubit separately.
Lex Fridman (35:23.540)
Okay, in general, I need an amplitude
Lex Fridman (35:26.100)
for every possible setting of all thousand of those bits, okay?
Lex Fridman (35:30.780)
So that what that means is two to the one thousand power amplitudes.
Scott Aaronson (35:34.900)
Okay, if I had to write those down,
Lex Fridman (35:37.620)
or let's say in the memory of a conventional computer,
Scott Aaronson (35:40.420)
if I had to write down two to the one thousand complex numbers,
Lex Fridman (35:43.740)
that would not fit within the entire observable universe.
Scott Aaronson (35:47.340)
Okay, and yet, you know, quantum mechanics is unequivocal
Lex Fridman (35:50.860)
that if these qubits can all interact with each other,
Lex Fridman (35:53.860)
and in some sense, I need two to the one thousand parameters,
Lex Fridman (35:58.020)
you know, amplitudes to describe what is going on.
Scott Aaronson (36:01.180)
Now, you know, now I can tell, you know, where all the popular articles,
Lex Fridman (36:05.900)
you know, about quantum computing go off the rails
Scott Aaronson (36:08.380)
is that they say, you know, they sort of say what I just said,
Lex Fridman (36:11.860)
and then they say, oh, so the way a quantum computer works
Scott Aaronson (36:14.620)
is just by trying every possible answer in parallel.
Lex Fridman (36:17.900)
You know, that sounds too good to be true,
Lex Fridman (36:21.020)
and unfortunately, it kind of is too good to be true.
Lex Fridman (36:24.620)
The problem is I could make a superposition
Scott Aaronson (36:27.980)
over every possible answer to my problem, you know,
Lex Fridman (36:31.340)
even if there are two to the one thousand of them, right?
Scott Aaronson (36:34.060)
I can easily do that.
Lex Fridman (36:35.740)
The trouble is for a computer to be useful,
Scott Aaronson (36:38.140)
you've got to, at some point, you've got to look at it
Lex Fridman (36:40.300)
and see an output, right?
Lex Fridman (36:42.380)
And if I just measure a superposition over every possible answer,
Lex Fridman (36:46.700)
then the rules of quantum mechanics tell me
Scott Aaronson (36:48.620)
that all I'll see will be a random answer.
Lex Fridman (36:51.340)
You know, if I just wanted a random answer,
Lex Fridman (36:53.020)
well, I could have picked one myself with a lot less trouble, right?
Lex Fridman (36:56.300)
So the entire trick with quantum computing,
Scott Aaronson (36:59.980)
with every algorithm for a quantum computer,
Lex Fridman (37:02.780)
is that you try to choreograph a pattern
Scott Aaronson (37:05.740)
of interference of amplitudes,
Lex Fridman (37:08.380)
and you try to do it so that for each wrong answer,
Scott Aaronson (37:11.500)
some of the paths leading to that wrong answer
Lex Fridman (37:14.060)
have positive amplitudes and others have negative amplitudes.
Lex Fridman (37:17.900)
So on the whole, they cancel each other out, okay?
Lex Fridman (37:20.540)
Whereas all the paths leading to the right answer
Scott Aaronson (37:23.420)
should reinforce each other, you know, should have amplitudes
Lex Fridman (37:26.620)
pointing the same direction.
Lex Fridman (37:28.060)
So the design of algorithms in the space
Lex Fridman (37:30.700)
is the choreography of the interferences.
Scott Aaronson (37:33.100)
Precisely. That's precisely what it is.
Lex Fridman (37:35.020)
Can we take a brief step back?
Lex Fridman (37:36.700)
And you mentioned information.
Lex Fridman (37:39.820)
Yes.
Lex Fridman (37:40.380)
So in which part of this beautiful picture
Lex Fridman (37:43.180)
that you've painted is information contained?
Scott Aaronson (37:46.620)
Oh, well, information is at the core of everything
Lex Fridman (37:49.500)
that we've been talking about, right?
Scott Aaronson (37:51.020)
I mean, the bit is, you know, the basic unit of information
Lex Fridman (37:55.260)
since, you know, Claude Shannon's paper in 1948.
Scott Aaronson (37:58.940)
You know, and, you know, of course, you know,
Lex Fridman (38:00.140)
people had the concept even before that, you know,
Lex Fridman (38:02.460)
he popularized the name, right?
Lex Fridman (38:05.100)
But I mean...
Lex Fridman (38:05.740)
But a bit is zero or one.
Lex Fridman (38:07.740)
That's right.
Lex Fridman (38:08.220)
So that's a basic element of information.
Lex Fridman (38:08.940)
That's right.
Lex Fridman (38:09.420)
And what we would say is that the basic unit
Lex Fridman (38:11.740)
of quantum information is the qubit,
Scott Aaronson (38:14.540)
is, you know, the object, any object
Lex Fridman (38:16.940)
that can be maintained in this, or manipulated,
Scott Aaronson (38:20.860)
in a superposition of zero and one states.
Lex Fridman (38:24.060)
Now, you know, sometimes people ask, well,
Lex Fridman (38:26.380)
but what is a qubit physically, right?
Lex Fridman (38:29.020)
And there are all these different, you know,
Scott Aaronson (38:32.220)
proposals that are being pursued in parallel
Lex Fridman (38:34.700)
for how you implement qubits.
Scott Aaronson (38:36.860)
There is, you know, superconducting quantum computing
Lex Fridman (38:39.660)
that was in the news recently
Lex Fridman (38:41.420)
because of Google's quantum supremacy experiment, right?
Lex Fridman (38:44.940)
Where you would have some little coils
Scott Aaronson (38:49.500)
where a current can flow through them
Lex Fridman (38:52.220)
in two different energy states,
Scott Aaronson (38:54.300)
one representing a zero, another representing a one.
Lex Fridman (38:57.500)
And if you cool these coils
Scott Aaronson (38:59.180)
to just slightly above absolute zero,
Lex Fridman (39:02.060)
like a hundredth of a degree, then they superconduct.
Lex Fridman (39:05.500)
And then the current can actually be
Lex Fridman (39:07.260)
in a superposition of the two different states.
Lex Fridman (39:10.620)
So that's one kind of qubit.
Lex Fridman (39:12.300)
Another kind would be, you know,
Lex Fridman (39:14.460)
just an individual atomic nucleus, right?
Lex Fridman (39:17.660)
It has a spin.
Scott Aaronson (39:18.940)
It could be spinning clockwise.
Lex Fridman (39:20.940)
It could be spinning counterclockwise,
Scott Aaronson (39:23.020)
or it could be in a superposition of the two spin states.
Lex Fridman (39:25.980)
That is another qubit.
Lex Fridman (39:27.420)
But see, just like in the classical world, right?
Lex Fridman (39:30.220)
You could be a virtuoso programmer
Lex Fridman (39:32.780)
without having any idea of what a transistor is, right?
Lex Fridman (39:36.300)
Or how the bits are physically represented inside the machine,
Lex Fridman (39:40.380)
even that the machine uses electricity, right?
Lex Fridman (39:43.180)
You just care about the logic.
Lex Fridman (39:44.940)
It's sort of the same with quantum computing, right?
Lex Fridman (39:47.260)
Qubits could be realized by many,
Scott Aaronson (39:49.420)
many different quantum systems.
Lex Fridman (39:51.260)
And yet all of those systems will lead to the same logic,
Scott Aaronson (39:54.380)
you know, the logic of qubits and how, you know,
Lex Fridman (39:58.540)
how you measure them, how you change them over time.
Lex Fridman (40:01.420)
And so, you know, the subject of, you know,
Lex Fridman (40:03.980)
how qubits behave and what you can do with qubits,
Scott Aaronson (40:07.420)
that is quantum information.
Lex Fridman (40:09.260)
So just to linger on that.
Scott Aaronson (40:10.940)
Sure.
Lex Fridman (40:11.260)
So the physical design implementation of a qubit
Scott Aaronson (40:14.380)
does not interfere with the,
Lex Fridman (40:18.700)
that next level of abstraction that you can program over it.
Lex Fridman (40:22.380)
So it truly is, the idea of it is, okay.
Lex Fridman (40:27.020)
Well, to be honest with you,
Scott Aaronson (40:28.780)
today they do interfere with each other.
Lex Fridman (40:30.700)
That's because all the quantum computers
Lex Fridman (40:32.860)
we can build today are very noisy, right?
Lex Fridman (40:35.420)
And so sort of the, you know,
Scott Aaronson (40:37.820)
the qubits are very far from perfect.
Lex Fridman (40:40.940)
And so the lower level sort of does affect the higher levels.
Lex Fridman (40:43.900)
And we sort of have to think about all of them at once.
Lex Fridman (40:46.380)
Okay, but eventually where we hope to get
Scott Aaronson (40:49.180)
is to what are called error corrected quantum computers,
Lex Fridman (40:52.460)
where the qubits really do behave
Scott Aaronson (40:54.540)
like perfect abstract qubits for as long as we want them to.
Lex Fridman (40:58.780)
And in that future, you know,
Scott Aaronson (41:01.500)
a future that we can already sort of prove theorems about
Lex Fridman (41:04.940)
or think about today.
Lex Fridman (41:06.380)
But in that future, the logic of it
Lex Fridman (41:09.500)
really does become decoupled from the hardware.
Lex Fridman (41:11.980)
So if noise is currently like the biggest problem
Lex Fridman (41:16.300)
for quantum computing,
Lex Fridman (41:18.220)
and then the dream is error correcting quantum computers,
Lex Fridman (41:23.020)
can you just maybe describe what does it mean
Lex Fridman (41:26.620)
for there to be noise in the system?
Lex Fridman (41:28.780)
Absolutely, so yeah, so the problem
Scott Aaronson (41:31.020)
is even a little more specific than noise.
Lex Fridman (41:33.100)
So the fundamental problem,
Scott Aaronson (41:35.260)
if you're trying to actually build a quantum computer,
Lex Fridman (41:38.380)
you know, of any appreciable size,
Scott Aaronson (41:41.260)
is something called decoherence.
Lex Fridman (41:43.660)
Okay, and this was recognized from the very beginning,
Scott Aaronson (41:46.220)
you know, when people first started thinking about this
Lex Fridman (41:48.460)
in the 1990s.
Scott Aaronson (41:49.980)
Now, what decoherence means
Lex Fridman (41:52.620)
is sort of the unwanted interaction
Scott Aaronson (41:54.780)
between, you know, your qubits,
Lex Fridman (41:56.860)
you know, the state of your quantum computer
Lex Fridman (41:59.180)
and the external environment.
Lex Fridman (42:01.100)
Okay, and why is that such a problem?
Scott Aaronson (42:03.100)
Well, I talked before about how, you know,
Lex Fridman (42:05.180)
when you measure a quantum system,
Lex Fridman (42:07.660)
so let's say if I measure a qubit
Lex Fridman (42:09.900)
that's in a superposition of zero and one states
Lex Fridman (42:12.140)
to ask it, you know, are you zero or are you one?
Lex Fridman (42:14.620)
Well, now I force it to make up its mind, right?
Lex Fridman (42:17.100)
And now, probabilistically, it chooses one or the other
Lex Fridman (42:20.860)
and now, you know, it's no longer a superposition,
Scott Aaronson (42:23.260)
there's no longer amplitudes,
Lex Fridman (42:25.020)
there's just, there's some probability that I get a zero
Lex Fridman (42:27.500)
and there's some that I get a one.
Lex Fridman (42:29.180)
And now, the trouble is that it doesn't have to be me
Lex Fridman (42:35.180)
who's looking, okay?
Lex Fridman (42:36.300)
Or in fact, it doesn't have to be any conscious entity.
Scott Aaronson (42:40.380)
Any kind of interaction with the external world
Lex Fridman (42:44.220)
that leaks out the information
Scott Aaronson (42:46.620)
about whether this qubit was a zero or a one,
Lex Fridman (42:49.900)
sort of that causes the zerowness
Scott Aaronson (42:52.380)
or the oneness of the qubit to be recorded
Lex Fridman (42:55.740)
in, you know, the radiation in the room,
Scott Aaronson (42:58.220)
in the molecules of the air,
Lex Fridman (43:00.540)
in the wires that are connected to my device,
Scott Aaronson (43:03.900)
any of that, as soon as the information leaks out,
Lex Fridman (43:07.900)
it is as if that qubit has been measured, okay?
Scott Aaronson (43:11.020)
It is, you know, the state has now collapsed.
Lex Fridman (43:15.020)
You know, another way to say it
Lex Fridman (43:16.220)
is that it's become entangled with its environment, okay?
Lex Fridman (43:19.340)
But, you know, from the perspective of someone
Scott Aaronson (43:21.740)
who's just looking at this qubit,
Lex Fridman (43:23.420)
it is as though it has lost its quantum state.
Lex Fridman (43:26.700)
And so, what this means is that
Lex Fridman (43:28.540)
if I want to do a quantum computation,
Scott Aaronson (43:31.660)
I have to keep the qubits sort of fanatically
Lex Fridman (43:34.780)
well isolated from their environment.
Lex Fridman (43:37.340)
But then at the same time,
Lex Fridman (43:38.540)
they can't be perfectly isolated
Scott Aaronson (43:40.300)
because I need to tell them what to do.
Lex Fridman (43:42.460)
I need to make them interact with each other,
Scott Aaronson (43:45.100)
for one thing, and not only that,
Lex Fridman (43:46.940)
but in a precisely choreographed way, okay?
Lex Fridman (43:50.060)
And, you know, that is such a staggering problem, right?
Lex Fridman (43:53.420)
How do I isolate these qubits from the whole universe
Lex Fridman (43:56.300)
but then also tell them exactly what to do?
Lex Fridman (43:58.700)
I mean, you know, there were distinguished physicists
Lex Fridman (44:01.420)
and computer scientists in the 90s who said,
Lex Fridman (44:04.620)
this is fundamentally impossible, you know?
Scott Aaronson (44:07.020)
The laws of physics will just never let you control qubits
Lex Fridman (44:10.540)
to the degree of accuracy that you're talking about.
Scott Aaronson (44:14.140)
Now, what changed the views of most of us
Lex Fridman (44:17.660)
was a profound discovery in the mid to late 90s
Scott Aaronson (44:22.300)
which was called the theory of quantum error correction
Lex Fridman (44:25.340)
and quantum fault tolerance, okay?
Lex Fridman (44:27.580)
And the upshot of that theory is that
Lex Fridman (44:29.980)
if I want to build a reliable quantum computer
Lex Fridman (44:33.500)
and scale it up to, you know, an arbitrary number
Lex Fridman (44:36.300)
of as many qubits as I want, you know,
Lex Fridman (44:38.540)
and doing as much on them as I want,
Lex Fridman (44:41.180)
I do not actually have to get the qubits
Scott Aaronson (44:43.580)
perfectly isolated from their environment.
Lex Fridman (44:46.060)
It is enough to get them really, really, really well isolated, okay?
Lex Fridman (44:50.060)
And even if every qubit is sort of leaking,
Lex Fridman (44:54.620)
you know, its state into the environment at some rate,
Scott Aaronson (44:57.820)
as long as that rate is low enough, okay,
Lex Fridman (45:00.460)
I can sort of encode the information that I care about
Scott Aaronson (45:05.100)
in very clever ways across the collective states
Lex Fridman (45:08.300)
of multiple qubits, okay?
Scott Aaronson (45:10.140)
In such a way that even if, you know,
Lex Fridman (45:12.380)
a small percentage of my qubits leak,
Scott Aaronson (45:14.940)
well, I'm constantly monitoring them
Lex Fridman (45:16.860)
to see if that leak happened.
Scott Aaronson (45:18.380)
I can detect it and I can correct it.
Lex Fridman (45:20.940)
I can recover the information I care about
Lex Fridman (45:23.340)
from the remaining qubits, okay?
Lex Fridman (45:25.500)
And so, you know, you can build a reliable quantum computer
Lex Fridman (45:30.300)
even out of unreliable parts, right?
Lex Fridman (45:32.700)
Now, in some sense, you know,
Scott Aaronson (45:35.740)
that discovery is what set the engineering agenda
Lex Fridman (45:39.100)
for quantum computing research
Lex Fridman (45:41.020)
from the 1990s until the present, okay?
Lex Fridman (45:43.660)
The goal has been, you know,
Scott Aaronson (45:45.420)
engineer qubits that are not perfectly reliable
Lex Fridman (45:48.940)
but reliable enough that you can then use
Scott Aaronson (45:51.900)
these error correcting codes
Lex Fridman (45:53.820)
to have them simulate qubits
Lex Fridman (45:56.140)
that are even more reliable than they are, right?
Lex Fridman (45:58.940)
The error correction becomes a net win
Lex Fridman (46:01.020)
rather than a net loss, right?
Lex Fridman (46:02.860)
And then once you reach that sort of crossover point,
Scott Aaronson (46:05.900)
then, you know, your simulated qubits
Lex Fridman (46:08.220)
could in turn simulate qubits
Scott Aaronson (46:10.140)
that are even more reliable and so on
Lex Fridman (46:12.460)
until you've just, you know, effectively,
Scott Aaronson (46:14.540)
you have arbitrarily reliable qubits.
Lex Fridman (46:17.020)
So long story short,
Scott Aaronson (46:18.140)
we are not at that breakeven point yet.
Lex Fridman (46:20.620)
We're a hell of a lot closer than we were
Scott Aaronson (46:22.540)
when people started doing this in the 90s,
Lex Fridman (46:24.700)
like orders of magnitude closer.
Lex Fridman (46:26.300)
But the key ingredient there
Lex Fridman (46:27.580)
is the more qubits, the better because...
Scott Aaronson (46:30.300)
Ah, well, the more qubits,
Lex Fridman (46:32.060)
the larger the computation you can do, right?
Scott Aaronson (46:35.100)
I mean, qubits are what constitute
Lex Fridman (46:38.060)
the memory of your quantum computer, right?
Lex Fridman (46:40.300)
But also for the, sorry,
Lex Fridman (46:41.580)
for the error correcting mechanism.
Scott Aaronson (46:43.100)
Ah, yes.
Lex Fridman (46:44.540)
So the way I would say it
Scott Aaronson (46:45.980)
is that error correction imposes an overhead
Lex Fridman (46:48.780)
in the number of qubits.
Lex Fridman (46:50.220)
And that is actually one of the biggest practical problems
Lex Fridman (46:53.260)
with building a scalable quantum computer.
Scott Aaronson (46:55.500)
If you look at the error correcting codes,
Lex Fridman (46:57.900)
at least the ones that we know about today,
Lex Fridman (47:00.380)
and you look at, you know,
Lex Fridman (47:01.340)
what would it take to actually use a quantum computer
Scott Aaronson (47:04.460)
to, you know, hack your credit card number,
Lex Fridman (47:09.100)
which is, you know,
Scott Aaronson (47:10.060)
maybe, you know, the most famous application
Lex Fridman (47:11.980)
people talk about, right?
Scott Aaronson (47:13.180)
Let's say to factor huge numbers
Lex Fridman (47:15.180)
and thereby break the RSA cryptosystem.
Scott Aaronson (47:17.900)
Well, what that would take
Lex Fridman (47:19.420)
would be thousands of, several thousand logical qubits.
Lex Fridman (47:23.980)
But now with the known error correcting codes,
Lex Fridman (47:26.460)
each of those logical qubits
Scott Aaronson (47:28.220)
would need to be encoded itself
Lex Fridman (47:29.980)
using thousands of physical qubits.
Lex Fridman (47:32.220)
So at that point,
Lex Fridman (47:32.940)
you're talking about millions of physical qubits.
Lex Fridman (47:35.740)
And in some sense,
Lex Fridman (47:36.620)
that is the reason why quantum computers
Scott Aaronson (47:38.860)
are not breaking cryptography already.
Lex Fridman (47:40.780)
It's because of these immense overheads involved.
Lex Fridman (47:43.740)
So that overhead is additive or multiplicative?
Lex Fridman (47:46.300)
Well, it's multiplicative.
Scott Aaronson (47:47.420)
I mean, it's like you take the number
Lex Fridman (47:49.580)
of logical qubits that you need
Scott Aaronson (47:52.460)
in your abstract quantum circuit,
Lex Fridman (47:54.380)
you multiply it by a thousand or so.
Scott Aaronson (47:56.700)
So, you know, there's a lot of work
Lex Fridman (47:58.220)
on, you know, inventing better,
Scott Aaronson (47:59.900)
trying to invent better error correcting codes.
Lex Fridman (48:02.220)
Okay, that is the situation right now.
Scott Aaronson (48:04.140)
In the meantime, we are now in,
Lex Fridman (48:07.420)
what the physicist John Preskill called
Scott Aaronson (48:09.580)
the noisy intermediate scale quantum or NISQ era.
Lex Fridman (48:13.420)
And this is the era,
Scott Aaronson (48:14.540)
you can think of it as sort of like the vacuum,
Lex Fridman (48:16.780)
you know, we're now entering the very early
Scott Aaronson (48:19.020)
vacuum tube era of quantum computers.
Lex Fridman (48:21.740)
The quantum computer analog of the transistor
Lex Fridman (48:24.700)
has not been invented yet, right?
Lex Fridman (48:26.460)
That would be like true error correction, right?
Scott Aaronson (48:29.020)
Where, you know, we are not or something else
Lex Fridman (48:31.420)
that would achieve the same effect, right?
Scott Aaronson (48:33.420)
We are not there yet.
Lex Fridman (48:37.020)
But where we are now,
Scott Aaronson (48:38.300)
let's say as of a few months ago,
Lex Fridman (48:40.140)
you know, as of Google's announcement
Scott Aaronson (48:41.980)
of quantum supremacy,
Lex Fridman (48:43.500)
you know, we are now finally at the point
Scott Aaronson (48:45.660)
where even with a non error corrected quantum computer,
Lex Fridman (48:49.260)
with, you know, these noisy devices,
Scott Aaronson (48:51.260)
we can do something that is hard
Lex Fridman (48:53.740)
for classical computers to simulate, okay?
Lex Fridman (48:56.380)
So we can eke out some advantage.
Lex Fridman (48:58.620)
Now, will we in this noisy era
Scott Aaronson (49:00.620)
be able to do something beyond
Lex Fridman (49:02.620)
what a classical computer can do
Lex Fridman (49:04.140)
that is also useful to someone?
Lex Fridman (49:06.380)
That we still don't know.
Scott Aaronson (49:07.660)
People are going to be racing over the next decade
Lex Fridman (49:10.460)
to try to do that.
Scott Aaronson (49:11.420)
By people, I mean, Google, IBM,
Lex Fridman (49:13.580)
you know, a bunch of startup companies.
Lex Fridman (49:16.220)
And research labs.
Lex Fridman (49:18.540)
Yeah, and research labs and governments.
Lex Fridman (49:21.180)
And yeah.
Lex Fridman (49:22.460)
You just mentioned a million things.
Scott Aaronson (49:23.980)
Well, I'll backtrack for a second.
Lex Fridman (49:25.580)
Yeah, sure, sure.
Lex Fridman (49:27.100)
So we're in these vacuum tube days.
Lex Fridman (49:29.580)
Yeah, just entering them.
Lex Fridman (49:31.020)
And just entering, wow.
Lex Fridman (49:32.860)
Okay, so how do we escape the vacuum?
Lex Fridman (49:36.380)
So how do we get to,
Lex Fridman (49:39.500)
how do we get to where we are now with the CPU?
Lex Fridman (49:42.140)
Is this a fundamental engineering challenge?
Lex Fridman (49:44.700)
Is there breakthroughs on the physics side
Lex Fridman (49:49.020)
that are needed on the computer science side?
Lex Fridman (49:53.180)
Or is it a financial issue
Scott Aaronson (49:56.060)
where much larger just sheer investment
Lex Fridman (49:59.420)
and excitement is needed?
Scott Aaronson (50:01.020)
So, you know, those are excellent questions.
Lex Fridman (50:03.660)
My guess might, well, no, no.
Scott Aaronson (50:05.740)
My guess would be all of the above.
Lex Fridman (50:09.260)
I mean, my guess, you know,
Scott Aaronson (50:11.020)
I mean, you could say fundamentally
Lex Fridman (50:13.420)
it is an engineering issue, right?
Scott Aaronson (50:15.100)
The theory has been in place since the 90s.
Lex Fridman (50:17.980)
You know, at least, you know, this is what,
Scott Aaronson (50:21.100)
you know, error correction would look like.
Lex Fridman (50:23.340)
You know, we do not have the hardware
Scott Aaronson (50:25.420)
that is at that level.
Lex Fridman (50:26.780)
But at the same time, you know,
Lex Fridman (50:28.380)
so you could just, you know, try to power through,
Lex Fridman (50:32.220)
you know, maybe even like, you know,
Scott Aaronson (50:34.220)
if someone spent a trillion dollars
Lex Fridman (50:36.540)
on some quantum computing Manhattan project, right?
Scott Aaronson (50:39.420)
Then conceivably they could just, you know,
Lex Fridman (50:43.020)
build an error corrected quantum computer
Lex Fridman (50:46.540)
as it was envisioned back in the 90s, right?
Lex Fridman (50:49.580)
I think the more plausible thing to happen
Scott Aaronson (50:52.460)
is that there will be further theoretical breakthroughs
Lex Fridman (50:55.420)
and there will be further insights
Scott Aaronson (50:57.340)
that will cut down the cost of doing this.
Lex Fridman (50:59.900)
So let's take a brief step to the philosophical.
Scott Aaronson (51:02.940)
I just recently talked to Jim Keller
Lex Fridman (51:05.420)
who's sort of like the famed architect
Scott Aaronson (51:09.660)
in the microprocessor world.
Lex Fridman (51:12.220)
And he's been told for decades,
Scott Aaronson (51:16.380)
every year that the Moore's law is going to die this year.
Lex Fridman (51:20.460)
And he tries to argue that the Moore's law
Scott Aaronson (51:24.220)
is still alive and well,
Lex Fridman (51:25.580)
and it'll be alive for quite a long time to come.
Lex Fridman (51:28.380)
How long?
Lex Fridman (51:29.020)
How long did he say?
Scott Aaronson (51:30.060)
Well, the main point is it's still alive,
Lex Fridman (51:33.660)
but he thinks there's still a thousand X improvement
Scott Aaronson (51:38.140)
just on shrinking the transition that's possible.
Lex Fridman (51:40.940)
Whatever.
Scott Aaronson (51:41.420)
The point is that the exponential growth we see
Lex Fridman (51:45.420)
is actually a huge number of these S curves,
Scott Aaronson (51:49.740)
just constant breakthroughs.
Lex Fridman (51:51.660)
At the philosophical level,
Lex Fridman (51:53.820)
why do you think we as descendants of apes
Lex Fridman (51:57.980)
were able to just keep coming up
Scott Aaronson (52:00.540)
with these new breakthroughs on the CPU side
Lex Fridman (52:03.500)
is this something unique to this particular endeavor
Scott Aaronson (52:06.940)
or will it be possible to replicate
Lex Fridman (52:09.660)
in the quantum computer space?
Scott Aaronson (52:11.660)
Okay.
Lex Fridman (52:11.980)
All right.
Scott Aaronson (52:12.780)
There was a lot there,
Lex Fridman (52:15.340)
but to break off something,
Scott Aaronson (52:17.660)
I mean, I think we are in an extremely special period
Lex Fridman (52:20.860)
of human history, right?
Scott Aaronson (52:22.460)
I mean, it is, you could say,
Lex Fridman (52:24.780)
obviously special in many ways, right?
Scott Aaronson (52:28.220)
There are way more people alive
Lex Fridman (52:31.740)
than there have been
Lex Fridman (52:33.420)
and the whole future of the planet
Lex Fridman (52:39.740)
is in question in a way that it hasn't been
Scott Aaronson (52:44.460)
for the rest of human history.
Lex Fridman (52:46.620)
But in particular, we are in the era
Scott Aaronson (52:51.100)
where we finally figured out
Lex Fridman (52:53.900)
how to build universal machines,
Scott Aaronson (52:57.580)
you could say, the things that we call computers,
Lex Fridman (53:00.460)
machines that you program to simulate the behavior
Scott Aaronson (53:04.780)
of whatever machine you want.
Lex Fridman (53:07.020)
And once you've sort of crossed this threshold
Scott Aaronson (53:13.420)
of universality, you've built,
Lex Fridman (53:15.900)
you could say, touring,
Scott Aaronson (53:17.260)
you've instantiated touring machines
Lex Fridman (53:19.500)
in the physical world.
Scott Aaronson (53:20.780)
Well, then the main questions are ones of numbers.
Lex Fridman (53:23.900)
They are ones of how much memory can you access?
Lex Fridman (53:29.500)
How fast does it run?
Lex Fridman (53:31.100)
How many parallel processors?
Scott Aaronson (53:33.260)
At least until quantum computing.
Lex Fridman (53:34.780)
Quantum computing is the one thing
Lex Fridman (53:36.300)
that changes what I just said, right?
Lex Fridman (53:38.540)
But as long as it's classical computing,
Scott Aaronson (53:42.380)
then it's all questions of numbers.
Lex Fridman (53:44.700)
And you could say at a theoretical level,
Scott Aaronson (53:48.700)
the computers that we have today
Lex Fridman (53:50.380)
are the same as the ones in the 50s.
Scott Aaronson (53:52.620)
They're just millions of times faster
Lex Fridman (53:55.500)
and with millions of times more memory.
Lex Fridman (53:57.260)
And I think there's been an immense economic pressure
Lex Fridman (54:01.500)
to get more and more transistors,
Scott Aaronson (54:04.780)
get them smaller and smaller,
Lex Fridman (54:07.100)
add more and more cores.
Lex Fridman (54:09.020)
And in some sense, a huge fraction
Lex Fridman (54:14.380)
of all of the technological progress
Scott Aaronson (54:16.780)
that there is in all of civilization
Lex Fridman (54:19.260)
has gotten concentrated just more narrowly
Lex Fridman (54:22.300)
into just those problems, right?
Lex Fridman (54:24.860)
And so it has been one of the biggest success stories
Lex Fridman (54:29.420)
in the history of technology, right?
Lex Fridman (54:31.260)
There's, I mean, it is, I am as amazed by it
Lex Fridman (54:34.620)
as anyone else is, right?
Lex Fridman (54:36.620)
But at the same time, we also know that it,
Lex Fridman (54:40.700)
and I really do mean we know
Lex Fridman (54:45.340)
that it cannot continue indefinitely, okay?
Scott Aaronson (54:48.460)
Because you will reach fundamental limits
Lex Fridman (54:52.220)
on how small you can possibly make a processor.
Lex Fridman (54:56.780)
And if you want a real proof
Lex Fridman (54:58.940)
that would justify my use of the word,
Scott Aaronson (55:01.340)
we know that Moore's law has to end.
Lex Fridman (55:04.060)
I mean, ultimately you will reach the limits
Scott Aaronson (55:06.300)
imposed by quantum gravity.
Lex Fridman (55:10.780)
If you tried to build a computer
Scott Aaronson (55:12.540)
that operated at 10 to the 43 Hertz,
Lex Fridman (55:15.580)
so did 10 to the 43 operations per second,
Scott Aaronson (55:18.620)
that computer would use so much energy
Lex Fridman (55:20.780)
that it would simply collapse through a black hole, okay?
Lex Fridman (55:24.380)
So in reality, we're going to reach the limits
Lex Fridman (55:28.620)
long before that, but that is a sufficient proof.
Scott Aaronson (55:31.900)
That there's a limit.
Lex Fridman (55:33.420)
Yes, yes.
Lex Fridman (55:35.820)
But it would be interesting to try to understand
Lex Fridman (55:38.220)
the mechanism, the economic pressure that you said,
Scott Aaronson (55:40.860)
just like the Cold War was a pressure on getting us,
Lex Fridman (55:44.380)
getting us, because my us is both the Soviet Union
Lex Fridman (55:49.340)
and the United States, but getting us,
Lex Fridman (55:52.380)
the two countries to get to hurry up,
Scott Aaronson (55:54.780)
to get to space, to the moon,
Lex Fridman (55:56.300)
there seems to be that same kind of economic pressure
Scott Aaronson (55:58.940)
that somehow created a chain of engineering breakthroughs
Lex Fridman (56:03.340)
that resulted in the Moore's law.
Lex Fridman (56:05.580)
And it'd be nice to replicate.
Lex Fridman (56:07.180)
Yeah, well, I mean, some people are sort of,
Scott Aaronson (56:10.380)
get depressed about the fact
Lex Fridman (56:11.980)
that technological progress may seem to have slowed down
Lex Fridman (56:16.540)
in many, many realms outside of computing, right?
Lex Fridman (56:19.900)
And there was this whole thing of we wanted flying cars
Lex Fridman (56:22.620)
and we only got Twitter instead, right?
Lex Fridman (56:24.620)
Yeah, good old Peter Thiel, yeah.
Scott Aaronson (56:27.260)
Yeah, yeah, yeah, right, right, right.
Lex Fridman (56:28.700)
So then jumping to another really interesting topic
Scott Aaronson (56:31.900)
that you mentioned, so Google announced with their work
Lex Fridman (56:37.180)
in the paper in Nature with quantum supremacy.
Scott Aaronson (56:40.460)
Yes.
Lex Fridman (56:40.940)
Can you describe, again, back to the basic,
Lex Fridman (56:43.820)
what is perhaps not so basic, what is quantum supremacy?
Lex Fridman (56:47.900)
Absolutely, so quantum supremacy is a term
Scott Aaronson (56:51.980)
that was coined by, again, by John Preskill in 2012.
Lex Fridman (56:57.580)
Not everyone likes the name, but it sort of stuck.
Scott Aaronson (57:04.220)
We don't, we sort of haven't found a better alternative.
Lex Fridman (57:07.980)
It's technically quantum computational supremacy.
Scott Aaronson (57:10.460)
Yeah, yeah, supremacy, that's right, that's right.
Lex Fridman (57:12.700)
But the basic idea is actually one that goes all the way back
Scott Aaronson (57:16.220)
to the beginnings of quantum computing
Lex Fridman (57:18.460)
when Richard Feynman and David Deutsch, people like that,
Scott Aaronson (57:21.420)
were talking about it in the early 80s.
Lex Fridman (57:24.940)
And quantum supremacy just refers to sort of the point
Scott Aaronson (57:28.540)
in history when you can first use a quantum computer
Lex Fridman (57:32.380)
to do some well defined task much faster
Scott Aaronson (57:36.380)
than any known algorithm running on any of the classical computers
Lex Fridman (57:40.460)
that are available, okay?
Lex Fridman (57:42.220)
So notice that I did not say a useful task, okay?
Lex Fridman (57:46.540)
It could be something completely artificial,
Lex Fridman (57:48.940)
but it's important that the task be well defined.
Lex Fridman (57:51.740)
So in other words, it is something that has right and wrong answers
Lex Fridman (57:57.100)
that are knowable independently of this device, right?
Lex Fridman (58:00.460)
And we can then run the device, see if it gets the right answer or not.
Lex Fridman (58:04.300)
Can you clarify a small point?
Lex Fridman (58:05.900)
You said much faster than a classical implementation.
Lex Fridman (58:09.420)
What about sort of what about the space with where the class,
Lex Fridman (58:13.580)
there's no, there's not, it doesn't even exist,
Lex Fridman (58:16.300)
a classical algorithm to show the power?
Lex Fridman (58:18.780)
So maybe I should clarify.
Scott Aaronson (58:20.460)
Everything that a quantum computer can do,
Lex Fridman (58:22.940)
a classical computer can also eventually do, okay?
Lex Fridman (58:26.700)
And the reason why we know that is that a classical computer
Lex Fridman (58:31.340)
could always, you know, if it had no limits of time and memory,
Scott Aaronson (58:35.500)
it could always just store the entire quantum state,
Lex Fridman (58:39.180)
you know, of your, you know, of the quantum,
Scott Aaronson (58:41.420)
store a list of all the amplitudes,
Lex Fridman (58:44.780)
you know, in the state of the quantum computer,
Lex Fridman (58:47.260)
and then just, you know, do some linear algebra
Lex Fridman (58:50.060)
to just update that state, right?
Lex Fridman (58:52.140)
And so anything that quantum computers can do
Lex Fridman (58:55.420)
can also be done by classical computers,
Scott Aaronson (58:58.300)
albeit exponentially slower in some cases.
Lex Fridman (59:00.620)
So quantum computers don't go into some magical place
Scott Aaronson (59:03.740)
outside of Alan Turing's definition of computation.
Lex Fridman (59:06.620)
Precisely.
Scott Aaronson (59:07.420)
They do not solve the halting problem.
Lex Fridman (59:09.900)
They cannot solve anything that is uncomputable
Scott Aaronson (59:12.620)
in Alan Turing's sense.
Lex Fridman (59:14.300)
What we think they do change
Lex Fridman (59:16.620)
is what is efficiently computable, okay?
Lex Fridman (59:19.260)
And, you know, since the 1960s, you know,
Scott Aaronson (59:22.220)
the word efficiently, you know,
Lex Fridman (59:23.980)
as well has been a central word in computer science,
Lex Fridman (59:26.780)
but it's sort of a code word for something technical,
Lex Fridman (59:29.900)
which is basically with polynomial scaling, you know,
Scott Aaronson (59:33.740)
that as you get to larger and larger inputs,
Lex Fridman (59:36.700)
you would like an algorithm that uses an amount of time
Scott Aaronson (59:39.580)
that scales only like the size of the input
Lex Fridman (59:42.220)
raised to some power
Lex Fridman (59:43.740)
and not exponentially with the size of the input, right?
Lex Fridman (59:47.180)
Yeah, so I do hope we get to talk again
Scott Aaronson (59:49.740)
because one of the many topics
Lex Fridman (59:52.540)
that there's probably several hours worth of conversation on
Scott Aaronson (59:55.820)
is complexity,
Lex Fridman (59:56.620)
which we probably won't even get a chance to touch today,
🔗 相关节目