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

As you've said, quantum computing, at least in the 1990s, was a profound story at the intersection of computer science, physics, engineering, math, and philosophy.

So there's this broad and deep aspect to quantum computing that represents more than just the quantum computer.

Yeah, so it's a proposal for a new type of computation, or let's say a new way to harness nature to do computation that is based on the principles of quantum mechanics.

Okay, now the principles of quantum mechanics have been in place since 1926.

You know, what's new is how we want to use them.

Okay, so what does quantum mechanics say about the world?

You know, the physicists, I think, over the generations, you know, convinced people that that is an unbelievably complicated question and, you know, just give up on trying to understand it.

I can let you in, not being a physicist, I can let you in on a secret, which is that it becomes a lot simpler if you do what we do in quantum information theory and sort of take the physics out of it.

So the way that we think about quantum mechanics is sort of as a generalization of the rules of probability themselves.

So, you know, you might say there's a, you know, there was a 30% chance that it was going to snow today or something.

You would never say that there was a negative 30% chance, right?

Much less would you say that there was an I percent chance, you know, square root of minus 1 percent chance.

Now the central discovery that sort of quantum mechanics made is that fundamentally the world is described by, or let's say the possibilities for what a system could be doing are described using numbers called amplitudes, okay, which are like probabilities in some ways, but they are not probabilities.

They can be positive, for 1 thing, they can be positive or negative.

In fact, they can even be complex numbers.

Okay, and if you've heard of a quantum superposition, this just means that some state of affairs where you assign an amplitude, 1 of these complex numbers, to every possible configuration that you could see a system in on measuring it.

So for example, you might say that an electron has some amplitude for being here and some other amplitude for being there, right?

Now, if you look to see where it is, you will localize it, right?

You will sort of force the amplitudes to be converted into probabilities.

That happens by taking their squared absolute value, okay?

And then, you know, you can say either the electron will be here or it will be there.

And you know, knowing the amplitudes, you can predict at least the probabilities that you'll see each possible outcome, okay?

But while a system is isolated from the whole rest of the universe, the rest of its environment, the amplitudes can change in time by rules that are different from the normal rules of probability and that are alien to our everyday experience.

So anytime anyone ever tells you anything about the weirdness of the quantum world, or assuming that they're not lying to you, they are telling you yet another consequence of nature being described by these amplitudes.

So most famously, what amplitudes can do is that they can interfere with each other.

Okay, so in the famous double slit experiment, what happens is that you shoot a particle, like an electron, let's say, at a screen with 2 slits in it and you find that there, you know, on a second screen, now there are certain places where that electron will never end up, you know, after it passes through the first screen.

And yet, if I close off 1 of the slits, then the electron can appear in that place, okay?

So by decreasing the number of paths that the electron could take to get somewhere, you can increase the chance that it gets there.

Well, it's because, as we would say now, the electron has a superposition state, okay?

It has some amplitude for reaching this point by going through the first slit.

It has some other amplitude for reaching it by going through the second slit.

But now if 1 amplitude is positive and the other 1 is negative, then I have to add them all up, right?

I have to add the amplitudes for every path that the electron could have taken to reach this point.

And those amplitudes, if they're pointing in different directions, they can cancel each other out.

That would mean the total amplitude is 0 and the thing never happens at all.

I close off 1 of the possibilities, then the amplitude is positive or it's negative and now the thing can happen.

Okay, so that is sort of the 1 trick of quantum mechanics.

And now I can tell you what a quantum computer is.

Okay, a quantum computer is a computer that tries to exploit, you know, these, exactly these phenomena, superposition, amplitudes, and interference in order to solve certain problems much faster than we know how to solve them otherwise.

So it's the basic building block of a quantum computer is what we call a quantum bit or a qubit, that just means a bit that has some amplitude for being 0 and some other amplitude for being 1.

So it's a superposition of 0 and 1 states, right?

But now the key point is that if I've got, let's say, a thousand qubits, the rules of quantum mechanics are completely unequivocal that I do not just need 1, you know, I don't just need amplitudes for each qubit separately.

Okay, in general, I need an amplitude for every possible setting of all thousand of those bits, okay?

So that what that means is 2 to the 1000 power amplitudes.

