Scott Aaronson: Quantum Computing | Lex Fridman Podcast #72

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.160 | Why?

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]

Scott Aaronson: Quantum Computing | Lex Fridman Podcast #72

Chapters