Full episode with Scott Aaronson (Feb 2020): https://www.youtube.com/watch?v=uX5t8EivCaM
Clips channel (Lex Clips): https://www.youtube.com/lexclips
Main channel (Lex Fridman): https://www.youtube.com/lexfridman
(more links below)

Podcast full episodes playlist:
https://www.youtube.com/playlist?list=PLrAXtmErZgOdP_8GztsuKi9nrraNbKKp4

Podcasts clips playlist:
https://www.youtube.com/playlist?list=PLrAXtmErZgOeciFP3CBCIEElOJeitOr41

Podcast website:
https://lexfridman.com/ai

Podcast on Apple Podcasts (iTunes):
https://apple.co/2lwqZIr

Podcast on Spotify:
https://spoti.fi/2nEwCF8

Podcast RSS:
https://lexfridman.com/category/ai/feed/

Scott Aaronson is a professor at UT Austin, director of its Quantum Information Center, and previously a professor at MIT. His research interests center around the capabilities and limits of quantum computers and computational complexity theory more generally.

Subscribe to this YouTube channel or connect on:
- Twitter: https://twitter.com/lexfridman
- LinkedIn: https://www.linkedin.com/in/lexfridman
- Facebook: https://www.facebook.com/lexfridman
- Instagram: https://www.instagram.com/lexfridman
- Medium: https://medium.com/@lexfridman
- Support on Patreon: https://www.patreon.com/lexfridman

Google announced with their work in the paper in Nature with quantum supremacy.

Can you describe, again, back to the basic, what is, perhaps not so basic, what is quantum supremacy?

Absolutely, So quantum supremacy is a term that was coined by, again, by John Preskill in 2012.

Not everyone likes the name, you know, but it sort of stuck.

We don't, we sort of haven't found a better alternative.

It's technically quantum computational supremacy.

Yeah, yeah, supremacy, that's right, that's right.

But the basic idea is actually 1 that goes all the way back to the beginnings of quantum computing, when Richard Feynman and David Deutch, people like that, were talking about it in the early 80s.

And quantum supremacy just refers to sort of the point in history when you can first use a quantum computer to do some well-defined task much faster than any known algorithm running on any of the classical computers that are available.

Okay, so, you know, notice that I did not say a useful task.

Okay, you know, it could be something completely artificial, but it's important that the task be well-defined.

So in other words, you know, there is, it is something that has right and wrong answers, you know, and that are knowable independently of this device, right?

And we can then, you know, run the device, see if it gets the right answer or not.

You said much faster than a classical implementation.

What about the space where there's no, doesn't even exist a classical algorithm

So maybe I should clarify, everything that a quantum computer can do, a classical computer can also eventually do, okay?

And the reason why we know that is that a classical computer could always, if it had no limits of time and memory, it could always just store the entire quantum state of the quantum, store a list of all the amplitudes in the state of the quantum computer and then just do some linear algebra to just update that state.

And so anything that quantum computers can do can also be done by classical computers, albeit exponentially slower

So quantum computers don't go to some magical place outside of Alan Turing's definition of computation.

Precisely, they do not solve the halting problem.

They cannot solve anything that is uncomputable in Alan Turing's sense.

What we think they do change is what is efficiently computable.

And since the 1960s, the word efficiently, as well as been a central word in computer science, but it's sort of a code word for something technical, which is basically with polynomial scaling.

That as you get to larger and larger inputs, you would like an algorithm that uses an amount of time that scales only like the size of the input raised to some power and not exponentially with the size of the input, right?

Yeah, So I do hope we get to talk again because 1 of the many topics that there's probably several hours worth of conversation on is complexity, which we probably won't even get a chance to touch today.

So you said the definition of quantum supremacy is basically achieving a place where much faster on a formal, that quantum computer is much faster on a formal, well-defined problem that is or isn't useful.

And I would say that we really want 3 things, right?

We want, first of all, the quantum computer to be much faster, just in the literal sense, of like number of seconds, you know?

Secondly, we want it to be sort of, you know, for a problem where we really believe that a quantum computer has better scaling behavior, right?

