- 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? - 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 wanna 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 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, you know, an I% chance, you know, square root of minus 1% chance.

Now, the central discovery that sort of quantum mechanics made is that fundamentally the world is described by, or, you know, the sort of, let's say the possibilities for, you know, 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 one 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, one 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, you know, alien to our everyday experience.

So anytime anyone ever tells you anything about the weirdness of the quantum world, you know, or assuming that they're not lying to you, right, they are telling you, you know, 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 two 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 one 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, you know, 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 one amplitude is positive and the other one is negative, then, you know, 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 zero and the thing never happens at all. I close off one 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 one 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 zero and some other amplitude for being one. So it's a superposition of zero and one 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 one, 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 two 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 two to the 1000 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 two to the 1000 parameters, you know, amplitudes to describe what is going on. Now, you know, now I can tell you know, where all the popular articles, you know, about quantum computing go off the rails is that they say, you know, 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, you know, even if there were two to the 1000 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 one 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. - Precisely, that's precisely what 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? - Oh, well, information is at the core of everything that we've been talking about, right? I mean, the bit is, you know, the basic unit of information.

Since, you know, Claude Shannon's paper in 1948, you know, and you know, of course, people had the concept even before that, you know, he popularized the name, right? But I mean-- - But a bit is zero or one. - That's right. - So that's the basic element of information.

- That's right, and what we would say is that the basic unit of quantum information is the qubit, is, you know, the object, any object that can be maintained in a, manipulated in a superposition of zero and one states. Now, you know, 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 two different energy states, one representing a zero, another representing a one, and if you cool these coils to just slightly above absolute zero, like a hundredth of a degree, then they superconduct, and then the current can actually be in a superposition of the two different states.

So that's one 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 two spin states. That is another qubit. But see, just like in the classical world, right, you could be a virtuoso programmer without having any idea of what a transistor is, right, or how the bits are physically represented inside the machine, even that the machine uses electricity, right?

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, you know, the subject of how qubits behave and what you can do with qubits, that is quantum information. - So just to linger on that. - Sure. - 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. - 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, you know, a future that we can already, you know, 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 like 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 this system? - Absolutely. 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, you know, when people first started thinking about this in the 1990s. Now, what decoherence means is sort of the unwanted interaction between, you know, your qubits, you know, the state of your quantum computer and the external environment. Okay, and why is that such a problem?

Well, I talked before about how, you know, when you measure a quantum system, so let's say if I measure a qubit that's in a superposition of zero and one states to ask it, you know, are you zero or are you one? Well, now I force it to make up its mind, right?

And now probabilistically it chooses one or the other, and now, you know, it's no longer a superposition, there's no longer amplitudes, there's just there's some probability that I get a zero and there's some that I get a one. And now the trouble is that it doesn't have to be me who's looking, okay?

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 zero or a one, 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 one thing, and not only that, but in a precisely choreographed way.

Okay, and, you know, 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, you know, 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, okay? 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, okay, 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, you know, 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 know, 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, right? The error correction becomes a net win rather than a net loss, right?

And then once you reach that sort of crossover point, then, you know, your simulated qubits could in turn simulate qubits that are even more reliable and so on until you've just, you know, 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, because-- - 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?

- But also for the, sorry, for 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 one 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, you know, what would it take to actually use a quantum computer to, you know, hack your credit card number, which is, you know, maybe, you know, 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? - 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 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, you know, 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, you know, we are now finally at the point where even with a non-error-corrected quantum computer, with, you know, these noisy devices, we can do something that is hard for classical computers to simulate, okay?

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-- - And research labs.

- Yeah, and research labs and governments and yeah, so-- - You just mentioned a million things. Well, I'll backtrack for a second and ask. - Yeah, sure, sure. - So we're in these vacuum tube days. - Yeah, just entering, though. - 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? - So, you know, those are excellent questions.

My guess-- - No answers. - 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, you know, at least, you know, this is what, you know, error correction would look like.

You know, 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. you