Okay, if I had to write those down, let's say in the memory of a conventional computer, if I had to write down 2 to the 1,000 complex numbers, that would not fit within the entire observable universe.

Okay, and yet, you know, quantum mechanics is unequivocal that if these qubits can all interact with each other, and in some sense, I need 2 to the 1,000 parameters, you know, amplitudes to describe what is going on.

Now, I can tell you where all the popular articles about quantum computing go off the rails is that they say, they sort of say what I just said, and then they say, oh, so the way a quantum computer works is just by trying every possible answer in parallel.

So, you know, that sounds too good to be true, and unfortunately it kind of is too good to be true.

The Problem is I could make a superposition over every possible answer to my problem, even if there were 2 to the 1,000 of them, right?

The trouble is for a computer to be useful, you've got at some point, you've got to look at it and see an output, right?

And if I just measure a superposition over every possible answer, then the rules of quantum mechanics tell me that all I'll see will be a random answer.

You know, if I just wanted a random answer, well, I could have picked 1 myself with a lot less trouble, right?

So the entire trick with quantum computing, with every algorithm for a quantum computer, is that you try to choreograph a pattern of interference of amplitudes.

And you try to do it so that for each wrong answer, some of the paths leading to that wrong answer have positive amplitudes and others have negative amplitudes so on the whole they cancel each other out.

Okay, whereas all the paths leading to the right answer should reinforce each other, you know, should have amplitudes pointing the same direction.

So the design of algorithms in the space is the choreography of the interferences.

So in which part of this beautiful picture that you've painted is information contained?

Oh, well, information is at the core of everything that we've been talking about, right?

I mean, the bit is the basic unit of information since Claude Shannon's paper in 1948.

And of course, people had the concept even before that.

and what we would say is that the basic unit of quantum information is the qubit, is the object, any object that can be maintained and manipulated in a superposition of 0 and 1 states.

Now, sometimes people ask, well, but what is a qubit physically, right?

And there are all these different, you know, proposals that are being pursued in parallel for how you implement qubits.

There is, you know, superconducting quantum computing that was in the news recently because of Google's quantum supremacy experiment, right?

Where you would have some little coils where a current can flow through them in 2 different energy states, 1 representing a 0, another representing a 1.

And if you cool these coils to just slightly above absolute 0, like a hundredth of a degree, then they superconduct and then the current can actually be in a superposition of the 2 different states.

Another kind would be, you know, just an individual atomic nucleus, right?

It could be spinning counterclockwise, or it could be in a superposition of the 2 spin states.

But see, just like in the classical world, you could be a virtuoso programmer without having any idea of what a transistor is, or how the bits are physically represented inside the machine, even that the machine uses electricity.

It's sort of the same with quantum computing, right?

Qubits could be realized by many, many different quantum systems, and yet all of those systems will lead to the same logic, you know, the logic of qubits and how you measure them, how you change them over time.

And so the subject of how qubits behave and what you can do with qubits, that is quantum information.

So the physical design implementation of a qubit does not interfere with that next level of abstraction that you can program over it?

Well, to be honest with you, today they do interfere with each other.

That's because all the quantum computers we can build today are very noisy, right?

And so sort of the qubits are very far from perfect.

And so the lower level sort of does affect the higher levels and we sort of have to think about all of them at once.

Okay, but eventually where we hope to get is to what are called error corrected quantum computers, where the qubits really do behave like perfect abstract qubits for as long as we want them to.

And in that future, a future that we can already sort of prove theorems about or think about today, but in that future, the logic of it really does become decoupled from the hardware.

So if noise is currently the biggest problem for quantum computing, and then the dream is error correcting quantum computers, can you just maybe describe what does it mean for there to be noise in the system?

So yeah, so the problem is even a little more specific than noise.

So the fundamental problem, if you're trying to actually build a quantum computer, you know, of any appreciable size, is something called decoherence.

Okay, And this was recognized from the very beginning, when people first started thinking about this in the 1990s.

Now what decoherence means is sort of the unwanted interaction between your qubits, the state of your quantum computer and the external environment.

Well, I talked before about how, when you measure a quantum system, so let's say if I measure a qubit that's in a superposition of 0 and 1 states to ask it, are you 0 or are you 1?

Well, now I force it to make up its mind, right?

