The following is a conversation with scott aaronson, a professor. U t austin director of it's quantum information center and previously a professor at mit, his research interests center around the capabilities and limits of quantum computers and computation complexity. Theory. More generally, he is an excellent writer and one of my favorite communicators of computer science in the world. We only had about an hour and a half of this conversation, so I decided to focus on quantum computing, but I can see us talking again in the future on this podcast at some point about computational complexity, theory and all the complexity classes. This card catalogs in his amazing complexity, zoo wiki, as a quick aside, based on questions and comments, I've received my goal with these conversations is to try to be in the background.

Without ego and do three things, one, let the guest shine and try to discover together the most beautiful insights in their work and in their mind, to try to play devil's advocate just enough to provide a creative tension and exploring ideas to conversation and three to ask very basic questions about terminology or concepts about ideas. Many of the topics we talk about in the podcast I've been studying for years as a grad student as a researcher and generally as a curious human who loves to read. But frankly, I see myself in these conversations as the main character for one of my favorite novels, but as the yassky called the idiot I enjoy playing don.

clearly, it comes naturally, but the basic questions don't come from my ignorance of the subject, but from an instinct that the fundamentals are simple and if we linger on them from almost a knave perspective, we can drawn an insightful thread from computer science to neuroscience to physics, the philosophy and the artificial intelligence. This is the artificial intelligence podcast the enjoy. It has youtube good, five stars and apple pie, gas or a patron or simply connected me on twitter lex Friedman, spelled f r I d m a n as usual I'll do one or two minutes of ads now and never any ads in the middle. That can break the flow of the conversation. I hope that works for you and doesn't hurt the listening experience. Quick summary of the ads to supporters today. First get cash app and use the code legs

podcast? Second, listen to the techmeme ride home podcast for tech, news search, ride home to words in your podcast app. This show is presented by kashyap the number one finance app in the app store when you get it use code lex, podcast cash app lets you send money to friends, buy bitcoin and invest in the stock market, with as little as one dollar broker services provided by cash up investing a subsidiary of square, a member, as I p c, since cash app does fractional share trading. Let me mention that the order execution algorithm that works behind the scenes to create the abstraction of fractional orders is an algorithmic marvel. The big props to the cash app engineers for solving a hard problem that, in the end, provides an easy interface that takes a step up to the next layer of abstraction over the stock market. Making trading more accessible for new investors and diverse

geisha and much easier. So again, if you get cash out from the app store google play and use the cove lux part cast you'll get ten dollars in cash apple also done it, and I was the first one of my favorite organizations that is helping to advance robotic systemic occasion for young people around the world. This episode is also supported by the tec. Meme ride home podcast. It's a technology podcast I've about listening to for awhile and really enjoying it go straight to the point gives you tech news you need to know and provides minimal, but essential context is released every day by five pm eastern and is only about fifteen to twenty minutes, long for fun alike. Billing apps on smartphones, most android samo, was a little curious about new flagship phones that come out. I saw that samsung announced the new

galaxy. As twenty and, of course, right away, tat mean right. Home has a new episode. That summarizes all that I needed to know about. This new device have also started to do weekend, bonus episodes of any views of people like a well founded steve case and investing and gary marcus Annie. I, who I've also interviewed, and this podcast you can find the tec meme ride home podcast. If you search your podcast ab for a ride home, two words then subscribe enjoy and keep up to date with the latest tech news and now here's my conversation with Scott harrison.

I sometimes get criticism from a listener here and there that, while having a conversation with a world class, mathematician physicists your biologist airspace engineer or a theoretical computer scientists like yourself, I waste time by asking philosophical quest since about free will cautiousness mortality, love nature of truth, super intelligence, whether time travel as possible, whether space time is emerging from the mental, even the crane. Questions like whether aliens exist with their language might look like what their maths might look like, whether math is inventor discovered and, of course, whether we live in a simulation or not. So I tracked with it out with it. I treaded dance back and forth from the deep technical to the

A soft gaza would have done that quite a bit to your world class computer scientists, and yet you have written about this very point. The philosophies important for experts in any technical discipline, though they somehow seem to avoid this. So I thought a peerage thing to talk to you about this point. Why should we compare cited? mathematicians, physicists care by philosophy. Do you think will I would rephrase the question a little bit, I mean philosophy. Almost by definition is the subject of concern with the biggest questions that you could pass. We ask right, so the ones you mentions right are are living in a simulation. Are we alone in the universe? How should we even think about such questions? You know is the future. the term in than what the? What do you mean by being determined Why are we alive at the time? We are not at some other time, you know, and

When you, when you sort of content, the enormity of the questions? I think you know you could ask well, then why Why be concerned with anything else? Why, Why not and your whole life. On those questions. I think I think in some sense that is the right click away, the phrase, the quest and you and and and and actually we know what what we learned I mean throughout history, but really starting with the scientific revolution with with gatt yo, galileo, and some one is that there is a good reason to you know, focus narrower questions in a more technical, yo, mathematical or empirical questions, and that is that you can actually make progress on them. could actually often answer them, and sometimes they actually tell you something about the philosophical questions. That sort of me, no, maybe motivated your curiosity, is a child right. Do you know they dont necessary we resolve the philosophical questions, but sometimes they,

me frame your whole understanding of them right and so, for me, philosophy is just the thing that you have in the background. From the very beginning, that you want. Do you know the unity are these are sort of the reasons why you went into intellectual life in the first place, at least the reasons why I did. but you know math and science are tools that we have for you know actually making progress? And you know, hopefully even No changing our understanding of these philosophical questions, sometimes even more than philosophy itself does what what do you think computer scientists avoid these question will run away from them. A little bit, at least in the technical scientific discourse. Well, I'm not I'm not sure if they so more than any other scientists I mean, I mean it I mean I mean I mean Alan turing was famously you know interested in. You know his is the most famous one of his two most famous papers

was in a philosophy journal mind. You know it was the one where he propose the turing test He took a wittgenstein course at cambridge argued with them I recently learned that the little bit and it's actually fascinating- and I I I was- I was trying to look for resources in trying to understand where the sources of disagreement and debate between with consign and touring warm, that's an interesting that these two minds have somehow in the arc of history, yet were whether the transcript of their the course, which was a night, Thirty, nine ray is one of the more fascinating documents that I've ever read, because you know of it can Steiner's is trying to say, while all of these these form systems are just a complete. relevancy is right. If a formal system is irrelevant. Who cares? You know why, that matter in real life, right during a saying. Well, look, you know if you,

it was an inconsistent formal system to design a bridge over the bridge, move may collapse anita. it's, a touring in some senses, thinking decades ahead, you know, I think, of aware of it can shine as to where the formal systems are actually going to be used. You know in computers I do do things in the world it interesting. That touring actually dropped the course halfway through. Why? Because he had to go to watch we park, and you know Work on something of more immediate importance. That's tracing the anchor step from philosophy to actual, like the I guess possible, step to actual engine with the actual real impact yeah, I would say more generally right in a lot of scientists. Are you know, interested in philosophy, but there also busy and they have you know a lot on their plate, and there are a lot of sort of very concrete questions. that are already you know not answered, but you know look like they might be answerable right, and so then you

I say well, then, why you know a break your brain over these. You know metaphysically, unanswerable, questions when there were all of these answerable ones instead, so I think you know for of for me. I enjoy talking about food, they are even go to philosophy conferences. Sometimes such as the unesco excise France's. I enjoy interacting with philosophy I would not want to be a professional philosopher because I like being in a field where like you know, you know I get to confused about the sort of eternal questions than I can actually make progress on something maybe later on that for just a little longer yeah. What do you think is the difference. The corollary of the criticism that I mentioned previously.

