back to indexScott Aaronson: Quantum Computing | Lex Fridman Podcast #72
Chapters
0:0 Introduction
5:7 Role of philosophy in science
29:27 What is a quantum computer?
41:12 Quantum decoherence (noise in quantum information)
49:22 Quantum computer engineering challenges
51:0 Moore's Law
56:33 Quantum supremacy
72:18 Using quantum computers to break cryptography
77:11 Practical application of quantum computers
82:18 Quantum machine learning, questinable claims, and cautious optimism
90:53 Meaning of life
00:00:00.000 |
The following is a conversation with Scott Aronson, 00:00:10.000 |
His research interests center around the capabilities 00:00:14.580 |
and computational complexity theory more generally. 00:00:23.320 |
We only had about an hour and a half for this conversation, 00:00:35.640 |
and all the complexity classes that Scott catalogs 00:00:43.640 |
based on questions and comments I've received, 00:00:48.200 |
is to try to be in the background without ego 00:00:53.400 |
One, let the guests shine and try to discover together 00:01:11.720 |
about terminology, about concepts, about ideas. 00:01:15.240 |
Many of the topics we talk about in the podcast 00:01:22.760 |
and generally as a curious human who loves to read. 00:01:26.160 |
But frankly, I see myself in these conversations 00:01:29.160 |
as the main character for one of my favorite novels 00:01:39.040 |
But the basic questions don't come from my ignorance 00:01:45.760 |
And if we linger on them from almost a naive perspective, 00:01:48.980 |
we can draw an insightful thread from computer science 00:02:05.640 |
support it on Patreon, or simply connect with me on Twitter 00:02:13.520 |
As usual, I'll do one or two minutes of ads now, 00:02:27.080 |
First, get Cash App and use the code LEXPODCAST. 00:02:31.640 |
Second, listen to the Tech Meme Ride Home Podcast 00:02:36.280 |
Search "ride home," two words, in your podcast app. 00:02:56.000 |
Brokerage services are provided by Cash App Investing, 00:03:03.020 |
Since Cash App does fractional share trading, 00:03:05.340 |
let me mention that the order execution algorithm 00:03:09.760 |
to create the abstraction of fractional orders 00:03:19.460 |
provides an easy interface that takes a step up 00:03:22.260 |
to the next layer of abstraction over the stock market, 00:03:25.140 |
making trading more accessible for new investors 00:03:44.100 |
that is helping to advance robotics and STEM education 00:03:55.740 |
It's a technology podcast I've been listening to for a while 00:04:12.600 |
For fun, I like building apps on smartphones, 00:04:16.260 |
most on Android, so I'm always a little curious 00:04:21.120 |
I saw that Samsung announced the new Galaxy S20, 00:04:35.540 |
They've also started to do weekend bonus episodes 00:04:38.580 |
with interviews of people like AOL founder Steve Case 00:04:51.580 |
if you search your podcast app for ride home, two words. 00:05:02.580 |
And now, here's my conversation with Scott Aronson. 00:05:06.660 |
I sometimes get criticism from a listener here and there 00:05:18.180 |
or a theoretical computer scientist like yourself, 00:05:21.740 |
I waste time by asking philosophical questions 00:05:33.500 |
whether space-time is emergent and fundamental, 00:05:35.940 |
even the crazier questions like whether aliens exist, 00:05:44.680 |
and of course, whether we live in a simulation or not. 00:05:51.360 |
I try to dance back and forth from the deep technical 00:05:55.460 |
to the philosophical, so I've done that quite a bit. 00:06:15.100 |
Why should we computer scientists, mathematicians, 00:06:17.740 |
physicists care about philosophy, do you think? 00:06:20.780 |
- Well, I would reframe the question a little bit. 00:06:26.760 |
is the subject that's concerned with the biggest questions 00:06:41.700 |
How should we even think about such questions? 00:06:45.980 |
And what do we even mean by it being determined? 00:07:01.020 |
well, then why be concerned with anything else, right? 00:07:04.500 |
Why not spend your whole life on those questions? 00:07:10.140 |
that is the right way to phrase the question. 00:07:13.580 |
And actually, what we learned, I mean, throughout history, 00:07:19.260 |
but really starting with the scientific revolution, 00:07:21.940 |
with Galileo and so on, is that there is a good reason 00:07:25.500 |
to focus on narrower questions, more technical, 00:07:33.620 |
And that is that you can actually make progress on them, 00:07:39.260 |
And sometimes they actually tell you something 00:07:43.820 |
that sort of maybe motivated your curiosity as a child. 00:07:58.140 |
that you have in the background from the very beginning 00:08:00.920 |
that you want to, these are sort of the reasons 00:08:05.480 |
why you went into intellectual life in the first place, 00:08:17.540 |
and hopefully even changing our understanding 00:08:23.260 |
sometimes even more than philosophy itself does. 00:08:26.420 |
- Why do you think computer scientists avoid these questions? 00:08:31.900 |
at least in the technical scientific discourse. 00:08:52.100 |
It was the one where he proposed the Turing test. 00:09:11.640 |
of disagreement and debates between Wittgenstein 00:09:32.560 |
is trying to say, well, all of these formal systems 00:09:51.160 |
to design a bridge, the bridge may collapse, right? 00:09:55.160 |
And so Turing, in some sense, is thinking decades ahead, 00:10:01.640 |
to where the formal systems are actually going to be used 00:10:05.080 |
in computers, right, to actually do things in the world. 00:10:15.360 |
and work on something of more immediate importance. 00:10:22.200 |
like the biggest possible step to actual engineering 00:10:26.440 |
- Yeah, and I would say more generally, right, 00:10:30.400 |
a lot of scientists are interested in philosophy, 00:10:39.480 |
and there are a lot of sort of very concrete questions 00:10:44.900 |
but look like they might be answerable, right? 00:10:47.960 |
And so then you could say, well, then why break your brain 00:10:52.920 |
over these metaphysically unanswerable questions 00:10:55.960 |
when there are all of these answerable ones instead? 00:11:06.280 |
I even go to philosophy conferences sometimes, 00:11:14.960 |
I would not want to be a professional philosopher 00:11:17.780 |
because I like being in a field where I feel like, 00:11:27.140 |
then I can actually make progress on something. 00:11:30.080 |
- Can you maybe link on that for just a little longer? 00:11:43.840 |
is if you want to ask philosophical questions, 00:11:46.220 |
then invite a real philosopher on and ask them. 00:11:54.640 |
and a philosopher ponders a philosophical question? 00:12:01.020 |
It's hard to make generalizations about entire fields. 00:12:21.860 |
You know, I mean, philosophers are really experts 00:12:24.160 |
in sort of, you know, like when I talk to them, 00:12:39.900 |
to a much greater extent than scientists would, right? 00:12:46.300 |
if you ask them about a philosophical problem, 00:12:53.540 |
they will try to relate it back to, you know, 00:13:03.860 |
that they personally are involved with, right? 00:13:07.980 |
of course they will want to talk about that, you know, 00:13:14.100 |
that maybe, you know, it's all interesting as it goes, 00:13:17.280 |
but maybe none of it touches the philosophical question. 00:13:20.660 |
But, you know, but maybe, you know, a science, 00:13:31.420 |
a deep dive into neurobiology will not answer 00:13:36.540 |
you know, maybe it can take us about as far as we can get 00:13:40.500 |
toward, you know, expanding our minds about it, 00:13:44.380 |
you know, toward thinking about it in a different way. 00:13:48.720 |
Well, I mean, I think neurobiology can do that, 00:13:51.040 |
but, you know, with these profound philosophical questions, 00:13:53.800 |
I mean, also art and literature do that, right? 00:14:00.240 |
we don't, for which we don't even know, really, 00:14:09.240 |
a beautiful mathematical way of discussing this 00:14:13.600 |
- You write that usually the only way to make progress 00:14:16.800 |
on the big questions, like the philosophical questions 00:14:31.380 |
so given an unanswerable philosophical riddle, Q, 00:14:39.060 |
scientific or mathematical question, Q prime, 00:14:41.920 |
which captures part of what people have wanted to know 00:14:49.920 |
So, you describe some examples of such Q prime sub-questions 00:15:04.560 |
on which you think theoretical computer science 00:15:12.920 |
- Well, yes, so I would say some of the most famous examples 00:15:33.880 |
And then he said, "Sorry, I think that question 00:15:36.600 |
"is too meaningless, but here's a different question. 00:15:47.960 |
he, in fact, just formulates the Q prime question. 00:15:56.180 |
Where you had these philosophers arguing for centuries 00:16:00.480 |
about the limits of mathematical reasoning, right? 00:16:25.740 |
that are not provable within the rules of the systems? 00:16:44.740 |
or to advocate doing something similar there for free will. 00:17:18.820 |
Taking it apart in the process of trying to predict them. 00:17:31.100 |
what is the computational substrate of the brain? 00:17:36.820 |
you know, just at the sort of level of the neurons? 00:17:39.340 |
You know, at sort of the abstraction of a neural network? 00:17:42.340 |
Or do you need to go deeper to the, you know, 00:17:44.900 |
molecular level, and ultimately even to the quantum level? 00:17:48.860 |
that would put limits on predictability if you did. 00:17:53.900 |
you need to reduce the mind to a computational device, 00:17:58.560 |
like formalize it so then you can make predictions about, 00:18:01.860 |
you know, whether you could predict the behavior of a system. 00:18:03.900 |
- Well, if you were trying to predict a person, 00:18:13.780 |
Can you make a model that will be accurate enough 00:18:16.740 |
to really seriously threaten people's sense of free will? 00:18:22.620 |
but like really, I have written in this envelope 00:18:28.940 |
So it's also a level of abstraction has to be right. 00:18:32.620 |
So if you're accurate at the, somehow at the quantum level, 00:18:37.620 |
that may not be convincing to us at the human level. 00:18:43.020 |
- Well, right, but the question is what accuracy 00:18:46.140 |
at the sort of level of the underlying mechanisms 00:18:49.020 |
do you need in order to predict the behavior, right? 00:18:54.300 |
can you, you know, foresee what the person is going to do? 00:19:06.300 |
very quickly dismiss that question as irrelevant. 00:19:11.700 |
Because, you know, if someone says, oh, well, you know, 00:19:14.900 |
a Laplace demon that knew the complete state of the universe, 00:19:19.900 |
you know, could predict everything you're going to do, 00:19:22.140 |
therefore you don't have free will, you know, 00:19:24.300 |
that it doesn't trouble me that much because, well, you know, 00:19:32.780 |
we even have some reasons to think, you know, 00:19:34.580 |
maybe, you know, it could not exist as part of our world. 00:19:37.260 |
You know, it was only an abstraction, a thought experiment. 00:19:40.740 |
On the other hand, if someone said, well, you know, 00:19:42.860 |
I have this brain scanning machine, you know, 00:19:47.180 |
every paper that you will ever write, it will write, 00:19:50.220 |
you know, every thought that you will have, you know, 00:19:52.420 |
even right now about the machine itself, it will foresee, 00:19:55.740 |
you know, well, if you could actually demonstrate that, 00:19:58.620 |
then I think, you know, that sort of threatens 00:20:11.620 |
We're asking, is such a machine possible or isn't it? 00:20:31.460 |
by which mechanism would enter the possibility 00:20:38.860 |
- Yeah, well, you could say the sort of obvious possibility, 00:20:45.660 |
and many others about as soon as quantum mechanics 00:20:48.060 |
was discovered in the 1920s, was that if, you know, 00:21:06.420 |
Hodgley-Huxkin equations in neuroscience, right, 00:21:14.820 |
Now, where does, you know, and this ultimately governs, 00:21:17.140 |
let's say, whether a neuron will fire or not fire, right? 00:21:27.820 |
and so you could ask, well, where does the randomness 00:21:30.500 |
in the process, you know, that neuroscientists, 00:21:34.100 |
or what neuroscientists would treat as randomness, 00:21:39.400 |
You know, ultimately, it's thermal noise, right? 00:21:51.460 |
a sort of butterfly effect, and so, you know, 00:22:02.840 |
that they would do one thing or do another thing, right? 00:22:05.460 |
I think that part is actually relatively uncontroversial, 00:22:08.580 |
right, the controversial question is whether any of it 00:22:12.380 |
matters for the sort of philosophical questions 00:22:17.220 |
if all it's doing is just injecting some randomness 00:22:20.400 |
into an otherwise completely mechanistic process, 00:22:25.180 |
And more concretely, if you could build a machine 00:22:28.500 |
that, you know, could just calculate even just 00:22:32.380 |
the probabilities of all of the possible things 00:22:48.180 |
- Exactly, I mean, to me, it seems essentially 00:22:51.120 |
just as bad as if the machine deterministically 00:23:02.360 |
could you even learn enough about someone's brain 00:23:11.240 |
is that making a measurement on a quantum state 00:23:15.160 |
is an inherently destructive operation, okay? 00:23:18.380 |
So, you know, if I want to measure the, you know, 00:23:24.140 |
well, before I measured, it had a superposition 00:23:35.300 |
And so you could say, well, maybe in trying to build 00:23:39.980 |
a model of someone's brain that was accurate enough 00:23:45.080 |
even well-calibrated probabilistic predictions 00:23:48.400 |
of their future behavior, maybe you would have 00:23:50.760 |
to make measurements that were just so accurate 00:23:53.180 |
that you would just fundamentally alter their brain, okay? 00:23:59.600 |
it would suffice to just make some nanorobots 00:24:02.440 |
that just measured some sort of much larger scale, 00:24:05.740 |
you know, macroscopic behavior, like, you know, 00:24:09.320 |
what is this neuron doing, what is that neuron doing? 00:24:24.640 |
- Yeah, but just as you said, that question may be 00:24:27.880 |
slightly detached from the philosophical question 00:24:30.500 |
in the sense if consciousness somehow has a role 00:24:36.080 |
Because ultimately, when we're talking about free will, 00:24:38.380 |
we're also talking about not just the predictability 00:24:46.460 |
- Yeah, well, I mean, a lot of philosophical questions 00:24:49.460 |
ultimately, like feedback to the hard problem 00:24:52.300 |
of consciousness, you know, and as much as you can try 00:24:57.200 |
And, you know, and there is a reason why people try 00:25:03.600 |
Democritus talked about the hard problem of consciousness, 00:25:13.900 |
And it's really not clear if there's been progress since 00:25:25.680 |
- Well, I mean, well, I mean, there is the whole question 00:25:35.960 |
And, you know, can it work in a completely different 00:25:40.420 |
I mean, you know, and of course that was Alan Turing's point 00:25:43.460 |
and, you know, and even if that was done, it's, you know, 00:25:46.260 |
maybe people would still argue about the hard problem 00:25:49.940 |
And yet, you know, my claim is a little different. 00:25:58.980 |
or where we'd been even overtaken by such AIs, 00:26:01.980 |
the entire discussion of the hard problem of consciousness 00:26:07.640 |
It would take place in different terms in such a world, 00:26:12.720 |
And my claim about free will would be similar, right? 00:26:15.620 |
That if this prediction machine that I was talking about 00:26:19.040 |
could actually be built, well, now the entire discussion 00:26:21.980 |
of the, you know, of free will is sort of transformed 00:26:27.340 |
the metaphysical question hasn't been answered. 00:26:32.940 |
It transforms it fundamentally because say that machine 00:26:37.620 |
and yet there is this deep experience of free will 00:26:40.100 |
and then that changes the question completely. 00:26:43.100 |
And it starts actually getting to the question of 00:26:58.500 |
Does that equal consciousness, intelligence, and free will? 00:27:02.280 |
- But see, Alex, if every time I was contemplating 00:27:06.820 |
a decision, you know, this machine had printed out 00:27:13.220 |
I think that actually would change my subjective experience 00:27:20.860 |
- Well, you know, I mean, the knowledge that this machine 00:27:25.020 |
I mean, it might drive me completely insane, right? 00:27:27.780 |
But at any rate, it would change my experience 00:27:30.700 |
to not just discuss such a machine as a thought experiment 00:27:39.120 |
- I mean, you know, you could say at that point, 00:27:43.920 |
why not simply call this machine a second instantiation 00:27:49.120 |
What, you know, why even privilege the original me 00:27:53.400 |
over this perfect duplicate that exists in the machine? 00:27:56.880 |
- Yeah, or there could be a religious experience with it too. 00:28:00.080 |
It's kind of what God throughout the generations 00:28:02.440 |
is supposed to have, that God kind of represents 00:28:05.400 |
that perfect machine, is able to, I guess, actually, 00:28:09.580 |
I don't even know, what are the religious interpretations 00:28:16.240 |
So if God knows perfectly everything in religion, 00:28:22.600 |
in the various religions, where does free will fit into that? 00:28:29.280 |
that theologians have argued about for thousands of years. 00:28:36.120 |
- So there's not a clear answer in a book like-- 00:28:38.880 |
- I mean, this is, you know, the Calvinists debated this, 00:28:46.120 |
have taken different positions on that question, 00:28:50.080 |
You know, meanwhile, you know, a large part of sort of 00:28:53.400 |
what animates, you know, theoretical computer science, 00:28:56.560 |
you could say, is, you know, we're asking sort of, 00:29:01.040 |
what you can know or, you know, calculate or figure out 00:29:05.480 |
by, you know, entities that you can actually build 00:29:09.700 |
And if I were trying to explain it to a theologian, 00:29:12.820 |
maybe I would say, you know, we are studying, you know, 00:29:16.440 |
gods can be made manifest in the physical world. 00:29:23.700 |
- So let's talk about quantum computers for a minute. 00:29:36.320 |
So there's this broad and deep aspect to quantum computing 00:29:40.280 |
that represents more than just the quantum computer. 00:29:47.680 |
- Yeah, so it's a proposal for a new type of computation, 00:29:52.680 |
or let's say a new way to harness nature to do computation 00:29:57.120 |
that is based on the principles of quantum mechanics. 00:30:00.200 |
Okay, now the principles of quantum mechanics 00:30:08.080 |
You know, what's new is, you know, how we wanna use them. 00:30:11.120 |
Okay, so what does quantum mechanics say about the world? 00:30:15.640 |
You know, the physicists, I think, over the generations, 00:30:18.560 |
you know, convinced people that that is an unbelievably 00:30:32.480 |
if you do what we do in quantum information theory 00:30:37.840 |
So the way that we think about quantum mechanics 00:30:45.700 |
So, you know, you might say there's a, you know, 00:30:48.920 |
there was a 30% chance that it was going to snow today 00:30:53.120 |
You would never say that there was a negative 30% chance, 00:30:57.880 |
Much less would you say that there was a, you know, 00:30:59.720 |
an i% chance, you know, square root of minus 1% chance. 00:31:04.200 |
Now, the central discovery that sort of quantum mechanics 00:31:09.200 |
made is that fundamentally the world is described by, 00:31:14.400 |
or you know, the sort of, let's say the possibilities 00:31:22.240 |
are described using numbers called amplitudes, okay, 00:31:34.900 |
In fact, they can even be complex numbers, okay? 00:31:37.760 |
And if you've heard of a quantum superposition, 00:31:45.760 |
one of these complex numbers to every possible 00:31:53.680 |
So for example, you might say that an electron 00:31:59.760 |
and some other amplitude for being there, right? 00:32:12.560 |
That happens by taking their squared absolute value, okay? 00:32:19.840 |
either the electron will be here or it will be there. 00:32:44.760 |
and that are, you know, alien to our everyday experience. 00:32:50.680 |
about the weirdness of the quantum world, you know, 00:32:53.280 |
or assuming that they're not lying to you, right? 00:33:06.120 |
is that they can interfere with each other, okay? 00:33:17.800 |
and you find that there, you know, on a second screen, 00:33:22.920 |
where that electron will never end up, you know, 00:33:32.700 |
then the electron can appear in that place, okay? 00:33:38.280 |
that the electron could take to get somewhere, 00:33:40.820 |
you can increase the chance that it gets there, okay? 00:33:45.420 |
Well, it's because, you know, as we would say now, 00:33:48.840 |
the electron has a superposition state, okay? 00:33:51.880 |
It has some amplitude for reaching this point 00:34:05.800 |
then, you know, I have to add them all up, right? 00:34:10.880 |
that the electron could have taken to reach this point. 00:34:26.460 |
then the amplitude is positive or it's negative 00:34:30.580 |
Okay, so that is sort of the one trick of quantum mechanics. 00:34:34.140 |
And now I can tell you what a quantum computer is, okay? 00:34:51.400 |
much faster than we know how to solve them otherwise. 00:34:54.520 |
So it's the basic building block of a quantum computer 00:35:00.200 |
That just means a bit that has some amplitude 00:35:02.600 |
for being zero and some other amplitude for being one. 00:35:06.120 |
So it's a superposition of zero and one states, right? 00:35:15.000 |
the rules of quantum mechanics are completely unequivocal 00:35:20.740 |
I don't just need amplitudes for each qubit separately. 00:35:26.360 |
for every possible setting of all thousand of those bits. 00:35:37.880 |
let's say in the memory of a conventional computer, 00:35:40.680 |
if I had to write down two to the 1,000 complex numbers, 00:35:44.000 |
that would not fit within the entire observable universe. 00:35:47.640 |
Okay, and yet, you know, quantum mechanics is unequivocal 00:35:51.120 |
that if these qubits can all interact with each other, 00:35:54.120 |
and in some sense, I need two to the 1,000 parameters, 00:35:58.280 |
you know, amplitudes to describe what is going on. 00:36:06.440 |
about quantum computing go off the rails is that they say, 00:36:12.200 |
and then they say, oh, so the way a quantum computer works 00:36:14.920 |
is just by trying every possible answer in parallel. 00:36:18.200 |
So, you know, that sounds too good to be true, 00:36:21.320 |
and unfortunately, it kind of is too good to be true. 00:36:31.280 |
you know, even if there were two to the 1,000 of them, 00:36:38.520 |
you've got, at some point, you've got to look at it 00:36:40.640 |
and see an output, right, and if I just measure 00:37:08.600 |
and you try to do it so that for each wrong answer, 00:37:11.680 |
some of the paths leading to that wrong answer 00:37:18.120 |
So on the whole, they cancel each other out, okay, 00:37:20.760 |
whereas all the paths leading to the right answer 00:37:25.800 |
should have amplitudes pointing the same direction. 00:37:43.320 |
that you've painted is information contained? 00:37:46.760 |
- Oh, well, information is at the core of everything 00:37:55.400 |
since, you know, Claude Shannon's paper in 1948, 00:38:06.120 |
- But a bit is zero or one, so that's the basic element. 00:38:10.480 |
is that the basic unit of quantum information is the qubit, 00:38:19.840 |
manipulated in a superposition of zero and one states. 00:38:37.000 |
There is, you know, superconducting quantum computing 00:38:41.520 |
because of Google's quantum supremacy experiment, right? 00:38:54.400 |
one representing a zero, another representing a one, 00:38:57.640 |
and if you cool these coils to just slightly above 00:39:17.800 |
It has a spin, it could be spinning clockwise, 00:39:23.240 |
or it could be in a superposition of the two spin states. 00:39:27.640 |
But see, just like in the classical world, right, 00:39:32.920 |
without having any idea of what a transistor is, right, 00:39:40.480 |
even that the machine uses electricity, right? 00:39:45.120 |
It's sort of the same with quantum computing, right? 00:39:51.440 |
and yet all of those systems will lead to the same logic, 00:40:01.560 |
And so, you know, the subject of how qubits behave 00:40:11.880 |
- So the physical design implementation of a qubit 00:40:14.640 |
does not interfere with that next level of abstraction 00:40:30.880 |
That's because all the quantum computers we can build today 00:40:41.080 |
And so the lower level sort of does affect the higher levels 00:40:44.120 |
and we sort of have to think about all of them at once. 00:40:49.360 |
is to what are called error-corrected quantum computers, 00:40:54.720 |
like perfect abstract qubits for as long as we want them to. 00:41:01.720 |
a future that we can already sort of prove theorems about 00:41:12.160 |
- So if noise is currently like the biggest problem 00:41:18.360 |
and then the dream is error-correcting quantum computers, 00:41:23.200 |
can you just maybe describe what does it mean 00:41:29.840 |
So yeah, so the problem is even a little more specific 00:41:35.400 |
if you're trying to actually build a quantum computer, 00:41:43.840 |
Okay, and this was recognized from the very beginning, 00:41:46.400 |
you know, when people first started thinking about this 00:41:53.160 |
the unwanted interaction between, you know, your qubits, 00:42:10.080 |
that's in a superposition of zero and one states 00:42:12.320 |
to ask it, you know, are you zero or are you one? 00:42:14.860 |
Well, now I force it to make up its mind, right? 00:42:21.000 |
And now, you know, it's no longer a superposition, 00:42:25.200 |
there's just, there's some probability that I get a zero 00:42:29.380 |
And now, the trouble is that it doesn't have to be me 00:42:36.440 |
Or in fact, it doesn't have to be any conscious entity. 00:42:39.140 |
Any kind of interaction with the external world 00:42:46.720 |
about whether this qubit was a zero or a one, 00:42:50.040 |
sort of that causes the zeroness or the oneness 00:42:56.340 |
the radiation in the room, in the molecules of the air, 00:43:00.560 |
in the wires that are connected to my device, any of that. 00:43:08.120 |
it is as if that qubit has been measured, okay? 00:43:11.120 |
It is, you know, the state has now collapsed. 00:43:15.240 |
You know, another way to say it is that it's become 00:43:19.480 |
But, you know, from the perspective of someone 00:43:23.600 |
it is as though it has lost its quantum state. 00:43:26.880 |
And so, what this means is that if I want to do 00:43:29.840 |
a quantum computation, I have to keep the qubits 00:43:33.680 |
sort of fanatically well isolated from their environment. 00:43:37.600 |
But then at the same time, they can't be perfectly isolated 00:43:42.680 |
I need to make them interact with each other, for one thing, 00:43:45.960 |
and not only that, but in a precisely choreographed way. 00:43:49.880 |
Okay, and, you know, that is such a staggering problem, 00:43:53.080 |
right, how do I isolate these qubits from the whole universe 00:43:58.920 |
I mean, you know, there were distinguished physicists 00:44:07.200 |
The laws of physics will just never let you control qubits 00:44:10.700 |
to the degree of accuracy that you're talking about. 00:44:17.740 |
was a profound discovery in the mid to late '90s, 00:44:22.340 |
which was called the theory of quantum error correction 00:44:27.740 |
And the upshot of that theory is that if I want to build 00:44:34.820 |
to, you know, an arbitrary number of as many qubits 00:44:37.540 |
as I want, you know, and doing as much on them as I want, 00:44:41.100 |
I do not actually have to get the qubits perfectly isolated 00:44:50.140 |
And even if every qubit is sort of leaking, you know, 00:45:00.580 |
I can sort of encode the information that I care about 00:45:05.060 |
in very clever ways across the collective states 00:45:08.460 |
of multiple qubits, okay, in such a way that even if, 00:45:11.980 |
you know, a small percentage of my qubits leak, 00:45:25.500 |
And so, you know, you can build a reliable quantum computer 00:45:46.740 |
that are not perfectly reliable, but reliable enough 00:45:50.700 |
that you can then use these error correcting codes 00:45:53.900 |
to have them simulate qubits that are even more reliable 00:46:02.820 |
And then once you reach that sort of crossover point, 00:46:08.340 |
could in turn simulate qubits that are even more reliable 00:46:13.740 |
effectively you have arbitrarily reliable qubits. 00:46:17.140 |
So long story short, we are not at that break-even point yet. 00:46:26.420 |
- But the key ingredient there is the more qubits, 00:46:32.220 |
the larger the computation you can do, right? 00:46:35.260 |
I mean, qubits are what constitute the memory 00:46:40.500 |
- But also for the, sorry, for the error correcting mechanism. 00:46:44.180 |
So the way I would say it is that error correction 00:46:50.420 |
And that is actually one of the biggest practical problems 00:47:18.060 |
Well, what that would take would be thousands of, 00:47:24.220 |
But now with the known error correcting codes, 00:47:26.620 |
each of those logical qubits would need to be encoded itself 00:47:38.140 |
quantum computers are not breaking cryptography already. 00:47:40.980 |
It's because of these immense overheads involved. 00:47:43.940 |
- So that overhead is additive or multiplicative? 00:47:47.580 |
I mean, it's like you take the number of logical qubits 00:47:51.960 |
that you need in your abstract quantum circuit, 00:47:56.860 |
So, you know, there's a lot of work on, you know, 00:48:04.300 |
In the meantime, we are now in what the physicist 00:48:08.660 |
John Preskill called the noisy intermediate scale 00:48:17.160 |
we're now entering the very early vacuum tube era 00:48:21.880 |
The quantum computer analog of the transistor 00:48:26.600 |
That would be like true error correction, right? 00:48:29.220 |
Where, you know, we are not, or something else 00:48:35.540 |
And, but where we are now, let's say as of a few months ago, 00:48:40.300 |
you know, as of Google's announcement of quantum supremacy, 00:48:45.860 |
where even with a non-error corrected quantum computer 00:48:51.420 |
we can do something that is hard for classical computers 00:48:58.740 |
Now, will we in this noisy era be able to do something 00:49:07.820 |
People are going to be racing over the next decade 00:49:10.620 |
to try to do that by people, I mean, Google, IBM, 00:49:14.700 |
you know, a bunch of startup companies, you know-- 00:49:18.660 |
- Yeah, and research labs and governments and yeah. 00:49:36.500 |
So how do we get to where we are now with the CPU? 00:49:49.260 |
that are needed on the computer science side? 00:49:53.180 |
What's, is it a financial issue where a much larger, 00:49:57.740 |
just sheer investment and excitement is needed? 00:50:01.180 |
- So, you know, those are excellent questions. 00:50:05.180 |
- Well, no, no, my guess would be all of the above. 00:50:09.420 |
I mean, my guess, you know, I mean, you know, 00:50:12.380 |
you could say fundamentally it is an engineering issue, 00:50:14.960 |
right, the theory has been in place since the '90s, 00:50:23.500 |
you know, we do not have the hardware that is at that level, 00:50:26.900 |
but at the same time, you know, so you could just, 00:50:32.700 |
maybe even like, you know, if someone spent a trillion 00:50:36.060 |
dollars on some quantum computing Manhattan project, 00:50:39.260 |
right, then conceivably they could just, you know, 00:50:46.580 |
as it was envisioned back in the '90s, right? 00:50:52.540 |
is that there will be further theoretical breakthroughs, 00:50:55.580 |
and there will be further insights that will cut down 00:51:00.100 |
- So let's take a brief step to the philosophical. 00:51:09.780 |
in the microprocessor world, and he's been told 00:51:18.180 |
is going to die this year, and he tries to argue 00:51:22.220 |
that the Moore's Law is still alive and well, 00:51:25.780 |
and it'll be alive for quite a long time to come. 00:51:33.860 |
but he thinks there's still a thousand X improvement 00:51:38.140 |
just on shrinking the transition, that's possible. 00:51:41.060 |
Whatever, the point is that the exponential growth we see 00:51:51.780 |
At the philosophical level, why do you think we, 00:51:56.380 |
as a descendants of apes, were able to just keep coming up 00:52:00.660 |
with these new breakthroughs on the CPU side? 00:52:03.620 |
Is this something unique to this particular endeavor, 00:52:18.380 |
I think we are in an extremely special period 00:52:22.620 |
I mean, it is, you could say, obviously special, 00:52:34.900 |
the whole future of the planet is in question 00:52:44.620 |
for the rest of human history, but, you know, 00:52:57.860 |
you could say, you know, the things that we call computers, 00:53:02.460 |
to simulate the behavior of whatever machine you want, 00:53:07.100 |
and, you know, and once you've sort of crossed 00:53:19.620 |
in the physical world, well, then the main questions 00:53:34.940 |
Quantum computing is the one thing that changes 00:53:38.700 |
But, you know, as long as it's classical computing, 00:53:44.740 |
And, you know, you could say at a theoretical level, 00:54:13.460 |
a huge fraction of sort of all of the technological progress 00:54:25.060 |
And so, you know, it has been one of the biggest 00:54:28.540 |
success stories in the history of technology, right? 00:54:32.940 |
I am as amazed by it as anyone else is, right? 00:54:36.820 |
But at the same time, you know, we also know that it, 00:54:48.580 |
Because you will reach, you know, fundamental limits 00:54:52.340 |
on, you know, how small you can possibly make a processor. 00:54:56.900 |
And, you know, if you want a real proof, you know, 00:54:59.140 |
that would justify my use of the word, you know, 00:55:01.460 |
we know that, you know, Moore's law has to end. 00:55:04.260 |
I mean, ultimately, you will reach the limits 00:55:10.940 |
if you tried to build a computer that operated 00:55:15.820 |
so it did 10 to the 43 operations per second, 00:55:20.980 |
that it would simply collapse to a black hole, okay? 00:55:27.420 |
we're going to reach the limits long before that. 00:55:34.700 |
- But it would be interesting to try to understand 00:55:38.380 |
the mechanism, the economic pressure that you said, 00:55:40.940 |
just like the Cold War was a pressure on getting us, 00:55:47.660 |
my us is both the Soviet Union and the United States, 00:55:53.660 |
to get, to hurry up to get to space, to the moon, 00:55:56.700 |
there seems to be that same kind of economic pressure 00:55:59.320 |
that somehow created a chain of engineering breakthroughs 00:56:07.760 |
- Yeah, well, I mean, some people are sort of, 00:56:10.780 |
get depressed about the fact that technological progress, 00:56:16.860 |
in many, many realms outside of computing, right? 00:56:21.460 |
we wanted flying cars and we only got Twitter instead, 00:56:29.020 |
So, then jumping to another really interesting topic 00:56:45.200 |
perhaps not so basic, what is quantum supremacy? 00:56:52.180 |
that was coined by, again, by John Preskill in 2012. 00:57:04.400 |
we don't, we sort of haven't found a better alternative. 00:57:08.360 |
- It's technically quantum computational supremacy. 00:57:10.600 |
- Yeah, yeah, supremacy, that's right, that's right. 00:57:15.520 |
all the way back to the beginnings of quantum computing 00:57:18.640 |
when Richard Feynman and David Deutch, people like that, 00:57:23.840 |
And quantum supremacy just refers to sort of the point 00:57:28.720 |
in history when you can first use a quantum computer 00:57:39.360 |
of the classical computers that are available, okay? 00:57:42.320 |
So, you know, notice that I did not say a useful task, okay? 00:57:46.360 |
You know, it could be something completely artificial, 00:57:49.120 |
but it's important that the task be well-defined. 00:57:53.680 |
it is something that has right and wrong answers, 00:57:56.600 |
you know, that are knowable independently of this device, 00:58:00.320 |
right, and we can then, you know, run the device, 00:58:06.080 |
You said much faster than a classical implementation. 00:58:12.840 |
with where the class, there's no, there's not, 00:58:15.200 |
it doesn't even exist a classical algorithm to-- 00:58:23.040 |
a classical computer can also eventually do, okay? 00:58:29.040 |
that a classical computer could always, you know, 00:58:35.600 |
it could always just store the entire quantum state, 00:58:41.320 |
right, store a list of all the amplitudes, you know, 00:58:47.320 |
and then just, you know, do some linear algebra 00:58:52.240 |
And so, so anything that quantum computers can do 00:59:00.720 |
- So quantum computers don't go to some magical place 00:59:03.840 |
outside of Alan Turing's definition of computation. 00:59:10.040 |
They cannot solve anything that is uncomputable 00:59:24.200 |
as well as been a central word in computer science, 00:59:27.040 |
but it's sort of a code word for something technical, 00:59:30.120 |
which is basically with polynomial scaling, you know, 00:59:36.880 |
you would like an algorithm that uses an amount of time 00:59:52.720 |
that there's probably several hours worth of conversation on 00:59:56.000 |
is complexity, which we probably won't even get a chance 00:59:58.400 |
to touch today, but you briefly mentioned it. 01:00:05.360 |
So you said the definition of quantum supremacy 01:00:08.680 |
is basically achieving a place where much faster 01:00:13.600 |
on a formal, that quantum computers much faster 01:00:16.560 |
on a formal, well-defined problem that is or isn't useful. 01:00:22.400 |
And I would say that we really want three things, right? 01:00:32.800 |
at just solving this, you know, well-defined, you know, 01:00:36.960 |
Secondly, we want it to be sort of, you know, 01:00:42.880 |
that a quantum computer has better scaling behavior, right? 01:00:51.240 |
as you went to larger and larger inputs, you know, 01:01:04.200 |
the actual observed speed up to only be explainable 01:01:10.720 |
So, you know, I want, you know, a real world, 01:01:16.640 |
let's say by a quantum computer with 50 qubits or so, 01:01:20.640 |
and for no one to be able to explain that in any way 01:01:37.180 |
would require keeping track of two to the 50th numbers, 01:01:42.560 |
- So the intuition is that then if you demonstrate 01:01:45.200 |
on 50 qubits, then once you get to 100 qubits, 01:02:06.680 |
is already enough by itself to refute the skeptics 01:02:11.000 |
who said a quantum computer will never outperform 01:02:15.320 |
- But one, how do you demonstrate quantum supremacy, 01:02:27.880 |
- Great, great questions, 'cause now you get into, 01:02:31.200 |
actually, you know, a lot of the work that I've, 01:02:35.840 |
for the last decade, which was precisely about 01:02:44.400 |
we thought would be available in the near future? 01:02:47.260 |
And so one of the main things that we realized 01:03:48.360 |
even, you know, assuming it's running perfectly, okay? 01:04:18.140 |
Or, you know, that you're trying to sample from. 01:04:20.140 |
Now, there are a lot of questions about this. 01:04:37.080 |
a randomly chosen sequence of operations, right? 01:04:40.400 |
So we, you know, we, and sometimes, you know, 01:04:56.600 |
and get another sample from that same distribution. 01:05:09.280 |
so if we're going to talk about Google's device, 01:05:14.200 |
And so there were two to the 53 power possible outputs. 01:05:20.480 |
there was a little bit more destructive interference 01:05:25.800 |
So their amplitudes were a little bit smaller. 01:05:35.240 |
and so those that were a little bit likelier, okay? 01:05:38.980 |
All of the outputs are exponentially unlikely, 01:05:42.320 |
but some are, let's say, two times or three times, 01:05:56.040 |
Now, the next question would be, well, how do you, 01:06:04.200 |
And so my students and I, and also the people at Google 01:06:09.200 |
were doing the experiment, came up with statistical tests 01:06:13.160 |
that you can apply to the outputs in order to 01:06:21.520 |
that at least that some hard problem is being solved. 01:06:32.960 |
And it's basically, you know, so the drawback of this test 01:06:50.880 |
is two to the 53? - It's about nine quadrillion. 01:07:04.400 |
back to that, it is just barely possible to run, 01:07:11.200 |
which is called Summit at Oak Ridge National Lab, okay? 01:07:27.120 |
we don't know how to verify the results, okay? 01:07:32.840 |
that the biggest classical computers on Earth 01:07:36.480 |
will have to sweat, and will just barely be able 01:07:43.240 |
using much more time, but they will still be able 01:07:45.920 |
to do it in order that we can verify the result. 01:08:01.880 |
that point will be passed, and then when you get 01:08:05.040 |
to larger numbers of qubits, then these types 01:08:08.920 |
of sampling experiments will no longer be so interesting, 01:08:12.280 |
because we won't even be able to verify the results, 01:08:15.060 |
and we'll have to switch to other types of computation. 01:08:17.880 |
So with the sampling thing, so the test that Google applied, 01:08:24.840 |
was basically just take the samples that were generated, 01:08:28.520 |
which are a very small subset of all the possible samples 01:08:32.360 |
that there are, but for those, you calculate, 01:08:35.200 |
with your classical computer, the probabilities 01:08:39.680 |
and you see, are those probabilities larger than the mean? 01:08:43.440 |
So is the quantum computer biased toward outputting 01:08:46.680 |
the strings that you want it to be biased toward? 01:08:50.440 |
Okay, and then, finally, we come to a very crucial question, 01:08:56.360 |
well, how do we know that a classical computer 01:09:01.400 |
How do we know that this couldn't have been spoofed 01:09:05.640 |
And so, well, the first answer is we don't know, for sure, 01:09:09.960 |
because this takes us into questions of complexity theory, 01:09:17.880 |
of the P versus NP question, and things like that, right? 01:09:23.640 |
that there could be fast classical algorithms 01:09:32.460 |
but we can give some evidence against that possibility, 01:09:36.280 |
and that was sort of the main thrust of a lot of the work 01:09:40.280 |
that my colleagues and I did over the last decade, 01:09:46.880 |
what led to Google deciding to do this experiment. 01:09:50.040 |
- So is the kind of evidence you, first of all, 01:09:53.200 |
the hard P equals NP problem that you mentioned, 01:09:55.960 |
and the kind of evidence that you were looking at, 01:10:00.920 |
is that something you come to on a sheet of paper, 01:10:03.880 |
or is this something, are these empirical experiments? 01:10:09.640 |
I mean, it's also, we have a bunch of methods 01:10:14.640 |
that are known for simulating quantum circuits, 01:10:20.160 |
or quantum computations with classical computers, 01:10:30.360 |
on these problems, and not just theoretically, 01:10:36.460 |
that are actually arising in Google's experiment. 01:10:40.420 |
Okay, so there is an empirical component to it, right? 01:10:56.240 |
that most of the problems we care about are hard, 01:10:58.960 |
but we know how to pass the blame to someone else. 01:11:06.480 |
but if it is easy, then all these other things 01:11:13.200 |
or were hard, then those would be easy as well, okay? 01:11:19.840 |
This has been the basic strategy in NP completeness, 01:11:24.400 |
right, in all of theoretical computer science, 01:11:31.120 |
And so we were able to give some reduction evidence 01:11:34.320 |
for the hardness of simulating these sampling experiments, 01:11:39.320 |
these sampling-based quantum supremacy experiments. 01:11:43.340 |
The reduction evidence is not as satisfactory 01:11:47.440 |
One of the biggest open problems in this area 01:11:57.560 |
a fast classical algorithm to spoof these experiments, 01:12:05.040 |
- Which is kind of in the same kind of space of reasoning 01:12:21.840 |
and presidential candidate with a lot of interesting ideas 01:12:45.160 |
Look, I'm actually, I'm a fan of Andrew Yang. 01:12:58.360 |
with the universal basic income and so forth, 01:13:09.560 |
to break cryptography, so the situation is this. 01:13:17.600 |
26 years ago, that really started quantum computing 01:13:28.280 |
then you could use it to efficiently find the prime factors 01:13:32.600 |
of huge numbers and calculate discrete logarithms 01:13:40.600 |
that are very, very special in character, right? 01:13:46.560 |
But it so happens that most of the public key cryptography 01:13:51.560 |
that we currently use to protect the internet 01:13:54.520 |
is based on the belief that these problems are hard. 01:14:00.080 |
scalable quantum computers, then that's no longer true. 01:14:07.040 |
there are two important points to understand here. 01:14:15.840 |
is very, very far from the kind of scalable quantum computer 01:14:25.920 |
But Google's device has 53 physical qubits, right? 01:14:32.800 |
you know, with any of the known error correction methods, 01:14:50.920 |
how great will the overhead be from the error correction? 01:14:55.320 |
But with the known codes, you're talking millions 01:14:58.960 |
of physical qubits and of a much higher quality 01:15:03.000 |
Okay, so, you know, I don't think that that is, 01:15:08.800 |
Although people who have secrets that, you know, 01:15:25.360 |
in the hope that eventually they'll be able to decode it 01:15:28.200 |
once quantum computers become available, okay? 01:15:30.880 |
So this brings me to the second point I wanted to make, 01:15:35.720 |
which is that there are other public key cryptosystems 01:15:39.560 |
that are known that we don't know how to break 01:15:45.640 |
And so there's a whole field devoted to this now, 01:15:48.640 |
which is called post-quantum cryptography, okay? 01:16:00.920 |
And there is already some push to try to migrate 01:16:09.960 |
to create standards for post-quantum cryptography, 01:16:14.160 |
which will be the first step in trying to get 01:16:16.600 |
every web browser and every router to upgrade, you know, 01:16:26.440 |
what we think is quantum secure cryptography. 01:16:48.960 |
if no, at least certainly if no one else knows 01:16:53.720 |
But eventually we think that we could migrate the internet 01:17:00.600 |
and then we'd be more or less back where we started. 01:17:11.080 |
The big, by the way, the biggest practical application 01:17:14.380 |
of quantum computing that we know about by far, 01:17:21.520 |
In order to, you know, learn about chemical reactions, 01:17:25.000 |
you know, design maybe new chemical processes, 01:17:32.920 |
new superconductors, all kinds of things like that. 01:17:38.800 |
that would be able to simulate the, you know, 01:17:46.960 |
for the kind of chemical reactions and that kind of work? 01:17:52.240 |
- Now you're asking a very, very current question, 01:17:57.920 |
People are going to be racing over the next decade 01:18:04.900 |
even with, you know, 100 or 200 qubit quantum computers 01:18:09.280 |
of the sort that we expect to be able to build 01:18:13.280 |
So that might be, you know, the first application 01:18:17.560 |
of quantum computing that we're able to realize, 01:18:20.280 |
you know, or maybe it will prove to be too difficult 01:18:23.280 |
and maybe even that will require fault tolerance 01:18:30.580 |
with the one case study, kind of like with Peter Shor, 01:18:39.220 |
we can actually do something very useful here. 01:18:41.940 |
- Right, but I think, you know, within the next decade, 01:18:44.340 |
the best shot we have is certainly not, you know, 01:18:47.380 |
using Shor's algorithm to break cryptography, you know, 01:18:55.880 |
The best shot we have is to do some quantum simulation 01:19:00.020 |
that tells the material scientists or chemists 01:19:09.180 |
You know, and you might only need one or two successes 01:19:14.780 |
Like, you know, the way that people make fertilizer 01:19:17.580 |
right now is still based on the Haber-Bosch process 01:19:24.300 |
quantum mechanics problem that no one really understands. 01:19:27.080 |
Right, if you could design a better way to make fertilizer, 01:19:30.640 |
right, that's, you know, billions of dollars right there. 01:19:36.160 |
that people are going to be aggressively racing toward 01:19:40.220 |
Now, I don't know if they're gonna realize it or not, 01:19:42.640 |
but, you know, they certainly at least have a shot. 01:19:46.360 |
So it's gonna be a very, very interesting next decade. 01:20:04.320 |
- Yeah, so I can tell you what the current studies 01:20:07.480 |
are saying, you know, I think probably better 01:20:14.080 |
But, you know, there was a group at Microsoft 01:20:23.840 |
you know, you could already learn something new 01:20:26.180 |
about the chemical reaction that makes fertilizer, 01:20:30.960 |
The trouble is they're talking about 100 qubits 01:20:43.100 |
- So the logical qubits as you mentioned before. 01:20:47.580 |
And now, you know, the hard part for the next decade 01:21:05.100 |
- Yeah, so people are gonna be pushing simultaneously 01:21:09.920 |
One direction, of course, is just making the qubits better. 01:21:14.300 |
And, you know, there is tremendous progress there. 01:21:31.780 |
you know, let's say lower overhead error correcting codes. 01:21:36.220 |
And even short of doing the full recursive error correction, 01:21:40.340 |
you know, there are these error mitigation strategies 01:21:43.480 |
that you can use, you know, that may, you know, 01:21:47.060 |
allow you to eke out a useful speed up in the near term. 01:21:54.820 |
the quantum algorithms for simulating quantum chemistry 01:22:07.980 |
And so when, you know, I quoted these estimates, 01:22:13.380 |
And so, you know, I hope that because people will care enough 01:22:18.900 |
- So you're one of the world-class researchers in this space. 01:22:35.980 |
You just, you put a lot of-- - You're too kind. 01:22:40.260 |
You put a lot of efforts sort of to communicating 01:22:47.980 |
exposing some of the BS and sort of the natural, 01:22:52.220 |
just like in the AI space, the natural charlatanism, 01:22:56.820 |
if that's a word, in this, in quantum mechanics in general, 01:23:03.020 |
Can you give some notes about people or ideas 01:23:26.980 |
Unfortunately, quantum computing is a little bit like 01:23:35.780 |
that is genuinely revolutionary and exciting. 01:23:52.340 |
I would say that the main way that people go astray 01:23:56.420 |
is by not focusing on sort of the question of, 01:24:05.140 |
And so people have like dismissed quantum supremacy 01:24:12.300 |
Or it's not itself, let's say, obviously useful for anything. 01:24:16.380 |
Okay, but ironically, these are some of the same people 01:24:26.260 |
and financial optimization and all these things. 01:24:32.140 |
but their entire spiel is sort of counting on 01:24:39.060 |
but how well could a classical computer do the same thing? 01:24:46.420 |
they say, well, a quantum computer can do this, 01:24:55.060 |
are you getting a speed up over a classical computer or not? 01:25:01.220 |
Have you really thought carefully about classical algorithms 01:25:10.100 |
that companies and investors are most excited about, 01:25:27.180 |
And the problem with that is that since the very beginning, 01:25:50.860 |
And what it can do is it can solve many, many of the problems 01:25:54.460 |
that arise in AI, machine learning, optimization, 01:26:00.780 |
But it can solve them in about the square root 01:26:03.540 |
of the number of steps that a classical computer 01:26:08.260 |
Now a square root speed up is important, it's impressive. 01:26:17.780 |
that let's say Shor's algorithm for factoring is, 01:26:20.820 |
or for that matter, that simulation of quantum mechanics is, 01:26:30.380 |
of the optimization problems that you could handle, right? 01:26:33.380 |
And so, because people found that, I guess, too boring 01:26:38.380 |
or too unimpressive, they've gone on to invent 01:26:49.380 |
you can just project your hopes onto them, right? 01:26:52.500 |
That well, maybe it gets an exponential speed up. 01:27:03.220 |
of that kind of thing, and a really worrying amount 01:27:11.780 |
that those of us in this field know perfectly well 01:27:20.620 |
show that there's a speed up over the classical. 01:27:24.380 |
- And in this space that you're referring to, 01:27:27.660 |
is the area that a lot of people are excited about 01:27:34.700 |
I know that there's a lot of smoke currently, 01:27:40.300 |
might be breakthroughs where you do get exponential 01:28:07.460 |
a super exciting candidate for an exponential 01:28:12.340 |
quantum speed up for a machine learning problem 01:28:19.100 |
The problem of recommending products to users 01:28:22.380 |
given some sparse data about their preferences. 01:28:25.540 |
Karunidas and Prakash in 2016 had an algorithm 01:28:29.500 |
for sampling recommendations that was exponentially faster 01:28:40.140 |
I had an 18 year old undergrad by the name of Yilin Tang. 01:28:55.620 |
would need to access exponentially more data? 01:29:01.740 |
this was not like a P versus NP type of question. 01:29:10.620 |
Eventually she figured out why she couldn't do it. 01:29:18.220 |
with a similar performance to the quantum algorithm. 01:29:30.260 |
a bunch of the other quantum machine learning algorithms 01:29:33.100 |
that were proposed have now also been de-quantized. 01:29:54.380 |
well, you know, there's a silver lining in this cloud. 01:29:57.100 |
They say, well, thinking about quantum computing 01:30:01.100 |
of potentially useful new classical algorithms. 01:30:04.780 |
- Right, and so you get these spinoff applications, 01:30:09.380 |
you really have to think carefully about that. 01:30:11.940 |
You know, Yilin's work was a perfect illustration of why. 01:30:29.420 |
Not only do I ardently support people thinking about that, 01:30:37.780 |
and have my students and postdocs think about it, 01:30:45.540 |
and the problem comes when so many of the companies 01:30:49.460 |
and journalists in this space are pretending that. 01:31:00.700 |
Let me ask the most absurdly philosophical last question. 01:31:19.060 |
trying to discover new things about the world 01:31:52.260 |
And you know, it's depressing that I can't do more 01:31:54.660 |
and that, you know, the world is facing crises 01:32:05.700 |
but you know, trying to stand against the things 01:32:17.540 |
- Well, yeah, I guess your question just did, I don't know. 01:32:28.580 |
We'll probably talk to you for many more hours, Scott. 01:32:34.500 |
- Thank you for listening to this conversation 01:32:37.260 |
and thank you to our presenting sponsor, Cash App. 01:32:40.340 |
Download it, use code LEGSPODCAST, you'll get $10, 01:32:45.620 |
an organization that inspires and educates young minds 01:32:48.620 |
to become science and technology innovators of tomorrow. 01:32:51.940 |
If you enjoy this podcast, subscribe on YouTube, 01:32:57.620 |
or simply connect with me on Twitter @LexFriedman. 01:33:03.860 |
from a funny and insightful blog post Scott wrote 01:33:07.300 |
over 10 years ago on the ever-present Malthusianisms 01:33:17.060 |
of first lamenting how badly something sucks, 01:33:19.780 |
then only much later having the crucial insight 01:33:28.100 |
Thank you for listening, I hope to see you next time.