And now probabilistically it chooses 1 or the other, and now it's no longer a superposition, there's no longer amplitudes, there's just there's some probability that I get a 0 and there's some that I get a 1.

And now the trouble is that it doesn't have to be me who's looking, okay?

Or in fact, it doesn't have to be any conscious entity.

Any kind of interaction with the external world that leaks out the information about whether this qubit was a 0 or a 1, sort of that causes the zeroness or the oneness of the qubit to be recorded in, you know, the radiation in the room, in the molecules of the air, in the wires that are connected to my device, any of that, as soon as the information leaks out, it is as if that qubit has been measured, okay?

It is, you know, the state has now collapsed.

You know, another way to say it is that it's become entangled with its environment.

Okay, but, you know, from the perspective of someone who's just looking at this qubit, it is as though it has lost its quantum state.

And so what this means is that if I want to do a quantum computation, I have to keep the qubits sort of fanatically well isolated from their environment.

But then at the same time, they can't be perfectly isolated because I need to tell them what to do.

I need to make them interact with each other, for 1 thing, and not only that, but in a precisely choreographed way.

Okay, and that is such a staggering problem, right?

How do I isolate these qubits from the whole universe, but then also tell them exactly what to do.

I mean, you know, there were distinguished physicists and computer scientists in the 90s who said this is fundamentally impossible.

You know, the laws of physics will just never let you control qubits to the degree of accuracy that you're talking about.

Now what changed the views of most of us was a profound discovery in the mid to late 90s, which was called the theory of quantum error correction and quantum fault tolerance.

Okay, and the upshot of that theory is that if I want to build a reliable quantum computer and scale it up to an arbitrary number of as many qubits as I want, and doing as much on them as I want, I do not actually have to get the qubits perfectly isolated from their environment.

It is enough to get them really, really, really well isolated.

And even if every qubit is sort of leaking its state into the environment at some rate, as long as that rate is low enough, I can sort of encode the information that I care about in very clever ways across the collective states of multiple qubits, okay, in such a way that even if a small percentage of my qubits leak, well, I'm constantly monitoring them to see if that leak happened.

I can recover the information I care about from the remaining qubits.

Okay, and so you can build a reliable quantum computer even out of unreliable parts, right?

Now, in some sense, you know, that discovery is what set the engineering agenda for quantum computing research from the 1990s until the present.

Okay, the goal has been, you know, engineer qubits that are not perfectly reliable, but reliable enough that you can then use these error correcting codes to have them simulate qubits that are even more reliable than they are.

So the error correction becomes a net win rather than a net loss, right?

And then once you reach that sort of crossover point, then your simulated qubits could in turn simulate qubits that are even more reliable and so on until you've just, effectively, you have arbitrarily reliable qubits.

So long story short, we are not at that break-even point yet.

We're a hell of a lot closer than we were when people started doing this in the 90s, like orders of magnitude closer.

But the key ingredient there is the more qubits the better.

Well, the more qubits, the larger the computation you can do, right?

I mean, qubits are what constitute the memory of your quantum computer, right?

So the way I would say it is that error correction imposes an overhead in the number of qubits.

And that is actually 1 of the biggest practical problems with building a scalable quantum computer.

If you look at the error correcting codes, at least the ones that we know about today, and you look at what would it take to actually use a quantum computer to hack your credit card number, which is maybe the most famous application people talk about, right, let's say to factor huge numbers and thereby break the RSA cryptosystem.

Well, what that would take would be thousands of, several thousand logical qubits, but now with the known error correcting codes, each of those logical qubits would need to be encoded itself using thousands of physical qubits.

So at that point, you're talking about millions of physical qubits.

And in some sense, that is the reason why quantum computers are not breaking cryptography already.

It's because of these immense overheads involved.

So that overhead is additive or multiplicative?

I mean, it's like you take the number of logical qubits that you need in your abstract quantum circuit, you multiply it by a thousand or so.

So, you know, there's a lot of work on, you know, inventing better, trying to invent better error correcting codes.

In the meantime, we are now in what the physicist John Preskill called the noisy intermediate scale quantum or NISQ era.

And this is the era, you can think of it as sort of like the vacuum, we're now entering the very early vacuum tube era of quantum computers.

The quantum computer analog of the transistor has not been invented yet, right?

