Scott Aaronson: Quantum Computing | Lex Fridman Podcast #72

Lex Fridman 0:00 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.

Lex Fridman 5:07 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?

Scott Aaronson 6:20 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.

Lex Fridman 8:26 Wh- why do you think computer scientists avoid these questions? Or run away-

Scott Aaronson 8:31 Hm.

Lex Fridman 8:31 ... from them a little bit, at least in, uh-

Scott Aaronson 8:32 Mm-hmm.

Lex Fridman 8:32 ... technical scientific discourse?

Scott Aaronson 8:34 Well, I'm- I'm not- I'm not sure if they do so more than any other scientist though.

Lex Fridman 8:39 Ah.

Scott Aaronson 8:39 I mean- I mean-

Lex Fridman 8:39 Yeah, right.

Scott Aaronson 8:40 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.

Narrator 9:01 (laughs)

Lex Fridman 9:01 I just recently learned that-

Scott Aaronson 9:03 And, uh-

Lex Fridman 9:03 ... that little bit, and it's actually fascinating.

Scott Aaronson 9:05 Hm.

Lex Fridman 9:05 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.

Scott Aaronson 9:15 Mm-hmm, mm-hmm.

Lex Fridman 9:15 'Cause it's interesting that these two minds have somehow met in the arc of history.

Scott Aaronson 9:20 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?

Lex Fridman 10:06 Right.

Scott Aaronson 10:06 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.

Lex Fridman 10:18 That's fascinating. Take- take a step from philosophy to actual, like the-

Scott Aaronson 10:22 Yeah.

Lex Fridman 10:22 ... biggest possible step to actual engineering with-

Scott Aaronson 10:25 Yeah.

Lex Fridman 10:25 ... actual real impact.

Scott Aaronson 10:26 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)

Lex Fridman 11:30 Can you maybe linger-

Scott Aaronson 11:30 Yeah.

Lex Fridman 11:30 ... on that for just a little longer?

Scott Aaronson 11:32 Yeah.

Lex Fridman 11:33 What do you think is the difference, so like the corollary of the criticism that I mentioned previously, uh, that why I ask the philosophical questions of the mathematician-

Scott Aaronson 11:44 Hm.

Lex Fridman 11:44 ... is if you want to ask philosophical questions, then invite a real philosopher on and ask them.

Scott Aaronson 11:48 Hm.

Lex Fridman 11:49 So, what's the difference between a- the way a computer scientist or mathematician ponders a philosophical question, and a philosopher ponders a philosophical question?

Scott Aaronson 11:57 Well, I mean- I mean, a lot of it just depends on the individual, right? It- it's hard to make generalizations about entire fields. But, you know, I think- I think, uh, if we- if we- if we tried to, if we tried to stereotype, you know-

Lex Fridman 12:11 Yes.

Scott Aaronson 12:11 ... we would say that uh- uh, um, you know, uh- uh, uh, a- a-... uh, scientists very often will be, uh, less careful in their use of words. You know, I mean, philosophers are really experts in sort of, you know, like when I- when I- when I talk to them, they will just pounce if I, you know, use the wrong phrase for something, uh-

Lex Fridman 12:30 Experts is a very nice word.

Scott Aaronson 12:32 (laughs)

Lex Fridman 12:32 You could say sticklers or...

Scott Aaronson 12:34 Sticklers, yeah, yeah, yeah.

Lex Fridman 12:35 Yeah.

Scott Aaronson 12:35 Or- or, you know, they will- they will sort of interrogate my word choices-

Lex Fridman 12:39 Yeah.

Scott Aaronson 12:39 ... let's say, to a much greater extent than scientists would, right? And, uh, and scientists, you know, will, uh, often, if you ask them about a philosophical problem, like the hard problem in- in- of consciousness or free will or whatever, they will try to relate it back to, you know, recent research.

Lex Fridman 12:57 Right.

Scott Aaronson 12:57 You know, research about- about, uh, uh, uh, neurobiology or, you know... But, you know, the- the best of all is research that they personally are involved with.

Lex Fridman 13:05 Right.

Scott Aaronson 13:05 Right? And, you know, and- and- and- and, you know, of course they will want to talk about that, you know, and it is what they will think of, you know, and the- and of course you could have an argument that maybe, you know, it- it's all interesting as it goes, but maybe none of it touches the philosophical question, right?

Lex Fridman 13:20 Right.

Scott Aaronson 13:20 But, you know, but maybe, um, you know, uh, uh, uh, a science, you know, at least i- it- it- as I said, it does tell us concrete things. And, you know, even if, uh, like a deep dive into neurobiology will not answer the hard problem of consciousness, you know, maybe it- it can take us about as far as we can get toward, you know, uh, uh, uh, expanding our minds about it, you know, toward thinking about it in a different way. Um... Well, I mean, I think neurobiology can do that. But, you know, with these profound philosophical questions, I mean, also art and literature do that, right? Uh, they're all different ways of trying to approach these questions that, you know, we don't... for which we don't even know really what an answer would look like. But, uh, uh... And yet somehow we can't help but keep returning to the questions.

Lex Fridman 14:07 And you have a kind of mathematical, beautiful mathematical way of discussing this with the idea of Q prime.

Scott Aaronson 14:12 Oh, right.

Lex Fridman 14:13 Y- y- you write that usually the only way to make progress on the big questions, like the philos- the philosophical questions we're talking about now, is to pick off smaller sub-questions.

Scott Aaronson 14:24 Mm-hmm.

Lex Fridman 14:24 Ideally sub-questions that you can attack using math, empirical observation, or both. You define the idea of a Q prime. So given an un- an unanswerable philosophical riddle Q, replace it with a "merely" in quotes, scientific or mathematical question, Q prime-

Scott Aaronson 14:41 Mm-hmm.

Lex Fridman 14:42 ... which captures part of what people have wanted to know when they first asked Q.

Scott Aaronson 14:46 Yes.

Lex Fridman 14:47 Then with luck, one solves Q prime. So you- you describe some examples of such Q prime sub-questions in, um, your long essay-

Scott Aaronson 14:58 Mm-hmm.

Lex Fridman 14:58 ... titled, Why Philosophers Should Care About Computational Complexity. So, you cataloged the various Q primes on which you think com- uh, theoretical computer science has made progress. Can you mention a few favorites, if any pop- if any pop to mind? Or that you remember?

Scott Aaronson 15:12 Well, yeah. So- so I mean, I- I would say some of the most famous examples in history of- of that sort of replacement were, you know... I mean- I mean, to- to go back to Alan Turing, right? What he did in his, uh, uh, computing machinery and intelligence paper was exactly... You know, uh, he, uh, uh, explicitly started with the question, "Can machines think?"

Lex Fridman 15:33 Yeah.

Scott Aaronson 15:33 And then he said, uh, uh, "Sorry, I think that question is too meaningless." But here's a different question. You know, could you program a computer so that you couldn't tell the difference between it and a human, right? And, you know, yeah.

Lex Fridman 15:46 So- so in the very first few sentences, he in fact just formulates-

Scott Aaronson 15:49 Yeah.

Lex Fridman 15:49 ... the Q prime question.