that why ask the philosophical questions in the mathematician is, if you want to ask for some questions that invite a real philosopher and ask them. So what's the difference between the way computer scientists are mathematician, ponders a philosophical question in a loss of partnership was awful question? Well, I mean I mean a lot of. It just depends on the individual right, it's hard to make generalizations about entire fields, but you know, I think, I think if we, if we, if we tried to traitor stereotype. You know we would say that, and us up scientists very often will be less care fall in their use. Words, you know I mean philosophers are really experts inside of you know, like when it when it. When I talk to them, they will just pounds if you now use the wrong phrase for something I regard as a very nice words, you could say colors.

Where is the hour or you know they will? They will sort of interrogate my word choices, let's say to a much greater extent than scientists word right under and scientists. We will often, if you ask them about a philosophical problem, the hard problem in ink of consciousness or free will or whatever they will try to related back to in a recent research research about about biology or even being the best of all, was research that they personally are involved. Right right and you know, and and and and you know, of course they will want to talk about that. You know, and it is what they will think of you know in the in. Of course, you could have an argument that may be you know it. It's all interesting. as it goes, but maybe none of it touches the philosophical question, but you know, but maybe You know as a science, you know, at least it is, as I said, it does tell us concrete things, and you know even have

a deep dive into neurobiology will not answer the hard problem of consciousness. You know, maybe it it can take us about as far as we can get toward you know expanding our minds about it. You know toward thinking about it in a different way. when I think neurobiology can do that? But you know with these profound philosophical questions I mean also art and literature: do that right either all different ways of trying to approach these question Is there a weed out for which we don't even know really what an answer would look like by it, and yet somehow we can't help but keep returning to the questions

and you have a kind of mathematical, beautiful mathematical. When discussing this with the idea of Q, prime I'll right, you're right, they usually the only way to make progress on the big questions like the full of the philosophical questions are talking about now, is to pick off smaller sub questions, ideally sub questions you can attack using math and empirical observation. Are both you define the idea of a cue prime so given? on an unanswerable, thus off goal riddle q replace it with a merely in quotes scientific, a mathematical question, q, prime, which captious part of what people I wanted to know when they first asked q. Yes, then, with the lock once ask you prime tell you you describe some examples of such q, prime some questions in your long essay titled. Why philosopher, should care about competition complexity?

The catalogue of various q primes and wish you think, I'm a theoretical can be a size has made progress. Can you mention a few favorites if any pop to my mind, during the Uruguay round us out, so I mean, I would say some of the most famous examples in history of of that sort of replacement. Were I mean I'm into to go back to Alan turing right what he did in his computer. Machinery and intelligence paper was exactly you know, explicitly started with the question. Can machines think and then he said sorry, I think that question is to meaningless, but here's a different question. You know: could you programme a computer so that you couldn't tell us difference between it and the human rights and yet Yes in the very first, you sense is he in fact just yellow most acute prime deepwater face. He does precisely that or you know we could look at at at at dirdle. Right, where you know you. You had these by philosophers arguing for centuries ago,

The limits of mathematical reasoning are to the limits of formal systems, and you know, then, by the early twentieth century logicians. You know, starting with you know friday right saw, and then you know most spectacularly girl. all. He managed to refrain those questions as what we have these formal systems they have. These definite rules are. There are questions that, can phrase within the rules of these systems that are not provable within the rules of the systems and can we prove that fact right, and so that would be another exit boy. You know how I had this essay called the ghost in the quantum touring machine is not one of the crazier things written, but I yeah I tried to do something's gonna do to advocate doing something similar there for free will, where ovens, I am talking about. Is free will

real, where we get hung up on the meaning of. What exactly do we mean by freedom? And can you have? Can you be you know, or do we mean compatible list free will? libertarian freewill? What are these things mean? You know I suggested just asking the question: how well in principle consistently with the laws of physics? Could a person's behaviour be predicted? without so, let's aid destroying the person's brain. You know taking it apart in the process of trying to protect them. and you in and that actually asking that question gets you into all sorts of media and interesting issues. You know issues of what is the computational substrate of the bridge. and you know- or can you one? your stay and the brain? You know just at the sort of level of the neurons, you know at sort of the abstraction of a neural network, or do you need to go

deeper to the you know a molecular level, ultimately even to the quantum level right and, of course, that would put limits on predictability. If, if you did so, you need to reduce any to reduce the mind to to a computational device like formalize it. So then you can make predictions about What do you know whether you could predict belong? If you were trying to predict a person yet, then? Presumably you would need some model of their brain right and now the question becomes one of how accurate can such a model, because can you make a model that will be accurate enough to really seriously threaten people's sense of free? Will, you know not just metaphysically but like really I written in this envelope what you were going to say next, I seen accuracy right term here. So much is this

the level of abstraction has to be right. So few of you, if your accurate at these some somehow at the quantum level that may not be convincing to us at the human level well outright, but to put the question what accuracy at these sort of level of the underlying mechanisms do you need in order to predict the baby you're right at the end the day the task is just can you, you know foresee what the person is going to do right. I am you know and and and and and you know and and and and in discussions of free will, you know it's seems like both sides want to. You know very quickly dismissed. That question is irrelevant. Well to me, it's totally relevant okay, because in a way of? If someone says oh well, you know I will allow applause demon, they knew the complete state of the universe. You know, could predict ever then you're going to do. Therefore you don't have free. Will you know that that it doesn't trouble me that much because

well. You know I've never met such a demon right eye ida and and we you know, we even have some reasons. The thing you know, maybe it you know it could not exist as part of our world, and you know it was only an abstraction. Thought experiment. On the other hand, if someone said I have this brain scanning machine. You know you step into and then you know every paper that you will have a right, it will right. You know everything that you will have you know even right now about the machine itself, it will first day you know if you can actually demonstrate that, then I think you know that that you know that that sort of threatens my internal sense of having free will in a much more visceral way. You know, but now you notice that we're asking an m p a much more empirical question. We're asking: is such a machine possible or isn't it we're asking if it's not,

the ball than what in the laws of physics or what about the behaviour of the brain prevents it from existing? So if you could philosophize a little bit within this empirical question at where do you think would enter the the by which mechanism would enter the possibility that we can predict the outcome? So there would be something, though, be akin to a free will well could save ii, these out of obvious possibility, which was recognised by adding ten and many others about as soon as quantum mechanics was discovered in the nineteen twenties? Was that if you know a little it's a sodium ion channel. You know in the in the in in in the brain writer. You know it it's it. It's behavior is chaotic right it. It sort of it's governed by these haji Haji Hawke skin equations and in neuroscience right, which are differential equations that have

Oh cast a component right now, where it is now an end. This ultimately governs was they whether in IRAN will fire? Not as I do that I as a chemical products or electrical process by which signals are sent in the brain, exactly exactly ends, and you know an answer. Could I ask you are well aware it is the random is in the process. You know that that that neuroscientist euro, but what neuroscientist would would would treat as randomness. Where does it come? You know ultimately its thermonuclear right, whereas thermal noise come from, but ultimately you know there are some quantum mechanical events at the molecular level that are getting sort of chaotically amplify. I'd buy. You know a sort of butterfly effect. And so are you know, even if you knew the complete quantum state of ones brain you know at best, you could predict the probabilities that they would do one thing and do another thing right. I think that part is actually relatively uncontroversial right. They ve the controversial question