So it's not just an incidental, you know, matter of hardware, but it's that, you know, as you went to larger and larger inputs, the classical scaling would be exponential and the scaling for the quantum algorithm would only be polynomial.

And then Thirdly, we want the first thing, the actual observed speedup, to only be explainable in terms of the scaling behavior, right?

So, you know, I want a real problem to get solved, let's say by a quantum computer with 50 qubits or so, and for no 1 to be able to explain that in any way other than, well, you know, this computer involved a quantum state with 2 to the 50th power amplitudes.

And, you know, a classical simulation, at least any that we know today, would require keeping track of 2 to the 50th numbers and this is the reason why it was faster.

So the intuition is that then if you demonstrate on 50 qubits, then once you get to 100 qubits, then it'll be even much more faster.

Yeah, and quantum supremacy does not require error correction, right?

We don't have, you could say, true scalability yet, or true error correction yet, but you could say quantum supremacy is already enough by itself to refute the skeptics who said a quantum computer will never outperform a classical computer for anything.

how do you demonstrate quantum supremacy?

And 2, what's up with these news articles I'm reading that Google did so?

Great, great questions, because now you get into actually a lot of the work that I and my students have been doing for the last decade, which was precisely about how do you demonstrate quantum supremacy using technologies that we thought would be available in the near future.

And so 1 of the main things that we realized around 2011, and this was me and my student, Alex Arkhipov at MIT at the time, and independently of some others, including Bremner, Josa, and Shepard, okay?

And the realization that we came to was that if you just want to prove that a quantum computer is faster, you know, and not do something useful with it, then there are huge advantages to sort of switching your attention from problems like factoring numbers that have a single right answer to what we call sampling problems.

So these are problems where the goal is just to output a sample from some probability distribution, let's say over strings of 50 bits, right?

So there are many, many, many possible valid outputs.

You know, your computer will probably never even produce the same output twice, you know, if it's running as, even, you know, assuming it's running perfectly, okay?

But the key is that some outputs are supposed to be likelier than other ones.

So, sorry, to clarify, is there a set of outputs that are valid and set that are not?

Or is it more that the distribution of a particular kind of output is more, is there's a specific distribution of

Yeah, there's a specific distribution that you're trying to hit, right, or that you're trying to sample from.

Now, there are a lot of questions about this.

Now, how you do it, it turns out that with a quantum computer even with the noisy quantum computers that we have now, that we have today, what you can do is basically just apply a randomly chosen sequence of operations, right?

So we, you know, we, in some of those, you know, we, you know, that part is almost trivial, right?

We just sort of get the qubits to interact in some random way, although a sort of precisely specified random way, so we can repeat the exact same random sequence of interactions again, and get another sample from that same distribution.

And what this does is it basically, well, it creates a lot of garbage, but very specific garbage, right?

So, of all of the, so if we're gonna talk about Google's device, there were 53 qubits there, okay?

And so there were 2 to the 53 power possible outputs.

Now, for some of those outputs, you know, there was a little bit more destructive interference in their amplitude, okay?

So their amplitudes were a little bit smaller.

And for others, there was a little more constructive interference.

You know, the amplitudes were a little bit more aligned with each other.

And so those that were a little bit likelier.

All of the outputs are exponentially unlikely, but some are, let's say, 2 times or 3 times unlikelier than others.

So you can define this sequence of operations that gives rise to this probability distribution.

Okay, now the next question would be, well, how do you, you know, even if you're sampling from it, how do you verify that?

And so my students and I, and also the people at Google were doing the experiment, came up with statistical tests that you can apply to the outputs in order to try to verify, you know, what is, you know, that at least that some hard problem is being solved.

The test that Google ended up using was something that they called the linear cross-entropy benchmark.

Okay, And it's basically, so the drawback of this test is that it requires you to do a 2 to the 53 time calculation with your classical computer.

So it's very expensive to do the test on a classical computer.

Well, you know, you want it in like scientific notation.

it is just- Is it impossible to run on a-

It is just barely possible to run, we think, on the largest supercomputer that currently exists on Earth, which is called Summit at Oak Ridge National Lab.