Scott Aaronson 15:50 It precis- he does precisely that. Or, you know, we could look at- at- at- at Godel, right? Uh, uh, where, you know, you had these, uh, philosophers arguing for centuries about the limits of mathematical reasoning, right? The limits of formal systems. And, um, you know, then by the early 20th century, uh, uh, logicians, you know, starting with, you know, Frege, Russell, and then, you know, most, uh, spectacularly Godel, you know, managed to reframe those questions as, "Look, we have these formal systems, they have these definite rules. Are there questions that we can phrase within the rules of these systems that are not provable within the rules of the systems? And can we prove that fact?" Right? And, um, so that would be another example. Uh, uh, you know, I- I had this essay called The Ghost in the Quantum Turing Machine. Uh, that was, you know, o- one of the crazier things I've written. But I- I, uh, I tried to do something s- or, you know, to- to advocate doing something similar there for free will, where, you know, instead of talking about, is free will, you know, real? Where we get hung up on the meaning of, you know, what exactly do we mean by freedom? And can you have... can you be... you know, or do we mean compatibilist free will? Libertarian free will? What do these things mean? You know, I, uh, suggested just asking the question, how well, in principle, consistently with the laws of physics, could a person's behavior be predicted? You know, without sort of, let's say, destroying the person's brain, you know, taking it apart in the process of trying to predict them. And, you know, and- and that actually, uh, asking that question gets you into all sorts of meaty and interesting issues. You know, issues of, uh, uh, what is the computational substrate of the brain, you know? Or, uh, uh, can you understand the brain, you know, just at the sort of level of the neurons? You know, at sort of the abstraction of a neural network? Or do you need to go deeper to the, you know, uh, molecular level and ultimately even to the quantum level, right? And of course that would put limits on predictability if- if- if you did. Uh-

Lex Fridman 17:52 So you need to reduce... you need to reduce the mind t- to a- a computational device, like formalize it, so then you can make predictions about wha... you know, whether you could predict the behavior of the system.

Scott Aaronson 18:03 Well, if you were trying to predict a person, yeah, then presumably you would need some model of their brain, right? And now the question becomes one of, how accurate can such a model become? Can you make a model that will be accurate enough to really seriously threaten people's sense of free will? You know, not just metaphysically, but like really, "I have written in this envelope what you are going to say next." You know, kind of thing. Yeah.

Lex Fridman 18:27 Is accuracy the right term here? So...

Scott Aaronson 18:29 Well...

Lex Fridman 18:29 It's- it's also a level of abstraction has to be right. So if you're-

Scott Aaronson 18:33 Yeah.

Lex Fridman 18:33 ... if you're accurate at the... som- somehow at the quantum level-

Scott Aaronson 18:38 Mm-hmm.

Lex Fridman 18:39 ... that may not be convincing to us at the human level.

Scott Aaronson 18:43 Well, uh, right. But the, but the question is, what accuracy at the sort of u- level of the underlying mechanisms do you need in order to predict the behavior, right? At the end of the day, the test is just, can you, you know, foresee what the person is going to do, right? I am... You know, and, and, and, and, um, you know, and, and, and, and in discussions of free will, you know, it s- seems like both sides wanna, you know, very quickly dismiss that question as irrelevant. Well, to me, it's totally relevant. Okay? Because, uh, you know, if, if someone says, "Oh, well, you know, a w- a Laplace demon that knew the complete state of the universe, uh, you know, could predict everything you're going to do, therefore you don't have free will," you know, that, that, it doesn't trouble me that much because, well, you know, I've never met such a demon, right?

Lex Fridman 19:29 (laughs)

Scott Aaronson 19:29 I, I, you know, uh, you know, and, and, uh, uh, we, you know, we even have some reasons to think, you know, maybe it, you know, it could not exist as part of our world. Uh, you know, it was only a, an abstraction, a thought experiment. On the other hand, if someone said, "Well, you know, I have this brain-scanning machine. You know, you step into it, and then, you know, every paper that you will ever write, it will write. You know, every thought that you will have, you know, even right now about the machine itself, it will foresee." You know, and well, if, if you can actually demonstrate that, then I think, you know, that, that, you know, that, that sort of threatens my internal sense of having free will-

Lex Fridman 20:04 Mm-hmm.

Scott Aaronson 20:04 ... in a much more visceral way. You know, but now you notice that we're asking an empi- a, a much more empirical question. We're asking, is such a machine possible or isn't it? We're asking, if it's not possible, then what in the laws of physics, or what about the behavior of the brain, you know, prevents it from existing?

Lex Fridman 20:23 So, if you could philosophize a little bit-

Scott Aaronson 20:25 Yeah.

Lex Fridman 20:25 ... within this empirical question, at, where do you think would enter the, the... by which mechanism would enter the possibility that we can't predict the outcome? So, there would be something that would be-

Scott Aaronson 20:37 Mm-hmm.

Lex Fridman 20:37 ... akin to a free will, and-

Scott Aaronson 20:38 Yeah, well, you could say the, the sort of obvious possibility, which was, you know, recognized by, uh, Eddington and many others about as soon as quantum mechanics was discovered in the 1920s, uh, was that, uh, if, um, you know, uh, l- let's say a sodium ion channel, you know, i- i- in the, in the, uh, in, in, in the brain, right, uh, you know, it, it's, it, its behavior is chaotic, right? It, it sort of, it's governed by these Hodge, uh, Hodges-Lee-Hodgkin equations in, in neuroscience, right, which are differential equations that have a stochastic component, right? Now, where does... You know, and then this ultimately governs, let's say, whether a neuron will fire or not fire, right? And-

Lex Fridman 21:19 So the, the, that's the basic chemical proc-

Scott Aaronson 21:21 Mm-hmm.

Lex Fridman 21:21 ... or electrical process by which signals are sent in the brain?

Scott Aaronson 21:24 Exactly, exactly. And, and, uh, you know, and, and so you could ask, "Well, well, where does the randomness in the process, you know, that, uh, uh, that, that neuroscientists, or w- what neuroscientists would, uh, would, would treat as randomness, where does it come from?" You know, ultimately, it's thermal noise, right? Where does thermal noise come from? Well, ultimately, you know, there are some quantum mechanical events at the molecular level that are getting sort of a- chaotically amplified by, you know, a sort of butterfly effect. Uh, and so, uh, you know, even if you, uh, knew the complete quantum state of someone's brain, you know, at best, you could predict the probabilities that they would do one thing or do another thing, right? I think that part is actually relatively uncontroversial, right? The, the, uh, the controversial question is whe- whether any of it matters for the sort of philosophical questions that we care about. Because you could say, if all it's doing is just injecting some randomness into an otherwise completely mechanistic process, well then who cares, right? And more concretely, if you could build a machine that, you know, could just calculate the, even just a, the, the probabilities of all of the possible things that you would do, right, and, you know, um, um, you know, of all the things that said you had a 10% chance of doing, you did exactly a tenth of them, you know, and, and, and, and so on and so on.

Lex Fridman 22:45 Yeah, that somehow also takes away the feeling of free will.

