Scott Aaronson: Quantum Supremacy

00:00:00.000 | Google announced with their work in the paper

00:00:05.000 | in Nature with quantum supremacy.

00:00:09.160 | Can you describe, again, back to the basic,

00:00:11.900 | what is, perhaps not so basic, what is quantum supremacy?

00:00:16.000 | - Absolutely.

00:00:17.080 | So quantum supremacy is a term that was coined by,

00:00:21.120 | again, by John Preskill in 2012.

00:00:24.640 | Not everyone likes the name, you know,

00:00:27.940 | but you know, it sort of stuck.

00:00:31.080 | You know, we don't, we sort of haven't found

00:00:35.040 | a better alternative.

00:00:36.240 | - It's technically quantum computational supremacy.

00:00:38.480 | - Yeah, yeah, supremacy, that's right, that's right.

00:00:40.640 | But the basic idea is actually one that goes

00:00:43.440 | all the way back to the beginnings of quantum computing

00:00:46.560 | when Richard Feynman and David Deutch, people like that,

00:00:49.520 | were talking about it in the early '80s.

00:00:51.560 | And quantum supremacy just refers to sort of the point

00:00:56.640 | in history when you can first use a quantum computer

00:01:00.460 | to do some well-defined task much faster

00:01:04.500 | than any known algorithm running on any

00:01:07.300 | of the classical computers that are available.

00:01:09.660 | Okay, so you know, notice that I did not say

00:01:12.300 | a useful task, okay?

00:01:14.300 | You know, it could be something completely artificial,

00:01:17.060 | but it's important that the task be well-defined.

00:01:19.860 | So in other words, you know, there is,

00:01:21.620 | it is something that has right and wrong answers,

00:01:24.540 | you know, that are knowable independently of this device,

00:01:28.240 | right, and we can then, you know, run the device,

00:01:30.480 | see if it gets the right answer or not.

00:01:32.440 | - Can you clarify a small point?

00:01:34.040 | You said much faster than the classical implementation.

00:01:37.520 | What about, sort of what about the space

00:01:40.800 | with where the class, there's no, there's not,

00:01:43.200 | it doesn't even exist a classical algorithm to--

00:01:45.880 | - So maybe I should clarify, everything that a quantum

00:01:49.860 | computer can do, a classical computer

00:01:52.280 | can also eventually do, okay?

00:01:54.700 | And the reason why we know that is that

00:01:57.340 | a classical computer could always, you know,

00:02:00.300 | if it had no limits of time and memory,

00:02:03.560 | it could always just store the entire quantum state,

00:02:07.260 | you know, of your, you know, of the quantum,

00:02:09.300 | right, store a list of all the amplitudes,

00:02:12.900 | you know, in the state of the quantum computer,

00:02:15.300 | and then just, you know, do some linear algebra

00:02:18.140 | to just update that state, right?

00:02:20.220 | And so, so anything that quantum computers can do

00:02:23.480 | can also be done by classical computers,

00:02:26.360 | albeit exponentially slower in some cases.

00:02:28.680 | - So quantum computers don't go into some magical place

00:02:31.800 | outside of Alan Turing's definition of computation.

00:02:34.720 | - Precisely, they do not solve the halting problem.

00:02:38.000 | They cannot solve anything that is uncomputable

00:02:40.760 | in Alan Turing's sense.

00:02:42.440 | What they, what we think they do change

00:02:44.720 | is what is efficiently computable, okay?

00:02:47.320 | And, you know, since the 1960s, you know,

00:02:50.380 | the word efficiently, you know,

00:02:52.140 | as well as been a central word in computer science,

00:02:54.980 | but it's sort of a code word for something technical,

00:02:58.040 | which is basically with polynomial scaling, you know,

00:03:01.840 | that as you get to larger and larger inputs,

00:03:04.820 | you would like an algorithm that uses an amount of time

00:03:07.780 | that scales only like the size of the input

00:03:10.360 | raised to some power, and not exponentially

00:03:13.240 | with the size of the input, right?

00:03:15.340 | - Yeah, so I do hope we get to talk again,