is where, whether any of it matters for this sort of philosophical questions that we care about, because you could say if all its doing just injecting some random this into an otherwise completely mechanistic process. Will then, who cares ray and more concrete Lee if you could build a machine that could just calculate the even just did the probabilities of all the possible things that you would do away, and you know of all the things that said you had a ten percent chance of doing. You did exactly a tenth of them. You know, and and and and and and and so on- that somehow also takes away the feeling of freely exactly I mean it, I mean to me it seems essentially just as bad as if the machine deterministic we predicted yo. It seems you know hardly different from that says that so then, but I'm a more and more subtle question is. Could you even learn enough about someone's brain to do that? Ok because

As you know, another central fact about quantum mechanics is that making a measurement on a quantum state is an inherently destructive operation they. So you know if I want to measure the be no position of a particle right. It was well before I, measured and had a superposition over many different positions, assumed they measure I localised right so now. I know that, The but I've also fundamentally change the state and so are you iD say well, maybe in in trying to build a model of someone's brain that was accurate enough to actually, you know, make let's say even even well calibrated probabilistic predictions of their future behavior, Maybe would have to make measurements that we're just so accurate that you would just fundamentally alter their break of day or or or maybe not. Maybe you only you it would suffice to just make some now. A robots, tat, just measured some sort of modules.

larger scale. You know macroscopic behaviour is that what is this neuron doing? What is that neuron doing? Maybe that would be enough. see, but now you know I I what I what I claim is that we're now asking a question you know in which you know it is it is. It is possible to envision what progress on it would look like yeah, but just as you said, that question may be slightly detached from the philosophical. Action in the sense, if cautiousness somehow has a role to the experience of free will because ultimately what one we're talk more free well were also talking about not just the predictability of our actions, but somehow the experience of their debts yeah. Well, I mean a lot of philosophical questions, ultimately like feedback to the hard problem of cards. Yes eve, you know and as much as you can try to sort of talk, and yet are not right in and then and then there is a reason why people try to talk around it, which is that you know

democritus talked about the hard problem of consciousness. You know four hundred bc in terms that would be totally recognised. the book to us today right and it's really not clear if there has been progress since or what progress could possibly consist? Is there a cue prime type of sub question that can help us get it she knows something about kind out. Well I mean, while their mean there is the whole question of below. of a high rate of you now: can you builder as a human level or superhuman level. I I and you know, can it can work in a completely different substrate from the brain. I mean there's, you know, of course that was alan turing boy, and you in an even if that was done, it's you know. Maybe people would still argue about the hard problem of consciousness rate and yet we might might my claim is a little different. My claim is that in a world where there were no human,

all eyes. Were we had been even overtaken by such eyes. The entire discussion of the hard problem of consciousness would have a different character right. It would take place in different terms in such a world. Even if we hadn't answered the question and, and my claim about free will would be similar right that, if their, if this prediction machine did I was talking about, could actually be bill. Will now the entire discussion of the issue of free will is sort of trains, warmed by that and you know even if in some sense the the metaphysical question hasn't been answered. Yeah exactly transforms it fundamentally because say that machine does tell you that it can predict perfectly yet there is this deep experience, a free one and that it had changed the question completely and it starts actually getting to the questioner

there s the asia. I the turing questions the demonstration of free world, a demonstration of intelligence demonstration of cautiousness. Does that equal marshes this entails instant failure, but see Alex if, if every time I was contemplating a decision, and you know this machine and printed out an envelope. You know where I could open it and see that it knew my decision. I think that actually would change my subjective experience of making this since you might mean as knowledge changer subject sparing where were you know me, I'm in the knowledge that this machine had predicted everything I would do. I mean it might drive me completely insane or hate, but it in a raid, it would change my experience to the act. You know to not just discuss such a machine as a thought experiment, but to actually say it

I mean I mean you know you could say at that point you know you could say we are what what what why not simply call this machine a second instance creation of many and be done with the right. What we are what what why even privilege the original may over this perfect duplicate that that exists in the machine there could be a religious experience with a deal it's kind of a god throughout the generations is supposed to have that God kind of represents that perfect machine is able to arm, I guess Actually you why? I don't even know what a work? What are the religious interpretations of free will does So if god knows perfectly, everything in religion in their various religions word is free will fit into that data. That has been one of the big things that theologians of argued about for thousands of years

I am. I am not a theologian, so maybe I shouldn't go there, there's not a clear answer in a book like I mean I mean this, as you know, the calvinists debated the there. You know this has been in I'm indifferent. Written religious movements have taken different positions on that question, but, that is how they think about it. We are, meanwhile, you know a large part of the sort of way what animates you? No theoretical computer science, you besides, you know we are asking sort of. What are the odds? image limits of you know what you can know, or you know calculate or figure out by you know, entities that you can actually build in the physical world right and the. If I were to trying to explain it to a theologian, maybe I would say you know we are studying you know to what extent you know god's can be made manifest in the physical world. I'm not sure my colleagues would like that. So, let's talk about quantum computers, yeah sure sure,

As you said, modern computing, at least in the nineteen nineties, was a profound story at the intersection of computer size, physics, engineering, math and philosophy said. There's this broad and deep aspect of quantum copying represents more than just the quantum computer. But can we start at the very basics? What is quantum yeah? So it's a proposal for a new type of computation a new way to harness nature, to do computation that is based on the principles of quantum mechanics they now the principles of quantum mechanics have been in place since nineteen twenty six. I haven't changed, you know what's new, is you know how we want to use them? Okay? So what does quantum mechanics say about the world? Know the physicists. I think over the generations yo convince people that that is an unbelievably complicated question and you have just give up on trying to understand it,

Can let you ain't nothin are not being a physicist. I can let you in on a secret, which is that it becomes a lot simpler. If you do it, we doing quantum information theory and serve take the physics out of it. So the way that we think about quantum mechanics is sort of as a generalization of the rules of probability themselves. So You know you might say, there's you know there was an authority percent chance that it was going to snow today or something you would never say that was a negative thirty percent chance right. That would be nonsense. Much last week, say that there was a you know when I percent chance. You know square root of minus one percent chance now. The central discovery that serve quantum mechanics made is that up Fundamentally the world is described by these are what they, the possibilities for a firm weight of what a system could be doing,

are described using numbers caught, amplitude K, which are alike 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 data if you ve heard of a quantum superposition. This just means the some state of affairs where you assign and amplitude one of these complex numbers to every possible us configuration that you could see a system and 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 forced the amplitude too, could be converted into probabilities that by taking their squared absolute value, gay and then the man, you know you can say either they elect

try and will be here, or it will be there knowing the amplitudes. You can predict the price, at least the probabilities that it will, that you'll see each possible outcome day, but while a system is isolated from the whole rest of the universe, the rest of it's environment or the amputee it can change in time by rules that are different from the than normal. the probability and that are no alien to our everyday experience so any time anyone ever tells you anything about the weirdness of the quantum world over assuming that not lying to you right, they are telling you you know, and yet their consequence of nature being described by these amputates so most famously. What amplitude can do is that they can interfere with each other day. 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 it.

There. Are you know on a second screen now there are certain places where that electron will never end up. You know, after as 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 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 we realise we would say now the away try and has a superposition state again it has some amplitude for reaching this point by going through the first slit and has some other amplitude for reaching it by going through the second slit. But now

one amplitude is positive and the other one is negative. Then no, you know I have to add them all up right after add the amplitudes, for every path that the electron could have taken to reach this point and do 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 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: a guy, a quantum computer is a a a a computer that tries to exploit. You know these exactly these phenomena superposition

