Master of (Computer) Science

All right, everybody. Welcome to Cloudflare TV, session number three of Master of Computer Science.

And I'm really, really glad to have Professor Scott Aaronson here from the University of Texas.

Scott, you're an expert in a number of areas in computer science.

Maybe you can share a little bit with the audience about what your expertise is and what it is that you're studying right now.

Okay, well, I mean, my main interest for the last 20 years or so has been the theory of quantum computation.

So quantum computer is the first proposal that we've had for a type of computation that would really go, you know, fundamentally beyond the Turing machine, you know, beyond the sort of theoretical model that governs, you know, all of the computers in the world today.

And you know, people talk about parallel computers, biological computers, optical computers.

In some sense, all of these are Turing machines, you know, all of these operate on the same rules.

A quantum computer is something different.

It, we think that it could solve problems efficiently, meaning like with linear scaling or, you know, quadratic scaling or something like that, that would require exponential scaling for any existing computer.

And it would do that by exploiting you know, the laws of quantum mechanics in a very fundamental way.

So, you know, my main interests have been, you know, how does quantum mechanics change the theory of computation?

How does it not change it?

You know, so what is, what is, like, for example, what problems are still hard, even in a world with quantum computers?

How does quantum mechanics change cryptography?

In particular, I've been very interested in possibilities like quantum money that would be physically impossible to counterfeit or intractable to counterfeit, copy protected quantum software.

I've been interested in how do you learn a quantum state?

How do you reconstruct it from the results of a small numbers of measurements?

And I've been interested in, you know, the theoretical foundations for how do you do an experiment that proves that a quantum computer can do something that exceeds what we can do with, you know, today's computers.

This was a goal called quantum supremacy, which, as some people might have heard, was just achieved by Google this past fall.

And a lot of what I and my students did over the last decade was to try to establish the theoretical foundations for that kind of experiment.

And, you know, I'm interested in, you know, what can quantum computation tell us about physics?

Can it feed back? Can it give us new insights about quantum gravity, about the black hole information problem?

You know, I'm not a physicist. I'm a computer scientist, but recently a lot of physicists have gotten, you know, even like string theorists and other, you know, theoretical physicists got super excited about quantum computing because of what they could tell them.

And I've sort of tried to have the computer science consultant anymore.

It looks like the image froze. Oh, I can't hear you.

Yeah, I lost you for a second there, Scott. I don't know if it's on your end or mine.

But, um, yeah, the last thing that you, what was the last thing that you just shared?

Oh, all right. Well, the last thing that I talked about was that there is a very, you know, recent connection where people have tried to use insights from quantum computing to try to learn something about the black hole information problem, about quantum gravity.

And so I've tried to help those people out as a sort of computer science consultant to, you know, the, to the physicists.

Okay, so yeah, this, this is a broad array of different projects being tackled in the, in the space of quantum computers.

When was a, when was a quantum computer first devised or first thought of?

What's the history of quantum computing? Yeah, so I would say that the idea of a quantum computer first emerged in the early 1980s.

And, you know, there were two physicists, Richard Feynman and David Deutsch, who are commonly credited with, you know, bringing the idea to most people's attention.

So, you know, it had been known for generations before that, that quantum mechanics, you know, which has been the framework for essentially all of physics since the 1920s, right, it has this kind of exponential character at the core of it, right?

The, the central thing that quantum mechanics says about the world is that if, you know, there are a bunch of different ways that something could happen, well then, in some sense, nature keeps track of all of them.

Right? Every possible way that something could happen, it assigns a complex number called an amplitude.

Okay, and, you know, amplitudes are a little bit like probabilities, but they're different.

For one thing, they can be negative numbers, or, you know, they can even be complex numbers, as I said, and to, to, if you want to know how likely it is that something will happen, like, for example, that a photon will hit a certain spot on a screen, or that a, you know, a radioactive nucleus will decay or something, well, you know, you have to add up the amplitudes for all of the possible ways that that thing could happen.

Okay, even if there are exponentially many of them.

And then you take the squared absolute value of the result that tells you the probability.

Okay, so, but the, the implication of this, and this was recognized from very early on, from the 1920s, even, is that if I have a collection of particles, doesn't have to be that many, maybe even like a thousand particles, and if each particle could store one bit of information, say, for example, in its spin state, you know, whether it's spinning up or spinning down, there's just some property, well, then I have to, to, you know, if those particles can interact with each other, then to write down the combined state of all of them, I actually need a list of 2 to the 1000th power amplitude.

Okay, I need an amplitude for every possible configuration of all thousands of particles.

Okay, so, you know, that is far more parameters than you could write down in the entire observable universe.

Okay, but, you know, quantum mechanics says that they are implicitly there, you know, in the state of that system, right.

And, you know, all of them could, in principle, enter in, you know, calculating the probability for the measurement results that you see when you look.

So, chemists and physicists knew that for generations.

They knew it mostly as a practical problem, right. They knew it as if you're trying to stimulate quantum mechanics on a conventional computer, then the difficulty of the simulation, you know, doubles or more with each new particle that you add.