00:03:17.820 | because one of the many topics

00:03:20.640 | that there's probably several hours worth of conversation on

00:03:23.920 | is complexity, which we probably won't even get a chance

00:03:26.360 | to touch today, but you briefly mentioned it.

00:03:30.640 | But let's maybe try to continue.

00:03:33.300 | So you said the definition of quantum supremacy

00:03:36.620 | is basically design, is achieving a place

00:03:40.400 | where much faster on a formal,

00:03:43.080 | that quantum computer is much faster

00:03:44.500 | on a formal, well-defined problem

00:03:47.380 | that is or isn't useful.

00:03:49.140 | - Yeah, yeah, yeah, right, right.

00:03:50.340 | And I would say that we really want three things, right?

00:03:53.300 | We want, first of all, the quantum computer

00:03:55.980 | to be much faster, just in the literal sense

00:03:58.580 | of like number of seconds, you know,

00:04:01.340 | at just solving this, you know, well-defined problem.

00:04:04.860 | Secondly, we want it to be sort of, you know,

00:04:08.560 | for a problem where we really believe

00:04:10.820 | that a quantum computer has better scaling behavior, right?

00:04:14.020 | So it's not just an incidental, you know,

00:04:16.740 | matter of hardware, but it's that, you know,

00:04:19.160 | as you went to larger and larger inputs, you know,

00:04:22.240 | the classical scaling would be exponential

00:04:25.280 | and the scaling for the quantum algorithm

00:04:27.760 | would only be polynomial.

00:04:29.600 | And then thirdly, we want the first thing,

00:04:32.120 | the actual observed speed up to only be explainable

00:04:36.080 | in terms of the scaling behavior, right?

00:04:38.640 | So, you know, I want, you know, a real world,

00:04:41.900 | you know, a real problem to get solved,

00:04:44.540 | let's say by a quantum computer with 50 qubits or so,

00:04:48.540 | and for no one to be able to explain that in any way

00:04:51.580 | other than, well, you know, to,

00:04:54.320 | this computer involved a quantum state

00:04:58.340 | with two to the 50th power amplitudes.

00:05:01.180 | And, you know, a classical simulation,

00:05:03.180 | at least any that we know today,

00:05:05.080 | would require keeping track of two to the 50th numbers.

00:05:08.460 | And this is the reason why it was faster.

00:05:10.440 | - So the intuition is that then if you demonstrate

00:05:13.120 | on 50 qubits, then once you get to 100 qubits,

00:05:16.380 | then it'll be even much more faster.

00:05:18.760 | - Precisely, precisely.

00:05:20.460 | Yeah, and, you know, and quantum supremacy

00:05:23.020 | does not require error correction, right?

00:05:25.200 | We don't, you know, we don't have,

00:05:26.520 | you could say true scalability yet,

00:05:28.700 | or true, you know, error correction yet,

00:05:32.620 | but you could say quantum supremacy

00:05:34.580 | is already enough by itself

00:05:36.920 | to refute the skeptics who said a quantum computer

00:05:40.200 | will never outperform a classical computer for anything.

00:05:43.200 | - But one, how do you demonstrate quantum supremacy?

00:05:48.200 | And two, what's up with these news articles

00:05:51.840 | I'm reading that Google did so?

00:05:53.840 | - Yeah, all right, well--

00:05:54.680 | - What did they actually do?

00:05:56.080 | - Great questions, 'cause now you get into,

00:05:59.100 | actually, you know, a lot of the work that I've,

00:06:01.920 | you know, I and my students have been doing

00:06:03.720 | for the last decade,

00:06:05.080 | which was precisely about how do you demonstrate

00:06:09.160 | quantum supremacy using technologies

00:06:11.760 | that, you know, we thought would be available

00:06:13.880 | in the near future?

00:06:15.180 | And so one of the main things that we realized

00:06:20.000 | around 2011, and this was me and my student,

00:06:24.640 | Alex Arkhipov at MIT at the time,

00:06:27.900 | and independently of some others,

00:06:31.240 | including Bremner, Josa, and Shepard, okay?

