back to index

Scott Aaronson: Quantum Computing | Lex Fridman Podcast #72


Chapters

0:0 Introduction
5:7 Role of philosophy in science
29:27 What is a quantum computer?
41:12 Quantum decoherence (noise in quantum information)
49:22 Quantum computer engineering challenges
51:0 Moore's Law
56:33 Quantum supremacy
72:18 Using quantum computers to break cryptography
77:11 Practical application of quantum computers
82:18 Quantum machine learning, questinable claims, and cautious optimism
90:53 Meaning of life

Whisper Transcript | Transcript Only Page

00:00:00.000 | The following is a conversation with Scott Aronson,
00:00:03.180 | a professor at UT Austin,
00:00:04.920 | director of its Quantum Information Center
00:00:07.200 | and previously a professor at MIT.
00:00:10.000 | His research interests center around the capabilities
00:00:12.840 | and limits of quantum computers
00:00:14.580 | and computational complexity theory more generally.
00:00:17.720 | He is an excellent writer
00:00:19.520 | and one of my favorite communicators
00:00:21.120 | of computer science in the world.
00:00:23.320 | We only had about an hour and a half for this conversation,
00:00:26.480 | so I decided to focus on quantum computing,
00:00:29.160 | but I can see us talking again in the future
00:00:30.920 | on this podcast at some point
00:00:33.240 | about computational complexity theory
00:00:35.640 | and all the complexity classes that Scott catalogs
00:00:38.480 | in his amazing Complexity Zoo Wiki.
00:00:41.100 | As a quick aside,
00:00:43.640 | based on questions and comments I've received,
00:00:46.040 | my goal with these conversations
00:00:48.200 | is to try to be in the background without ego
00:00:51.560 | and do three things.
00:00:53.400 | One, let the guests shine and try to discover together
00:00:56.980 | the most beautiful insights in their work
00:00:59.080 | and in their mind.
00:01:00.720 | Two, try to play devil's advocate,
00:01:02.920 | just enough to provide a creative tension
00:01:05.480 | in exploring ideas through conversation.
00:01:08.000 | And three, to ask very basic questions
00:01:11.720 | about terminology, about concepts, about ideas.
00:01:15.240 | Many of the topics we talk about in the podcast
00:01:18.720 | I've been studying for years,
00:01:20.560 | as a grad student, as a researcher,
00:01:22.760 | and generally as a curious human who loves to read.
00:01:26.160 | But frankly, I see myself in these conversations
00:01:29.160 | as the main character for one of my favorite novels
00:01:31.640 | by Dostoyevsky called "The Idiot."
00:01:35.120 | I enjoy playing dumb.
00:01:36.900 | Clearly it comes naturally.
00:01:39.040 | But the basic questions don't come from my ignorance
00:01:41.240 | of the subject, but from an instinct
00:01:43.660 | that the fundamentals are simple.
00:01:45.760 | And if we linger on them from almost a naive perspective,
00:01:48.980 | we can draw an insightful thread from computer science
00:01:52.240 | to neuroscience, to physics, to philosophy,
00:01:55.320 | and to artificial intelligence.
00:01:57.900 | This is the Artificial Intelligence Podcast.
00:02:01.480 | If you enjoy it, subscribe on YouTube,
00:02:03.680 | give it five stars on Apple Podcasts,
00:02:05.640 | support it on Patreon, or simply connect with me on Twitter
00:02:08.960 | at Lex Friedman, spelled F-R-I-D-M-A-N.
00:02:13.520 | As usual, I'll do one or two minutes of ads now,
00:02:16.440 | and never any ads in the middle
00:02:17.880 | that can break the flow of the conversation.
00:02:20.120 | I hope that works for you
00:02:21.520 | and doesn't hurt the listening experience.
00:02:24.100 | Quick summary of the ads.
00:02:25.560 | Two supporters today.
00:02:27.080 | First, get Cash App and use the code LEXPODCAST.
00:02:31.640 | Second, listen to the Tech Meme Ride Home Podcast
00:02:35.040 | for tech news.
00:02:36.280 | Search "ride home," two words, in your podcast app.
00:02:40.420 | This show is presented by Cash App,
00:02:43.440 | the number one finance app in the App Store.
00:02:45.880 | When you get it, use code LEXPODCAST.
00:02:49.320 | Cash App lets you send money to friends,
00:02:51.600 | buy Bitcoin, and invest in the stock market
00:02:54.100 | with as little as $1.
00:02:56.000 | Brokerage services are provided by Cash App Investing,
00:02:59.020 | a subsidiary of Square, a member of SIPC.
00:03:03.020 | Since Cash App does fractional share trading,
00:03:05.340 | let me mention that the order execution algorithm
00:03:08.180 | that works behind the scenes
00:03:09.760 | to create the abstraction of fractional orders
00:03:12.500 | is an algorithmic marvel.
00:03:14.620 | So big props to the Cash App engineers
00:03:16.940 | for solving a hard problem that, in the end,
00:03:19.460 | provides an easy interface that takes a step up
00:03:22.260 | to the next layer of abstraction over the stock market,
00:03:25.140 | making trading more accessible for new investors
00:03:28.480 | and diversification much easier.
00:03:31.700 | So again, if you get Cash App
00:03:33.580 | from the App Store or Google Play
00:03:35.380 | and use the code LEXPODCAST, you'll get $10,
00:03:39.220 | and Cash App will also donate $10 to FIRST,
00:03:42.080 | one of my favorite organizations
00:03:44.100 | that is helping to advance robotics and STEM education
00:03:47.360 | for young people around the world.
00:03:49.580 | This episode is also supported
00:03:52.220 | by the Tech Meme Ride Home podcast.
00:03:55.740 | It's a technology podcast I've been listening to for a while
00:03:58.620 | and really enjoying.
00:04:00.260 | It goes straight to the point,
00:04:01.740 | gives you the tech news you need to know,
00:04:03.660 | and provides minimal but essential context.
00:04:07.080 | It's released every day by 5 p.m. Eastern,
00:04:09.980 | and is only about 15 to 20 minutes long.
00:04:12.600 | For fun, I like building apps on smartphones,
00:04:16.260 | most on Android, so I'm always a little curious
00:04:18.820 | about new flagship phones that come out.
00:04:21.120 | I saw that Samsung announced the new Galaxy S20,
00:04:25.620 | and of course, right away,
00:04:27.700 | Tech Meme Ride Home has a new episode
00:04:30.520 | that summarizes all that I needed to know
00:04:33.220 | about this new device.
00:04:35.540 | They've also started to do weekend bonus episodes
00:04:38.580 | with interviews of people like AOL founder Steve Case
00:04:42.020 | on investing and Gary Marcus on AI,
00:04:45.580 | who I've also interviewed on this podcast.
00:04:48.700 | You can find the Tech Meme Ride Home podcast
00:04:51.580 | if you search your podcast app for ride home, two words.
00:04:56.580 | Then subscribe, enjoy, and keep up to date
00:05:00.140 | with the latest tech news.
00:05:02.580 | And now, here's my conversation with Scott Aronson.
00:05:06.660 | I sometimes get criticism from a listener here and there
00:05:11.640 | that while having a conversation
00:05:13.400 | with a world-class mathematician, physicist,
00:05:16.180 | neurobiologist, aerospace engineer,
00:05:18.180 | or a theoretical computer scientist like yourself,
00:05:21.740 | I waste time by asking philosophical questions
00:05:24.660 | about free will, consciousness, mortality,
00:05:28.340 | love, nature of truth, superintelligence,
00:05:31.900 | whether time travel is possible,
00:05:33.500 | whether space-time is emergent and fundamental,
00:05:35.940 | even the crazier questions like whether aliens exist,
00:05:39.420 | what their language might look like,
00:05:40.820 | what their math might look like,
00:05:43.020 | whether math is invented or discovered,
00:05:44.680 | and of course, whether we live in a simulation or not.
00:05:47.940 | So I try-- - Out with it.
00:05:49.880 | - Out with it.
00:05:51.360 | I try to dance back and forth from the deep technical
00:05:55.460 | to the philosophical, so I've done that quite a bit.
00:05:59.060 | So you're a world-class computer scientist,
00:06:01.700 | and yet you've written about this very point
00:06:04.140 | that philosophy is important for experts
00:06:06.700 | in any technical discipline,
00:06:09.040 | though they somehow seem to avoid this.
00:06:12.040 | So I thought it'd be really interesting
00:06:13.460 | to talk to you about this point.
00:06:15.100 | Why should we computer scientists, mathematicians,
00:06:17.740 | physicists care about philosophy, do you think?
00:06:20.780 | - Well, I would reframe the question a little bit.
00:06:23.020 | I mean, philosophy, almost by definition,
00:06:26.760 | is the subject that's concerned with the biggest questions
00:06:30.940 | that you could possibly ask, right?
00:06:33.160 | So the ones you mentioned, right?
00:06:35.740 | Are we living in a simulation?
00:06:38.440 | Are we alone in the universe?
00:06:41.700 | How should we even think about such questions?
00:06:44.320 | Is the future determined?
00:06:45.980 | And what do we even mean by it being determined?
00:06:48.680 | Why are we alive at the time we are
00:06:51.740 | and not at some other time?
00:06:53.140 | When you sort of contemplate the enormity
00:06:58.620 | of those questions, I think you could ask,
00:07:01.020 | well, then why be concerned with anything else, right?
00:07:04.500 | Why not spend your whole life on those questions?
00:07:08.740 | And I think in some sense,
00:07:10.140 | that is the right way to phrase the question.
00:07:13.580 | And actually, what we learned, I mean, throughout history,
00:07:19.260 | but really starting with the scientific revolution,
00:07:21.940 | with Galileo and so on, is that there is a good reason
00:07:25.500 | to focus on narrower questions, more technical,
00:07:30.500 | mathematical or empirical questions.
00:07:33.620 | And that is that you can actually make progress on them,
00:07:36.500 | and you can actually often answer them.
00:07:39.260 | And sometimes they actually tell you something
00:07:41.740 | about the philosophical questions
00:07:43.820 | that sort of maybe motivated your curiosity as a child.
00:07:48.220 | They don't necessarily resolve
00:07:50.060 | the philosophical questions,
00:07:51.760 | but sometimes they reframe
00:07:53.300 | your whole understanding of them.
00:07:55.100 | And so for me, philosophy is just the thing
00:07:58.140 | that you have in the background from the very beginning
00:08:00.920 | that you want to, these are sort of the reasons
00:08:05.480 | why you went into intellectual life in the first place,
00:08:08.620 | at least the reasons why I did, right?
00:08:10.620 | But math and science are tools that we have
00:08:15.180 | for actually making progress,
00:08:17.540 | and hopefully even changing our understanding
00:08:21.480 | of these philosophical questions,
00:08:23.260 | sometimes even more than philosophy itself does.
00:08:26.420 | - Why do you think computer scientists avoid these questions?
00:08:30.560 | We'll run away from them a little bit,
00:08:31.900 | at least in the technical scientific discourse.
00:08:34.620 | - Well, I'm not sure if they do so
00:08:37.040 | more than any other scientist do.
00:08:39.180 | I mean, Alan Turing was famously interested,
00:08:44.180 | and one of his two most famous papers
00:08:49.420 | was in a philosophy journal, Mind.
00:08:52.100 | It was the one where he proposed the Turing test.
00:08:54.740 | He took Wittgenstein's course at Cambridge,
00:08:59.960 | argued with him.
00:09:01.480 | - I just recently learned that little bit,
00:09:03.880 | and it's actually fascinating.
00:09:05.380 | I was trying to look for resources
00:09:08.440 | in trying to understand where the sources
00:09:11.640 | of disagreement and debates between Wittgenstein
00:09:13.880 | and Turing were.
00:09:15.720 | That's interesting that these two minds
00:09:17.480 | have somehow met in the arc of history.
00:09:20.200 | - Yeah, well, the transcript of the course,
00:09:25.200 | which was in 1939, right,
00:09:26.880 | is one of the more fascinating documents
00:09:29.020 | that I've ever read, because Wittgenstein
00:09:32.560 | is trying to say, well, all of these formal systems
00:09:36.200 | are just complete irrelevancies, right?
00:09:41.200 | If a formal system is irrelevant, who cares?
00:09:44.560 | Why does that matter in real life, right?
00:09:46.880 | And Turing is saying, well, look,
00:09:49.000 | if you use an inconsistent formal system
00:09:51.160 | to design a bridge, the bridge may collapse, right?
00:09:55.160 | And so Turing, in some sense, is thinking decades ahead,
00:09:58.720 | I think, of where Wittgenstein is
00:10:01.640 | to where the formal systems are actually going to be used
00:10:05.080 | in computers, right, to actually do things in the world.
00:10:08.720 | You know, and it's interesting that Turing
00:10:10.440 | actually dropped the course halfway through.
00:10:13.980 | Because he had to go to Bletchley Park
00:10:15.360 | and work on something of more immediate importance.
00:10:18.280 | - That's fascinating.
00:10:19.960 | Take a step from philosophy to actual,
00:10:22.200 | like the biggest possible step to actual engineering
00:10:25.040 | with actual real impact.
00:10:26.440 | - Yeah, and I would say more generally, right,
00:10:30.400 | a lot of scientists are interested in philosophy,
00:10:35.120 | but they're also busy, right?
00:10:36.720 | And they have a lot on their plate,
00:10:39.480 | and there are a lot of sort of very concrete questions
00:10:42.760 | that are already not answered,
00:10:44.900 | but look like they might be answerable, right?
00:10:47.960 | And so then you could say, well, then why break your brain
00:10:52.920 | over these metaphysically unanswerable questions
00:10:55.960 | when there are all of these answerable ones instead?
00:10:59.360 | So I think, you know, for me,
00:11:03.280 | I enjoy talking about philosophy.
00:11:06.280 | I even go to philosophy conferences sometimes,
00:11:09.880 | such as the, you know, FQXI conferences.
00:11:12.080 | I enjoy interacting with philosophers.
00:11:14.960 | I would not want to be a professional philosopher
00:11:17.780 | because I like being in a field where I feel like,
00:11:20.960 | you know, if I get too confused
00:11:25.440 | about the sort of eternal questions,
00:11:27.140 | then I can actually make progress on something.
00:11:30.080 | - Can you maybe link on that for just a little longer?
00:11:32.480 | - Yeah.
00:11:33.320 | - What do you think is the difference?
00:11:34.600 | So like the corollary of the criticism
00:11:37.640 | that I mentioned previously,
00:11:40.040 | that why ask the philosophical questions
00:11:42.500 | of the mathematician,
00:11:43.840 | is if you want to ask philosophical questions,
00:11:46.220 | then invite a real philosopher on and ask them.
00:11:49.040 | So what's the difference between the way
00:11:51.200 | a computer scientist or mathematician
00:11:52.920 | ponders a philosophical question
00:11:54.640 | and a philosopher ponders a philosophical question?
00:11:57.300 | - Well, I mean, a lot of it just depends
00:11:59.300 | on the individual, right?
00:12:01.020 | It's hard to make generalizations about entire fields.
00:12:04.780 | But, you know, I think if we tried to,
00:12:09.620 | we tried to stereotype, you know,
00:12:11.460 | we would say that, you know,
00:12:14.300 | scientists very often will be less careful
00:12:19.300 | in their use of words.
00:12:21.860 | You know, I mean, philosophers are really experts
00:12:24.160 | in sort of, you know, like when I talk to them,
00:12:27.140 | they will just pounce if I, you know,
00:12:28.820 | use the wrong phrase for something.
00:12:30.780 | - Experts is a very nice word.
00:12:32.540 | You could say sticklers or--
00:12:34.140 | - Sticklers, yeah, yeah, yeah.
00:12:35.420 | Or, you know, they will sort of interrogate
00:12:37.940 | my word choices, let's say,
00:12:39.900 | to a much greater extent than scientists would, right?
00:12:42.900 | And scientists, you know, will often,
00:12:46.300 | if you ask them about a philosophical problem,
00:12:48.900 | like the hard problem of consciousness
00:12:51.860 | or free will or whatever,
00:12:53.540 | they will try to relate it back to, you know,
00:12:55.700 | recent research, you know,
00:12:57.460 | research about neurobiology or, you know,
00:13:01.860 | but, you know, the best of all is research
00:13:03.860 | that they personally are involved with, right?
00:13:06.440 | And, you know, and, you know,
00:13:07.980 | of course they will want to talk about that, you know,
00:13:10.380 | and it is what they will think of, you know,
00:13:12.220 | and of course you could have an argument
00:13:14.100 | that maybe, you know, it's all interesting as it goes,
00:13:17.280 | but maybe none of it touches the philosophical question.
00:13:20.660 | But, you know, but maybe, you know, a science,
00:13:24.260 | you know, at least it, as I said,
00:13:26.560 | it does tell us concrete things,
00:13:28.980 | and, you know, even if, like,
00:13:31.420 | a deep dive into neurobiology will not answer
00:13:34.500 | the hard problem of consciousness,
00:13:36.540 | you know, maybe it can take us about as far as we can get
00:13:40.500 | toward, you know, expanding our minds about it,
00:13:44.380 | you know, toward thinking about it in a different way.
00:13:48.720 | Well, I mean, I think neurobiology can do that,
00:13:51.040 | but, you know, with these profound philosophical questions,
00:13:53.800 | I mean, also art and literature do that, right?
00:13:56.900 | They're all different ways of trying
00:13:58.400 | to approach these questions that, you know,
00:14:00.240 | we don't, for which we don't even know, really,
00:14:02.200 | what an answer would look like,
00:14:03.680 | but, and yet somehow we can't help
00:14:06.160 | but keep returning to the questions.
00:14:07.760 | - And you have a kind of mathematical,
00:14:09.240 | a beautiful mathematical way of discussing this
00:14:11.260 | with the idea of Q prime.
00:14:12.760 | - Oh, right.
00:14:13.600 | - You write that usually the only way to make progress
00:14:16.800 | on the big questions, like the philosophical questions
00:14:20.040 | we're talking about now,
00:14:21.440 | is to pick off smaller sub-questions.
00:14:24.360 | Ideally, sub-questions that you can attack
00:14:26.360 | using math, empirical observation, or both.
00:14:29.120 | You define the idea of a Q prime,
00:14:31.380 | so given an unanswerable philosophical riddle, Q,
00:14:36.120 | replace it with a merely, in quotes,
00:14:39.060 | scientific or mathematical question, Q prime,
00:14:41.920 | which captures part of what people have wanted to know
00:14:44.840 | when they first asked Q.
00:14:46.860 | - Yes.
00:14:47.700 | - Then, with luck, one solves Q prime.
00:14:49.920 | So, you describe some examples of such Q prime sub-questions
00:14:54.920 | in your long essay titled,
00:14:59.240 | "Why Philosophers Should Care
00:15:00.400 | About Computational Complexity."
00:15:02.460 | So, you catalog the various Q primes
00:15:04.560 | on which you think theoretical computer science
00:15:07.160 | has made progress.
00:15:08.040 | Can you mention a few favorites,
00:15:09.920 | if any pop to mind, or that you remember?
00:15:12.920 | - Well, yes, so I would say some of the most famous examples
00:15:16.980 | in history of that sort of replacement were,
00:15:20.760 | I mean, to go back to Alan Turing, right?
00:15:23.280 | What he did in his computing machinery
00:15:26.480 | and intelligence paper was exactly,
00:15:29.360 | he explicitly started with the question,
00:15:32.080 | "Can machines think?"
00:15:33.880 | And then he said, "Sorry, I think that question
00:15:36.600 | "is too meaningless, but here's a different question.
00:15:40.340 | "Could you program a computer
00:15:42.100 | "so that you couldn't tell the difference
00:15:43.580 | "between it and a human?"
00:15:44.960 | Right?
00:15:45.800 | - So, in the very first few sentences,
00:15:47.960 | he, in fact, just formulates the Q prime question.
00:15:50.920 | - He does precisely that.
00:15:52.640 | Or, we could look at Godel, right?
00:15:56.180 | Where you had these philosophers arguing for centuries
00:16:00.480 | about the limits of mathematical reasoning, right?
00:16:03.160 | The limits of formal systems.
00:16:04.680 | And then, by the early 20th century,
00:16:08.760 | logicians, starting with Frege, Russell,
00:16:12.340 | and then most spectacularly, Godel,
00:16:15.480 | managed to reframe those questions as,
00:16:18.060 | look, we have these formal systems,
00:16:19.820 | they have these definite rules.
00:16:21.500 | Are there questions that we can phrase
00:16:23.480 | within the rules of these systems
00:16:25.740 | that are not provable within the rules of the systems?
00:16:28.220 | And can we prove that fact?
00:16:30.180 | Right?
00:16:31.020 | And so that would be another example.
00:16:34.060 | I had this essay called,
00:16:36.580 | "The Ghost in the Quantum Turing Machine."
00:16:39.060 | It's one of the crazier things I've written.
00:16:41.900 | But I tried to do something,
00:16:44.740 | or to advocate doing something similar there for free will.
00:16:48.740 | Where, instead of talking about,
00:16:50.900 | is free will real?
00:16:53.240 | Or we get hung up on the meaning of,
00:16:55.500 | what exactly do we mean by freedom?
00:16:57.500 | And can you have, can you be,
00:16:59.740 | or do we mean compatibilist free will?
00:17:02.220 | Libertarian free will?
00:17:03.660 | What do these things mean?
00:17:05.380 | I suggested just asking the question,
00:17:08.220 | how well, in principle,
00:17:10.260 | consistently with the laws of physics,
00:17:12.340 | could a person's behavior be predicted?
00:17:15.100 | You know, without, so let's say,
00:17:16.620 | destroying the person's brain, you know?
00:17:18.820 | Taking it apart in the process of trying to predict them.
00:17:22.140 | And you know, and that actually,
00:17:24.620 | asking that question gets you into
00:17:26.380 | all sorts of meaty and interesting issues.
00:17:29.220 | You know, issues of,
00:17:31.100 | what is the computational substrate of the brain?
00:17:33.820 | You know, or can you understand the brain,
00:17:36.820 | you know, just at the sort of level of the neurons?
00:17:39.340 | You know, at sort of the abstraction of a neural network?
00:17:42.340 | Or do you need to go deeper to the, you know,
00:17:44.900 | molecular level, and ultimately even to the quantum level?
00:17:48.020 | Right, and of course,
00:17:48.860 | that would put limits on predictability if you did.
00:17:52.660 | - So you need to reduce,
00:17:53.900 | you need to reduce the mind to a computational device,
00:17:58.560 | like formalize it so then you can make predictions about,
00:18:01.860 | you know, whether you could predict the behavior of a system.
00:18:03.900 | - Well, if you were trying to predict a person,
00:18:05.820 | yeah, then presumably you would need
00:18:07.380 | some model of their brain, right?
00:18:09.180 | And now the question becomes one of
00:18:11.180 | how accurate can such a model become?
00:18:13.780 | Can you make a model that will be accurate enough
00:18:16.740 | to really seriously threaten people's sense of free will?
00:18:21.060 | You know, not just metaphysically,
00:18:22.620 | but like really, I have written in this envelope
00:18:25.140 | what you were going to say next.
00:18:26.780 | - Is accuracy the right term here?
00:18:28.940 | So it's also a level of abstraction has to be right.
00:18:32.620 | So if you're accurate at the, somehow at the quantum level,
00:18:37.620 | that may not be convincing to us at the human level.
00:18:43.020 | - Well, right, but the question is what accuracy
00:18:46.140 | at the sort of level of the underlying mechanisms
00:18:49.020 | do you need in order to predict the behavior, right?
00:18:52.220 | At the end of the day, the test is just,
00:18:54.300 | can you, you know, foresee what the person is going to do?
00:18:57.820 | Right, I am, you know, and, you know,
00:19:00.980 | and in discussions of free will, you know,
00:19:03.580 | it seems like both sides wanna, you know,
00:19:06.300 | very quickly dismiss that question as irrelevant.
00:19:09.420 | Well, to me, it's totally relevant, okay?
00:19:11.700 | Because, you know, if someone says, oh, well, you know,
00:19:14.900 | a Laplace demon that knew the complete state of the universe,
00:19:19.900 | you know, could predict everything you're going to do,
00:19:22.140 | therefore you don't have free will, you know,
00:19:24.300 | that it doesn't trouble me that much because, well, you know,
00:19:27.420 | I've never met such a demon, right?
00:19:29.300 | I, you know, and we, you know,
00:19:32.780 | we even have some reasons to think, you know,
00:19:34.580 | maybe, you know, it could not exist as part of our world.
00:19:37.260 | You know, it was only an abstraction, a thought experiment.
00:19:40.740 | On the other hand, if someone said, well, you know,
00:19:42.860 | I have this brain scanning machine, you know,
00:19:45.180 | you step into it and then, you know,
00:19:47.180 | every paper that you will ever write, it will write,
00:19:50.220 | you know, every thought that you will have, you know,
00:19:52.420 | even right now about the machine itself, it will foresee,
00:19:55.740 | you know, well, if you could actually demonstrate that,
00:19:58.620 | then I think, you know, that sort of threatens
00:20:01.620 | my internal sense of having free will
00:20:04.380 | in a much more visceral way, you know,
00:20:06.580 | but now you notice that we're asking
00:20:08.980 | a much more empirical question.
00:20:11.620 | We're asking, is such a machine possible or isn't it?
00:20:14.700 | We're asking, if it's not possible,
00:20:16.260 | then what in the laws of physics
00:20:18.380 | or what about the behavior of the brain,
00:20:21.220 | you know, prevents it from existing?
00:20:23.020 | - So if you could philosophize a little bit
00:20:25.300 | within this empirical question,
00:20:27.780 | where do you think would enter the,
00:20:31.460 | by which mechanism would enter the possibility
00:20:33.860 | that we can't predict the outcome?
00:20:35.620 | So there would be something
00:20:37.260 | that would be akin to a free will.
00:20:38.860 | - Yeah, well, you could say the sort of obvious possibility,
00:20:42.460 | which was, you know, recognized by Eddington
00:20:45.660 | and many others about as soon as quantum mechanics
00:20:48.060 | was discovered in the 1920s, was that if, you know,
00:20:54.100 | let's say a sodium ion channel, you know,
00:20:56.660 | in the brain, right, you know,
00:21:00.900 | its behavior is chaotic, right?
00:21:04.020 | It's sort of, it's governed by these
00:21:06.420 | Hodgley-Huxkin equations in neuroscience, right,
00:21:10.980 | which are differential equations
00:21:12.540 | that have a stochastic component, right?
00:21:14.820 | Now, where does, you know, and this ultimately governs,
00:21:17.140 | let's say, whether a neuron will fire or not fire, right?
00:21:19.540 | - So that's the basic chemical process
00:21:21.740 | or electrical process by which signals
00:21:23.900 | are sent in the brain.
00:21:24.820 | - Exactly, exactly, and, you know,
00:21:27.820 | and so you could ask, well, where does the randomness
00:21:30.500 | in the process, you know, that neuroscientists,
00:21:34.100 | or what neuroscientists would treat as randomness,
00:21:38.060 | where does it come from?
00:21:39.400 | You know, ultimately, it's thermal noise, right?
00:21:41.740 | Where does thermal noise come from?
00:21:43.620 | Well, ultimately, you know,
00:21:44.900 | there are some quantum mechanical events
00:21:46.820 | at the molecular level that are getting
00:21:48.660 | sort of chaotically amplified by, you know,
00:21:51.460 | a sort of butterfly effect, and so, you know,
00:21:55.340 | even if you knew the complete quantum state
00:21:59.260 | of someone's brain, you know, at best,
00:22:01.140 | you could predict the probabilities
00:22:02.840 | that they would do one thing or do another thing, right?
00:22:05.460 | I think that part is actually relatively uncontroversial,
00:22:08.580 | right, the controversial question is whether any of it
00:22:12.380 | matters for the sort of philosophical questions
00:22:15.340 | that we care about, because you could say,
00:22:17.220 | if all it's doing is just injecting some randomness
00:22:20.400 | into an otherwise completely mechanistic process,
00:22:23.700 | well, then who cares, right?
00:22:25.180 | And more concretely, if you could build a machine
00:22:28.500 | that, you know, could just calculate even just
00:22:32.380 | the probabilities of all of the possible things
00:22:34.860 | that you would do, right, and, you know,
00:22:37.040 | you know, of all the things that said
00:22:39.940 | you had a 10% chance of doing,
00:22:41.860 | you did exactly a 10th of them, you know,
00:22:43.980 | and so on and so on.
00:22:45.580 | - Yeah, that somehow also takes away
00:22:47.340 | the feeling of free will.
00:22:48.180 | - Exactly, I mean, to me, it seems essentially
00:22:51.120 | just as bad as if the machine deterministically
00:22:54.160 | predicted you, it seems, you know,
00:22:55.920 | hardly different from that.
00:22:57.360 | So then, but a more subtle question is,
00:23:02.360 | could you even learn enough about someone's brain
00:23:05.240 | to do that, okay, because, you know,
00:23:07.440 | another central fact about quantum mechanics
00:23:11.240 | is that making a measurement on a quantum state
00:23:15.160 | is an inherently destructive operation, okay?
00:23:18.380 | So, you know, if I want to measure the, you know,
00:23:21.700 | position of a particle, right, it was,
00:23:24.140 | well, before I measured, it had a superposition
00:23:26.580 | over many different positions.
00:23:28.460 | As soon as I measure, I localize it, right?
00:23:31.040 | So now I know the position, but I've also
00:23:33.020 | fundamentally changed the state.
00:23:35.300 | And so you could say, well, maybe in trying to build
00:23:39.980 | a model of someone's brain that was accurate enough
00:23:42.820 | to actually, you know, make, let's say,
00:23:45.080 | even well-calibrated probabilistic predictions
00:23:48.400 | of their future behavior, maybe you would have
00:23:50.760 | to make measurements that were just so accurate
00:23:53.180 | that you would just fundamentally alter their brain, okay?
00:23:56.200 | Or maybe not, maybe you only, you know,
00:23:59.600 | it would suffice to just make some nanorobots
00:24:02.440 | that just measured some sort of much larger scale,
00:24:05.740 | you know, macroscopic behavior, like, you know,
00:24:09.320 | what is this neuron doing, what is that neuron doing?
00:24:12.280 | Maybe that would be enough.
00:24:13.900 | See, but now, you know, what I claim is that
00:24:16.980 | we're now asking a question, you know,
00:24:19.280 | in which it is possible to envision
00:24:22.680 | what progress on it would look like.
00:24:24.640 | - Yeah, but just as you said, that question may be
00:24:27.880 | slightly detached from the philosophical question
00:24:30.500 | in the sense if consciousness somehow has a role
00:24:33.880 | to the experience of free will.
00:24:36.080 | Because ultimately, when we're talking about free will,
00:24:38.380 | we're also talking about not just the predictability
00:24:42.300 | of our actions, but somehow the experience
00:24:44.920 | of that predictability.
00:24:46.460 | - Yeah, well, I mean, a lot of philosophical questions
00:24:49.460 | ultimately, like feedback to the hard problem
00:24:52.300 | of consciousness, you know, and as much as you can try
00:24:55.280 | to sort of talk around it or not, right?
00:24:57.200 | And, you know, and there is a reason why people try
00:25:00.860 | to talk around it, which is that, you know,
00:25:03.600 | Democritus talked about the hard problem of consciousness,
00:25:07.800 | you know, in 400 BC in terms that would be
00:25:11.180 | totally recognizable to us today, right?
00:25:13.900 | And it's really not clear if there's been progress since
00:25:16.960 | or what progress could possibly consist of.
00:25:19.540 | - Is there a Q prime type of sub-question
00:25:22.420 | that could help us get at consciousness?
00:25:24.400 | It's something about consciousness.
00:25:25.680 | - Well, I mean, well, I mean, there is the whole question
00:25:27.740 | of, you know, of AI, right?
00:25:29.640 | Of, you know, can you build a human level
00:25:33.680 | or superhuman level AI?
00:25:35.960 | And, you know, can it work in a completely different
00:25:39.140 | substrate from the brain?
00:25:40.420 | I mean, you know, and of course that was Alan Turing's point
00:25:43.460 | and, you know, and even if that was done, it's, you know,
00:25:46.260 | maybe people would still argue about the hard problem
00:25:48.660 | of consciousness, right?
00:25:49.940 | And yet, you know, my claim is a little different.
00:25:53.120 | My claim is that in a world where, you know,
00:25:55.860 | there were, you know, human level AIs
00:25:58.980 | or where we'd been even overtaken by such AIs,
00:26:01.980 | the entire discussion of the hard problem of consciousness
00:26:05.940 | would have a different character, right?
00:26:07.640 | It would take place in different terms in such a world,
00:26:10.440 | even if we hadn't answered the question.
00:26:12.720 | And my claim about free will would be similar, right?
00:26:15.620 | That if this prediction machine that I was talking about
00:26:19.040 | could actually be built, well, now the entire discussion
00:26:21.980 | of the, you know, of free will is sort of transformed
00:26:24.620 | by that, you know, even if in some sense
00:26:27.340 | the metaphysical question hasn't been answered.
00:26:30.180 | - Yeah, exactly.
00:26:32.940 | It transforms it fundamentally because say that machine
00:26:35.240 | does tell you that it can predict perfectly
00:26:37.620 | and yet there is this deep experience of free will
00:26:40.100 | and then that changes the question completely.
00:26:43.100 | And it starts actually getting to the question of
00:26:46.540 | the AGI, the Turing questions,
00:26:52.220 | the demonstration of free will,
00:26:54.900 | the demonstration of intelligence,
00:26:56.540 | the demonstration of consciousness.
00:26:58.500 | Does that equal consciousness, intelligence, and free will?
00:27:02.280 | - But see, Alex, if every time I was contemplating
00:27:06.820 | a decision, you know, this machine had printed out
00:27:09.380 | an envelope, you know, where I could open it
00:27:11.540 | and see that it knew my decision,
00:27:13.220 | I think that actually would change my subjective experience
00:27:16.500 | of making decisions, right?
00:27:18.180 | I mean, it would-- - Does knowledge
00:27:19.260 | change your subjective experience?
00:27:20.860 | - Well, you know, I mean, the knowledge that this machine
00:27:23.460 | had predicted everything I would do,
00:27:25.020 | I mean, it might drive me completely insane, right?
00:27:27.780 | But at any rate, it would change my experience
00:27:30.700 | to not just discuss such a machine as a thought experiment
00:27:34.880 | but to actually see it.
00:27:36.120 | - Yeah.
00:27:37.920 | (laughing)
00:27:39.120 | - I mean, you know, you could say at that point,
00:27:41.720 | you know, you could say, you know,
00:27:43.920 | why not simply call this machine a second instantiation
00:27:47.280 | of me and be done with it, right?
00:27:49.120 | What, you know, why even privilege the original me
00:27:53.400 | over this perfect duplicate that exists in the machine?
00:27:56.880 | - Yeah, or there could be a religious experience with it too.
00:28:00.080 | It's kind of what God throughout the generations
00:28:02.440 | is supposed to have, that God kind of represents
00:28:05.400 | that perfect machine, is able to, I guess, actually,
00:28:09.580 | I don't even know, what are the religious interpretations
00:28:15.280 | of free will?
00:28:16.240 | So if God knows perfectly everything in religion,
00:28:22.600 | in the various religions, where does free will fit into that?
00:28:26.600 | Do you know?
00:28:27.440 | - That has been one of the big things
00:28:29.280 | that theologians have argued about for thousands of years.
00:28:32.080 | (laughing)
00:28:33.360 | You know, I am not a theologian,
00:28:35.280 | so maybe I shouldn't go there.
00:28:36.120 | - So there's not a clear answer in a book like--
00:28:38.880 | - I mean, this is, you know, the Calvinists debated this,
00:28:41.920 | the, you know, this has been, you know,
00:28:43.800 | I mean, different religious movements
00:28:46.120 | have taken different positions on that question,
00:28:48.120 | but that is how they think about it.
00:28:50.080 | You know, meanwhile, you know, a large part of sort of
00:28:53.400 | what animates, you know, theoretical computer science,
00:28:56.560 | you could say, is, you know, we're asking sort of,
00:28:58.440 | what are the ultimate limits of, you know,
00:29:01.040 | what you can know or, you know, calculate or figure out
00:29:05.480 | by, you know, entities that you can actually build
00:29:08.140 | in the physical world, right?
00:29:09.700 | And if I were trying to explain it to a theologian,
00:29:12.820 | maybe I would say, you know, we are studying, you know,
00:29:15.240 | to what extent, you know,
00:29:16.440 | gods can be made manifest in the physical world.
00:29:19.800 | I'm not sure my colleagues would like that.
00:29:21.440 | (laughing)
00:29:23.700 | - So let's talk about quantum computers for a minute.
00:29:25.600 | - Yeah, sure, sure.
00:29:27.320 | - As you've said, quantum computing,
00:29:29.200 | at least in the 1990s, was a profound story
00:29:32.280 | at the intersection of computer science,
00:29:33.960 | physics, engineering, math, and philosophy.
00:29:36.320 | So there's this broad and deep aspect to quantum computing
00:29:40.280 | that represents more than just the quantum computer.
00:29:42.560 | - Yes.
00:29:43.400 | - But can we start at the very basics?
00:29:45.160 | What is quantum computing?
00:29:47.680 | - Yeah, so it's a proposal for a new type of computation,
00:29:52.680 | or let's say a new way to harness nature to do computation
00:29:57.120 | that is based on the principles of quantum mechanics.
00:30:00.200 | Okay, now the principles of quantum mechanics
00:30:02.520 | have been in place since 1926.
00:30:06.040 | You know, they haven't changed.
00:30:08.080 | You know, what's new is, you know, how we wanna use them.
00:30:11.120 | Okay, so what does quantum mechanics say about the world?
00:30:15.640 | You know, the physicists, I think, over the generations,
00:30:18.560 | you know, convinced people that that is an unbelievably
00:30:21.200 | complicated question, and you know,
00:30:23.160 | just give up on trying to understand it.
00:30:25.680 | I can let you in, not being a physicist,
00:30:28.480 | I can let you in on a secret,
00:30:29.880 | which is that it becomes a lot simpler
00:30:32.480 | if you do what we do in quantum information theory
00:30:35.720 | and sort of take the physics out of it.
00:30:37.840 | So the way that we think about quantum mechanics
00:30:41.160 | is sort of as a generalization of the rules
00:30:43.800 | of probability themselves.
00:30:45.700 | So, you know, you might say there's a, you know,
00:30:48.920 | there was a 30% chance that it was going to snow today
00:30:52.280 | or something.
00:30:53.120 | You would never say that there was a negative 30% chance,
00:30:55.920 | right, that would be nonsense.
00:30:57.880 | Much less would you say that there was a, you know,
00:30:59.720 | an i% chance, you know, square root of minus 1% chance.
00:31:04.200 | Now, the central discovery that sort of quantum mechanics
00:31:09.200 | made is that fundamentally the world is described by,
00:31:14.400 | or you know, the sort of, let's say the possibilities
00:31:19.240 | for, you know, what a system could be doing
00:31:22.240 | are described using numbers called amplitudes, okay,
00:31:25.880 | which are like probabilities in some ways,
00:31:29.420 | but they are not probabilities.
00:31:31.180 | They can be positive, for one thing,
00:31:32.820 | they can be positive or negative.
00:31:34.900 | In fact, they can even be complex numbers, okay?
00:31:37.760 | And if you've heard of a quantum superposition,
00:31:40.360 | this just means that some state of affairs
00:31:43.560 | where you assign an amplitude,
00:31:45.760 | one of these complex numbers to every possible
00:31:50.480 | configuration that you could see a system in
00:31:52.680 | on measuring it.
00:31:53.680 | So for example, you might say that an electron
00:31:57.040 | has some amplitude for being here
00:31:59.760 | and some other amplitude for being there, right?
00:32:02.600 | Now, if you look to see where it is,
00:32:05.080 | you will localize it, right?
00:32:06.800 | You will sort of force the amplitudes
00:32:09.460 | to be converted into probabilities.
00:32:12.560 | That happens by taking their squared absolute value, okay?
00:32:15.760 | And then, you know, you can say
00:32:19.840 | either the electron will be here or it will be there.
00:32:22.960 | And, you know, knowing the amplitudes,
00:32:24.560 | you can predict at least the probabilities
00:32:26.920 | that you'll see each possible outcome, okay?
00:32:30.260 | But while a system is isolated
00:32:32.880 | from the whole rest of the universe,
00:32:35.020 | the rest of its environment,
00:32:36.760 | the amplitudes can change in time
00:32:39.160 | by rules that are different
00:32:41.740 | from the normal rules of probability
00:32:44.760 | and that are, you know, alien to our everyday experience.
00:32:47.840 | So anytime anyone ever tells you anything
00:32:50.680 | about the weirdness of the quantum world, you know,
00:32:53.280 | or assuming that they're not lying to you, right?
00:32:56.240 | They are telling you, you know,
00:32:58.000 | yet another consequence of nature
00:33:00.440 | being described by these amplitudes.
00:33:03.360 | So most famously, what amplitudes can do
00:33:06.120 | is that they can interfere with each other, okay?
00:33:08.360 | So in the famous double slit experiment,
00:33:11.560 | what happens is that you shoot a particle,
00:33:13.840 | like an electron, let's say,
00:33:15.520 | at a screen with two slits in it,
00:33:17.800 | and you find that there, you know, on a second screen,
00:33:21.280 | now there are certain places
00:33:22.920 | where that electron will never end up, you know,
00:33:25.600 | after it passes through the first screen.
00:33:29.680 | And yet, if I close off one of the slits,
00:33:32.700 | then the electron can appear in that place, okay?
00:33:35.560 | So by decreasing the number of paths
00:33:38.280 | that the electron could take to get somewhere,
00:33:40.820 | you can increase the chance that it gets there, okay?
00:33:43.520 | Now, how is that possible?
00:33:45.420 | Well, it's because, you know, as we would say now,
00:33:48.840 | the electron has a superposition state, okay?
00:33:51.880 | It has some amplitude for reaching this point
00:33:55.120 | by going through the first slit.
00:33:57.880 | It has some other amplitude for reaching it
00:33:59.960 | by going through the second slit.
00:34:01.800 | But now if one amplitude is positive
00:34:04.080 | and the other one is negative,
00:34:05.800 | then, you know, I have to add them all up, right?
00:34:08.160 | I have to add the amplitudes for every path
00:34:10.880 | that the electron could have taken to reach this point.
00:34:13.880 | And those amplitudes,
00:34:15.800 | if they're pointing in different directions,
00:34:17.900 | they can cancel each other out.
00:34:19.840 | That would mean the total amplitude is zero
00:34:22.220 | and the thing never happens at all.
00:34:24.340 | I close off one of the possibilities,
00:34:26.460 | then the amplitude is positive or it's negative
00:34:28.920 | and now the thing can happen.
00:34:30.580 | Okay, so that is sort of the one trick of quantum mechanics.
00:34:34.140 | And now I can tell you what a quantum computer is, okay?
00:34:37.140 | A quantum computer is a computer
00:34:41.340 | that tries to exploit, you know,
00:34:43.480 | these, exactly these phenomena,
00:34:45.720 | superposition, amplitudes, and interference
00:34:49.200 | in order to solve certain problems
00:34:51.400 | much faster than we know how to solve them otherwise.
00:34:54.520 | So it's the basic building block of a quantum computer
00:34:57.020 | is what we call a quantum bit or a qubit.
00:35:00.200 | That just means a bit that has some amplitude
00:35:02.600 | for being zero and some other amplitude for being one.
00:35:06.120 | So it's a superposition of zero and one states, right?
00:35:09.480 | But now the key point is that if I've got,
00:35:12.560 | let's say, a thousand qubits,
00:35:15.000 | the rules of quantum mechanics are completely unequivocal
00:35:18.320 | that I do not just need one, you know,
00:35:20.740 | I don't just need amplitudes for each qubit separately.
00:35:23.800 | Okay, in general, I need an amplitude
00:35:26.360 | for every possible setting of all thousand of those bits.
00:35:30.520 | Okay, so that what that means
00:35:32.120 | is two to the 1,000 power amplitudes.
00:35:35.120 | Okay, if I had to write those down,
00:35:37.880 | let's say in the memory of a conventional computer,
00:35:40.680 | if I had to write down two to the 1,000 complex numbers,
00:35:44.000 | that would not fit within the entire observable universe.
00:35:47.640 | Okay, and yet, you know, quantum mechanics is unequivocal
00:35:51.120 | that if these qubits can all interact with each other,
00:35:54.120 | and in some sense, I need two to the 1,000 parameters,
00:35:58.280 | you know, amplitudes to describe what is going on.
00:36:01.440 | Now, you know, now I can tell you, you know,
00:36:03.840 | where all the popular articles, you know,
00:36:06.440 | about quantum computing go off the rails is that they say,
00:36:09.720 | you know, they sort of say what I just said,
00:36:12.200 | and then they say, oh, so the way a quantum computer works
00:36:14.920 | is just by trying every possible answer in parallel.
00:36:18.200 | So, you know, that sounds too good to be true,
00:36:21.320 | and unfortunately, it kind of is too good to be true.
00:36:24.960 | The problem is I could make a superposition
00:36:28.280 | over every possible answer to my problem,
00:36:31.280 | you know, even if there were two to the 1,000 of them,
00:36:34.000 | right, I can easily do that.
00:36:36.080 | The trouble is for a computer to be useful,
00:36:38.520 | you've got, at some point, you've got to look at it
00:36:40.640 | and see an output, right, and if I just measure
00:36:43.760 | a superposition over every possible answer,
00:36:47.080 | then the rules of quantum mechanics tell me
00:36:49.000 | that all I'll see will be a random answer.
00:36:51.720 | You know, if I just wanted a random answer,
00:36:53.360 | well, I could have picked one myself
00:36:54.800 | with a lot less trouble, right?
00:36:56.640 | So the entire trick with quantum computing,
00:37:00.280 | with every algorithm for a quantum computer
00:37:03.000 | is that you try to choreograph a pattern
00:37:06.000 | of interference of amplitudes,
00:37:08.600 | and you try to do it so that for each wrong answer,
00:37:11.680 | some of the paths leading to that wrong answer
00:37:14.280 | have positive amplitudes,
00:37:15.960 | and others have negative amplitudes.
00:37:18.120 | So on the whole, they cancel each other out, okay,
00:37:20.760 | whereas all the paths leading to the right answer
00:37:23.600 | should reinforce each other, you know,
00:37:25.800 | should have amplitudes pointing the same direction.
00:37:28.240 | - So the design of algorithms in the space
00:37:30.800 | is the choreography of the interferences.
00:37:33.240 | - Precisely, that's precisely what it is.
00:37:35.280 | - Can we take a brief step back?
00:37:36.800 | And you mentioned information.
00:37:39.920 | - Yes.
00:37:40.760 | - So in which part of this beautiful picture
00:37:43.320 | that you've painted is information contained?
00:37:46.760 | - Oh, well, information is at the core of everything
00:37:49.640 | that we've been talking about, right?
00:37:51.120 | I mean, the bit is, you know,
00:37:53.080 | the basic unit of information,
00:37:55.400 | since, you know, Claude Shannon's paper in 1948,
00:37:59.080 | you know, and you know, of course,
00:38:00.240 | people had the concept even before that,
00:38:02.320 | you know, he popularized the name, right?
00:38:05.280 | But I mean--
00:38:06.120 | - But a bit is zero or one, so that's the basic element.
00:38:09.080 | - That's right, and what we would say
00:38:10.480 | is that the basic unit of quantum information is the qubit,
00:38:14.640 | is, you know, the object, any object
00:38:17.120 | that can be maintained in a,
00:38:19.840 | manipulated in a superposition of zero and one states.
00:38:24.120 | Now, you know, sometimes people ask,
00:38:26.120 | well, but what is a qubit physically, right?
00:38:29.120 | And there are all these different, you know,
00:38:32.360 | proposals that are being pursued in parallel
00:38:34.800 | for how you implement qubits.
00:38:37.000 | There is, you know, superconducting quantum computing
00:38:39.760 | that was in the news recently
00:38:41.520 | because of Google's quantum supremacy experiment, right?
00:38:45.040 | Where you would have some little coils
00:38:49.560 | where a current can flow through them
00:38:52.320 | in two different energy states,
00:38:54.400 | one representing a zero, another representing a one,
00:38:57.640 | and if you cool these coils to just slightly above
00:39:00.960 | absolute zero, like a hundredth of a degree,
00:39:03.960 | then they superconduct, and then the current
00:39:06.840 | can actually be in a superposition
00:39:08.400 | of the two different states.
00:39:09.840 | So that's one kind of qubit.
00:39:12.400 | Another kind would be, you know,
00:39:14.560 | just an individual atomic nucleus, right?
00:39:17.800 | It has a spin, it could be spinning clockwise,
00:39:21.120 | it could be spinning counterclockwise,
00:39:23.240 | or it could be in a superposition of the two spin states.
00:39:26.080 | That is another qubit.
00:39:27.640 | But see, just like in the classical world, right,
00:39:30.320 | you could be a virtuoso programmer
00:39:32.920 | without having any idea of what a transistor is, right,
00:39:36.520 | or how the bits are physically represented
00:39:39.120 | inside the machine,
00:39:40.480 | even that the machine uses electricity, right?
00:39:43.360 | You just care about the logic.
00:39:45.120 | It's sort of the same with quantum computing, right?
00:39:47.360 | Qubits could be realized
00:39:49.040 | by many, many different quantum systems,
00:39:51.440 | and yet all of those systems will lead to the same logic,
00:39:54.580 | you know, the logic of qubits,
00:39:57.840 | and how you measure them,
00:39:59.720 | how you change them over time.
00:40:01.560 | And so, you know, the subject of how qubits behave
00:40:05.720 | and what you can do with qubits,
00:40:07.560 | that is quantum information.
00:40:09.320 | - So just to linger on that.
00:40:11.040 | - Sure.
00:40:11.880 | - So the physical design implementation of a qubit
00:40:14.640 | does not interfere with that next level of abstraction
00:40:20.600 | that you can program over it.
00:40:22.560 | So it truly is, the idea of it is,
00:40:26.640 | okay.
00:40:27.480 | - Well, to be honest with you,
00:40:28.880 | today they do interfere with each other.
00:40:30.880 | That's because all the quantum computers we can build today
00:40:33.920 | are very noisy, right?
00:40:35.520 | And so sort of the, you know,
00:40:37.960 | the qubits are very far from perfect.
00:40:41.080 | And so the lower level sort of does affect the higher levels
00:40:44.120 | and we sort of have to think about all of them at once.
00:40:46.680 | Okay, but eventually where we hope to get
00:40:49.360 | is to what are called error-corrected quantum computers,
00:40:52.680 | where the qubits really do behave
00:40:54.720 | like perfect abstract qubits for as long as we want them to.
00:40:58.960 | And in that future, you know,
00:41:01.720 | a future that we can already sort of prove theorems about
00:41:05.120 | or think about today, but in that future,
00:41:08.480 | the logic of it really does become decoupled
00:41:11.320 | from the hardware.
00:41:12.160 | - So if noise is currently like the biggest problem
00:41:16.360 | for quantum computing,
00:41:18.360 | and then the dream is error-correcting quantum computers,
00:41:23.200 | can you just maybe describe what does it mean
00:41:26.760 | for there to be noise in the system?
00:41:28.880 | - Absolutely.
00:41:29.840 | So yeah, so the problem is even a little more specific
00:41:32.680 | than noise.
00:41:33.520 | So the fundamental problem,
00:41:35.400 | if you're trying to actually build a quantum computer,
00:41:38.480 | you know, of any appreciable size,
00:41:41.320 | is something called decoherence.
00:41:43.840 | Okay, and this was recognized from the very beginning,
00:41:46.400 | you know, when people first started thinking about this
00:41:48.600 | in the 1990s.
00:41:50.100 | Now, what decoherence means is sort of
00:41:53.160 | the unwanted interaction between, you know, your qubits,
00:41:57.000 | you know, the state of your quantum computer
00:41:59.320 | and the external environment.
00:42:01.240 | Okay, and why is that such a problem?
00:42:03.280 | Well, I talked before about how, you know,
00:42:05.360 | when you measure a quantum system,
00:42:07.840 | so let's say if I measure a qubit
00:42:10.080 | that's in a superposition of zero and one states
00:42:12.320 | to ask it, you know, are you zero or are you one?
00:42:14.860 | Well, now I force it to make up its mind, right?
00:42:17.240 | And now probabilistically,
00:42:19.040 | it chooses one or the other.
00:42:21.000 | And now, you know, it's no longer a superposition,
00:42:23.480 | there's no longer amplitudes,
00:42:25.200 | there's just, there's some probability that I get a zero
00:42:27.680 | and there's some that I get a one.
00:42:29.380 | And now, the trouble is that it doesn't have to be me
00:42:35.320 | who's looking, okay?
00:42:36.440 | Or in fact, it doesn't have to be any conscious entity.
00:42:39.140 | Any kind of interaction with the external world
00:42:44.340 | that leaks out the information
00:42:46.720 | about whether this qubit was a zero or a one,
00:42:50.040 | sort of that causes the zeroness or the oneness
00:42:53.440 | of the qubit to be recorded in, you know,
00:42:56.340 | the radiation in the room, in the molecules of the air,
00:43:00.560 | in the wires that are connected to my device, any of that.
00:43:04.900 | As soon as the information leaks out,
00:43:08.120 | it is as if that qubit has been measured, okay?
00:43:11.120 | It is, you know, the state has now collapsed.
00:43:15.240 | You know, another way to say it is that it's become
00:43:17.120 | entangled with its environment, okay?
00:43:19.480 | But, you know, from the perspective of someone
00:43:21.960 | who's just looking at this qubit,
00:43:23.600 | it is as though it has lost its quantum state.
00:43:26.880 | And so, what this means is that if I want to do
00:43:29.840 | a quantum computation, I have to keep the qubits
00:43:33.680 | sort of fanatically well isolated from their environment.
00:43:37.600 | But then at the same time, they can't be perfectly isolated
00:43:40.480 | because I need to tell them what to do.
00:43:42.680 | I need to make them interact with each other, for one thing,
00:43:45.960 | and not only that, but in a precisely choreographed way.
00:43:49.880 | Okay, and, you know, that is such a staggering problem,
00:43:53.080 | right, how do I isolate these qubits from the whole universe
00:43:56.480 | but then also tell them exactly what to do?
00:43:58.920 | I mean, you know, there were distinguished physicists
00:44:01.580 | and computer scientists in the '90s who said
00:44:04.760 | this is fundamentally impossible, you know?
00:44:07.200 | The laws of physics will just never let you control qubits
00:44:10.700 | to the degree of accuracy that you're talking about.
00:44:14.300 | Now, what changed the views of most of us
00:44:17.740 | was a profound discovery in the mid to late '90s,
00:44:22.340 | which was called the theory of quantum error correction
00:44:25.500 | and quantum fault tolerance, okay?
00:44:27.740 | And the upshot of that theory is that if I want to build
00:44:31.420 | a reliable quantum computer and scale it up
00:44:34.820 | to, you know, an arbitrary number of as many qubits
00:44:37.540 | as I want, you know, and doing as much on them as I want,
00:44:41.100 | I do not actually have to get the qubits perfectly isolated
00:44:45.340 | from their environment.
00:44:46.220 | It is enough to get them really, really,
00:44:48.060 | really well isolated, okay?
00:44:50.140 | And even if every qubit is sort of leaking, you know,
00:44:55.100 | its state into the environment at some rate,
00:44:57.960 | as long as that rate is low enough, okay,
00:45:00.580 | I can sort of encode the information that I care about
00:45:05.060 | in very clever ways across the collective states
00:45:08.460 | of multiple qubits, okay, in such a way that even if,
00:45:11.980 | you know, a small percentage of my qubits leak,
00:45:15.140 | well, I'm constantly monitoring them to see
00:45:17.360 | if that leak happened.
00:45:18.500 | I can detect it and I can correct it.
00:45:21.060 | I can recover the information I care about
00:45:23.420 | from the remaining qubits, okay?
00:45:25.500 | And so, you know, you can build a reliable quantum computer
00:45:30.340 | even out of unreliable parts, right?
00:45:32.820 | Now, in some sense, you know, that discovery
00:45:36.820 | is what set the engineering agenda
00:45:39.180 | for quantum computing research
00:45:41.100 | from the 1990s until the present, okay?
00:45:43.740 | The goal has been, you know, engineer qubits
00:45:46.740 | that are not perfectly reliable, but reliable enough
00:45:50.700 | that you can then use these error correcting codes
00:45:53.900 | to have them simulate qubits that are even more reliable
00:45:57.740 | than they are, right? - Got it.
00:45:59.100 | - The error correction becomes a net win
00:46:01.140 | rather than a net loss, right?
00:46:02.820 | And then once you reach that sort of crossover point,
00:46:05.940 | then, you know, your simulated qubits
00:46:08.340 | could in turn simulate qubits that are even more reliable
00:46:11.640 | and so on until you've just, you know,
00:46:13.740 | effectively you have arbitrarily reliable qubits.
00:46:17.140 | So long story short, we are not at that break-even point yet.
00:46:20.780 | We're a hell of a lot closer than we were
00:46:22.700 | when people started doing this in the '90s,
00:46:24.820 | like orders of magnitude closer.
00:46:26.420 | - But the key ingredient there is the more qubits,
00:46:29.140 | the better because--
00:46:30.700 | - Ah, well, the more qubits,
00:46:32.220 | the larger the computation you can do, right?
00:46:35.260 | I mean, qubits are what constitute the memory
00:46:38.980 | of your quantum computer, right?
00:46:40.500 | - But also for the, sorry, for the error correcting mechanism.
00:46:43.260 | - Ah, yes.
00:46:44.180 | So the way I would say it is that error correction
00:46:47.400 | imposes an overhead in the number of qubits.
00:46:50.420 | And that is actually one of the biggest practical problems
00:46:53.520 | with building a scalable quantum computer.
00:46:55.700 | If you look at the error correcting codes,
00:46:58.180 | at least the ones that we know about today,
00:47:00.580 | and you look at what would it take
00:47:02.740 | to actually use a quantum computer
00:47:04.620 | to hack your credit card number,
00:47:09.300 | which is maybe the most famous application
00:47:12.140 | people talk about, right?
00:47:13.380 | Let's say to factor huge numbers
00:47:15.380 | and thereby break the RSA cryptosystem.
00:47:18.060 | Well, what that would take would be thousands of,
00:47:21.620 | several thousand logical qubits.
00:47:24.220 | But now with the known error correcting codes,
00:47:26.620 | each of those logical qubits would need to be encoded itself
00:47:30.140 | using thousands of physical qubits.
00:47:32.440 | So at that point, you're talking about
00:47:33.940 | millions of physical qubits.
00:47:35.980 | And in some sense, that is the reason why
00:47:38.140 | quantum computers are not breaking cryptography already.
00:47:40.980 | It's because of these immense overheads involved.
00:47:43.940 | - So that overhead is additive or multiplicative?
00:47:46.460 | - Well, it's multiplicative.
00:47:47.580 | I mean, it's like you take the number of logical qubits
00:47:51.960 | that you need in your abstract quantum circuit,
00:47:54.540 | you multiply it by a thousand or so.
00:47:56.860 | So, you know, there's a lot of work on, you know,
00:47:58.980 | inventing better, trying to invent better
00:48:01.060 | error correcting codes.
00:48:02.500 | Okay, that is the situation right now.
00:48:04.300 | In the meantime, we are now in what the physicist
00:48:08.660 | John Preskill called the noisy intermediate scale
00:48:11.780 | quantum or NISQ era.
00:48:13.660 | And this is the era, you can think of it
00:48:15.540 | as sort of like the vacuum, you know,
00:48:17.160 | we're now entering the very early vacuum tube era
00:48:20.420 | of quantum computers.
00:48:21.880 | The quantum computer analog of the transistor
00:48:24.780 | has not been invented yet, right?
00:48:26.600 | That would be like true error correction, right?
00:48:29.220 | Where, you know, we are not, or something else
00:48:31.640 | that would achieve the same effect, right?
00:48:33.580 | We are not there yet.
00:48:35.540 | And, but where we are now, let's say as of a few months ago,
00:48:40.300 | you know, as of Google's announcement of quantum supremacy,
00:48:43.740 | you know, we are now finally at the point
00:48:45.860 | where even with a non-error corrected quantum computer
00:48:49.400 | with, you know, these noisy devices,
00:48:51.420 | we can do something that is hard for classical computers
00:48:55.180 | to simulate, okay?
00:48:56.580 | So we can eke out some advantage.
00:48:58.740 | Now, will we in this noisy era be able to do something
00:49:02.320 | beyond what a classical computer can do
00:49:04.340 | that is also useful to someone?
00:49:06.540 | That we still don't know.
00:49:07.820 | People are going to be racing over the next decade
00:49:10.620 | to try to do that by people, I mean, Google, IBM,
00:49:14.700 | you know, a bunch of startup companies, you know--
00:49:17.660 | - And research labs.
00:49:18.660 | - Yeah, and research labs and governments and yeah.
00:49:22.660 | - You just mentioned a million things.
00:49:24.140 | Well, I'll backtrack for a second.
00:49:25.740 | - Yeah, sure, sure.
00:49:27.260 | - So we're in these vacuum tube days.
00:49:29.700 | - Yeah, just entering though.
00:49:31.180 | - And just entering, wow, okay.
00:49:33.260 | So how do we escape the vacuum?
00:49:36.500 | So how do we get to where we are now with the CPU?
00:49:41.500 | Is this a fundamental engineering challenge?
00:49:44.820 | Is there breakthroughs on the physics side
00:49:49.260 | that are needed on the computer science side?
00:49:53.180 | What's, is it a financial issue where a much larger,
00:49:57.740 | just sheer investment and excitement is needed?
00:50:01.180 | - So, you know, those are excellent questions.
00:50:03.820 | My guess-- - With no answers.
00:50:05.180 | - Well, no, no, my guess would be all of the above.
00:50:09.420 | I mean, my guess, you know, I mean, you know,
00:50:12.380 | you could say fundamentally it is an engineering issue,
00:50:14.960 | right, the theory has been in place since the '90s,
00:50:18.140 | you know, at least, you know, this is what,
00:50:21.220 | you know, error correction would look like,
00:50:23.500 | you know, we do not have the hardware that is at that level,
00:50:26.900 | but at the same time, you know, so you could just,
00:50:30.460 | you know, try to power through, you know,
00:50:32.700 | maybe even like, you know, if someone spent a trillion
00:50:36.060 | dollars on some quantum computing Manhattan project,
00:50:39.260 | right, then conceivably they could just, you know,
00:50:43.100 | build an error-corrected quantum computer
00:50:46.580 | as it was envisioned back in the '90s, right?
00:50:49.700 | I think the more plausible thing to happen
00:50:52.540 | is that there will be further theoretical breakthroughs,
00:50:55.580 | and there will be further insights that will cut down
00:50:58.500 | the cost of doing this.
00:51:00.100 | - So let's take a brief step to the philosophical.
00:51:03.100 | I just recently talked to Jim Keller,
00:51:05.520 | who's sort of like the famed architect
00:51:09.780 | in the microprocessor world, and he's been told
00:51:14.500 | for decades every year that the Moore's Law
00:51:18.180 | is going to die this year, and he tries to argue
00:51:22.220 | that the Moore's Law is still alive and well,
00:51:25.780 | and it'll be alive for quite a long time to come.
00:51:28.460 | - How long, how long did he say?
00:51:30.140 | - Well, the main point is it's still alive,
00:51:33.860 | but he thinks there's still a thousand X improvement
00:51:38.140 | just on shrinking the transition, that's possible.
00:51:41.060 | Whatever, the point is that the exponential growth we see
00:51:45.540 | is actually a huge number of these S curves,
00:51:49.820 | just constant breakthroughs.
00:51:51.780 | At the philosophical level, why do you think we,
00:51:56.380 | as a descendants of apes, were able to just keep coming up
00:52:00.660 | with these new breakthroughs on the CPU side?
00:52:03.620 | Is this something unique to this particular endeavor,
00:52:07.140 | or will it be possible to replicate
00:52:09.820 | in the quantum computer space?
00:52:11.820 | - Okay, all right, there was a lot there,
00:52:15.300 | but to break off something, I mean,
00:52:18.380 | I think we are in an extremely special period
00:52:21.060 | of human history, right?
00:52:22.620 | I mean, it is, you could say, obviously special,
00:52:26.220 | you know, in many ways, right?
00:52:28.380 | There are, you know, way more people alive
00:52:31.980 | than there have been, and, you know,
00:52:34.900 | the whole future of the planet is in question
00:52:41.820 | in a way that it hasn't been, you know,
00:52:44.620 | for the rest of human history, but, you know,
00:52:48.100 | in particular, you know, we are in the era
00:52:51.220 | where, you know, we finally figured out
00:52:54.060 | how to build, you know, universal machines,
00:52:57.860 | you could say, you know, the things that we call computers,
00:53:00.420 | you know, machines that you program
00:53:02.460 | to simulate the behavior of whatever machine you want,
00:53:07.100 | and, you know, and once you've sort of crossed
00:53:12.100 | this threshold of universality, you know,
00:53:15.300 | you've built, you could say, you know,
00:53:16.780 | Turing, you've instantiated Turing machines
00:53:19.620 | in the physical world, well, then the main questions
00:53:22.380 | are ones of numbers.
00:53:24.100 | They are, you know, ones of how many,
00:53:26.540 | how much memory can you access?
00:53:29.620 | How fast does it run?
00:53:31.260 | How many parallel processors?
00:53:33.260 | You know, at least until quantum computing.
00:53:34.940 | Quantum computing is the one thing that changes
00:53:37.100 | what I just said, right?
00:53:38.700 | But, you know, as long as it's classical computing,
00:53:42.500 | then it's all questions of numbers.
00:53:44.740 | And, you know, you could say at a theoretical level,
00:53:48.860 | the computers that we have today
00:53:50.540 | are the same as the ones in the '50s.
00:53:52.820 | They're just millions of times, you know,
00:53:55.020 | faster with millions of times more memory.
00:53:57.340 | And, you know, I mean, I think there's been
00:53:59.380 | an immense economic pressure to, you know,
00:54:02.620 | get more and more transistors, you know,
00:54:04.940 | get them smaller and smaller, you know,
00:54:07.300 | add more and more cores.
00:54:09.140 | And, you know, and in some sense, like,
00:54:13.460 | a huge fraction of sort of all of the technological progress
00:54:16.980 | that there is in all of civilization
00:54:19.420 | has gotten concentrated just more narrowly
00:54:22.420 | into just those problems, right?
00:54:25.060 | And so, you know, it has been one of the biggest
00:54:28.540 | success stories in the history of technology, right?
00:54:31.500 | There's, you know, I mean, it is,
00:54:32.940 | I am as amazed by it as anyone else is, right?
00:54:36.820 | But at the same time, you know, we also know that it,
00:54:40.580 | you know, and I really do mean we know
00:54:45.540 | that it cannot continue indefinitely, okay?
00:54:48.580 | Because you will reach, you know, fundamental limits
00:54:52.340 | on, you know, how small you can possibly make a processor.
00:54:56.900 | And, you know, if you want a real proof, you know,
00:54:59.140 | that would justify my use of the word, you know,
00:55:01.460 | we know that, you know, Moore's law has to end.
00:55:04.260 | I mean, ultimately, you will reach the limits
00:55:06.420 | imposed by quantum gravity, you know?
00:55:08.900 | You know, if you were doing,
00:55:10.940 | if you tried to build a computer that operated
00:55:13.540 | at 10 to the 43 Hertz,
00:55:15.820 | so it did 10 to the 43 operations per second,
00:55:18.780 | that computer would use so much energy
00:55:20.980 | that it would simply collapse to a black hole, okay?
00:55:24.460 | So, you know, that, you know, in reality,
00:55:27.420 | we're going to reach the limits long before that.
00:55:29.980 | But, you know, that is a sufficient proof.
00:55:32.060 | - That there's a limit.
00:55:33.460 | - Yes, yes.
00:55:34.700 | - But it would be interesting to try to understand
00:55:38.380 | the mechanism, the economic pressure that you said,
00:55:40.940 | just like the Cold War was a pressure on getting us,
00:55:45.060 | getting us, 'cause I'm both,
00:55:47.660 | my us is both the Soviet Union and the United States,
00:55:51.100 | but getting us, the two countries,
00:55:53.660 | to get, to hurry up to get to space, to the moon,
00:55:56.700 | there seems to be that same kind of economic pressure
00:55:59.320 | that somehow created a chain of engineering breakthroughs
00:56:03.780 | that resulted in the Moore's law.
00:56:06.100 | - Yeah. - It'd be nice
00:56:06.940 | to replicate.
00:56:07.760 | - Yeah, well, I mean, some people are sort of,
00:56:10.780 | get depressed about the fact that technological progress,
00:56:14.780 | you know, may seem to have slowed down
00:56:16.860 | in many, many realms outside of computing, right?
00:56:20.260 | There was this whole thing of, you know,
00:56:21.460 | we wanted flying cars and we only got Twitter instead,
00:56:24.620 | right? (laughs)
00:56:25.460 | - Yeah, good old Peter Thiel, yeah.
00:56:27.620 | - Yeah, yeah, yeah, right, right, right.
00:56:29.020 | So, then jumping to another really interesting topic
00:56:32.220 | that you mentioned, so Google announced
00:56:36.540 | with their work in the paper in Nature
00:56:39.360 | with quantum supremacy.
00:56:40.900 | - Yes. - Can you describe,
00:56:42.520 | again, back to the basic, what is,
00:56:45.200 | perhaps not so basic, what is quantum supremacy?
00:56:48.080 | - Absolutely, so quantum supremacy is a term
00:56:52.180 | that was coined by, again, by John Preskill in 2012.
00:56:57.680 | Not everyone likes the name, you know,
00:57:00.000 | but it sort of stuck, you know,
00:57:04.400 | we don't, we sort of haven't found a better alternative.
00:57:08.360 | - It's technically quantum computational supremacy.
00:57:10.600 | - Yeah, yeah, supremacy, that's right, that's right.
00:57:12.720 | But the basic idea is actually one that goes
00:57:15.520 | all the way back to the beginnings of quantum computing
00:57:18.640 | when Richard Feynman and David Deutch, people like that,
00:57:21.600 | were talking about it in the early '80s.
00:57:23.840 | And quantum supremacy just refers to sort of the point
00:57:28.720 | in history when you can first use a quantum computer
00:57:32.540 | to do some well-defined task much faster
00:57:36.560 | than any known algorithm running on any
00:57:39.360 | of the classical computers that are available, okay?
00:57:42.320 | So, you know, notice that I did not say a useful task, okay?
00:57:46.360 | You know, it could be something completely artificial,
00:57:49.120 | but it's important that the task be well-defined.
00:57:51.920 | So in other words, you know, there is,
00:57:53.680 | it is something that has right and wrong answers,
00:57:56.600 | you know, that are knowable independently of this device,
00:58:00.320 | right, and we can then, you know, run the device,
00:58:02.520 | see if it gets the right answer or not.
00:58:04.480 | - Can you clarify a small point?
00:58:06.080 | You said much faster than a classical implementation.
00:58:09.560 | What about, sort of, what about the space
00:58:12.840 | with where the class, there's no, there's not,
00:58:15.200 | it doesn't even exist a classical algorithm to--
00:58:17.920 | - So maybe I should clarify, everything
00:58:21.320 | that a quantum computer can do,
00:58:23.040 | a classical computer can also eventually do, okay?
00:58:26.720 | And the reason why we know that is
00:58:29.040 | that a classical computer could always, you know,
00:58:32.360 | if it had no limits of time and memory,
00:58:35.600 | it could always just store the entire quantum state,
00:58:39.300 | you know, of your, you know, of the quantum,
00:58:41.320 | right, store a list of all the amplitudes, you know,
00:58:45.280 | in the state of the quantum computer,
00:58:47.320 | and then just, you know, do some linear algebra
00:58:50.160 | to just update that state, right?
00:58:52.240 | And so, so anything that quantum computers can do
00:58:55.500 | can also be done by classical computers,
00:58:58.380 | albeit exponentially slower in some cases.
00:59:00.720 | - So quantum computers don't go to some magical place
00:59:03.840 | outside of Alan Turing's definition of computation.
00:59:06.760 | - Precisely.
00:59:07.600 | They do not solve the halting problem.
00:59:10.040 | They cannot solve anything that is uncomputable
00:59:12.800 | in Alan Turing's sense.
00:59:14.460 | What they, what we think they do change
00:59:16.760 | is what is efficiently computable, okay?
00:59:19.360 | And, you know, since the 1960s, you know,
00:59:22.440 | the word efficiently, you know,
00:59:24.200 | as well as been a central word in computer science,
00:59:27.040 | but it's sort of a code word for something technical,
00:59:30.120 | which is basically with polynomial scaling, you know,
00:59:33.920 | that as you get to larger and larger inputs,
00:59:36.880 | you would like an algorithm that uses an amount of time
00:59:39.840 | that scales only like the size of the input
00:59:42.440 | raised to some power, and not exponentially
00:59:45.320 | with the size of the input, right?
00:59:47.400 | - Yeah, so I do hope we get to talk again,
00:59:49.880 | because one of the many topics
00:59:52.720 | that there's probably several hours worth of conversation on
00:59:56.000 | is complexity, which we probably won't even get a chance
00:59:58.400 | to touch today, but you briefly mentioned it.
01:00:02.720 | But let's maybe try to continue.
01:00:05.360 | So you said the definition of quantum supremacy
01:00:08.680 | is basically achieving a place where much faster
01:00:13.600 | on a formal, that quantum computers much faster
01:00:16.560 | on a formal, well-defined problem that is or isn't useful.
01:00:21.200 | - Yeah, yeah, yeah, right, right.
01:00:22.400 | And I would say that we really want three things, right?
01:00:25.360 | We want, first of all, the quantum computer
01:00:28.040 | to be much faster, just in the literal sense
01:00:30.640 | of like number of seconds, you know,
01:00:32.800 | at just solving this, you know, well-defined, you know,
01:00:36.040 | problem.
01:00:36.960 | Secondly, we want it to be sort of, you know,
01:00:40.640 | for a problem where we really believe
01:00:42.880 | that a quantum computer has better scaling behavior, right?
01:00:46.080 | So it's not just an incidental, you know,
01:00:48.800 | matter of hardware, but it's that, you know,
01:00:51.240 | as you went to larger and larger inputs, you know,
01:00:54.320 | the classical scaling would be exponential
01:00:57.360 | and the scaling for the quantum algorithm
01:00:59.840 | would only be polynomial.
01:01:01.680 | And then thirdly, we want the first thing,
01:01:04.200 | the actual observed speed up to only be explainable
01:01:08.160 | in terms of the scaling behavior, right?
01:01:10.720 | So, you know, I want, you know, a real world,
01:01:13.960 | you know, a real problem to get solved,
01:01:16.640 | let's say by a quantum computer with 50 qubits or so,
01:01:20.640 | and for no one to be able to explain that in any way
01:01:23.680 | other than, well, you know, to,
01:01:26.440 | this computer involved a quantum state
01:01:30.440 | with two to the 50th power amplitudes,
01:01:33.280 | and, you know, a classical simulation,
01:01:35.320 | at least any that we know today,
01:01:37.180 | would require keeping track of two to the 50th numbers,
01:01:40.560 | and this is the reason why it was faster.
01:01:42.560 | - So the intuition is that then if you demonstrate
01:01:45.200 | on 50 qubits, then once you get to 100 qubits,
01:01:48.480 | then it'll be even much more faster.
01:01:50.880 | - Precisely, precisely.
01:01:52.560 | Yeah, and, you know, and quantum supremacy
01:01:55.120 | does not require error correction, right?
01:01:57.320 | We don't, you know, we don't have,
01:01:58.640 | you could say true scalability yet,
01:02:00.800 | or true, you know, error correction yet,
01:02:04.720 | but you could say quantum supremacy
01:02:06.680 | is already enough by itself to refute the skeptics
01:02:11.000 | who said a quantum computer will never outperform
01:02:13.360 | a classical computer for anything.
01:02:15.320 | - But one, how do you demonstrate quantum supremacy,
01:02:20.320 | and two, what's up with these news articles
01:02:23.960 | I'm reading that Google did so?
01:02:25.960 | - Yeah, all right, well--
01:02:26.800 | - What did they actually do?
01:02:27.880 | - Great, great questions, 'cause now you get into,
01:02:31.200 | actually, you know, a lot of the work that I've,
01:02:34.040 | you know, I and my students have been doing
01:02:35.840 | for the last decade, which was precisely about
01:02:39.960 | how do you demonstrate quantum supremacy
01:02:42.400 | using technologies that, you know,
01:02:44.400 | we thought would be available in the near future?
01:02:47.260 | And so one of the main things that we realized
01:02:52.080 | around 2011, and this was me and my student,
01:02:56.720 | Alex Arkhipov at MIT at the time,
01:02:59.960 | and independently of some others,
01:03:03.280 | including Bremner, Josa, and Shepard, okay?
01:03:06.320 | And the realization that we came to
01:03:10.320 | was that if you just want to prove
01:03:13.120 | that a quantum computer is faster, you know,
01:03:15.240 | and not do something useful with it,
01:03:17.280 | then there are huge advantages
01:03:19.400 | to sort of switching your attention
01:03:21.520 | from problems like factoring numbers
01:03:24.080 | that have a single right answer
01:03:26.160 | to what we call sampling problems.
01:03:28.720 | So these are problems where the goal
01:03:31.040 | is just to output a sample
01:03:33.120 | from some probability distribution,
01:03:35.540 | let's say over strings of 50 bits, right?
01:03:38.200 | So there are, you know, many, many,
01:03:40.160 | many possible valid outputs.
01:03:42.240 | You know, your computer will probably
01:03:43.720 | never even produce the same output twice,
01:03:46.440 | you know, if it's running as,
01:03:48.360 | even, you know, assuming it's running perfectly, okay?
01:03:52.960 | But the key is that some outputs
01:03:55.280 | are supposed to be likelier than other ones.
01:03:57.800 | So-- - So sorry, to clarify,
01:03:59.820 | is there a set of outputs that are valid
01:04:02.680 | and a set that are not?
01:04:03.880 | Or is it more that the distribution
01:04:08.060 | of a particular kind of output is more,
01:04:11.300 | is there's a specific distribution
01:04:13.420 | of a particular kind of output?
01:04:14.260 | - Yeah, there's a specific distribution
01:04:16.740 | that you're trying to hit, right?
01:04:18.140 | Or, you know, that you're trying to sample from.
01:04:20.140 | Now, there are a lot of questions about this.
01:04:22.660 | You know, how do you do that, right?
01:04:24.660 | Now, how you do it, you know,
01:04:27.820 | it turns out that with a quantum computer,
01:04:30.340 | even with the noisy quantum computers
01:04:32.380 | that we have now, that we have today,
01:04:34.960 | what you can do is basically just apply
01:04:37.080 | a randomly chosen sequence of operations, right?
01:04:40.400 | So we, you know, we, and sometimes, you know,
01:04:42.520 | that part is almost trivial, right?
01:04:44.740 | We just sort of get the qubits to interact
01:04:47.440 | in some random way, although a sort of
01:04:49.640 | precisely specified random way,
01:04:51.760 | so we can repeat the exact same
01:04:54.200 | random sequence of interactions again
01:04:56.600 | and get another sample from that same distribution.
01:04:59.680 | And what this does is it basically,
01:05:02.020 | well, it creates a lot of garbage,
01:05:04.280 | but, you know, very specific garbage, right?
01:05:06.720 | So, you know, of all of the,
01:05:09.280 | so if we're going to talk about Google's device,
01:05:11.520 | there were 53 qubits there, okay?
01:05:14.200 | And so there were two to the 53 power possible outputs.
01:05:18.160 | Now, for some of those outputs, you know,
01:05:20.480 | there was a little bit more destructive interference
01:05:24.380 | in their amplitude, okay?
01:05:25.800 | So their amplitudes were a little bit smaller.
01:05:28.180 | And for others, there was a little more
01:05:29.600 | constructive interference.
01:05:31.360 | You know, the amplitudes were a little bit
01:05:33.000 | more aligned with each other, you know,
01:05:35.240 | and so those that were a little bit likelier, okay?
01:05:38.980 | All of the outputs are exponentially unlikely,
01:05:42.320 | but some are, let's say, two times or three times,
01:05:45.520 | you know, unlikelier than others, okay?
01:05:47.840 | And so you can define, you know,
01:05:50.880 | this sequence of operations that gives rise
01:05:53.680 | to this probability distribution, okay?
01:05:56.040 | Now, the next question would be, well, how do you,
01:05:59.560 | you know, even if you're sampling from it,
01:06:01.160 | how do you verify that?
01:06:02.400 | - Right, exactly. - How do you know?
01:06:04.200 | And so my students and I, and also the people at Google
01:06:09.200 | were doing the experiment, came up with statistical tests
01:06:13.160 | that you can apply to the outputs in order to
01:06:17.000 | try to verify, you know, what is, you know,
01:06:21.520 | that at least that some hard problem is being solved.
01:06:25.920 | The test that Google ended up using
01:06:28.760 | was something that they called
01:06:29.960 | the linear cross-entropy benchmark, okay?
01:06:32.960 | And it's basically, you know, so the drawback of this test
01:06:36.440 | is that it requires, like, it requires you
01:06:39.400 | to do a two to the 53 time calculation
01:06:43.200 | with your classical computer, okay?
01:06:45.040 | So it's very expensive to do the test
01:06:47.880 | on a classical computer. - Yeah.
01:06:49.380 | - The good news is-- - How big of a number
01:06:50.880 | is two to the 53? - It's about nine quadrillion.
01:06:53.760 | - Okay. - That doesn't help.
01:06:55.260 | - Well, you know, it's, you want it
01:06:57.080 | in like scientific notation?
01:06:58.480 | - No, no, no, what I mean is--
01:07:00.400 | - It is just-- - Is it impossible
01:07:02.160 | to run on a-- - Yeah, so we will come
01:07:04.400 | back to that, it is just barely possible to run,
01:07:07.620 | we think, on the largest supercomputer
01:07:09.480 | that currently exists on Earth,
01:07:11.200 | which is called Summit at Oak Ridge National Lab, okay?
01:07:14.680 | - Great, this is exciting.
01:07:17.000 | - That's the short answer.
01:07:18.360 | So ironically, for this type of experiment,
01:07:22.080 | we don't want 100 qubits, okay?
01:07:24.480 | Because with 100 qubits, even if it works,
01:07:27.120 | we don't know how to verify the results, okay?
01:07:29.720 | So we want a number of qubits that is enough
01:07:32.840 | that the biggest classical computers on Earth
01:07:36.480 | will have to sweat, and will just barely be able
01:07:40.640 | to keep up with the quantum computer,
01:07:43.240 | using much more time, but they will still be able
01:07:45.920 | to do it in order that we can verify the result.
01:07:48.400 | - Which is where the 53 comes from,
01:07:50.280 | for the number of qubits? - Basically, well,
01:07:51.360 | I mean, that's also, that's sort of,
01:07:55.640 | I mean, that's sort of where they are now,
01:07:59.000 | in terms of scaling, and then soon,
01:08:01.880 | that point will be passed, and then when you get
01:08:05.040 | to larger numbers of qubits, then these types
01:08:08.920 | of sampling experiments will no longer be so interesting,
01:08:12.280 | because we won't even be able to verify the results,
01:08:15.060 | and we'll have to switch to other types of computation.
01:08:17.880 | So with the sampling thing, so the test that Google applied,
01:08:22.880 | this linear cross-entropy benchmark,
01:08:24.840 | was basically just take the samples that were generated,
01:08:28.520 | which are a very small subset of all the possible samples
01:08:32.360 | that there are, but for those, you calculate,
01:08:35.200 | with your classical computer, the probabilities
01:08:37.800 | that they should have been output,
01:08:39.680 | and you see, are those probabilities larger than the mean?
01:08:43.440 | So is the quantum computer biased toward outputting
01:08:46.680 | the strings that you want it to be biased toward?
01:08:50.440 | Okay, and then, finally, we come to a very crucial question,
01:08:54.400 | which is supposing that it does that,
01:08:56.360 | well, how do we know that a classical computer
01:08:58.560 | could not have quickly done the same thing?
01:09:01.400 | How do we know that this couldn't have been spoofed
01:09:03.800 | by a classical computer?
01:09:05.640 | And so, well, the first answer is we don't know, for sure,
01:09:09.960 | because this takes us into questions of complexity theory,
01:09:13.620 | I mean, questions of the magnitude
01:09:17.880 | of the P versus NP question, and things like that, right?
01:09:20.760 | We don't know how to rule out definitively
01:09:23.640 | that there could be fast classical algorithms
01:09:26.680 | for even simulating quantum mechanics,
01:09:29.080 | and for simulating experiments like these,
01:09:32.460 | but we can give some evidence against that possibility,
01:09:36.280 | and that was sort of the main thrust of a lot of the work
01:09:40.280 | that my colleagues and I did over the last decade,
01:09:43.840 | which is then sort of in around 2015 or so,
01:09:46.880 | what led to Google deciding to do this experiment.
01:09:50.040 | - So is the kind of evidence you, first of all,
01:09:53.200 | the hard P equals NP problem that you mentioned,
01:09:55.960 | and the kind of evidence that you were looking at,
01:10:00.920 | is that something you come to on a sheet of paper,
01:10:03.880 | or is this something, are these empirical experiments?
01:10:07.480 | - It's math, for the most part.
01:10:09.640 | I mean, it's also, we have a bunch of methods
01:10:14.640 | that are known for simulating quantum circuits,
01:10:20.160 | or quantum computations with classical computers,
01:10:23.640 | and so we have to try them all out,
01:10:25.420 | and make sure that they don't work,
01:10:28.160 | make sure that they have exponential scaling
01:10:30.360 | on these problems, and not just theoretically,
01:10:34.280 | but with the actual range of parameters
01:10:36.460 | that are actually arising in Google's experiment.
01:10:40.420 | Okay, so there is an empirical component to it, right?
01:10:43.480 | But now, on the theoretical side,
01:10:47.760 | basically what we know how to do
01:10:49.840 | in theoretical computer science,
01:10:51.760 | and computational complexity,
01:10:53.640 | is we don't know how to prove
01:10:56.240 | that most of the problems we care about are hard,
01:10:58.960 | but we know how to pass the blame to someone else.
01:11:01.920 | Okay, we know how to say, well, look,
01:11:04.120 | I can't prove that this problem is hard,
01:11:06.480 | but if it is easy, then all these other things
01:11:09.040 | that you probably were much more confident,
01:11:13.200 | or were hard, then those would be easy as well, okay?
01:11:16.880 | So we can give what are called reductions.
01:11:19.840 | This has been the basic strategy in NP completeness,
01:11:24.400 | right, in all of theoretical computer science,
01:11:27.580 | and cryptography since the 1970s, really.
01:11:31.120 | And so we were able to give some reduction evidence
01:11:34.320 | for the hardness of simulating these sampling experiments,
01:11:39.320 | these sampling-based quantum supremacy experiments.
01:11:43.340 | The reduction evidence is not as satisfactory
01:11:46.280 | as it should be.
01:11:47.440 | One of the biggest open problems in this area
01:11:50.040 | is to make it better.
01:11:51.560 | But we can do something.
01:11:53.680 | Certainly we can say that if there is
01:11:57.560 | a fast classical algorithm to spoof these experiments,
01:12:01.280 | then it has to be very, very unlike
01:12:03.280 | any of the algorithms that we know.
01:12:05.040 | - Which is kind of in the same kind of space of reasoning
01:12:10.320 | that people say P not equals NP.
01:12:13.280 | - Yeah, it's in the same spirit.
01:12:15.560 | - Yeah, in the same spirit.
01:12:16.840 | Okay, so Andrew Yang, a very intelligent
01:12:21.840 | and presidential candidate with a lot of interesting ideas
01:12:27.520 | in all kinds of technological fields,
01:12:29.760 | tweeted that because of quantum computing,
01:12:33.440 | no code is uncrackable.
01:12:36.180 | Is he wrong or right?
01:12:38.480 | - He was premature, let's say.
01:12:40.920 | So, well, okay, wrong.
01:12:42.840 | (both laughing)
01:12:45.160 | Look, I'm actually, I'm a fan of Andrew Yang.
01:12:49.720 | I like his ideas, I like his candidacy.
01:12:53.120 | I think that he may be ahead of his time
01:12:58.360 | with the universal basic income and so forth,
01:13:01.880 | and he may also be ahead of his time
01:13:04.000 | in that tweet that you referenced.
01:13:06.080 | So, regarding using quantum computers
01:13:09.560 | to break cryptography, so the situation is this.
01:13:13.360 | So, the famous discovery of Peter Shor,
01:13:17.600 | 26 years ago, that really started quantum computing
01:13:21.480 | as an autonomous field was that if you built
01:13:25.440 | a full scalable quantum computer,
01:13:28.280 | then you could use it to efficiently find the prime factors
01:13:32.600 | of huge numbers and calculate discrete logarithms
01:13:37.600 | and solve a few other problems
01:13:40.600 | that are very, very special in character, right?
01:13:43.040 | They're not NP-complete problems.
01:13:44.960 | We're pretty sure they're not, okay?
01:13:46.560 | But it so happens that most of the public key cryptography
01:13:51.560 | that we currently use to protect the internet
01:13:54.520 | is based on the belief that these problems are hard.
01:13:58.000 | What Shor showed is that once you get
01:14:00.080 | scalable quantum computers, then that's no longer true.
01:14:03.440 | But now, before people panic,
01:14:07.040 | there are two important points to understand here.
01:14:09.960 | Okay, the first is that quantum supremacy,
01:14:13.320 | the milestone that Google just achieved,
01:14:15.840 | is very, very far from the kind of scalable quantum computer
01:14:19.840 | that would be needed to actually
01:14:21.480 | threaten public key cryptography.
01:14:23.760 | Okay, so we touched on this earlier, right?
01:14:25.920 | But Google's device has 53 physical qubits, right?
01:14:29.920 | To threaten cryptography, you're talking,
01:14:32.800 | you know, with any of the known error correction methods,
01:14:35.160 | you're talking millions of physical qubits.
01:14:37.560 | - 'Cause error correction would be required
01:14:39.880 | to threaten cryptography. - Yes, yes, yes.
01:14:42.560 | Yes, it certainly would, right?
01:14:46.960 | And, you know, how much, you know,
01:14:50.920 | how great will the overhead be from the error correction?
01:14:53.960 | That we don't know yet.
01:14:55.320 | But with the known codes, you're talking millions
01:14:58.960 | of physical qubits and of a much higher quality
01:15:01.720 | than any that we have now.
01:15:03.000 | Okay, so, you know, I don't think that that is,
01:15:07.040 | you know, coming soon.
01:15:08.800 | Although people who have secrets that, you know,
01:15:13.120 | need to stay secret for 20 years, you know,
01:15:15.880 | are already worried about this, you know,
01:15:18.160 | for the good reason that, you know,
01:15:20.040 | we presume that intelligence agencies
01:15:22.760 | are already scooping up data, you know,
01:15:25.360 | in the hope that eventually they'll be able to decode it
01:15:28.200 | once quantum computers become available, okay?
01:15:30.880 | So this brings me to the second point I wanted to make,
01:15:35.720 | which is that there are other public key cryptosystems
01:15:39.560 | that are known that we don't know how to break
01:15:43.400 | even with quantum computers, okay?
01:15:45.640 | And so there's a whole field devoted to this now,
01:15:48.640 | which is called post-quantum cryptography, okay?
01:15:51.800 | And so there is already,
01:15:53.480 | so we have some good candidates now.
01:15:56.480 | The best known being what are called
01:15:58.560 | lattice-based cryptosystems.
01:16:00.920 | And there is already some push to try to migrate
01:16:03.760 | to these cryptosystems.
01:16:04.960 | So NIST in the US is holding a competition
01:16:09.960 | to create standards for post-quantum cryptography,
01:16:14.160 | which will be the first step in trying to get
01:16:16.600 | every web browser and every router to upgrade, you know,
01:16:21.000 | and use, you know, something like SSL
01:16:23.880 | that would be based on, you know,
01:16:26.440 | what we think is quantum secure cryptography.
01:16:29.440 | But, you know, this will be a long process,
01:16:33.560 | but, you know, it is something that people
01:16:35.320 | are already starting to do.
01:16:36.840 | And so, you know, I'm sure his algorithm
01:16:40.400 | is sort of a dramatic discovery.
01:16:43.000 | You know, it could be a big deal
01:16:44.440 | for whatever intelligence agency first gets
01:16:47.120 | a scalable quantum computer,
01:16:48.960 | if no, at least certainly if no one else knows
01:16:51.680 | that they have it, right?
01:16:53.720 | But eventually we think that we could migrate the internet
01:16:58.560 | to the post-quantum cryptography,
01:17:00.600 | and then we'd be more or less back where we started.
01:17:03.540 | Okay, so this is sort of not the application
01:17:06.300 | of quantum computing, I think,
01:17:07.680 | that's really going to change the world
01:17:09.560 | in a sustainable way, right?
01:17:11.080 | The big, by the way, the biggest practical application
01:17:14.380 | of quantum computing that we know about by far,
01:17:17.520 | I think is simply the simulation
01:17:19.640 | of quantum mechanics itself.
01:17:21.520 | In order to, you know, learn about chemical reactions,
01:17:25.000 | you know, design maybe new chemical processes,
01:17:28.480 | new materials, new drugs, new solar cells,
01:17:32.920 | new superconductors, all kinds of things like that.
01:17:35.880 | - What's the size of a quantum computer
01:17:38.800 | that would be able to simulate the, you know,
01:17:42.280 | quantum mechanical systems themselves
01:17:44.840 | that would be impactful for the real world
01:17:46.960 | for the kind of chemical reactions and that kind of work?
01:17:50.520 | What scale are we talking about?
01:17:52.240 | - Now you're asking a very, very current question,
01:17:56.020 | a very big question.
01:17:57.920 | People are going to be racing over the next decade
01:18:01.100 | to try to do useful quantum simulations,
01:18:04.900 | even with, you know, 100 or 200 qubit quantum computers
01:18:09.280 | of the sort that we expect to be able to build
01:18:11.640 | over the next decade, okay?
01:18:13.280 | So that might be, you know, the first application
01:18:17.560 | of quantum computing that we're able to realize,
01:18:20.280 | you know, or maybe it will prove to be too difficult
01:18:23.280 | and maybe even that will require fault tolerance
01:18:26.260 | or, you know, will require error correction.
01:18:28.480 | - So there's an aggressive race to come up
01:18:30.580 | with the one case study, kind of like with Peter Shor,
01:18:34.220 | with the idea that would just capture
01:18:37.380 | the world's imagination of, look,
01:18:39.220 | we can actually do something very useful here.
01:18:41.940 | - Right, but I think, you know, within the next decade,
01:18:44.340 | the best shot we have is certainly not, you know,
01:18:47.380 | using Shor's algorithm to break cryptography, you know,
01:18:51.540 | just because it requires, you know,
01:18:53.540 | too much in the way of error correction.
01:18:55.880 | The best shot we have is to do some quantum simulation
01:19:00.020 | that tells the material scientists or chemists
01:19:03.820 | or nuclear physicists, you know,
01:19:05.920 | something that is useful to them
01:19:07.580 | and that they didn't already know.
01:19:09.180 | You know, and you might only need one or two successes
01:19:11.780 | in order to change some, you know,
01:19:13.080 | billion dollar industries, right?
01:19:14.780 | Like, you know, the way that people make fertilizer
01:19:17.580 | right now is still based on the Haber-Bosch process
01:19:20.860 | from a century ago, and it is some many-body
01:19:24.300 | quantum mechanics problem that no one really understands.
01:19:27.080 | Right, if you could design a better way to make fertilizer,
01:19:30.640 | right, that's, you know, billions of dollars right there.
01:19:33.240 | So those are sort of the applications
01:19:36.160 | that people are going to be aggressively racing toward
01:19:38.760 | over the next decade.
01:19:40.220 | Now, I don't know if they're gonna realize it or not,
01:19:42.640 | but, you know, they certainly at least have a shot.
01:19:46.360 | So it's gonna be a very, very interesting next decade.
01:19:49.120 | - But just to clarify, what's your intuition
01:19:51.640 | is if a breakthrough like that comes,
01:19:54.140 | is it possible for that breakthrough
01:19:55.480 | to be on 50 to 100 qubits,
01:19:58.320 | or is scale a fundamental thing,
01:20:01.200 | like 500, 1,000 plus qubits?
01:20:04.320 | - Yeah, so I can tell you what the current studies
01:20:07.480 | are saying, you know, I think probably better
01:20:11.360 | to rely on that than on my intuition.
01:20:14.080 | But, you know, there was a group at Microsoft
01:20:17.600 | had a study a few years ago that said,
01:20:20.920 | even with only about 100 qubits,
01:20:23.840 | you know, you could already learn something new
01:20:26.180 | about the chemical reaction that makes fertilizer,
01:20:30.020 | for example.
01:20:30.960 | The trouble is they're talking about 100 qubits
01:20:34.580 | and about a million layers of quantum gates.
01:20:39.020 | Okay, so basically they're talking about
01:20:40.860 | 100 nearly perfect qubits.
01:20:43.100 | - So the logical qubits as you mentioned before.
01:20:44.820 | - Yeah, exactly, 100 logical qubits.
01:20:47.580 | And now, you know, the hard part for the next decade
01:20:50.840 | is gonna be, well, what can we do
01:20:52.380 | with 100 to 200 noisy qubits?
01:20:56.140 | - Yeah. - Yeah.
01:20:57.140 | - Is there error correction breakthroughs
01:20:59.220 | that might come without the need to do
01:21:01.900 | thousands or millions of physical qubits?
01:21:05.100 | - Yeah, so people are gonna be pushing simultaneously
01:21:07.980 | on a bunch of different directions.
01:21:09.920 | One direction, of course, is just making the qubits better.
01:21:13.080 | Right?
01:21:14.300 | And, you know, there is tremendous progress there.
01:21:17.100 | I mean, you know, the fidelity is like,
01:21:19.420 | the accuracy of the qubits has improved
01:21:22.700 | by several orders of magnitude, you know,
01:21:24.700 | in the last decade or two.
01:21:28.440 | Okay, the second thing is designing better,
01:21:31.780 | you know, let's say lower overhead error correcting codes.
01:21:36.220 | And even short of doing the full recursive error correction,
01:21:40.340 | you know, there are these error mitigation strategies
01:21:43.480 | that you can use, you know, that may, you know,
01:21:47.060 | allow you to eke out a useful speed up in the near term.
01:21:52.060 | And then the third thing is just taking
01:21:54.820 | the quantum algorithms for simulating quantum chemistry
01:21:58.900 | or materials and making them more efficient.
01:22:01.940 | You know, and those algorithms are already
01:22:04.060 | dramatically more efficient than they were,
01:22:06.260 | let's say, five years ago.
01:22:07.980 | And so when, you know, I quoted these estimates,
01:22:10.540 | like, you know, circuit depth of 1 million.
01:22:13.380 | And so, you know, I hope that because people will care enough
01:22:16.820 | that these numbers are gonna come down.
01:22:18.900 | - So you're one of the world-class researchers in this space.
01:22:23.900 | There's a few groups, like you mentioned,
01:22:26.100 | Google and IBM working at this.
01:22:27.900 | There's other research labs.
01:22:30.980 | But you put also, you have an amazing blog.
01:22:35.980 | You just, you put a lot of-- - You're too kind.
01:22:37.660 | - You put a, you paid me to say it.
01:22:40.260 | You put a lot of efforts sort of to communicating
01:22:44.220 | the science of this and communicating,
01:22:47.980 | exposing some of the BS and sort of the natural,
01:22:52.220 | just like in the AI space, the natural charlatanism,
01:22:56.820 | if that's a word, in this, in quantum mechanics in general,
01:23:01.060 | but quantum computers and so on.
01:23:03.020 | Can you give some notes about people or ideas
01:23:08.020 | that people like me or listeners in general
01:23:10.380 | from outside the field should be cautious of
01:23:12.700 | when they're taking in news headings
01:23:15.980 | that Google achieved quantum supremacy?
01:23:19.460 | So what should we look out for?
01:23:21.540 | Where's the charlatans in this space?
01:23:23.180 | Where's the BS?
01:23:24.020 | - Yeah, so, good question.
01:23:26.980 | Unfortunately, quantum computing is a little bit like
01:23:31.660 | cryptocurrency or deep learning.
01:23:34.180 | Like there is a core of something
01:23:35.780 | that is genuinely revolutionary and exciting.
01:23:38.860 | And because of that core, it attracts
01:23:41.500 | this sort of vast penumbra of people making
01:23:45.700 | just utterly ridiculous claims.
01:23:48.980 | And so with quantum computing, I mean,
01:23:52.340 | I would say that the main way that people go astray
01:23:56.420 | is by not focusing on sort of the question of,
01:24:00.860 | are you getting a speed up
01:24:02.300 | over a classical computer or not, right?
01:24:05.140 | And so people have like dismissed quantum supremacy
01:24:10.420 | because it's not useful, right?
01:24:12.300 | Or it's not itself, let's say, obviously useful for anything.
01:24:16.380 | Okay, but ironically, these are some of the same people
01:24:19.980 | who will go and say, well,
01:24:21.260 | we care about useful applications.
01:24:23.500 | We care about solving traffic routing
01:24:26.260 | and financial optimization and all these things.
01:24:29.940 | And that sounds really good,
01:24:32.140 | but their entire spiel is sort of counting on
01:24:36.900 | nobody asking the question, yes,
01:24:39.060 | but how well could a classical computer do the same thing?
01:24:42.340 | - Yes. - Right?
01:24:43.940 | I really mean the entire thing is,
01:24:46.420 | they say, well, a quantum computer can do this,
01:24:50.540 | a quantum computer can do that, right?
01:24:52.300 | And they just avoid the question,
01:24:55.060 | are you getting a speed up over a classical computer or not?
01:24:58.660 | And if so, how do you know?
01:25:01.220 | Have you really thought carefully about classical algorithms
01:25:05.260 | to solve the same problem, right?
01:25:07.740 | And a lot of the application areas
01:25:10.100 | that companies and investors are most excited about,
01:25:15.100 | that the popular press is most excited about
01:25:19.780 | for quantum computers have been things like
01:25:22.180 | machine learning, AI, optimization, okay?
01:25:27.180 | And the problem with that is that since the very beginning,
01:25:31.780 | even if you have a perfect fault tolerant,
01:25:36.700 | scalable quantum computer,
01:25:38.500 | we have known of only modest speed ups
01:25:43.060 | that you can get for these problems, okay?
01:25:46.380 | So there is a famous quantum algorithm
01:25:48.740 | called Grover's algorithm, okay?
01:25:50.860 | And what it can do is it can solve many, many of the problems
01:25:54.460 | that arise in AI, machine learning, optimization,
01:25:58.180 | including NP complete problems, okay?
01:26:00.780 | But it can solve them in about the square root
01:26:03.540 | of the number of steps that a classical computer
01:26:05.980 | would need for the same problems, okay?
01:26:08.260 | Now a square root speed up is important, it's impressive.
01:26:12.340 | It is not an exponential speed up, okay?
01:26:15.140 | So it is not the kind of game changer
01:26:17.780 | that let's say Shor's algorithm for factoring is,
01:26:20.820 | or for that matter, that simulation of quantum mechanics is,
01:26:23.700 | okay, it is a more modest speed up.
01:26:26.300 | Let's say roughly, in theory,
01:26:28.780 | it could roughly double the size
01:26:30.380 | of the optimization problems that you could handle, right?
01:26:33.380 | And so, because people found that, I guess, too boring
01:26:38.380 | or too unimpressive, they've gone on to invent
01:26:43.980 | all of these heuristic algorithms where,
01:26:47.100 | because no one really understands them,
01:26:49.380 | you can just project your hopes onto them, right?
01:26:52.500 | That well, maybe it gets an exponential speed up.
01:26:55.820 | You can't prove that it doesn't,
01:26:57.740 | and the burden is on you to prove
01:26:59.300 | that it doesn't get a speed up, right?
01:27:00.860 | And so they've done an immense amount
01:27:03.220 | of that kind of thing, and a really worrying amount
01:27:07.140 | of the case for building a quantum computer
01:27:09.780 | has come to rest on this stuff
01:27:11.780 | that those of us in this field know perfectly well
01:27:14.860 | is on extremely shaky foundations.
01:27:17.620 | - So the fundamental question is,
01:27:20.620 | show that there's a speed up over the classical.
01:27:23.540 | - Yes, absolutely.
01:27:24.380 | - And in this space that you're referring to,
01:27:26.500 | which is actually really interesting,
01:27:27.660 | is the area that a lot of people are excited about
01:27:30.100 | is machine learning.
01:27:31.340 | So your sense is, do you think it will,
01:27:34.700 | I know that there's a lot of smoke currently,
01:27:37.780 | but do you think there actually eventually
01:27:40.300 | might be breakthroughs where you do get exponential
01:27:43.700 | speed ups in the machine learning space?
01:27:46.580 | - Absolutely, there might be.
01:27:48.020 | I mean, I think we know of modest speed ups
01:27:50.660 | that you can get for these problems.
01:27:52.700 | I think whether you can get bigger speed ups
01:27:55.500 | is one of the biggest questions
01:27:58.100 | for quantum computing theory.
01:28:00.620 | For people like me to be thinking about.
01:28:03.580 | Now, we had actually recently a really,
01:28:07.460 | a super exciting candidate for an exponential
01:28:12.340 | quantum speed up for a machine learning problem
01:28:15.180 | that people really care about.
01:28:16.780 | This is basically the Netflix problem.
01:28:19.100 | The problem of recommending products to users
01:28:22.380 | given some sparse data about their preferences.
01:28:25.540 | Karunidas and Prakash in 2016 had an algorithm
01:28:29.500 | for sampling recommendations that was exponentially faster
01:28:33.660 | than any known classical algorithm.
01:28:35.900 | And so a lot of people were excited.
01:28:38.020 | I was excited about it.
01:28:40.140 | I had an 18 year old undergrad by the name of Yilin Tang.
01:28:44.540 | And she was obviously brilliant.
01:28:47.180 | She was looking for a project.
01:28:48.820 | I gave her as a project,
01:28:50.380 | can you prove that this speed up is real?
01:28:52.900 | Can you prove that any classical algorithm
01:28:55.620 | would need to access exponentially more data?
01:28:58.900 | And this was a case where if that was true,
01:29:01.740 | this was not like a P versus NP type of question.
01:29:05.100 | This might well have been provable.
01:29:07.180 | But she worked on it for a year.
01:29:09.180 | She couldn't do it.
01:29:10.620 | Eventually she figured out why she couldn't do it.
01:29:13.460 | And the reason was that that was false.
01:29:15.540 | There is a classical algorithm
01:29:18.220 | with a similar performance to the quantum algorithm.
01:29:20.900 | So Yilin succeeded in de-quantizing
01:29:23.940 | that machine learning algorithm.
01:29:25.380 | And then in the last couple of years,
01:29:28.020 | building on Yilin's breakthrough,
01:29:30.260 | a bunch of the other quantum machine learning algorithms
01:29:33.100 | that were proposed have now also been de-quantized.
01:29:36.580 | Okay, and so I would say--
01:29:37.420 | - That's a kind of important backward step.
01:29:40.180 | - Yes.
01:29:41.020 | - Or a forward step for science,
01:29:43.700 | but a step for quantum machine learning
01:29:47.020 | that precedes the big next forward step.
01:29:50.860 | - Right, right, right.
01:29:51.700 | - If it's possible.
01:29:52.540 | - Right, now some people will say,
01:29:54.380 | well, you know, there's a silver lining in this cloud.
01:29:57.100 | They say, well, thinking about quantum computing
01:29:59.340 | has led to the discovery
01:30:01.100 | of potentially useful new classical algorithms.
01:30:03.940 | - That's true.
01:30:04.780 | - Right, and so you get these spinoff applications,
01:30:07.540 | but if you want a quantum speedup,
01:30:09.380 | you really have to think carefully about that.
01:30:11.940 | You know, Yilin's work was a perfect illustration of why.
01:30:15.340 | Right, and I think that the challenge,
01:30:18.980 | the field is now open, right?
01:30:22.460 | Find a better example.
01:30:23.900 | Find where quantum computers are going
01:30:27.020 | to deliver big gains for machine learning.
01:30:29.420 | Not only do I ardently support people thinking about that,
01:30:36.100 | I'm trying to think about it myself
01:30:37.780 | and have my students and postdocs think about it,
01:30:40.740 | but we should not pretend
01:30:43.100 | that those speedups are already established,
01:30:45.540 | and the problem comes when so many of the companies
01:30:49.460 | and journalists in this space are pretending that.
01:30:54.580 | - Like all good things, like life itself,
01:30:57.900 | this conversation must soon come to an end.
01:31:00.700 | Let me ask the most absurdly philosophical last question.
01:31:04.780 | What is the meaning of life?
01:31:07.660 | What gives your life fulfillment, purpose,
01:31:11.700 | happiness, and yeah, meaning?
01:31:15.660 | - I would say, you know, number one,
01:31:19.060 | trying to discover new things about the world
01:31:22.580 | and share them and communicate
01:31:25.500 | and learn what other people have discovered.
01:31:29.540 | You know, number two, my friends, my family,
01:31:34.540 | my kids, my students,
01:31:39.060 | you know, just the people around me.
01:31:42.980 | Number three, you know, trying when I can
01:31:47.780 | to make the world better in some small ways.
01:31:52.260 | And you know, it's depressing that I can't do more
01:31:54.660 | and that, you know, the world is facing crises
01:31:59.660 | over the climate and over, you know,
01:32:02.460 | sort of resurgent authoritarianism
01:32:04.620 | and all these other things,
01:32:05.700 | but you know, trying to stand against the things
01:32:10.700 | that I find horrible when I can.
01:32:12.540 | - Let me ask you one more absurd question.
01:32:16.260 | What makes you smile?
01:32:17.540 | - Well, yeah, I guess your question just did, I don't know.
01:32:21.540 | (both laughing)
01:32:23.700 | - I thought I tried that absurd one on you.
01:32:25.740 | Well, it was a huge honor to talk to you.
01:32:28.580 | We'll probably talk to you for many more hours, Scott.
01:32:30.740 | Thank you so much.
01:32:31.660 | - Well, thank you, thank you, it was great.
01:32:34.500 | - Thank you for listening to this conversation
01:32:36.180 | with Scott Aronson,
01:32:37.260 | and thank you to our presenting sponsor, Cash App.
01:32:40.340 | Download it, use code LEGSPODCAST, you'll get $10,
01:32:44.060 | and $10 will go to FIRST,
01:32:45.620 | an organization that inspires and educates young minds
01:32:48.620 | to become science and technology innovators of tomorrow.
01:32:51.940 | If you enjoy this podcast, subscribe on YouTube,
01:32:54.380 | give it five stars on Apple Podcast,
01:32:56.260 | support it on Patreon,
01:32:57.620 | or simply connect with me on Twitter @LexFriedman.
01:33:00.980 | Now, let me leave you with some words
01:33:03.860 | from a funny and insightful blog post Scott wrote
01:33:07.300 | over 10 years ago on the ever-present Malthusianisms
01:33:10.980 | in our daily lives.
01:33:12.980 | Quote, "Again and again,
01:33:14.860 | I've undergone the humbling experience
01:33:17.060 | of first lamenting how badly something sucks,
01:33:19.780 | then only much later having the crucial insight
01:33:23.500 | that it's not sucking
01:33:25.180 | wouldn't have been a Nash equilibrium."
01:33:28.100 | Thank you for listening, I hope to see you next time.
01:33:32.380 | (upbeat music)
01:33:34.980 | (upbeat music)
01:33:37.580 | [BLANK_AUDIO]