Lex Fridman PodcastScott Aaronson: Quantum Computing | Lex Fridman Podcast #72
EVERY SPOKEN WORD
150 min read · 30,095 words- 0:00 – 5:07
Introduction
- LFLex Fridman
The following is a conversation with Scott Aaronson, a professor at UT Austin, director of its Quantum Information Center, and previously a professor at MIT. His research interests center around the capabilities and limits of quantum computers and computational complexity theory more generally. He is an excellent writer and one of my favorite communicators of computer science in the world. We only had about an hour and a half for this conversation, so I decided to focus on quantum computing, but I can see us talking again in the future on this podcast at some point about computational complexity theory and all the complexity classes that Scott catalogs in his amazing Complexity Zoo Wiki. As a quick aside, based on questions and comments I've received, my goal with these conversations is to try to be in the background, without ego, and do three things. One, let the guest shine and try to discover together the most beautiful insights in their work and in their mind. Two, try to play devil's advocate just enough to provide a creative tension in exploring ideas through conversation. And three, to ask very basic questions about terminology, about concepts, about ideas. Many of the topics we talk about in the podcast, I've been studying for years as a grad student, as a researcher, and generally as a curious human who loves to read. But frankly, I see myself in these conversations as the main character from one of my favorite novels by Dostoevsky called The Idiot. I enjoy playing dumb. Clearly, it comes naturally. But the basic questions don't come from my ignorance of the subject, but from an instinct that the fundamentals are simple, and if we linger on them from almost a naive perspective, we can draw an insightful thread from computer science to neuroscience, to physics, to philosophy, and to artificial intelligence. This is the Artificial Intelligence Podcast. If you enjoy it, subscribe on YouTube, give it five stars on Apple Podcasts, support it on Patreon, or simply connect with me on Twitter @LexFridman, spelled F-R-I-D-M-A-N. As usual, I'll do one or two minutes of ads now and never any ads in the middle that can break the flow of the conversation. I hope that works for you and doesn't hurt the listening experience. Quick summary of the ads. Two supporters today. First, get Cash App and use the code LEXPODCAST. Second, listen to the Tech Meme Ride Home Podcast for tech news. Search "Ride Home," two words, in your podcast app. This show is presented by Cash App, the number one finance app in the App Store. When you get it, use code LEXPODCAST. Cash App lets you send money to friends, buy Bitcoin, and invest in the stock market with as little as $1. Broker services are provided by Cash App Investing, a subsidiary of Square and member SIPC. Since Cash App does fractional share trading, let me mention that the order execution algorithm that works behind the scenes to create the abstraction of fractional orders is an algorithmic marvel. So big props to the Cash App engineers for solving a hard problem that, in the end, provides an easy interface that takes a step up to the next layer of abstraction over the stock market, making trading more accessible for new investors and diversification much easier. So again, if you get Cash App from the App Store or Google Play and use the code LEXPODCAST, you'll get $10 and Cash App will also donate $10 to FIRST, one of my favorite organizations that is helping to advance robotics and STEM education for young people around the world. This episode is also supported by the Tech Meme Ride Home Podcast. It's a technology podcast I've been listening to for a while and really enjoying. It goes straight to the point, gives you the tech news you need to know, and provides minimal but essential context. It's released every day by 5:00 PM Eastern and is only about 15 to 20 minutes long. For fun, I like building apps on smartphones, mostly on Android, so I'm always a little curious about new flagship phones that come out. I saw that Samsung announced the new Galaxy S20, and of course, right away, Tech Meme Ride Home has a new episode that summarizes all that I needed to know about this new device. They've also started to do weekend bonus episodes with interviews of people like AOL founder Steve Case on investing and Gary Marcus on AI, who I have also interviewed on this podcast. You can find the Tech Meme Ride Home Podcast if you search your podcast app for "Ride Home," two words. Then subscribe, enjoy, and keep up to date with the latest tech news. And now here's my conversation with Scott Aaronson.
- 5:07 – 29:27
Role of philosophy in science
- LFLex Fridman
I sometimes get criticism from a listener here and there that while having a conversation with a world-class mathematician, physicist, neurobiologist, aerospace engineer, or a theoretical computer scientist like yourself, I waste time by asking philosophical questions about free will, consciousness, mortality, love, nature of truth, super intelligence, whether time travel is possible, whether space-time is emergent or fundamental. Uh, even the crazier questions like whether aliens exist, what their language might look like, what their math might look like, whether math is invented or discovered, and of course whether we live in a simulation or not. So I try to- Out with it. (laughs) Out with it. I try to dance back and forth from the deep technical- Mm-hmm. ... to the philosophical. So I've, I've done that quite a bit. Mm-hmm. So you're a world-class computer scientist, and yet you've written about this very point that philosophy is important for experts in, uh, any technical discipline, though they somehow seem to avoid this.So, I thought it'd be really interesting to talk to you about this point. Why should we computer scientists, mathematicians, physicists care about philosophy, do you think?
- SAScott Aaronson
Well, I would reframe the question a little bit. I mean, eh, philosophy almost by definition is, eh, the subject that's, eh, concerned with the biggest questions that you could possibly ask. Right? So, you know, eh, the ones you mentioned, right? Are, are we living in a simulation? Uh, uh, you know, are we alone in the universe? How should we even think about such questions? You know, is the future determined, and what, you know, what do we even mean by it being determined? Uh, why are we alive at the time we are and not at some other time? You know, and- and- and, uh, you know, when you- when you sort of contemplate the enormity of those questions, I think, you know, you could ask, "Well then why- why be concerned with anything else?" Right? "Why, uh- uh, why not spend your whole life on those questions?" You know, and I think- I think in- in some sense, that is the- the right que- uh, way to phrase the question. And, you know, and- and- and- and actually, you know, what- what we learned, you know, I mean, throughout history but really starting with the scientific revolution with Ga- you know, Galileo and so on, is that there is a good reason to, you know, focus on, uh, narrower questions. You know, more, uh, technical, you know, mathematical or empirical questions, and that is that you can actually make progress on them, right? And you can actually, uh, often answer them, and sometimes they actually tell you something about the philosophical questions that sort of, you know, maybe motivated your curiosity as a child, right? You know, they don't necessarily resolve the philosophical questions, but sometimes they reframe your whole understanding of them, right? And so for me, philosophy is just a thing that you have in the background from the very beginning, that you want to, uh- uh, you know, you know, the- these are- these are sort of the reasons why you went into intellectual life in the first place. At least the reasons why I did, right? Uh, uh, but you know, uh- uh, math and science are tools that we have for, you know, actually making progress. And, you know, hopefully even, you know, changing our understanding of these philosophical questions, sometimes even more than philosophy itself does.
- LFLex Fridman
Wh- why do you think computer scientists avoid these questions? Or run away-
- SAScott Aaronson
Hm.
- LFLex Fridman
... from them a little bit, at least in, uh-
- SAScott Aaronson
Mm-hmm.
- LFLex Fridman
... technical scientific discourse?
- SAScott Aaronson
Well, I'm- I'm not- I'm not sure if they do so more than any other scientist though.
- LFLex Fridman
Ah.
- SAScott Aaronson
I mean- I mean-
- LFLex Fridman
Yeah, right.
- SAScott Aaronson
Uh, I mean- I mean- I mean, Alan Turing was famously, you know, interested and, you know, his- his, uh, uh, most famous, uh, one of his two most famous papers was in a philosophy journal, Mind. You know, it was the one where he proposed the Turing test. Uh, he, uh- uh, took, uh- uh, Wittgenstein's course at Cambridge, you know, argued with him.
- NANarrator
(laughs)
- LFLex Fridman
I just recently learned that-
- SAScott Aaronson
And, uh-
- LFLex Fridman
... that little bit, and it's actually fascinating.
- SAScott Aaronson
Hm.
- LFLex Fridman
Um, I- I- I was- I was trying to look for resources in, uh, trying to understand where the sources of disagreement and debates between Wittgenstein and, uh, Turing were.
- SAScott Aaronson
Mm-hmm, mm-hmm.
- LFLex Fridman
'Cause it's interesting that these two minds have somehow met in the arc of history.
- SAScott Aaronson
Yeah, well- well- well, the- the transcript, you know, of their, uh- uh- uh, the course which was in 1939, right, is one of the more fascinating documents that I've ever read because, you know, uh, uh, Wittgenstein is- is trying to say, "Well, all of these- these formal systems are just, uh- uh- uh- uh- uh- uh- uh- um, com- complete irrelevancies," right? If a formal system is irrelevant, who cares, you know? Why does that matter in real life, right? And Turing is saying, "Well, look, you know, if you use an inconsistent formal system to design a bridge, you know, the bridge may- may collapse," right? (laughs) And you know, so- so Turing in some sense is thinking decades ahead, you know, uh, I think of- of where Wittgenstein is, to where the formal systems are actually going to be used, you know, in computers, right?
- LFLex Fridman
Right.
- SAScott Aaronson
To actually do things in the world. You know, and- and- and it's interesting that Turing actually dropped the course halfway through. Why? Because he had to go to Bletchley Park and, you know, work on something of more immediate importance. (laughs) Yeah.
- LFLex Fridman
That's fascinating. Take- take a step from philosophy to actual, like the-
- SAScott Aaronson
Yeah.
- LFLex Fridman
... biggest possible step to actual engineering with-
- SAScott Aaronson
Yeah.
- LFLex Fridman
... actual real impact.
- SAScott Aaronson
Yeah, and- and- and I- I would say more generally, right, uh- uh- uh, you know, a lot of scientists are, you know, uh- uh- uh, interested in philosophy, but they're also busy, right? And they have, you know, a lot on their plate, and there are a lot of sort of very concrete questions that are already, you know, not answered but, you know, look like they might be answerable, right? And so then you could say, uh- uh, "Well then why, you know, uh, break your brain over these, you know, metaphysically unanswerable questions when there are all of these answerable ones instead?" Uh, so I think, um, you know, for a- a- a- a- a- for me, uh, I- I enjoy talking about philosophy. I even go to philosophy conferences sometimes, uh, such as the, you know, FQXi conferences. I, uh, enjoy interacting with philosophers. I would not want to be a professional philosopher, because I like being in a field where I feel like, you know, uh- uh- um, you know, if- if, uh- uh, I get too confused about the sort of eternal questions, then I can actually make progress on something. (laughs)
- LFLex Fridman
Can you maybe linger-
- 29:27 – 41:12
What is a quantum computer?
- SAScott Aaronson
- LFLex Fridman
As you've said-
- SAScott Aaronson
Mm-hmm.
- LFLex Fridman
... quantum computing, at least in the 1990s, was a profound story at the intersection of computer science, physics, engineering, math and philosophy. So the- there's this broad and deep aspect to quantum computing that represents more-
- SAScott Aaronson
Mm-hmm.
- LFLex Fridman
... than just the quantum computer.
- SAScott Aaronson
Yes.
- LFLex Fridman
But can we start at the very basics?
- SAScott Aaronson
Mm-hmm.
- LFLex Fridman
What is quantum computing?
- SAScott Aaronson
Yeah. So it's a proposal for a, uh, new type of computation, or let's say a new way to harness nature to do computation, uh, that is based on the principles of quantum mechanics. Okay? Now, the principles of quantum mechanics have been in place since 1926. You know, they haven't changed. Uh, you know, what's new is, you know, how we wanna use them. Okay, so what does quantum mechanics say about the world? You know, the, the physicists, I think over the generations, you know, convinced people that that is an unbelievably complicated question, and you know-
- LFLex Fridman
Right.
- SAScott Aaronson
... just give up on trying to understand it. Uh, I can let you in... Not, uh, not being a physicist, I can let you in on a secret...
- LFLex Fridman
Okay.
- SAScott Aaronson
... which is that it becomes a lot simpler, uh, if you do what we do in quantum information theory, and sort of take the physics out of it. (laughs) So, uh, uh, the way that we think about quantum mechanics is sort of as a generalization of the rules of probability themselves. So, um, you know, you might say there's a, you know, there was a, a 30% chance that it was going to snow today or something. You would never say that there was a negative 30% chance, right? That would be nonsense, uh, much less would you say that there was a, you know, an I% chance, you know, a square root of minus 1% chance. Uh, now the central discovery that, uh, sort of quantum mechanics, uh, uh, made is that, uh, uh, uh, fundamentally, the world is described by, uh, uh, um...... or, you know, the, the sort of, let's say, the possibilities for, for, you know, what a system could be doing are, uh, described using numbers called amplitudes, okay, which are like probabilities in some ways, but they are not probabilities. They can be positive, for one thing, they can be positive or negative. In fact, they can even be complex numbers. Okay, and if you've heard of a quantum superposition, this just means the, uh, some state of affairs where you assign an amplitude, one of these complex numbers, to every possible, uh, s-, uh, uh, configuration that you could see a system in on measuring it. So for example, you might say that, uh, an electron has some amplitude for being here and some other amplitude for being there, right? Now, if you look to see where it is, you will localize it, right? You will sort of force the amplitudes to c- be converted into probabilities. That happens by taking their squared absolute value, okay? And then, and, and, uh, uh, uh, and then, you know, y- e- e- you can say either the electron will be here or it will be there. And, you know, knowing the amplitudes, you can predict the pro- at least the probabilities that it will... that you'll see each possible outcome, okay? But while a system is isolated from the whole rest of the universe, the rest of its environment, uh, the amplitudes can change in time by rules that are, uh, uh, different from the, the, the normal rules of probability and that are, you know, alien to our everyday experience. So any time anyone ever tells you anything about the weirdness of the quantum world, you know, or, uh, assuming that they're not lying to you, right, they are telling you s- you know, an- yet another consequence of nature being, uh, described by these amplitudes. So most famously, what amplitudes can do is that they can interfere with each other, okay? So, uh, in the famous double-slit experiment, what happens is that you shoot a particle, like an, an electron, let's say, at a screen with two slits in it, and you find that there a- you know, on a second screen, now there are certain places where that electron will never end up, you know, after, uh, uh, uh, uh, uh, it passes through the first screen. And yet, if I close off one of the slits, then the electron can appear in that place, okay? So by, so by decreasing the number of paths that the electron could take to get somewhere, you can increase the chance that it gets there, okay? Now, how is that possible? Well, it's because we, you know, as we would say, uh, now, the electron, uh, has a superposition state, okay? It has some amplitude for reaching this point by going through the first slit. It has some other amplitude for reaching it by going through the second slit. But now if one amplitude is positive and the other one is negative, then th- you know, I have to add them all up, right? I have to add the amplitudes for every path that the electron could have taken to reach this point. And tho- those amplitudes, if they're pointing in different directions, they can cancel each other out.
- LFLex Fridman
Mm-hmm.
- SAScott Aaronson
That would mean the total amplitude is zero and the thing never happens at all. I close off one of the possibilities, then the amplitude is positive or it's negative, and now the thing can happen. Okay, so that is sort of the one trick of quantum mechanics. And now I can tell you what a quantum computer is.
- LFLex Fridman
(laughs)
- SAScott Aaronson
Okay? A quantum computer is a, uh, a, a computer that tries to exploit, you know, these, exactly these phenomena, superposition, amplitudes, and interference, in order to solve certain problems much faster than we know how to solve them otherwise. So it's the basic building block of a quantum computer, is what we call a quantum bit or a qubit. That just means a bit that has some amplitude for being zero and some other amplitude for being one, so it's a superposition of zero and one states, right? But now, the key point is that if I've got, let's say, 1,000 qubits, the rules of quantum mechanics are completely unequivocal that I do not just need one amplit- you know, I don't just need amplitudes for each qubit separately, okay? In general, I need an amplitude for every possible setting of all thousand of those bits, okay? So that, what that means is two to the 1,000 power amplitudes, okay? If I, if I had to write those down, let's, or let's say in the memory of a conventional computer, if I had to write down two to the 1,000 complex numbers, that would not fit i- within the entire observable universe, okay? And yet, you know, quantum mechanics is unequivocal that if these qubits can all interact with each other, then in some sense, I need two to the 1,000 parameters, you know, amplitudes to describe what is going on. Now, you know, now I can tell you, you know, w- where all the popular articles, you know, about quantum computing go off the rails is that they say, you know, they, they sort of, sort of say what I just said, and then they say, "Oh, so the way a quantum computer works is just by trying every possible answer in parallel." You know?
- LFLex Fridman
(laughs) Right.
- SAScott Aaronson
You know, you know, and that, that sounds too good to be true, and unfortunately, it kind of is too good to be true. Uh, the, the problem is I could c- make a superposition over every possible answer to my problem, you know, even if there were two to the 1,000 of them, right? I can, I can easily do that. The trouble is, for a computer to be useful, you've got to, at some point, you've got to look at it and see, and see an output, right?
- LFLex Fridman
Mm-hmm.
- SAScott Aaronson
And if I just measure a superposition over every possible answer, then the rules of quantum mechanics tell me that all I'll see will be a random answer, you know? If I just wanted a random answer, well, I could have picked one myself with a lot less trouble, right?
- LFLex Fridman
(laughs) Yeah.
- SAScott Aaronson
So the entire trick with quantum computing, with every algorithm for a quantum computer, is that you try to choreograph a pattern of interference of amplitudes, and you try to do it so that for each wrong answer, some of the paths leading to that wrong answer have positive amplitudes and others have negative amplitudes. So on the whole, they cancel each other out, okay? Whereas all the paths leading to the right answer should reinforce each other, you know, should have amplitudes pointing the same direction.
- LFLex Fridman
So the design of algorithms in this space-
- SAScott Aaronson
Mm-hmm.
- LFLex Fridman
... is the choreography of the interferences?
- SAScott Aaronson
Precisely.
- LFLex Fridman
Yeah.
- 41:12 – 49:22
Quantum decoherence (noise in quantum information)
- SAScott Aaronson
- LFLex Fridman
So if, if noise is currently like, the-
- SAScott Aaronson
Yeah.
- LFLex Fridman
... biggest problem for quantum computing-
- SAScott Aaronson
Mm-hmm.
- LFLex Fridman
... and then the dream is, uh, error-correcting-
- SAScott Aaronson
Mm-hmm.
- LFLex Fridman
... quantum computers-
- SAScott Aaronson
Yes.
- LFLex Fridman
... can you just maybe describe what does it mean for there to be noise in the system?
- SAScott Aaronson
Absolutely. So, yeah. So the problem is even a little more specific than noise. So the, the fundamental problem, if you're trying to actually build a quantum computer, you know, of, of, of, of any appreciable size, is, uh, something called decoherence. Okay? And this was recognized from the very beginning, you know, when people first started thinking about this in the 1990s. Now, what decoherence means is sort of the unwanted interaction between, you know, your qubits, you know, the state of your quantum computer, and the external environment. Okay? And why is that such a problem? Well, I s- talked before about how, you know, when you measure a quantum system, so let's say if I measure a qubit, uh, that's in a superposition of zero and one states to ask it, you know, "Are you zero or are you one?" Well, now I force it to make up its mind, right? And now, probabilistically, it chooses one or the other. And now, you know, it's no longer a superposition, there's no longer amplitudes. There's just, there's some probability that I get a zero, and there's some that I get a one. Um, uh, now, the, the, the, the, the, the trouble is that it doesn't have to be me who's looking, okay? Or in fact, it doesn't have to be any conscious entity. Uh, uh, any kind of interaction with the external world that leaks out the information about whether this qubit was a zero or a one, sort of that causes the zeroness or the oneness of the qubit to be recorded in, you know, the radiation in the room, in the molecules of the air, in the, uh, uh, wires that are connected to my device, any of that, uh, uh, uh, as soon as the information leaks out, it is as if that qubit has been measured. Okay? It is, um, you know, the, the, the state has now collapsed. Uh, you know, another way to say it is that it's become entangled with its environment. Okay? But, you know, from the perspective of someone who's just looking at this qubit, it's, it is as though it has lost its quantum state. And so, what this means is that if I want to do a quantum computation, I have to keep the qubits sort of fanatically well isolated from their environment. But then at the same time, they can't be perfectly isolated, because I need to tell them what to do. I need to make them interact with each other-
- LFLex Fridman
Mm-hmm.
- SAScott Aaronson
... for one thing, and not only that, but in a precisely choreographed way. Okay? And, you know, that is such a staggering problem, right? How do I isolate these qubits from the whole universe, but then also tell them exactly what to do? I mean, you know, there were distinguished physicists and computer scientists in the '90s who said, "This is fundamentally impossible." You know? "The laws of physics will just never let you control qubits to the degree of accuracy that you're talking about." Um, now, what changed-... the views of most of us was a profound discovery in the, uh, mid to late '90s, uh, which was called the theory of quantum error correction and quantum fault tolerance. Okay? And the upshot of that theory is that if I want to build a reliable quantum computer and scale it up to, you know, an arbitrary number of as many qubits as I want, you know, and doing as much on them as I want, um, I do not actually have to get the qubits perfectly isolated from their environment. It is enough to get them really, really, really well isolated. Okay? And even if every qubit is sort of leaking, you know, its state into the environment at some rate, as long as that rate is low enough, okay, I can sort of encode the information that I care about a c- uh, in very clever ways across the collective states of multiple qubits, okay, in such a way that even if, you know, s- a small percentage of my qubits leak, while I'm constantly monitoring them to see if that leak happened, I can detect it, and I can correct it. I can recover the information I care about from the remaining qubits. Okay? And, uh, uh, so, you know, you can build a reliable quantum computer even out of unreliable parts, right? Now, the, the, um ... in some sense, you know, that discovery is what set the engineering agenda for quantum computing research from the 1990s until the present. Okay? The goal has been, you know, engineer qubits that are not perfectly reliable, but reliable enough that you can then use these error-correcting codes to have them simulate qubits that are even more reliable than they are, right?
- LFLex Fridman
Got it.
- SAScott Aaronson
So, the, the error correction becomes a net win rather than a net loss, right? And then once you reach that sort of crossover point, then, you know, your simulated qubits could in turn simulate qubits that are even more reliable, and so on, until you've just, you know, effectively you have arbitrarily reliable qubits. So, long story short, we are not at that break-even point yet. We're a hell of a lot closer than we were when people started doing this in the '90s, like, orders of magnitude closer.
- LFLex Fridman
But the key ingredient-
- SAScott Aaronson
Yeah.
- LFLex Fridman
... there is the more qubits, the better, because-
- SAScott Aaronson
Uh, ah, well, the more qubits, the larger the computation you can do, right? I mean, I mean, uh, uh, uh, uh, qubits are what constitute the memory of your quantum computer, right? Yeah.
- LFLex Fridman
But also for the, uh, sorry, for the error-correcting mechanism.
- SAScott Aaronson
Ah, yes. So, so, so the w- the way I would say it is that error correction imposes an overhead in the number of qubits. And that i- is actually one of the biggest practical problems with building a scalable quantum computer. If you look at the error-correcting codes, at least the ones that we know about today, and you look at, you know, what would it take to actually use a quantum computer to, uh, uh, you know, uh, uh, uh, um, um, um, hack your credit card number-
- LFLex Fridman
Right.
- SAScott Aaronson
... which is, you know, you know what I mean, you know, the most famous application people talk about-
- LFLex Fridman
Yeah.
- SAScott Aaronson
... right, let's say to factor huge numbers and thereby break the RSA cryptosystem. Well, w- what, what that would take would be thousands of, uh, several thousand logical qubits, but now with the known error-correcting codes, each of those logical qubits would need to be encoded itself using thousands of physical qubits. So, at that point, you're talking about millions of physical qubits. And in, in some sense, that is the reason why quantum computers are not breaking cryptography already. It's because of this, these immense overheads involved. Yeah.
- LFLex Fridman
So, that overhead is additive or multiplicative?
- SAScott Aaronson
Well, multiplicative. I mean, it's, it's like you take the number of, uh, uh, logical qubits that you need in your abstract quantum circuit, you multiply it by a thousand or so. So, you know, there's a lot of work on, you know, inventing better, trying to invent better error-correcting codes. Okay, but that is the situation right now. In the meantime, uh, uh, we are now in, um, what, uh, physicist John Preskill called the noisy intermediate scale quantum, or NISQ era. And this is the era, you can think of it as sort of, like, the vacu- you know, we're now entering the very early vacuum tube era of-
- LFLex Fridman
Yeah.
- SAScott Aaronson
... quantum computers. The quantum computer analog of the transistor has not been invented yet, right? That would be, like, true error correction, right, where, you know, we are not, or, or, or something else that would achieve the same effect, right? We are not there yet. Uh, and, um, but, but, but where we are now, let's say as of a few months ago, you know, as of Google's announcement of quantum supremacy, you know, we are now finally at the point where even with a non-error-corrected quantum computer, with, you know, these noisy devices, we can do something that is hard for classical computers to simulate. Okay? So, we can eke out some advantage. Now, will we, in this noisy era, be able to do something beyond what a classical computer can do that is also useful to someone? That, we still don't know. People are going to be racing over the next decade to try to do that. By people, I mean Google, IBM, um, you know, a bunch of startup companies, uh, you know, uh, uh-
- LFLex Fridman
And research labs.
- 49:22 – 51:00
Quantum computer engineering challenges
- SAScott Aaronson
yeah. So-
- LFLex Fridman
You just mentioned a million things. Well, I'll, I'll backtrack for a second-
- SAScott Aaronson
Yeah, sure, sure.
- LFLex Fridman
... and ask. Uh, so we're in these vacuum tube days.
- SAScott Aaronson
Yeah.
- LFLex Fridman
Uh-
- SAScott Aaronson
Just entering them, I'd say.
- LFLex Fridman
Uh, en- just entering. Wow. Okay, so-
- SAScott Aaronson
Yeah.
- LFLex Fridman
... how do we escape the vacuum? So, how do we-
- SAScott Aaronson
Mm-hmm.
- LFLex Fridman
... get to ... Uh, h- how do we get to where we are now with the CPU?
- SAScott Aaronson
Yeah.
- LFLex Fridman
Uh, is this a fundamental engineering challenge? Is there f- is there breakthroughs in, on the physics side that are needed, on the computer science side? What's-
- SAScott Aaronson
W-
- LFLex Fridman
Or is there an in- is it a financial issue, where a hu- m- much larger just sheer investment and excitement is needed?
- SAScott Aaronson
Uh, so it's the ... You know, th- tho- those are excellent questions. Uh, my guess, my, my-
- LFLex Fridman
With no answers? (laughs)
- SAScott Aaronson
Well, well, no, no. My, my, my, my, my, my guess would be all of the above.
- LFLex Fridman
Yeah.
- SAScott Aaronson
(laughs) I mean, my, my guess, you know, I mean, I mean-... you know, you could say fundamentally, it is an engineering issue, right? The theory has been in place since the '90s. You know, at least, you know, uh, uh, uh, this is what, you know, error correction w- you know, would look like. You know, we, we do not have the hardware that is at that level. But, at the same time, you know, so you could just, um, you know, try to power through, you know, maybe even like, you know, if someone spent a trillion dollars on some quantum computing Manhattan Project, right?
- LFLex Fridman
Mm-hmm.
- SAScott Aaronson
Then conceivably, they could just, you know, build a, a, an error-corrected quantum computer as it was envisioned back in the '90s, right? I think the more plausible thing to happen is that there will be further theoretical breakthroughs, and there will be further insights that will cut down the cost of doing this.
- 51:00 – 56:33
Moore's Law
- LFLex Fridman
So, let's take a-
- SAScott Aaronson
Yeah.
- LFLex Fridman
... brief step-
- SAScott Aaronson
Yeah, yeah.
- LFLex Fridman
... to, to the philosophical.
- SAScott Aaronson
Sure.
- LFLex Fridman
I just, uh, recently talked to Jim Keller, who's a, sort of a, like, the f- the famed architect in the-
- SAScott Aaronson
Mm.
- LFLex Fridman
... in this, in the microprocessor world.
- SAScott Aaronson
Okay.
- LFLex Fridman
And he's been told for decades, every year, that the Moore's Law is goi- going to die this year.
- SAScott Aaronson
Mm.
- LFLex Fridman
And he try- tries to argue that the, the, the Moore's Law is still alive and well, and it'll be alive for quite a long time to come. So, that's-
- SAScott Aaronson
How long? How long did he say?
- LFLex Fridman
Well, the, well, he's-
- SAScott Aaronson
Yeah.
- LFLex Fridman
It's the, the main point is it's still alive.
- SAScott Aaronson
Okay.
- LFLex Fridman
But he thinks, uh, there's still 1,000X improvement just-
- SAScott Aaronson
Okay.
- LFLex Fridman
... on shrinking the transistors that's possible.
- SAScott Aaronson
Mm.
- LFLex Fridman
Whatever. The point is that the exponential growth we see, it is actually a huge number of these S-curves.
- SAScott Aaronson
Mm-hmm.
- LFLex Fridman
Just constant breakthroughs.
- SAScott Aaronson
Mm-hmm.
- LFLex Fridman
At the philosophical level-
- SAScott Aaronson
Mm-hmm.
- LFLex Fridman
... why do you think we, as a descendants of apes, were able to c-
- SAScott Aaronson
(laughs)
- 56:33 – 1:12:18
Quantum supremacy
- LFLex Fridman
Google-
- SAScott Aaronson
Mm.
- LFLex Fridman
... announced with their work in, uh, the, the paper in nature with quantum supremacy.
- SAScott Aaronson
Yes.
- LFLex Fridman
Can you describe, again back to the basic, what is, perhaps not so basic, what is quantum supremacy?
- SAScott Aaronson
Absolutely. So, uh, quantum supremacy is a term that was coined by, again by John Preskill in, uh, 2012. Uh, not, not everyone likes the name, you know, but uh, uh, you know, it, it, it, it sort of stuck. Uh, uh, you know, we don't, uh, uh, we s- haven't found a better alternative. I know that-
- LFLex Fridman
It's technically quantum computational com- uh, supremacy.
- SAScott Aaronson
Yeah, yeah supremacy, that's right, that's right. And, but, but the basic idea is actually one that goes all the way back to the beginnings of quantum computing when, uh, Richard Feynman and David Deutsch, people like that were talking about it in the early '80s. And, and, uh, and, and quantum supremacy just refers to sort of the point in history when you can first use a quantum computer to do some well-defined task, uh, much faster than any known algorithm running on any of the classical computers that are available. Okay? So, uh, you know, notice that I did not say a useful task.
- LFLex Fridman
Yes.
- SAScott Aaronson
Okay? Y- you know, it could be something completely artificial, but it's important that the task be well defined. So, in other words, you know, there is, it, it is something that has right and wrong answers, you know, and th- that are knowable independently of this device, right? And we can then, you know, run the device, see if it gets the right answer or not.
- LFLex Fridman
Can you clarify-
- SAScott Aaronson
Yeah.
- LFLex Fridman
... a small point? You said much faster than a classical implementation.
- SAScott Aaronson
Yeah.
- LFLex Fridman
Uh, what about m- th- th- sort of what about the space w- where the class- there is no, there's not, it doesn't even exist a classical algorithm to-
- SAScott Aaronson
Oh.
- LFLex Fridman
... solve the problem.
- SAScott Aaronson
So, so, so maybe I should clarify. Everything that a quantum computer can do, a classical computer can also eventually do, okay? And the reason why we know that is that, uh, uh, a, a classical computer could always, you know, i- if it had no limits of time and memory, it could always just store the entire quantum state, you know, of your, you know, o- of the quantum-
- LFLex Fridman
Mm-hmm.
- SAScott Aaronson
Or store in, a list of all the amplitudes, you know, in, in the state of the quantum computer, and then just, you know, do some linear algebra to just update that state, right? And so, so anything that quantum computers can do, can also be done by classical computers, albeit exponentially slower in some cases.
- LFLex Fridman
So, quantum computers don't go to some magical place outside of Alan Turing's-
- SAScott Aaronson
They don't.
- LFLex Fridman
... definition of computation?
- SAScott Aaronson
Precisely. They do not solve the halting problem.
- LFLex Fridman
Right.
- SAScott Aaronson
They cannot solve anything that is uncomputable in Alan Turing's sense. What they, what we think they do change is what is efficiently computable.
- LFLex Fridman
Mm.
- SAScott Aaronson
Okay? And, uh, you know, since the 1960s, you know, the word efficiently, i- you know, has, well has been a central word in computer science, but it's sort of a code word for something technical, which is, uh, basically with polynomial scaling.
- LFLex Fridman
Mm-hmm.
- SAScott Aaronson
You know? That as you get to larger and larger inputs, you would like an algorithm that uses an amount of time that scales only like the size of the input raised to some power, and not exponentially with the size of the in- input, right?
- 1:12:18 – 1:17:11
Using quantum computers to break cryptography
- LFLex Fridman
Andrew Yang-
- SAScott Aaronson
Mm-hmm.
- LFLex Fridman
... a very intelligent...
- SAScott Aaronson
Mm-hmm.
- LFLex Fridman
... and, uh, a presidential candidate with a lot of interesting ideas in all kinds of technological fields, tweeted that because of quantum computing, no code is uncrackable.
- SAScott Aaronson
Mm-hmm.
- LFLex Fridman
Is he wrong or right?
- SAScott Aaronson
Uh, he was, uh, premature, let's say. Uh, so, well, okay, uh, uh, wrong. (laughs)
- LFLex Fridman
(laughs)
- SAScott Aaronson
So, look, I, you know, I- I'm- I'm actually, I'm- I'm, you know, I'm a fan of Andrew Yang.
- LFLex Fridman
Mm-hmm.
- SAScott Aaronson
I like his can- you know, I like his ideas, I like his candidacy. Um, I think that, uh, uh, you know, he, you know, he may be ahead of his time with, you know, the universal basic income, and, you know, and so forth, and he may also be ahead of his time in- in that tweet that you referenced. So, regarding- regarding, uh, using quantum computers to break, uh, cryptography, so the situation is this-
- LFLex Fridman
Yeah.
- SAScott Aaronson
... okay? So, um, the famous discovery of Peter Shor, you know, 26 years ago that really started quantum computing, you know, as- as an autonomous field-
- LFLex Fridman
Mm-hmm.
- SAScott Aaronson
... was that, uh, if you built a full scalable quantum computer, then, um, you could use it to efficiently-... find the prime factors of- of- of- of huge numbers and, uh, calculate discrete logarithms, and, uh, solve a few other problems that are very, very special in character, right? They're not NP-complete problems.
- LFLex Fridman
Mm-hmm.
- SAScott Aaronson
We're pretty sure they're not, okay? But, uh, i- it so happens that most of the public key cryptography that we currently use (laughs) to protect the internet is based on the belief that these problems are hard.
- LFLex Fridman
Yeah.
- SAScott Aaronson
Okay, what Shor showed is that once you get scalable quantum computers, then that's no longer true, okay? But now, you know, uh- uh- uh, you know, before people panic, there are two important points to understand here, okay? The first is that, uh, quantum supremacy, the milestone that Google just achieved, is very, very far from the kind of scalable quantum computer that would be needed to actually threaten public key cryptography. Okay, so, you know, we touched on this earlier, right? But Google's device has 53 physical qubits, right? To threaten cryptography, you're talking, you know, w- with any of the known error correction methods, you're talking millions of physical qubits and-
- LFLex Fridman
'Cause error correction would be required to threaten-
- SAScott Aaronson
Yes.
- LFLex Fridman
... cryptography.
- SAScott Aaronson
Yes. Yes. Uh- Uh- Uh- Uh- Yes. Y- yeah, yeah, i- i- it's, uh- uh- uh- i- uh- it certainly would, right? And, uh- uh, you know, h- uh- uh- um, how much, you know, h- how great will the overhead be from the error correction? That we don't know yet. But, uh, with the known codes, you're talking millions of physical qubits and of a much higher quality than any that we have now.
- LFLex Fridman
Mm-hmm.
- SAScott Aaronson
Okay, so, um, you know, I- I don't- I don't think that that is, you know, uh- uh, coming soon, although, uh- uh, people who have secrets that, you know, need to stay secret for 20 years, you know, are already worried about this, you know, for- for the good reason that, you know, we- we presume that intelligence agencies are already scooping up data, you know, in the hope that eventually, they'll be able to decode it once quantum computers become available, okay? (laughs) So- so there is- so- so- so- so this brings me to the second, uh- uh, point I wanted to make, which is that there are other public key crypto systems that are known, uh, that, uh- uh, we don't know how to break even with quantum computers, okay? And there's- so there's a whole field devoted to this now, which is called post-quantum cryptography, okay?
- LFLex Fridman
(laughs)
- SAScott Aaronson
And so there is already ... So- so we have some good candidates now, uh, the, uh, best known being what are called lattice-based crypto systems. And there is already some push to try to migrate to these crypto systems. So NIST, uh- uh- uh- in- in the US, is holding a competition to create standards for post-quantum cryptography.
- LFLex Fridman
Wow.
- SAScott Aaronson
Uh, which will be the first step in trying to get every web browser and every router to upgrade, you know, and use, uh, um, you know, something like SSL that is- would be based on- on, you know, what we think as quantum-secure cryptography. Uh, but, you know, this will- this will be a long process. Uh, uh, but, you know, it is- it is something that people are already starting to do. And so- so, you know, sh- um, um, Shor's algorithm is- was sort of a dramatic discovery. You know, it could be a big deal for whatever intelligence agency first gets a scalable quantum computer if no one... at least, uh, certainly if no one else knows that they have it, right? (laughs) uh, but eventually, uh, we think that we could migrate the internet to the post-quantum cryptography, and then we'd be more or less back where we started. Okay, so this is sort of not the application of quantum computing I think that's really gonna change the world in a sustainable way, right?
- 1:17:11 – 1:22:18
Practical application of quantum computers
- SAScott Aaronson
The- the big... by the way, the biggest practical application of quantum computing that we know about, by far, I think is simply the simulation of quantum mechanics itself in order to, you know, learn about chemical reactions, you know, design maybe new chemical processes, new, uh, materials, new drugs, uh, new solar cells, new superconductors, uh, all kinds of things like that.
- LFLex Fridman
What's the size of a quantum computer that would, uh, be able to simulate the, you know, quantum mechanical systems themselves, that would be impactful for the real world, for the kind of, uh, uh, chemical reactions and that kind of work? What- what scale are we talking about?
- SAScott Aaronson
Now- now- n- now- n- now- now you're asking a very, very current question, a very big question. P- uh, people are going to be racing over the next decade to try to do useful quantum simulations, uh, even with, you know, 100 or 200 qubit quantum computers of the sort that we're-
- LFLex Fridman
Okay.
- SAScott Aaronson
... we expect to be able to build over the next decade. Okay, so that might be, you know, the first application of quantum computing that we're able to realize, you know, or- or maybe it will prove to be too difficult, and maybe even that will require fault tolerance or, you know, will require error correction. Uh, but that is-
- LFLex Fridman
So there's an aggressive race to come up with-
- SAScott Aaronson
Yes.
- LFLex Fridman
... the one case study, kind of like with-
- SAScott Aaronson
Yeah.
- LFLex Fridman
... Peter Shor, though- with the-
- SAScott Aaronson
Mm-hmm.
- LFLex Fridman
... with the idea that would just capture the world's imagination of like-
- SAScott Aaronson
Yeah.
- LFLex Fridman
... "Look, we can actually do something very-"
- SAScott Aaronson
Yeah.
- LFLex Fridman
"... useful here."
- SAScott Aaronson
But I... Right. But I think, you know, within the next decade, the best shot we have is certainly not, you know, sh- using Shor's algorithm to break cryptography. Uh- uh, you know, just- just because it requires, you know, too much in the way of error correction. The best shot we have is to do some quantum simulation that tells the material scientists or chemists or nuclear physicists, you know, something that is useful to them and that they didn't already know, you know, and you might only need one or two successes in order to change some, you know, billion dollar industries, right? Like, you know, the way that people make fertilizer right now is still based on the Haber-Bosch process from a century ago, and it is some many body quantum mechanics problem that no one really understands, right? If you could design a better way to make fertilizer, right, that's, you know, billions of dollars right there. So-
- LFLex Fridman
Exactly.
- SAScott Aaronson
So- so tho- those are sort of the applications that people are going to be aggressively racing toward over the next decade. Now, I don't know if they're gonna realize it or not, but, you know, it is, you know, there's- they're cert- they certainly at least have a shot. So it's-
Episode duration: 1:33:41
Install uListen for AI-powered chat & search across the full episode — Get Full Transcript
Transcript of episode uX5t8EivCaM
Get more out of YouTube videos.
High quality summaries for YouTube videos. Accurate transcripts to search & find moments. Powered by ChatGPT & Claude AI.
Add to Chrome