So that, you know, simulating, for example, all but the very simplest chemical reactions, you know, can become intractable, even for the largest supercomputers that we have.

You know, if you look at what supercomputing cycles are used for today, you know, a good fraction of it is just trying to simulate quantum mechanics.

Right, trying to solve the Schrodinger equation, which, you know, is this very, very hard problem because of that exponentiality.

But what happened in the early 80s was that Deutsch and Feynman and a few others said, well, if nature is giving us this computational lemon, you know, why don't we turn it into lemonade, right.

Why don't we, you know, build machines that themselves would have an exponential number of amplitudes, you know, that could do computations by you know, using these, you know, enormous vectors of amplitudes and you know, that themselves would be able to take advantage of this, you know, phenomena of, you know, entanglement, you know, this sort of, you know, exponential growth and the size of the state and this interference of positive and negative amplitudes can cancel each other out and so forth.

Now, of course, they faced the question, well, supposing that you had this quantum computer, what would it be good for?

At the time, they only really had one answer to that question, which is, it would be good for simulating quantum mechanics.

Now, I think that that actually remains the commercially most important application of quantum computing that anyone has thought of.

But, you know, for more than a decade, it sort of just remained an idea that a few oddballs, you know, thought about.

What really started quantum computing as a field was a couple of developments in the 1990s.

One of them was the spectacular discovery that you could actually use a quantum computer to solve certain classical problems much faster than a Can you hear me?

Yeah, I can hear you.

Okay, okay, that you could solve certain classical problems much faster than a classical computer could solve the same problems.

The most famous example is finding the prime factors of enormous numbers.

I think we might be having some video issues here, Scott.

Not sure exactly how to resolve that.

Which, you know, All right, um, yeah, it's a shame that there's a problem with the Internet connection.

Um, can you, can you see me now? Yeah, I can see you and hear you.

So the All right. All right. All right. Well, why don't, why don't I just continue then.

Yeah, please. So, so, okay, so, so, so, so some remarkable quantum algorithms were, you know, discovered in the 1990s that said, you know, you could actually use this bizarre effect that nature gives you this interference of amplitudes To solve certain purely classical problems faster than a classical computer could solve them.

And that spurred people to think about, well, what would it take to actually build a quantum computer?

And there were a lot of people who said, well, it's a neat idea, but it could never ever happen in real life.

Because you will never be able to get qubits well, you know, or quantum bits well enough isolated from their environment that you could actually compute with them, right, they're just going to be too fragile.

Then, you know, another huge discovery in the 90s was the theory of quantum error correction, which, you know, In principle addresses this worry, right, says that, you know, this is merely an unbelievably hard engineering problem, but, you know, it should not present any new problem of physics.

You know, if quantum mechanics works the way that we think it does, then it ultimately it ought to be possible to protect quantum bits, you know, using clever error correcting codes.

And so that really set the agenda for the rest of the field, you know, figure out what else you can do with a quantum computer that's interesting or exciting.

And then get qubits well enough controlled that you can start doing start applying these error correcting codes.

And in that way, build a quantum computer that would actually scale to, you know, millions of qubits or as many qubits as you need it to actually solve hard problems.

I joined the field in about 1999, you know, after these basic foundations were established, you know, and there's been a lot that's happened since then.

But I think it's all of it as a built on that foundation. That's fascinating.

So how did the leap, the mental leap happen to go from thinking about quantum computers as something that can solve These physical problems in quantum modeling to something as obscure and different as discrete mathematics.

Yeah, that's a great question.

You know, there was a sequence of discoveries that preceded that right Where, you know, initially, David Deutsch, you know, the, the, the, the part when in when he wrote one of the first papers about quantum computing and the mid 1980s.

You know, the example that he gave for where quantum computer could do something faster.

Was that it could compute the exclusive or of two bits and then in one step instead of, you know, with only one look up if you like, instead of two look ups by querying both of the bits and superposition Okay, or, you know, having some amplitude to query each of the two bits.

Most people did not regard that as a very impressive example, right, you know, getting exclusive or is not such a hard problem that we, you know, we need that speed up for it.

But, you know, he was just trying to prove a point and what what happened in the early 1990s was that some computer scientists started looking at this field, in particular, my, my former PhD advisor mesh buzzer Ronnie.

Who's a professor at Berkeley.

And, you know, he was, he said, you know, he was just looking around for some, you know, he had gotten bored with his other work, you know, and he had studied some physics.

And he got really fascinated by the idea of quantum computing and he said, but, you know, these physicists who are talking about it, you know, they are not sort of Maybe asking the questions that we would ask as computer scientists, right, like, what is the class of problems that is solvable in polynomial time using a quantum computer, right.

You know, is that a mathematically sensible class is it well defined.

Is it robust. How does it fit in with the classical Complexity classes, the classes of problems that every computer science major learns about like a and NP and P space.

Right. So they had a Famous paper in 1993 where they defined a quantum version of polynomial time.

Okay, we would call the class BQP bounded error quantum polynomial time.