in ample opportunity and interference in order to solve certain problems much faster than we know how to solve them. Otherwise says the basic building block of quantum computer is what we call a quantum bed or a cue bet. That just means a bit that has some amplitude for being zero and some other amplitude for being what so, it's a superposition of zero and one states right. But now the key point is that if I've got what say a thousand cubits, the rules of quantum mechanics are completely unequivocal that I do now I just need one amp. What you know, I don't just need amplitudes for each cube, it separately, k in general. I need an amplitude for every possible setting of all thousand of those bits. Okay, so that what that means is to to the one thousand power amplitudes. Okay, if I

If I had to write those down- let's er, let's say in the memory of a conventional computer, if I had the right down to to the one thousand complex numbers that would not fit it within the entire observable universe. Okay, and yet you know, quantum mechanics is unequivocal that if these cubits can interact with each other. In some sense, I need to through the one thousand parameters amplitude to describe what is going on now. No now I can do you know where all the popular articles about quantum computing go off the rails is that they say you're they they sort of. Sir. say what I just said. Then they say. Oh, so the way a quantum computer works just by trying every possible answer in power Well, you know. You know that that sounds too good to be true, and unfortunately, it kind of is too good to be true that the problem is. I could make a superposition over every possible answer. a problem, even if there are two to the one thousand of them right I can. I can easily

do that the trouble is for a computer to be useful. You ve got at some point. You ve gotta, look at it and see and see. put by and if I just measure as superposition over every possible answer, then the rules of quantum mechanics tell me that all sea will be a re undermine, sir. I just wanted to random answer well, I could have picked one myself with a lot. Less trouble is that the entire trick, with quantum computing with every algorithm for a quantum computer, is that you try to choreograph a pattern of interference of amplitude and you try to do it so that for each wrong answer, some of the paths leading to that right. Answer have positive attitudes and others have negative amplitude. So, on the whole, they cancel each other out gay, whereas all the paths adding to the right answer should reinforce each other. You know should have amplitude pointing the same direction.

So the design of algorithms in space isn't a choreography of the interference is precisely that precisely what it would take, a brief stepped back, and let you mentioned information, yes, so in which part of this beautiful picture they ve painted is in information contained. Oh wow 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 nineteen, forty eight, you know, and you know, of course you know people had the concept even before that you know he popularized the name right, but I mean for a bit it Cyril or one that's right, basic outright and what we would say that the basic unit of quantum information is the cube. It is, you know the object, any object that can be maintained in its as are manipulated. in a super position of the euro in one states now, you know sometimes people ask well, but but but what is acute

physically, and there are all these differ. you know, proposals that are being pursued Parallel for how you implement gear bets, there is enough superconducting. bottom computing? That was in the news recently because of Google's the quantum supremacy experiment right. Where You would have some widows coils where a current can flow through them in two different energy source. it's one representing zero another representing the one, and if you cool these coils to just slightly above absolute zero like a hundred of the grey, then they super contact and then the current can actually being superposition of the two different states. So that's one kind of cubit. Another kind would be you know just

an individual atomic nucleus right. It has a spin, it could be spinning clockwise, it could be spitting counterclockwise or it could be in a superposition of the two spin states that is another cubit by sea, just like in the classical were all right. You could be a virtuoso programmer without having any idea of what a transistor is hider, how the bits are physically represented inside the machine even the machine uses electricity right. You just care about the logic it sort of the same. With quantum computing right cuba, could be realised by many many different quantum systems, and yet all of their systems will lead to the same logic. You know the logic of of of of q

That said and how you know how you measure them, how you change them over time, and so you know that the subject of you know how cubits behave and what you can do with cubits. That is quantum information, so got it just to linger on that short. So does the physical design implementation of a cubic does not does not interfere with the that next of all of abstraction. They, u can programme over. It's a trap, is the idea of it. It is the aim is to be honest with you today. They do interfere with other that because the all the quantum computers we can build a day or very noisy and some sort of the the the cubits are very far from 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 cubits really do behave like perfect,

abstract cubits, for as long as we want them to and in that future you know the euro, which we note a future that we can already street or serve proof theorems about or think about the day but future the logic of it really does become decoupled from the hardware serve. If, if noise is currently like the biggest problem for a quantum com eating, and then the dream is air. Correcting a modern computers. Can you just maybe scribe what does it mean for there to be noise in this system? Absolutely so! Yes, it is. The problem is even a little more specific than noise, so that the fundamental problem, if you're trying to actually build- quantum computer you know of any appreciable size is something called de coherence, gay and this was recorded.

I used from the very beginning. You know when people first started thinking about this in the nineteen nineties. Now, what d coherence means is sort of unwanted interaction between you know your cubits. You know the state of your quantum computer and the external environment again is that such a problem, why I sit talk before about how you know when you measure quantum systems what say if I measure a cue bet, it's in a super position of the euro in one states to ask get your car use the euro? Or are you one well now I force it to make up its mind right now, probabilistic lay it chooses, on the other, and now you know it's no longer superposition, there's no longer amplitude, there's just there's some probability. I get a zero in their son that I get a what I now the the the trouble

oh, is that it doesn't have to be me, use looking guy or in fact it doesn't have to be any conscious entity, any kind of interaction with the external world that leaks out the information. about whether this cubit was zero or one sure of the causes these, your own S or the wonders of the queue bit to be recorded, 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 weeks out. It is as if that cuba has been measured guy. It is, The the state has now collapsed you know another way to say it is that it's become entangled with its environment. Ok, but we know from the perspective of someone has just looking at this cubit its. 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 cubits sort of thing, adequately well isolated from their environment, but that 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 and not only that, but in a precisely choreographed way, a gay- and you know that- is such a staggering problem right. How do I isolate these cubits from the whole universe, but then They tell them exactly what to do mania. There were distinguished physicists and computer scientists the nineties who said this is fundamentally impossible. You know the laws of physics, we'll just never let you control cubits 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 too late nineties, which was called the theory of quantum era, correction and quantum fault, tolerance, gay and the upshot of that theory is that if I want to build a reliable quantum, computer and scale it up to you know an arbitrary number of as many cubits as I want. You know in doing as much on them as I want. I do not actually have to get the cubits perfectly isolated from there. I mean it is enough to get them really really really well isolated, okay and even if every cubit is sort of leaking, You know it state into the environment at some rate, as long as that, rate is low enough gay. I can sort of encode the information that I care about a a in very clever ways across the collective states of multiple cubits k in such a way that, even if you knows a small

percentage of my cubits week, while I'm constantly monitoring them to see. If that we cap and I can detect it, and I can correct it, I can recover the information I care about from the remaining cuba a gay, and so you know you can and build a reliable quantum computer even out of unreliable parts right now. The the in some sense. You know that discovery is what set the engineering agenda for quantum computing research, the ninety nine days until the present. Ok, the gall has been engineer you bet that are not perfectly reliable, but liable enough that you can. use these era correcting codes to have them, stimulate you it's that are even more reliable than they are regarded. The IRA correction become a net win rather than a net was right and then once you reach that sort of cross over point there

you know, you're simulated cubits could in turn stimulate cubits that are even more reliable and so on. Until you ve just you know, effective leave you have arbitrarily reliable cubans, so long story short, We are not at that break even point yet, where a hell of a lot closer than we were in people started doing this in the nineties. Like orders of magnitude, closer The key ingredient is the more cubist the butter, because, while the more cubits the larger the computation You can do right. Gimme, I mean a cue bets are what constitute the memory of your quantum computer right off the date set for the air corrective mechanism? Yes, so so so, though, the way I would say it is that era correction imposes in overhead, and the number of cuba