Scott Aaronson 22:48 Exactly. I mean, I mean, to me it seems essentially just as bad as if, uh, the machine deterministically predicted you. It seems, you know, hardly different from that. So, so the, so then, um, uh, uh, but a, a more, a more subtle question is could you even learn enough about someone's brain to do that, okay? Because, you know, another central fact about quantum mechanics is that, uh, uh, m- making a measurement on a quantum state is an inherently destructive operation. Okay? So, uh, you know, if I want to measure the, you know, position of a particle, right, it was... Well, before I measured, it had a super position over many different positions. As soon as I measure, I localize it, right? So now I know the position, but I've also fundamentally changed the state. And so, so you, you could say, well maybe in, in trying to build a model of someone's brain that was accurate enough to actually, you know, make, let's say, even, even well-calibrated probabilistic predictions of their future behavior, maybe you would have to make measurements that were just so accurate that you would just fundamentally alter their brain. Okay?

Lex Fridman 23:55 (laughs) Yeah.

Scott Aaronson 23:56 Or, or, or, or maybe not. Maybe you on- you know, you, it would suffice to just make some nano robots that just measured some sort of much larger scale, you know, macroscopic, uh, behavior, like, you know, is th- what is this neuron doing, what is that neuron doing? Maybe that would be enough. See, but now, you know, I, I, I, what I, what I claim is that we're now asking a question, you know, in which, you know, it is, it is, it is possible to envision what progress on it would look like.

Lex Fridman 24:24 Yeah, but just as you said, that question may be slightly detached from the philosophical question in the sense if-

Scott Aaronson 24:32 Mm-hmm.

Lex Fridman 24:32 ... consciousness somehow has a role to the experience of free will. Because ultimately what-

Scott Aaronson 24:37 Mm-hmm.

Lex Fridman 24:37 ... when we're talking about free will, we're also-

Scott Aaronson 24:39 Yeah.

Lex Fridman 24:39 ... talking about not just the predictability of our actions, but somehow the experience of that-

Scott Aaronson 24:45 Yes.

Lex Fridman 24:45 ... predictability?

Scott Aaronson 24:46 Yeah. Well, I mean, a lot of philosophical questions ultimately, like, feed back to the hard problem of consciousness. (laughs)

Lex Fridman 24:53 Yeah.

Scott Aaronson 24:53 You know, and as much as you can try to sort of talk around it or not, right? And, and, you know, and then, and, and there is a, a reason why people try to talk around it, which is that, you know, uh, Democritus talked about the hard problem of consciousness, you know, in 400 BC in terms that would be totally recognizable to us today.

Lex Fridman 25:13 (laughs)

Scott Aaronson 25:13 Right? And it's really not clear if there's been progress, uh-

Lex Fridman 25:16 (laughs)

Scott Aaronson 25:16 ... since, or what progress could possibly consist of.

Lex Fridman 25:19 Is there a Q prime type of sub-question that could help us get at consciousness? It's something about consciousness ?

Scott Aaronson 25:25 Well, well, I mean, well, I mean, there is the whole question of, you know, of, of AI, right? Of, you know, can you build a, a, a, a, a, a human-level or superhuman-level AI? And, uh, you know, can it, can it work in a completely different substrate from the brain? I mean, there's, you know... And, of course, that was Alan Turing's point. And, you know, and, and, and even if that was done, it's, you know, maybe people would still argue about the hard problem of consciousness, right?

Lex Fridman 25:49 Sure.

Scott Aaronson 25:50 And yet, you know, my, my, my claim is a little different. My claim is that, in a world where, you know, there were, you know, uh, human-level AIs, or we'd been even overtaken by such AIs, the entire discussion of the hard problem of consciousness would have a different character, right? It would take place in different terms in such a world, even if we hadn't answered the question. And, and my claim about free will would be similar, right? That if there, if this prediction machine that I was talking about could actually be built, well, now the entire discussion of the, you know, of free will is sort of transformed by that, um, you know, even if, in some sense, the, the metaphysical question hasn't been answered.

Lex Fridman 26:31 Yeah.

Scott Aaronson 26:32 Yeah.

Lex Fridman 26:32 Exactly. It transforms it fundamentally because, say, that machine does tell you that it can predict perfectly, and yet there is this deep experience of free will, and then-

Scott Aaronson 26:40 Yep.

Lex Fridman 26:40 ... that, that changes the question completely.

Scott Aaronson 26:42 Yeah.

Lex Fridman 26:43 And it starts actually, uh-

Scott Aaronson 26:45 Yeah.

Lex Fridman 26:45 ... getting to the question of, uh, the, the A-, the AGI, the Turing questions-

Scott Aaronson 26:51 Mm-hmm.

Lex Fridman 26:52 ... of the demonstration of free will, the demonstration of intelligence, the demonstration of consciousness.

Scott Aaronson 26:58 Mm-hmm.

Lex Fridman 26:58 Does that equal-

Scott Aaronson 26:59 Mm-hmm.

Lex Fridman 27:00 ... consciousness-

Scott Aaronson 27:00 Mm-hmm.

Lex Fridman 27:00 ... intelligence and free will?

Scott Aaronson 27:01 Mm-hmm. But see, uh, uh, uh, Lex, if, if every time I was contemplating a decision, you know, this machine had printed out an envelope, you know, where I could open it and see that it knew my decision, I think that actually would change my subjective experience of making decisions, right? I mean, it would-

Lex Fridman 27:18 You mean does knowledge change your subjective experience, I suppose?

Scott Aaronson 27:20 Well, or, you know, I mean, I mean, the knowledge that this machine had predicted everything I would do. I mean, it might drive me completely insane, right? But at any rate, it would change my experience to, to a- you know, to not just discuss such a machine as a thought experiment, but to actually see it.

Lex Fridman 27:37 Yeah. There-

Scott Aaronson 27:38 Yeah.

Lex Fridman 27:38 (laughs)

Scott Aaronson 27:38 (laughs)

Lex Fridman 27:39 Uh-

Scott Aaronson 27:39 I mean, I mean, you know, you-

Lex Fridman 27:40 It's-

Scott Aaronson 27:40 ... you could say at that point, you know, you could say, you know, w- wha- wha- why not simply call this machine a second instantiation of me and be done with it, right? What, you know, what, w- w- why, why even privilege the original me over this perfect duplicate that, that exists in the machine?

Lex Fridman 27:56 Yeah.

Scott Aaronson 27:57 Yeah.

Lex Fridman 27:57 Or it, there could be a religious experience with it too.

Scott Aaronson 28:00 Yeah.

Lex Fridman 28:00 It's kind of what God, throughout the generations-

Scott Aaronson 28:02 (laughs)

Lex Fridman 28:02 ... is supposed to have d- that God kind of represents that perfect machine.

Scott Aaronson 28:06 Mm-hmm.

Lex Fridman 28:06 He's able to, um... I guess, actually-

Scott Aaronson 28:09 Yeah.

Lex Fridman 28:10 Wh- I, I don't even know what are, what, what are the religious interpretations of free will.

Scott Aaronson 28:16 (laughs)

Lex Fridman 28:16 Uh, does... So if God knows perfectly everything in, in religion-

Scott Aaronson 28:22 Mm-hmm.

Lex Fridman 28:22 ... in the various religions-

Scott Aaronson 28:24 Mm-hmm.

Lex Fridman 28:24 ... where does free will fit into that? Do you know?

Scott Aaronson 28:27 That, that has been one of the big things that theologians have argued about for thousands of years.

Lex Fridman 28:31 Okay. (laughs)

Scott Aaronson 28:33 (laughs) You know, I am, I am not a theologian-