It's basically like the class of all of the yes or yes or no problems that are efficiently solvable by a quantum computer right and they prove, you know, the basic facts about it like it contains classical day, you know, so anything that a classical computer A quantum computer can simulate and Oracle evidence that wasn't completely satisfying, but it was a first step and then You can still hear me.

I can hear you.

Yeah. That caused another Guy.

Simon to look into it, who is actually like a cryptography going to get a speed up that's going to failing to prove it and he's Eventually analyzing his failures led to the discovery of another famous algorithm, which was called Simon's algorithm.

Okay, which is for finding a certain hidden structure in a in a function, a sort of hidden periodic structure and hidden periodicity in it.

So it was a problem with a kind of cryptographic flavor and he showed that, you know, for this black box problem, a classical algorithm would need exponential time to solve it, but a quantum algorithm could solve it in polynomial time.

Okay. And that was the first such example.

And I think that is A For this was actually rejected from people said, you know, this is just a completely contrived problem.

What does it really matter.

But there was one guy, a guy who really, really liked this paper, whose name was Peter shore.

Okay. And he was Someone, you know, who knew quantum mechanics, you know, he knew he knew a lot of classical number theory and classical computer science and he said, well, obviously, if you just Made you know if you could just adapt Simon's algorithm to work for a slightly different problem like finding a period of a periodic function over the integers, then You know, for reasons related to the four year transform, you know, a period finding should let you do things in number theory like factory, you know, that was not obvious to most people, but, you know, There was one guy who I guess knew the right combination of things and he worked on it for about a year to, you know, work out all the details of it.

And that was short factoring algorithm. So how far has the categorization of algorithms gone.

How much do we know about where the what is it the bounded error quantum polynomial.

Yes. Problems. Yeah, yeah. So, so, okay. So let me tell you some of what we know.

So we know that Anything that is in BQP is also can be done by a classical computer with a polynomial amount of memory.

So it's in this class called P space.

Okay, P space and turn is in x, which is anything you can do with a classical computer in an exponential amount of time.

So, so what this means is that, you know, quantum computers are not going to solve the whole thing problem right they can't do anything that's literally undecidable, they can at most get an exponential speed up over classical computers.

And furthermore, in the current state of theoretical computer science, we sort of, we have no hope of proving unconditionally That quantum computers will get an exponential advantage for a real world problem.

And the reason for that is that for Half a century.

No one has even been able to prove that P is not equal to piece. Right. You know, that's very, very closely related to the versus NP problem.

And, you know, now and now BQP is sandwiched in between the NP space.

Right. So if you wanted to prove Unconditionally that BQP is larger than a well, you'd also have to separate the from the space, you know, and that would be that would require a revolution in mathematics, you know, which is not to say that it will never happen.

You know, I hope that it will.

But, but those are the stakes. Right. And so the, so the You know, if we, if we want to sort of get evidence that quantum computers can actually do things better.

Well, there are two things we can do. We can work in this black box model, which I've been talking about before, where you only count like the number of accesses that are made to some Function some sub routine some black box, you know, in that setting, we actually can prove that quantum computers get exponential advantages.

For certain problems like, for example, for finding a period of a periodic function, which is the heart of short algorithm.

Okay. You know, the other thing we can do is we can say, well, look, you know, here is a fast quantum algorithm for factoring numbers and, you know, if You know, if you think that quantum computers, they'll get any advantage over classical one.

Well, then there must also be a fast classical algorithm for factoring numbers, which we know what is that out.

So what, so what is that algorithm and, you know, The burden of proof to the person who thinks that there's no quantum advantage.

So, you know, now, now some, you know, what, one of the biggest questions of the field is, you know, what is the relationship between BQP and NDP You know NP being the class of all the problems where you can easily check a solution that even though the solution might be very, very hard to find.

So, you know, the famous traveling salesman problem, you know, coloring a map packing boxes that they fit in the trunk of your car.

Mind sweeper, you know, these are all examples of NP complete problems and, you know, which are among the hardest problems in NP.

Okay. And You know, of course, the famous P versus NP question asks whether any of these NP complete problems or equivalently whether all of them can be solved efficiently by a classical computer And, you know, when, when quantum computing first came along.

A lot of people had the idea.

Well, maybe this will crack the NP complete problem right maybe this will, you know, if this is redrawing the boundary of what's computable and polynomial time.

Well, then, you know, why shouldn't it give us the NP complete problem right which would be Completely revolutionary.

And, you know, unfortunately, if you read most popular articles about quantum computing, even to this day.

Even, you know, 25 years after this stuff was understood, you know, they will still give you the impression that quantum computers would solve NP complete problems.

Just by trying all the possible answers in parallel, you know, or something like that.

And that this is why people are excited about them. Unfortunately, you know, it's a lot more subtle than that.

What we think Is that quantum computers would give some advantage for NP complete problems, but the kind of advantage we think that we could get is A polynomial advantage.

It's roughly solving the NP complete problem in about the square root of the number of steps that you would have needed classically So, for example, instead of two to the 100 steps, you might nearly, you might nearly need two to the 50 steps.

Okay, so You know, it's still a lot.

But, you know, it, you know, you know, this is Relying on maybe the second most famous quantum algorithm after Shor's algorithm, something called Grover's algorithm.