and that it is actually one of the biggest practical problems with building a scalable quantum computer. If you look at the erika wrecked and 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, I'm hack your credit card number, which, as you know we can, it may be that are the most famous application people talk about right, but they do factor huge numbers and thereby break the arrest. They crept assist them well. What what? What? would take would be thousands of several thousand logical cubits, but now, with the known era, correcting codes, each of those logical cubits would need to be encoded itself using thousands of physical cubits. So at that point, you're talking about millions, physical q best and as something that is the reason why quantum computer Those are not breaking cryptography already it's because of this, these immense overheads involved. So that overhead is additive or multiple multiplicative. I mean it. It's like

you take. The number of logical q bets that you, 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 cave. That is the situation, and right now, in the meantime, we are now in whether physicist John prescott called the noise intermediate scale. Quantum or nysc era misses the era you can think of it as sort of like the vacuum. We are now entering the very early vacuum tube era of quantum computers, the quantum Computer analogue of the transistor has not been invented yet right. That would be like true error, correction They, where you know we are not or or or something else that would achieve the same effect rate we are now. They are yet and but but but where we are now, let's say as of a few months ago, we know as of google's announcement of quantum supremacy in it. We are now Finally, at the point where even

if a non error corrected quantum computer with me. You know these noisy devices. We can do something that is hard for classical computers, dissimulate gay, 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 that by people I mean Google ibm b, a bunch of start up companies- yellow, red layer lapse, yan and research, labs and governments and the yeah. A mention. A million things are backtrack, first, that yeah sure sure. So when these vacuum two days, yes, just entering and just entering, allow ok so near how do we escape the vacuum? So how do we get to. How do we get to where we are now the cpu, this a funding it

engineering challenge is there is their breakthroughs in, and the physics I d there needed on the computer science side what's or is there in and is it financial issue were much larger, just sheer investment and excitement is neo. Says that the other there there are excellent questions. My gun, organizers that I know of one that might might make my might my guess, would be all of the above. I am being my. I guess you know me, I mean believes they find a man. It is an engineering issue right. The theory has been in place since the nineties You know this is. Why no our correction. What you 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, if someone spent a trillion dollars on some quantum computing manhattan project right then conceivably, they could just.

We know build a a in error, corrected quantum computer as it was envision back in the nineties by. 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 simplistic, briefly, I did to the full soft go. I just your recently talked to Jim Keller, who is a sort of like the famed architect and then in the micro processor, world, ok and he's been told, for decades. Every year that the moors laws got going to die this year, may he tried trust argue that them more lie still alive and well

well and it'll be alive for quite a long time to come. How long? How long did what what his is? The the main point is still alive. Burgundy thinks there's still a thousand x improvement just on shrinking that transition as possible. Whatever the point is that the exponential growth who see it is actually a huge number of these s, curves just constant breakthroughs at the philosophical level, why I think we, as a descendants of apes, were able to just keep coming up with these new breakthrough on the supply side is there's something you need to this point geller endeavour by would it be possible to replicate in the quantum computer space? that other there was a lot there to do the job, but did not dare to break off something.

I think we are in an extremely special period of human history. It I mean it's, it is. You could say obviously special well, you know in in in in many ways right there. You know. Ah, you know way more people alive than their than their than there have been and, and the you know there all in all future of the planet is in is in his income. Gin in a way that it it. It hasn't been you for fur, the rest of human history, but but In particular. You know we are in the era where Are we we finally figured out? how to build a universal machines that you know the things that we call computers, machines that you programme to stimulate the behaviour, of whatever machine you white yeah

and and and and and and and and once you ve should have crossed this threshold of universality. You know you ve built, you could say you know touring you ve instantiated touring genes in the physical world will then the main questions are ones of numbers. They are. You know ones of how many of how much memory can you access? How fast does it rhine? How many parallel processors, at least until quantum computing quantum computing, is the one thing that you Just what I just said, Joe in fields as well as well as long as it's classical computing, then it's all questions of numbers and you know the the you could say at a theoretical level, the computers that we have today or are the same as the ones in the fifties. They're just millions of times. You know faster with millions of times more memory, and you know I mean Think there's been an immense economic pressure to you know, get more and more transistors, you know get them smaller and some

or get you add, more and more cores and I know, and and and and and in in some sense, like a huge fraction of shirt of all of the technological progress that there is in all of civilization, has gotten concentrated just more narrowly into just those problems right, and so you know it has been one of the biggest success stories in the history of technology. Right there's, you know it is I am as amazed by it as as anyone else's right, but at the same time you know we are. so now that it now I need I really do mean. We know that it cannot continue indefinitely again because you will reach. You know fundamental limits. No, how small you can possibly make a processor. and you know, if you want a real proof, you know that would justify by use of the word. You know. We know that me as long as the end mean

admittedly, you will reach the limits imposed by quantum gravity. You know you know if, if you were doing, if you try to build a computer that operated, tend to the forty three hearts, so they tend to the forty three operations per second, that computer or would you so much energy that it would simply collapse to a black hole? So, You know that I know alien and, in reality, we're going to reach the limits. Long before that, but that is a sufficient proof. That is element. Yes, yes, but it'll be interesting to try to understand the mechanism, the economic pressure. These said, like the cold war? Was oppression getting us getting us get example. My as both the soviet union and the united states, we're getting us the two countries to get to hurry up to get the space to the moon. There seem to be the same kind of economic pressure that somehow

in a chain of engineering breakthroughs that resulted in the moors law, yet more united europe yeah I mean I mean some people are sort of get depressed about. The fact that technological progress you know me seemed to have slowed down in many many realms outside of computing. My right there was dissolved, Have you know we wanted flying cars and we only got twitter instead right and yeah good old peter deal, yeah yeah, yeah right right right So when then jumping to another, a really interesting topic that you mentioned said: google announced with their work in the the paper in nature, with quantum supremacy. Yes, can you describe again back to the basic? What is perhaps not so basic? What is quantum supremacy? Absolutely so a quantum supremacy is a term that was coined.

I again by John prescott in a two thousand twelve. Ah, not not everyone likes the name, you know, but you know it it it it sort of stuck. You know we don't. You: haven't found a better alternative stagnating want a computational come around. Mr, that's right! That's right and bite, but the base the idea is actually one that goes all the way back to the beginnings of quantum computing. When a rich. fine man and David deutsche people like that. We're talking about it in the early eighties and and and and quantum supremacy just refers to sort of the point in history when you can first use a quantum computer to do some well defined task, much faster, than any known algorithm running on any of the classical computers that are available

So are you noticed that I did not say a useful task? You guys it could be something completely artificial, but it's important that the task be well defined. So, in other words, you know there is it. It is something that has right and wrong answers, you know that our knowable independently of this device we can, then you know, run the device see if it gets the right answer or not. He clarified small point. You said much faster than a classical implementation. What about what about the space with where the class there's no there's night doesn't even exist a classical out loud who so of the south are so maybe I should clarify everything that a quantum computer can do a classical You can also eventually do ok and the reason why we know that is. A classical computer could always you know if it had no limits of time in memory, it could always just story the entire quantum state

You know of your you know of the bottom store in a list of all the amplitude. You know in the state of the quantum computer and then just you know some linear algebra to just update that state may, and so so anything that quantum computers can do can also be done by classical computers, albeit exponentially flowers, zog case one on computers, don't go to magical place outside of Alan turing say that mission of computation precisely they do not solve the whole thing problem. They cannot solve anything that is uncomfortable and alan turing sense what they. What we think they do change is what is a fish my computer box guy- and you know, since the nineteen sixties, you know the word efficiently and you know as well as been a central word in computer science, but it serve a code word for something technical, which is basically with paulina meal scale. You know that, as you get to larger and larger inputs, you would like an algorithm.

