back to indexScott Aaronson: Quantum Computing | Lex Fridman Podcast #72
link |
The following is a conversation with Scott Aaronson,
link |
a professor at UT Austin,
link |
director of its Quantum Information Center,
link |
and previously a professor at MIT.
link |
His research interests center
link |
around the capabilities and limits of quantum computers
link |
and computational complexity theory more generally.
link |
He is an excellent writer
link |
and one of my favorite communicators
link |
of computer science in the world.
link |
We only had about an hour and a half of this conversation,
link |
so I decided to focus on quantum computing.
link |
But I can see us talking again in the future
link |
on this podcast at some point
link |
about computational complexity theory
link |
and all the complexity classes that Scott catalogs
link |
in his amazing Complexity Zoo Wiki.
link |
based on questions and comments I've received,
link |
my goal with these conversations
link |
is to try to be in the background without ego
link |
and do three things.
link |
One, let the guests shine
link |
and try to discover together
link |
the most beautiful insights in their work
link |
and in their mind.
link |
Two, try to play devil's advocate
link |
just enough to provide a creative tension
link |
in exploring ideas through conversation.
link |
And three, to ask very basic questions
link |
about terminology, about concepts, about ideas.
link |
Many of the topics we talk about in the podcast
link |
I've been studying for years
link |
as a grad student, as a researcher,
link |
and generally as a curious human who loves to read.
link |
But frankly, I see myself in these conversations
link |
as the main character
link |
for one of my favorite novels by Dostoevsky
link |
I enjoy playing dumb.
link |
Clearly, it comes naturally.
link |
But the basic questions
link |
don't come from my ignorance of the subject
link |
but from an instinct that the fundamentals are simple.
link |
And if we linger on them
link |
from almost a naive perspective,
link |
we can draw an insightful thread
link |
from computer science to neuroscience
link |
to physics to philosophy
link |
and to artificial intelligence.
link |
This is the Artificial Intelligence Podcast.
link |
If you enjoy it, subscribe on YouTube,
link |
give it five stars on Apple Podcast,
link |
support it on Patreon,
link |
or simply connect with me on Twitter
link |
at Lex Friedman, spelled F R I D M A N.
link |
As usual, I'll do one or two minutes of ads now
link |
and never any ads in the middle
link |
that can break the flow of the conversation.
link |
I hope that works for you
link |
and doesn't hurt the listening experience.
link |
Quick summary of the ads.
link |
Two supporters today.
link |
First, get Cash App and use the code LEX PODCAST.
link |
Second, listen to the Tech Meme Ride Home podcast
link |
Search Ride Home, two words, in your podcast app.
link |
This show is presented by Cash App,
link |
the number one finance app in the App Store.
link |
When you get it, use code LEX PODCAST.
link |
Cash App lets you send money to friends,
link |
buy Bitcoin, and invest in the stock market
link |
with as little as one dollar.
link |
Broker services are provided by Cash App Investing,
link |
a subsidiary of Square, a member SIPC.
link |
Since Cash App does fractional share trading,
link |
let me mention that the order execution algorithm
link |
that works behind the scenes
link |
to create the abstraction of fractional orders
link |
is an algorithmic marvel.
link |
So big props to the Cash App engineers
link |
for solving a hard problem that in the end
link |
provides an easy interface that takes a step up
link |
to the next layer of abstraction over the stock market,
link |
making trading more accessible for new investors
link |
and diversification much easier.
link |
So again, if you get Cash App from the App Store
link |
or Google Play and use the code LEX PODCAST,
link |
you'll get $10 and Cash App will also donate $10 to FIRST,
link |
one of my favorite organizations
link |
that is helping to advance robotics and STEM education
link |
for young people around the world.
link |
This episode is also supported
link |
by the Tech Meme Ride Home Podcast.
link |
It's a technology podcast I've been listening to
link |
for a while and really enjoying.
link |
It goes straight to the point,
link |
gives you the tech news you need to know
link |
and provides minimal but essential context.
link |
It's released every day by 5 p.m. Eastern
link |
and is only about 15 to 20 minutes long.
link |
For fun, I like building apps on smartphones,
link |
most on Android, so I'm always a little curious
link |
about new flagship phones that come out.
link |
I saw that Samsung announced the new Galaxy S20
link |
and of course, right away, Tech Meme Ride Home
link |
has a new episode that summarizes all that I needed to know
link |
about this new device.
link |
They've also started to do weekend bonus episodes
link |
with interviews of people like AWOL founder Steve Case
link |
on investing and Gary Marcus on AI,
link |
who I've also interviewed on this podcast.
link |
You can find the Tech Meme Ride Home Podcast
link |
if you search your podcast app for Ride Home, two words.
link |
Then subscribe, enjoy, and keep up to date
link |
with the latest tech news.
link |
And now, here's my conversation with Scott Aaronson.
link |
I sometimes get criticism from a listener here and there
link |
that while having a conversation
link |
with a world class mathematician, physicist,
link |
neurobiologist, aerospace engineer,
link |
or a theoretical computer scientist like yourself,
link |
I waste time by asking philosophical questions
link |
about free will, consciousness, mortality, love,
link |
nature of truth, super intelligence,
link |
whether time travel is possible,
link |
whether space time is emergent and fundamental,
link |
even the crazier questions like whether aliens exist,
link |
what their language might look like,
link |
what their math might look like,
link |
whether math is invented or discovered,
link |
and of course, whether we live in a simulation or not.
link |
I try to dance back and forth from the deep technical
link |
to the philosophical, so I've done that quite a bit.
link |
So you're a world class computer scientist,
link |
and yet you've written about this very point,
link |
the philosophy is important for experts
link |
in any technical discipline,
link |
though they somehow seem to avoid this.
link |
So I thought it'd be really interesting
link |
to talk to you about this point.
link |
Why should we computer scientists, mathematicians,
link |
physicists care about philosophy, do you think?
link |
Well, I would reframe the question a little bit.
link |
I mean, philosophy almost by definition
link |
is the subject that's concerned with the biggest questions
link |
that you could possibly ask, right?
link |
So the ones you mentioned, right?
link |
Are we living in a simulation?
link |
Are we alone in the universe?
link |
How should we even think about such questions?
link |
Is the future determined,
link |
and what do we even mean by it being determined?
link |
Why are we alive at the time we are
link |
and not at some other time?
link |
And when you sort of contemplate
link |
the enormity of those questions,
link |
I think you could ask,
link |
well, then why be concerned with anything else, right?
link |
Why not spend your whole life on those questions?
link |
I think in some sense,
link |
that is the right way to phrase the question.
link |
And actually, what we learned, I mean, throughout history,
link |
but really starting with the scientific revolution
link |
with Galileo and so on,
link |
is that there is a good reason to focus
link |
on narrower questions, more technical,
link |
mathematical or empirical questions.
link |
And that is that you can actually make progress on them,
link |
and you can actually often answer them.
link |
And sometimes they actually tell you something
link |
about the philosophical questions
link |
that sort of maybe motivated your curiosity as a child.
link |
They don't necessarily resolve the philosophical questions,
link |
but sometimes they reframe
link |
your whole understanding of them, right?
link |
And so for me, philosophy is just the thing
link |
that you have in the background from the very beginning
link |
that you want to, these are sort of the reasons
link |
why you went into intellectual life in the first place,
link |
at least the reasons why I did, right?
link |
But math and science are tools that we have
link |
for actually making progress.
link |
And hopefully even changing our understanding
link |
of these philosophical questions,
link |
sometimes even more than philosophy itself does.
link |
Why do you think computer scientists avoid these questions?
link |
We'll run away from them a little bit,
link |
at least in a technical scientific discourse.
link |
Well, I'm not sure if they do so
link |
more than any other scientists do.
link |
I mean, Alan Turing was famously interested
link |
and his most famous, one of his two most famous papers
link |
was in a philosophy journal mind.
link |
It was the one where he proposed the Turing test.
link |
He took a Wittgenstein's course at Cambridge,
link |
I just recently learned that little bit
link |
and it's actually fascinating.
link |
I was trying to look for resources
link |
in trying to understand where the sources of disagreement
link |
and debates between Wittgenstein and Turing were.
link |
That's interesting that these two minds
link |
have somehow met in the arc of history.
link |
Yeah, well, the transcript of the course,
link |
which was in 1939, right,
link |
is one of the more fascinating documents that I've ever read
link |
because Wittgenstein is trying to say,
link |
well, all of these formal systems
link |
are just complete irrelevancies, right?
link |
If a formal system is irrelevant, who cares?
link |
Why does that matter in real life, right?
link |
And Turing is saying, well, look,
link |
if you use an inconsistent formal system to design a bridge,
link |
the bridge may collapse, right?
link |
And so Turing, in some sense, is thinking decades ahead,
link |
you know, I think, of where Wittgenstein is,
link |
to where the formal systems are actually going to be used
link |
in computers, right, to actually do things in the world.
link |
You know, and it's interesting that Turing
link |
actually dropped the course halfway through.
link |
Because he had to go to Bletchley Park
link |
and work on something of more immediate importance.
link |
That's fascinating.
link |
Take a step from philosophy to actual,
link |
like the biggest possible step to actual engineering
link |
with actual real impact.
link |
Yeah, and I would say more generally, right,
link |
a lot of scientists are interested in philosophy,
link |
but they're also busy, right?
link |
And they have a lot on their plate,
link |
and there are a lot of sort of very concrete questions
link |
that are already not answered,
link |
but look like they might be answerable, right?
link |
And so then you could say, well, then why break your brain
link |
over these metaphysically unanswerable questions
link |
when there were all of these answerable ones instead?
link |
So I think, you know, for me,
link |
I enjoy talking about philosophy.
link |
I even go to philosophy conferences sometimes,
link |
such as the FQXI conferences.
link |
I enjoy interacting with philosophers.
link |
I would not want to be a professional philosopher
link |
because I like being in a field where I feel like,
link |
you know, if I get too confused
link |
about the sort of eternal questions,
link |
then I can actually make progress on something.
link |
Can you maybe link on that for just a little longer?
link |
What do you think is the difference?
link |
So like the corollary of the criticism
link |
that I mentioned previously,
link |
that why ask the philosophical questions
link |
of the mathematician is if you want
link |
to ask philosophical questions,
link |
then invite a real philosopher on and ask them.
link |
So what's the difference between the way
link |
a computer scientist or mathematician
link |
ponders a philosophical question
link |
and a philosopher ponders a philosophical question?
link |
Well, I mean, a lot of it just depends
link |
on the individual, right?
link |
It's hard to make generalizations about entire fields,
link |
but, you know, I think if we tried to,
link |
if we tried to stereotype, you know,
link |
we would say that scientists very often
link |
will be less careful in their use of words.
link |
You know, I mean, philosophers are really experts
link |
in sort of, you know, like when I talk to them,
link |
they will just pounce if I, you know,
link |
use the wrong phrase for something.
link |
Experts is a very nice word.
link |
You could say sticklers.
link |
Sticklers, yeah, yeah, yeah, or, you know,
link |
they will sort of interrogate my word choices,
link |
let's say, to a much greater extent
link |
than scientists would, right?
link |
And scientists, you know, will often,
link |
if you ask them about a philosophical problem,
link |
like the hard problem of consciousness
link |
or free will or whatever,
link |
they will try to relate it back to, you know,
link |
recent research, you know, research about neurobiology
link |
or, you know, the best of all is research
link |
that they personally are involved with, right?
link |
And, you know, of course they will want to talk about that,
link |
you know, and it is what they will think of, you know,
link |
and of course you could have an argument
link |
that maybe, you know, it's all interesting as it goes,
link |
but maybe none of it touches the philosophical question,
link |
But, you know, but maybe, you know, a science,
link |
you know, at least it, as I said,
link |
it does tell us concrete things.
link |
And, you know, even if like a deep dive into neurobiology
link |
will not answer the hard problem of consciousness,
link |
you know, maybe it can take us about as far as we can get
link |
toward, you know, expanding our minds about it,
link |
you know, toward thinking about it in a different way.
link |
Well, I mean, I think neurobiology can do that,
link |
but, you know, with these profound philosophical questions,
link |
I mean, also art and literature do that, right?
link |
They're all different ways
link |
of trying to approach these questions that, you know,
link |
we don't, for which we don't even know really
link |
what an answer would look like,
link |
but, and yet somehow we can't help,
link |
but keep returning to the questions.
link |
And you have a kind of mathematical,
link |
beautiful mathematical way of discussing this
link |
with the idea of Q prime.
link |
You write that usually the only way to make progress
link |
on the big questions, like the philosophical questions
link |
we're talking about now is to pick off smaller sub questions.
link |
Ideally sub questions that you can attack
link |
using math, empirical observation, or both.
link |
You define the idea of a Q prime.
link |
So given an unanswerable philosophical riddle Q,
link |
replace it with a merely, in quotes, scientific
link |
or mathematical question Q prime,
link |
which captures part of what people have wanted to know
link |
when they first asked Q.
link |
Then with luck, one solves Q prime.
link |
So you described some examples of such Q prime sub questions
link |
in your long essay titled,
link |
Why Philosophers Should Care About Computational Complexity.
link |
So you catalog the various Q primes
link |
on which you think theoretical computer science
link |
has made progress.
link |
Can you mention a few favorites, if any pop to mind,
link |
or do you remember some?
link |
So, I mean, I would say some of the most famous examples
link |
in history of that sort of replacement were,
link |
I mean, to go back to Alan Turing, right?
link |
What he did in his computing machinery
link |
and intelligence paper was exactly,
link |
he explicitly started with the question,
link |
can machines think?
link |
And then he said, sorry,
link |
I think that question is too meaningless,
link |
but here's a different question.
link |
Could you program a computer
link |
so that you couldn't tell the difference
link |
between it and a human, right?
link |
So in the very first few sentences,
link |
he in fact just formulates the Q prime question.
link |
He does precisely that.
link |
Or we could look at Gödel, right?
link |
Where you had these philosophers arguing for centuries
link |
about the limits of mathematical reasoning, right?
link |
The limits of formal systems.
link |
And then by the early 20th century,
link |
logicians, starting with Frege, Russell,
link |
and then most spectacularly Gödel,
link |
managed to reframe those questions as,
link |
look, we have these formal systems.
link |
They have these definite rules.
link |
Are there questions that we can phrase
link |
within the rules of these systems
link |
that are not provable within the rules of the systems?
link |
And can we prove that fact, right?
link |
And so that would be another example.
link |
You know, I had this essay called
link |
The Ghost in the Quantum Turing Machine.
link |
That was one of the crazier things I've written,
link |
but I tried to do something,
link |
or to advocate doing something similar there for free will,
link |
where instead of talking about is free will real,
link |
where we get hung up on the meaning of,
link |
what exactly do we mean by freedom?
link |
And can you have, can you be,
link |
or do we mean compatibilist free will,
link |
libertarian free will?
link |
What do these things mean?
link |
You know, I suggested just asking the question,
link |
how well in principle, consistently with the laws of physics,
link |
could a person's behavior be predicted?
link |
You know, without, so let's say,
link |
destroying the person's brain, you know,
link |
taking it apart in the process of trying to predict them.
link |
And, you know, and that actually,
link |
asking that question gets you into all sorts of meaty
link |
and interesting issues, you know, issues of,
link |
what is the computational substrate of the brain?
link |
You know, or can you understand the brain, you know,
link |
just at the sort of level of the neurons, you know,
link |
at sort of the abstraction of a neural network,
link |
or do you need to go deeper to the, you know,
link |
molecular level and ultimately even to the quantum level?
link |
Right, and of course,
link |
that would put limits on predictability if you did.
link |
So you need to reduce,
link |
you need to reduce the mind to a computational device,
link |
like formalize it so then you can make predictions
link |
about what, you know, whether you could predict the behavior
link |
of the system. Well, if you were trying
link |
to predict a person, yeah, then presumably,
link |
you would need some model of their brain, right?
link |
And now the question becomes one of,
link |
how accurate can such a model become?
link |
Can you make a model that will be accurate enough
link |
to really seriously threaten people's sense of free will?
link |
You know, not just metaphysically, but like really,
link |
I have written in this envelope
link |
what you were going to say next.
link |
Is accuracy the right term here?
link |
So it's also a level of abstraction has to be right.
link |
So if you're accurate at the, somehow at the quantum level,
link |
that may not be convincing to us at the human level.
link |
Well, right, but the question is what accuracy
link |
at the sort of level of the underlying mechanisms
link |
do you need in order to predict the behavior, right?
link |
At the end of the day, the test is just,
link |
can you, you know, foresee what the person is going to do?
link |
Right, I am, you know, and in discussions of free will,
link |
you know, it seems like both sides wanna, you know,
link |
very quickly dismiss that question as irrelevant.
link |
Well, to me, it's totally relevant.
link |
Okay, because, you know, if someone says,
link |
oh, well, you know, a Laplace demon
link |
that knew the complete state of the universe,
link |
you know, could predict everything you're going to do,
link |
therefore you don't have free will.
link |
You know, it doesn't trouble me that much because,
link |
well, you know, I've never met such a demon, right?
link |
You know, and we, you know, we even have some reasons
link |
to think, you know, maybe, you know,
link |
it could not exist as part of our world,
link |
you know, it's only an abstraction, a thought experiment.
link |
On the other hand, if someone said,
link |
well, you know, I have this brain scanning machine,
link |
you know, you step into it and then, you know,
link |
every paper that you will ever write, it will write,
link |
you know, every thought that you will have, you know,
link |
even right now about the machine itself, it will foresee.
link |
You know, well, if you can actually demonstrate that,
link |
then I think, you know, that sort of threatens
link |
my internal sense of having free will
link |
in a much more visceral way.
link |
You know, but now you notice that we're asking
link |
a much more empirical question.
link |
We're asking, is such a machine possible or isn't it?
link |
We're asking, if it's not possible,
link |
then what in the laws of physics
link |
or what about the behavior of the brain,
link |
you know, prevents it from existing?
link |
So if you could philosophize a little bit
link |
within this empirical question,
link |
where do you think would enter the,
link |
by which mechanism would enter the possibility
link |
that we can't predict the outcome?
link |
So there would be something
link |
that would be akin to a free will.
link |
Yeah, well, you could say the sort of obvious possibility,
link |
which was, you know, recognized by Eddington
link |
and many others about as soon as quantum mechanics
link |
was discovered in the 1920s, was that if,
link |
you know, let's say a sodium ion channel,
link |
you know, in the brain, right?
link |
You know, its behavior is chaotic, right?
link |
It's sort of, it's governed by these
link |
Hodgley–Huckskin equations in neuroscience, right?
link |
Which are differential equations
link |
that have a stochastic component, right?
link |
Now, where does, you know, and this ultimately governs,
link |
let's say whether a neuron will fire or not fire, right?
link |
So that's the basic chemical process
link |
or electrical process by which signals
link |
are sent in the brain.
link |
And, you know, and so you could ask,
link |
well, where does the randomness in the process,
link |
you know, that neuroscientists,
link |
or what neuroscientists would treat as randomness,
link |
where does it come from?
link |
You know, ultimately it's thermal noise, right?
link |
Where does thermal noise come from?
link |
But ultimately, you know,
link |
there were some quantum mechanical events
link |
at the molecular level
link |
that are getting sort of chaotically amplified
link |
by, you know, a sort of butterfly effect.
link |
And so, you know, even if you knew
link |
the complete quantum state of someone's brain,
link |
you know, at best you could predict the probabilities
link |
that they would do one thing or do another thing, right?
link |
I think that part is actually relatively uncontroversial,
link |
The controversial question is whether any of it matters
link |
for the sort of philosophical questions that we care about.
link |
Because you could say, if all it's doing
link |
is just injecting some randomness
link |
into an otherwise completely mechanistic process,
link |
well, then who cares, right?
link |
And more concretely, if you could build a machine
link |
that, you know, could just calculate
link |
even just the probabilities
link |
of all of the possible things that you would do, right?
link |
And, you know, of all the things that said
link |
you had a 10% chance of doing,
link |
you did exactly a 10th of them, you know,
link |
and so on and so on.
link |
And that somehow also takes away the feeling of free will.
link |
I mean, to me, it seems essentially just as bad
link |
as if the machine deterministically predicted you.
link |
It seems, you know, hardly different from that.
link |
So then, but a more subtle question
link |
is could you even learn enough
link |
about someone's brain to do that, okay?
link |
Because, you know, another central fact
link |
about quantum mechanics is that making a measurement
link |
on a quantum state is an inherently destructive operation.
link |
Okay, so, you know, if I want to measure the, you know,
link |
position of a particle, right?
link |
It was, well, before I measured,
link |
it had a superposition over many different positions.
link |
As soon as I measure, I localize it, right?
link |
So now I know the position,
link |
but I've also fundamentally changed the state.
link |
And so you could say, well, maybe in trying to build
link |
a model of someone's brain that was accurate enough
link |
to actually, you know, make, let's say,
link |
even well calibrated probabilistic predictions
link |
of their future behavior,
link |
maybe you would have to make measurements
link |
that were just so accurate
link |
that you would just fundamentally alter their brain, okay?
link |
Or maybe not, maybe you only, you know,
link |
it would suffice to just make some nanorobots
link |
that just measured some sort of much larger scale,
link |
you know, macroscopic behavior, like, you know,
link |
what is this neuron doing?
link |
What is that neuron doing?
link |
Maybe that would be enough.
link |
See, but now, you know, what I claim is that
link |
we're now asking a question, you know,
link |
in which, you know, it is possible to envision
link |
what progress on it would look like.
link |
Yeah, but just as you said,
link |
that question may be slightly detached
link |
from the philosophical question in the sense
link |
if consciousness somehow has a role
link |
to the experience of free will.
link |
Because ultimately, when we're talking about free will,
link |
we're also talking about not just the predictability
link |
of our actions, but somehow the experience
link |
of that predictability.
link |
Yeah, well, I mean, a lot of philosophical questions
link |
ultimately, like, feedback to the hard problem
link |
of consciousness, you know,
link |
and as much as you can try to sort of talk around it
link |
And, you know, and there is a reason
link |
why people try to talk around it,
link |
which is that, you know,
link |
Democritus talked about the hard problem of consciousness,
link |
you know, in 400 BC in terms that would be
link |
totally recognizable to us today, right?
link |
And it's really not clear if there's been progress since
link |
or what progress could possibly consist of.
link |
Is there a Q prime type of subquestion
link |
that could help us get at consciousness?
link |
It's something about consciousness.
link |
Well, I mean, well, I mean, there is the whole question
link |
of, you know, of AI, right?
link |
Of, you know, can you build a human level
link |
or superhuman level AI?
link |
And, you know, can it work in a completely different
link |
substrate from the brain?
link |
I mean, you know, and of course,
link |
that was Alan Turing's point.
link |
And, you know, and even if that was done,
link |
it's, you know, maybe people would still argue
link |
about the hard problem of consciousness, right?
link |
And yet, you know, my claim is a little different.
link |
My claim is that in a world where, you know,
link |
there were, you know, human level AIs
link |
or we'd been even overtaken by such AIs,
link |
the entire discussion of the hard problem of consciousness
link |
would have a different character, right?
link |
It would take place in different terms in such a world,
link |
even if we hadn't answered the question.
link |
And my claim about free will would be similar, right?
link |
That if this prediction machine that I was talking about
link |
could actually be built, well, now the entire discussion
link |
of the, you know, of free will is sort of transformed
link |
by that, you know, even if in some sense
link |
the metaphysical question hasn't been answered.
link |
Yeah, exactly, it transforms it fundamentally
link |
because say that machine does tell you
link |
that it can predict perfectly
link |
and yet there is this deep experience of free will
link |
and then that changes the question completely.
link |
And it starts actually getting to the question
link |
of the AGI, the touring questions
link |
of the demonstration of free will,
link |
the demonstration of intelligence,
link |
the demonstration of consciousness,
link |
does that equal consciousness, intelligence and free will?
link |
But see, Alex, if every time I was contemplating a decision,
link |
you know, this machine had printed out an envelope,
link |
you know, where I could open it
link |
and see that it knew my decision,
link |
I think that actually would change
link |
my subjective experience of making decisions, right?
link |
Does knowledge change your subjective experience?
link |
Well, you know, I mean, the knowledge
link |
that this machine had predicted everything I would do,
link |
I mean, it might drive me completely insane, right?
link |
But at any rate, it would change my experience
link |
to act, you know, to not just discuss such a machine
link |
as a thought experiment, but to actually see it.
link |
I mean, you know, you could say at that point,
link |
you know, you could say, you know,
link |
why not simply call this machine
link |
a second instantiation of me and be done with it, right?
link |
What, you know, why even privilege the original me
link |
over this perfect duplicate that exists in the machine?
link |
Yeah, or there could be a religious experience with it too.
link |
It's kind of what God throughout the generations
link |
is supposed to have.
link |
That God kind of represents that perfect machine,
link |
is able to, I guess, actually,
link |
well, I don't even know what are the religious
link |
interpretations of free will.
link |
So if God knows perfectly everything in religion,
link |
in the various religions,
link |
where does free will fit into that?
link |
That has been one of the big things that theologians
link |
have argued about for thousands of years.
link |
You know, I am not a theologian,
link |
so maybe I shouldn't go there.
link |
So there's not a clear answer in a book like...
link |
I mean, this is, you know, the Calvinists debated this,
link |
the, you know, this has been, you know,
link |
I mean, different religious movements
link |
have taken different positions on that question,
link |
but that is how they think about it.
link |
You know, meanwhile, you know,
link |
a large part of sort of what animates,
link |
you know, theoretical computer science,
link |
you could say is, you know, we're asking sort of,
link |
what are the ultimate limits of, you know,
link |
what you can know or, you know, calculate or figure out
link |
by, you know, entities that you can actually build
link |
in the physical world, right?
link |
And if I were trying to explain it to a theologian,
link |
maybe I would say, you know, we are studying, you know,
link |
to what extent, you know,
link |
gods can be made manifest in the physical world.
link |
I'm not sure my colleagues would like that.
link |
So let's talk about quantum computers for a second.
link |
As you've said, quantum computing,
link |
at least in the 1990s, was a profound story
link |
at the intersection of computer science,
link |
physics, engineering, math, and philosophy.
link |
So there's this broad and deep aspect to quantum computing
link |
that represents more than just the quantum computer.
link |
But can we start at the very basics?
link |
What is quantum computing?
link |
Yeah, so it's a proposal for a new type of computation,
link |
or let's say a new way to harness nature to do computation
link |
that is based on the principles of quantum mechanics.
link |
Okay, now the principles of quantum mechanics
link |
have been in place since 1926.
link |
You know, they haven't changed.
link |
You know, what's new is, you know, how we wanna use them.
link |
Okay, so what does quantum mechanics say about the world?
link |
You know, the physicists, I think, over the generations,
link |
you know, convinced people
link |
that that is an unbelievably complicated question
link |
and, you know, just give up on trying to understand it.
link |
I can let you in, not being a physicist,
link |
I can let you in on a secret,
link |
which is that it becomes a lot simpler
link |
if you do what we do in quantum information theory
link |
and sort of take the physics out of it.
link |
So the way that we think about quantum mechanics
link |
is sort of as a generalization
link |
of the rules of probability themselves.
link |
So, you know, you might say there was a 30% chance
link |
that it was going to snow today or something.
link |
You would never say that there was a negative 30% chance,
link |
right, that would be nonsense.
link |
Much less would you say that there was, you know,
link |
an I% chance, you know, square root of minus 1% chance.
link |
Now, the central discovery
link |
that sort of quantum mechanics made
link |
is that fundamentally the world is described by,
link |
or, you know, the sort of, let's say the possibilities
link |
for, you know, what a system could be doing
link |
are described using numbers called amplitudes, okay,
link |
which are like probabilities in some ways,
link |
but they are not probabilities.
link |
They can be positive.
link |
For one thing, they can be positive or negative.
link |
In fact, they can even be complex numbers.
link |
Okay, and if you've heard of a quantum superposition,
link |
this just means some state of affairs
link |
where you assign an amplitude,
link |
one of these complex numbers,
link |
to every possible configuration
link |
that you could see a system in on measuring it.
link |
So for example, you might say that an electron
link |
has some amplitude for being here
link |
and some other amplitude for being there, right?
link |
Now, if you look to see where it is,
link |
you will localize it, right?
link |
You will sort of force the amplitudes
link |
to be converted into probabilities.
link |
That happens by taking their squared absolute value, okay,
link |
and then, you know, you can say
link |
either the electron will be here or it will be there.
link |
And, you know, knowing the amplitudes,
link |
you can predict at least the probabilities
link |
that you'll see each possible outcome, okay?
link |
But while a system is isolated
link |
from the whole rest of the universe,
link |
the rest of its environment,
link |
the amplitudes can change in time
link |
by rules that are different
link |
from the normal rules of probability
link |
and that are, you know, alien to our everyday experience.
link |
So anytime anyone ever tells you anything
link |
about the weirdness of the quantum world,
link |
you know, or assuming that they're not lying to you, right,
link |
they are telling you, you know,
link |
yet another consequence of nature
link |
being described by these amplitudes.
link |
So most famously, what amplitudes can do
link |
is that they can interfere with each other, okay?
link |
So in the famous double slit experiment,
link |
what happens is that you shoot a particle,
link |
like an electron, let's say,
link |
at a screen with two slits in it,
link |
and you find that there are, you know, on a second screen,
link |
now there are certain places
link |
where that electron will never end up,
link |
you know, after it passes through the first screen.
link |
And yet, if I close off one of the slits,
link |
then the electron can appear in that place, okay?
link |
So by decreasing the number of paths
link |
that the electron could take to get somewhere,
link |
you can increase the chance that it gets there, okay?
link |
Now, how is that possible?
link |
Well, it's because, you know, as we would say now,
link |
the electron has a superposition state, okay?
link |
It has some amplitude for reaching this point
link |
by going through the first slit.
link |
It has some other amplitude for reaching it
link |
by going through the second slit.
link |
But now, if one amplitude is positive
link |
and the other one is negative,
link |
then, you know, I have to add them all up, right?
link |
I have to add the amplitudes for every path
link |
that the electron could have taken to reach this point.
link |
And those amplitudes,
link |
if they're pointing in different directions,
link |
they can cancel each other out.
link |
That would mean the total amplitude is zero
link |
and the thing never happens at all.
link |
I close off one of the possibilities,
link |
then the amplitude is positive or it's negative,
link |
and now the thing can happen.
link |
Okay, so that is sort of the one trick of quantum mechanics.
link |
And now I can tell you what a quantum computer is.
link |
Okay, a quantum computer is a computer
link |
that tries to exploit, you know, exactly these phenomena,
link |
superposition, amplitudes, and interference,
link |
in order to solve certain problems much faster
link |
than we know how to solve them otherwise.
link |
So the basic building block of a quantum computer
link |
is what we call a quantum bit or a qubit.
link |
That just means a bit that has some amplitude for being zero
link |
and some other amplitude for being one.
link |
So it's a superposition of zero and one states, right?
link |
But now the key point is that if I've got,
link |
let's say, a thousand qubits,
link |
the rules of quantum mechanics are completely unequivocal
link |
that I do not just need one ampli...
link |
You know, I don't just need amplitudes for each qubit separately.
link |
Okay, in general, I need an amplitude
link |
for every possible setting of all thousand of those bits, okay?
link |
So that what that means is two to the one thousand power amplitudes.
link |
Okay, if I had to write those down,
link |
or let's say in the memory of a conventional computer,
link |
if I had to write down two to the one thousand complex numbers,
link |
that would not fit within the entire observable universe.
link |
Okay, and yet, you know, quantum mechanics is unequivocal
link |
that if these qubits can all interact with each other,
link |
and in some sense, I need two to the one thousand parameters,
link |
you know, amplitudes to describe what is going on.
link |
Now, you know, now I can tell, you know, where all the popular articles,
link |
you know, about quantum computing go off the rails
link |
is that they say, you know, they sort of say what I just said,
link |
and then they say, oh, so the way a quantum computer works
link |
is just by trying every possible answer in parallel.
link |
You know, that sounds too good to be true,
link |
and unfortunately, it kind of is too good to be true.
link |
The problem is I could make a superposition
link |
over every possible answer to my problem, you know,
link |
even if there are two to the one thousand of them, right?
link |
I can easily do that.
link |
The trouble is for a computer to be useful,
link |
you've got to, at some point, you've got to look at it
link |
and see an output, right?
link |
And if I just measure a superposition over every possible answer,
link |
then the rules of quantum mechanics tell me
link |
that all I'll see will be a random answer.
link |
You know, if I just wanted a random answer,
link |
well, I could have picked one myself with a lot less trouble, right?
link |
So the entire trick with quantum computing,
link |
with every algorithm for a quantum computer,
link |
is that you try to choreograph a pattern
link |
of interference of amplitudes,
link |
and you try to do it so that for each wrong answer,
link |
some of the paths leading to that wrong answer
link |
have positive amplitudes and others have negative amplitudes.
link |
So on the whole, they cancel each other out, okay?
link |
Whereas all the paths leading to the right answer
link |
should reinforce each other, you know, should have amplitudes
link |
pointing the same direction.
link |
So the design of algorithms in the space
link |
is the choreography of the interferences.
link |
Precisely. That's precisely what it is.
link |
Can we take a brief step back?
link |
And you mentioned information.
link |
So in which part of this beautiful picture
link |
that you've painted is information contained?
link |
Oh, well, information is at the core of everything
link |
that we've been talking about, right?
link |
I mean, the bit is, you know, the basic unit of information
link |
since, you know, Claude Shannon's paper in 1948.
link |
You know, and, you know, of course, you know,
link |
people had the concept even before that, you know,
link |
he popularized the name, right?
link |
But a bit is zero or one.
link |
So that's a basic element of information.
link |
And what we would say is that the basic unit
link |
of quantum information is the qubit,
link |
is, you know, the object, any object
link |
that can be maintained in this, or manipulated,
link |
in a superposition of zero and one states.
link |
Now, you know, sometimes people ask, well,
link |
but what is a qubit physically, right?
link |
And there are all these different, you know,
link |
proposals that are being pursued in parallel
link |
for how you implement qubits.
link |
There is, you know, superconducting quantum computing
link |
that was in the news recently
link |
because of Google's quantum supremacy experiment, right?
link |
Where you would have some little coils
link |
where a current can flow through them
link |
in two different energy states,
link |
one representing a zero, another representing a one.
link |
And if you cool these coils
link |
to just slightly above absolute zero,
link |
like a hundredth of a degree, then they superconduct.
link |
And then the current can actually be
link |
in a superposition of the two different states.
link |
So that's one kind of qubit.
link |
Another kind would be, you know,
link |
just an individual atomic nucleus, right?
link |
It could be spinning clockwise.
link |
It could be spinning counterclockwise,
link |
or it could be in a superposition of the two spin states.
link |
That is another qubit.
link |
But see, just like in the classical world, right?
link |
You could be a virtuoso programmer
link |
without having any idea of what a transistor is, right?
link |
Or how the bits are physically represented inside the machine,
link |
even that the machine uses electricity, right?
link |
You just care about the logic.
link |
It's sort of the same with quantum computing, right?
link |
Qubits could be realized by many,
link |
many different quantum systems.
link |
And yet all of those systems will lead to the same logic,
link |
you know, the logic of qubits and how, you know,
link |
how you measure them, how you change them over time.
link |
And so, you know, the subject of, you know,
link |
how qubits behave and what you can do with qubits,
link |
that is quantum information.
link |
So just to linger on that.
link |
So the physical design implementation of a qubit
link |
does not interfere with the,
link |
that next level of abstraction that you can program over it.
link |
So it truly is, the idea of it is, okay.
link |
Well, to be honest with you,
link |
today they do interfere with each other.
link |
That's because all the quantum computers
link |
we can build today are very noisy, right?
link |
And so sort of the, you know,
link |
the qubits are very far from perfect.
link |
And so the lower level sort of does affect the higher levels.
link |
And we sort of have to think about all of them at once.
link |
Okay, but eventually where we hope to get
link |
is to what are called error corrected quantum computers,
link |
where the qubits really do behave
link |
like perfect abstract qubits for as long as we want them to.
link |
And in that future, you know,
link |
a future that we can already sort of prove theorems about
link |
or think about today.
link |
But in that future, the logic of it
link |
really does become decoupled from the hardware.
link |
So if noise is currently like the biggest problem
link |
for quantum computing,
link |
and then the dream is error correcting quantum computers,
link |
can you just maybe describe what does it mean
link |
for there to be noise in the system?
link |
Absolutely, so yeah, so the problem
link |
is even a little more specific than noise.
link |
So the fundamental problem,
link |
if you're trying to actually build a quantum computer,
link |
you know, of any appreciable size,
link |
is something called decoherence.
link |
Okay, and this was recognized from the very beginning,
link |
you know, when people first started thinking about this
link |
Now, what decoherence means
link |
is sort of the unwanted interaction
link |
between, you know, your qubits,
link |
you know, the state of your quantum computer
link |
and the external environment.
link |
Okay, and why is that such a problem?
link |
Well, I talked before about how, you know,
link |
when you measure a quantum system,
link |
so let's say if I measure a qubit
link |
that's in a superposition of zero and one states
link |
to ask it, you know, are you zero or are you one?
link |
Well, now I force it to make up its mind, right?
link |
And now, probabilistically, it chooses one or the other
link |
and now, you know, it's no longer a superposition,
link |
there's no longer amplitudes,
link |
there's just, there's some probability that I get a zero
link |
and there's some that I get a one.
link |
And now, the trouble is that it doesn't have to be me
link |
who's looking, okay?
link |
Or in fact, it doesn't have to be any conscious entity.
link |
Any kind of interaction with the external world
link |
that leaks out the information
link |
about whether this qubit was a zero or a one,
link |
sort of that causes the zerowness
link |
or the oneness of the qubit to be recorded
link |
in, you know, the radiation in the room,
link |
in the molecules of the air,
link |
in the wires that are connected to my device,
link |
any of that, as soon as the information leaks out,
link |
it is as if that qubit has been measured, okay?
link |
It is, you know, the state has now collapsed.
link |
You know, another way to say it
link |
is that it's become entangled with its environment, okay?
link |
But, you know, from the perspective of someone
link |
who's just looking at this qubit,
link |
it is as though it has lost its quantum state.
link |
And so, what this means is that
link |
if I want to do a quantum computation,
link |
I have to keep the qubits sort of fanatically
link |
well isolated from their environment.
link |
But then at the same time,
link |
they can't be perfectly isolated
link |
because I need to tell them what to do.
link |
I need to make them interact with each other,
link |
for one thing, and not only that,
link |
but in a precisely choreographed way, okay?
link |
And, you know, that is such a staggering problem, right?
link |
How do I isolate these qubits from the whole universe
link |
but then also tell them exactly what to do?
link |
I mean, you know, there were distinguished physicists
link |
and computer scientists in the 90s who said,
link |
this is fundamentally impossible, you know?
link |
The laws of physics will just never let you control qubits
link |
to the degree of accuracy that you're talking about.
link |
Now, what changed the views of most of us
link |
was a profound discovery in the mid to late 90s
link |
which was called the theory of quantum error correction
link |
and quantum fault tolerance, okay?
link |
And the upshot of that theory is that
link |
if I want to build a reliable quantum computer
link |
and scale it up to, you know, an arbitrary number
link |
of as many qubits as I want, you know,
link |
and doing as much on them as I want,
link |
I do not actually have to get the qubits
link |
perfectly isolated from their environment.
link |
It is enough to get them really, really, really well isolated, okay?
link |
And even if every qubit is sort of leaking,
link |
you know, its state into the environment at some rate,
link |
as long as that rate is low enough, okay,
link |
I can sort of encode the information that I care about
link |
in very clever ways across the collective states
link |
of multiple qubits, okay?
link |
In such a way that even if, you know,
link |
a small percentage of my qubits leak,
link |
well, I'm constantly monitoring them
link |
to see if that leak happened.
link |
I can detect it and I can correct it.
link |
I can recover the information I care about
link |
from the remaining qubits, okay?
link |
And so, you know, you can build a reliable quantum computer
link |
even out of unreliable parts, right?
link |
Now, in some sense, you know,
link |
that discovery is what set the engineering agenda
link |
for quantum computing research
link |
from the 1990s until the present, okay?
link |
The goal has been, you know,
link |
engineer qubits that are not perfectly reliable
link |
but reliable enough that you can then use
link |
these error correcting codes
link |
to have them simulate qubits
link |
that are even more reliable than they are, right?
link |
The error correction becomes a net win
link |
rather than a net loss, right?
link |
And then once you reach that sort of crossover point,
link |
then, you know, your simulated qubits
link |
could in turn simulate qubits
link |
that are even more reliable and so on
link |
until you've just, you know, effectively,
link |
you have arbitrarily reliable qubits.
link |
So long story short,
link |
we are not at that breakeven point yet.
link |
We're a hell of a lot closer than we were
link |
when people started doing this in the 90s,
link |
like orders of magnitude closer.
link |
But the key ingredient there
link |
is the more qubits, the better because...
link |
Ah, well, the more qubits,
link |
the larger the computation you can do, right?
link |
I mean, qubits are what constitute
link |
the memory of your quantum computer, right?
link |
But also for the, sorry,
link |
for the error correcting mechanism.
link |
So the way I would say it
link |
is that error correction imposes an overhead
link |
in the number of qubits.
link |
And that is actually one of the biggest practical problems
link |
with building a scalable quantum computer.
link |
If you look at the error correcting codes,
link |
at least the ones that we know about today,
link |
and you look at, you know,
link |
what would it take to actually use a quantum computer
link |
to, you know, hack your credit card number,
link |
which is, you know,
link |
maybe, you know, the most famous application
link |
people talk about, right?
link |
Let's say to factor huge numbers
link |
and thereby break the RSA cryptosystem.
link |
Well, what that would take
link |
would be thousands of, several thousand logical qubits.
link |
But now with the known error correcting codes,
link |
each of those logical qubits
link |
would need to be encoded itself
link |
using thousands of physical qubits.
link |
you're talking about millions of physical qubits.
link |
And in some sense,
link |
that is the reason why quantum computers
link |
are not breaking cryptography already.
link |
It's because of these immense overheads involved.
link |
So that overhead is additive or multiplicative?
link |
Well, it's multiplicative.
link |
I mean, it's like you take the number
link |
of logical qubits that you need
link |
in your abstract quantum circuit,
link |
you multiply it by a thousand or so.
link |
So, you know, there's a lot of work
link |
on, you know, inventing better,
link |
trying to invent better error correcting codes.
link |
Okay, that is the situation right now.
link |
In the meantime, we are now in,
link |
what the physicist John Preskill called
link |
the noisy intermediate scale quantum or NISQ era.
link |
And this is the era,
link |
you can think of it as sort of like the vacuum,
link |
you know, we're now entering the very early
link |
vacuum tube era of quantum computers.
link |
The quantum computer analog of the transistor
link |
has not been invented yet, right?
link |
That would be like true error correction, right?
link |
Where, you know, we are not or something else
link |
that would achieve the same effect, right?
link |
We are not there yet.
link |
But where we are now,
link |
let's say as of a few months ago,
link |
you know, as of Google's announcement
link |
of quantum supremacy,
link |
you know, we are now finally at the point
link |
where even with a non error corrected quantum computer,
link |
with, you know, these noisy devices,
link |
we can do something that is hard
link |
for classical computers to simulate, okay?
link |
So we can eke out some advantage.
link |
Now, will we in this noisy era
link |
be able to do something beyond
link |
what a classical computer can do
link |
that is also useful to someone?
link |
That we still don't know.
link |
People are going to be racing over the next decade
link |
to try to do that.
link |
By people, I mean, Google, IBM,
link |
you know, a bunch of startup companies.
link |
And research labs.
link |
Yeah, and research labs and governments.
link |
You just mentioned a million things.
link |
Well, I'll backtrack for a second.
link |
So we're in these vacuum tube days.
link |
Yeah, just entering them.
link |
And just entering, wow.
link |
Okay, so how do we escape the vacuum?
link |
So how do we get to,
link |
how do we get to where we are now with the CPU?
link |
Is this a fundamental engineering challenge?
link |
Is there breakthroughs on the physics side
link |
that are needed on the computer science side?
link |
Or is it a financial issue
link |
where much larger just sheer investment
link |
and excitement is needed?
link |
So, you know, those are excellent questions.
link |
My guess might, well, no, no.
link |
My guess would be all of the above.
link |
I mean, my guess, you know,
link |
I mean, you could say fundamentally
link |
it is an engineering issue, right?
link |
The theory has been in place since the 90s.
link |
You know, at least, you know, this is what,
link |
you know, error correction would look like.
link |
You know, we do not have the hardware
link |
that is at that level.
link |
But at the same time, you know,
link |
so you could just, you know, try to power through,
link |
you know, maybe even like, you know,
link |
if someone spent a trillion dollars
link |
on some quantum computing Manhattan project, right?
link |
Then conceivably they could just, you know,
link |
build an error corrected quantum computer
link |
as it was envisioned back in the 90s, right?
link |
I think the more plausible thing to happen
link |
is that there will be further theoretical breakthroughs
link |
and there will be further insights
link |
that will cut down the cost of doing this.
link |
So let's take a brief step to the philosophical.
link |
I just recently talked to Jim Keller
link |
who's sort of like the famed architect
link |
in the microprocessor world.
link |
And he's been told for decades,
link |
every year that the Moore's law is going to die this year.
link |
And he tries to argue that the Moore's law
link |
is still alive and well,
link |
and it'll be alive for quite a long time to come.
link |
How long did he say?
link |
Well, the main point is it's still alive,
link |
but he thinks there's still a thousand X improvement
link |
just on shrinking the transition that's possible.
link |
The point is that the exponential growth we see
link |
is actually a huge number of these S curves,
link |
just constant breakthroughs.
link |
At the philosophical level,
link |
why do you think we as descendants of apes
link |
were able to just keep coming up
link |
with these new breakthroughs on the CPU side
link |
is this something unique to this particular endeavor
link |
or will it be possible to replicate
link |
in the quantum computer space?
link |
There was a lot there,
link |
but to break off something,
link |
I mean, I think we are in an extremely special period
link |
of human history, right?
link |
I mean, it is, you could say,
link |
obviously special in many ways, right?
link |
There are way more people alive
link |
than there have been
link |
and the whole future of the planet
link |
is in question in a way that it hasn't been
link |
for the rest of human history.
link |
But in particular, we are in the era
link |
where we finally figured out
link |
how to build universal machines,
link |
you could say, the things that we call computers,
link |
machines that you program to simulate the behavior
link |
of whatever machine you want.
link |
And once you've sort of crossed this threshold
link |
of universality, you've built,
link |
you could say, touring,
link |
you've instantiated touring machines
link |
in the physical world.
link |
Well, then the main questions are ones of numbers.
link |
They are ones of how much memory can you access?
link |
How fast does it run?
link |
How many parallel processors?
link |
At least until quantum computing.
link |
Quantum computing is the one thing
link |
that changes what I just said, right?
link |
But as long as it's classical computing,
link |
then it's all questions of numbers.
link |
And you could say at a theoretical level,
link |
the computers that we have today
link |
are the same as the ones in the 50s.
link |
They're just millions of times faster
link |
and with millions of times more memory.
link |
And I think there's been an immense economic pressure
link |
to get more and more transistors,
link |
get them smaller and smaller,
link |
add more and more cores.
link |
And in some sense, a huge fraction
link |
of all of the technological progress
link |
that there is in all of civilization
link |
has gotten concentrated just more narrowly
link |
into just those problems, right?
link |
And so it has been one of the biggest success stories
link |
in the history of technology, right?
link |
There's, I mean, it is, I am as amazed by it
link |
as anyone else is, right?
link |
But at the same time, we also know that it,
link |
and I really do mean we know
link |
that it cannot continue indefinitely, okay?
link |
Because you will reach fundamental limits
link |
on how small you can possibly make a processor.
link |
And if you want a real proof
link |
that would justify my use of the word,
link |
we know that Moore's law has to end.
link |
I mean, ultimately you will reach the limits
link |
imposed by quantum gravity.
link |
If you tried to build a computer
link |
that operated at 10 to the 43 Hertz,
link |
so did 10 to the 43 operations per second,
link |
that computer would use so much energy
link |
that it would simply collapse through a black hole, okay?
link |
So in reality, we're going to reach the limits
link |
long before that, but that is a sufficient proof.
link |
That there's a limit.
link |
But it would be interesting to try to understand
link |
the mechanism, the economic pressure that you said,
link |
just like the Cold War was a pressure on getting us,
link |
getting us, because my us is both the Soviet Union
link |
and the United States, but getting us,
link |
the two countries to get to hurry up,
link |
to get to space, to the moon,
link |
there seems to be that same kind of economic pressure
link |
that somehow created a chain of engineering breakthroughs
link |
that resulted in the Moore's law.
link |
And it'd be nice to replicate.
link |
Yeah, well, I mean, some people are sort of,
link |
get depressed about the fact
link |
that technological progress may seem to have slowed down
link |
in many, many realms outside of computing, right?
link |
And there was this whole thing of we wanted flying cars
link |
and we only got Twitter instead, right?
link |
Yeah, good old Peter Thiel, yeah.
link |
Yeah, yeah, yeah, right, right, right.
link |
So then jumping to another really interesting topic
link |
that you mentioned, so Google announced with their work
link |
in the paper in Nature with quantum supremacy.
link |
Can you describe, again, back to the basic,
link |
what is perhaps not so basic, what is quantum supremacy?
link |
Absolutely, so quantum supremacy is a term
link |
that was coined by, again, by John Preskill in 2012.
link |
Not everyone likes the name, but it sort of stuck.
link |
We don't, we sort of haven't found a better alternative.
link |
It's technically quantum computational supremacy.
link |
Yeah, yeah, supremacy, that's right, that's right.
link |
But the basic idea is actually one that goes all the way back
link |
to the beginnings of quantum computing
link |
when Richard Feynman and David Deutsch, people like that,
link |
were talking about it in the early 80s.
link |
And quantum supremacy just refers to sort of the point
link |
in history when you can first use a quantum computer
link |
to do some well defined task much faster
link |
than any known algorithm running on any of the classical computers
link |
that are available, okay?
link |
So notice that I did not say a useful task, okay?
link |
It could be something completely artificial,
link |
but it's important that the task be well defined.
link |
So in other words, it is something that has right and wrong answers
link |
that are knowable independently of this device, right?
link |
And we can then run the device, see if it gets the right answer or not.
link |
Can you clarify a small point?
link |
You said much faster than a classical implementation.
link |
What about sort of what about the space with where the class,
link |
there's no, there's not, it doesn't even exist,
link |
a classical algorithm to show the power?
link |
So maybe I should clarify.
link |
Everything that a quantum computer can do,
link |
a classical computer can also eventually do, okay?
link |
And the reason why we know that is that a classical computer
link |
could always, you know, if it had no limits of time and memory,
link |
it could always just store the entire quantum state,
link |
you know, of your, you know, of the quantum,
link |
store a list of all the amplitudes,
link |
you know, in the state of the quantum computer,
link |
and then just, you know, do some linear algebra
link |
to just update that state, right?
link |
And so anything that quantum computers can do
link |
can also be done by classical computers,
link |
albeit exponentially slower in some cases.
link |
So quantum computers don't go into some magical place
link |
outside of Alan Turing's definition of computation.
link |
They do not solve the halting problem.
link |
They cannot solve anything that is uncomputable
link |
in Alan Turing's sense.
link |
What we think they do change
link |
is what is efficiently computable, okay?
link |
And, you know, since the 1960s, you know,
link |
the word efficiently, you know,
link |
as well has been a central word in computer science,
link |
but it's sort of a code word for something technical,
link |
which is basically with polynomial scaling, you know,
link |
that as you get to larger and larger inputs,
link |
you would like an algorithm that uses an amount of time
link |
that scales only like the size of the input
link |
raised to some power
link |
and not exponentially with the size of the input, right?
link |
Yeah, so I do hope we get to talk again
link |
because one of the many topics
link |
that there's probably several hours worth of conversation on
link |
which we probably won't even get a chance to touch today,
link |
but you briefly mentioned it,
link |
but let's maybe try to continue.
link |
So you said the definition of quantum supremacy
link |
is basically achieving a place
link |
where much faster on a formal,
link |
that quantum computer is much faster
link |
on a formal well defined problem
link |
that is or isn't useful.
link |
Yeah, yeah, yeah, right, right.
link |
And I would say that we really want three things, right?
link |
We want, first of all,
link |
the quantum computer to be much faster
link |
just in the literal sense of like number of seconds,
link |
you know, it's a solving this, you know,
link |
well defined, you know, problem.
link |
Secondly, we want it to be sort of, you know,
link |
for a problem where we really believe
link |
that a quantum computer has better scaling behavior, right?
link |
So it's not just an incidental, you know,
link |
matter of hardware,
link |
but it's that, you know,
link |
as you went to larger and larger inputs,
link |
you know, the classical scaling would be exponential
link |
and the scaling for the quantum algorithm
link |
would only be polynomial.
link |
And then thirdly, we want the first thing,
link |
the actual observed speed up
link |
to only be explainable in terms of the scaling behavior, right?
link |
So, you know, I want, you know,
link |
a real world, you know, a real problem to get solved,
link |
let's say by a quantum computer with 50 qubits or so,
link |
and for no one to be able to explain that in any way
link |
other than, well, you know, this computer involved a quantum state
link |
with two to the 50th power amplitudes.
link |
And, you know, a classical simulation,
link |
at least any that we know today,
link |
would require keeping track of two to the 50th numbers.
link |
And this is the reason why it was faster.
link |
So the intuition is that then if you demonstrate on 50 qubits,
link |
then once you get to 100 qubits,
link |
then it'll be even much more faster.
link |
Precisely, precisely.
link |
Yeah, and, you know, and quantum supremacy
link |
does not require error correction, right?
link |
We don't, you know, we don't have, you could say,
link |
true scalability yet or true, you know, error correction yet.
link |
But you could say quantum supremacy is already enough by itself
link |
to refute the skeptics who said a quantum computer
link |
will never outperform a classical computer for anything.
link |
But one, how do you demonstrate quantum supremacy?
link |
And two, what's up with these news articles
link |
I'm reading that Google did so?
link |
Yeah, all right, well, great, great questions,
link |
because now you get into actually, you know,
link |
a lot of the work that I've, you know,
link |
I and my students have been doing for the last decade,
link |
which was precisely about how do you demonstrate
link |
quantum supremacy using technologies that, you know,
link |
we thought would be available in the near future.
link |
And so one of the main things that we realized around 2011,
link |
and this was me and my student, Alex Arkhipov at MIT at the time,
link |
and independently of some others,
link |
including Bremner, Joseph, and Shepherd, okay?
link |
And the realization that we came to was that
link |
if you just want to prove that a quantum computer is faster,
link |
you know, and not do something useful with it,
link |
then there are huge advantages to sort of switching
link |
your attention from problems like factoring numbers
link |
that have a single right answer
link |
to what we call sampling problems.
link |
So these are problems where the goal is just to output
link |
a sample from some probability distribution,
link |
let's say over strings of 50 bits, right?
link |
So there are, you know, many, many,
link |
many possible valid outputs.
link |
You know, your computer will probably never even produce
link |
the same output twice, you know,
link |
if it's running as, even, you know,
link |
assuming it's running perfectly, okay?
link |
But the key is that some outputs are supposed
link |
to be likelier than other ones.
link |
So, sorry, to clarify, is there a set of outputs
link |
that are valid and set they're not,
link |
or is it more that the distribution
link |
of a particular kind of output is more,
link |
is like there's a specific distribution
link |
of a particular kind of output?
link |
Yeah, there's a specific distribution
link |
that you're trying to hit, right?
link |
Or, you know, that you're trying to sample from.
link |
Now, there are a lot of questions about this,
link |
you know, how do you do that, right?
link |
Now, how you do it, you know,
link |
it turns out that with a quantum computer,
link |
even with the noisy quantum computers
link |
that we have now, that we have today,
link |
what you can do is basically just apply
link |
a randomly chosen sequence of operations, right?
link |
So we, you know, in some of the, you know,
link |
that part is almost trivial, right?
link |
We just sort of get the qubits to interact
link |
in some random way,
link |
although a sort of precisely specified random way
link |
so we can repeat the exact same random sequence
link |
of interactions again and get another sample
link |
from that same distribution.
link |
And what this does is it basically,
link |
well, it creates a lot of garbage,
link |
but, you know, very specific garbage, right?
link |
So, you know, of all of the,
link |
so we're gonna talk about Google's device
link |
that were 53 qubits there, okay?
link |
And so there were two to the 53 power possible outputs.
link |
Now, for some of those outputs,
link |
you know, there was a little bit more
link |
destructive interference in their amplitude, okay?
link |
So their amplitudes were a little bit smaller.
link |
And for others, there was a little more
link |
constructive interference.
link |
You know, the amplitudes were a little bit
link |
more aligned with each other, you know,
link |
and so those were a little bit likelier, okay?
link |
All of the outputs are exponentially unlikely,
link |
but some are, let's say, two times or three times,
link |
you know, unlikelier than others, okay?
link |
And so you can define, you know,
link |
this sequence of operations that gives rise
link |
to this probability distribution.
link |
Okay, now the next question would be,
link |
well, how do you, you know,
link |
even if you're sampling from it,
link |
how do you verify that, right?
link |
And so my students and I,
link |
and also the people at Google
link |
were doing the experiment,
link |
came up with statistical tests
link |
that you can apply to the outputs
link |
in order to try to verify, you know,
link |
what is, you know, that at least
link |
that some hard problem is being solved.
link |
The test that Google ended up using
link |
was something that they called
link |
the linear cross entropy benchmark, okay?
link |
And it's basically, you know,
link |
so the drawback of this test
link |
is that it requires, like,
link |
it requires you to do a two to the 53 time calculation
link |
with your classical computer, okay?
link |
So it's very expensive to do the test
link |
on a classical computer.
link |
The good news is...
link |
How big of a number is two to the 53?
link |
It's about nine quadrillion, okay?
link |
That doesn't help.
link |
it's, you want it in like scientific notation.
link |
No, no, no, what I mean is...
link |
Yeah, it is just...
link |
It's impossible to run on a...
link |
Yeah, so we will come back to that.
link |
It is just barely possible to run,
link |
we think, on the largest supercomputer
link |
that currently exists on Earth,
link |
which is called Summit at Oak Ridge National Lab, okay?
link |
Great, this is exciting.
link |
That's the short answer.
link |
So ironically, for this type of experiment,
link |
we don't want 100 qubits, okay?
link |
Because with 100 qubits, even if it works,
link |
we don't know how to verify the results, okay?
link |
So we want, you know, a number of qubits
link |
that is enough that, you know,
link |
the biggest classical computers on Earth
link |
will have to sweat, you know,
link |
and we'll just barely, you know,
link |
be able to keep up with the quantum computer,
link |
you know, using much more time,
link |
but they will still be able to do it
link |
in order that we can verify the results.
link |
Which is where the 53 comes from for the number of qubits?
link |
Basically, well, I mean, that's also,
link |
that's sort of, you know,
link |
I mean, that's sort of where they are now
link |
in terms of scaling, you know?
link |
And then, you know, soon, you know, that point will be passed.
link |
And then when you get to larger numbers of qubits,
link |
then, you know, these types of sampling experiments
link |
will no longer be so interesting
link |
because we won't even be able to verify the results
link |
and we'll have to switch to other types of computation.
link |
So with the sampling thing,
link |
you know, so the test that Google applied
link |
with this linear cross entropy benchmark
link |
was basically just take the samples that were generated,
link |
which are, you know, a very small subset
link |
of all the possible samples that there are.
link |
But for those, you calculate with your classical computer
link |
the probabilities that they should have been output.
link |
And you see, are those probabilities
link |
like larger than the mean?
link |
You know, so is the quantum computer biased
link |
toward outputting the strings that it's,
link |
you know, that you want it to be biased toward?
link |
Okay, and then finally,
link |
we come to a very crucial question,
link |
which is supposing that it does that.
link |
Well, how do we know that a classical computer
link |
could not have quickly done the same thing, right?
link |
How do we know that, you know,
link |
this couldn't have been spoofed by a classical computer, right?
link |
And so, well, the first answer is we don't know for sure
link |
because, you know, this takes us
link |
into questions of complexity theory.
link |
You know, I mean, questions of the magnitude
link |
of the P versus NP question and things like that, right?
link |
You know, we don't know how to rule out definitively
link |
that there could be fast classical algorithms
link |
for, you know, even simulating quantum mechanics
link |
and for, you know, simulating experiments like these,
link |
but we can give some evidence against that possibility.
link |
And that was sort of the, you know,
link |
the main thrust of a lot of the work
link |
that my colleagues and I did, you know,
link |
over the last decade,
link |
which is then sort of in around 2015 or so,
link |
what led to Google deciding to do this experiment.
link |
So is the kind of evidence here,
link |
first of all, the hard P equals NP problem that you mentioned
link |
and the kind of evidence that you were looking at,
link |
is that something you come to on a sheet of paper
link |
or is this something, are these empirical experiments?
link |
It's math for the most part.
link |
I mean, you know, it's also, you know,
link |
we have a bunch of methods
link |
that are known for simulating quantum circuits
link |
or quantum computations with classical computers.
link |
And so we have to try them all out
link |
and make sure that, you know, they don't work,
link |
you know, make sure that they have exponential scaling
link |
on, you know, these problems and not just theoretically,
link |
but with the actual range of parameters
link |
that are actually, you know, arising in Google's experiment.
link |
Okay, so there is an empirical component to it, right?
link |
But now on the theoretical side,
link |
you know, basically what we know how to do
link |
in theoretical computer science and computational complexity
link |
is, you know, we don't know how to prove
link |
that most of the problems we care about are hard,
link |
but we know how to pass the blame to someone else, okay?
link |
We know how to say, well, look, you know,
link |
I can't prove that this problem is hard,
link |
but if it is easy, then all these other things
link |
that, you know, you probably were much more confident
link |
or were hard, then those would be easy as well, okay?
link |
So we can give what are called reductions.
link |
This has been the basic strategy in, you know,
link |
NP completeness, right, in all of theoretical computer science
link |
and cryptography since the 1970s, really.
link |
And so we were able to give some reduction evidence
link |
for the hardness of simulating these sampling experiments,
link |
these sampling based quantum supremacy experiments.
link |
So reduction evidence is not as satisfactory as it should be.
link |
One of the biggest open problems in this area
link |
is to make it better.
link |
But, you know, we can do something.
link |
You know, certainly we can say that, you know,
link |
if there is a fast classical algorithm
link |
to spoof these experiments, then it has to be very,
link |
very unlike any of the algorithms that we know.
link |
TREVOR Which is kind of in the same kind
link |
of space of reasoning that people say P not equals NP.
link |
BENJAMIN Yeah, it's in the same spirit.
link |
TREVOR Okay, so Andrew Yang, a very intelligent
link |
and a presidential candidate with a lot of interesting ideas
link |
in all kinds of technological fields, tweeted that
link |
because of quantum computing, no code is uncrackable.
link |
Is he wrong or right?
link |
BENJAMIN He was premature, let's say.
link |
So, well, okay, wrong.
link |
Look, I'm actually, you know, I'm a fan of Andrew Yang.
link |
I like his candidacy.
link |
I think that, you know, he may be ahead of his time
link |
with, you know, the universal basic income and so forth.
link |
And he may also be ahead of his time in that tweet
link |
that you referenced.
link |
So regarding using quantum computers
link |
to break cryptography, so the situation is this, okay?
link |
So the famous discovery of Peter Shor, you know, 26 years ago
link |
that really started quantum computing, you know,
link |
as an autonomous field was that if you built a full
link |
scalable quantum computer, then you could use it
link |
to efficiently find the prime factors of huge numbers
link |
and calculate discrete logarithms and solve
link |
a few other problems that are very, very special
link |
in character, right?
link |
They're not NP complete problems.
link |
We're pretty sure they're not, okay?
link |
But it so happens that most of the public key cryptography
link |
that we currently use to protect the internet
link |
is based on the belief that these problems are hard.
link |
Okay, what Shor showed is that once you get
link |
scalable quantum computers, then that's no longer true, okay?
link |
But now, you know, before people panic,
link |
there are two important points to understand here.
link |
Okay, the first is that quantum supremacy,
link |
the milestone that Google just achieved,
link |
is very, very far from the kind of scalable quantum computer
link |
that would be needed to actually threaten
link |
public key cryptography.
link |
Okay, so, you know, we touched on this earlier, right?
link |
But Google's device has 53 physical qubits, right?
link |
To threaten cryptography, you're talking, you know,
link |
with any of the known error correction methods,
link |
you're talking millions of physical qubits.
link |
Because error correction would be required
link |
to threaten cryptography.
link |
Yes, yes, yes, it certainly would, right?
link |
And, you know, how much, you know,
link |
how great will the overhead be from the error correction?
link |
That we don't know yet.
link |
But with the known codes, you're talking millions
link |
of physical qubits and of a much higher quality
link |
than any that we have now, okay?
link |
So, you know, I don't think that that is, you know,
link |
coming soon, although people who have secrets
link |
that, you know, need to stay secret for 20 years,
link |
you know, are already worried about this,
link |
you know, for the good reason that, you know,
link |
we presume that intelligence agencies
link |
are already scooping up data, you know,
link |
in the hope that eventually they'll be able to decode it
link |
once quantum computers become available, okay?
link |
So this brings me to the second point I wanted to make,
link |
which is that there are other public key cryptosystems
link |
that are known that we don't know how to break
link |
even with quantum computers, okay?
link |
And so there's a whole field devoted to this now,
link |
which is called post quantum cryptography, okay?
link |
And so there is already, so we have some good candidates now.
link |
The best known being what are called
link |
lattice based cryptosystems.
link |
And there is already some push to try to migrate
link |
to these cryptosystems.
link |
So NIST in the US is holding a competition
link |
to create standards for post quantum cryptography,
link |
which will be the first step in trying to get
link |
every web browser and every router to upgrade,
link |
you know, and use, you know, something like SSL
link |
that would be based on, you know,
link |
what we think is quantum secure cryptography.
link |
But, you know, this will be a long process.
link |
But, you know, it is something that people
link |
are already starting to do.
link |
And so, you know, I'm sure this algorithm
link |
is sort of a dramatic discovery.
link |
You know, it could be a big deal
link |
for whatever intelligence agency
link |
first gets a scalable quantum computer,
link |
if no, at least certainly if no one else
link |
knows that they have it, right?
link |
But eventually we think that we could migrate
link |
the internet to the post quantum cryptography
link |
and then we'd be more or less back where we started.
link |
Okay, so this is sort of not the application
link |
of quantum computing.
link |
I think that's really gonna change the world
link |
in a sustainable way, right?
link |
The big, by the way, the biggest practical application
link |
of quantum computing that we know about by far,
link |
I think is simply the simulation
link |
of quantum mechanics itself.
link |
In order to, you know, learn about chemical reactions,
link |
you know, design maybe new chemical processes,
link |
new materials, new drugs, new solar cells,
link |
new superconductors, all kinds of things like that.
link |
What's the size of a quantum computer
link |
that would be able to simulate the,
link |
you know, quantum mechanical systems themselves
link |
that would be impactful for the real world
link |
for the kind of chemical reactions
link |
and that kind of work?
link |
What scale are we talking about?
link |
Now you're asking a very, very current question,
link |
a very big question.
link |
People are going to be racing over the next decade
link |
to try to do useful quantum simulations
link |
even with, you know, 100 or 200 qubit quantum computers
link |
of the sort that we expect to be able to build
link |
over the next decade.
link |
Okay, so that might be, you know,
link |
the first application of quantum computing
link |
that we're able to realize, you know,
link |
or maybe it will prove to be too difficult
link |
and maybe even that will require fault tolerance
link |
or, you know, will require error correction.
link |
So there's an aggressive race to come up
link |
with the one case study kind of like Peter Schor
link |
with the idea that would just capture
link |
the world's imagination of like,
link |
look, we can actually do something very useful here.
link |
Right, but I think, you know, within the next decade,
link |
the best shot we have is certainly not,
link |
you know, using Schor's algorithm to break cryptography,
link |
you know, just because it requires,
link |
you know, too much in the way of error correction.
link |
The best shot we have is to do some quantum simulation
link |
that tells the material scientists
link |
or chemists or nuclear physicists,
link |
you know, something that is useful to them
link |
and that they didn't already know,
link |
you know, and you might only need one or two successes
link |
in order to change some, you know,
link |
billion dollar industries, right?
link |
Like, you know, the way that people make fertilizer right now
link |
is still based on the Haber Bosch process
link |
from a century ago.
link |
And it is some many body quantum mechanics problem
link |
that no one really understands, right?
link |
If you could design a better way to make fertilizer, right?
link |
That's, you know, billions of dollars right there.
link |
So those are sort of the applications
link |
that people are going to be aggressively racing toward
link |
over the next decade.
link |
Now, I don't know if they're gonna realize it or not,
link |
but, you know, they certainly at least have a shot.
link |
So it's gonna be a very, very interesting next decade.
link |
But just to clarify, what's your intuition?
link |
If a breakthrough like that comes with,
link |
is it possible for that breakthrough to be on 50
link |
to 100 qubits or is scale a fundamental thing
link |
like 500, 1000 plus qubits?
link |
Yeah, so I can tell you what the current studies are saying.
link |
You know, I think probably better to rely on that
link |
than on my intuition.
link |
But, you know, there was a group at Microsoft
link |
had a study a few years ago that said
link |
even with only about 100 qubits,
link |
you know, you could already learn something new
link |
about the chemical reaction that makes fertilizer, for example.
link |
The trouble is they're talking about 100 qubits
link |
and about a million layers of quantum gates.
link |
Okay, so basically they're talking about
link |
100 nearly perfect qubits.
link |
So the logical qubits, as you mentioned before.
link |
Yeah, exactly, 100 logical qubits.
link |
And now, you know, the hard part for the next decade
link |
is gonna be, well, what can we do
link |
with 100 to 200 noisy qubits?
link |
Yeah, is there error correction breakthroughs
link |
that might come without the need to do
link |
thousands or millions of physical qubits?
link |
Yeah, so people are gonna be pushing simultaneously
link |
on a bunch of different directions.
link |
One direction, of course,
link |
is just making the qubits better, right?
link |
And, you know, there is tremendous progress there.
link |
I mean, you know, the fidelity is like
link |
the accuracy of the qubits has improved
link |
by several orders of magnitude, you know,
link |
in the last decade or two.
link |
Okay, the second thing is designing better error,
link |
you know, let's say lower overhead error correcting codes
link |
and even short of doing the full recursive error correction.
link |
You know, there are these error mitigation strategies
link |
that you can use, you know, that may, you know,
link |
allow you to eke out a useful speed up in the near term.
link |
And then the third thing is just taking the quantum algorithms
link |
for simulating quantum chemistry or materials
link |
and making them more efficient.
link |
You know, and those algorithms
link |
are already dramatically more efficient
link |
than they were, let's say, five years ago.
link |
And so when, you know, I quoted these estimates
link |
like, you know, circuit depth of one million.
link |
And so, you know, I hope that because people will care enough
link |
that these numbers are gonna come down.
link |
So you're one of the world class researchers in this space.
link |
There's a few groups like you mentioned,
link |
Google and IBM working at this.
link |
There's other research labs, but you put also,
link |
you have an amazing blog.
link |
You just, you put a lot, you paid me to say it.
link |
You put a lot of effort sort of to communicating
link |
the science of this and communicating,
link |
exposing some of the BS and sort of the natural,
link |
just like in the AI space, the natural charlatanism,
link |
if that's a word in this, in the quantum mechanics in general,
link |
but quantum computers and so on.
link |
Can you give some notes about people or ideas
link |
that people like me or listeners in general
link |
from outside the field should be cautious of
link |
when they're taking in news headings
link |
that Google achieved quantum supremacy?
link |
So what should we look out for?
link |
Where's the charlatans in the space?
link |
Yeah, so good question.
link |
Unfortunately, quantum computing is a little bit like
link |
cryptocurrency or deep learning.
link |
Like there is a core of something
link |
that is genuinely revolutionary and exciting.
link |
And because of that core, it attracts this sort of
link |
vast penumbra of people making just utterly ridiculous claims.
link |
And so with quantum computing, I mean,
link |
I would say that the main way that people go astray
link |
is by not focusing on sort of the question of,
link |
are you getting a speed up over a classical computer or not?
link |
And so people have like dismissed quantum supremacy
link |
because it's not useful, right?
link |
Or it's not itself, let's say, obviously useful for anything.
link |
Okay, but ironically, these are some of the same people
link |
who will go and say, well, we care about useful applications.
link |
We care about solving traffic routing
link |
and financial optimization and all these things.
link |
And that sounds really good, but their entire spiel
link |
is sort of counting on nobody asking the question,
link |
yes, but how well could a classical computer
link |
do the same thing, right?
link |
I really mean the entire thing is they say,
link |
well, a quantum computer can do this,
link |
a quantum computer can do that.
link |
A quantum computer can do that, right?
link |
And they just avoid the question,
link |
are you getting a speed up over a classical computer or not?
link |
And if so, how do you know?
link |
Have you really thought carefully about classical algorithms
link |
to solve the same problem, right?
link |
And a lot of the application areas
link |
that the companies and investors are most excited about
link |
that the popular press is most excited about
link |
where quantum computers have been things
link |
like machine learning, AI, optimization, okay?
link |
And the problem with that is that since the very beginning,
link |
even if you have a perfect fault tolerant,
link |
scalable quantum computer,
link |
we have known of only modest speed ups
link |
that you can get for these problems, okay?
link |
So there is a famous quantum algorithm
link |
called Grover's algorithm, okay?
link |
And what it can do is it can solve many,
link |
many of the problems that arise in AI,
link |
machine learning, optimization,
link |
including NP complete problems, okay?
link |
But it can solve them in about the square root
link |
of the number of steps that a classical computer would need
link |
for the same problems, okay?
link |
Now a square root speed up is important, it's impressive.
link |
It is not an exponential speed up, okay?
link |
So it is not the kind of game changer
link |
that let's say Shor's algorithm for factoring is,
link |
or for that matter that simulation of quantum mechanics is,
link |
okay, it is a more modest speed up.
link |
And let's say roughly, in theory,
link |
it could roughly double the size
link |
of the optimization problems that you could handle, right?
link |
And so because people found that I guess too boring
link |
or too unimpressive, they've gone on to like invent
link |
all of these heuristic algorithms
link |
where because no one really understands them,
link |
you can just project your hopes onto them, right?
link |
That, well, maybe it gets an exponential speed up.
link |
You can't prove that it doesn't,
link |
and the burden is on you to prove
link |
that it doesn't get a speed up, right?
link |
And so they've done an immense amount of that kind of thing.
link |
And a really worrying amount of the case
link |
for building a quantum computer has come to rest
link |
on this stuff that those of us in this field
link |
know perfectly well is on extremely shaky foundations.
link |
So the fundamental question is,
link |
show that there's a speed up over the classical.
link |
And in this space that you're referring to,
link |
which is actually really interesting,
link |
it's the area that a lot of people excited about
link |
is machine learning.
link |
So your sense is, do you think it will,
link |
I know that there's a lot of smoke currently,
link |
but do you think there actually eventually
link |
might be breakthroughs where you do get exponential speed ups
link |
in the machine learning space?
link |
Absolutely, there might be.
link |
I mean, I think we know of modest speed ups
link |
that you can get for these problems.
link |
I think, you know, whether you can get bigger speed ups
link |
is one of the biggest questions for quantum computing theory,
link |
you know, for people like me to be thinking about.
link |
Now, you know, we had actually recently
link |
a really, you know, a super exciting candidate
link |
for an exponential quantum speed up
link |
for a machine learning problem
link |
that people really care about.
link |
This is basically the Netflix problem,
link |
the problem of recommending products to users
link |
given some sparse data about their preferences.
link |
Karinidis and Prakash in 2016 had an algorithm
link |
for sampling recommendations that was exponentially faster
link |
than any known classical algorithm, right?
link |
And so, you know, a lot of people were excited.
link |
I was excited about it.
link |
I had an 18 year old undergrad by the name of Yilin Tang,
link |
and she was obviously brilliant.
link |
She was looking for a project.
link |
I gave her as a project,
link |
can you prove that this speed up is real?
link |
Can you prove that, you know, any classical algorithm
link |
would need to access exponentially more data, right?
link |
And, you know, this was a case where if that was true,
link |
this was not like a P versus NP type of question, right?
link |
This might well have been provable,
link |
but she worked on it for a year.
link |
She couldn't do it.
link |
Eventually she figured out why she couldn't do it.
link |
And the reason was that that was false.
link |
There is a classical algorithm
link |
with a similar performance to the quantum algorithm.
link |
So Yilin succeeded in dequantizing
link |
that machine learning algorithm.
link |
And then in the last couple of years,
link |
building on Yilin's breakthrough,
link |
a bunch of the other quantum machine learning algorithms
link |
that were proposed have now also been dequantized.
link |
Okay, and so I would say, yeah.
link |
That's a kind of important backwards step.
link |
Like a forward step for science,
link |
but a step for quantum machine learning
link |
that precedes the big next forward step.
link |
Right, right, right.
link |
Right, now some people will say,
link |
well, you know, there's a silver lining in this cloud.
link |
They say, well, thinking about quantum computing
link |
has led to the discovery
link |
of potentially useful new classical algorithms.
link |
And so, you know, so you get these spinoff applications,
link |
but if you want a quantum speed up,
link |
you really have to think carefully about that.
link |
You know, Yilin's work was a perfect illustration of why.
link |
Right, and I think that, you know, the challenge,
link |
you know, the field is now open, right?
link |
Find a better example,
link |
find, you know, where quantum computers
link |
are going to deliver big gains for machine learning.
link |
You know, I am, you know,
link |
not only do I ardently support,
link |
you know, people thinking about that,
link |
I'm trying to think about it myself
link |
and have my students and postdocs think about it,
link |
but we should not pretend
link |
that those speed ups are already established.
link |
And the problem comes when so many of the companies
link |
and, you know, and journalists in this space
link |
are pretending that.
link |
Like all good things, like life itself,
link |
this conversation must soon come to an end.
link |
Let me ask the most absurdly philosophical last question.
link |
What is the meaning of life?
link |
What gives your life fulfillment, purpose,
link |
happiness, and yeah, meaning?
link |
I would say, you know, number one,
link |
trying to discover new things about the world
link |
and share them and, you know, communicate
link |
and learn what other people have discovered.
link |
You know, number two, you know, my friends,
link |
my family, my kids, my students,
link |
you know, just the people around me.
link |
Number three, you know, trying, you know,
link |
when I can to, you know, make the world better
link |
in some small ways.
link |
And, you know, it's depressing that I can't do more
link |
and that, you know, the world is, you know,
link |
facing crises over, you know, the climate
link |
and over, you know, sort of resurgent authoritarianism
link |
and all these other things, but, you know,
link |
trying to stand against the things
link |
that I find horrible when I can.
link |
Let me ask you one more absurd question.
link |
What makes you smile?
link |
Well, yeah, I guess your question just did.
link |
I thought I tried that absurd one on you.
link |
Well, it was a huge honor to talk to you.
link |
We'll probably talk to you for many more hours, Scott.
link |
Thank you so much.
link |
Thank you for listening to this conversation
link |
with Scott Aaronson.
link |
And thank you to our presenting sponsor, Cash App.
link |
Download it, use code LexPodcast,
link |
you'll get $10 and $10 will go to FIRST,
link |
an organization that inspires and educates young minds
link |
to become science and technology innovators of tomorrow.
link |
If you enjoy this podcast, subscribe on YouTube,
link |
give it five stars on Apple Podcast,
link |
support it on Patreon,
link |
or simply connect with me on Twitter at Lex Friedman.
link |
Now, let me leave you with some words
link |
from a funny and insightful blog post
link |
Scott wrote over 10 years ago
link |
on the ever present Malthusianisms in our daily lives.
link |
Quote, again and again,
link |
I've undergone the humbling experience
link |
of first lamenting how badly something sucks,
link |
then only much later having the crucial insight
link |
that it's not sucking
link |
wouldn't have been a Nash equilibrium.
link |
Thank you for listening.
link |
I hope to see you next time.