Or basically searching a list of n possibilities and about the square root of n steps.

And so, so that has a very, very broad applicability, but it doesn't turn an exponential problem into a polynomial problem.

Right. So today, most of us would conjecture that The NP complete problems are not in BQP.

Okay. Can we prove that. Well, of course, we can't prove it because we can't even prove that the NP complete problems are not in P.

Right, which would be a prerequisite to that.

Okay. But, you know, in the same way that many of us believe that P is not equal to NP.

So today, many of us. Believe that NP is not in BQP, that it's only certain special, you know, classically hard problems, you know, factoring being a preeminent example that are going to be in BQP.

Okay. And, you know, there is much, much more to say and much, much more that's been studied about the relationship between BQP and all sorts of classical, you know, Computational complexity classes such as the polynomial hierarchy, you know, in fact, there was a recent breakthrough about the relationship between BQP and the polynomial hierarchy.

And all sorts of other classes, but that that's that's sort of a from 30,000 feet.

That's a picture of what we know and what we believe Okay, so if, if you were to talk to someone who's, you know, read a pop science sort of article about quantum computing and think, wow, you can do all of these computations in parallel.

Why would you be able to solve these hard problem. Now, how do you explain, how do you sort of Give it good.

That's it. That's it. That's an excellent question.

You know, like I couldn't have planted a better one. So, You know, the, the, the issue is this, you know, like, let's say that we have some NP complete problem, you know, involving some astronomical number of different tours that a salesman could take, you know, to visit a bunch of cities or, you know, a bunch of Variables that we could set where we're trying to satisfy a bunch of constraints, you know, as in, you know, satisfiability.

You know, now it's a very natural thought.

Well, why don't we just create a quantum superposition over all the possible answers.

Right. So give every possible answer a certain amplitude. And you can do that.

Not only can you do it. It's a very easy thing to do with a quantum computer make a superposition over exponentially many different answers.

The trouble is that for a computer to be useful.

Well, at some point, you've got to look at it and you've got to read an answer out Right.

And if you just took this equal superposition over all the different answers and you just measured the quantum state.

Not having done anything else to it, then the rules of quantum mechanics tell you that what you're going to see will just be a random answer.

Okay. Well, now, if you just wanted a random guess for the answer. You could have just picked one yourself by flipping a coin, a bunch of times.

Right. You didn't even, you know, you could you could have saved all of the however many billions of dollars it took to build this quantum computer.

Okay, so the only hope of getting a speed up.

With a quantum computer compared to what you could have done with a classical computer.

Is to exploit the way that the amplitudes work differently from classical probabilities.

Right. So you have to exploit somehow the fact that amplitudes are complex numbers, right, or, you know, For example, that they could be positive or negative.

Okay, that is kind of the defining difference of quantum mechanics.

And how do you exploit that. Well, sort of the central effect in quantum mechanics is what we call interference.

Hey, this is where You have a certain outcome.

Like, let's say a certain possible output of your computer. And some of the paths leading to that output at a positive amplitude and other paths leading there had a negative amplitude.

And so those amplitudes cancel each other out.

They interfere destructively. Okay, so that the total amplitude is zero.

So now the The game sort of with every quantum algorithm is to try to choreograph a pattern of interference.

So that for each wrong answer each answer that you don't want to see there is destructive interference right the paths leading to that wrong answer.

Are, you know, pointing every which way, you know, in the complex plane, let's say, or some are positive and some are negative.

And, you know, they so they Mostly are entirely cancel each other out. Whereas for the right answer.

The answer you want to see you would like all the different contributions to its amplitude to be pointing the same way.

To be all in phase with one another.

Okay. And then you get what we call constructive interference on the right answer.

Okay, if you can do that, then when you look, you will see the right answer with a high probability.

Okay, so Now the hard part is you have to choreograph this pattern, even though you don't know yourself in advance which answer is the right one.

Right. If you knew that, then there would have been no point in doing the quantum computation.

Okay. And it's really only for a few very special problems, you know, like period finding and hence factoring that people have figured out how to do that.

Right. You know, how do you create this gargantuan interference pattern among, you know, an exponential number of different paths.

Where, you know, you can just mathematically guarantee that, you know, at the end of the the battle, you know, and all the dust is settled, you'll have All you know all of the the amplitude concentrating just on the answer that you want, like the period of your periodic Function right you know that takes, you know, some some insight to do right.

It's not just a simple matter of Try all the answers in parallel and then the right one can wave to all the other ones and say, hey, everyone over here.

I found it. Right, you know, it's not that simple sort of all of the paths have to collaborate somehow in this creating this interference pattern.

And, you know, in the case of Shor's algorithm that work by doing a four year transform right the four year transform for those who studied a signal processing or electrical engineering or anything like that is all about switching from a time domain to a frequency domain.

Right. So it's all about Taking a periodic, you know, taking periodic data and then doing a linear transformation on it that somehow extracts the period from the data.

Right, which is exactly what Shor needed.

And that is a linear transformation, the sort that you could program.