it uses an amount of time that scales only like the size of the input raised to some power and not exponentially with the size of the input right so yeah, so I I do hope we get to talk again because one of the many topics that this probably several hours where the company conversation is complexity, which we have long. You get a chance to privilege to today, but you briefly mention it, but let's see less, maybe try to continue. She said the the definition acquire supremacy is basically designed is achieving a place where much fast, you're on a formal quantity peters, much faster on a formal, well defined problem that is always and use

oh yeah, yeah yeah right right in, and I would say that we really want three things right. We want, first of all, the quantum computer to be much faster, just in the literal sense of a number of seconds. You know at solving the scene, a well defined me no problem. Secondly, we want it to. keep sort of a you know for a problem where we really believe that a quantum computer has better scaling behavior right. So it's not just an incidental. You know matter of hardware, but it's that you know, as He went to larger and larger inputs. You know the classical scaling would be exponential and the scaling for the quantum algorithm would only be polly no meal and then thirdly, we want the first thing. The actual observed speed up to only be explain a ball in terms of the scaling back. If you're right so you'd I want I want. You know a we'll work- you know a real problem to get solved. Let's say by a quantum computer with fifty cubits

or how and for no one to be able to explain that, any way other than well. You know the to do this. Computer involved a quantum stay with two to the fiftieth power, amplitude annie of clay. the girl simulation, and at least any that we know today would require keeping track of due to the fiftieth numbers, and this is the reason why it was faster. So the intuition is dead. Then, if you demonstrate on fifty cubits, then once you get two hundred cubic, then you'll be even it's much more faster, precisely precisely yeah and- and you know, and and and quantum supremacy does not require error. Correction re. We don't we don't have you the true scale ability yet true, you know our correction yet, but you could say quantum supremacy is already enough by itself to refute the sceptics who said a quantum.

beauty will never outperform classical computer for anything, but one how'd. You demonstrate quantum yeah supremacy and too What's up with these new news articles are meeting their google and did so yeah. While the do derive great questions, because now you get into actual You know a lot of the work that I mean and I my students have been doing for the last decade, which was precisely about How do you demonstrate quantum supremacy using technologies that you know we thought would be available in the near future? and so one of the main things that we realized around anti eleven, and this was me and my students alex arc above at mit at the time, Independently of some others, including Abram, Joseph shepherd, ok,

and there were the realisation that that we came to was that if you just want to prove that a quantum computer is faster, you know and not do something useful with that. Then there are huge advantages to serve switching your attention from prob seems like factoring numbers that have a single right answer to what we call sampling problems. So these are problems where the goal is to output a sample from some probability distribution, let's say over strings of fifty bets rights. There are you know many many many possible valid outputs. You know your computer will probably never even produce the same output twice. You know if it's real, Seeing as as

yeah. We're assuming it's running perfectly. Ok, but but the key is that some outputs are supposed to be likelier than other. What's so so to clarify? Is there a set of outputs that are valid and said they're not, or is it more that the distribution of a particular kind of output is moral? Is the disease specific distribution of particular that their their third the specific distribution that you're trying to hit writer. You know that you're trying to sample from now. There are a lot of questions about this. You know, how do you do that right now, now how you? How how you do it? You know it turns out that with a quantum computer, even with the noisy quantum computers that we have now that we have today, but you can do, is basically just. Why a randomly chosen sequence of operations night, so we we are, as you know, we do know that part is almost trivial right. We just sort of get the cubits to interact in some.

Adam way, although a sort of precisely specified random way? So we can repeat the exact same random sequence of interactions again and get another sample from that same distribution, and what this does is it basically will it creates a lot of garbage, but you know very simple, epic garbage hey, so he knows to have all of the ah. So if we're going to talk about google's device that were fifty three cubits they're, okay, and so there are two to the fifty three power possible outputs. Now, for some of the, His outputs, you know there are. There- was a little bit more destructive interference in their amplitude okay, so their amplitude were a little bit smaller and for others, there is a little more constructive interference. The amplitude work. little bit more aligned with each other and so those. Is that, where a little bit likelier gave him all of the outputs are ex

potentially unlikely. But some are, let's say: two times are three times you know unlikelier than others, gay and So so you can define you know the sequence of operations that gives rise to this probability, distribution, ok now the next question would be well you, you know, even if your sampling from and how do you verify that right now, how do you know so my stupid, said, I and also the people, a google we're doing, the experiment came up with statistical tests that you can apply to the outputs In order to try to verify you know,

What is you know that that at that are at least some hard problem is being solved they? The task the google ended up using were was something that they called the linear across entropy benchmark k and its basically in us at it. The drawback of this task is that it requires like it requires you to do it too, to the fifty three times calculation with your classical computer, they so so it's very expensive to do the test on a classical computer. The good news Did he give a numbers tooth to about nine quadrillion? Doesn't help well well. Ada, if you want, I mean like scientific notation. I know what I mean is it is it is, it is impossible to run in is yeah, so we will come back to that. It is just barely possible, two rhine. We think on the largest supercomputer the currently exists on earth, which is called summit at oak ridge, national lab I decided that there that's the short answer, so so,

Ironically, for this type of experiment, we don't want a hundred cubits, ok, because with a hundred cubits, even if it works, we don't know how to verify the results. Ok, so we want you know a number of cubits. That is enough, that you know click the biggest classical Peters on earth will have this sweat you down, we'll just barely, you know be able to keep up with with. Quantum computer, you know using much more time, but they will still be able to do it in order that we can verify. That was just where the fifth, three comes from four may available. I mean I mean I mean I mean that's also that sort of thing you know the moat. I mean that that's that sort of where they are now in terms of scaling. You know, I know, soon. You know that point will be passed. And then, when you get to larger numbers of cubits, then you know these. These types of sampling spider. Man will no longer be so interesting because we will be

don't even be able to verify the results and we'll have to switch to other types of computation so with it with the sampling thing you know so so the task that Google applied, where this linear cross entropy benchmark with basically just take the samples that were generated, which are you know, a some very small subset of all the possible samples that there are, but for those you calculate with your classical computer, the probability is that they should have been output, and you say, are those probability is like larger than the mean, so is the quantum computer bias towards out putting that the strings that it's? You know that you wanted, be biased toward ok and then. Finally, we come to a very crucial question which is proposing that it does. that will how do we know that a classical computer could not have quickly done the same thing How do we know that you know this couldn't have been spoof by a classical computer? I am so whether the first answer is, we don't know for sure, because you know this takes us into questions of complexity,

we are aware that there have been questions on the of the magnitude of the p, verses, np question they re? We know we don't know how to rule out definitively that there could be fast, classical algorithms, for you, know even simulating quantum mechanics and the for you know, stimulating experiments like these, but we can give some evidence against that possibility and that was sort of the you know. The main thrust of a lot of the work that my colleagues and I did you know over the last decade, which is then sort of in around twenty fifteen, or so what led to google deciding to do this experiment- So is the kind of evidence. Your first of all, the hard peak was np problem that you mentioned, and the kind of evidence the year we're looking at. Is there somebody you come to on a sheet of paper or is this something? Are these empirical experiments