So ironically, for this type of experiment, we don't want 100 qubits, okay?

Because with 100 qubits, even if it works, we don't know how to verify the results, okay?

So we want a number of qubits that is enough that the biggest classical computers on Earth will have to sweat and will just barely be able to keep up with the quantum computer using much more time, but they will still be able to do it in order that we can verify the result.

Which is where the 53 comes from for the number of qubits.

Basically, well, I mean, that's also, that's sort of, you know, the, I mean, that's sort of where they are now in terms of scaling.

You know, and then, you know, soon, you know, that point will be passed.

And then when you get to larger numbers of qubits, then these types of sampling experiments will no longer be so interesting because we won't even be able to verify the results and we'll have to switch to other types of computation.

So with the sampling thing, you know, so the test that Google applied, where this linear cross entropy benchmark, was basically just take the samples that were generated, which are, you know, a very small subset of all the possible samples that there are.

But for those, you calculate with your classical computer the probabilities that they should have been output.

you see, are those probabilities like larger than the mean?

You know, so is the quantum computer biased toward outputting the strings that it's, you know, that you want it to be biased toward.

Okay, and then finally we come to a very crucial question, which is supposing that it does that, well how do we know that a classical computer could not have quickly done the same thing?

How do we know that this couldn't have been spoofed by a classical computer, right?

And so, well, the first answer is we don't know for sure because this takes us into questions of complexity theory, I mean, questions of the magnitude of the P versus NP question and things like that, right?

We don't know how to rule out definitively that there could be fast classical algorithms for even simulating quantum mechanics and for simulating experiments like these, but we can give some evidence against that possibility.

And that was sort of the main thrust of a lot of the work that my colleagues and I did over the last decade, which is then sort of in around 2015 or so, what led to Google deciding to do this experiment.

So is the kind of evidence you, first of all, the hard P equals NP problem that you mentioned and the kind of evidence that you're, we're looking at, is that something you come to on a sheet of paper or is this something, are these empirical experiments?

I mean, it's also, we have a bunch of methods that are known for simulating quantum circuits or quantum computations with classical computers.

And so we have to try them all out and make sure that they don't work.

Make sure that they have exponential scaling on these problems and not just theoretically, but with the actual range of parameters that are actually arising in Google's experiment.

Okay, so there is an empirical component to it, right?

But now on the theoretical side, basically what we know how to do in theoretical computer science and computational complexity is we don't know how to prove that most of the problems we care about are hard, but we know how to pass the blame to someone else.

We know how to say, well, look, I can't prove that this problem is hard, but if it is easy, then all these other things that you probably were much more confident or were hard, then those would be easy as well.

So we can give what are called reductions.

This has been the basic strategy in NP completeness, right, in all of theoretical computer science and cryptography since the 1970s, really.

And so we were able to give some reduction evidence for the hardness of simulating these sampling experiments, these sampling-based quantum supremacy experiments.

The reduction evidence is not as satisfactory as it should be.

1 of the biggest open problems in this area is to make it better.

Certainly we can say that if there is a fast classical algorithm to spoof these experiments, then it has to be very, very unlike any of the algorithms that we know.

Which is kind of in the same kind of space of reasoning that people say P not equals NP.


Speaker 0: Google announced with their work in the paper in Nature with quantum supremacy. Can you describe, again, back to the basic, what is, perhaps not so basic, what is quantum supremacy?

Speaker 1: Absolutely, So quantum supremacy is a term that was coined by, again, by John Preskill in 2012. Not everyone likes the name, you know, but it sort of stuck. We don't, we sort of haven't found a better alternative.

Speaker 0: It's technically quantum computational supremacy.

Speaker 1: Yeah, yeah, supremacy, that's right, that's right. But the basic idea is actually 1 that goes all the way back to the beginnings of quantum computing, when Richard Feynman and David Deutch, people like that, were talking about it in the early 80s. And quantum supremacy just refers to sort of the point in history when you can first use a quantum computer to do some well-defined task much faster than any known algorithm running on any of the classical computers that are available. Okay, so, you know, notice that I did not say a useful task. Okay, you know, it could be something completely artificial, but it's important that the task be well-defined.