Well, should you know one had to show this but Shor showed how you could program a quantum computer to do that transformation to your gigantic list of amplitudes and and furthermore, do it efficiently.

Right, that's also key. Do it in time that only scales like the number of qubits or like, you know, the square of the number of qubits or something like that.

And it does not scale like the number of amplitudes, which is an exponentially greater number.

Okay, so Yeah, it's Yeah, yeah.

So, you know, I like to say, you know, if it was just as simple as just trying every possible answer in parallel.

Well, then, you know, you wouldn't have needed Shor to think of it.

Right, right. Yeah, you have to get everything to work together.

Otherwise, you're just going to Yeah, yeah, yeah. But, but, but the other thing is, you know, this is You know, I like to say that this is weird enough that like no I don't think any science fiction writer would have had the imagination to invent this Right.

And so, you know, when I first learned about it.

Right. You know, I felt like, you know, this is this is this is almost, you know, weird enough that maybe it has to be true.

And, you know, this is, you know, if someone was just making it up and they would have said you get to try all the answers in parallel or something like that.

Right. Yeah. Okay. So you had mentioned at the beginning, some of the interesting current research topics that you're going into.

But yeah, before we get into that. Maybe it would be interesting for the audience to learn how you got started and how you got interested in the space and Where, yeah, yeah.

So, um, I guess I was A Teenager, you know, in the Bit to late 90s, you know, I, I think I read a popular article about shores algorithm.

And, you know, my first reaction was indeed, you know, this sounds like garbage.

Right. This sounds like some physicists who just do not understand the enormity of what they're going up against right the You know, the church touring thesis, the extended church touring thesis that, you know, whatever physics is doing, you ought to be able to simulate it with a classical computer, you know, you know, by some, you know, You know, the efficiently right or, you know, the, you know, I mean, I guess I thought that the universe, you know, was probably some sort of gigantic video game, you know, like a giant cellular automaton or something like that.

Yeah, yeah.

And, and, you know, if you if You know, I mean, I mean, I mean, what, what, what, what, once I had learned what programming was that just seemed like the natural thing to believe You know, it was a very convenient belief for me because if true, it meant that I wouldn't have to know much about physics.

Okay. It's like A, you know, the, the, you know, all the laws of physics, which is the kind of like machine language, you know, implementation details, if you like.

Right. And, you know, really, all that's going on is some kind of computation.

Okay. But, you know, now this quantum computing was coming along and it was saying no physics actually matters for even just for determining what kind of computation, you know, nature is At the at the most, you know, fundamental level.

And, you know, that was a staggering claim, you know, and I think my first reaction was This, this couldn't possibly be true.

And, but, but, you know, I read about it. I think I did a I was lucky enough to do a summer internship at Bell Labs.

You know, just doing some software development that had nothing to do with quantum computing, but my boss.

Was a nice enough to say, hey, you know, you're interested in quantum computing just, you know, spend a month, you know, reading about it and And I did that, you know, and, you know, there were, I mean, I mean, the, the, the, the web itself was Was was not that old by then, but there were already websites explaining shores algorithm and Grover's algorithm and You know, and I read the papers about it.

And, you know, I realized, well, you know, the this quantum mechanics is a real thing, you know, the, you know, the physicists, you know, discovered something of a comparable enormity to the church touring uses and You know, and and and you know when when you read a popular account of quantum mechanics, you know, it You know, it often doesn't make sense.

People say things like, oh, you know, the electron is sort of orbiting the nucleus, but sort of not because it's sort of a smear of probability wave and you say, well, why isn't that just a fancy way of saying that, you know, you don't know where the electron is right But, you know, as soon as you read the, you know, what, what happened with quantum computing was that people put the The sort of the mathematical foundation of quantum mechanics and started having to explain it to computer scientists.

Right, which meant, you know, stripping away most of the complication and just saying, look, what's really going on is that we replace probabilities by these complex numbers, these amplitudes.

Okay. But after that, that, that one, you know, Profound change that we may then it's all just linear algebra because multiplying vectors and matrices.

And it's like, hey, you know, I'm, you know, I, I, I haven't studied, you know, much physics, but I know how to multiply vectors and matrices, you know, maybe I could learn this.

And so, you know, so it turns out to be a lot more approachable than I imagined that it would be.

And then I discovered that while Grover. Who was the discoverer of Grover's algorithm, just a couple of years before that worked in the same building.

As me at Bell Labs.

So I went and talked to him and I had ideas for improving Grover's algorithm that were complete nonsense that didn't work.

But Lav was nice enough to offer that I could come back the next summer and work with him.

And so I did that and and and then there were a bunch of other students working with Lav, including A student from from Berkeley, a student of Umesh Vazirani, which was the sort of a group that was sort of the center of the world at that time and developing quantum computing theory.

So I found out what was going on there and I, you know, I didn't, I didn't know if, you know, I could actually do anything new in this area, but I spent that whole summer with Grover Grover trying to solve a problem that had to do with what advantage could a quantum computer get over a classical one for searching game trees like for playing games, let's say like chess or go, for example, and You know, I was trying to show that the quantum advantage could be at most the square root could be at most the advantage of Grover's algorithm.