Lex Fridman 28:35 Yeah.

Scott Aaronson 28:35 ... so maybe I shouldn't go there, but yeah.

Lex Fridman 28:36 So there's not a clear answer in a book, like, uh-

Scott Aaronson 28:38 I mean, I mean, this is, you know... The Calvinists debated this. The, you know, this has been, you know... I mean, different r- r- religious movements have taken different positions on that question. But that is how they think about it. You know, meanwhile, you know, a large part of, sort of what, what animates, you know, theoretical computer science, you can say-

Lex Fridman 28:57 Mm-hmm.

Scott Aaronson 28:57 ... is, you know, we are asking sort of, what are the ultimate limits of, you know, what you can know or, you know, calculate or figure out by, you know, entities that you can actually build in the physical world, right? And, uh, if I were trying to explain it to a theologian, maybe I would say, you know, "We are studying, you know, to what extent, you know, gods can be made manifest in the physical world." I'm not sure my colleagues would like that.

Lex Fridman 29:21 (laughs) So let's, let's talk about quantum computers for a moment.

Scott Aaronson 29:25 Yeah, sure, sure.

Lex Fridman 29:27 As you've said-

Scott Aaronson 29:28 Mm-hmm.

Lex Fridman 29:28 ... 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-

Scott Aaronson 29:41 Mm-hmm.

Lex Fridman 29:41 ... than just the quantum computer.

Scott Aaronson 29:42 Yes.

Lex Fridman 29:42 But can we start at the very basics?

Scott Aaronson 29:45 Mm-hmm.

Lex Fridman 29:45 What is quantum computing?

Scott Aaronson 29:47 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-

Lex Fridman 30:23 Right.

Scott Aaronson 30:23 ... 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...

Lex Fridman 30:29 Okay.

Scott Aaronson 30:29 ... 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.

Lex Fridman 34:19 Mm-hmm.

Scott Aaronson 34:19 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.

Lex Fridman 34:36 (laughs)

Scott Aaronson 34:37 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?

Lex Fridman 36:18 (laughs) Right.

Scott Aaronson 36:18 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?

Lex Fridman 36:42 Mm-hmm.

Scott Aaronson 36:42 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?

Lex Fridman 36:56 (laughs) Yeah.

Scott Aaronson 36:56 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.

Lex Fridman 37:28 So the design of algorithms in this space-

Scott Aaronson 37:31 Mm-hmm.

Lex Fridman 37:31 ... is the choreography of the interferences?

Scott Aaronson 37:33 Precisely.

Lex Fridman 37:34 Yeah.

Scott Aaronson 37:34 That's precisely what it is.

Lex Fridman 37:35 Can we take a brief step back and me-

Scott Aaronson 37:37 Sure.

Lex Fridman 37:37 Uh, uh-You mentioned information.

Scott Aaronson 37:40 Yes.

Lex Fridman 37:40 So in which part of this beautiful picture that you've painted-

Scott Aaronson 37:44 Mm.

Lex Fridman 37:44 ... is im- information contained?

Scott Aaronson 37:46 Oh. Well, information is at the core of everything that we've been talking about, right? I mean, th- the bit is, you know, the basic unit of information, since, you know, Claude Shannon's paper in 1948. You know, and you know, of course, you know, people had the concept even before that. You know, he, uh, popularized the name, right? But I mean-

Lex Fridman 38:05 But a bit is zero or one.

Scott Aaronson 38:07 That's right.

Lex Fridman 38:08 So that's a basic element of information.

Scott Aaronson 38:09 That's right. And what we would say is that the basic unit of quantum information is the qubit, is, you know, the object, any object that can be maintained in a s- a s- m- manipulated in a superposition of zero and one states. Uh, now, you know, sometimes people ask, "Well, but, but, but what is a qubit, physically?" Right? And there are all these different, you know, uh, uh, proposals that are being pursued in parallel for how you implement qubits. There is, you know, superconducting quantum computing that, uh, was in the news recently because of Google's, uh, quantum supremacy experiment, right, where, um, um, you would have, uh, some little s- uh, uh, coils where, uh, a current can flow through them in two different energy states, one representing a zero, another representing a one. And if you cool these coils to just s- slightly above absolute zero, like 1/100 of a degree, then they superconduct, and then the current can actually be in a superposition of the two different states. Uh, so that's one kind of qubit. Another kind would be, uh, you know, just a, an, an individual atomic nucleus, right? It has a spin. It could be spinning clockwise, it could be spinning counterclockwise, or it could be in a superposition of the two spin states. That is another qubit. But see, just like in the classical world, right, you could be a virtuoso programmer without having any idea of what a transistor is, right? Or how the bits are physically represented inside the machine, or even that the machine uses electricity, right? You just care about the logic. It's sort of the same with quantum computing, right? Qubits could be realized by many, many different quantum systems, and yet all of those systems will lead to the same logic, you know, the logic of, of, of, of, of qubits, and, and how, you know, how you measure them, how you change them over time. And so, you know, the, the subject of, you know, how qubits behave and what you can do with qubits, that is quantum information. Yeah.

Lex Fridman 40:09 So j- just to linger on that-

Scott Aaronson 40:11 Sure.

Lex Fridman 40:11 So, so, so the, the physical design implementation of a qubit-

Scott Aaronson 40:14 Mm-hmm.

Lex Fridman 40:15 ... does not, does not interfere with the, that next level of abstraction that you can program over it. So it truly is-

Scott Aaronson 40:23 Well-

Lex Fridman 40:23 ... the idea of it i- i- is the a, is it... Okay.

Scott Aaronson 40:27 Mm-hmm. Well, to-

Lex Fridman 40:27 Y- yeah.

Scott Aaronson 40:27 To be honest with you, today, they do interfere with each other.

Lex Fridman 40:30 Right.

Scott Aaronson 40:30 That's because the, all the quantum computers we can build today are very noisy, right? And so sort of the, the, the, you know, the qubits are very far from per- from perfect, and so the lower levels sort of does affect the higher levels, and we sort of have to think about all of them at once. Okay? But eventually, where we hope to get is to what are called error-corrected quantum computers-

Lex Fridman 40:52 Mm-hmm.

Scott Aaronson 40:52 ... where the qubits really do behave like perfect abstract qubits for as long as we want them to. And in that future, you know, the, you know, which, you know, a future that we can already s- you know, sort of prove theorems about or think about today, but in that future, uh, uh, the, the logic of it really does become decoupled from the hardware.

Lex Fridman 41:12 So if, if noise is currently like, the-

Scott Aaronson 41:14 Yeah.

Lex Fridman 41:14 ... biggest problem for quantum computing-

Scott Aaronson 41:18 Mm-hmm.

Lex Fridman 41:18 ... and then the dream is, uh, error-correcting-

Scott Aaronson 41:22 Mm-hmm.

Lex Fridman 41:22 ... quantum computers-

Scott Aaronson 41:23 Yes.

Lex Fridman 41:23 ... can you just maybe describe what does it mean for there to be noise in the system?

Scott Aaronson 41:28 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-

Lex Fridman 43:45 Mm-hmm.

Scott Aaronson 43:45 ... 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?

Lex Fridman 45:58 Got it.

Scott Aaronson 45:59 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.