00:06:34.280 | And the realization that we came to

00:06:38.280 | was that if you just want to prove

00:06:41.080 | that a quantum computer is faster, you know,

00:06:43.200 | and not do something useful with it,

00:06:45.280 | then there are huge advantages to sort of

00:06:47.840 | switching your attention from problems

00:06:50.400 | like factoring numbers that have a single right answer

00:06:54.120 | to what we call sampling problems.

00:06:56.680 | So these are problems where the goal

00:06:59.000 | is just to output a sample

00:07:01.080 | from some probability distribution,

00:07:03.500 | let's say over strings of 50 bits, right?

00:07:06.160 | So there are, you know, many, many, many

00:07:08.500 | possible valid outputs.

00:07:10.200 | You know, your computer will probably

00:07:11.680 | never even produce the same output twice,

00:07:14.400 | you know, if it's running as,

00:07:16.320 | even, you know, assuming it's running perfectly, okay?

00:07:20.920 | But the key is that some outputs

00:07:23.260 | are supposed to be likelier than other ones.

00:07:25.760 | - So, sorry, to clarify,

00:07:27.780 | is there a set of outputs that are valid

00:07:30.640 | and a set that are not?

00:07:31.840 | Or is it more that the distribution

00:07:36.020 | of a particular kind of output is more,

00:07:39.260 | is there's a specific distribution

00:07:41.380 | of a particular kind of output?

00:07:42.220 | - Yeah, there's a specific distribution

00:07:44.700 | that you're trying to hit, right?

00:07:46.080 | Or, you know, that you're trying to sample from.

00:07:48.080 | Now, there are a lot of questions about this.

00:07:50.620 | You know, how do you do that, right?

00:07:52.620 | Now, how you do it, you know,

00:07:55.740 | it turns out that with a quantum computer,

00:07:58.280 | even with the noisy quantum computers

00:08:00.340 | that we have now, that we have today,

00:08:02.900 | what you can do is basically just apply

00:08:05.020 | a randomly chosen sequence of operations, right?

00:08:08.340 | So we, you know, we, in some of those, you know,

00:08:10.460 | that part is almost trivial, right?

00:08:12.700 | We just sort of get the qubits to interact

00:08:15.400 | in some random way, although a sort of

00:08:17.620 | precisely specified random way,

00:08:19.740 | so we can repeat the exact same

00:08:22.180 | random sequence of interactions again

00:08:24.580 | and get another sample from that same distribution.

00:08:27.640 | And what this does is it basically,

00:08:29.980 | well, it creates a lot of garbage,

00:08:32.260 | but, you know, very specific garbage, right?

00:08:34.700 | So, you know, of all of the,

00:08:37.260 | so if we're going to talk about Google's device,

00:08:39.500 | there were 53 qubits there, okay?

00:08:42.180 | And so there were two to the 53 power possible outputs.

00:08:46.140 | Now, for some of those outputs, you know,

00:08:48.460 | there was a little bit more destructive interference

00:08:52.340 | in their amplitude, okay?

00:08:53.780 | So their amplitudes were a little bit smaller.

00:08:56.140 | And for others, there was a little more

00:08:57.540 | constructive interference.

00:08:59.320 | You know, the amplitudes were a little bit more aligned

00:09:01.600 | with each other, you know, and so those,

00:09:04.380 | those that were a little bit likelier, okay?

00:09:06.940 | All of the outputs are exponentially unlikely,

00:09:10.300 | but some are, let's say, two times or three times,

00:09:13.500 | you know, unlikelier than others, okay?

00:09:15.820 | And so you can define, you know,

00:09:18.860 | this sequence of operations that gives rise

00:09:21.660 | to this probability distribution.

00:09:23.780 | Okay, now, the next question would be,

00:09:26.820 | well, how do you, you know, even if you're sampling from it,

00:09:29.140 | how do you verify that?

00:09:30.360 | - Right, exactly. - How do you know?

00:09:32.160 | And so my students and I, and also the people at Google

00:09:37.160 | were doing the experiment, came up with statistical tests

00:09:41.120 | that you can apply to the outputs in order to