So in other words, you know, there is, it is something that has right and wrong answers, you know, and that are knowable independently of this device, right? And we can then, you know, run the device, see if it gets the right answer or not.

Speaker 0: Can you clarify a small point? You said much faster than a classical implementation. What about the space where there's no, doesn't even exist a classical algorithm

Speaker 1: to solve the problem? So maybe I should clarify, everything that a quantum computer can do, a classical computer can also eventually do, okay? And the reason why we know that is that a classical computer could always, if it had no limits of time and memory, it could always just store the entire quantum state of the quantum, store a list of all the amplitudes in the state of the quantum computer and then just do some linear algebra to just update that state. And so anything that quantum computers can do can also be done by classical computers, albeit exponentially slower

Speaker 0: in some cases. So quantum computers don't go to some magical place outside of Alan Turing's definition of computation.

Speaker 1: Precisely, they do not solve the halting problem. They cannot solve anything that is uncomputable in Alan Turing's sense. What we think they do change is what is efficiently computable. And since the 1960s, the word efficiently, as well as been a central word in computer science, but it's sort of a code word for something technical, which is basically with polynomial scaling. That as you get to larger and larger inputs, you would like an algorithm that uses an amount of time that scales only like the size of the input raised to some power and not exponentially with the size of the input, right?

Speaker 0: Yeah, So I do hope we get to talk again because 1 of the many topics that there's probably several hours worth of conversation on is complexity, which we probably won't even get a chance to touch today. But you briefly mentioned it. But let's maybe try to continue. So you said the definition of quantum supremacy is basically achieving a place where much faster on a formal, that quantum computer is much faster on a formal, well-defined problem that is or isn't useful.

Speaker 1: Yeah, yeah, yeah, right, right. And I would say that we really want 3 things, right? We want, first of all, the quantum computer to be much faster, just in the literal sense, of like number of seconds, you know? It's solving this well-defined problem. Secondly, we want it to be sort of, you know, for a problem where we really believe that a quantum computer has better scaling behavior, right?

So it's not just an incidental, you know, matter of hardware, but it's that, you know, as you went to larger and larger inputs, the classical scaling would be exponential and the scaling for the quantum algorithm would only be polynomial. And then Thirdly, we want the first thing, the actual observed speedup, to only be explainable in terms of the scaling behavior, right? So, you know, I want a real problem to get solved, let's say by a quantum computer with 50 qubits or so, and for no 1 to be able to explain that in any way other than, well, you know, this computer involved a quantum state with 2 to the 50th power amplitudes. And, you know, a classical simulation, at least any that we know today, would require keeping track of 2 to the 50th numbers and this is the reason why it was faster.

Speaker 0: So the intuition is that then if you demonstrate on 50 qubits, then once you get to 100 qubits, then it'll be even much more faster.

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

Speaker 0: how do you demonstrate quantum supremacy? And 2, what's up with these news articles I'm reading that Google did so? What did they actually do?

Speaker 1: Great, great questions, because now you get into actually a lot of the work that I and my students have been doing for the last decade, which was precisely about how do you demonstrate quantum supremacy using technologies that we thought would be available in the near future. And so 1 of the main things that we realized around 2011, and this was me and my student, Alex Arkhipov at MIT at the time, and independently of some others, including Bremner, Josa, and Shepard, okay? And the realization that we came to was that if you just want to prove that a quantum computer is faster, you know, and not do something useful with it, then there are huge advantages to sort of switching your attention from problems like factoring numbers that have a single right answer to what we call sampling problems. So these are problems where the goal is just to output a sample from some probability distribution, let's say over strings of 50 bits, right? So there are many, many, many possible valid outputs.

You know, your computer will probably never even produce the same output twice, you know, if it's running as, even, you know, assuming it's running perfectly, okay? But the key is that some outputs are supposed to be likelier than other ones.