And I didn't manage to prove that. But then the fall afterwards, another of the students from Berkeley named Andres Ambayanis did solve that problem by inventing a whole new method and I learned about it.

You know, through, you know, a contact that I had made at Bell Labs and I read Ambayanis's paper and it just bowled me over and I said, I have to go to Berkeley for graduate school.

I have to learn what these people know and You know, so I was lucky enough to get admitted to Berkeley for grad school.

I was an undergrad at Cornell by this time, but I You know, and at Cornell at that time there was really no one doing quantum computing, but, you know, there were people doing AI.

I was also very interested in AI and machine learning, which, you know, I guess ended up being a pretty big deal as well.

But Yeah, it was actually the machine learning people who Were the ones who admitted me to Berkeley.

And so I went there and I did machine learning for a year.

With with with Mike Jordan, actually, but my heart was sort of still in quantum computing and after a year I fell in with with Vazirani's gang and I guess You know, I, I think about, you know, I, you know, I also do some classical computer science, but, you know, quantum computing has remained sufficiently interesting for the last 20 years or, you know, it just kept throwing up enough new stuff that I just, you know, keep keep coming back for more.

So since then quantum computers themselves have developed in terms of being built and being, yes, yes.

How closely. Have you been involved in in washing the development of real quantum computers.

Yeah, well, I mean, I mean, of course I watch it, you know, and it's been tremendously exciting to see the the progress that there's been You know, so, you know, when I when I joined the field, you know, I would say that the experimentalists were, you know, working, you know, we're trying to get one or two cubits at a time to work, you know, more or less, and You know, and meanwhile, the theorists were sort of off in this, you know, completely different world talking about, you know what you could or couldn't do with, you know, arbitrary numbers of cubits right and And and so, so there wasn't, you know, like what we could appreciate each other, you know, we sort of, we, you know, we knew that, you know, we needed each other in some sense, but there wasn't all that much for us to talk about intellectually.

Right. You know, they were sort of the theory and experiment were kind of two separate worlds and in the 20 years since I've been in this field, you know, I've It's been incredibly gratifying to see them come together a lot more Because, you know, now the experimentalists can integrate You know 50 cubits, you know, numbers like that for special purposes, even hundreds of cubits, you know, into one platform.

Have a programmable device where they, you know, can specify what they want to do with those cubits.

Now it is it is still not good enough to get to The threshold of quantum error correction like right we're not there yet in terms of being able to scale to arbitrary numbers of cubits and You know, making them as reliable as needed.

But, you know, just this fall, we did get to the threshold of quantum supremacy.

Okay, you know, doing some artificial task with, you know, in that case of 53 cubit device that was built by Google that, you know, as far, you know, and wherever that was done in a few minutes using the The superconducting quantum chip, where, as far as we know, it would take at least a few days to simulate the same thing using a state of the art supercomputer, even with, you know, tens of thousands, of course.

Okay, so So, so, you know, as the hardware got to the point where this, you know, looked like a serious prospect, then, you know, the experimentalists started reaching out to theorists.

And started saying, well, you know, look, we're going to have these devices.

What do we do with them. That is interesting.

Right. What do we do with them that you are confident would actually be achieving a speed up over a classical computer.

Right. And, you know, once we do it.

How do we prove that we did it. Right. And, you know, so, you know, this. So this became, you know, sort of an obvious item on on on our agenda and, you know, so With a student, a student, a student of mine named Alex Arkhipov and I in 2011 wrote a paper about something called Boson sampling, which was an idea for How to solve a hard sampling problem using an optical quantum computer, one that we just generate photons and send them through a network of beam splitters and things like that and You know, Boson sampling did not end up being how you know Google achieve quantum supremacy.

Right, but You know, but, but it was pursued by a bunch of experimentalists, you know, quantum optics people that was, I would say, was the first thing that really brought me into close contact with the experimentalists.

Right, because, you know, the, I mean, I mean, we, we started thinking about those on sampling mostly from a theoretical point of view.

Right. We were just, you know, for complexity theory reasons, but then, you know, we met quantum optics people who said, well, you know, this sounds a lot like what we can do in our lab.

Right. You know, not with 100 photons as might be needed to get a speed up over a classical computer, but, you know, maybe with five photons, maybe with 10 photons.

Right.

And so So, so then, you know, we started talking to them and they started doing the first Boson sampling experiments, you know, the record by now I think is 14 photons.

Right. At that time they were doing it with three photons. Right.

And So, you know, and but it was clear, you know, already then that, you know, if you could scale this up to 50 or 100 photons.

Then this might be a route by which you could demonstrate that you could outperform a classical computer at some, you know, well defined task right with some programmable device.

And basically what happened then was that in 2014 or 2015 so john Martinez, who was maybe the world leader in building experimental, you know, in actually building superconducting qubit superconducting quantum computers was hired by Google and You know, to build a new lab in Santa Barbara and they looked around and said, you know, what, what can we do that will demonstrate quantum supremacy.

And they basically said, well, we want to do something like those on sampling, except with superconducting qubits.