That would be like true error correction, right?

Where, you know, we are not, or something else that would achieve the same effect, right?

And, but where we are now, let's say as of a few months ago, you know, as of Google's announcement of quantum supremacy, we are now finally at the point where even with a non-error corrected quantum computer, with these noisy devices, we can do something that is hard for classical computers to simulate.

Now, will we in this noisy era be able to do something beyond what a classical computer can do that is also useful to someone?

People are going to be racing over the next decade to try to do that by people, I mean Google, IBM, you know, a bunch of startup companies, you know, players that, yeah, and research labs and governments and yeah.

So how do we get to where we are now with the CPU.

Is this a fundamental engineering challenge?

Is there breakthroughs on the physics side that are needed on the computer science side?

Is it a financial issue where a much larger just sheer investment and excitement is needed?

So, you know, those are excellent questions.

My guess, my, well, no, no, my guess would be all of the above.

I mean, my guess, you know, I mean, you know, you could say fundamentally it is an engineering issue, right?

The theory has been in place since the 90s, at least this is what error correction would look like.

We do not have the hardware that is at that level.

But at the same time, you know, so you could just, you know, try to power through, you know, maybe even like, you know, if someone spent a trillion dollars on some quantum computing Manhattan project, right, then conceivably, they could just, you know, build an error-corrected quantum computer as it was envisioned back in the 90s, right?

I think the more plausible thing to happen is that there will be further theoretical breakthroughs and there will be further insights that will cut down the cost of doing this.


Speaker 0: As you've said, quantum computing, at least in the 1990s, was a profound story at the intersection of computer science, physics, engineering, math, and philosophy. So there's this broad and deep aspect to quantum computing that represents more than just the quantum computer. But can we start at the very basics? What is quantum computing?

Speaker 1: Yeah, so it's a proposal for a new type of computation, or let's say a new way to harness nature to do computation that is based on the principles of quantum mechanics. Okay, now the principles of quantum mechanics have been in place since 1926. You know, they haven't changed. You know, what's new is how we want to use them. Okay, so what does quantum mechanics say about the world?

You know, the physicists, I think, over the generations, you know, convinced people that that is an unbelievably complicated question and, you know, just give up on trying to understand it. I can let you in, not being a physicist, I can let you in on a secret, which is that it becomes a lot simpler if you do what we do in quantum information theory and sort of take the physics out of it. So the way that we think about quantum mechanics is sort of as a generalization of the rules of probability themselves. So, you know, you might say there's a, you know, there was a 30% chance that it was going to snow today or something. You would never say that there was a negative 30% chance, right?

That would be nonsense. Much less would you say that there was an I percent chance, you know, square root of minus 1 percent chance. Now the central discovery that sort of quantum mechanics made is that fundamentally the world is described by, or let's say the possibilities for what a system could be doing are described using numbers called amplitudes, okay, which are like probabilities in some ways, but they are not probabilities. They can be positive, for 1 thing, they can be positive or negative. In fact, they can even be complex numbers.

Okay, and if you've heard of a quantum superposition, this just means that some state of affairs where you assign an amplitude, 1 of these complex numbers, to every possible configuration that you could see a system in on measuring it. So for example, you might say that an electron has some amplitude for being here and some other amplitude for being there, right? Now, if you look to see where it is, you will localize it, right? You will sort of force the amplitudes to be converted into probabilities. That happens by taking their squared absolute value, okay?

And then, you know, you can say either the electron will be here or it will be there. And you know, knowing the amplitudes, you can predict at least the probabilities that you'll see each possible outcome, okay? But while a system is isolated from the whole rest of the universe, the rest of its environment, the amplitudes can change in time by rules that are different from the normal rules of probability and that are alien to our everyday experience. So anytime anyone ever tells you anything about the weirdness of the quantum world, or assuming that they're not lying to you, they are telling you yet another consequence of nature being described by these amplitudes. So most famously, what amplitudes can do is that they can interfere with each other.

Okay, so in the famous double slit experiment, what happens is that you shoot a particle, like an electron, let's say, at a screen with 2 slits in it and you find that there, you know, on a second screen, now there are certain places where that electron will never end up, you know, after it passes through the first screen. And yet, if I close off 1 of the slits, then the electron can appear in that place, okay? So by decreasing the number of paths that the electron could take to get somewhere, you can increase the chance that it gets there. Okay, now how is that possible? Well, it's because, as we would say now, the electron has a superposition state, okay?

