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