its math and for the most part I mean it's also trot. You know, we know we have a bunch of methods, known for stimulating quantum. Circuit, certainly quantum computations, with classical computers, and so we have to try them all out and make sure that you know they don't work here and make sure that they have exponential scaling on or near these problems and and not just theoretically, but with the actual range of parameter, is that are actually you know arising in. Do those experiment? Ok, so so there is an empirical component. Do it right, but thou on on on the theoretical side you know, Basically, what we know how to do in theoretical, computer science and computational complexity. Is we don't know how to prove that most of the problems we care about her hard, but we know how to pass the blame to some one else. Now we know it is well what you know. I can't prove that this problem is hard, but if it is

See then all these other things that you know, if you know for sure, yeah, you probably were were much more confident were were hard to do than those would be easy as well. Okay, so so we can give what are called reductions. This has been the basic strategy in you know and np completeness right in in all of theoretical computers. Science and cryptography since the nineteen seventies really, and so we were able to give some reduction evidence for the hardness of simulating these sampling experiments. These sampling, based quantum supremacy experiments that reduction evidence is not as satisfactory as it should be. One of the biggest open problems in this area is to make it better, but you know we can do something you know. Certainly we can we say that you know if there is a fast classical algorithm to spoof these experiments, then it has to be very very unlike any

the algorithms that we know, which is kind of in the same kind of space, of reasoning that people say peak or not equals np yeah it it's in the same spirit yeah in the same spirit, okay, so as yang a very intelligent. And the presidential car It was a lot of interesting ideas in all kinds of technological fields, tweeted that, because of quantum computing, no code is an crackle. Is he wrong or right, or he was premature, let's say so well wrong, expelled, Look. I get it, I'm actually, I'm I'm! You know, I'm I'm a fan of Andrew Yang, I like his cat. You know I like his ideas. I like his gad. That is the and I think that

You know he. You know he may be ahead of his time with you know the universal basic income and you know and so forth, and he may also be ahead of his time and in that tweet, that you reference so guarding regarding using quantum computers to break a cryptography? So the situation is this guy, so the famous discovery of peter sure you know twenty six years ago that really started quantum computing. You know, as as an autonomous field, was that if you bill a full scalable quantum computer, then you could use it to efficiently find the prime factors of of of of of huge numbers and calculate discrete logarithms and solve a few other problems that are very, very special in character. Right, they're, not np, complete problems, we're pretty further, not okay, but it so happens that most of the public key cryptography that we currently use to protect

internet is based on the belief that these problems are hard day. What shore showed is that once you get scalable quantum computers than that's no longer true? Ok, but now you know, you know before people panic. There are two important points to understand here. The first is that quantum supremacy the milestone, google just achieved is very, very far from the kind of scalable quantum computer that would be needed to actually threaten public key cryptography gay. So you know we touched on this earlier bright, but Google's device has fifty three physical cubits right. You threat in cryptography, you're talking, you know, with with any of the known error, correction methods, you're talking millions of physical cubits cause air interaction would be required to yes cause target. Yes, yes, yeah. Ah, yes yeah, its. It certainly would write.

And you know how how much you know how great, while the overhead be from the erika or that we don't know yet, but with the known codes you're talking millions of physical cubits and of a much higher quality than any. we have now okay, so I know I I don't. I don't think that that is. You know coming soon, although up people who have secrets that you know need this they secret for twenty years in our already worried about this, for further good reason that we we presume that intelligence agencies are already scooping up data. You know in the hope that eventually they'll be able to decode it once guam computers become available, so so there is so sensitive to this brings me to the second point I wanted to make, which is that there are other public key crept us

The steps that are known that we don't know how to break even with quantum computers, gay, and this too, there is a whole field devoted to this now, which is called post quantum cryptography, and so there is already so so we have some good candidates now best known being what are called lattice based, crypt their systems, and there is all I do some push to try to migrate to these cryptosystems, so nest a n in the. U s is holding a competition to create standards for post quantum cryptography, which will be the first step in trying to get free web browser in every router to upgrade. You know and use the you know something like ssl that is would be based on on. You know what we think is quantum secure cryptography, but you know this: will this will be a long process? Ah, but

it is. It is something that people are already starting to do, and so so you knows I'm sure algorithm- is them sort of a dramatic discovery. You know it could be a big deal for whatever intelligence agency first gets first scalable quantum computer, if no at least certainly if no one else knows that they have it, but eventually, we think that we could migrate the internet to the post, quantum cryptography aid and we be more or less back where we started a so. This is sort of not the application of quantum computing. I think that's real going to change the world in a sustainable way right. The three big by the way, the biggest practical application of quantum computing that we know about by far, I think, is simply the simulation of quantum mechanics itself, in order to learn about chemical reactions, Zena design, maybe new chemical process. These new materials new drugs,

solar cells, new superconductors, all kinds of things like that was the size of a quantum computer that would be able to simulate the vienna quantum mechanical systems themselves because that would be impact for for the rural world for the kind of chemical reactions in that kind of work. Quite what scale are we talking about? Now not now you're asking a very, very current question, a very big question: p people are going to be re. Thing over the next decade to try to do useful quantum simulations even with you, no one hundred or two hundred cubic quantum computers of the sort that worry we expect to be able to build over the next decade. Okay, so that might be. You know the first apple asian of quantum computing that were able to realize you know, or or maybe it will prove to be too difficult and may be and that will require full tolerance, sir enough over will era correct

I live in an era of race to come up with the a case study can. I can you, if you're sure, though the winner with aid. That that would just capture the world's imagination. Let look. We can actually do something very yeah you're right, but I think you know within the next decade the best shot we have. Certainly not you know she using shores algorithm to break cryptography You know re just just because it requires you know too much way of error correction, the best shot we is to do some quantum simulation tells the material scientists or chemists or nuclear physicist in something that is used. Them them and that they didn't already you you know, and you might only need one or two successes in order to change the billy billion dollar industries. Right, like you know, the way that people make fertilizer right now is still based on the harbor bausch process from a century ago.

It is some many body, quantum mechanics problem, that no one really understands right. If you could design. In a better way to make fertilizer right that pseudo billions of dollars right there so says to those. those are sort of the applications. The people are going to be aggressively racing toward over the next decade. Now no, if they're gonna realise that are not by you know it is you know, there's there, sir, they certainly at least have a shot so much it's gonna be a very very interesting next decade, but just to get what's watch your intuition is if a breakthrough that comes with, is it possible for that break through the beyond fifty two hundred cubits or is scale of monumental thing like five hundred thousand of yes cubits yeah? So I I can tell you what the current studies are say are saying you know, I think probably better to rely on that that, if my into It- but you know there is there- was a group at microsoft- a study a few years ago, that said even with

about one hundred cubits. You know you could already learn something new about this that the chemical reaction that makes fertilizer and, for example, the trouble is they're talking about a hundred cubits and about a million layers of quantum gates gay. So this are basically there talking about a hundred nearly perfect cubits, so the logical cuba's image, exactly read logical, qubits and- and now you know the the heart to heart, for the next decade is going to be. Will what can we do with one hundred to two hundred noisy cubits yeah yeah? Is an error, correction breakthroughs make them without the need to do a thousand as are millions of yeah, so physical give it yeah, so people are going to be pushing simultaneously on a bunch of different directions. One direction, of course, is just

making the cubits batter right and you know there's there, there is tremendous progress there I mean you know the fidelity is like tv. The accuracy of the cubits hissing, improve by several waters, of, Do you know in the in the last decade or to kay the second thing is designing better, our you know the let alone overhead era? Correcting kids and even short of doing the full recursive erica. action you know there are these error mitigation strategies that you can use You know that, may you know, allow you to eke out a useful speed up in the near term, and then the third thing is just taking. The quantum rhythms for simulating quantum camp. stray or materials and me giving them more efficient when those algorithms are already dramatically more efficient than they were what they five years ago, and so