It has some amplitude for reaching this point by going through the first slit. It has some other amplitude for reaching it by going through the second slit. But now if 1 amplitude is positive and the other 1 is negative, then I have to add them all up, right? I have to add the amplitudes for every path that the electron could have taken to reach this point. And those amplitudes, if they're pointing in different directions, they can cancel each other out.

That would mean the total amplitude is 0 and the thing never happens at all. I close off 1 of the possibilities, then the amplitude is positive or it's negative and now the thing can happen. Okay, so that is sort of the 1 trick of quantum mechanics. And now I can tell you what a quantum computer is. Okay, a quantum computer is a computer that tries to exploit, you know, these, exactly these phenomena, superposition, amplitudes, and interference in order to solve certain problems much faster than we know how to solve them otherwise.

So it's the basic building block of a quantum computer is what we call a quantum bit or a qubit, that just means a bit that has some amplitude for being 0 and some other amplitude for being 1. So it's a superposition of 0 and 1 states, right? But now the key point is that if I've got, let's say, a thousand qubits, the rules of quantum mechanics are completely unequivocal that I do not just need 1, you know, I don't just need amplitudes for each qubit separately. Okay, in general, I need an amplitude for every possible setting of all thousand of those bits, okay? So that what that means is 2 to the 1000 power amplitudes.

Okay, if I had to write those down, let's say in the memory of a conventional computer, if I had to write down 2 to the 1,000 complex numbers, that would not fit within the entire observable universe. Okay, and yet, you know, quantum mechanics is unequivocal that if these qubits can all interact with each other, and in some sense, I need 2 to the 1,000 parameters, you know, amplitudes to describe what is going on. Now, I can tell you where all the popular articles about quantum computing go off the rails is that they say, they sort of say what I just said, and then they say, oh, so the way a quantum computer works is just by trying every possible answer in parallel. So, you know, that sounds too good to be true, and unfortunately it kind of is too good to be true. The Problem is I could make a superposition over every possible answer to my problem, even if there were 2 to the 1,000 of them, right?

I can easily do that. The trouble is for a computer to be useful, you've got at some point, you've got to look at it and see an output, right? And if I just measure a superposition over every possible answer, then the rules of quantum mechanics tell me that all I'll see will be a random answer. You know, if I just wanted a random answer, well, I could have picked 1 myself with a lot less trouble, right? So the entire trick with quantum computing, with every algorithm for a quantum computer, is that you try to choreograph a pattern of interference of amplitudes.

And you try to do it so that for each wrong answer, some of the paths leading to that wrong answer have positive amplitudes and others have negative amplitudes so on the whole they cancel each other out. Okay, whereas all the paths leading to the right answer should reinforce each other, you know, should have amplitudes pointing the same direction.

Speaker 0: So the design of algorithms in the space is the choreography of the interferences.

Speaker 1: Precisely, that's precisely what

Speaker 0: it is. Can we take a brief step back? And you mentioned information. Yes. So in which part of this beautiful picture that you've painted is information contained?

Speaker 1: Oh, well, information is at the core of everything that we've been talking about, right? I mean, the bit is the basic unit of information since Claude Shannon's paper in 1948. And of course, people had the concept even before that. He popularized the name, right? But I mean-

Speaker 0: But a bit is 0 or 1. That's right. So that's the basic

Speaker 1: element of information.

Speaker 0: That's right,

Speaker 1: and what we would say is that the basic unit of quantum information is the qubit, is the object, any object that can be maintained and manipulated in a superposition of 0 and 1 states. Now, sometimes people ask, well, but what is a qubit physically, right? And there are all these different, you know, proposals that are being pursued in parallel for how you implement qubits. There is, you know, superconducting quantum computing that was in the news recently because of Google's quantum supremacy experiment, right? Where you would have some little coils where a current can flow through them in 2 different energy states, 1 representing a 0, another representing a 1.

And if you cool these coils to just slightly above absolute 0, like a hundredth of a degree, then they superconduct and then the current can actually be in a superposition of the 2 different states. So that's 1 kind of qubit. Another kind would be, you know, just an individual atomic nucleus, right? It has a spin. It could be spinning clockwise.