And so I actually started a whole email thread with them. And, you know, I think 20 2015 or so that was about, you know, what, what would be the easiest way to demonstrate quantum supremacy.

You know, with superconducting qubits with some, you know, some kind of sampling experiment and we we sort of You know, figured out, you know, you know that, you know, we should decision that they should just do what was the most natural for their hardware.

And then we the theorists would have the job of adapting the theory that that, you know, to the capabilities of their hardware.

Right, rather than them, you know, spending $100 million, let's say to adapt their hardware to where the theory was right you know theory is just cheaper.

And so, you know, so then that became our task to sort of, you know, establish the theoretical foundations for what by then we knew what the type of experiment that Google was going to do And, you know, we didn't know how long it was going to take, you know, but you know it they they managed to actually get a very nice result within four or five years.

So what was the results. What was the heart.

Well, okay, good. So, so, so the result was that they they solved a sampling task.

Okay. So what does this mean So they have a chip. They call it sycamore that has 53 superconducting qubits on it.

Why 53 while they built 54 and one of them didn't work.

Okay. But, you know, they are laid out in a rectangular array, you know, each qubit can talk to its neighbors in the array.

So it can sort of become entangled with its neighbors.

You know, you know, interact with them and, you know, and the pattern of interactions is completely programmable.

Okay, so you have a Classic classical electronics that are outside of the chip that are, you know, going into it telling which qubit to, you know, engage in which interaction with which of its neighboring qubits wet.

Okay. And the, the, the chip itself in order for it to superconduct.

So in order for you to see the quantum behavior in the first place for these Little superconducting coils to behave as qubits be in superpositions of zero and one states, you have to cool it to very close to absolute zero.

Okay, so you put it in this dilution refrigerator. Looks like a kind of upside down wedding cake, you know, that's maybe the size of a closet.

Okay. And it cools it to about 10 millikelvin about 100th of a degree above absolute zero.

Okay, that's not as cold as we would like. But, you know, that's about as cold as you get with a commercially available, you know, dilution fridge and And, and, and then what what operations do they do, you know, so this is, you know, so, so, so these qubits are very noisy, but they can maintain their quantum state for a few 10s of microseconds.

Okay, few, you know, 10s of millions of a second. And the good news is that you can do operations on the qubits much faster than that.

So you can actually do about maybe about 20 layers of operations. Well, you know, while the qubits are still preserving their superposition nature before they've leaked their state out into the environment.

Okay, so what do we do? Well, we're just trying to scramble things up as fast as possible in order to, you know, evade the ability for a classical computer to simulate what is happening.

Okay, we're not, we're not yet trying to do anything useful.

Okay, so we basically just do 20 layers of randomly chosen operations.

Okay, but we remember exactly which randomly chosen operations they were.

Okay. And then we measure each of the qubits.

So we ask each of the 53 qubits. Are you a zero or a one. And that collapses their state.

So now we just see a string of 53 bits, right, a 53 bit string.

Okay, now every time you run the same experiment, it's going to be a different 53 bit string.

Right, because all you're doing is you're sampling from some probability distribution over the possible string.

You know, where the probability of each string is determined by its quantum mechanical amplitude.

Okay, but now what's crucial here is that this is not the uniform distribution, which means not all the strings are equally likely.

Okay, they're all exponentially unlikely.

You know, you'll probably never see the same one twice, but some of them are a little bit likelier than others, like twice as likely, three times as likely.

They have little bumps and wiggles like that. And why? Well, because the interference on all of the amplitudes occurs a little bit more perfectly for some of the outcomes than it does for others, right.

For, you know, each final amplitude is a sum of a whole bunch of contributions that you could think of as random and they cancel each other out a little bit more perfectly, you know, for some of the output strings than they do for other strings, right.

So some end up being a little bit likelier.

Okay, now this leads to a testable prediction, right.

Namely, that if we run this experiment over and over, and if we really had a working quantum computer, then, you know, the strings that were predicted to be more likely, we ought to be seeing them more often, right.

So, you know, the outputs, the samples that we get should be biased toward the strings that can be predicted to be more likely, given knowledge of this quantum circuit, right.

Now, unfortunately, testing that prediction is itself, you know, a very, very computationally intensive problem for a classical computer, right.

That's one of the ironies of this subject, right, that even just to test that the quantum computer is doing what you wanted it to do, you need, you know, a huge classical supercomputer, okay.

And in fact, you know, this experiment with 53 qubits, it just barely worked, you know, you were just barely able to do the verification.

If you had had 100 qubits, well then, even if the experiment was working, we would never have been able to prove it.

Okay, we just would not have had the classical computation power to prove it.

Okay, so this is not a problem like factoring, right.

Factoring, you know, once you've found the factors of a 10,000 digit number, they're easy to check, right, which is what we mean in saying that factoring is an NP problem, right.

These sampling problems are not NP problems, okay.

But now the questions that we had to think about as theorists were, you know, what tests do you actually apply to the outputs to see, you know, are they biased toward the right ones, right.

What statistics do you apply? And then how hard would it have been for a classical computer if it was just trying to spoof the quantum computer, you know, in this test, right.

So would it have been hard for a classical computer to produce output strings that were similarly biased, right.