Speaker 0: So, yeah. So, sorry, to clarify, is there a set of outputs that are valid and set that are not? Or is it more that the distribution of a particular kind of output is more, is there's a specific distribution of

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

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

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

All of the outputs are exponentially unlikely, but some are, let's say, 2 times or 3 times unlikelier than others. So you can define this sequence of operations that gives rise to this probability distribution. Okay, now the next question would be, well, how do you, you know, even if you're sampling from it, how do you verify that? How do you know? And so my students and I, and also the people at Google were doing the experiment, came up with statistical tests that you can apply to the outputs in order to try to verify, you know, what is, you know, that at least that some hard problem is being solved.

The test that Google ended up using was something that they called the linear cross-entropy benchmark. Okay, And it's basically, so the drawback of this test is that it requires you to do a 2 to the 53 time calculation with your classical computer. So it's very expensive to do the test on a classical computer. The good news is-

Speaker 0: How big of a number is 250? It's about 9 quadrillion. Okay. That doesn't help.

Speaker 1: Well, you know, you want it in like scientific notation.

Speaker 0: No, no, no, what I mean

Speaker 1: is- Yeah,

Speaker 0: it is just- Is it impossible to run on a-

Speaker 1: Yeah, so we will come back to that. It is just barely possible to run, we think, on the largest supercomputer that currently exists on Earth, which is called Summit at Oak Ridge National Lab. Okay?

Speaker 0: Great, this is exciting.

Speaker 1: That's the short answer. So ironically, for this type of experiment, we don't want 100 qubits, okay? Because with 100 qubits, even if it works, we don't know how to verify the results, okay? So we want a number of qubits that is enough that the biggest classical computers on Earth will have to sweat and will just barely be able to keep up with the quantum computer using much more time, but they will still be able to do it in order that we can verify the result.

Speaker 0: Which is where the 53 comes from for the number of qubits.

Speaker 1: Basically, well, I mean, that's also, that's sort of, you know, the, I mean, that's sort of where they are now in terms of scaling. You know, and then, you know, soon, you know, that point will be passed. And then when you get to larger numbers of qubits, then these types of sampling experiments will no longer be so interesting because we won't even be able to verify the results and we'll have to switch to other types of computation. So with the sampling thing, you know, so the test that Google applied, where this linear cross entropy benchmark, was basically just take the samples that were generated, which are, you know, a very small subset of all the possible samples that there are. But for those, you calculate with your classical computer the probabilities that they should have been output.

Speaker 0: And

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

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

Speaker 0: So is the kind of evidence you, first of all, the hard P equals NP problem that you mentioned and the kind of evidence that you're, we're looking at, is that something you come to on a sheet of paper or is this something, are these empirical experiments?

Speaker 1: It's math for the most part. I mean, it's also, we have a bunch of methods that are known for simulating quantum circuits or quantum computations with classical computers. And so we have to try them all out and make sure that they don't work. Make sure that they have exponential scaling on these problems and not just theoretically, but with the actual range of parameters that are actually arising in Google's experiment. Okay, so there is an empirical component to it, right?

But now on the theoretical side, basically what we know how to do in theoretical computer science and computational complexity is we don't know how to prove that most of the problems we care about are hard, but we know how to pass the blame to someone else. We know how to say, well, look, I can't prove that this problem is hard, but if it is easy, then all these other things that you probably were much more confident or were hard, then those would be easy as well. So we can give what are called reductions. This has been the basic strategy in NP completeness, right, in all of theoretical computer science and cryptography since the 1970s, really. And so we were able to give some reduction evidence for the hardness of simulating these sampling experiments, these sampling-based quantum supremacy experiments.

The reduction evidence is not as satisfactory as it should be. 1 of the biggest open problems in this area is to make it better. But we can do something. Certainly we can say that if there is a fast classical algorithm to spoof these experiments, then it has to be very, very unlike any of the algorithms that we know.

Speaker 0: Which is kind of in the same kind of space of reasoning that people say P not equals NP.

Speaker 1: Yeah, it's in the same spirit.

See all Lex Fridman transcripts on Youtube

Scott Aaronson: Quantum Supremacy | AI Podcast Clips