It could be spinning counterclockwise, or it could be in a superposition of the 2 spin states. That is another qubit. But see, just like in the classical world, you could be a virtuoso programmer without having any idea of what a transistor is, or how the bits are physically represented inside the machine, even that the machine uses electricity. You just care about the logic. It's sort of the same with quantum computing, right?

Qubits could be realized by many, many different quantum systems, and yet all of those systems will lead to the same logic, you know, the logic of qubits and how you measure them, how you change them over time. And so the subject of how qubits behave and what you can do with qubits, that is quantum information.

Speaker 0: So just to linger on that. So the physical design implementation of a qubit does not interfere with that next level of abstraction that you can program over it? So it truly is, the idea of it is, okay.

Speaker 1: Well, to be honest with you, today they do interfere with each other. That's because all the quantum computers we can build today are very noisy, right? And so sort of the qubits are very far from perfect. And so the lower level sort of does affect the higher levels and we sort of have to think about all of them at once. Okay, but eventually where we hope to get is to what are called error corrected quantum computers, where the qubits really do behave like perfect abstract qubits for as long as we want them to.

And in that future, a future that we can already sort of prove theorems about or think about today, but in that future, the logic of it really does become decoupled from the hardware.

Speaker 0: So if noise is currently the biggest problem for quantum computing, and then the dream is error correcting quantum computers, can you just maybe describe what does it mean for there to be noise in the system? Absolutely.

Speaker 1: So yeah, so the problem is even a little more specific than noise. So the fundamental problem, if you're trying to actually build a quantum computer, you know, of any appreciable size, is something called decoherence. Okay, And this was recognized from the very beginning, when people first started thinking about this in the 1990s. Now what decoherence means is sort of the unwanted interaction between your qubits, the state of your quantum computer and the external environment. Okay, and why is that such a problem?

Well, I talked before about how, when you measure a quantum system, so let's say if I measure a qubit that's in a superposition of 0 and 1 states to ask it, are you 0 or are you 1? Well, now I force it to make up its mind, right? And now probabilistically it chooses 1 or the other, and now it's no longer a superposition, there's no longer amplitudes, there's just there's some probability that I get a 0 and there's some that I get a 1. And now the trouble is that it doesn't have to be me who's looking, okay? Or in fact, it doesn't have to be any conscious entity.

Any kind of interaction with the external world that leaks out the information about whether this qubit was a 0 or a 1, sort of that causes the zeroness or the oneness of the qubit to be recorded in, you know, the radiation in the room, in the molecules of the air, in the wires that are connected to my device, any of that, as soon as the information leaks out, it is as if that qubit has been measured, okay? It is, you know, the state has now collapsed. You know, another way to say it is that it's become entangled with its environment. Okay, but, you know, from the perspective of someone who's just looking at this qubit, it is as though it has lost its quantum state. And so what this means is that if I want to do a quantum computation, I have to keep the qubits sort of fanatically well isolated from their environment.

But then at the same time, they can't be perfectly isolated because I need to tell them what to do. I need to make them interact with each other, for 1 thing, and not only that, but in a precisely choreographed way. Okay, and that is such a staggering problem, right? How do I isolate these qubits from the whole universe, but then also tell them exactly what to do. I mean, you know, there were distinguished physicists and computer scientists in the 90s who said this is fundamentally impossible.

You know, the laws of physics will just never let you control qubits to the degree of accuracy that you're talking about. Now what changed the views of most of us was a profound discovery in the mid to late 90s, which was called the theory of quantum error correction and quantum fault tolerance. Okay, and the upshot of that theory is that if I want to build a reliable quantum computer and scale it up to an arbitrary number of as many qubits as I want, and doing as much on them as I want, I do not actually have to get the qubits perfectly isolated from their environment. It is enough to get them really, really, really well isolated. And even if every qubit is sort of leaking its state into the environment at some rate, as long as that rate is low enough, I can sort of encode the information that I care about in very clever ways across the collective states of multiple qubits, okay, in such a way that even if a small percentage of my qubits leak, well, I'm constantly monitoring them to see if that leak happened.