Lex Fridman 46:26 But the key ingredient-

Scott Aaronson 46:27 Yeah.

Lex Fridman 46:27 ... there is the more qubits, the better, because-

Scott Aaronson 46:30 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.

Lex Fridman 46:40 But also for the, uh, sorry, for the error-correcting mechanism.

Scott Aaronson 46:43 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-

Lex Fridman 47:09 Right.

Scott Aaronson 47:09 ... which is, you know, you know what I mean, you know, the most famous application people talk about-

Lex Fridman 47:12 Yeah.

Scott Aaronson 47:12 ... 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.

Lex Fridman 47:44 So, that overhead is additive or multiplicative?

Scott Aaronson 47:46 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-

Lex Fridman 48:20 Yeah.

Scott Aaronson 48:20 ... 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-

Lex Fridman 49:17 And research labs.

Scott Aaronson 49:17 ... players of the ... Yeah, and, and, and research labs, and governments-

Lex Fridman 49:21 Yeah.

Scott Aaronson 49:21 ... and, uh,

Scott Aaronson 49:22 yeah. So-

Lex Fridman 49:22 You just mentioned a million things. Well, I'll, I'll backtrack for a second-

Scott Aaronson 49:25 Yeah, sure, sure.

Lex Fridman 49:27 ... and ask. Uh, so we're in these vacuum tube days.

Scott Aaronson 49:29 Yeah.

Lex Fridman 49:30 Uh-

Scott Aaronson 49:30 Just entering them, I'd say.

Lex Fridman 49:31 Uh, en- just entering. Wow. Okay, so-

Scott Aaronson 49:33 Yeah.

Lex Fridman 49:34 ... how do we escape the vacuum? So, how do we-

Scott Aaronson 49:37 Mm-hmm.

Lex Fridman 49:37 ... get to ... Uh, h- how do we get to where we are now with the CPU?

Scott Aaronson 49:42 Yeah.

Lex Fridman 49:42 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-

Scott Aaronson 49:53 W-

Lex Fridman 49:53 Or is there an in- is it a financial issue, where a hu- m- much larger just sheer investment and excitement is needed?

Scott Aaronson 50:00 Uh, so it's the ... You know, th- tho- those are excellent questions. Uh, my guess, my, my-

Lex Fridman 50:05 With no answers? (laughs)

Scott Aaronson 50:05 Well, well, no, no. My, my, my, my, my, my guess would be all of the above.

Lex Fridman 50:09 Yeah.