You know. I quoted these estimates like a circuit of one million, and so you know. I hope that, because people will care enough that these numbers are going to come down so you're, one of the a world class researchers in this space. There's a few groups commission, Google and ib am working at this is a there's other research labs, but you put also have if amazing blogger, is that you put your poor, lad. Eye and ear. Put you paid me to say it we put a lot lot of efforts into to communicating the science of this and communicating exposing some of the bs and the sort of the the natural just look in the air space, the natural charlatan ism, if that's a word in this in the quantum mechanics, ingenerable, quanta, computers and so on, do you give some notes

about people or ideas that people like me early, in general from outside the field should be cautious of when they're, taking in news headings that Google achieved quantum supremacy in what way. What should we look out for where's the shots? in other words the bs yeah, so good question. Unfortunately, I'm computing is a little bit like crypto currency, deep learning like there is a core of something that is genuinely revolutionary and exciting, and because core. It attracts this sort of vast penumbra of yo people making nodes. Utterly ridiculous claims, and so, with with quantum computing I mean I I would

say that the main way that people go astray is by you know not focusing on sort of the question of you. No are you getting is speed up over a classical computer or not right, and so so, I'm your people have like dismissed quantum supremacy, because it's not useful writer. You know it's not itself, let's say obviously use. Well, for any thing! Ok, but you I I ironically, these are some of the same people who will go and they will. I will we care about useful applications. We care about solving. after reading an optimum, you know and and financial optimization and all these things, and that sounds really good. You know, but there you know their their entire speech. Is that of truck counting on nobody asking the question: yes, but how well good a classical computer do the same yes right. You know, I really mean the entire thing. Is is, as you know it you know they they say war quantum compete

Europe can do there's a quantum computer can do that ray I'm ages avoid the question: are you getting is speed up over a classical computer or not and yo? If so, you know how. How do you know? Have you really thought carefully about classical algorithms to do you know to solve the same problem right and a lot of the application areas that you know the you know, companies and investors are most excited about that. The popular press is most excited about you know. Four quantum computers have been things like machine learning. ay. I optimization bulgaria and the problem with that. Is that since the very beginning, you know, even if you have a perfect in a fault tower it no quantum scalable,

Adam computer. You know we have known of only modest speed up that you can get for these problems. Okay, so so there is a famous quantum algorithm cod grover's algorithm. and what it can do as it can solve many many of the problems that arise. In a way I machine learning optimization, including np, complete problems gave it can solve them about the square root of the number of steps that a classical computer with need for the same problems they now a square root. Speed up is veto important its impressive. It is not an exponential speed up. Ok, so it is not the kind of game changer that lets a short, the algorithm for factoring is or for that matter, that simulation of quantum mechanics, it's ok, it is a more modest speed up unless ada, roughly you know in theory. It could roughly double the size of the optimization problems that you could anthem ray and, and so what we know because people

I found that I guess to two boring earlier to unimpressive. You know they ve gone on to do like invent all of these horrific algorithm where you know, because no one really understands them. You can just project your hopes onto them right that. Well, maybe it gets an exponential speed up. You can't prove that it doesn't. You know, and the burden is on you to prove that it doesn't get to speed up ryan inessa. They ve done an immense. now of that kind of thing, and a really worrying amount of the case for building a quantum computer has come to rest on this stuff. That those of us in this field know perfectly well was on extremely shaky. Foundations so the fundamental idea show that there's a speed up, yes, Glasgow, absolutely end in this space the year, referring to it actually I think that this is the area that alot of people excited about machine learning. Yeah see your senses. Do you think it will fail

I know that there is a lot of smoke currently yeah, but do you think there are actually eventually might be breakthroughs? Were you do get exponential speed? Ups in the machine learning space? Absolutely there might be. I mean I think we know of modest speed up that you can get for these problems. I think we're whether you can get bigger speed. Ups is one of the biggest questions four quantum computing theory. You know for people like me to be thinking about now we had. Actually recently, a really you know as a super exciting candidate for an exponential quantum made up for a machine learning problem that people really care about. This is basically the netflix problem, the problem of recommending products to users, given some sparse data about their preferences corynaeus and caution. Twenty sixteen had an algorithm fur sampling recommendations that was exponentially faster than any.

known, classical algorithm ray, and I know a lot of people were excited. I was excited about it I had in eighteen year old undergrad by the name of even tang, and she was what you know she was obviously brilliant. She was looking for a project I gave her of as a project. Can you prove that this speed up is real? Can you prove that any classical algorithm would need to access exponentially more data ray and ensure that this was a case where, if that was true, this was not like a p verses, np type of question right. This does might well have been provable, but each she worked on it for a year? She couldn't do it eventually she figured out why she couldn't do it, and the reason was that that was false. There is a classical algorithm with a similar performance to the quantum algorithm, so even succeeded in quantum thing that machine learning algorithm and then in the last couple of years bill thing on evens break through a bunch of the other quantum

machine learning. Algorithms that were proposed have now also been decline, enticed Ok and then I would say of important backward step. He gets a lot like a yes or a forest emphasise, but well yes, that Ferko machine learning that that precedes the big next forests that right right re now, if its bright now not not not now some people will say well, you know, there's a so we're lining in this cloud. They say well, we're thinking about quantum computing has led to the discovery of potentially useful new, classical algorithm. That's true right, and so you know so you get these spin off applications. But if you want a quantum speed up, you really have to think carefully about that. You know he wins. Work was a perfect illustration of why right, and I think that you know the key challenge. You know the idea that the year the field is now open right, find a better example, find you know where Quantum computers are going to deliver big gains for machine learning. You know I am

Not only do I ardently support you know people thinking about that. I'm trying to think about it myself and have my students and post docs think about it, but we should not pretend that those speed ups are already established, and the problem comes when so many of the companies and in and the journalists in this space are pretending that, like all good things like life itself, this conversation must soon come to an end. Let me ask the most absurdly philosophical, ass fresh and what is the meaning of life. What gives your life fulfilment? Purpose happened ass, an yeah meaning I would say yes, number. I'm trying to discover new things, about the world and and share them and you know communicate and and and and learn what other people have discovered

are number two in amazement. My friends, my family, my kids. My students You know they're the people around and may number three trying you know when I can to make the world better. in some small way that I know it's depressing, that I get do more and that you know The world is, you know in you know, facing crises over. you know the climate and over you know, reserve research, it authoritarian it is in all these other things, but you know, try to stand against the things that I find horrible? When I can, let me ask you one more absurd question. Yes, what makes you smile? Well yeah. I guess your question just did I dunno, I thought I'd. Try that absurd.

Tanya. Well, as a huge honor to talk to. You will probably talk to you for many more hours, god. Thank you so much well! Thank you. Thank you. It was great thank you for listening to this conversation with scott aaronson and thank you to our presenting sponsor cash app download. It use cold legs, podcast you'll get ten dollars. Ten dollars will go to first, an organization that inspires and educates young minds to become science and technology innovators of tomorrow enjoy this podcast subscribe on youtube, give it five stars and apple podcast support or a patron or simply connected me on twitter at lex Friedman. Now let me leave you some words from a funny insightful blot. Both Scott wrote over ten years ago on the ever present malthusian isms. In our daily lives, quote again again of undergone the humbling experience, a first lamenting about something sucks.

Then I much later having a crucial inside that it's not sucking, wouldn't have been a nash equilibrium. Thank you for listening. I hope to see you Next time. The.