And well, we think that the answer is yes, it would have been hard.

Can we prove that?

Well, once again, no, right. We don't know how to prove these things because we can't even prove that P is not equal to P space and so forth.

Okay, but, you know, we could give some cryptographic style evidence that it was hard, right.

We could say, if you could spoof this test, then you could, you know, you could get a lot of leverage in the general task of simulating a quantum circuit with a classical computer in a way that we don't think is likely.

Okay. And then we, you know, we had to worry about the noise in the experiment, right.

So what you, when Google really runs this experiment, they're not really seeing a sample from the true output distribution, you know, corresponding to that quantum circuit.

Because of the noise in their system, what they're really seeing is like 99.8% the uniform distribution and then 0.2% the distribution that you want, right.

So they have to extract a signal from that, you know, huge amount of noise.

Fortunately, they were able to do that because in their setup, taking a sample takes only a few tens of microseconds, which means that after a few minutes, they can get millions of samples, right.

So then you extract a signal from this noise and then you have to argue about, well, how hard would it have been for a classical computer and you could say, even with that much noise in it, we think it still would have been hard, you know, under some complexity assumptions.

So that's, that's basically what the result was, that they did this and that, you know, as far as we can say, it works like the theory said it would work.

Well, I'd love to keep digging into this, but we're close to the end. And I'd like to get Oh, you're frozen again for a second.

Um, I'd like to get some of your perspectives on the future of this area of research.

What does the next 10 or 20 years look like in the next 10 or 20 years?

Yeah, sure. This conversation. Sure.

Well, um, So I, I have learned to be, you know, really, really cagey about predicting how long things will take.

Right. Like you can, you know, know, you know, as much as you want about, you know, even like a very specific area.

Right. And you can still be off by orders of magnitude and predicting how many years it will take, because that depends on, you know, not just on the science, but on, you know, who will care.

Enough to fund it. And, you know, even, you know, will civilization be paused because of a coronavirus and, you know, all kinds of wild and weird possibilities like that.

Right. But, um, but, but, but I can certainly tell you what are the next things on people's agenda in this field.

Okay.

And, and the clear next thing on everyone's agenda right now is to get the first demonstration of useful quantum error correction.

Okay, so, you know, People say, you know, okay, quantum supremacy, you know, been there, done that, you know, I, by the way, I think that there's a lot more to do even there in, you know, First of all, you know, replicate Google's results right do it in other hardware platforms.

Figure out how to do this kind of quantum supremacy experiment in a way where you can actually easily verify the answer with a classical computer.

Right. You know, that's a problem for theorists really figure out what, if anything, it's useful for.

Right. I have a proposal that you could repurpose these sorts of quantum supremacy experiments to actually generate random bits.

In a way that's cryptographically secure where, you know, everyone can see that, you know, they were not secretly pseudo random, you know, that might have some uses for proof of state crypto currencies and things like that.

But, you know, it will take a lot of work to make that practical, you know, do, you know, even before quantum error correction, people are going to work on Can we do useful simulations of quantum physics.

Can we use quantum computers to learn something new about material science about condensed matter physics.

Maybe even about quantum gravity, you know, just by simulating various quantum systems on these noisy quantum computers with 50 or 100 qubits.

So those are all frontiers that people are absolutely going to be pursuing over the next decade.

But the real Holy Grail that has come, you know, even more clearly into view now that quantum supremacy has been achieved is the first useful demonstration of quantum error correction.

Okay. Because quantum error correction is really the idea that will let this thing scale right like if you know sort of, I'd say just about everyone in this field agrees If quantum computing can ultimately scale to, you know, millions or billions of qubits.

If you can actually achieve the You know, the original promise of this field that what Feynman and Deutsch were talking about, it will be because we have figured out how to protect the qubits.

From, you know, interaction with their environment.

And that means quantum error correction or else something very much like it.

Okay. And so, so there have been demonstrations already of quantum error correction.

But either they've only worked against restricted kinds of errors or else they have not yet been a net gain.

Okay, so it's kind of like you are you're you're trying to protect your qubits, but you end up with a protected Protected qubit or an encoded qubit that is even noisier than your underlying physical qubits.

Right. So that's, you know, that's not very good yet.

It's like, you know, you're, it's as if you're trying to do and, you know, build a Nuclear power plant or, you know, or a nuclear bomb and so far it's fizzling out right we're not yet at the break even point where you do where you apply this error correction and you get an encoded qubit that is That lives for longer than the physical qubits live for, but that is something that people are going to try to demonstrate, you know, not on the scale of decades, but on the scale of like the coming few years.

And, you know, once that's achieved, then, you know, there will still be a lot of work to do, both on the engineering side and on the theory side, right, because, you know, we're still I gotta cut you off there because We're running out of time, but All right.

All right. Okay. Anyway, I think that that's for for, you know, people interested in getting actual real quantum computers in that that that would be the next frontier to look for.

There's lots of I'm excited.

All right. Well, thank you so much for this conversation. Yeah. Yeah. All right.

No problem. No problem. The next conversation. Thanks, Scott. Thank you.