Transcription
Uh, thanks everybody for coming. First, I wanted to thank, uh, the Dela Petra family, who are here, for allowing this, uh, tradition of, uh, many luminaries coming to Stonybrook once in a while and giving these amazing lectures. So, thank you for that.
Uh, today, [applause] so today, we're honored to have, uh, Scott Ernson, who is currently at UT Austin. So, he's known for his, uh, groundbreaking work on, uh, quantum comput-, quantum computers, uh, complexity theory, and many, many other fields. He's also very interested in physics, and he's now the head of the Quantum Information Center. He's the head of the Quantum, the AI and Alignment Center at UT Austin, and just recently, uh, during the last week, he was elected to the National Academy of Sciences. He got the, look at Revvis Prize for outreach, and, yeah, the number of accolades is, uh, very, very long. I'm not going to go over all of that, but he's a very, very interesting person, interested also with many, many contributions to outreach, to science, many different interests, a true renaissance man. So, anyway, we're very happy to have Scott. And, yeah.
>> Yeah. [applause]
>> Okay. See, um, is this, is this on? Uh, can you hear in the back? All right, good. So, yeah. Uh, so, so, uh, uh, thank you, Zohor, for that, you know, much too kind introduction, but, uh, I've gotten to know Zohor over the last year, and, uh, I was, uh, really happy to accept this introduction somehow. This is my first time in Stonybrook. I don't know how, uh, I'm sure it won't be the last. I've, uh, heard all about the, uh, Simon Center here, and it's been really great, uh, to see it for myself, and, and thank you all. That thanks to all of you, uh, uh, for coming, whether you're from the university, uh, uh, high school students here, uh, thanks, thanks for showing up.
So, uh, uh, you know, I, I, I gave this talk a sort of clickbait title, you know, "The Truth About Quantum Computing," you know, "You Won't Believe Point Number Six," or whatever. But, uh, um, uh, you know, so, so basically, you know, I, I, I, I never planned my life this way, but, you know, I started this blog in, you know, 2005. Um, it's called Optimized, uh, but, uh, uh, uh, yeah, and I, I write about all kinds of things. But, you know, what the main thing that the blog became known for was, you know, again and again, you know, some company would announce, you know, "We can use quantum computers to recognize handwriting." "We could use quantum computers to, you know, to do, uh, uh, vehicle routing," or to do, you know, in this case, it was to do finance. Okay. Uh, uh, HSBC was saying, "We can use a quantum computer to, you know, to, to, uh, basically, uh, uh, pick stocks better." Right? And again and again, like these claims just sort of evaporate when you look into them, right? Because, you know, what, what they never want to do is do a fair comparison against, well, what could a classical computer do for the same problem, right? But people learned, you know, you put the word "quantum" in front of something, right? And people will throw, you know, a hundred million dollars at it, right? You know, they don't have to understand anything. You don't have to have a case that makes any sense, right? And so, you know, my blog has just been like, you know, pouring water on this, on this sort of endless fire, right? People, e-, you know, basically, like every week, people would email me, you know, you know, you know, "This claim is is spreading all over, you know, the news sites," and journalists are just credulously repeating it. And so then I put up, put up a post about this claim, and, you know, and it's like pushing, you know, Sisyphus pushing the boulder up the hill. I'm not sure that it actually, you know, changes anything or makes any difference, but at least I feel like I have discharged, you know, my moral duty, right?
And so, um, and, and, you know, and, and, and, uh, uh, uh, it's, it's crazy because because, you know, again, over and over and over, you know, I have like have, uh, uh, colleagues, you know, including, you know, people who did very good technical work in this field, but then, you know, they decide to start a startup, right? And often, you know, the startup, like, says things that kind of don't make sense to me, you know, and they, and they raise $50 million, right? And then, and then the next person does that, you know, and it's like, like in a zombie movie. It's like, "You two?" Like, I'm like the last person in quantum computing who doesn't have a startup, right? And, you know, what, what's amazing is that it's only within like, literally the last couple months that I started asking myself, like, "Wait a minute, who's the stupid one here?"
>> [laughter]
>> Like, maybe I should start a startup. [laughter] Okay. Uh, but, so, so, but, but, you know, what, what I became known for, and again, I didn't plan it this way, it just happened, was just sort of the person who would just, you know, whose goal was to just try to tell the truth. Okay. And, you know, doing that, I get, I got screamed at a lot by both sides, right? So, like, uh, uh, I, you know, so, so there are all these, you know, uh, quantum computing investors, you know, who regard me as like the biggest, you know, skeptic and, you know, person, you know, rejecting every claim about quantum computing. But then, you know, there are also people who just deny that quantum computing is possible at all, right? Still, even today, right? Uh, uh, uh, you know, despite, you know, all the experimental progress that's been made, they say, like, "This can't work." Uh, you know, there are people in the Bitcoin community who are just sort of in aggressive denial that this is ever going to happen, you know, that, uh, uh, this will ever, you know, uh, threaten, uh, the, the security of Bitcoin. Uh, and, and, and to those people, you know, now, now they're also attacking me as like a, a credulous quantum computing booster, right? So, you know, I, one thing about about blogging is like, you do have to develop a thick skin, right? Like, you could say, "Waffles are delicious," and people will scream at you and say that, you know, you should be fired from your job. Okay. Um, and, you know, and, and, and, and believe me, that I have learned that. Uh, but, you know, I, I just try to tell the truth, uh, uh, you know, and, and, and say things that, you know, actually, you know, are, are mostly not even controversial among, you know, my colleagues, among people who, who, uh, work on quantum algorithms professionally. Uh, but then, you know, when when things get out to the public, or they get to the popular press, or to the business world, there is somehow things get lost in translation, somehow. Uh, you know, I think a mixture of sort of bad incentives and this genuinely being kind of complicated and and subtle to explain, you know, causes like wrong things to get out there. And so, you know, I just, there was, there was a gap for someone who would just try to tell the truth about this to to the public. Uh, so, so I tried to fill that gap. Okay.
So, uh, uh, you know, again and again, you know, every week I'm on the phone with with some journalist who's doing a quantum computing piece, and they're like, "Look, you know, I need you to just explain what is a quantum computer in one sentence." And I'm like, you know, I've been trying to explain this stuff for 25 years now. Uh, can you give me 10 minutes? [laughter] Okay? Uh, because I, I haven't figured out how to compress it more than that. Uh, because, you know, to, to, to actually say, you know, what a quantum computer is, how it's different from a classical computer, you first have to say something about what is quantum mechanics, right? Quantum mechanics is, you know, uh, arguably the most counterintuitive thing that's ever been discovered in the history of science. Uh, uh, you know, experts, you know, a hundred years after its discovery, still argue, you know, fundamentally disagree about what it means, you know, about what it's telling us about reality. Um, but, uh, uh, uh, you know, you, uh, if you want to understand quantum computing, like, you have to actually, like, see the thing as it is. You know, you can't sort of rely on on on sort of hokey metaphors that that, uh, uh, round it to something that it isn't, right?
So, uh, you know, the way, uh, but, but, but, there is good news here. The good news is that, uh, quantum computing is actually much, much simpler than than most people have been led to believe it is, uh, once you take the physics out of it. Okay. So, uh, the way that we like to think about quantum mechanics in my field, in, you know, quantum computing, quantum information, is really just a certain generalization of the rules of probability themselves. Okay. So, uh, you know, it's something that, a priori, you wouldn't have even thought was part of the subject matter of physics. Like, you would have thought, "Look, we know the laws of probability," you know, uh, uh, sitting in our armchairs, right? You know, if I don't know, uh, uh, uh, whether it's going to rain tomorrow, I can assign a real number from zero to one. You know, we call that a probability. It quantifies my degree of belief, right? And if, and crucially, if something could happen in two different ways, you know, and I know the probability of each way, then I can add those two probabilities and find the total probability that that thing will happen. This all seems obvious. Okay. Um, and yet, you know, that, uh, uh, that last thing that I just said about adding probabilities, that is actually the thing that quantum mechanics overturns. Okay. Uh, uh, and, um, so, so what, what is going on, you know, so, so what we learned a century ago is that, uh, the rules of probability that we're all used to are not the ones that nature chose. Uh, it chose a somewhat different set of rules, uh, that involve complex numbers, okay, that are called amplitudes. Uh, and so, you know, you, like, like, you would never say, "There is a negative 20% chance of rain tomorrow." Okay? If you said that, people would be like, "You know, what are you smoking?" Okay? Uh, you know, even less would you say that there's an i% you know, a square root of minus 1% chance, okay? But, uh, uh, what quantum mechanics says is that to every possible way that a physical system could evolve, so, for example, every path that a particle could take, uh, uh, you have to assign, uh, this number called an amplitude, which is a complex number. Okay? And, you know, at first, that seems like nonsense, right? Because, you know, again, you know, there can't be a complex chance of something happening. Okay? The key is, you know, once you, when you look, when you make a measurement, then there a new rule comes into effect, uh, uh, which converts the amplitudes into probabilities. Okay?
So, um, [snorts] so, uh, uh, you know, there's, I'll show it on the next slide. You know, there's a rule for how that happens. So, when you look, you see the particle in one place or another place, right? You never, you know, you never actually see these amplitudes. Okay? But if you want to calculate the probability that a particle will end up in one place or in another place, you have to use these amplitudes. Okay? Because the amplitudes are what the particle keeps track of when no one is looking at it. Okay? They're, uh, uh, you know, they're what, they're what, they're what nature likes to, uh, uh, uh, uh, likes to do in private. Okay? And, you know, and, and, and, and we know that because it's the only way to explain the probabilities when you do look. Okay? The most famous illustration of that is called the two-slit experiment. This is where you take a particle like an electron. This is, you know, this might as well be what an electron looks like, uh, for my purposes. And you shoot it at a screen with two little holes in it. And then you look at, you know, where does it end up on a second screen behind it. Okay? And, uh, um, you know, you would think, "Okay, well, well, of course, obviously, you know, if I, if I open more slits, then that could increase the chance that the particle might get to a certain spot. It's never going to decrease the chance, right? You know, it now just has more ways that it could get there." Okay? But that is not what you find. You find that, no, there are certain spots on the second screen where the particle, uh, can hit them if only one of the holes is open. Uh, but if both holes are open, then it can never hit that spot. Okay? So, it's as if the two paths that the particle could have taken to reach that spot have interfered with each other. They have canceled each other out. Okay? And this is the signature that we're dealing with a change to the rules of probability themselves. Okay? And, uh, you know, the, the way that you, we explained that in quantum mechanics was just to say, "Well, there was an amplitude for the electron, let's say, to f-, to hit this spot by following this top path here, and there was an amplitude for it to hit the same spot by following the bottom path." But now, let's say one of those amplitudes was a half, and the other one was minus a half. Then those two contributions will cancel each other out, right? They will, they will sum up to zero, which then means the total amplitude for the photon to hit that spot is zero, and you never see it there, right? If I close one of the, uh, two holes, then now, uh, the amplitude is a half, or it's negative a half, so now it's not zero, which means that the particle can appear there, okay? So, this is interference. And, you know, anything that anyone ever tells you about the weirdness of the quantum world, okay, whether that's, uh, about, uh, uh, tunneling, or about entanglement, or whatever. You know, either it's wrong, or else it's just another, uh, uh, downstream consequence of this change to the rules of probability. Okay? That blew my mind when I learned it as a teenager. I was like, "Why didn't anyone tell me that before?" Okay? That all this weird, you know, quantum weirdness they said is too hard to understand. No, it's vectors of complex numbers. Okay? The state of a physical system is a list of complex numbers called amplitudes, one for each configuration, and then, you know, the, the, these are the things that give rise to probabilities.
So, you know, this is how, like, physicists write it. They like to use these funny, uh, uh, asymmetrical, uh, brackets that are called "ket"s. Okay. So, the, the simplest quantum system, and one that we love to study in quantum computing, is called a quantum bit, or a qubit. Okay? Qubit just means a bit that can have an amplitude for being zero and another amplitude for being one. So, it can be in a superposition, as we say, of the zero state and the one state. Okay? If you look at it, you know, if you ask it whether it's zero or it's one, then it has to make up its mind, right? It probabilistically collapses to one or the other. Uh, each one with the probabilities, as I said before, that are the, the square of the absolute value of the amplitude. Okay? So, with pro-, with this probability, you get one. Uh, sorry, with this probability, you get zero, with that probability, you get one. And then, you know, if you, if you measure the qubit a second time, you know, if you, the qubit, uh, was one, and you measure it a second time, and nothing's happened in the interim, it says, you know, "I'm still one. You know, what are you, uh, why are you asking me again?" Okay? But if the qubit is isolated, then the way that these amplitudes change over time is by a different rule, you know, alien to our experience, right? Which is just that the, the, the list of amplitudes evolves via a linear equation. Okay? If any of you have heard of the Schrödinger equation, which is the central equation of quantum mechanics, it basically just says that. Okay? It says an isolated system, you know, uh, uh, has its amplitudes evolve, uh, in time by some linear equation, which has to preserve the property that the, uh, squared absolute values of the amplitudes always has to add up to one. Okay? Why does it have to always add up to one? Because these are the probabilities of the different possible outcomes. So, those have to, you know, for this to make sense, those have to always be one. Okay? But any linear transformation that preserves that, uh, which are called the unitary transformations, uh, is allowed. Okay?
So, so now, uh, we can finally talk about more than one qubit. Okay? So, you know, this is, this is, uh, interesting enough by itself. Okay? But now, let's say I, I have two, two qubits. Okay? So, now, by the way, you know, a qubit, you know, I, I won't care that much, you know, what it physically is. Okay? It could be an electron that has, you know, where zero is its ground state and one is its first excited state. Okay? It could be an atomic nucleus where zero means it's spinning clockwise, one means it's spinning counterclockwise about some axis. Um, you know, and there are many other examples, just like a classical bit could be, you know, we physically instantiate them in our computers by voltages, you know, in transistors. Okay? But there are many other things that, you know, that could, you know, even the position of an abacus bead that could represent a classical bit. Okay? So, it is with a qubit. Okay? Now, if I have two qubits, so say, like, two particles, you know, whose spins I'm keeping track of. Uh, the rules are very unequivocal that I cannot just assign amplitudes to each qubit separately from the others. Instead, I need an amplitude for every possible configuration of all of my qubits together. And this is really crucial. So, if I have two qubits, I now need four amplitudes. I need an amplitude for 00 and for 01 and for 10 and for 11, right? Every possible two-bit string. Okay? Uh, and, and so, in particular, I could have a superposition of 00 and 11, right? Which would have the property that if I measure one of the qubits and I see that it's zero, then immediately I know that the other qubit is also zero. And likewise, if I, if I see that one of them is one, the other one is also one. Okay? You've heard of entanglement. That's what entanglement means. Okay? Uh, so, it's the sort of the quantum version of correlation. Okay? And, you know, uh, uh, uh, again and again, you know, for the last hundred years, people get excited that, you know, "Doesn't this mean that I can send a message faster than light?" And again and again, for a hundred years, it has to be explained to them, "No, it doesn't mean that." Okay? [laughter] Because, you know, you get to measure, but you don't get to choose the outcome of the measurement, right? And that's what would be needed to actually send a message faster than light. So, this actually upholds the letter of, you know, Einstein's relativity, uh, even though it is in a weird kind of tension with it. And, uh, you can do experiments with entangled particles whose results you could not explain without the entanglement. And if you've heard of the Bell inequality, which was this huge discovery from the 1960s, uh, that's what that is about. Okay?
Okay. But now, uh, uh, where we really get excited in quantum computing is when you have not just two qubits, but a lot of qubits. Okay? Why, why is that exciting? Well, if you have three qubits, uh, now we need eight amplitudes to keep track of its state, right? For 000, for 001, and so forth. If I have 50 qubits, I need 2 to the 50th power amplitudes. Okay? That is, uh, uh, uh, I mean, you can, you can fit that on, you know, the, the biggest supercomputers on the planet, but you really do need something like that. Okay? If I have a thousand qubits, now I need 2 to the thousand amplitudes. Okay? That is way more than I could write down in the whole observable universe, even if I used like every atom to to store another amplitude. Okay? So, uh, quantum mechanics has been telling us, you know, for a century, you know, this is right there in Schrödinger's paper from 1926, uh, that, you know, just to keep track of what a thousand measly particles are doing, in some sense, nature, you know, off to the side where we never see it, uh, must be maintaining a scratch paper with 2 to the thousand power parameters in it. Okay? More than would fit in the whole, you know, visible universe. And every time something happens to those thousand particles, nature has to cross off everything in that scratch paper and replace it with new parameters, right? That is a staggering amount of work for nature to be going to. Uh, uh, and, um, you know, chemists and physicists have, of course, known this for generations. They've known it mostly as a practical problem, right? Go, if, if you're trying to, uh, solve, you know, quantum mechanics to understand, you know, some relatively complicated, you know, even a fairly simple mo-, even the H2O molecule, for example, right? Or even, you know, fairly simple atoms, right? You have this giant number of amplitudes to keep track of. Uh, this is why people, you know, use some of the, the, the, the best high-performance computing in the world for simulating quantum mechanics. And even then, they can't do everything they want. They can, you know, they often have to resort to heuristics and tricks and approximation methods, uh, that don't always work. And so, it was not until, uh, the early 1980s that a few physicists, most famously Richard Feynman, if you've heard of him, uh, David Deutsch, um, started saying, "Look, if nature is giving us this computational lemon, why don't we make lemonade out of it?" You know, why don't we build a computer that itself would be made of qubits, that itself, uh, would, would take advantage of this exponentiality of amplitudes and of entanglement and of interference among the amplitudes. Okay? But, you know, of course, uh, you know, they immediately face the question, "Well, supposing that you built that quantum computer, what is it good for?" Uh, and at the time, they really only knew one answer. Uh, it's good for simulating quantum mechanics itself, right? And, you know, that, that's kind of obvious. And yet, you know, 45 years later, you know, we, we're still, uh, uh, struggling to improve over that answer. Uh, you know, we've, we've, we've, we've had a few successes, as I'll tell you about. Uh, so, okay.
So, now we, we can really get to the heart of, of how a quantum computer would give a speedup and how it would not. Okay. And now, you know, if you read pretty much any popular article written about quantum computing for the past 30 years, okay, they say something that sounds, you know, irresistibly good and that anyone can understand. The only problem is, it's wrong. Okay? What, what they all want to say is, "A quantum computer is just a computer that can try every possible answer in parallel." Right? A classical computer, you know, just has to try, you know, each one, one, one at a time, because a bit has to be either zero or one. But a qubit can be zero and one simultaneously. And that means that you get to try each answer in a different parallel universe and then just magically pick the best one. Right? Now, like, if that was how it worked, like, that, you know, yeah, that would, that would certainly change the world, right? That would, uh, uh, uh, but, you know, that, that might s-, you know, there might be, uh, something in the back of your mind like, you know, "Isn't that too good to be true?" Um, so here's the key. Okay? It is true that with a quantum computer, you can make a superposition, an equal superposition over all the possible answers to your problem. For example, all the possible, uh, uh, keys to a cryptographic code, or all the possible solutions to some gigantic optimization problem, right? That's even an easy thing to do with a quantum computer. Okay? But for a computer to be useful, at some point, you have to look at it. You have to get an output. You have to measure, right? And if you just took an equal superposition over all the answers and you measure, not having done anything else, the rules of quantum mechanics that I showed in the previous slide, uh, tell you that what you're going to see is just a random answer. Okay? Well, if all you wanted was a random answer, you should have just taken a quarter out of your pocket and flipped it, you know, a bunch of times, right? Or just used a, a random number generator on a classical computer. You should have saved the billions of dollars that it took to build this quantum computer. So, okay. So, the, uh, musical interlude. Okay. So, all right. So, uh, uh, uh, uh, for that reason, uh, uh, uh, uh, the only hope of getting, uh, an advantage from a quantum computer is to exploit the way that these amplitudes, being complex numbers, work differently from probabilities. Okay? And with every quantum algorithm, the game we're playing is we're trying to choreograph a pattern of interference. So that, uh, for each wrong answer, some of the contributions to its amplitude are positive and others are negative. So, or that are pointing every which way in the complex plane, let's say. So, on the whole, they're canceling each other out to zero, right? Whereas for the right answer, we want all the different contributions to its amplitude to be pointing in the same way. Okay? If we can arrange that, then when we measure, we're going to see the right answer with a high probability. Now, if we don't see it, we can always just repeat a few times until we do. Okay? But we're trying to use inter-, quantum interference, uh, to boost the probability of seeing the right answer, uh, to beyond what we could have gotten classically. Okay? The tricky part is, we have to, we have to do this despite not knowing in adv-, ourselves in advance which answer is the right one. If we already knew, what would be the point? We also have to do this faster than any classical algorithm could do the same thing. Okay? And in practice, that is often the sticking point. Okay? Because classical algorithms can be very, very clever. We don't know their limits either. Right? And the classical side gets to fight back. Okay?
So, you know, what is this actually good for? It is as if nature has given us a hammer that is weirder than any science fiction writer would have had the imagination to invent. And then we have to figure out, like, what nails, if any, can that hammer hit, you know, besides the obvious one of simulating quantum mechanics itself. So, what are the main applications of quantum computing? Uh, you know, the way I think about it, they basically fall into three categories. Okay? So, now, uh, um, the first one, you know, now, you know, there was, in fact, a huge, uh, bombshell that came in 1994, uh, um, uh, by this guy, Peter Shor, when he discovered that, uh, there is a fast quantum algorithm for certain specific problems in number theory, uh, uh, such as finding the prime factors of a huge composite number. Okay? This problem, you know, uh, uh, it is not as simple as just, you try every possible divisor in parallel. If it were that simple, you would not have needed Peter Shor to think of it. Okay? Uh, it is, uh, uh, you know, exploiting very special structure in this problem, factoring, okay, where you can reduce it to finding the period of a periodic function, and that in turn, you can do using something called the quantum Fourier transform, which Shor then had to show how to do with a quantum computer in a short amount of time. Okay? The Fourier transform is all about revealing periodic patterns, right? Revealing, uh, decomposing a signal into a sum of of periodic components. And that's exactly what you want here. And, uh, for sort of reasons of, you know, classical number theory, that lets you do things like factoring, discrete logarithms, problems involving elliptic curves. Now, why do any of us care about that? Well, it so happens that most of the encryption that protects the internet, then, you know, in the '90s and still to this day, depends on the belief that those particular problems are hard. Okay? That was kind of bad luck, right? Uh, because, because what Shor's algorithm shows is that if and when someone builds a really scalable quantum computer, then all of that cryptography can be broken. Okay? So, that includes, you know, uh, everything that is protecting your credit card, you know, whenever you're sending information over the web using HTTPS, for example. Uh, uh, it includes the signature schemes of Bitcoin and other cryptocurrencies. Okay? As soon as we have a scalable quantum computer, you know, if Bitcoin has not upgraded by then to use post-quantum cryptography, then Bitcoin is broken. You know, its value goes to zero. >> Okay. Um, you know, there is, I should say, like, about a hundred billion dollars worth of Bitcoin, apparently, in, uh, early wallets, you know, that that that that are only protected by elliptic curve cryptography, uh, you know, which could then just immediately be be taken, you know, uh, um, uh, and, uh, you know, so, so, you know, a lot of, uh, uh, uh, uh, people in cybersecurity are very well aware of this. They are trying to migrate right now to, uh, to other cryptographic codes, uh, that we don't know how to break even with a quantum computer, right? And, and, again, like, if you just thought a quantum computer tries every answer in parallel, then you wouldn't understand this, because then it could break any cryptographic code, right? But no, you know, it's this interference effect, right? Which is a very, very specific thing, okay? And it breaks certain codes with the right kind of mathematical structure, and it doesn't break others, as far as we know. So, uh, okay. So, this is certainly like a huge deal for, uh, uh, for the world. We'll have to adapt to this. Uh, uh, uh, uh, this is not necessar-, this is not so obviously a positive for humanity. Uh, you know, it's for positive for whichever intelligence agency gets it first, especially if no one else knows that they have it. So, uh, so moving on to things that seem more positive for humanity.
I think we basically have two categories. The first is the one that I told you about before: simulating quantum physics and chemistry themselves. This could be useful potentially for designing new drugs, for designing new materials, uh, better batteries, uh, uh, um, um, more efficient, uh, photovoltaics, uh, uh, high-temperature superconductors, you know, better ways of making fertilizer, right? There's no guarantee with any of these things, right? You know, we don't know if the better materials or the better chemical reactions even exist, okay? But it seems like it would surely help to have this general-purpose programmable quantum simulator, uh, where instead of having to go and do the experiment, you know, synthesize the molecule for each thing you want to try, or instead of having to struggle to fit this exponentially large amplitude vector, you know, or pro-, into a classical computer or approximate it with one. We would just have this general-purpose quantum simulator. So, uh, so this is where I think most of the real economic value is, as far as we know, right? And then my third category is everything else. Okay. So, there's, you know, been a huge amount of research on to what extent could quantum computers help, for example, with AI, with training of neural nets, with optimization, uh, with, you know, combinatorial search problems. Uh, and here, I think the story is much more mixed. Okay? So, there is a famous quantum algorithm called Grover's algorithm. That's Lov Grover. You know, it is maybe the second most, uh, uh, uh, important quantum algorithm after Shor's. Uh, Grover's algorithm is much, much broader in application than Shor's algorithm. Okay? It, it can speed up the solution of pretty much any search problem, like any case where you're looking for a needle in a haystack. Uh, but the drawback is that the speedup is less dramatic. Okay? So, Shor's algorithm basically lets you factor an n-digit number using a number of steps that grows only like n-squared, roughly, whereas the best known classical algorithms take a number of steps that grows exponentially with n, actually with the cube root of n. But it's, it's exponential growth. Uh, so that, so that is what that is why we call it an exponential speedup. Grover's algorithm lets you take a problem of searching through a list of n possible solutions. So, classically, that takes about n steps, and it lets you solve it with a quantum computer in about the square root of n steps. Okay? So, that's, that's good. You know, you take it, right? But, uh, it's a more modest advantage. Okay? And in practice, you know, that, what that means is that, you know, that it's going to be a lot longer before Grover's algorithm becomes a win in practice, because running a, a, a fault-tolerant quantum computer at all will incur an enormous overhead, right? Like, uh, your basic operations will be, you know, much, much slower than we can do with a classical computer. So, then the relevant question is going to be like, "How large does n have to be before, let's say, a million times the square root of n is less than n?" Right? And, you know, yeah, when n is big enough, then, then that that will become a win, but it only becomes a win once n is in the trillions. Okay? So, that's Grover's algorithm. Eventually, it helps with AI and optimization and all those other things, but only modestly, probably not for a, a while, right? And so, then there's been a search ever since to try to find quantum algorithms that will give bigger speedups for optimization and machine learning and AI problems. And, you know, there's a bunch of interesting things that people have discovered. You know, it's a very complicated, evolving story. Uh, uh, but, you know, in, in the meantime, people learn that they can just say that quantum computers will speed up all of this stuff exponentially. And people will eat that up with mustard, right? But, you know, since, you know, if, if that's what you wanted to hear, you, you know, there are many, many people who will tell you that, but since you came to my talk, uh, uh, I'm going to tell you the truth. Okay?
Now, what I like to say is, for me, that, you know, for me personally, the, the real application of a quantum computer has never been, you know, uh, uh, for AI, or for breaking cryptography, or even for quantum simulation. No, for me, the real application has always just been disproving the people who said that quantum computing was impossible. Right? There are still, you know, as I said, you know, you, if you go to my blog, you will see people who just with utter serene confidence, they say, "Well, if quantum mechanics says that you can solve factoring in, you know, n-squared time, then so much the worse for quantum mechanics. Right? That's just an absurd prediction, and, you know, something is wrong with the physics. What it is, I don't really care. You know, I'm not a detail person, but, you know, you..." [laughter] "...know, but, you know, these, these devices just cannot possibly work." Okay? I want to be able to go to those people and say, "Give me your 20,000-digit integer, right? I will give you its factors." And at that point, there will not be more to argue about, right? I want to rub these people's faces in the real, in the reality, in the truth of quantum mechanics. And if that's wrong, if quantum mechanics, if building a quantum computer leads to the discovery that quantum mechanics is actually false, then I want to do it even more. Okay? Because that's Nobel Prizes for all of us. That's the biggest revolution in physics for a century. Okay? Not what I expect. I expect the more boring, more conservative outcome that quantum computers will merely be possible. Okay? But, you know, let's, let's know the truth, you know? And, but, you know, this is, for some reason, this is not the case that resonated with the funding agencies or with the venture capitalists, even though I think it's the most honest case. Okay?
So, you know, in theoretical computer science, we sort of organize our, we like to organize problems into these classes and give them these weird sequences of capital letters. You know, physicists are much better than us at naming things. They call them, you know, quark, black hole, right? We're stuck with non-deterministic polynomial time. Okay? But, you know, this is, this is sort of our world map where, you know, the, the real holy grail of computer science has for, uh, 60 years has been what are called these NP-complete problems. Um, so, just to explain what this means, P stands for polynomial time. It's the class of all the problems where there is an algorithm running on a conventional computer, like the one in your pocket, let's say, that uses a number of steps that grows at most like the number of bits in the input, uh, raised to some power. So, like a linear time algorithm, a quadratic time algorithm, you know, O(n), O(n^2). Okay? And most of what we do with our computers on a day-to-day basis involves solving problems in P. Uh, uh, NP stands for, as I said, non-deterministic polynomial. It's all the problems where if someone gave you the answer, then there's a fast algorithm for checking it. Okay? But it might take exponential time to find that answer. So, uh, uh, factoring, very famously, is an NP problem. Okay? Because, you know, however hard it is to find the prime factors of a giant number, if someone hands them to you, you know, it's pretty easy, at least for your computer, to multiply them and to check that they are correct. Uh, uh, the NP-complete problems are, in some sense, the hardest problems in NP. Okay? They're the NP problems that if you could solve those, then you could solve every other NP problem. Okay? The huge discovery in the 1970s that really started theoretical computer science as we know it today is that tons of the problems that we really want to solve, uh, uh, in practice, you know, the famous traveling salesman problem, uh, uh, uh, sort of bin packing, you know, uh, uh, uh, all sorts of, uh, op-, um, um, optimization and scheduling problems, uh, they're all NP-complete. Okay? Uh, and now, uh, quantum computing comes along, and it, it sort of, uh, uh, um, it does something to this picture. Okay? So, this is BQP, bounded-error quantum polynomial time. I drew it with this wavy border because, you know, everything quantum is spooky and weird, right? Uh, BQP contains classical P. So, anything that a classical computer can do, a quantum computer can do as well. Okay? Uh, for, for, for most of it, you wouldn't want a quantum computer, right? Like, people say, "Well, will we use quantum computers, you know, for, for playing video games, or for sending email, or, you know, when will I have one on my desk to do those things?" And like I say to them, it's like, "Would you use the space shuttle to taxi people around a parking lot?" Right? It's like, it's not that you couldn't, it's just that there's not a point, right? [laughter] Uh, so, uh, uh, you know, what, what, what, what we really care about is, you know, is there anything in BQP that is not in P, right? And what Shor's great discovery was is that this factoring problem is in BQP, okay? Which means that either BQP is really bigger than P, or else factoring has to be in P, right? Or else there is a fast classical factoring algorithm as well, you know, something that no one has ruled out. Uh, and the other direction, you know, we don't know whether BQP is contained in NP, which means there could be problems that a quantum computer can solve where a classical computer cannot even check the answer in a reasonable amount of time, let alone finding it. Okay? That will be a very relevant point for us, uh, uh, uh, uh, later. Okay? Uh, uh, now, you know, as far as anyone could prove, right, you know, we can't even formally rule out the possibility that all of these things and or collapse down to P, right? Uh, so, you know, the greatest unsolved problem in, uh, theoretical computer science, maybe the greatest in all of mathematics, is called the P versus NP problem, right? Just to prove that NP is larger than P. Um, you know, and so, uh, uh, we can't do that. And so, certainly, we can't prove today that BQP is larger than P. You know, uh, we, we can't do it. But as quantum computing people, it's not our fault. Okay? It's just that, uh, uh, ma-, mathematics has not advanced to the stage of being able to like prove these classes are different. The most we can do is to say, like, "Well, either they're different, or else factoring is in P," stuff like that. Okay? So, that's just a little picture of how this fits into theoretical computer science, uh, how quantum computing fits into it, you know, as we've understood it since the 1970s. Uh, so, so let's come back to this question of, you know, what else could a quantum computer be good for? And, you know, as I said, there's been a lot of excitement about, well, you know, maybe, uh, uh, it, uh, uh, we could get more than the Grover speedup for optimization problems or machine learning problems. Maybe, you know, even if we can't prove it, you know, maybe, maybe in practice, you know, we'll have heuristic quantum algorithms, and they'll, and they'll get these speedups for reasons that no one really understands, okay? Just like modern AI, you know, is changing the world even though no one actually understands how it works, okay? Right? No one has any theorem that says if you train, you know, a, a neural net on all the text on the internet, then it will start you conversing intelligently. Okay? But just, you know, my, uh, friends or former friends at OpenAI just went and did that, and it worked. Okay? So, maybe it'll be the same with quantum algorithms, right? We'll just throw them at these machine learning and optimization problems, and they'll give us this amazing performance. So, uh, there was a lot of discussion around something called the adiabatic algorithm, which is, uh, very much trying to do that. Here's the problem. The problem is, if, if you want to be honest in this field, you have to compare against the best heuristic algorithm running on a classical computer, right? Which could also work very quickly for reasons that no one understands, right? And you, you know, and what matters is the differential between the two, right? So, again and again, people will go to the press saying, "We use a quantum computer to, you know, do this neural net thing, to to recognize handwriting, to route vehicles," and people will just say, "That's, you know, that, you know, that that's a huge achievement," right? And they don't even reach the point of asking, you know, what to us would be the only relevant question, which is, "Are you beating the best classical heuristic?" Right? When you compare them head-to-head, and of course, the reason they don't ask is that the answer is no. Okay? Um, so, but, you know, we, we have people have found examples, or, you know, you can construct artificial examples, basically, where there seem to be very large quantum speedups, you know, using this, uh, these quantum annealing methods of, for example, uh, um, the thing we don't know is whether those, whether anything like those examples will ever show up in practice. Right? So, like, uh, uh, so, so I would say that the, the quantum speedups that we, that we have for optimization and machine learning, they tend to be at least one of modest, or, um, spe-, highly specialized, or speculative. Right? So, uh, uh, um, you know, and, and the challenge is to, is to get one that is that is sort of, uh, uh, uh, broad and exponential, and we're confident that it's real. Okay? Uh, so, you know, there's been a lot of excitement also since the mid-2000s about a different class of quantum algorithms that let, sort of, do linear algebra on exponentially large matrices and vectors and do it in polynomial time, right? So, there was this
The famous HHL algorithm, it was called after Harrow, Hassidim, and Lloyd. Uh, that, um, you know, seems to let you invert an N by N matrix in some sense in only log of N time, right? So that sounds amazing. People got excited about that.
The catch is, what it does is it maps a quantum state representing your input to a different quantum state representing your output. Okay? And now Treble was like, well, to actually be useful, first of all, you need a way to prepare the input state. Second of all, you need a way to measure the output state in a way that where you would actually learn what you wanted to know. And there's not a fast classical algorithm that would tell you that same thing, right? So, so, you know, HHL kind of, you know, wiped their hands at that point. They say, "Our job is done, right? You figure out what this is good for." Okay?
But, so, so often with these quantum machine learning speedups, uh, the hard part is to find what we call an end-to-end speedup, right? It's very easy to get what looks like an exponential speedup when you're just talking about transforming quantum states. But in the at the end of the day, we want to start with a classical input and end with a classical answer and get from one to the other exponentially faster than we could do it classically. Okay.
So, you know, here's a little case study just to show you the the difficulty of this subject. So in 2016, uh, there was a really nice quantum algorithm, uh, due to Curonus and Pash, uh, for, uh, an actually practical machine learning problem. Uh, it was related to recommendation systems like Netflix, you know, that have to recommend products to users based on partial data. Okay. And they said, "Under these clearly stated assumptions, we get an exponential quantum speedup over any known classical algorithm for this task." And I said, "Good, this is exactly the kind of thing I've been asking for. Now all that's left is to prove that this speedup is real." Okay.
So I had, this was my first year at UT. I had this amazing, uh, 18-year-old, uh, uh, uh, undergrad in my course named Ewin who wanted to do a project with me. And I said, "Okay, can you just rule out a fast classical algorithm for this, you know, recommendations problem and thereby prove the separation between quantum and classical for, uh, for this?" So, uh, you know, I didn't expect her to get anywhere on it, but I thought, you know, it'll be a good learning experience. Uh, she spent a year on it. Okay. She just had one false attempt after the other. And then after a year, she said, "I think I know why I haven't been able to prove this. It's because it's not true." Okay. [laughter] It's, you know, that that's always an obstruction to a proof, by the way. Okay.
But, you know, uh, um, that I think there actually is a a classical randomized algorithm with similar performance to the quantum algorithm. I was skeptical, but I said, "Keep working on it." Uh, she was right. Okay. And then that was, uh, that, uh, that was a real breakthrough. And, you know, building on what Ewin did, uh, uh, most of the other quantum machine learning speedups that were known at that time were then also dequantized, or as I call it, Ewanized. Okay. And, um, uh, you know, so, so intellectually, this is, you know, one of the the best things to have come out of our group for the field of quantum machine learning. It was not so great. Uh, I mean, you know, they were sort of back to the drawing board. Okay.
But, you know, this is what I was saying. You can't just, you know, invent a quantum algorithm. You have to compare to the best that a classical computer could do. Class, the classical side gets to fight back. Okay. So, you know, so, so what can we do? Let's say throw away any goal of doing anything useful. Let's say, can we just prove that a quantum computer can do something, anything that is classically hard? Can we just prove the reality of quantum speedup? So this was a question that I and others started asking around 2009. Okay.
And I worked with my then a student at MIT named Alex Archipov. And we had a proposal for how to do that. We said, "If you just want to demonstrate, you know, the reality of quantum speedup in an experiment, you shouldn't need a full programmable quantum computer for that. You know, there should be much more rudimentary systems that will let you do the same thing." The example that we gave, uh, we called Boson sampling. Okay. And there is basically just, you generate a bunch of photons, you send them through a network of beam splitters, and then you measure where they end up. Okay. So this is a really, really simple kind of setup. Uh, it probably can't even do universal classical computing. Uh, uh, uh, um, but, but we said, "If if your goal was just to simulate this system, that is sample from the same distribution over sort of output states over, you know, where each photon ends up, uh, that this samples from. We gave strong evidence that that should be hard for any classical algorithm." Okay. And we said, you know, and then the quantum optics people got all excited because like, you know, they have photons, right? They know they know a lot about routing them through these networks of beam splitters.
So then starting around 2013, a bunch of experimentalists tried to actually implement our proposal. And at first, they could only do it with three photons. Uh, you know, your classical computer is not going to break a sweat to simulate three photons. Okay. But then it became 10 photons and 20 and and and now it's, they actually do these experiments with thousands of photons, uh, which, uh, uh, you know, as far as we know, should take longer than the age of the universe to simulate with a classical computer. Right? This is now an experiment that that people do. Okay.
Although even before they got to this quantum supremacy, and by the way, I did not coin that term. Uh, uh, if anyone doesn't like it, they should blame, uh, my colleague John Preskill. Okay. Uh, but, you know, this is, this is, this is, this is, this is what he called it. Okay. Uh, uh, uh, so the the first people to plausibly claim this quantum supremacy milestone, uh, were Google, uh, uh, who, uh, built a chip with, um, 50, uh, 53 superconducting qubits, um, which they then put in a dilution refrigerator, which is like this upside-down wedding cake thing here. And they cool it to, uh, a hundredth of a degree above absolute zero. That's what allows the currents around the, the, uh, superconducting coils to to behave as qubits at all. And then they send, uh, control signals to tell the qubits what to do and what, what operations to apply on them, what, uh, unitary operations. Okay.
And so in 2019, uh, you know, they, they said, "Okay, we, you know, we have done this." It's, you know, they, they basically said, you know, "We, we had worked with them. They said, 'We want to do something like Boson sampling but more adapted to our hardware.'" So, you know, we worked out the theory of that. And then Google, uh, actually did it. And there was a lot of arguing back and forth for a few years because Google published this in 2019. They said, "We did this sampling task on our chip in three minutes that we estimate would have taken 10,000 years for a classical supercomputer." And, you know, of course, the press loved that. They ran with that. But then a few weeks later, IBM put, you know, which is Google's competitor in superconducting qubits, put out a paper saying, "No, it doesn't take 10,000 years. Uh, we have a way that Google didn't think of where we can simulate it in a few days on a on a on a classical computer." Okay.
But Google was less worried about that than you might have expected. They said, "Yeah, fine." You know, you know, uh, uh, uh, you know, "We, we expected that, you know, classical costs will come down. But as we scale this up, the quantum computers are clearly going to win." And indeed, that is what has happened. So in 2024, they repeated the experiment, but this time with a 103 qubit chip. And and now, um, you know, we can say, even using the best algorithms that anyone has figured out in recent years, including IBM's, including other people's, including this tensor network contraction and all the fancy things that people have come up with, uh, it looks like simulating their 103 qubit chip would take, uh, about 10 to the 25 on, uh, on the biggest supercomputers that exist. Okay.
There's only one catch, right? The catch is that to check that the Google machine produced the right answer, that would also take 10 to the 25 years. Okay. So that's that, that's a little thing that we're still, uh, working on. Okay.
So, yeah, so here is how I think about the current situation with quantum supremacy experiments. Okay. We basically, we want three things, three properties. First of all, of course, we want to show that we can beat a classical computer. As I said, we want to prove the quantum computing skeptics are wrong. Okay? Uh, so we need that. But then number two, we want something that we can actually implement using devices that we have today. Why? Because we're impatient. Okay? We don't want to wait, you know, how, you know, even if it might just be a few years at this point, no one knows, but, you know, we don't want to wait for a full error-corrected scalable quantum computer. We want to do something today. Okay? And then, and thirdly, we want, uh, a problem where we can actually check the answer. Okay? Uh, uh, you know, either using a classical computer, you know, or using a second quantum computer, or, you know, or somehow, uh, uh, uh, uh, actually prove that the quantum computer, uh, worked correctly. Okay.
And the situation until very recently was that we knew how to achieve any two of these three requirements. Okay. Uh, so what we did with the sampling-based quantum supremacy was to show how to get quantum advantage on a near-term device. Okay. But it wasn't easy to verify. That's the problem, right? Can you, can you verify it up to maybe 50 qubits, right? Using millions of dollars of classical, you know, uh, uh, uh, compute, and and people have done that. Okay. But you can't go up to a 100 qubits. That's the problem. Okay. Uh, if you just want something, you know, near-term and efficiently verifiable, and you don't care whether you're beating a classical computer, well, there's, there's, you know, uh, uh, tons of startup companies that will happily sell you that. Okay. Uh, and then, you know, uh, if you want in-principle quantum advantage and you can check the answer. Well, Shor's factoring algorithm was like the OG version of that, right? Factoring has this wonderful property that, you know, you could be the biggest skeptic of quantum computing in the world. If someone hands you the factors of your number, someone breaks your, you know, uh, uh, uh, cryptographic key, right? You can check whether they succeeded. Uh, uh, but, you know, we haven't known how to get into the intersection of all three of these.
Only just within the last year are there credible proposals, I would say, uh, especially from Quantinuum in Colorado, which is a, you know, trapped ion quantum computing startup that I was just visiting this Monday, and from Google, from their quantum computing lab in Santa Barbara. They have, uh, uh, they have put forward, uh, quantum supremacy demonstrations that that seem to do all three of these things. Okay. Some of them involve what physicists call out-of-time-order correlators, or OTOCs. Uh, you, there are some, we're starting to see some simulations of quantum systems that sort of give us answers that, you know, like, like not samples, but specific numbers that we didn't know how to calculate classically, like related to the Fermi-Hubbard model, which is used in the study of superconductivity, for example. Um, and, you know, and we get these numbers that, you know, we didn't know how to calculate classically. Uh, uh, and, and, um, you know, now, uh, you could check those numbers, if nothing else, by comparing them against a second quantum computer. Okay. Although that, that, that still needs to be done. Uh, and, you know, there's another idea that my student and I proposed just a few years ago, which we called peaked quantum circuits. Uh, here you generate a quantum circuit that looks random, looks like just complete garbage, but it hides secretly a signal in it that causes this circuit, when run, to output one particular output string with over, with a very high probability. Okay. And you, so you do whatever you can to sort of manipulate the circuit to obfuscate that peak. Okay. And there's a company called, um, BlueQubit, that has actually implemented our proposal. And they have these peaked circuits, which they run on the Quantinuum, uh, machine, for example. You see this peak, you know, this hidden output string. It just pops out when you run it on the quantum computer. But it's not obvious, you know, given the same quantum circuit, how a classical computer would figure out this peak. Okay. Just a couple weeks ago, some of their circuits were broken. Someone figured out with a classical computer how to get the peak. Some, uh, some other of their circuits are still standing. Okay. So the cat and mouse game could go on for a while. Uh.
So I had, you know, some other, you know, interesting things that we can do with with quantum computers. Since, uh, uh, time is short, I, I won't say much about it, but, um, um, eight years ago, I realized that these quantum supremacy experiments, which we had designed to be almost gloriously useless, right? They might actually, you know, they might not succeed entirely at being useless. Okay. So, in particular, if you want random, random numbers, right? It's very easy to get random numbers once you know you have quantum mechanics, right? You just measure your qubits, right? You know, randomness is baked into how quantum mechanics works. Right? But a harder problem is, if let's say you need to generate bits that you can prove to any skeptic over the internet were truly random, right? You did not secretly backdoor these numbers. Okay. This is a problem that is faced right now by various cryptocurrencies, such as Ethereum, for example, which has migrated to be a proof-of-stake cryptocurrency. Okay. That is way more energy efficient than Bitcoin, right? You're not using like 1% or whatever of the world's electricity to, you know, invert this hash function uselessly. Okay. Uh, but you have to constantly run a lottery to decide who gets to add the next block to the blockchain. Okay? And everyone has to trust that that lottery is happening fairly. Right? So how do you prove that a bit is actually random? Well, what, what, uh, what I and others realized was that once you are doing these quantum supremacy demonstrations, then they almost for free give you a way of doing that. And basically, it involves you repeatedly send these challenges to the quantum computer. You say, "Run this circuit which you've generated pseudo-randomly, and then give me some samples from its output distribution." And then, you know, given enough time, you can go and check those samples. Okay. Uh, and then you can prove a theorem that basically says, if the quantum computer has passed your challenges and done it quickly, then under some hardness conjecture, even a quantum computer could only do that quickly by sampling the answer randomly. Right? So now you have guaranteed entropy, which you can use to get nearly pure random bits to to use in cryptographic applications. Okay. This is the only thing I've done that I've patented. Uh, through. It's the only thing I've done that's ever been in any danger of being useful to anyone. Okay. We, we licensed this to Google for a while, but, uh, uh, now actually a a collaboration between Quantinuum and JP Morgan Chase has actually experimentally demonstrated this certified randomness protocol. Okay. So we just, we just need to find a customer who wants it. Uh.
So another recent experiment that we did in collaboration with Quantinuum, we showed we can do a quantum computation involving 12 qubits on the Quantinuum machine where we then, you know, randomly decide on how to measure our 12 qubit state and we get some outcomes. We collect statistics. Then we prove that if they were secretly classical bits rather than qubits, then you would have needed way more than 12 of them. You would have needed hundreds of classical bits, probably, or, you know, at any rate, like at least 60 or so. Okay. To explain, uh, these measurement results. So you get an exponential separation between qubits and classical bits. We've actually demonstrated it now, uh, experimentally. And, uh, crucially, this separation, unlike all the other ones, this does not depend on any unproved conjecture about problems being hard for classical computers. This is just a theorem. We can just prove this unconditionally. Okay. Uh, just in the last month, there was a paper from John Preskill's group saying that you could potentially use this quantum information supremacy idea to get exponential space savings for various problem streaming problems that are relevant in machine learning, like support vector machines, sparse linear systems, principal component analysis. Okay. So this is completely different from what we're normally trying to do with quantum computers. It's not a time savings, it's a space savings, right? But this is, uh, you know, there are these new frontiers, right? What I always tell people who are sort of searching for new quantum algorithms is, just don't keep jumping for the same, you know, fruits high up in the tree. Find a different orchard. Okay? Find new problems to look, you know, or new, new tasks. So this is an example.
So, you know, there's lots of ideas for how to build a quantum computer that are sort of being pursued in parallel. I've touched on some of these in the talk. If people want to ask me about that, they can. You know, I also, I had a slide about why is building it so difficult in practice. Um, it's, you know, basically, you know, unwanted interaction between the quantum computer and its environment that we have to, uh, protect against. Uh, and, you know, the only reason why we think that building a scalable quantum computer is possible at all is because of this discovery in the mid-1990s called quantum error correction. Okay. That says that we can encode our qubits, uh, you know, using a large number of physical qubits in such a way that even if some of our qubits sort of get prematurely measured or leak into their environment, we can recover what we need from the remaining qubits. Okay. So the race right now is basically to demonstrate that. Okay. And it is only within the last, literally within the last year, that we have seen hardware that is s sort of can manipulate physical qubits well enough that these, this quantum error correction idea should start to work. Okay. It should start to give you a net win. It should start to correct errors faster than it is introducing new errors. Okay. And that was, you know, Google's biggest headline result from 2024 was the demonstration of quantum error correction to protect, you know, I hope you're sitting down for this one, one qubit. Okay.
So, you know, so here's a sort of outlook. You know, we, we've achieved the sampling-based quantum supremacy. Uh, we're starting to see these verifiable quantum advantages. Uh, what, you know, we're, what I hope will be done this year is to actually verify, you know, by comparing against a second quantum computer, some of these simulations like of the Fermi-Hubbard model. And then we would like to do simulations that are actually interesting to scientists in the relevant fields. You know, even if they didn't care about quantum computing, I would like to give the material scientists or the chemists like a number that answers some question that they had. Okay. And then we can, what a, after that, not before, we can worry about, can we do something commercially useful? And then, can we get to a fully scalable, fault-tolerant device, which has been the dream for the last 30 years. So it's an exciting time for quantum computing. After decades, we finally started to see clear speedups over classical computers for some specialized problems with devices with about a 100 qubits, and even the beginnings of quantum error correction. You know, achieving full scalability and fault tolerance and threatening public key cryptography finally look like they are on the horizon. But please, no one ask me how long, how many years. If I knew how to answer such things, I wouldn't be a professor. I'd be an investor. I'd have a nicer house. Okay. Uh, but we've also seen that quantum speedups are extremely subtle, and they depend on the structure of the problem you're solving. It's not just free exponential parallelism. It's something new and weird. All right. So, thanks for listening. [applause] Thank you so much, Scott. Excellent. Um, yeah, we have time for a few questions. >> I can run around with the mic. >> It's a quick one. >> Yeah. >> How fault tolerant are classical computers? >> Uh, so classical computers are extremely fault tolerant. So your laptop, it probably suffers like a few hardware errors per year, you know, in the microchip, mostly when a cosmic ray comes through, okay, and and hits something. Okay. It is rare enough that you wouldn't normally notice it at all. Uh, uh, if, if you are running a data center on the scale of Google or Amazon, then you actually do have to worry about cosmic rays, you know, causing hardware errors, and they do have a whole infrastructure to deal with exactly that. Okay. But there's a very interesting history here, which is that in the 1950s, John von Neumann invented the whole theory of classical fault tolerance because he was very worried about this, the same thing that we're worried about today with quantum computing. He was worried about with classical computing, how do you build a reliable classical computer out of unreliable parts? And he proved a beautiful theorem saying that in principle, you can do that as long as the rate of error is below some threshold, you know, exactly the same thing that would later be proved in the 1990s, uh, for quantum computation, right? And so von Neumann had this great discovery in the '50s of classical fault tolerance. And then what happened was that the transistor and the integrated circuit, you know, uh, uh, became the way that we build things, and they were so reliable that we hardly even needed any of his work. But for quantum computing, we probably will need the analog of that, uh, certainly for the foreseeable future. >> Um, thanks for the talk. Um, I just have like one question, which was, what is an anyon accord for the for the Microsoft version? >> Yeah. So, all right. This, do we have another hour? I'm, I'm kidding. All right. Uh, and so, so an anyon is a, so, so the, so the particles, uh, that occur in nature fall into two types. They're either fermions or bosons, right? Basically, bosons like to stack up on top of each other. Fermions, uh, never do that. Okay? And, uh, you know, they have different statistics when you swap two identical ones. Okay? But now, if we lived in two dimensions instead of three, then it turns out that there are more possibilities than just those two. You can have what are more complicated statistics, uh, that arise when I swap two identical particles. And so people realized that, I think already in in the '80s or before. Okay. And they developed this whole theory of of what are called anyons. And, you know, at first, this was just kind of interesting physics. But then, um, a guy named Alexei Kitaev, uh, and and his friends, I guess Mike Freedman and and others, in the late 1990s, realized that if you could actually create these non-abelian anyons, which would have to be excitations in some two-dimensional medium, then you could use them to build a universal quantum computer. Okay? Just by braiding them around each other in some appropriate pattern, that would be enough to do any quantum circuit. Okay? And not only that, but the physics of the system would give you some built-in protection against errors, right? And that was really the thing that excited people, right? That like, in order to change the the answer, you would actually have to change the topology of how the, in, like, in what order was which particle braided past which one, right? A local change to the path doesn't matter if it doesn't change the topology. Okay? So, so this, you know, like, if anyone dreamed that like, like what we did with classical computing, which was just to just render von Neumann irrelevant by inventing the transistor, right? And have fault tolerance just built into the physics of our system, right? Like, like, if, you know, uh, like there's been a dream of someday doing that for quantum computing, right? Like, like, if, uh, I would say that non-abelian anyons are the closest that anyone has come to articulating what that dream would look like. Okay? The only problem with it is that to make it work, you have to engineer a new state of matter, which has never been seen in nature. Okay? So Microsoft famously put a huge gamble on this topological approach to quantum computing, which you could say is is like speculative or far out, even by quantum computing standards, right? And, you know, with the other, with the more conventional approaches, we're now at, you know, a 100 qubits, 200 qubits, you know, we're doing fully programmable circuits, thousands of operations. With the, the Microsoft group, with their non-abelian anyons, they're still arguing with skeptics about whether they've succeeded or not at making one topological qubit. Okay? So that's where that is. Okay? Maybe eventually, once it works, it will overtake everything else. You know, hard to say, but that, but that's where it is right now. >> Yeah. >> Yeah. You mentioned the collaboration with JP Morgan. Yeah. And, um, we've heard a lot about JP Morgan's interest. The, uh, I think the head of quantum computing, JP Morgan, became CEO of IonQ, that company you mentioned, and then you hear all this, and I can't believe that their sole interest is for has to do with public key crypto. There must be a real >> driving interest. Yeah. So, so I, I, I, I get some version of this again and again that like, well, you know, you, like, I hear everything that you took, you know, this hour to explain, and yet you can't be right, because if you were right, then these CEOs wouldn't be investing billions of dollars in it, but they are. You know, they must be rational. There must be some galaxy brain thing that you don't know. Okay. The thing is that I've talked to these CEOs. Okay? I've talked to them. And so I, I, I have a sense of what they know and don't know. And basically, you know, the way that they think is different from how we think in science. Okay? In science, you say, okay, this idea, like, does not hold together. It has not been thought through. Come back when you have something, you know, that is more serious. Okay? The way that people in Silicon Valley think is, yes, you know, this hasn't been thought through. This doesn't make any sense. That's why I'm only going to put 50 million on it. Okay? [laughter] Because they don't care if they lose that 50 million. What they care about is if they miss the next Google or the next OpenAI. But >> that's their fe. That's that is their only fear. >> But Ion is $20 billion. It's >> uh, Ion is now valued at 17 billion. That's correct. >> Yeah. Uh, they have, uh, not been, what is the phrase people use these days? Not, they, they've been less than consistently candid, let's say, in in in what they have said to retail investors, what they've said to the public about what their devices can do. Uh, you can quote me on that. >> I mean >> Last question. >> Um, so about, about Shor's algorithm, um, how many qubits do you need to factor an N-digit integer? >> Yeah, it's a, it's a good question. And especially because, you know, the estimate for how many you need has been coming down very, very recently. Okay. So to factor an N-digit number, you know, the number, so, so, so there's, there's two questions here. How many logical qubits do you need? Which is like, how many qubits would you need assuming a perfect or error-free quantum computer, right? And that question, you know, we know a lot about. You can do it with 4N, you know, or if you're willing to use more time, you can even do it with like 2N qubits, something like that. Okay? But then there's the question, how many actual physical qubits do you need? Right? And now this is in large part a question about what error correcting code are you going to use, right? And which error correcting code, now this depends a lot on which architecture are you using, you know, what basic operations does it give you, what is your underlying physical error rate, like what do you have to protect against, right? And so until recently, the estimates were quite scary. Okay? They basically said you are going to need, you know, probably at a minimum like, uh, thousands of physical qubits per logical qubit. Okay? Which means that like, if you wanted to factor, let's say, a 48-bit integer, right? Like cryptographically relevant, then, you know, now we're talking about millions, maybe even tens or hundreds of millions of physical qubits. Okay? And, you know, in principle, you could do that, but, you know, you might mean you have to fill a building with dilution refrigerators, okay, that are shuttling qubits around, and this is what people were talking about. Okay? Now, within the last year, that estimate has come down by multiple orders of magnitude, okay, as mostly because people have realized that there are these much lower overhead quantum error correcting codes, uh, that, you know, they'd been using the, what's called the Kitaev surface code, which had come out of topological quantum computing, and which is very convenient to implement. But there are what are called LDPC codes, low-density parity check codes, that can, you know, at least in the trapped ion and the neutral atom architectures, probably not in the superconducting architecture, they can they can work with a much lower overhead. And so just a month or two ago, there was a paper from Preskill's group at Caltech that said, "We estimate that, you know, we could break Bitcoin, you know, so break 256-bit, say, elliptic curve cryptography using only about 30,000 physical qubits." Okay? And, you know, maybe it would take a few days per key that you wanted to break. Okay? And you get similar estimates for factoring, maybe maybe a couple hundred thousand. Right? This is still kind of a lot. It's still certainly beyond what we have now. But, you know, based on this, people I respect a lot have have been saying, you know, "We think, you know, this ought to be possible by 2029, 2030, something like that." Are they right or not? I don't know. But I think, uh, uh, I am, I have now moved to clearly recommending people upgrade to post-quantum cryptography, or at any rate, like, don't come and tell me that I didn't warn you. Any last urgent questions or? Okay, thanks so much, Scott, again. [applause]