Scott Aaronson 50:09 (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?

Lex Fridman 50:39 Mm-hmm.

Scott Aaronson 50:40 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.

Lex Fridman 51:00 So, let's take a-

Scott Aaronson 51:00 Yeah.

Lex Fridman 51:00 ... brief step-

Scott Aaronson 51:01 Yeah, yeah.

Lex Fridman 51:01 ... to, to the philosophical.

Scott Aaronson 51:03 Sure.

Lex Fridman 51:03 I just, uh, recently talked to Jim Keller, who's a, sort of a, like, the f- the famed architect in the-

Scott Aaronson 51:10 Mm.

Lex Fridman 51:10 ... in this, in the microprocessor world.

Scott Aaronson 51:11 Okay.

Lex Fridman 51:12 And he's been told for decades, every year, that the Moore's Law is goi- going to die this year.

Scott Aaronson 51:20 Mm.

Lex Fridman 51:20 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-

Scott Aaronson 51:28 How long? How long did he say?

Lex Fridman 51:29 Well, the, well, he's-

Scott Aaronson 51:30 Yeah.

Lex Fridman 51:30 It's the, the main point is it's still alive.

Scott Aaronson 51:33 Okay.

Lex Fridman 51:34 But he thinks, uh, there's still 1,000X improvement just-

Scott Aaronson 51:38 Okay.

Lex Fridman 51:38 ... on shrinking the transistors that's possible.

Scott Aaronson 51:41 Mm.

Lex Fridman 51:41 Whatever. The point is that the exponential growth we see, it is actually a huge number of these S-curves.

Scott Aaronson 51:49 Mm-hmm.

Lex Fridman 51:49 Just constant breakthroughs.

Scott Aaronson 51:51 Mm-hmm.

Lex Fridman 51:51 At the philosophical level-

Scott Aaronson 51:53 Mm-hmm.

Lex Fridman 51:53 ... why do you think we, as a descendants of apes, were able to c-

Scott Aaronson 51:58 (laughs)

Lex Fridman 51:59 ... to just keep coming up with these new breakthroughs on the CPU side? Is this something unique to this particular endeavor?

Scott Aaronson 52:07 Mm.

Lex Fridman 52:07 Or will it be r- possible to replicate in the quantum computer space?

Scott Aaronson 52:11 (laughs) Okay. All right. The, the, there, there was a lot there to, to, to, uh, but, but just to, to-

Lex Fridman 52:16 Mm.

Scott Aaronson 52:16 ... to, uh, break off something, I mean, I think we are in an extremely special period of human history.

Lex Fridman 52:22 Yeah.

Scott Aaronson 52:22 Right? It, I mean, it's, it is, uh, you could say, obviously special, you know, in, in, in, in many ways, right? There are, you know, uh, uh, uh, you know, way more people alive than there, than there, than there have been. And, and, uh, you know, the, uh, um, um, you know, the whole, you know, uh, future of the planet is in, is in, is in question in a way that it, it, it hasn't been, you know, for, for, uh, the rest of human history. But, but, uh, you know, in particular, you know, we are in, in the era where, you know, we, we finally figured out how to build, you know, universal, uh, uh, machines. You could say, you know, the things that we call computers, you know, machines-

Lex Fridman 53:01 Mm-hmm.

Scott Aaronson 53:01 ... that you program to, uh, uh, simulate the behavior of, of whatever machine you want. And, um, you know, and, and, and, and, and, and, and, and once you've sort of crossed this threshold of universality, you know, you've built, you could say, you know, Turing ... You've instantiated Turing machines in the physical world. Well, then the main questions are, are ones of numbers. They are, you know, ones of how many, uh, uh, um, how much memory, uh, c- can you access? How fast does it run? How many parallel processors? You know, at least until quantum computing. Quantum computing is the one thing that changes what I just said. Right?

Lex Fridman 53:38 Yeah, yeah. It's, it's phase shift.

Scott Aaronson 53:38 But, you know, in, you know, as lo- as lo- as long as it's classical computing, then it's all questions of numbers. And, uh, uh, uh, you know, the, the, you could say at a theoretical level, the computers that we have today are, are the same as the ones in the '50s. They're just millions of times, you know, faster, with millions of times more memory. And, you know, I mean, I think there's been an immense economic pressure to, you know, get more and more transistors, you know, get them smaller and smaller, get, you know, add more and more cores. And, um, you know, and, and, and, and in, in, in some sense, like, a huge fraction of sort of all of the technological progress that there is in all of civilization has gotten concentrated just more narrowly into just those problems, right? And so, you know, it has been one of the biggest success stories in the history of technology, right? There's, you know ... I mean, it is ... I, I am as amazed by it as, as anyone else is, right? But at, at the same time, you know, we also know that it, you know, and I, I, I, I, I, uh, uh, I really do mean we know that it cannot continue indefinitely. Okay? Because you will reach, you know, fundamental limits on, um, you know, how small you can possibly make a processor. And, you know, if you want a real proof, you know, that would justify my use of the word, you know, we know that, you know, Moore's Law has to end, I mean, ultimately you will reach the limits imposed by quantum gravity.

Lex Fridman 55:08 Mm-hmm.

Scott Aaronson 55:08 You know? (laughs) You know, if, if you were doing, uh, if you tried to build a computer that operated at 10 to the 43 hertz, so it did 10 to the 43 operations per second, that computer would use so much energy that it would simply collapse to a black hole.

Lex Fridman 55:23 Mm-hmm.

Scott Aaronson 55:23 Okay? (laughs) So, you know, that, and you know, i- n- and you know, i- in, in, in reality, we're going to reach the limits long before that. But, you know, that is a sufficient proof that you know-

Lex Fridman 55:32 That there's a limit.

Scott Aaronson 55:33 (laughs) Yes, yes.

Lex Fridman 55:36 But it would be interesting to try to understand the mechanism, the economic pressure that you said. Just like-

Scott Aaronson 55:41 Yeah.

Lex Fridman 55:41 ... the Cold War was the pressure on getting us, uh, getting us-

Scott Aaronson 55:45 Mm.

Lex Fridman 55:46 ... get- uh, 'cause I'm both, my us is both the Soviet Union and-

Scott Aaronson 55:50 Mm.

Lex Fridman 55:50 ... the United States.

Scott Aaronson 55:51 Yeah.

Lex Fridman 55:51 But getting us, the two countries to get, to hurry up, to get the space, to the moon-

Scott Aaronson 55:56 Uh-huh.

Lex Fridman 55:56 ... there seems to be that same kind of economic pressure that somehow created a chain of engineering breakthroughs that resulted in-

Scott Aaronson 56:05 Yeah.

Lex Fridman 56:05 ... the Moore's Law.

Scott Aaronson 56:06 Yeah, well-

Lex Fridman 56:06 And it'd be nice to replicate.

Scott Aaronson 56:07 Yeah, well, I mean, I mean, some people are sort of, uh, uh, um, get depressed about the fact that technological progress, you know, may seem to have slowed down in, in many, many realms outside of computing.

Lex Fridman 56:19 Right.

Scott Aaronson 56:20 Right? And there was this whole thing of, you know, we wanted flying cars, and we only got Twitter instead. Right? (laughs)

Lex Fridman 56:26 Yeah, Peter-

Scott Aaronson 56:26 But-

Lex Fridman 56:26 Good old Peter Thiel, yeah.

Scott Aaronson 56:27 Yeah, yeah, yeah, right. Re- right.

Lex Fridman 56:29 So, and then jumping to another really interesting topic that you mentioned, so-...

Lex Fridman 56:33 Google-

Scott Aaronson 56:34 Mm.

Lex Fridman 56:35 ... announced with their work in, uh, the, the paper in nature with quantum supremacy.

Scott Aaronson 56:40 Yes.

Lex Fridman 56:41 Can you describe, again back to the basic, what is, perhaps not so basic, what is quantum supremacy?

Scott Aaronson 56:48 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-

Lex Fridman 57:08 It's technically quantum computational com- uh, supremacy.

Scott Aaronson 57:10 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.

Lex Fridman 57:45 Yes.

Scott Aaronson 57:45 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.

Lex Fridman 58:04 Can you clarify-

Scott Aaronson 58:05 Yeah.

Lex Fridman 58:05 ... a small point? You said much faster than a classical implementation.

Scott Aaronson 58:09 Yeah.

Lex Fridman 58:09 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-

Scott Aaronson 58:18 Oh.

Lex Fridman 58:18 ... solve the problem.

Scott Aaronson 58:18 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-

Lex Fridman 58:41 Mm-hmm.

Scott Aaronson 58:41 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.

Lex Fridman 59:01 So, quantum computers don't go to some magical place outside of Alan Turing's-

Scott Aaronson 59:05 They don't.

Lex Fridman 59:05 ... definition of computation?

Scott Aaronson 59:06 Precisely. They do not solve the halting problem.

Lex Fridman 59:09 Right.

Scott Aaronson 59:10 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.

Lex Fridman 59:19 Mm.

Scott Aaronson 59:19 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.

Lex Fridman 59:33 Mm-hmm.

Scott Aaronson 59:33 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?

Lex Fridman 59:47 So, yeah, so I, I do hope we get to talk again because-

Scott Aaronson 59:50 Mm.

Lex Fridman 59:50 ... one of the many topics that there's probably several hours worth of comp-

Scott Aaronson 59:55 Mm-hmm.

Lex Fridman 59:55 ... conversation on is complexity, which-

Scott Aaronson 59:57 Yes.

Lex Fridman 59:57 ... we probably won't even get a chance to touch-

Scott Aaronson 59:59 (laughs) Mm.

Lex Fridman 59:59 ... today. But, uh, you briefly mentioned it.

Scott Aaronson 1:00:02 Uh-huh.

Lex Fridman 1:00:02 But let's, uh, let's maybe try to continue. So you said, uh, the definition of quantum supremacy is basically, uh, designed, is achieving a place where much faster on a formal-

Scott Aaronson 1:00:14 Mm-hmm.

Lex Fridman 1:00:15 ... that a quantum computer is much faster on a formal well-defined problem-

Scott Aaronson 1:00:18 Yes.

Lex Fridman 1:00:19 ... that's n- that is or isn't useful.

Scott Aaronson 1:00:21 Yeah, yeah, yeah, right, right. And, and I would say that we really want three things, right? We want, first of all, the quantum computer to be much faster just in the literal sense of like number of seconds, you know? Uh, and just solving this, you know, well-defined, you know, problem. Secondly, we want it to be sort of, uh, uh, you know, for a problem where we really believe that a quantum computer has better scaling behavior, right? So, it's not just an incidental, you know, matter of hardware, but it's that, you know, as you went to larger and larger inputs, you know, the classical scaling would be exponential and the scaling f- for the quantum algorithm would only be polynomial. And then thirdly, we want the first thing, the actual observed speed up, to only be explainable in terms of the scaling behavior, right? So, you know, I want, I want, you know, a, a real world, you know, a real problem to get solved, uh, let's say by a quantum computer with 50 qubits-

Lex Fridman 1:01:19 Mm-hmm.

Scott Aaronson 1:01:20 ... or so, and for no one to be able to explain that in any way other than, well, you know, t- to, uh, th- uh, this, this computer involved a quantum state with two to the 50th power amplitudes. And, you know, a classical simulation, at least any that we know today, would require keeping track of two to the 50th numbers, and this is the reason why it was faster.

Lex Fridman 1:01:42 So, the intuition is that-

Scott Aaronson 1:01:43 Yeah.

Lex Fridman 1:01:43 ... then if you demonstrate, uh, on 50 qubits, then once you get to 100 qubits, then it'll be even m- much more faster.

Scott Aaronson 1:01:50 Precisely.

Lex Fridman 1:01:51 Right?

Scott Aaronson 1:01:51 Precisely. Yeah, and, and, you know, and, and, and quantum supremacy does not require error correction, right? We don't, you know, we don't have you could say true scalability yet, or true, you know, uh, uh, uh, uh, error correction yet. But you could say quantum supremacy is already enough by itself to refute the skeptics who said a quantum computer will never outperform a classical computer for anything.

Lex Fridman 1:02:15 But one, how do you demonstrate-

Scott Aaronson 1:02:18 Mm-hmm.

Lex Fridman 1:02:18 ... quantum-

Scott Aaronson 1:02:19 Yeah.

Lex Fridman 1:02:19 ... supremacy? And two, what's up with these new- news articles I'm reading that Google did so?

Scott Aaronson 1:02:26 Yeah. All right, well, uh-

Lex Fridman 1:02:26 What did they actually do?

Scott Aaronson 1:02:27 ... uh, uh great, great, great questions 'cause now you get into, uh, uh, actually, you know, a lot of the work that I've-... you know, I and my students have been doing for the last decade, which was precisely about, uh, uh, how do you demonstrate quantum supremacy using technologies that, you know, we thought would be available in the near future. And so, um, one of the main things that, uh, we realized i- around 2011, and this was, um, me and my student, uh, Alex Arkhipov at, at MIT at the time, and, uh, independently, uh, some, um, um, others including, uh, Bremner, Joza, and Shepherd. Okay? And, uh, uh, the, the realization that, that, that we came to was that if you just want to prove that a quantum computer is faster, you know, and not do something useful with it-

Lex Fridman 1:03:17 Mm-hmm.

Scott Aaronson 1:03:17 ... then there are huge advantages to sort of switching your attention from problems like factoring numbers that have a single right answer to, uh, what we call sampling problems. So, these are problems where the goal is just to output a sample from some probability distribution, let's say over strings of 50 bits. Right? So, there are, you know, many, many, many possible valid outputs. You know, your computer will probably never even produce the same output twice, you know, if it's running as, as, uh, uh, uh, uh, uh, even, you know, assuming it's running perfectly. Okay? But, but the key is that some outputs are supposed to be likelier than other ones. So-

Lex Fridman 1:03:58 S- Sorry-

Scott Aaronson 1:03:58 Yeah?

Lex Fridman 1:03:58 ... to, to clarify, i- is there a set of outputs that are valid and a set that are not? Or is it more that-

Scott Aaronson 1:04:05 It's-

Lex Fridman 1:04:05 ... the distribution-

Scott Aaronson 1:04:07 Mm-hmm.

Lex Fridman 1:04:08 ... of a particular kind of output is more l- i- is, like there's-

Scott Aaronson 1:04:12 Yeah.

Lex Fridman 1:04:12 ... a specific distribution for a particular kind of output?

Scott Aaronson 1:04:13 Yeah. There's a, there's, there's, there's, there's a specific distribution that you're trying to hit, right? Or, you know, that you're trying to sample from. Now, there are a lot of questions about this. You know, how do you do that, right? Now, now, how you, how, how you do it, you know, it turns out that with a quantum computer, even with the noisy quantum computers that we have now, that we have today, what you can do is basically just apply a randomly chosen sequence of operations.

Lex Fridman 1:04:40 Mm-hmm.

Scott Aaronson 1:04:40 Right? So, we, you know, we ... And sometimes, you know, we, you know, that part is almost trivial, right? We just sort of get the qubits to interact in some random way, although a sort of precisely specified random way, so we can repeat the exact same random sequence of interactions again, and get another sample from that same distribution. And what this does is it basically, well, it creates a lot of garbage, but, you know, very specific garbage, right? So, you know, s- o- of all of the, uh, so if we're gonna talk about Google's device, there were 53 qubits there, okay? And so there are two to the 53 power possible outputs.

Lex Fridman 1:05:18 Mm-hmm.

Scott Aaronson 1:05:18 Now, for some of those outputs, you know, there were, um, there was a little bit more destructive interference in their amplitude. Okay? So, their amplitudes were a little bit smaller. And for others, there was a little more constructive interference. You know, the amplitudes were a little bit more aligned with each other, you know, the ... And so those, those that were a little bit likelier, okay?

Lex Fridman 1:05:38 Mm-hmm.

Scott Aaronson 1:05:39 All of the outputs are exponentially unlikely, but some are, let's say, two times or three times, you know, unlikelier than others.

Lex Fridman 1:05:47 Okay.

Scott Aaronson 1:05:47 Okay? And, uh, so, so you can define, you know, the sequence of operations that gives rise to this probability distribution. Okay, now, um, the next question would be, well, how do you, you know, even if you're sampling from it, how do you verify that?

Lex Fridman 1:06:02 Right, exactly.

Scott Aaronson 1:06:03 How do you, how do you know? And so, um, my students and I, and also the, uh, people at Google who were doing the experiment, came up with s- statistical tests that you could apply to the outputs, uh, in order to, uh, uh, um, try to verify, you know, what is, you know, that, that, uh, that, uh, at least that some hard problem is being solved. Uh, the, the test that Google ended up using w- was something that they called the linear cross-entropy benchmark. Okay? And it's basically, you know, so the, the, the drawback of this test is that it requires, like, it requires you to do a two to the 53 time c- calculation with your classical computer. Okay? So it r- so it's very expensive-

Lex Fridman 1:06:46 Oh. (laughs)

Scott Aaronson 1:06:47 ... to do the test on a classical computer.

Lex Fridman 1:06:49 Yeah.

Scott Aaronson 1:06:49 The good news is-

Lex Fridman 1:06:50 How big of a number is two f- to the 53?

Scott Aaronson 1:06:51 It's about nine quadrillion.

Lex Fridman 1:06:53 Okay. That doesn't help.

Scott Aaronson 1:06:54 (laughs) Well, you know, it's a-

Lex Fridman 1:06:56 (laughs)

Scott Aaronson 1:06:56 You want it in-

Lex Fridman 1:06:57 I mean-

Scott Aaronson 1:06:57 ... like scientific notation? No, I mean, it's a-

Lex Fridman 1:06:58 No, no, no. What I mean is, uh-

Scott Aaronson 1:07:00 Yeah. It is, it is, it is just-

Lex Fridman 1:07:01 ... uh, it's impossible to run on a supercomputer?

Scott Aaronson 1:07:03 Yeah, so we will come b- back to that.

Lex Fridman 1:07:04 Yeah.

Scott Aaronson 1:07:04 It is just barely possible to run, we think, on the largest supercomputer that currently exists on Earth, which is called Summit at Oak Ridge National Lab. Okay? (laughs)

Lex Fridman 1:07:15 Great. This is exciting.

Scott Aaronson 1:07:17 That's the, that's the, that's the short answer. So, so, I, I, ironically, for this type of experiment, we don't want 100 qubits, okay? Because with 100 qubits, even if it works, we don't know how to verify the results.

Lex Fridman 1:07:29 Mm-hmm.

Scott Aaronson 1:07:29 Okay? So, we want, you know, a number of qubits that is enough that, you know, qu- the biggest classical computers on Earth will have to sweat, you know, and will just barely, you know, be able to keep up with, with the quantum computer, you know, using much more time. But they will still be able to do it in order that we can verify the results.

Lex Fridman 1:07:48 Which is where the 53 comes from for the q- number of qubits?

Scott Aaronson 1:07:50 R- basically, well, I mean, I mean, I mean, I mean, that- I mean, that's also, that's sort of, you know, th- the mo- I mean, that's, that's, that's sort of where they are now-

Lex Fridman 1:07:58 Yeah.

Scott Aaronson 1:07:58 ... in terms of scaling. You know, and then, you know, soon, you know, that point will be passed, and, and then when you get to larger numbers of qubits, then, you know, these, these types of sampling experiments will no longer be so interesting, because we w- we won't even be able to verify the results, and we'll have to switch to other types of computation. So, with the, with the sampling thing, you know, so, so the test that Google applied w- this linear cross-entropy benchmark would basically just take the samples that were generated-

Lex Fridman 1:08:28 Mm-hmm.

Scott Aaronson 1:08:28 ... which are, you know, a s- very small subset of all the possible samples that there are. But for those, you calculate, with your classical computer, the probabilities that they should've been output.

Lex Fridman 1:08:39 Mm-hmm.

Scott Aaronson 1:08:39 And you see, are those probabilities, like, larger than the mean, you know? So, is the quantum computer biased toward outputting the, the strings that it's, you know, that, that you want it to be biased toward? Okay? And then finally, we come to a very crucial question, which is supposing that it does that, well, how do we know that a classical computer could not have quickly done the same thing?... right? How do we know that, you know, this couldn't have been spoofed by a classical computer, right? And so, uh, well, the first answer is, we don't know for sure, because, you know, this takes us into questions of complexity theory.

Lex Fridman 1:09:13 Right.

Scott Aaronson 1:09:13 You know, uh, you know, the, I mean, questions on the, of the magnitude of the P versus NP question, and things like that, right?

Lex Fridman 1:09:20 Right.

Scott Aaronson 1:09:20 We, you know, we don't know how to rule out, uh, definitively that there could be fast classical algorithms for, you know, even simulating quantum mechanics, and, uh, for, you know, simulating experiments like these. But we can give some evidence against that possibility, and that was sort of the, you know, the main thrust of a lot of the work that my colleagues and I did, you know, over the last decade, which is then, sort of in around 2015 or so, what led to Google deciding to do this experiment.

Lex Fridman 1:09:50 So, uh, is the kind of evidence you're... First of all, the hard P equals NP problem that you mentioned-

Scott Aaronson 1:09:55 Mm-hmm. Mm-hmm.

Lex Fridman 1:09:56 ... and the kind of, uh, evidence that you're, uh, were looking at, is that something you come to on a sheet of paper, or is this something... Are these empirical experiments?

Scott Aaronson 1:10:07 It's- it's math, for the most part. I mean, it- it, you know, it's also tr- you know, we know, we have a bunch of s- uh, methods that are known for simulating quantum, uh, uh, uh, circuits, or, you know, quantum computations with classical computers. And so we have to try them all out and make sure that, you know, they don't work, you know?

Lex Fridman 1:10:27 Right.

Scott Aaronson 1:10:28 Make sure that they have exponential scaling on- on- on, you know, these problems, and- and not just theoretically, but with the actual range of parameters that are actually, you know, uh, uh, arising in Google's experiment. Okay? So- so there is an empirical component to it, right? But now, um, on- uh, on- on the theoretical side, you know, what... Basically, what we know how to do in theoretical computer science and computational complexity is, you know, we don't know how to prove that most of the problems we care about are hard, but we know how to pass the blame to someone else.

Lex Fridman 1:11:01 (laughs) Right.

Scott Aaronson 1:11:01 Okay? We know how to say, "Well, look, you know, I can't prove that this problem is hard, but if it is easy, then all these other things that, you know, you know, for s- you probably were- were much more confident or were- were hard, th- then those would be easy as well." Okay? So- so we can give what are called reductions. And this has been the basic strategy in, you know, in NP-completeness, right? In- in all of theoretical computer science and cryptography since the 1970s, really. And so we were able to give some reduction evidence for the hardness of simulating these, um, um, sampling experiments, these sampling-based quantum supremacy experiments. The reduction evidence is not as satisfactory as it should be. One of the biggest open problems in this area is to make it better. But, you know, we can do something. You know, certainly, we can sh- say that, you know, if there is a fast classical algorithm to spoof these experiments, then it has to be very, very unlike any of the algorithms that we know.

Lex Fridman 1:12:07 Which is kind of in the same kind of space of reasoning that people say P equal- not equals NP, is- is-

Scott Aaronson 1:12:13 Yeah, it- it- it's in the same spirit.

Lex Fridman 1:12:15 Yeah, in the same spirit. Okay, so,

Lex Fridman 1:12:19 Andrew Yang-

Scott Aaronson 1:12:20 Mm-hmm.

Lex Fridman 1:12:20 ... a very intelligent...

Scott Aaronson 1:12:22 Mm-hmm.

Lex Fridman 1:12:23 ... 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.

Scott Aaronson 1:12:35 Mm-hmm.

Lex Fridman 1:12:36 Is he wrong or right?

Scott Aaronson 1:12:38 Uh, he was, uh, premature, let's say. Uh, so, well, okay, uh, uh, wrong. (laughs)

Lex Fridman 1:12:44 (laughs)

Scott Aaronson 1:12:44 So, look, I, you know, I- I'm- I'm actually, I'm- I'm, you know, I'm a fan of Andrew Yang.

Lex Fridman 1:12:49 Mm-hmm.

Scott Aaronson 1:12:49 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-

Lex Fridman 1:13:12 Yeah.

Scott Aaronson 1:13:12 ... 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-

Lex Fridman 1:13:23 Mm-hmm.

Scott Aaronson 1:13:23 ... 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.

Lex Fridman 1:13:44 Mm-hmm.

Scott Aaronson 1:13:44 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.

Lex Fridman 1:13:57 Yeah.

Scott Aaronson 1:13:57 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-

Lex Fridman 1:14:37 'Cause error correction would be required to threaten-

Scott Aaronson 1:14:40 Yes.

Lex Fridman 1:14:40 ... cryptography.

Scott Aaronson 1:14:41 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.

Lex Fridman 1:15:02 Mm-hmm.

Scott Aaronson 1:15:03 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?

Lex Fridman 1:15:51 (laughs)

Scott Aaronson 1:15:51 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.

Lex Fridman 1:16:13 Wow.

Scott Aaronson 1:16:14 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?

Scott Aaronson 1:17:11 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.

Lex Fridman 1:17:35 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?

Scott Aaronson 1:17:52 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-

Lex Fridman 1:18:10 Okay.

Scott Aaronson 1:18:10 ... 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-

Lex Fridman 1:18:28 So there's an aggressive race to come up with-

Scott Aaronson 1:18:31 Yes.

Lex Fridman 1:18:31 ... the one case study, kind of like with-

Scott Aaronson 1:18:33 Yeah.

Lex Fridman 1:18:33 ... Peter Shor, though- with the-

Scott Aaronson 1:18:35 Mm-hmm.

Lex Fridman 1:18:35 ... with the idea that would just capture the world's imagination of like-

Scott Aaronson 1:18:38 Yeah.

Lex Fridman 1:18:39 ... "Look, we can actually do something very-"

Scott Aaronson 1:18:41 Yeah.

Lex Fridman 1:18:41 "... useful here."

Scott Aaronson 1:18:41 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-

Lex Fridman 1:19:33 Exactly.

Scott Aaronson 1:19:33 So- so tho- those are