00:09:44.960 | try to verify, you know, what is, you know,

00:09:49.480 | that at least that some hard problem is being solved.

00:09:53.920 | The test that Google ended up using

00:09:56.720 | was something that they called

00:09:57.900 | the linear cross-entropy benchmark, okay?

00:10:00.880 | And it's basically, you know, so the drawback of this test

00:10:04.360 | is that it requires, like, it requires you

00:10:07.320 | to do a two to the 53 time calculation

00:10:11.120 | with your classical computer, okay?

00:10:12.960 | So it's very expensive to do the test

00:10:15.800 | on a classical computer. - Yeah.

00:10:17.320 | - The good news is-- - How big of a number

00:10:18.800 | is two to the 53? - It's about nine quadrillion.

00:10:21.680 | - Okay. - That doesn't help.

00:10:23.200 | - Well, you know, it's, you want it

00:10:25.040 | in like scientific notation-- - No, no, no, no.

00:10:26.680 | - What I mean is-- - Yeah, it is, it is,

00:10:29.080 | it is just-- - Is it impossible

00:10:30.120 | to run on a-- - Yeah, so we will come

00:10:32.360 | back to that.

00:10:33.200 | It is just barely possible to run, we think,

00:10:35.920 | on the largest supercomputer that currently exists on Earth,

00:10:39.160 | which is called Summit at Oak Ridge National Lab, okay?

00:10:42.440 | (laughing)

00:10:43.440 | - Great, this is exciting.

00:10:44.920 | - That's the short answer.

00:10:46.280 | So ironically, for this type of experiment,

00:10:50.000 | we don't want 100 qubits, okay?

00:10:52.400 | Because with 100 qubits, even if it works,

00:10:55.040 | we don't know how to verify the results, okay?

00:10:57.640 | So we want a number of qubits that is enough

00:11:00.800 | that the biggest classical computers on Earth

00:11:04.440 | will have to sweat and will just barely be able

00:11:08.560 | to keep up with the quantum computer,

00:11:11.160 | using much more time, but they will still be able to do it

00:11:14.680 | in order that we can verify the results.

00:11:16.440 | - Which is where the 53 comes from,

00:11:18.200 | for the number of qubits. - Basically, well,

00:11:19.280 | I mean, that's also, that's sort of,

00:11:23.560 | I mean, that's sort of where they are now,

00:11:26.920 | in terms of scaling, you know?

00:11:28.480 | And then, you know, soon, you know,

00:11:29.800 | that point will be passed.

00:11:31.720 | And then when you get to larger numbers of qubits,

00:11:34.880 | then, you know, these types of sampling experiments

00:11:38.200 | will no longer be so interesting,

00:11:40.240 | because we won't even be able to verify the results,

00:11:43.000 | and we'll have to switch to other types of computation.

00:11:45.800 | So with the sampling thing, you know,

00:11:48.120 | so the test that Google applied,

00:11:50.600 | with this linear cross-entropy benchmark,

00:11:52.800 | is basically just take the samples that were generated,

00:11:56.480 | which are, you know, a very small subset

00:11:58.920 | of all the possible samples that there are,

00:12:01.120 | but for those, you calculate, with your classical computer,

00:12:04.680 | the probabilities that they should have been output.

00:12:07.640 | And you see, are those probabilities,

00:12:09.640 | like, larger than the mean?

00:12:11.160 | You know, so is the quantum computer biased

00:12:13.400 | toward outputting the strings that it's, you know,

00:12:16.240 | that you want it to be biased toward?

00:12:18.400 | Okay, and then, finally, we come to a very crucial question,

00:12:22.360 | which is supposing that it does that,

00:12:24.320 | well, how do we know that a classical computer

00:12:26.520 | could not have quickly done the same thing, right?

00:12:29.360 | How do we know that, you know,

00:12:30.480 | this couldn't have been spoofed by a classical computer,

00:12:33.360 | right, and so, well, the first answer is we don't know,

00:12:36.960 | for sure, because, you know,

00:12:38.560 | this takes us into questions of complexity theory,