I can detect it and I can correct it. I can recover the information I care about from the remaining qubits. Okay, and so you can build a reliable quantum computer even out of unreliable parts, right? Now, in some sense, you know, that discovery is what set the engineering agenda for quantum computing research from the 1990s until the present. Okay, the goal has been, you know, engineer qubits that are not perfectly reliable, but reliable enough that you can then use these error correcting codes to have them simulate qubits that are even more reliable than they are.

So the error correction becomes a net win rather than a net loss, right? And then once you reach that sort of crossover point, then your simulated qubits could in turn simulate qubits that are even more reliable and so on until you've just, effectively, you have arbitrarily reliable qubits. So long story short, we are not at that break-even point yet. We're a hell of a lot closer than we were when people started doing this in the 90s, like orders of magnitude closer.

Speaker 0: But the key ingredient there is the more qubits the better. Because...

Speaker 1: Well, the more qubits, the larger the computation you can do, right? I mean, qubits are what constitute the memory of your quantum computer, right?

Speaker 0: But also for the, sorry, for

Speaker 1: the error correcting mechanism. Yes. So the way I would say it is that error correction imposes an overhead in the number of qubits. And that is actually 1 of the biggest practical problems with building a scalable quantum computer. If you look at the error correcting codes, at least the ones that we know about today, and you look at what would it take to actually use a quantum computer to hack your credit card number, which is maybe the most famous application people talk about, right, let's say to factor huge numbers and thereby break the RSA cryptosystem.

Well, what that would take would be thousands of, several thousand logical qubits, but now with the known error correcting codes, each of those logical qubits would need to be encoded itself using thousands of physical qubits. So at that point, you're talking about millions of physical qubits. And in some sense, that is the reason why quantum computers are not breaking cryptography already. It's because of these immense overheads involved.

Speaker 0: So that overhead is additive or multiplicative?

Speaker 1: Well, it's multiplicative. I mean, it's like you take the number of logical qubits that you need in your abstract quantum circuit, you multiply it by a thousand or so. So, you know, there's a lot of work on, you know, inventing better, trying to invent better error correcting codes. Okay, that is the situation right now. In the meantime, we are now in what the physicist John Preskill called the noisy intermediate scale quantum or NISQ era.

And this is the era, you can think of it as sort of like the vacuum, we're now entering the very early vacuum tube era of quantum computers. The quantum computer analog of the transistor has not been invented yet, right? That would be like true error correction, right? Where, you know, we are not, or something else that would achieve the same effect, right? We are not there yet.

And, but where we are now, let's say as of a few months ago, you know, as of Google's announcement of quantum supremacy, we are now finally at the point where even with a non-error corrected quantum computer, with these noisy devices, we can do something that is hard for classical computers to simulate. So we can eke out some advantage. Now, will we in this noisy era be able to do something beyond what a classical computer can do that is also useful to someone? That we still don't know. People are going to be racing over the next decade to try to do that by people, I mean Google, IBM, you know, a bunch of startup companies, you know, players that, yeah, and research labs and governments and yeah.

Speaker 0: You just mentioned a million things. Well, I'll backtrack for a second.

Speaker 1: Yeah, sure, sure.

Speaker 0: So we're in these vacuum tube days. Yeah, just entering. And just entering, wow, okay. So how do we escape the vacuum? So how do we get to where we are now with the CPU.

Is this a fundamental engineering challenge? Is there breakthroughs on the physics side that are needed on the computer science side? Is it a financial issue where a much larger just sheer investment and excitement is needed?

Speaker 1: So, you know, those are excellent questions. My guess, my, well, no, no, my guess would be all of the above. I mean, my guess, you know, I mean, you know, you could say fundamentally it is an engineering issue, right? The theory has been in place since the 90s, at least this is what error correction would look like. We do not have the hardware that is at that level.

But at the same time, you know, so you could just, you know, try to power through, you know, maybe even like, you know, if someone spent a trillion dollars on some quantum computing Manhattan project, right, then conceivably, they could just, you know, build an error-corrected quantum computer as it was envisioned back in the 90s, right? I think the more plausible thing to happen is that there will be further theoretical breakthroughs and there will be further insights that will cut down the cost of doing this.

See all Lex Fridman transcripts on Youtube

Scott Aaronson: What is a Quantum Computer? | AI Podcast Clips