00:12:41.840 | you know, I mean, questions on the,

00:12:44.720 | of the magnitude of the P versus NP question,

00:12:47.560 | and things like that, right?

00:12:48.400 | You know, we don't know how to rule out definitively

00:12:51.640 | that there could be fast classical algorithms for,

00:12:55.000 | you know, even simulating quantum mechanics,

00:12:57.080 | and for, you know, simulating experiments like these,

00:13:00.440 | but we can give some evidence against that possibility,

00:13:04.280 | and that was sort of the, you know,

00:13:06.120 | the main thrust of a lot of the work

00:13:08.280 | that my colleagues and I did, you know,

00:13:10.680 | over the last decade, which is then sort of in,

00:13:13.280 | around 2015 or so, what led to Google

00:13:16.320 | deciding to do this experiment.

00:13:18.040 | - So is the kind of evidence you,

00:13:20.640 | first of all, the hard P equals NP problem that you mentioned

00:13:23.920 | and the kind of evidence that you're,

00:13:26.360 | were looking at, is that something you come to

00:13:30.520 | on a sheet of paper, or is this something,

00:13:33.720 | are these empirical experiments?

00:13:35.480 | - It's math, for the most part.

00:13:37.640 | I mean, you know, it's also, you know,

00:13:40.840 | we have a bunch of methods that are known

00:13:44.440 | for simulating quantum circuits,

00:13:48.280 | you know, quantum computations with classical computers,

00:13:51.600 | and so we have to try them all out

00:13:53.400 | and make sure that, you know, they don't work,

00:13:55.600 | you know, make sure that they have exponential scaling

00:13:58.320 | on, you know, these problems,

00:14:00.800 | and not just theoretically,

00:14:02.240 | but with the actual range of parameters

00:14:04.440 | that are actually, you know, arising in Google's experiment.

00:14:08.400 | Okay, so there is an empirical component to it, right?

00:14:11.440 | But now, on the theoretical side,

00:14:15.200 | you know, basically what we know how to do

00:14:17.800 | in theoretical computer science and computational complexity

00:14:21.560 | is, you know, we don't know how to prove

00:14:24.160 | that most of the problems we care about are hard,

00:14:26.880 | but we know how to pass the blame to someone else.

00:14:29.840 | Okay, we know how to say, well, look, you know,

00:14:32.040 | I can't prove that this problem is hard,

00:14:34.440 | but if it is easy, then all these other things

00:14:36.960 | that, you know, you probably were much more confident

00:14:41.120 | or were hard, then those would be easy as well, okay?

00:14:44.800 | So we can give what are called reductions.

00:14:47.780 | And this has been the basic strategy in, you know,

00:14:50.720 | NP completeness, right,

00:14:52.640 | in all of theoretical computer science and cryptography

00:14:56.800 | since the 1970s, really.

00:14:59.060 | And so we were able to give some reduction evidence

00:15:02.260 | for the hardness of simulating these sampling experiments,

00:15:07.260 | these sampling-based quantum supremacy experiments.

00:15:11.280 | The reduction evidence is not as satisfactory

00:15:14.200 | as it should be.

00:15:15.380 | One of the biggest open problems in this area

00:15:17.960 | is to make it better.

00:15:19.480 | But, you know, we can do something.

00:15:21.380 | You know, certainly we can say that, you know,

00:15:24.780 | if there is a fast classical algorithm

00:15:27.460 | to spoof these experiments,

00:15:29.240 | then it has to be very, very unlike

00:15:31.220 | any of the algorithms that we know.

00:15:32.980 | - Which is kind of in the same kind of space of reasoning

00:15:38.240 | that people say P not equals NP.

00:15:41.200 | - Yeah, it's in the same spirit.

00:15:43.580 | (silence)

00:15:45.740 | (silence)

00:15:47.900 | (silence)

00:15:50.060 | (silence)

00:15:52.220 | (silence)

00:15:54.380 | (silence)

00:15:56.540 | (silence)

00:15:58.700 | [BLANK_AUDIO]

Scott Aaronson: Quantum Supremacy | AI Podcast Clips

Chapters