The Origins Podcast with Lawrence Krauss - Scott Aaronson: From Quantum Computing to AI Safety

Episode Date: December 15, 2023

Scott Aaronson is one of the deepest mathematical intellects I have known since, say Ed Witten—the only physicist to have won the prestigious Fields Medal in Mathematics. While Ed is a string theorist, Scott decided to devote his mathematical efforts to the field of computer science, and as a theoretical computer scientist has played a major role in the development of algorithms that have pushed forward the field of quantum computing, and helped address several thorny issues that hamper our ability to create practical quantum computers. In addition to his research, Scott has, for a number of years, written a wonderful blog about issues in computing, in particular with regard to quantum computing. It is a great place to get educated about many of these issues. Most recently, Scott has spent the last year at OpenAI thinking about the difficult issue of AI safety, and how to ensure that as AI systems improve that they will not have an unduly negative or dangerous impact on human civilization. As I mention in the podcast I am less worried than some people, and I think so is Scott, but nevertheless, some careful thinking in advance can avert a great deal of hand wringing in the future. Scott has some very interesting ideas that are worth exploring, and we began to explore them in this podcast. Our conversation ran the gamut from quantum computing to AI safety and explored some complex ideas in computer science in the process, in particular the notion of computational complexity, which is important in understanding all of these issues. I hope you will find Scott’s remarks as illuminating and informative as I did. As always, an ad-free video version of this podcast is also available to paid Critical Mass subscribers. Your subscriptions support the non-profit Origins Project Foundation, which produces the podcast. The audio version is available free on the Critical Mass site and on all podcast sites, and the video version will also be available on the Origins Project Youtube channel as well. Get full access to Critical Mass at lawrencekrauss.substack.com/subscribe

Hi, I'm Lawrence Krause and welcome to the Origins Podcast. Scott Aronson is quite simply one of the most remarkable mathematical intellects I've had the pleasure to interact with since, say, Edward Witten, who is a remarkable physicist and string theorist and has really, and was the only physicist I know who also won the field medal for mathematics. Scott reminds me of Ed in the depth and breadth of his thinking. And it's kind of appropriate that I actually first met Scott in Washington a number of years ago when we were both getting awards, but he was getting the Waterman Prize, which is basically the highest award of the National Science Foundation for young researchers under 40. And the first person who'd ever won that prize was indeed Ed Witten. It was so it's a pleasure to have known that Scott won that. Award. And since that time, when we briefly met, I've come to watch and learn as Scott,

as a computer scientist, applies his mathematical expertise to a broad variety of areas, thinking in particular about quantum computing, an area which he's become a leader in pushing forward the theoretical ideas necessary to think about what quantum computing can and can't do and how it could do those things. He also writes a fantastic blog explaining quantum competing people. And then, of course, recently, he's moved to the idea of AI safety. He's spent some time at OpenAI and been thinking deeply about how one can implement the kind of safety measures that many people worry about when they think about unrestrained general AI in our society.

I happen to think many of those societal concerns are overblown, but nevertheless, fortune favors the prepared mind and his mind is wonderful, and the preparations he's been doing are incredible. So we were able, in this episode, to talk about everything from computer science to AI safety, focusing on this rather esoteric idea of computational complexity. And so we worked through some rather sophisticated ideas in computation to talk about the basics, many aspects of quantum computing, which complement nicely my earlier podcast with John Preskell, who's a physicist who's coming to that field. And it's interesting to see how a computer scientist thinks about those same issues. And then we move to the thorny question of AI safety and some of the remarkable ideas that Scott has. regard to that. It was a remarkable conversation. He's a, as I say, an extremely deep and thoughtful intellect and it was a pleasure to finally be able to spend time with him again. I thank him for being on it. I think you'll find it amazing. I hope you enjoy the podcast. If you want to

watch the podcast without commercial interruptions, I hope you'll subscribe to our Critical Mass Substack site. And all of the paid subscriptions for that go to help support the Origins Project Foundation, which produces the podcast among many of the other public science programs that we do. And if you can't do that, you can certainly watch it later on on YouTube, or of course, listen to the podcast and any podcast site. Regardless of how you do so, I hope you are as inspired and provoked by the thoughts of Scott Aronson and quantum computing. the issue of AI safety, which is going to be becoming more and more important as AI systems become more sophisticated.

So without further ado, Scott Aronson. Well, Scott, thank you so much for making the time to be here. It's great to see you again. It's been a while, actually. Yes. Thanks for having me. I've been looking forward to this, and as I'll explain, dreading it for the same reason, because I admire you so much. we first met, I think, at least 12 or 13 years ago, maybe 14 years ago now, 13, I guess. I think that was the first time we met when we were both getting awards from the National Science Foundation. And we shared a limo in Washington, the State Department. And I confess, so I was getting some public service award.

And was that where you received the Waterman Award? It was. Yeah, you know, I confess maybe because I was so into myself that time, that I forgot it was a Waterman Award till much later. And it's just as well. Anyway, it was an amazing night. It was a lovely evening and it was lovely to meet. You were, I think, newly married then or maybe.

I was, yes. Yes, my kids were not yet born. Yes. Yes, your kids weren't born and it was lovely to see you and your wife, a young couple, so excited about this award. I knew it was an award for young people. But the Waterman Award is the highest prize that the National Science Foundation gives to a scientist under 40. And I normalize it, let me say, because I remember when it first was created, I'm old enough,

and I remember when they asked for nominations. And it wasn't surprising to me that I think the first recipient was Ed Witten, who is, I think by almost anyone's standards, the smartest person in the world. And I thought, okay, well, that's a nice bar. And I have to say that having thought about, I've known things, you know, I've known of your work and read some things by you, but deciding to go into understanding you, I suddenly realized that I had the same feeling that I have when I was talking to Ed, who's an old friend of mine and a nice guy as well.

But the kind of the sense of the depth and breadth of your intellect is remarkable to me. I'm saying that outright. I'm intimidated in some sense by it. It's astounding. I want to hopefully do it justice. I think the problems you're looking at are interesting and your attitude is refreshing. You add a difference in the sense that you also like to write about your thoughts, which I don't think Ed does. But I kind of feel, you know, as a preview of what we're going to talk about, I kind of feel that when you talk about computationally hard problems, for me, you're a computationally hard problem.

And this, you know, I may require not computing polynomially time, but exponential time to fully grasp your intellect. And in that sense, and I'm going to say things that people will understand right now, but we'll get to it. In that sense, I'm hoping that P is equal to NP because I'm hoping that I can somehow understand how to get to where you are. Well, you're extremely kind. I mean, I have gotten to know at a little bit over the last five years through the It from Qbit collaboration and things like that. I will certainly not be able to simulate him in any way, shape, or form. And I feel like the, you know, the questions that I work on seem, you know, ridiculously elementary in many ways, you know, compared to what my friends in string theory do.

But, you know, I like being in a field where that's relatively young and where the questions are are very easy to state. Yeah, well, something that, but as you just alluded, questions that are easy to state are not necessarily easy to answer. In fact, sometimes they're the hardest ones to answer. You know, my new books about known unknowns and in some sense, as I say at the beginning of the book, and it really hit me is that the problems at the forefront of science that we don't understand are precisely the problems

that almost everyone has asked themselves at some point or another. So it's kind of interesting to see that. But I, but you know, another hand, I, you know, I can ask questions without making sure I understand what the questions are. In fact, I was thinking about that because we'll get to JATGBT. I'm hoping that we may have a very fascinating discussion, even if I'm kind of like JAPD, where I don't really understand exactly what the questions I'm asking are or what you're saying is, but I know how to get there. So anyway, let's see. Well, we're going. I find it fascinating.

And I should say that, you know, I wanted to talk to you. as a, initially also for a variety of reasons, one, because I wanted to talk to you, but also as a compliment, as you may know, I did a long podcast with my old friend, John Presco, who goes back to me back to when we were Harvard together before he started working in quantum computing. I like to kind of think that are the issues we worked on

on black holes and information are really what may have spurred him into thinking about quantum computing. I watched that transition happen as we were working on papers. Yeah, no, I, I, John has been instrumental in my career. I mean, one of the most important summers that I ever spent was at Caltech in 2001,

going to his group meetings and just feeling invigorated after everyone to a remarkable understand what quantum mechanics says about computation. Yeah, no, but he comes from a different point of view. He's not by training a computer. a computer scientist than you are. And I thought, you know, quantum computing, which we talked a lot about with him, I thought the more different directions you can come at it from, the more useful it might be from the public. But I, but I wasn't, so that's where I wanted to start. And then when you sent me things to read,

when you kindly sent me things to read when I asked you, you know, maybe some for some sources, it will of course, went way beyond quantum computing. And, and as we'll talk about, your interest in the last year, at least has been an AI safety, which is something that's on everyone's mind. But in the interim, what I began to learn about with that your real interest, where your heart is is computational complexity. I think that's a fair statement, the mathematical question of computational complexity. So I want to talk about how we got there before we start talking about. We'll talk about quantum computing, computational complexity, and AI safety.

Hopefully we'll get through it in the next day or two. But as you may know if you've watched any of these, and maybe you haven't, I like to, it's an origins podcast. And I like to start by learning about the people I'm fascinated by, about their origins and how they got to where they, where they now are. Now, the first thing I learned when I read a little bit about you is that your father was a science writer who then became a public relations executive. So his training was, was his training in science or was his training in writing? Both of my parents were English majors. English majors. Okay, perfect.

Well, that does explain something. things. Well, that's interesting. But English majors clearly, well, in your father's side, and I want to ask about your mother a little bit, because I don't know any better, but in your father's side, you know, I think it's great when English majors become science writers, because ideally, if an English major can understand it, then anyone can understand it. And so it's better they don't get lost in jargon, but what caused him to be a science writer? Well, he studied at Penn State, and he actually studied with a somewhat well-known science. fiction writer named Phil Klass.

Okay. And he was, you know, extremely interested in, well, in science and in science fiction. And he, you know, he found jobs, you know, writing articles about, you know, the Big Bang about cosmology. You know, he interviewed Stephen Weinberg. Actually, you know, when I first met Stephen Weinberg seven years ago when I was considering moving to U.T. Austin, he confused me with my father, who he had still remembered from me. Oh, really? Having being interviewed by him in the 70s.

Oh, fascinating. But, you know, he wrote for, you know, science magazines. He also wrote for Playboy in Pennhouse, which. Which I maintained had great articles. I used to tell my mother that I read Playboy for the articles. And I did. He had these Playboys in his office, right? But, you know, he could legitimately say, like, you know, I have an article in here about

why is there more matter than antimatter, you know, in the year. And they had great interviews. Claudia Dreyfis is an old friend of mine. Science writer. And she used to do interviews for them. She interviewed me once, and it ended up being for Scientific American. but but yeah no it was it was a great source of it's a kind of yeah so that was that was what he did in the in the 70s and then he uh was hired by bell labs to be a science writer there and uh actually when

pensius and wilson you know won the Nobel for the cosmic microwave background uh he was involved in you know the the publicity efforts around that right and so so he got to know or no Penzi as well and uh uh big but uh um you know and and and then you know when when Congress was you know debating you know a breaking up uh AT&T you know he was responsible for you know writing speeches about you know why is this going to destroy Bell Labs you know which of course it did destroy Bell Labs you know on the other hand we all got you know cheap phone service so that was the trade off yeah it did destroy Bell Labs and nothing Something like a monopoly if you want to spend time on research.

Yeah. And then he and then he moved to the to the corporate side. And became public relations for Bell for for AT&A? Yeah, yeah. No, he was at AT&T. And then and then it loosened after they spun off. Lucent and then it Avaya. So yeah.

Did he write, did he ever write any science fiction by the way? I believe he did. But you never saw it? No, I, you, he, Years ago, I probably read one of his short stories. But no, he was also, you know, constantly, you know, giving, giving me feedback on my writing, usually just telling me to cut, cut, cut, you know. Yeah, admit needless words.

Yeah, well, you know, it didn't completely take that advice. Well, that's okay. I like, I like, for me, I often, especially when I'm trying to understand something, more is sometimes better. But it explained a lot to me when I learned a little bit about your father because, you know, you have been involved with. And in spite of the fact that for many people, blogging is the death of their science. I know at least one physicist who I'd say that for. Really? Yeah, I think, I think so. I'm not going to mention. I mean, I feel like blogs are already something that like you look back on with nostalgia. Like, gosh, you know, people really

express themselves in depth and back in that lost golden age of blogging. Well, you know, it's great. I mean, but something, you know, your blogs have been very useful for a lot of people and that's great. But now I understand why you're motivated, at least the example of why you're motivated to write because, you know, your intellectual interest is in an area that is in some sense as far divorced from public explication as you might imagine, and especially involves mathematical complexity, two words which generally are an anathema to the public. And so, yeah, so now I understand where you got that instrument.

And by the way, I know you've got a great idea for a science fiction story. You've told it enough that I'm expecting someone else to write it if you don't. But maybe we'll talk about your science fiction story before we're done, because it's a great idea, I agree. But you have to know enough to know what the hook is for science fiction. What about your mother? Your mother was an English major? Yeah, so my mom was a remedial reading teacher, and she actually taught for decades in inner city Philadelphia. And, you know, she, you know, worked at Catholic schools mostly.

But, you know, but she was an employee of the city, right? And the Supreme Court kept changing its mind about whether she was allowed to be in the building or whether she had to be in a trailer outside the building. It was a big separation of church and state. Yeah, yeah, yeah. But, you know, she was, you know, these, you know, although kids went to Catholic school, if they had reading difficulties, they were entitled to, you know, a specialist to help them. And so she was, you know, and I'm an expert in that. And, you know, I think that she could have probably been, you know, done, done research in that area and, you know,

and done much more in it. But she really sacrificed a lot for, you know, for me and my brother. I mean, she, you know, she wanted a job where she could be there for us. Well, that's lovely. Yeah. Now, which one of the more one of them or maybe both was, you know, because he was a science writer, is that what, what sparked your interest in science in the first place?

Oh, gosh. I mean, it's, it's kind of like, you know, how, you know, you, how could you not be there's a, I mean, you hear that there's a maximum speed that anything can go at, right? But a lot of people don't hear that. It's 186,000 miles per second. Like, how can you, how can you not want to understand? Well, yeah, but a lot of people don't even know that. What would happen if I tried to go faster, right?

Yeah, sure, but where did you first hear that? A lot of people have never heard that. I mean, I mean, my, my, my, my, my dad told me, you know, a bunch of these things when I was four or five, you know, let me think, you know, I mean, I had, you know, I had science books that I read. You know, I think, you know, at some point, you know, when I was 10 or 11, I started devouring Isaac Asimov. Me too. I was a little older, probably 13 Isaac Asimov. Yeah, yeah, yeah. Yeah, and then. Yeah, okay, yeah. And then after that, Richard Dawkins, Carl Sagan, Bertrand Russell, you know,

and then I just started devouring biographies of scientists. So, you know, biographies of, you know, Einstein and touring and Ramonogen and just, you know, learning about, you know, the whole world, so the whole, you know, almost Well, let's go back. I mean, that's the next I was going to ask. So you were, you, it's, you got part of your interest in sciences from reading, and that's certainly was spark, that's what got my interest going. But was there, I assume because they're both English majors,

reading was a big deal. You read a tremendous amount when you were younger. Your parents encouraged that. I read a pretty good amount. I mean, you know, I was also playing Nintendo a lot. Yeah. You know, once I had that, right? And, you know, I think that for a while, my main ambition in life was to create my own Nintendo games, right?

Because, you know, these were, these were whole universes. And yet, you know, unlike our universe, these were universes that apparently someone completely understood because they had created them. Well, you know, that's not too different, it seems to me, from where you ended up. But we'll see. But, you know, we were joking that your kids like to play. on their iPads. And I said, if you were their age now, that's what you'd be doing, I think. But you got exposed to science in some sense,

primarily through your dad and through the access to books and books by scientists and about scientists, which of course, certainly one of the reasons I write is to return the favor. But you also had another experience that I think, I assume was formative. Your father went, you went to Hong Kong for a year. Yes.

And that took you to a school that allowed you to do mathematics way beyond what would have been possible in American school? It was a little complicated. So, you know, I, for nine years, all through, you know, elementary, I went to a Hebrew Day school. And, you know, it was not because my parents were particularly religious. It was mostly that the Hebrew Day School, you know, alone among all of the schools, said, okay, he can take a math book. he can, you know, proceed at his own rate. Oh. And, you know, and then, you know, I went to. Let me step back.

Let me just step back. Yeah. No, no, no. I'm sorry, but I'm interrupting here for a reason. Often I don't. But no, no, I interrupt too much. I know everyone tells me. But you could take a back math book with you.

You were precocious, beyond precocious as a mathematical person. Where did the interest in math come from? as opposed to science. Well, that, that's as early as I can remember, really. Okay. So you just were fascinated with, you know, I know. I mean, I mean, I think, you know, when, when I was three or four, I was interested in just what are the biggest numbers that, you know, that I could name.

Did you talk to any about that or did you ask? Yeah. I mean, I, I mean, to my, to my parents. And then, and then at school, I had a, I had a teacher who was, you know, really formative for me. Encouraging teachers. Mrs. Lack. Yes.

And then and encouraged you to keep, and so in Jewish day school or whatever, you could, you could follow math and they let you do that, which is. They let me, you know, at least, at least, you know, be somewhat accelerated. And then, you know, in seventh grade, I went to public school and, you know, was allowed to be, you know, to do the honors algebra then. And then, and then, I, I was allowed to be, you know, to do the, the, the, the, the, the, the, the, the, uh, and then. And then after that is when we all moved to Hong Kong for a year because my dad became the director of AT&T's Asia Pacific Public Relations Division. And so they paid for us to go to a, you know, a fancy private school for, you know, for, you know, for, for, for, for, for, for expats and for, you know, for, for, for, for, for, for, for Chinese people who could afford it. It's called, you know, Hong Kong international school. But there I was placed in eighth grade. But, you know, I, I, um, you know, I, um, you know, I, um, you know, it turned out that it would not work for me to go over to the high school to take math. It just didn't work logistically. There was also bullying. There was a lot of things I didn't like about it.

And so then, you know, ultimately, you know, we convinced them to just let me skip to ninth grade entirely. And then and then also, you know, skip more in math. Math, you know, in some sense, was sort of the excuse, you know, at this point, like, as soon as I understood that I, you know, like, it was possible to do such a thing, then I just sort of wanted to get out of the school environment as quickly as I could, you know, and, you know, and I still don't know whether, whether I was right, right, whether, you know, think things ended up better or worse, but when I came back to the US, the year after, then I was like, well, you know,

I was in ninth grade, but it was really sort of like 10th grade. So really I should be in 11th grade. And so then I, you know, I did that. And then I finished the AP calculus that year. And then and then the school, had said that, you know, I would be able after that to just take, you know, Stanford had this online learning course, you know, I could do multivariable calculus or differential equations, but then it turned out that I couldn't do that, you know, not even if my parents paid for it,

right? You know, I wasn't allowed to even just sit in a room to do that. And so I said, you know, again, I used that as an excuse. And I said, you know, there was a program in upstate New York called the Clarkson School, where you live at Clarkson University, which is, you know, way up in Potsdam, and you take college courses, and you do that as your senior year of high school. So I said, you know, why don't I go there? And, you know, I had many reasons for wanting to get out of high school. But, you know, my parents, you know, after some convincing where we're kind enough to let me do this. And we had the car all packed up, ready to go there. And like, as the car was all packed up. Then we got a phone call from a teacher at the high school who, you know,

one who would really support me. And he said, I have great news. I finally arranged that he can take multivariable calculus. But, you know, by then it was too late. And so then, you know, I was, I was 15 when I started college. And I, you know, after a year at Clarkson, sometimes your original high school is nice enough to give you a diploma. But mine would not. because I was missing phys ed. So they said I had to spend the summer doing push-ups, basically. You know, and this was a problem because, you know, I had gotten, you know, I had applied to other colleges, you know, as a freshman,

and Cornell was nice enough to accept me out of all the places I applied to. So I was going to Cornell, but, you know, I needed a high school degree and to enroll. And so then, you know, eventually, you know, the plan was for me to just get in New York State GED. And there was a rule that you had to be 17 to get it. But my mom spent some hours on the phone with them and convinced them to give me a GED. And you're what, 16? You were 15. I was, yeah, I was 15 at the time. Yeah.

And then 16 when I started at Cornell. When you started. Now, you your braids, it's true that not only did you not enjoy your high school because of their restrictions. you from doing what you wanted. But your grades weren't that good there either, were they? Yeah, I mean, I had a, you know, I had a lot of conflict with, uh, with, with, with a chemistry teacher, for example, who, who gave me a C, you know, and I just remember, you know, the, the one thing I clearly remember from that class is that like, you know, when, when, when, when you had a, uh, calculation to do, you know, even if you had the right answer, it would be marked wrong if you

didn't write one mole divided by one mole and then cross both of them out. Well, you know, I'm going to sympathize a little with your namely when it comes to physics often on, and chemistry is just really a part of physics. But, you know, understanding dimensional quantities and is very useful for understanding how to get the right answer and even what the right equations are. No doubt, no doubt.

I'll give them, I'll give them. But on the other hand, chemistry teachers, next to math teachers are often the worst in the world. So, so. But also, you know, I was, was, you know, I, it became clear that, you know, I was not good at chemistry experiments. Yeah, well, sure. And, you know, and, but, but, but, but, but, but, but, but, but, but, but, but,

but, but, but, but, but, but, but, but, but, you know, you are graded on whether you know, the answer you're supposed to get. And, you know, the incentive is overwhelming to just fudge things to get that answer. Yeah. It's like teaching the opposite of what you want to teach people. I agree. I agree. The process is what's important.

Yeah. Yeah. No, yeah, and there's a lot, we won't, maybe we'll get into education later on, but process and asking questions, not the answers, especially in a world where we have smartphones and soon other and chat GPT. But okay, you enter Cornell and you, but now, by the way, at the same time, one thing we skipped, and this will become relevant later on. So you're prodigiously talented in mathematics, clearly.

but you also were, you know, started at the same time as you learned calculus around age 11, you also started to do computer programming. It felt like you were already way behind the curve. Was that because you had friends who'd been doing it from the time there, five, or just because Well, I met when I was 12, at my junior high school, I met another kid named Alex, who had had been programming. for much longer than me, could, you know, create amazing things and a visual basic. And, you know, it was clear that I was never going to be as good as he was.

Now, he became my best friend. He still is. He's now a very well-known computer security researcher, Alex Alderman. He's often in the news for, you know, especially in the last few years for studying the security problems with electronic voting machines. Oh, wow. You know, but even even when he, when we were 12 years old, he was extremely interested in, you know, hacking the school computers and, you know, and sort of showing how ridiculously poor the security was. And, you know, and he, and he had a sense of sort of what was actually going on in the machines, right?

Not just what could in principle be going on, but, you know, but what was. And I think, I think, you know, Alex was, was part of how. how I learned that I am not cut out to be a software engineer. You know, at the, but that was probably very useful for you because you could, I mean, I know all that smart kids who just get in that morass of programming and building apps. And so, of course, something that become rich. That's a different story. But when they could have, when they actually have the aptitude to do other things, to do other things. And it's very seductive.

And of course, the money is very seductive if you're a young person. Right. Well, you know, there, I mean, there is this, this kind of running joke that, you know, we, We see someone who left a PhD program and start a Google or an Amazon and getting, you know, $20 billion. And we say to ourselves, like, man, it's so sad. They really could have been something. Yeah, yeah, that's right. I think of Nathan Mirvald, for example, if, you know, wasn't able to get a job in physics,

but he did okay. Right, right, right. I mean, I mean, I mean, that's one perspective you can take. But, you know, I did have face this sort of decision point when I was a, teenager. Like do, you know, this was the time when, you know, all of these internet companies were being started. You know, I, I knew that there was this cool research project at Stanford or something called Page Rank than, you know, these guys, Bryn and Page were doing, right? Yeah. I had also been thinking about, you know, how do you optimize the web? How do you think about the web as a directed

graph? You know, those were, I, that was actually the subject of my first paper, which I, you know, did when I was at Clarkson when I was 15. You could have been rich. You know, so, so, so that, you know, those were all things of great interest to me. But, you know, do I try to, you know, go to Silicon Valley, start a company, or do I go into research? And, you know, I feel like, you know, I, I think the, you know, the way I put it recently was that, like, in the end, I was too selfish to try to get rich. like you know like if if if i if i if i did make a you know uh uh you know even if i succeeded at

making a ton of money which which was not at all certain you know it would just face me with with with with the burden of figuring out what to do with it and you know how could i have an impact on the world it wasn't it it's making a lot of money was not intellectually interesting i know that feeling when i was younger i certainly had it i mean i mean it might it might it might well have been. I mean, that, that, you know, that that was that, you know, in any case, that's a different branch of the wave function. Yeah, it is. A different range way. It's a difference. It's a difference set of skills. You know, I created a program physics entrepreneurship once when I was chair of a department. And I learned how different having a successful company is and having good ideas. It's a very different

thing. Right. Right. I mean, I mean, I mean, I mean, I mean, I mean, I've, you know, a little bit, I'm coming full circle because now I'm on leave. I am working at Open AI. I'm out in San Francisco a lot. And And it is, you know, it's so bizarre to go there, right? Because I still think of myself mentally as like this little kid, this little teenager, right? And OpenAI, I think I am literally like the oldest person there. Okay. You know, just about everyone is, you know, in their 20s. And, you know, and I'm like, you know, well, the way we thought about machine learning back in the 20th century,

which none of you young uns remember is. Okay. Okay. Now, well, we're going to get to where you are now, but we'll get there almost on. I am intrigued, though, when you enter Cornell, you decide to do a BS in computing. And I mean, you think like a mathematician, when I read you, it reminds me of reading mathematics. I did a degree in mathematics and one in physics, and I quickly became clear to me, even though I was good in mathematics, that I was a physicist and not a mathematician. And I got the same sense of impenetrability about some of your thoughts that I do have in mathematics.

And so why did you do computing rather than mathematics? Yeah. Well, okay. So there's a sort of silly reason. I took enough math to be a math major at Cornell. But in order to be one, I'd have to be in the College of Arts and Sciences. And then I would have to take two years of a foreign language. Oh, I see.

And at the time, that just seemed like, you know, a big waste of me. You know, just like, you know, when I had been at Jewish day school, you know, learning Hebrew, it seemed like the biggest ways to me. Now I'm married to an Israeli, and I wish that I had paid more attention. Oh, okay. I dropped out of Hebrew school three. But, you know, I never had any great facility with foreign languages. You know, I also tried to learn Mandarin the year that I was in Hong Kong,

and that was also not a great success. But, but, but, but, but so. So I was in the college of engineering and, you know, I was doing computer science there. And I did, you know, take a little bit of physics. And, you know, I realized that my mind just does not sync with partial differential equations. You know, like, okay, you know, I like, okay, yeah, at some conceptual level, I understand. But, you know, I just, you know, I wasn't, I wasn't good at them. And, and, and, and, and, and, and, and, and, and, and, and, and, and, and, and, and, and, and, and, you know i i you know the the the the the moments in the physics class when i got the most engaged was you know when there was a you know a mathematical point right yeah no it's that's that's countable or uncountable yeah yeah it was fascinating for me it was a revelation for me i did a degree in math and one in physics and i and and i was in you know therefore in the honors math and i was with really good mathematicians and it shocked me because i figured if you're a really good mathematician

that physics would be trivial. And it shocked me that these guys who were light years beyond me in math, I felt, I couldn't, you know, even introductory physics was difficult. And it was interesting to me to see that. It was actually made me feel better, of course, in some sense, because physics was, you know, the difference for me was that I could, I could, when I was doing physics problems versus math problems, I want to ask you this.

With the physical problems, I could see way down where we were going and where, you know, where the future was. problems I could do them, but somehow I could only see just one step beyond where I was at best. I see. I see. Yeah, no, I mean, so I've spent my whole career in quantum computing, you know, interacting with physicists who are the majority of the field, you know, and very often feeling like an imposter, because, you know, I, okay, at some point I learn what Hamiltonians are. I learn how bosons and fermions work, right? But, you know, these are all just things that I pick up on the streets. you know that's right i mean it's picking up you know i think my my you know retirement project will be to really

seriously study quantum field theory and also general relativity right right and uh you know but but but on the other hand we know what what what uh what i realized like pretty early on uh you know after i had gotten into quantum computing was that uh you know like you know there there could be a particle physicists, right, who are like asking me to explain the bell in equality. Yeah, sure. Like the things that, you know, that were just the most basic to me were often things that the physicist didn't, you know, understand and wanted to understand. Yeah, because they didn't really need to know and in some sense, I mean, you know, you work with quantum mechanics. You don't need to know about it. That's right. That's right. That's right. And so, so I actually, you know, had a whole like little career just giving

colloquia in physics departments, you know, explaining the basics. of quantum information and quantum computing, you know, which you know, I didn't have to explain quantum field theory because they already know that. Yeah, yeah, yeah. Yeah. I will say one other, I'll interject one other thing.

I don't want to interject myself too much, but it's when you say you didn't do this because of, you didn't want to take foreign languages, it's intriguing to me because when I was reading all your stuff, it occurred to me how wrong I was about something. The first professorship I had at Yale, and I think I got put on as, even as a junior faculty, committee that determined science was to determine science requirements because Yale students

basically didn't have to take science, which is not surprising for Yale. And so we tried to sort of double or triple a science requirements. And we wanted and the computer science department desperately wanted computer science to be an introductory science requirements. We said no, you know, we want an experimental science. And so I remember saying what we could make it a foreign language requirement. So, you know, Fortran or, or what are you? And now I realize how completely well, at the time, it might have been true that the computer science in 1980 was not, but, but at least for undergraduates. But it's certainly, now that I read your stuff, I realized how wrong I was about, but, well, I mean, I mean, look, I mean, I mean, I mean, I mean, part of what, you know,

computer science majors learn is languages, but actually there's a lot of complaints about the computer science major, you know, that it doesn't prepare people for, you know, optimally for careers in tech because there's too much theory, you know, too much ideas and not enough hack. You know, that's, that's, that's, that's what it is, right? But you don't need as the 12 year olds who start companies show, you don't need to go to, you don't need to go to college to. Yeah, yeah, right, right. I think, I think, I think a lot of fields have this conflict. Yeah, yeah. Yeah. Now, so, okay, so you chose math rather than computer, now, I mean, computer science rather than math, and I understand was to get away. By the way, that's why I chose a

degree in math because it allowed me to skip doing an experimental physics class. So you know, and now I kind of regret. I mean, I mean, I mean, I mean, I mean, the other thing, you know, like, like I realized that, you know, I wanted to prove theorems, right? I like proving theorems. But then, you know, there's a question of which theorems, right? And in math, what you have is, you have such, you know, staggeringly high towers of abstraction, right? Yeah. Even to get to where the frontier is,

you know, even to understand the questions that are being asked at the frontier, right? It could take years. And then when you finally reach that point, then it's very hard to explain to anyone who's still at the bottom, right? Yeah. And, you know, I feel like theoretical computer science in a way was much younger. Like the questions were much easier to understand.

Initially. And, you know, which didn't make them. easier. I mean, you know, yeah, yeah, yeah. P versus NP seems to be as hard as anything, you know, that's ever been asked, right? It's pretty hard. Yeah, but, but, but, but, but, but, but, but, but, but, but, but, but, but, but, but, but, but, but, but, but,

but, but, but, you know, and you sort of see this, you know, there are these seven clay millennium problems. Yeah, yeah, yeah, yeah, that you get the million dollar price for, right? But, uh, when people try to popularize them, they inevitably end up focusing on P versus NP, right? Yeah, yeah, because it's the one of the seven where you can explain to explain to anyone on the street. Yeah, you can.

Why, you know, how could an answer to this question change civilization? Yeah, well, I hope so. We're going to get you to explain that. Yeah, yeah, yeah. But I'm not going to get you to explain the Poncarre conjecture or something. It's already solved, so it's a past. That's the right. That's the one that's solved. Yeah.

So you went from an undergraduate. I'm almost finished with your life story before we get to the science. All right. But I found it fascinating. You went to Berkeley, interesting choice. And you decide to work on quantum computing. Is that because of your, because you let me, let me, I, maybe I'll ask a leading question as a lawyer would say. If I think about your interest now that I know them, which are really in computation complexity,

was it because quantum computing was sort of the most exciting way to actually empirically kind of address that problem? Or was it something else? Well, I mean, it was a, this new emerging field. that sort of brought together computational complexity with some of the biggest questions about physics. Like, you know, is quantum mechanics, you know, really true all the way up to macroscopic scales? Yeah, right?

And how should we think about quantum mechanics, right? You know, should we, you know, believe or disbelieve and, you know, the many worlds interpretation. And so, you know, so, I mean, I think I first read about quantum computing in a popular article, you know, around 1995, like, you know, just shortly after Shore's factoring algorithm was discovered, right? And it was about that. And it was saying, you know, the usual wrong things that people still say about Shore's algorithm today. They say, you know, it works by just trying every possible divisor in a different parallel universe. And then, you know,

magically you get to pick the best one. And my first reaction when I read about this is like, this sounds like garbage, you know, this sounds like some physicists who just don't understand what they're up against, you know, that, you know, which it was probably. Yeah, well, you know, an English major too, and of course, it was right. Yeah, no, no, that, you know, like, you know, they, you know, they don't understand, you know, the church touring thesis, right? That all, you know, a different, you know, laws of physics can all, you know, reasonably well simulate one another and, you know, and, and, and, you know, It must be some phenomenon of some small number of particles that they're just illegitimately extrapolating to a large number.

But of course, I had to learn something about it, right? Sure. That's great. I, you know, the web itself was not that old, but, you know, there were already websites explaining Shores algorithm and Grover's search algorithm, which had sort of just been discovered, you know, for searching a list of N items and only square root of N steps. And, you know, what really struck me was that, like, you know,

I had read popular books at this point, you know, that said, you know, quantum mechanics involves waves that are somehow also particles, and they change when you look at them, and you shouldn't even try to understand this. It defies any, you know, and I said, okay, fine, whatever. I guess I'm never going to understand that, right? And then as soon as I started reading about quantum computing, it was completely different. They said, look, here's the deal. You know, this state of a system is this unit vector of complex numbers. And, you know, they're they're kind of like probabilities, you know, but they're not probabilities because they're complex. You know, you can, you know, you can turn them into probabilities by taking their squared absolute values, right? That's what happens when you make a measurement.

But when you don't make a measurement, then this vector of amplitudes just undergoes this, you know, linear transformations, these unitary transformations that preserve their norm. And I said, wait a minute. Like I understood that. Why didn't anyone tell me that before? And then, and then, you know, with a little bit more than that, you know, what are the basic rules of a quantum computer? And then, you know, in some sense, you know, you are, you know, you are playing the same game as, you know, even, you know, someone who spent their life doing physics, right? You, you know, you know the same rules that they know. I mean, yes, the physicists may, you know, have all sorts of intuitions that come from scattering theory and, you know, that will let them think of, you know, quantum algorithms that you can't, right?

A great example of this would be Ed Farhue, you know, who was my colleague at MIT for nine years, right? And, you know, he worked with Jeffrey Goldstone and others, right? And they really invented quantum algorithms that I would never have been able to invent by leveraging their knowledge of, of, of, you know, of particle physics, right? But on the other hand, as a computer scientist, you know, I might know things that they don't know, right? And I can bring those to bear. And just understanding that there were these clear axioms.

I mean, philosophically, you know, how should we interpret them? What do they mean? People still argue about that, right? Yeah, we'll talk about that. Although I'm not sure the audience. But once you learn the axioms, then in some sense, you can argue about those things too, you know, as an equal of anyone, right? And, you know, it's true that, you know, there's a vast amount of physics, you know, beyond just, you know, the axioms of quantum mechanics.

But in some sense, you know, it's, it's kind of like, you know, with with a classical computing, right? You know, you can know the rules of how a touring machine works. You know, that doesn't mean that you understand Windows. That doesn't mean you understand, you know, all of the software frameworks that were built on top of it, right? But, you know, like most of physics is just, you know, application software that is installed on the, you know, on the on the. That's why we say shut up and calculate. We just, you know what they are and you just calculate and use that. Yeah, yeah, yeah.

And so, so, you know, and that was not at all the way that, you know, quantum mechanics was taught in, you know, to physics majors, right? Certainly not at that time. Yeah, sure. It's finally changing. It's starting to change now. But, you know, if I had been a physics major, I would not have learned it that way, right? What I would have learned was the historical order

in which the things were discovered, which means first you master classical mechanics, you know, and you learn about thermodynamics, you learn about classical field theory, and then you learn this whole, you know, the whole shaggy dog story of all of the anomalies that were discovered between 1900 and, you know, 1925, like until people finally figured out what's going on that, okay, you know, states are vectors of complex numbers, right? And, you know, in quantum information, we do it a completely different way. Yeah, it's a historical. You know, let's let's assume, you know, let's grant that the experimentalist did a good job.

And they, you know, and let's try to understand, you know, what, what did they discover and how do we make sense of it. Yeah, to be fair, I think people, I think, I don't want to belabor this, but to be fair, I think it's often taught that when quantum mechanics, because quantum mechanics is so hard to understand that you've kind of, I feel you want to lead students gently into it to show why physicists were dragged, kicking, and they just didn't get this craziness. Sometimes the best way to get used to a cold pool is to just leap in. Jump in, I know, I know. In any case, some people have argued, I remember one, a friend, I remember one time in Toronto, he argued he was, and they tried. It was abysmal failure to teach quantum mechanics before class mechanics. Because you don't need, in fact, I never understood this. I never do what a Hamiltonian really. It was. until I get quantum mechanics. Right. Well, the thing is like I first knew a Hamiltonian as just, you know,

the instantaneous time version of a unitary transformation. Absolutely. There you go. The thing you exponentiate to get unitary evolution. And then I had to go back and learn what it had to do with energy. Okay. Well, that's good. And where it came from in classical physics, right?

But, I mean, I think the danger in learning things, you know, the, you know, in starting with classical physics, is that then you're always thinking, about quantum mechanics as a sort of correction. Well, that's, we'll come back to that because I think that's part of the huge problem. You wrote a whole long article for philosophers, which shows more patience than I would have. About, and one of the big arguments is interpretations of quantum mechanics, which I would argue is it just a big waste of time. But, but, but, but, but, but, I mean, I mean, I mean, I mean, I mean, I mean, I mean, I mean, I mean, I mean, I mean, I mean, I mean, I mean, I mean, I mean, I mean, I mean, I mean, I mean, I mean, I mean,

I feel like, well, you know, you know, look, you know, you know, bell was driven to discover the Bell inequality by obsessing about Bohemian mechanics. Yeah, yeah. David Deutsch was driven to, you know, proposed quantum computing by obsessing about the many worlds. Yeah, which, yeah, and you like me both. I think philosophy, you know, a philosophy can be used. Yeah, philosophical questions can be nice springboards,

but then you get, then you get away from them. And then you don't try, then you don't harp on many worlds. You point out we'll talk about. I was, you let me think that his fixation with many worlds is misplaced, because we'll get there maybe because all right fine talked about this in the context of corner we can we can go there at Harvard who'd really convince you know that this was the world is quantum mechanical why talk about trying to interpret it in terms of class mechanics we don't do that with anything else but before we get there um the um there actually was um oh yeah but you but by

having the way you have we learned it what's really useful i just was had a podcast with a well-known biologist the other day and he had learned quantum mechanics and quickly he thinks quantum mechanics is indeterministic which it isn't it's just the linear equation it's second order differential equation moving forward deterministically it depends on at what level you look at it yeah i know but fundamentally it's a deterministic theory which is a unitary nothing more deterministic certainly if you are a many world or or abominian then it is but yeah anyway well i don't think you have to say that to do that but we'll get there okay you went to the institute of study right after your PhD? I did you talk to. I mean, I was there for a while and I it was there

wasn't a quantum computing group or do you talk? Well, not not exactly. There was a, you know, there was and still is one of the leading theoretical computer science groups. And it's led by Avi Wigderson, who I had known. I'd actually spent a semester with him at that point at the Hebrew University in Jerusalem. And then, you know, he moved. He was in, you know, in the process of moving to Princeton, where he still is. And, you know, he's in the school of mathematics. So I was, I was part of his group. And, um, okay. Yeah. And, and, and, uh, you know, it was, you know, in, uh, you know, I mean, I mean, it was a very tough decision. I also, you know, you know, really like, you know, the idea of going to Caltech and, you know, working with

John Prescott. But, uh, you know, a large, uh, a large fraction of theoretical computer scientists go through office. Right? Okay. Now I understand that. Let me, then you went, you went to MIT?

Yeah, yeah. And, but, but I did talk to, you know, I actually gave a talk there about quantum computing that I was hoping the physicists would come to,

but the one who came was Pete Hut. Pete Hut, who's all, yeah, yeah, yeah. So I got, I, so I did get to know Pete Hut a little. I did talk once to Maldesina. You know, and I was, you know, trying to, you know, you know, that this was like 2005, right,

but I was trying to see, you know, what might string theory, you know, say about computational complexity. And, you know, he was reminiscing about it with me recently, right? He was saying like, yeah, you know, there was, you know, this crazy kid, you know, thinking that, like, quantum gravity and complexity theory were going to come together, you know, like, you know, how do I get, how do I get him out of my office? I mean, you know, I mean, you know, he was, he was actually very nice. He was very polite. But of course, you know, this was this was a decade before this integration really started to happen. Yeah, yeah, no, well, yeah, it was wondering whether, whether Ed or, well, actually, Freeman Dyson, I would have thought might have come because at least he was. Yeah, no, I mean, I, I, you know, in retrospect, I wish that I had been bold enough to talk to Ed or to talk to Freeman Dyson. And I wasn't. Yeah, when I was there, I, those are the two I knew, but I didn't hang out with a string theorist. So Freeman, Freeman,

was the one I spent time with because he didn't talk to anyone. I mean, he talked to people, but he was right in the middle. And he was fascinating. But you went to, so you went to MIT, which of course is a natural place to be. Yeah, I also had two years in University of Woodrow. And that was. Oh, yeah, that's right. University of World. Yeah, that had an institute for quantum computing. Yeah, so I went there. Yeah, they were, they were quite pressing. Yeah, that was that was, that was a, you know, very important two years in my, my career. And then, yeah, And then after that, yeah, I was lucky enough to get a faculty position at MIT. So, and that's where I was for nine years.

Yeah. And then I wanted to ask, because I mentioned you're not the first person I know who left Boston for Austin. A lot of my colleagues did when I was at Harvard and other places. And as you mentioned, Steve Weinberg was the first of the bunch to make that, to make that. And he was actually involved in recruiting us. I wouldn't be surprised. I would be surprised if it wasn't the case. Steve is a hero and amazing.

I used to visit Austin regularly to see him, just to see him. Probably the only person I used to see there. But why did you move? Was it because they created a center for quantum computing? Well, I mean, the immediate thing was just that my wife and I had a two-body problem to solve. That's why he moved to Austin as well. Okay.

Yes. It's a great way to get good people to solve that two-body problem. So we did a search together. And, you know, the options that we, you know, that we had, I mean, you know, we were, we were, we were lucky to have to have options at all. But, you know, they were, they ended up being four big state universities. It was Michigan, Maryland, Illinois, or Texas. And so we looked at all of them. And to tell you the truth, I never would have imagined living in Texas.

That is just not my, not on my radar at all. But we like Texas the most. You know, we like, we like Austin as a city. Austin's a nice town. We like, we know, we like the computer science department here. You know, they didn't, you know, have much in quantum computing, but they wanted to build something. And they had a very strong group in theoretical computer science.

Also, you know, I should say my wife, Donna is also a theoretical computer science. Oh, okay. You know, they were very strong in the kind of stuff that she does. And so, you know, this system ended up, being what we chose. Okay, yeah, yeah. And they did make your director right away of this quantum information center,

which I assume is an interaction with resources, I guess. I mean, that was well. Yeah, I mean, you're reminding me that I'll need to get more resources. But yeah. Anyway, yeah, yeah, no, you'll need. Now once the universities give you resources

when they think you may leave, and that's what I've always found. So maybe they think you'll go to open AI and they'll give you more resources. In any case, in the rest is history. And I notice among your prizes, they're groundbreaking contributions to quantum computing. And, um, and, uh, and those groundbreaking contributions, probably the reasons we first met

with the Waterman prize to come full circle. And, um, and which I see behind you, because I, I have mine up in my own. I see it right. I see it right back to my mind looks very similar. Oh yeah. Yeah. Yeah. Yeah. And, um, okay.

So let's start with quantum computing. And, and, you know, there's so many places one could go. But why don't we? talk about I want to I want to get to shore at some point but why don't we talk about what it is and what it isn't because you're absolutely right I look I'm I'm guilty of of when people asking quantum computing of saying well you know a an electron could be doing many things at the same time so you can do parallel calculations and instead of one calculation it's a simple way of saying what happens

and and and and you point out rightly that that's that's that's not not it. But why don't you talk about what common computing is and what it isn't, and I may interrupt you with questions in the interim. Sure. Yeah, I mean, I mean, you can see why people fall for that, because the actual reality of what it is, I think is weirder than any science fiction writer would have had the imagination to invent. That's what's great about science. It's usually weird. Yeah, exactly. And, you know, the way that I think of quantum mechanics is that it's a generalization of the rules of probability. So, you know, like, you might think that, you know,

it's just an axiom of math, that, you know, that it's not even physics to say, look, if you want to know the probability that something happens, like that a particle reaches a certain point, then the way to get that is you add up the probabilities for all of the different ways that the particle could have gone to reach that point, and you see what's the total, right? And then quantum mechanics comes along

and says that that's not true, right? There's a, you know, actually, the way that nature calculates probabilities, you know, at the fundamental level, looks very different from that, okay? And it involves that different. It's just a complex number instead of a real one. Well, yeah, that's right.

That's right. That's right. But, you know, you know, there's one change. Yeah. And everything else is the downstream consequences of that one change to the rules of probability. Okay. And the change is that now we have to deal with these numbers called amplitudes, which are complex numbers. Although, although actually,

you know, most of the stuff we care about in quantum information, you would already see just with positive and negative real numbers. Yeah, you could already see. I'm going to interrupt. But the, the important point is that they have signs, right? They have not just a magnitude, but they have a have a sign. Let me step back for the people. I don't anyone will have gotten this far if they don't know, haven't ever heard of a complex number, but just for people who know, yeah, their numbers that are more complex, it's because they involve the square roots of negative numbers. But effectively, it allows you a much more, a much more rich way of adding up things. Instead of just plus and minus one, you have all these other options for adding things

way away and that's what makes it richer. So I just wanted to step back so people. Yeah, yeah, sure, sure. So, you know, and, and, you know, complex numbers were, you know, discovered by, you know, mathematicians in the 1500s, right? And I think it would have blown their minds at the time if you told them that that nature actually uses these things, you know, at the deepest level, that they're, that they're not just the human invention, right? Yeah. But in all of science is requires them. It's amazing. Yeah, yeah, that's right. But so, so basically, you know, the key, well, I mean, I mean, we touched on this before, but, you know, the, the, the key thing that quantum mechanics says is that, you know, if I want to know how likely something is to happen,

like, you know, a particle is to hit, to be observed at a certain spot on a screen, then number one, I have to add up amplitudes for all of the different paths that it could have taken to reach that place. And then number two, I take the total amplitude, and then I take the square of its absolute value. And that tells me the probability. Okay, but now the big implication of this is, let's say that the particle could reach a place one way with a positive amplitude and another way with a negative amplitude. Okay, then there's two contributions can cancel each other out. So the total amplitude is zero. And that then means that the particle will never be seen there at all. Okay. Whereas if I close, you know, I mean, I'm saying this, you know, not for your benefit,

but you know, for people who haven't heard this before, you know, if I, if I close off a one of the paths that the particle could take, now I only have a positive contribution or only a negative one. And now, you know, the particle can be seen there, right? So by deep, increasing the number of paths that the particle could take, I can increase the chance that it ends up somewhere, right? This is the part that has, you know, you know, no analog in our... That's the basis of the famous double-slit experiment. Exactly, exactly. And now, you know, what's, you know, the, you know, the, you could say like the, the craziest part of all is that now if I just watch the particle as it's going to, you know, just see which path it's going, then, then, you know, I just.

don't get this interference anymore, right? Then then the different options just add up in, you know, just the same as they would in classical. Well, you just got rid of some of those negative paths. That's what you're saying. Exactly. Right. It's only, it's only when I, it's only when I leave the particle isolated from the whole rest of the universe that I see this, you know, the summing of amplitudes that leads to this interference. Okay. So, so interference is something that particles somehow like to do in private. You know, they don't, they don't like to be seen while they're doing it, right? Okay, so now what's a quantum computer?

Well, you know, to say that, you know, we have to say, you know, the basic building block of it is just going to be the quantum version of a bit, what we call a qubit, right? And what's a quantum? what's a qubit, it's just some bit that has an amplitude for being zero and an amplitude for being one. Okay, so it can be, as we say, in a superposition of the zero state and the one state. Okay, so, you know, mathematically we could say it's a unit vector of complex numbers, right? It's two complex numbers, you know, amplitude of zero, amplitude of one. But now, if I have, let's say, two cubits, then I can't just write down amplitude separately for the first cubit and for the second cubit, right?

I have to, because measuring one cubit might tell me something about the other cubit, right? And so there are four possibilities for two bits, zero, zero, one, one, zero, and one one, right? And we've known for a century now that quantum mechanics forces us to write down an amplitude for each of those four. But now it gets worse because if I have three qubits, now there are eight configurations of three bits, you know, from zero zero, zero, up to one, one, one. And so now I need eight amplitudes. You know, if I have a hundred cubits, now I need two to the 100 power amplitudes, right? a thousand, two to the 1,000 power amplitudes. And now already we have more amplitudes just to describe our thousand, you know, little particles than there are atoms in the observable universe, right?

And so, you know, and this has been a core part of quantum mechanics, you know, since Schrodinger, you know, wrote down his equation in 1926, right? He was very explicit about this, like, you know, if you read his paper. But in some sense, it is only with quantum computing that the full staggeringness of this is really brought to bear and that we're really trying to exploit it to do something. So quantum mechanics has been telling us that just to keep track of the state of a thousand measly particles, you know, nature off to the side somewhere has to maintain some scratch paper with more parameters. then you could write down in the entire visible universe. And every time something happens to those particles, it has to cross off all of those parameters and replace them with new parameters.

So that's a ridiculous amount of work for nature to be going to, from a computational standpoint, right? Just to keep track of what a thousand particles are doing. And chemists and physicists have, in a sense, they've known this for a long time, time, you know, but they've known it mostly as a practical problem. As a practical problem, if they want to try and understand even a small molecule, you have to calculate so many things to try to understand how quantum mechanically how

molecule behaves, much less a, much less a nucleotide or a DNA or a protein. No, absolutely. I mean, you know, so they've known that there's this exponential explosion and the number of parameters you have to keep track of. This is why, you know, very powerful. you know, supercomputers, including, you know, one we have here in Austin called Stampede, you know, are often used for just trying to solve the Schrodinger equation, trying to, you know, simulate complicated quantum systems.

And, you know, people have gotten very good at inventing approximation methods and the shortcuts, you know, that sometimes let you manage it. But, you know, but, but sometimes not. And so, you know, it was not until, you know, the early 80s. I would say that a few physicists, you know, most famously, Richard Feynman, and then David Deutsch, you know, started saying, well, if nature is giving us this, you know, computational lemon, then why don't we make lemon it? Yeah, yeah.

Feynman basically said maybe he could help him understand quantum mechanics, which is always Yeah, exactly. You know, so why don't we build a computer that itself, you know, would be made out of cubits that would exploit, you know, this exponentiality of amplitudes. And, well, you know, supposing you built that quantum computer, what would it be good for? Well, Feynman really only had one answer 40 years ago, which is it would be good for simulating quantum mechanics.

Yeah, I mean, and just let's step. I mean, that was what excite him. And let's step back. What he said is, look, I can't calculate. I know how to calculate the answer to this problem, but I can't physically do it. But if we use, if the calculator itself is quantum mechanical, it can do it in a way I can't do and get an answer.

And yeah, for Feynman, that was, and he was way ahead of his time, of course, but as always, but or often, not always. And, and yeah, and he said, yeah, let's make, maybe we can make quantum computers so we can solve quantum mechanics problems that I can't solve. And then maybe I'll better understand quantum mechanics. I understand the aspects of quantum mechanics

from interference and other things. Yeah, a biography of Feynman. Right. Now, now, now, now, it's a, important to say a quantum computer wouldn't be able to do anything that's literally uncomputable with a classical computer. Because if you had enough time, then with your classical computer, you could always just write down the entire list of amplitudes explicitly. But that could be exponentially slow. I think that simulating quantum mechanics is still today, 40 years later,

you know, after everything that's happened, it's still the most important economic application of quantum computers. Yeah, let's stop, let's stop everyone because it's a fascinating thing to say that in the end, and I agree, and it's something I think that, that Breslin I talked about, because it's not what you get in the media. The media, that's right. That's right. Absolutely right, right. But, you know, that was not what put quantum computing on most of the world's radar. It was something. What put it, well, what, what, what originally put it on, you know, most of the world's radar,

including the computer science community, you know, and the math community, was a sequence of discoveries in the 1990s that culminated in showing us that a quantum computer can sometimes get enormous speedups over anything we know how to do with a classical computer, even for solving problems that have nothing to do with quantum mechanics. You know, purely, purely classical problems. Yeah, in principle. You know, the famous example here is finding the prime factors of enormous numbers, which, you know, for better or worse,

there's a problem that much of the security that protects the modern internet is based on. Well, let's face it. I mean, I mean, I'm, I watch this from an outsider. I watch it explode after that. Yeah.

And yeah, of course. And it's kind of fascinating. It's the same, but it's interesting. The reason that physics, that particle physics and, you know, exploded. And it was because they could do the atomic bombs

and it was, and the defense of the nation seemed to be, okay, we'll throw out. as much money as you as we as you want but there maybe there's other things you want to do but we're interested in it for this reason and it was amazing to see i think the first i could be wrong but from it outside it looked like the first group to start funding was defense for the same reason and if you could factor pro large prime numbers you would be able to crack the like financials yeah and therefore we're as much money as possible at this field and you can worry about your other physics questions but

right well i mean i mean i mean that that was certainly the discovery that made, you know, the military and intelligence communities interested in this, right? Money. You know, but, but, but, but, but, but, but, but, but, but, but, but, but, but, but, but, that's right. That's right. That's right. Now, you know, the main ones driving it are, our private companies, you know, who are hoping that it's going to be a massive accelerant for AI and machine learning and finance. Exactly. It moved on those things. Just as part of the course. And those claims

are often very iffy ones. Yeah, we'll get there. They're very iffy. We can we can get it into that. But what I wanted to say was that, you know, the way that almost every popular article will explain quantum computing, you know, still to this day is just by saying, well, you know, classical computer with classical bits can only try the possible solutions one by one, right?

And, you know, if there's an astronomical number, then that could take longer than the age of the universe. Whereas a quantum computer can just try all of them in parallel, in superposition, you know, and that's the source of its speed, right? But, you know, that kind of sounds too good to be true, right? Like, wait a minute, I just get this magic machine that lets me, you know, try everything in parallel, right? And it turns out that, yeah, that is too good to be true, right? And that was one of the earliest things that people had to understand is that the only hope of getting any advantage at all from a quantum computer is to exploit the way that these amplitudes being complex numbers are different from probabilities, right? And specifically, it's to exploit this effect of

interference. Okay. So basically, you know, I think I think the right way to think about it is that with every algorithm for a quantum computer, we are trying to choreograph a pattern of interference, right? And we're trying to make it to that for each wrong answer, each one that we don't want to see, some of the contributions to its amplitude are positive, some are negative, or, you know, at any rate, they mostly cancel each other out. Yeah, they're pointing every which way, right? Whereas, For the right answer, the one we do want to see, we want all the contributions to its amplitude to be mostly pointing the same direction, okay?

And so that they all reinforce each other, right? And if you can arrange that, then when you make a measurement, quantum mechanics tells you're gonna see the right answer with a high probability, right? You know, of course, high probability is all you need. If you don't get it, you can always try again until you, you know, until you get it, right?

because I mean, it's a beautiful explanation, but it also emphasized something else that I know I've learned from your descriptions, I think, that what people don't realize is that you end, there may be all these cubits, but you measure something in the end. And so you get a number out at the end. And so we get all these parallel calculations.

You could say in some sense, this exponential amount of information was there, quote, unquote, you know, what I call this giant scratch paper, you know, with all of these, these parameters, but we never directly see them, right? And you could ask if we never see them, how do we know that they were ever there in the first place, right? Well, we know that we need them to calculate the probabilities of the different things that we do see, right? But when we look, then all we see is, you know, if I have N-Q-bits and I measure them, then all I see at the very end is N classical bits. And the whole game is to choreograph the interference pattern

so that those classical bits are the ones that I want, the ones that solve my problem, right? Now, the hard part is, you know, I have to choreograph this whole interference pattern that magically concentrates amplitude on the right answer, even though I don't know myself in advance which answer is the right one. You know, if I knew that, what would be the point, right? You know, and I have to do it all faster than a classical computer could do the same thing, or else, again, you know, why didn't I just do it with a classical computer, right? Right. So, you know, nature gives you this really bizarre hammer, right? And it's not obvious whether there are any interesting nails that that hammer can hit, you know, other than, you know, maybe simulating quantum mechanics itself, right?

And that's why, you know, it was really a non-trivial discovery, you know, in the 90s that there are classical problems where we can figure out how to, you know, design this, this interference pattern, you know, shape it in the right way. that took more than a decade after Feynman. Yeah, sure. That's when people got excited. Now, you have given, and I've read your, I think probably the first time I really understood, I missed admit the real time, yeah, first time I really understood Shores algorithm,

I was reading your explanation of it. I'll be open and say that. I don't know whether, so the problem is easily framed. Once again, large, you know, you're, it's very, It takes longer in the age of the universe to take a very large number and find the prime factors of that very large number. Well, it might. No one has proven that, right? Yeah, okay.

That's right. So far. I've even talked to mathematicians who strongly believe that there is a fast classical way to do it. But the reality is no one knows. Well, you know, what's interesting. Yeah, yeah. I will tell you this as a physicist, maybe something, an analogy that you haven't heard before. I'm amazed that you don't take things seriously until they've been measured.

And so I've written a lot of papers about stuff that I could have written before, but I never really thought about it until some experiment came along and that, oh, you know, and the interesting thing is when we get to quantum supremacy, that it was only after sort of this claim of quantum supremacy, it seemed to me, that people started to realize, oh, I've got a classical algorithm that's actually much faster because I'll take it seriously. And you're right. This sort of thing has happened.

I mean, there have even been interesting new classical algorithms that were only discovered because people were first thinking about quantum algorithms. Absolutely. I think it's interesting.

I think it's fascinating how that happens. Yeah, absolutely. It's set back. It may be that it takes long. Apparently, if you don't think hard enough, it takes longer in the age of the universe to do to empirically find the prime factors

because you'd have to try every prime factor in a big number. I mean, we know methods that are somewhat better than that, but they're still, you know, some kind of exponential. Best methods, like the ones that the NSA is presumably using to, you know, try to, you know, break, you know, cryptographic keys. They take an amount of time that grows exponentially with the cube root of the number of digits. Okay, there we go. So it's exponential. Anyway.

And so what, what was a surprise was that there was a quantum algorithm, rhythm that might allow you to find the prime factors of a large number that was only polynomial in the number of size of the number. Yes. Yes. Well, in 1994, Peter Shore proved a theorem. And the theorem says, if you build a quantum computer, and, you know, if it works, like the theory says, then it can, in fact, factor a number that's end digits long using a number of elementary operations that only grows like roughly like n squared. So that so that so that so that is exponentially faster okay now. Now we've taken a long time already and we've got a lot left to do so I don't know if I'm

going to ask you and you may not I mean I've read your argument it would take 15 10 or 15 minutes is there I mean I mean I mean I mean I mean really it's sure's argument I'm just okay okay sure's argument but is there a simple yeah yeah is there a simple kind of one minute way of saying what the trick is or not? If there isn't, it's okay. I mean, I can try. So the key is, you know, it's, there's, there's, there's a half of Shores algorithm that's got nothing to do with quantum mechanics, okay, where, you know, it's just about a number theory, really, okay? Where you're taking the problem of factoring and you're reducing it to a superficially different problem. Okay. And the different problem,

looking problem that you reduce factor into is called period finding. Okay. So, so consider the problem where I have this enormous sequence of numbers, right? It could be like a sequence of, you know, a Google numbers, right? You know, whatever, right? But, and this, and you're told that the sequence repeats itself with a certain period, right? So it's a, it's secretly a periodic function. Okay, you can compute any desired entry of the sequence, right?

you have an algorithm that, you know, given, you know, you ask for, you know, entry number or J, you know, it tells you what that is pretty quickly. But now your task is to discover what is the period, right? And so now, you know, we, so, so what, what, the first thing that Shor showed was that if you can solve that problem, then you can also factor, right? And the reason, you know, it's a few lines of algebra, basically, right? But not having a board, I probably won't go through it. So, but you know, it's, you know, the point is, you know, a lot of interesting problems in number theory sort of can be boiled down to sort of finding this hidden periodic structure, you know, in a periodic function.

Okay. There's there's something called, you know, if I have some composite number, there's something called the multiplicative group, you know, modulo that composite number, all the number, all the numbers. numbers that are relatively primed to it. And basically what I'm trying to do is discover how many elements are in that group. And if I figure that out, then that also reveals to me what are the factors. Okay. So I'm trying to figure out the order of this group, you know, and to do that, I have to find the hidden period of this periodic function. Okay.

So now, you know, how can we do that? Well, if I just had a classical computer, I could imagine that I just had a classical computer, I could imagine that I just pick a bunch of random elements in the sequence and I hope that eventually I get lucky and I find two elements that are the same. And if I find two that are the same, then I know that whatever was the period of the sequence, it divides the difference between, you know. Okay. But that would take again an astronomical amount of time. Right. So now, so, so, so so here's where the quantum computed is going to come in. Okay. So now what Shore says to do, you know, and he was directly building on, you know, earlier work by

Bernstein and Vazirani, you know, Vazirani was my advisor at Berkeley, you know, and then, and then, and then Dan Simon, who did, you know, very closely related things, but they didn't solve a problem that was, you know, as high profile as factor, right? And then, and then, you know, you know, but now is going to come, you know, the step where we need to exploit quantum interference. So we create an equal superposition over all of the possible, you know, elements in the sequence, right? We calculate all of them in superposition, okay? So, you know, so now so far we have, it doesn't look like we've made that much progress. because if I just took this superposition over all the elements of the sequence and I just measured it right now, you know, if I was impatient, all I'm going to get out will be a random element of the sequence.

Yeah, right? And I didn't need a quantum computer for that, right? Okay, so now somehow I have to exploit interference, right? And so what I do is, you know, I do a sequence of unitary operations on my qubits that has the effect of taking, this giant vector of amplitudes, you know, that encodes my periodic function and replacing it by its four-year transform. Okay. So now, you know, the four-year transform, as you know, you know, for the benefit of our listeners, it is, you know, one of the most basic operations in, you know, linear algebra and, you know, has been central to quantum mechanics since, you know, Isaac wrote down. on the uncertainty principle, right? But it is a, it's a linear transformation that sort of, you know, it's a change of basis that sort of moves you from, you know,

looking at, you know, an engineer might say moves you from the time domain to the frequency domain, right? So it moves you from looking at your sequence, just element by element, to looking at it as a sum of periodic contributions, you know, each of which has a different period. And so what you do is you, you know, you do this short sequence of unitary operations, each of which acts on only one or two cubits at a time. But it has the effect of taking this amplitude vector, replacing it by its four-year transform.

Okay. And now the four-year transform was designed from the beginning to reveal periodicity information, right? And so now you get like these giant, you get a new quantum. superposition, but that has giant spikes at numbers that, you know, are, you know, they're not necessarily, you know, like the period themselves, but they're like, they're like close to integer multiples of inverses of the period, right? And so, so now you measure and now you get numbers that, that are, you know, that, you know, if I just see a few of them, then just using my classical computer, I can put them together and reconstruct what the period of the sequence was.

Okay. And a good way to think about what's going on here is that like for every possible number that I could have measured, right? It has an amplitude that's a sum of many, many contributions, right? But only for the ones that are multiples of the inverse period or very close to them are all of the contributions to their amplitude adding up constructively? Are they reinforcing, right? For the wrong numbers, you know, I have the contributions are just pointing every which way in the complex plane, and they're just canceling each other out. So that's, that would be, I don't know if that was like three minutes or, but, you know, that would. But it was, and I think people get the idea. Yeah, that would be, that would be my summary of Shores algorithm.

It's a great. When I teach in my undergraduate course in quantum information, you know, you can just do this in full details in about three lectures. Yeah, it's really amazing. But it demonstrates something, but now I want to get, and some people, I'm sure, got lost during it, but, but may not, well, maybe no one did. But I, but I suspect some did. But I want to, but it's important to talk about it because now it, when one of the things I think, which is clear, you've already made clear, but people don't recognize is the world. I would say now, and this is something that took me a while to realize and you help me. But over the years, It's when people talk about what fun of commuteers are going to be used for, I would argue that that's as like the, that cracking financial codes or is is going to be the last is, is not realistic in the near term. I'm not sure that it's ever realistic in the long term. And it's probably not going to be the number one one activity.

I mean, I mean, I mean, first of all, I think it is realistic in the long term. Okay. Well, it's going to require, if you have, it's basically, I think once you, okay, so we haven't talked about the practical problem of how do you build. The problem is how do you keep N cubits going? I mean, that's right. That's right. How do you know, you're going to need a large number of cubic.

So that's what I want to get to next. Exactly. Exactly. So the main problem is that you need what we call error corrected cubits or full power in cubits. One's that, you know, so, so, you know, like I said before, quantum states are very fragile, right there you know like a being in super position is something that particles only want to do in private you know exactly and that's really important i want to emphasize that because people don't get it

when they see the difference in quantum mechanics and class mechanics or the exploitation of quantum mechanics at a macroscopic level requires something it's very unnatural for particles or anything the reason we're not quantum mechanical or don't behave quantum we are at some fundamental level but we don't behave that way is it where a mix mash of particles interacting with the all think which other in my body and all the photons from the lights that are yes and it's all washing out all of measuring everything else that make quantum mechanics so special and that's why we don't ever see it and so what you've got to do if you have a bunch of these if you have one a large if you don't have a large number of bits i mean you know my my phone has a large number

of bits in it um gigabits and you know and and but but if i'm going to have a large number um then i got to make sure it somehow that large number remains quantum mechanical and that And if it did, then I would be used to it. And so most of the time it doesn't. Exactly. No, you could say that that problem is so staggeringly difficult. You know, how do you keep your qubits, like, you know, almost perfectly isolated from everything else in the universe,

but then also have them interact with each other, you know, in this precisely choreographed way, right? And, you know, like something has to come in and tell them what to do, right? It's so hard that there were distinguished physicists and computer scientists, scientists in the 90s who said this is fundamentally impossible, right? This is like building a perpetual motion machine or a Maxwell's demon or something like that, right? Like there, you know, like maybe this works with a few cubits, but this can never scale

to a large number of cubits, right? And I think, you know, a priori, like, okay, that was a plausible position, right? Sometimes you can write something down formally that, you know, that abstracts away some key feature of the real world that would actually make it impossible. But, you know, then there was a key further discovery in the 90s that convinced almost all of us that this is, quote unquote, merely a staggeringly hard engineering problem, right? Not requiring any new physics. Okay. dollars. Peter Shore was again, you know, very involved in that discovery, and then a bunch of other

people were as well. And it culminated, and basically what it said is that there are, you know, in the classical world, right, when we have noise in a communication channel, right, we deal with it using error correcting codes. But, you know, and this goes back to Claude Shannon and, you know, Hamming and many others, right? But for example, instead of sending either a zero or a one, I might send zero, zero, zero, or one, one, right? And then if any one of the three bits flips, then I can still recover the message by just taking the majority of the three. Right.

And you know, and you know exactly. And you could test to see whether it was. Yeah. Right. And now that doesn't immediately work for cupits because, you know, one reason is that you can't clone, you know, a quantum state. right? If you don't know what it is, there's no, you know, there's no way to make a copy of a of a qubit. And, and also, you know, errors in, in, in qubits could be continuous, right? It doesn't just have to be a discrete bit flipping. It could be any little change to these amplitudes. And so some people

said, well, this seems like an analog computer, right? And analog computers never, you know, you know, you know, they didn't win in the end, right? And the main reason was error was, you know, that the, you know, you would just have errors that would build up and kill you. I mean, that's why digital computing won. Okay, but the key discovery of quantum error correction is that there are these very clever quantum generalizations

of error correcting codes, right? So, you know, the first one discovered was called the short code, right? It encodes a single cubit, a single logical cubit into nine physical cubits, okay? You know, it turns out, you know, nine is not the minimum. You can also do it with five, okay? But you know, classically, you needed three, right?

Quantumly, you need five, okay? And what these quantum error correcting codes do is that they, they allow you to make a measurement that just that only tells you, like, didn't ever happen. And if so, what do I have to do to fix it? And it doesn't tell you anything else about the qubit, but you don't want to know more. You don't want to destroy the that would destroy the state. So you know, you know, you know, that that that that that joke where like someone calls 911 and says, oh my God, you know, this person was, you know, was was was was shot and

you know, and was killed. And then they said, well, okay. And the dispatcher says, okay, but did you check to make sure that they're dead. And then you hear a gunshot. And they say, OK, all right. Now I'm sure. Now you know, what now? So you know, quantum error correcting codes are kind of like that. It's like you know, it's like, you know,

if there was some tiny rotation in the amplitude, like well, you say, was that an error? Was that not an error? Well, the way you decide is by making a measurement, right? And the result of the measurement might be that it just snaps back to where it was before. And then, OK, I guess there wasn't an error. error or the result of the measurement might be that it flips all the way and then okay well i guess there

i guess there was an error but now the error was discreet because i measured and i made it discreet right and now i know exactly where it was and i know what i have to do to fix it okay so so this this whole line of work culminated with something called the fault tolerance theorem or the threshold theorem which said that if you want to build a reliable quantum computer you don't don't have to get the rate of noise, the rate of interaction between the qubits and the external world all the way down to zero. You merely need to make it very, very, very small. But there is some non-zero rate of noise, which is low enough that you can then use error correcting codes to push the effective error rate as close to zero as you would like.

So there is a threshold effect. you know it's kind of like you know the critical mass for a nuclear weapon right if you're halfway there you don't get half as big an explosion yeah right it's like you have to you have to be able to correct the errors faster than you are introducing new errors you know by by by by by by by by by by by by by by by by by by by by by by by by by by by there's some finite rate of error where where you know you where this becomes a net win and you know you could think of the engineering goal in quantum computing for, you know, ever since then, you know, really for the past 25 years, has just been trying to get better and better control over quantum systems until ultimately you would

pass this threshold of fault tolerance. And at that point, once you have fault tolerant cubits, then it really is just an engineering problem, right? Like, you know, how many, you know, you could have in principle as many cubits as you want, and they'll stay alive for as many operations as you want to do with. Yeah, which is the holy grail. And now. That's right. That's right.

And it is, you know, if you look at the numbers, you know, it's, you know, it doesn't even look like a totally unattainable grail. I mean, when I entered this field, you know, in like the late 90s, you know, it would have been spectacular if you could do, you know, a two-cubit gate. So just, you know, an interaction between two qubits with like 50% accuracy, right, or some number like that. Okay. And then that 50% became 90%, you know, came 95, you know, with Google's quantum supremacy experiment that it announced four years ago, you know, they had like 53 cubits and they could get any two neighboring ones to talk to each other with 99.5% accuracy, right? for some short time.

Yeah, that's right. Within the last year, you know, groups like IBM, Quantinium in Colorado are talking about 99.8% pushing 99.9% accuracy. Okay. Now, our best estimate from fault tolerance is that if you could get this to 99.99% accuracy, then quantum error correction should start to work. Should start to be practical. Okay.

So, you know, if you just plot it on a graph, it looks like, you know, we're now only about one order of magnitude away. Exactly. And I should look. So it's a, it is a, it is nevertheless a an experiment. It's a, well, as you mentioned, with lots of money and lots of time, people, there's improvements, but it's experimentally at the limit of what we can do. It is. And. Oh, yeah. I mean, these are amazing experiments. But, you know, I mean, a priority. you might have worried that this would have to go on forever. Yeah, no, no, in fact, I would say that I was one of the naysayers before fall tolerance. I was saying, there's no way you're going to be able to get a quantum system to survive long enough to do what you wanted to do. Yeah.

And then, okay, well, now it's still a challenge to get it to survive long enough for enough cubits. But I guess my point is, you know, so if you have, if you have, you know, 80 cubits, then maybe you can begin to do something, you know, realistic when it comes to issues of cryptography. No, no, no, you're going to need a lot more than 80. Yeah, okay, maybe a lot more. So basically, no, people have gamed this out in a lot of detail at this point.

So, I mean, if you want something that's useful for breaking cryptographic codes, then you're going to need a few thousand logical cubits. A few thousand, okay. And then with error correction, that's going to translate into millions of physical cupids. Okay, so this is my point. I guess what I was trying to say is a physicist rather than the mathematician is you're right. I don't think there's any logical barrier.

But my point before we leave this area or at least talk against the conventional wisdom, is that with five cubits, you can do really interesting quantum mechanical problems of that, you know, molecules. And that's feasible. What I wanted to say is if you're going to get to this realm, which one day we may get to, of doing things that are realistic cryptographically, well, already the world financial system will have adjusted that you can be done. Oh, yeah, yeah. That's a different discussion. Yeah, I guess what I was saying is for those who think the world financial system

is suddenly going to be broken, the time scale of quantum computing improvements with fault or correction is such that it's not going to, may there be other problems, it'll help, with, but, but, but, but, but, but the world financial system will have long go past that by in some other way. Yeah. So, no, so, so, so, so, so I did want to talk about these engineering issues, but I, I, I agree with you that, you know, breaking public key cryptography has never been the sort of, you know, you know, well, well, you know, it's, first of all, it's far from obvious that it's a positive for humanity if you can do that. Yeah. It's a, you know, it, it all depends on who has the capability and who else knows about it.

Okay, but second of all, you know, we already know cryptographic codes that seem to resist attack, even with quantum computers. Okay, now it's going to be a massive effort to get everyone to migrate to those new cryptographic codes. And, you know, and the crypto community for the last decade

has been, you know, pushing that. And, you know, the National Institute of Standards and Technology NIST just concluded a competition to, you know, come up with the standards, for post-quantum cryptosystems. You know, the winner, as many of us had expected, are these public key cryptographic codes

based on high-dimensional lattices. Yeah, yeah, no, I... Yeah, yeah, and, you know, so these systems exist. They do require, like, larger key sizes, larger message sizes than the, the cryptographic codes that currently underpin the web. So, you know, so they're a little bit annoying, but, you know, they can,

be used and people are already thinking about how to deploy them. So, you know, if we succeed at migrating everyone to post-quantum cryptography, then, you know, you could say, you know, like, in practical terms, you know, Shores algorithm could just be this, this colossal, you know, scientifically fascinating, nothing burger, right? You know, it's, you know, it'll just, you know, we'll just all be right back where we started, right? And so, so I think that, you know, the, the, the, the, the, the, the, the, the, the, the, the, the, the, the, the, the biggest hope of Look, I mean, for me, for me personally, the number one application of a quantum computer has always been just to disprove the people who said quantum computing was impossible. Okay. And by and by and by and by and by token for me as a physicist, you might say the number two application is to demonstrate that quantum mechanics works.

Yeah, that's right. We can we can we can we can we can collapse those and you know, is the same thing. It's really the same thing. It's different sides to the same coin. It's like a quantum computer as the same sort of thing as, you know, the LHC or LIGO or the James Webb Space Telescope. You know, it's you're just probing nature in a new regime. And of course, you want to do that if you can. Yeah.

I mean, there's some of people like me. And then I think I think the number two thing is to give us this general purpose programmable tool for simul quantum mechanics, which might be useful for designing new batteries or solar cells or high-temperature superconductors or drugs, you know. Drugs, but, but, you know, I mean, I mean, the truth is we don't really know. We don't know. We don't know what such a device would discover. But, you know, I think there's a, there's a pretty strong case that, yeah, that would be,

that would be useful to have. Yeah. And we know we don't know. That just makes it so exciting. Right. Right. And then, you know, I think, um, I'm, um, I'm, um, I'm, um, um, I'm, um, um, um, I'm, Neither of those things is what has mainly driven the investment over the last decade, right?

Yeah, yeah. The reason why there's, you know, these billions of dollars being invested in quantum computing now by Google, Microsoft, IBM, Amazon, and then, like, I think hundreds of venture-backed startups, you know, at this point, right? It is, you know, what people have mainly gotten excited about is the hope that a quantum computer will accelerate machine learning, optimization, financial problems, AI problems. And here, you know, as a quantum algorithms person, you know, I, you know, honesty compels me to report to you that the situation is much, much ifier. You know, yes, there are some quantum advantages that eventually, you know, you should be able to realize for those problems. Okay. A lot of them derive from Grover's algorithm, which I mentioned before, which is, you know, maybe the second most famous quantum algorithm after shorts.

Grover's algorithm can be used for sort of searching any list of n possible solutions in only about the square root of n steps. And so it has an enormously wider range of application than Shores algorithm does. Shores algorithm is really, really specialized to factoring, period finding, you know, and a few related problems in like group theory and number theory, right? Grover's algorithm is for like, you know, you can just flip through a computer science textbook and like, you know, two-thirds of what's there could be groverized in some way, right? So, you know, it could be a workhorse for all kinds of things. But the disadvantage is that the speed up is not exponential.

The speed up is only, quote unquote, by this square root, you know, this quadratic factor, right? And now that has to compete against the enormous overheads that it would take to run a fault-tolerant quantum computer at all, right? So it's like if you can take a problem of size N and solve it in, you know, you can, you know, like as theorists, we'd say, you know, Grover solves it with scaling that only grows like the square root of N. But in practice, that's probably something like a million times the square root of it, right?

And so now the point is N has to be big enough that a million times the square root of N is less than N. And you can solve that, but you know, and has to be pretty big, right? Yeah, actually pretty big. So, so that's the main issue with all of these speedups based on Grover.

And so then people say, okay, but, you know, there are all, you know, we don't need an algorithm with a provable performance guarantee. There were all of these heuristic quantum algorithms. Okay. And so, so a lot of the excitement over the last decade has been driven by things like quantum annealing, you know, which is like the quantum adiabatic algorithm, you know, which my, you know, is, you know, is, I alluded to before my former colleague Gad Farhi and his, his, his, his friends had developed this. You know, and these are like, you know, there are these classical, heuristic algorithms, you know, that don't always work, you know, often don't work, actually, but often enough, they do work.

A famous example would be simulated anneal it, right, where I just start with a random solution and then I just keep flipping bits, you know, if it looks like it's improving things, right? And I try to get to as good of a solution as possible. And so what people have done is that they've invented quantum, versions of those heuristic algorithms. And then, you know, and now here's what happens, okay? Like as theorists, like, you know, we don't know what the hell these things do, right?

But we can't rule out the possibility that at least sometimes they might solve these AI or optimization problems exponentially faster than any classical algorithm, right? And so then the sort of, you know, business people or the funding people, like, that's all they need, right? Then they just be like, you know, okay, so then let's just make the most optimistic assumption imaginable, right? Let's just assume that these will get these exponential speedups for all of these problems that, you know, but now, you know, you can see, like, like, there is not a case here that is, that is anywhere near, like the case that Shores algorithm helps you with factoring, right? And in fact, what is what is turned out again and again

is that when people have claimed to be able to use these heuristic algorithms to get the huge quantum speedups again and again people have been able to decontize them okay to say no actually if we think about it enough we can replicate that sort of performance with a classical computer which is what which is sort of what happened and i want to leave quantum community a second but which is sort of quantum supremacy quantum supremacy which the term coined by prescoe i guess was it was is the idea that basically, you know, you've gotten a point when quantum computers can do something. Maybe not something interesting,

but something in a finite time that a classical computer would take longer in the age of the universe. Well, there was a big report, 2019, Google, you know, and then, but then IBM, as you might imagine, came up and said, hold on, there's a, actually we found out to do it in three hours instead of two minutes or something like that.

And I should say something because I was heavily, involved in this story. Yeah, I know. Okay. Yeah. So, so, so, you know, I mean, I mean, you know, my student and I in 2011, you know, proposed, you know, one of the, the, the, the, the, I guess, I guess the main ideas for how you would do this, these quantum supremacy experiments, right? And then, and then a year later, Prescoe coined this term quantum supremacy to refer to, you know, things like what we had proposed, right, where you're not trying to solve something that is useful. You're merely trying to solve something that is well-defined and that is classically hard. Yeah. Right. And it turns out that, you know, if that's your goal, then it looks like the most direct way to do that would be using

what are called sampling problems, where they don't have a single right answer, right? You're just trying to output samples from some particular probability. distribution, like over, over, let's say, 50-bit strings, where you could argue that, you know, plausibly any classical algorithm would need a much, much larger amount of time to sample, you know. And so then Google, you know, in 2014, hired this, you know, leader in superconducting cubits named John Martinez. And Martinez said, you know, let's do this. Let's actually, you know, try, But it wasn't my proposal because mine and my students called boson sampling was sort of best adapted to optical quantum computing.

And they were doing superconducting quantum computing, but they said, let's adapt boson sampling to our setup. And we said, okay, you know, you could do that. And we sort of adapted the theory to what they were building. And then in 2019, they reported a result, which was that using 53-com, you know, qubits. You know, they could sample from this distribution over 53-bit strings, you know, in a few minutes. And at the time, they estimated that, well, the best classical algorithm that they know would take 10,000 years to do the same thing. And, you know, and then that number got picked up by the

media, right? And that was kind of unfortunate, right? Because, you know, you always have to ask the question, like, you know, do we really know what the best classical algorithm is? Right. And so, you know, since then, starting with IBM, but people have gotten better and better at spoofing these experiments classically. And I would say that the situation right now is that some quantum advantage remains in these experiments. You know, if you measure it, let's say, by, you know, how much money does it take to run the machine or, you know, how much electricity does it take? You know, I mean, the quantum computer needs a dilution refrigerator. It's cooling your chip to, you know, a hundredth of a degree above absolute zero, right? That's, that's a decent amount

of electricity right there. Okay, but, you know, to simulate it, you need a quite large cluster of classical computers, right? And maybe that's a hundred times more electricity or something like that, right? So I think there's some quantum advantage that remains, but it's only by two or three orders of magnitude. Almost certainly, you know, better quantum supremacy experiments could be done right now that would reestablish a larger gap. But, you know, but, but, but, but now what's happened is that, you know, the big players like Google, uh, IBM, like they barely even care about quantum supremacy anymore. They just say, you know, let's let's go straight for our correction, right? You know, I, I, I would actually like to see some, you know, better quantum supremacy experiments. No.

Okay, well, let's, let's see if they, what happens. Um, yeah, look, before, okay, I was going to talk about, you know, you wrote some beautiful work on, well, I mean, that I found interesting on what it needs to, to what, what, how much structure is needed for quantum speedups. But I think, I think I want to proceed. We're going to go the three hours, just so you know. And, and, and, and, and, uh, I want to spend the last hour of this on the harder questions because he spent less time on them because they're harder questions. But before we leave it in the last few minutes. All right. There's a quote from you that I found interesting. There's lots of quotes.

I have, I should say I have 20 pages of notes, which I'm going to, of which we'll probably go through four or five. But here's a quote from you that I don't understand. Well, maybe. If quantum mechanics seems to predict that you can harness an exponential number of amplitudes for computation, then so much the worse for our present understanding of quantum mechanics. I don't understand. Well, I think I was, no, no, no. I was stating that as a possible position that someone could take.

I was not myself endorsing that. Oh, okay. Okay, good. Okay, maybe I read it wrong. Because there are people who somehow think that quantum mechanics is wrong. I don't know what. Well, I do. One of them is a good friend.

You know, a good friend. You know, he does believe that. You know, but he, I mean, he also, you know,

I mean, he has a particular idea for a classical theory that would replace quantum mechanics. But, you know, I would say that it can't even explain the violation of the Bellin equality without postulating, like what,

what to my mind is, mind is like a giant cosmic conspiracy theory. Yeah, I agree. But he has a good track record. So I'm going to, yeah, I know. He's the right to, like I say about Bob Dylan, he can, he can, he's earned the right to do whatever he wants. And so it's hard to solve most of the problems of the physics in the 1970s.

Many of them can do whatever the heck he wants. And he's worth listening to. There's some people I would chalk off. But anyway, so we will see, of course, that's the great thing coming back to that's right. That's right. Either way, let's find out the truth. It's like the skeptics of quantum computing,

I believe that they're probably wrong. But if they were right, then that would be even more exciting. Yeah, it would be even more exciting. Exactly. And coming back to five minutes, really, you know, his interest was learning about quantum mechanics. And we may. That's right.

I would argue we'll get to whether it's relevant. You know, you talk about the philosophers. You wrote a whole 50-page article, which I had to plow through, than we're talking to philosophers about questions that I may be of interest to philosophers, but not to physicists as far as I'm concerned. But we'll get there because we're going to be led there in the next half hour. I want to talk about computational complexity, which is really your, I don't know what a forte,

but I think it's what you're real, from what I can tell, your real heart is an understanding, which is different. So complexity is different than computability. Now, obviously, we don't have, I time, do justice to this, nor could I, I think, do justice as much as I've tried to wrap my head around it. But there are a few things I think we can talk about. One is the, when do you talk about the difference between complexity and computability? So, computability is the field that you could say, Alan Turing, you know, and his friends started in the 1930s when they created computer science in the first place, right? It said that computer science is one of the only fields that was born with the knowledge of its own limitations.

So in the very same paper, you know, one of the most famous papers of the 20th century where Alan Turing introduced the touring machine, right, which is the mathematical model for what we would now call a programmable computer. he also proved a theorem that said that, you know, there are some well-defined problems that a touring machine cannot solve, okay, you know, regardless of how much time or memory you might give it. Okay. And the famous example there is called the halting problem, right? And it's a problem where you are given as input a touring machine, or in other words, a description of a computer program. You know, it could be in any programming language of your choice. And you need to decide. whether that program will ever stop running or not. Okay. So, you know, now, like at first glance, that problem might not seem so hard, right? Like if you think about, you know, anyone with experience programming would say, yeah, I can just kind of stare at the program. I can see, does it have an infinite loop? Does it, you know, does it not have one?

Okay. But, you know, you can easily invent, you know, incredibly hard examples. So, so, for example, imagine a program that just, you know, checks all of the even numbers four and higher, okay, and tries to write each one as a sum of two prime numbers, okay? And it halts only if it finds an even number that cannot be written as a sum of two primes, right? Then this is a program that halts, if it only if it finds a counter-example to the Goldbach conjecture, you know, saying every even number four and above is a sum of two primes. that is still an unsolved problem in number theory, right?

And so solving the halting problem, you know, would automatically also solve, you know, a large fraction of the great unsolved problems in math, right, which can be phrased as, you know, does some computer program ever stop running or not, right? And what Turing said is that, you know, yes, there are specific programs where we can figure out whether they halt or not, but there cannot be any general math. method, you know, at least you know, using computer programs themselves for solving this halting problem. And the way he did that was a, you know, a self-referential argument, you know, which is, I think, you know, a justly famous. I mean, he was inspired by, you know, girdle's incompleteness

theorem, which, you know, had been proved just a few years earlier. And, you know, and even before that, by, by Cantor's discovery, you know, of the different orders of infinity, okay? But, but, but, What Turing basically said was that you suppose to the contrary that you had a program that could solve the halting problem. So it took any program and determine whether it halts or not. Then you could modify this program to basically be one that would take itself as input, take its own code as input, and do the opposite of whatever it does. Okay, so it could analyze itself, and if it determines that it is going to halt, then it would run forever. And if it determines that it would run forever, then it would halt. Okay, and that's a contradiction.

And the only conclusion is that the program can't have existed in the first place. So a computability theory, you know, in the decade since the 1930s was developed to, you know, a very high level of sophistication. you know people discovered that you know there there are other interesting examples of uncomputable problems so for example if i just give you an equation you know and i ask you does it have a whole number solution you know so solving a diophantine equation that is equivalent to the halting problem right there could be no there can be no general algorithm to solve that problem and again it's not even a question of time or memory right they're just it's a mathematical proof it's a question of finite versus infinite, right? It just, you know, that there is, there is no way to take,

you know, the infinite number of possible solutions and, and rule all of them out in a finite amount of time. So, in fact, let's stop for a second. In a sense, computability is the question of finite versus infinite. Yes. Complexibility is it is a more, it's a finer distinction. Is that, you think exactly, exactly. Now, you know, um, um, when people started building actual computers, you know, in the 50s and 60s, right? You know, they, you know, like some of the first things they wanted to do is, okay, you know, there are all these problems that we know to be computable. So let's try to solve them, right?

You know, some of them were like, like, for example, there was a famous theorem of Tarski that said that for, you know, like, well, deciding whether equations have whole number solutions as uncomputable. You know, if I just want to decide the truth or falsehood of sentences involving real numbers, then that problem has an algorithm. Okay, that is computable, right? And so they tried to do that with the mainframe computers of the 50s and 60s. Now, but then they quickly realized the problem, you know, which is that while Tarski's

algorithm, you know, had given an algorithm, the amount of time needed by the algorithm could only be expressed using like a stack of exponentials. It was like two to the two to the right. And so, you know, this, this is not just a practical issue of like, does your program take 10 seconds or 20 seconds, right? You know, this is, this is a question of can you do it like within the lifetime of the universe, right? And so, so, so by the 60s, it had become clear to people that we needed to make a finer

distinction, you know, among the problems that are computable, you know, which is, you know, an enormous number of problems that we care about. But, you know, we actually need to know further which problem, which of those problems have an algorithm with a reasonable scaling. Okay. And it took, it took a while for people to sort of, you know, converge on sort of what, what is even the right question to ask there, right? But, you know, by the, I would say by the late 60s, it was clear to people that a really crucial distinction was between the problems that require exponential scaling and the problems that allow for polynomial scaling. So polynomial scaling would mean I use a number of steps that grows only like the size of my input raised to some fixed power, such as two or three,

for example. And now, you know, if I have an algorithm that takes end to the 10,000 time, you know, and being the size of the input. Okay, then technically that would also be polynomial, you know, even though no one would ever pretend that that was fast in practice, right? But then on the other side of this chasm are the problems that inherently require an amount of time that grows exponentially with that, right?

Such as two to the end, for example, or it could be even worse, you know, N factorial, right? Now, you know, it's complicated. You know, there are, you know, you can be intermediate, you know, between these two. Okay. Like, you know, end to the log end power would be an example, right? You can, you know, you can have mild exponentials and you can have, you know, as I said, you can have brutal polynomials.

Okay. But empirically, what people found was that the problems that we care about, you know, in practice, tend to organize themselves into, you know, first the polynomial one. that usually have a pretty mild scaling, such as quadratic or cubic at worst, you know, and even if the first algorithm that's discovered is like end to the 10, usually if you put enough effort into it, you know, you can make that end to the five, and then you can make it end to the four, right? You know, you can, you can, you can, you can whittle down the exponent from one year to the next. And so people,

people got really, really good at that game. Okay. And then on the other side, there are the problems with exponential scaling, okay, that have a sort of inherent interactability to them, right? And that's, you know, not just a contingent statement about, you know, this year's model of computers, right? That seems like something inherent, right? And now, you know, it could have been a priori that there would just be, you know, thousands of different hard problems, you know, that would have exponential scaling for thousands of different reasons. Okay. But now we get to, you know, the key discovery in the 1970s, which is that, you know, of the problems that have exponential scaling, almost always, it's, you know, just for, for one of the same few reasons, right? And this was this key discovery, which was called NP completeness. Okay, yeah. So now, good. I wanted to get, you know, I want to, let's talk about P and NP. Sure. Which, by the way, I actually, yeah, anyway, let's talk about P and NP, which I think I only fully understood reading you as well. All right, sure. So P stands for polynomial time. And it's just the class of all of the problems that have an algorithm, you know, on a conventional computer that solves, you know, any instance of that problem.

you know, with polynomial scaling. Okay, so you can think of it, you know, loosely as the class of all of the efficiently solvable problems. Yeah. Okay. So examples of problems in P would be, you know, I give you a map and I ask you, you know, is every city reachable from by every other city, right? I give you a graph, you know, are all the vertices connected to each other, okay?

you know, less obvious examples. I give you an integer, you know, say written in binary. I ask you, is it prime or composite? Okay. It turns out that if you just want to know whether a number is prime, that can be done way, way more efficiently on a classical computer than we know how to actually find the factors if it's composite. Right.

So that's a non-obvious fact. Okay. But primality testing was, yeah, actually was discussed. covered in 2002 to be in P. Linear program. So I give you a system of linear constraints. And I ask, is there a point that satisfies all of those constraints? Or even simpler than that, solving, you know, I give you a set of linear equations.

I ask, does it, you know, is there a solution? Like, is this matrix invertible or not? I give you a list of boys and girls and which ones are, you? willing to date which other ones. And I ask you, can they all be paired off in a way where everyone is happy? That's called the perfect matching problem. And these kind of problems, I mean, I,

you know, I couldn't resist this quote that you gave from during what you just said, you know, it's not obvious that, I mean, it's certainly not obvious someone that knowing whether something's prime or not is gonna be a lot easier than finding his factors. But yeah, the view that machines cannot give rise to surprises is due, I believe, to a fallacy

to which philosophers and mathematicians are particularly subject. This is the assumption that as soon as a fact is presented to a mind, all consequences of that fact springs into the mind simultaneously with it. It's a very useful assumption under many circumstances, but one too easily forgets that it is false. And if you ever tried, it is false. Yeah, it's a great quote.

Toring often had excellent ways of putting things. But so, okay, so that was P. You know, that's the class of all the efficiently, solvable problems. And, you know, when, you know, undergraduates, you know, major in computer science, you know, in their algorithms class, you know, they'll learn, you know, many, many examples of problems that are in P and why they're in P, right? Okay. But then there's NP, which it doesn't stand for not polydom. Yeah, which is, well, for a long time, I always saw it with that's what it stood for. Yeah, yeah, right. Common, you know, a issue. I mean, I mean, look, we're just not as good at naming things,

as physicists are, right? You've got names like core, you know, black hole, right? We're stuck with, you know, P and NP. But NP stands for nondeterministic polynomial time. And you can think of it as the class of all of the problems where there is a polynomial time algorithm that is an efficient algorithm for checking an answer to see whether it's correct or not, right? Not necessarily for finding the answer, but just for checking. We're checking. Okay. So, so, you know, so, so factoring is an example of an NP problem, right?

Like it might, you know, if I give you a huge composite number, it might be incredibly hard to find its prime factors. But once you found them, you know, if someone doesn't believe you, then, you know, it's easy to convince them. You just show them the factors. And, you know, with their computer, they can easily multiply them together and check that they work. can even check that they're prun, right? So, so, so we would say that factoring is an NB problem. Okay, but, you know, there are many other examples like, you know, so the famous traveling salesman problem, because, you know, I tell you the distance between each pair of cities. And now I ask, is there a route that visits every city with, you know, at most 5,000 miles total or something

like that, right? And, you know, this might require some, you know, enormous combinatorial search to find that path. But if you do, if you succeed at finding it, then it's very easy to check. You just add up the distances. Yeah. Right. And, you know, a huge number of games and puzzles have the same character. So, you know, Sudoku,

right? You know, okay, you know, many people have experience that, you know, it can take a while to solve, but it's easy to check. You know, jigsaw puzzles, okay? You know, have the, have have the same character. You know, and in fact, you know, now we get a little bit meta, but math itself has the same character, right?

If I ask you, you know, give me a proof of this theorem, right? Like since, you know, the work of Bertrand Russell and his friends a century ago, you know, we have known completely formal languages for expressing mathematics. Yeah, right? Or even a computer can check the validity of a proof, right? but that still doesn't mean that the computer has a way to find the proof in any reasonable amount of time, right? So if I ask, like, is there, you know, I give you a theorem like, you know, or a conjecture, you know, like the remand hypothesis or something. And I ask, is there a proof of it in this formal language that is at most, you know, a billion symbols long, right?

That's another example of an NP problem. And so now we can already pose the central unsolved problem. The biggest problem. A theoretical computer science for the last half century, which is does P equal NP? Okay. So is there a polynomial time algorithm to solve all of the NP problems that is all the problems where you can efficiently check a solution? So we know one is a subset of the other.

That's right. P is contained in NPin. So, you know, if you can solve a problem yourself, then clearly you can also verify the solution, right? Like, you know, but the question is if you can verify a solution efficiently, then does that also mean that you can find a solution efficiently? Right. And, you know, I like to joke that, like, if we had been physicists rather than mathematicians, we would have just said, you know, of course not. Next question. You know, we would have declared that P is not equal to NP as a law of nature, you know, and maybe given ourselves Nobel Prizes for its discovery. And if later it turned out that P equals NP, well, then that could just be more Nobel Prizes.

Okay, okay. I wouldn't quite so far, but in any case. We might, we might do. And by the way, and this will come to the next half hour, we might do as if this is, to say, I have other problems I can solve. I'm not going to worry about that one. Yeah, no, no, of course. You know, you can chew, you know,

and I mean, any, I mean, especially given the experience of the last half century, anyone could be forgiven for not choosing to spend their time on the P versus NP problem. But it's got profound implications. Yes. And I want to, in sort of, I want to lead them in directions. Really, the directions of what, A, what,

computers do? Yes. And B, can they think? Ultimately, in my mind. Oh, yeah, sure. Absolutely. No, but just to tie things up, I wanted to say, you know, the key discovery that people made in the early 70s was that, you know, a huge number of problems that, that, you know, you might care about, including the traveling salesman problem, including actually Siddoku puzzles, it turns out, including, you know, finding a bunch of people, you know, in a social network, we're all friends with each other, you know, minimizing the energy of like, you know, of a folded protein. So, you know, practical problems also, right? You know, a huge number of these problems, actually, you can prove that they are solvable in polynomial time if and only if p equals n p okay so each of these problems in itself individually encodes the entire difficulty of the p versus n p problem okay that that was the non-obvious part okay and problems that have this property that they're sort of you know np problems that are at least as hard as any other problem in

n p these are what are called the np complete problems okay and and so what was the discoverers that like if you come up with some problem that involves like satisfying a whole bunch of different constraints, you know, that might conflict with each other and, you know, you have some combinatorial explosion of, you know, of ways to set your variables. Like such problems will generally, generally will be and be complete unless they have a very good reason not to be. Okay. Now a factoring is an exception. Okay. Factoring is an NP problem that sees, to not be NP complete. So there is very special. There are some non-incolute complete.

There are outliers. Factoring seems to be like in a no man's land between P and NP complete. But okay, now you gave some examples. So this sounds a little abstract for most people, but let's bring it down to Earth in a way. Sure. In another way, which is the reasons to think that P doesn't equal NP are many as a physicist, let's say. And one of the reasons is the analogy that I like, so this is the idea of NPR problems that you can show, you can, you can verify the solution. You can verify it's good in a finite time or a polynomial time, even if you can't solve it. But if that's equivalent to the problems that could be solved in a polynomial time, then the analogy use, well, there are a bunch of it, but one is, would be, so if anyone is able to appreciate a great symphony, they could also compose one themselves. So yeah. No. Knowing it's great is the NP part, I can verify that it's great.

But if it's equal to P, then I must be able to do it. And for those of those who haven't been able to close a great sympathy. Right. I mean, I mean, most people's intuition would be like, you know, as soon as they understand the question, they'd be like, of course these are different, right? Of course you might need X. Now, now the tricky part is that there are problems. Like, you know, to go back to that example from before, like I give you a bunch of boys

and girls. I tell you who's willing to date whom. right you have to pair them off so that everyone is with a partner that they like that problem also seems on its face like it would require an exponential search right like maybe that one is npete complete but then it's not there's a clever algorithm for it that lets you avoid the you know considering exponentially many solutions well in fact it yeah it's really important i want to go back i want to say that a lot of times you things just look so hard you give up but smart people and one of them one of them which i think really important was the misunderstanding you mentioned it in one of your articles which is evolution

that that one of the mistakes that people make who look for intelligent design and i forget which of the great scientists made that mistake himself i don't know if it's touring but uh no no no so so so so so so so so so so so so so so so so so so so so so so got it's not that he didn't understand natural selection he just thought he dreamed of proving a theorem that would say that it was vanishingly unlikely to have, you know, produced, you know, intelligent life in a mere four billion years. Yeah, I mean, and that's, by the way, you know, that's still the obstacle. He was kind of a mystic. Now, I would, I would not put very good odds on being able to prove that theorem because, well, yeah, exactly. I mean, I think we're a counterfeit. But by the way, it's really important because there's

every day when I debate these people say, look how complex, even on DNA molecules, you can't do that. And so you can't make the assumption just because something's complicated that it's impossibly complicated. That's right. No, I mean, Dawkins caused us the argument from personal incredulity, right? Yeah, yeah. Just because you can't see an efficient way for something to be found doesn't mean that there isn't one. And that was a lesson that computer scientists, you know, had to have seared into their consciousness from, you know, very early on, right? And that's why the P versus NP problem is so difficult, right?

because how do you rule out that there's some clever approach that just everyone has missed for half a century? Well, okay, so I want to focus because, again, there's so much we could talk about, but there's lack of time. I want to focus on this idea of thinking. I want to focus on a touring test. In principle, a touring test is kind of an NP kind of problem, right? Can I recognize that I might not be able to do it, but can I recognize that a computer is a computer or a thinking human being? And well, okay, I mean, I would say, you know, what touring was trying to do in this famous paper in 1950 was to give an operational criterion, right, by which, you know, we could decide whether to call something intelligent or not, right? Now, now technically, you know, he, you know, he wasn't saying that it's an NP problem. Because, you know, after all, he wasn't reducing it to a computational problem. He still needed a human judge. Right. Yeah, yeah. And, you know, and, you know, and, you know, touring might have to believe. you know, I mean, touring, you know, like many people today, might well have believed that there is nothing that the human brain is doing, you know, that can't be simulated by a computer, right? But in formulating the touring test, he still had the judge be a human being.

Yeah, no. And I'm doing this with malice of forethought because I want to lead to AI safety, which I think, which is related to this. I mean, you know, AI sentience. So let me ask you a question. if P does not equal NP, does that imply that there's no effective touring tests that's possible? There's no way to tell ultimately. People for a long time, if you're interested in seeing if chat GPT is intelligent, if P is not equal NP, there's no effective way that you can do it ultimately. So you don't know if it's intelligent.

I don't think it does, to be honest. I mean, I think that, you know, the question, you know, the technical question of P versus NP, and the informal question of how do we recognize intelligence, right? They do interact with each other in some ways, right? But they're not the same question. They cut across each other in a kind of... Well, you know, the reason I'm asking is one of the things that upsets me

about a lot of this AI safety stuff to begin with, but all and singularity stuff is how little time is spent and actually talking about what human intelligence is or sentience. And since we don't really understand that at all, we don't understand the consciousness i wrote a book in the whole last chapter is about how little we understand consciousness so if we don't understand human consciousness how can we well be so concerned about anyway i mean i mean i mean i mean i would say all of that is completely true now what you know the people worried about a i existential risk you know what they would say is that our our lack of

understanding is not a reason uh to to be calm right yeah okay yeah and they and they would say that you know, the, the unbelievable success, you know, and just, you know, scaled up machine learning, you know, that we've witnessed over the past few years, you know, demonstrates that we don't have to deeply understand some, you know, facet of intelligence in order to be able to replicate it. And or be able to replicate, but then the question is, is it, you replicating it and being the same are, of course, the million dollars question. Of course, but, you know, if you are, you know, so let's say, you know, there's a philosophical question of like, you know, is the AI truly conscious? Is there anything that it's like to be the

AI? How could we ever know that? But then there's also the practical question. What affects is this AI going to have one civilization? And we'll get that. And what the AI risk people would say is that we don't have to answer the first question. Yeah, of course. But I want to do with the first question before we get to the second question in the last half hour, which is. Yeah, yeah, yeah, yeah, right. And no, but you could say that also what touring was trying to do with the touring test was also to pull apart those two questions and somsets. He would say, let's set aside the question of is the machine conscious? And let's just focus on this empirical question of can you build a machine that acts in a way that we cannot tell apart from the human. Yeah, and I guess that's what my question, that's why I asked is that P, not equal to NP.

Because I can imagine that, you know, there's no polynomial way. There's no finite time way in which you could do an algorithm by which you could distinguish whether the computer has solved what it means by being intelligent. That's what I mean by it. I mean, I can imagine P not equal to NP would be a statement that it's plausible. It's possible that there is just simply no way to ultimately do the touring test. That's why I ask you the question. Well, okay. So, I mean, now that I'm spending a couple of years, you know, moonlighting and AI, you know, working with Open AI, you know, I am forced to get comfortable with the fact that in AI, you usually don't have formal definitions of the concepts that you want.

And, you know, and you have to deal with them anyway, you know, because they are changing the world. Right. And so, you know, you could say, you know, even, you know, without, you know, having a mathematical definition of when is a machine intelligent and when is it not, right? You, you know, you have to answer questions like, you know, how intelligent do we expect GPT5 to be, you know, and we can try to operationalize that in various ways. Like, will it be able to get a gold medal on the International Math Olympiad, right? And, you know, and, you know, and, and, and, and, and, and, And none of those questions will capture all the facets of what we care about.

But at least at least they give us some empirical handle on it. Now, now, now, P versus NP is a technical question, right? That, you know, it's a profound one. But it's one that, you know, I think, you know, it's sort of, you know, it's neither necessary nor sufficient for, you know, for having human level AI, right? Yeah, okay. I could say even in a world where P is not equal to NP, okay, you know, that would mean that no computer

program could, you know, sort of magically guess the answers to, you know, any well-posed mathematical question, you know, whose answer can be efficiently checked. But, you know, that, that, that wouldn't say anything about the impossibility of AI because after all, we can't do that either. Yeah, yeah, exactly. No, and my point is ultimately, it may just be a, question of semantics to distinguish yeah yeah let me let me ask you one last question before we hit the heart of this all right fine um which is well this isn't maybe it's irrelevant if it's irrelevant we'll just do it in a minute but it intrigue me sure so you might say there limits to so human intelligence as a classical computer or whatever you want to call it can do certain things but it's

limited and can't do things that um you know certain solve certain questions in polynomial time but here's my question if humans can build if humans can build quantum computers and quantum computers can solve in polynomial times then i haven't essentially human intelligence solve the problem at polynomial time or is that just a yes well okay i mean you you know you could say that you know we are using maybe the way a computer scientist would say is that we are then using the physical world as an oracle to to do to do something that are that are unaided brains could not i mean that that all the time. Of course, we already use classical computers in that way. Where we use telescopes. We use every, every bit of sight. Right, but, but, but, you know, I mean, I mean, I mean, I mean, I mean, quantum computing, of course, also feeds into the discussion of P and NPig. So, you know, there is what, what my former advisor, uh, Umash Vazerani, what he did 30 years ago is to define the, you know, the quantum generalization of the class P. Okay. So the class of all the problems that a quantum computer could solve in polynomial, you know,

And that class we call BQP, bounded error quantum polynomial time, right? And now you have a new set of questions to ask. One of them is, is P equal to BQP? Right. And Schor's algorithm, then, you know, which came a year later, gave some evidence that the answer is no. It said if, you know, P could only be equal to BQP if factoring numbers is in P. Right? Because, you know, factoring, you know, as Schor says, is a BQP problem.

Okay, but then we can also ask the question, what is the relationship between NP and BQP, right? And we still don't know. We don't know that either of them is contained in the other, okay? So they could just be incomparable, okay? But, you know, when you ask, is NP in BQP, that's just another way of asking, could quantum computers solve NP complete problems in polynomial? time. And, you know, so we, of course, we don't know, because, you know, we don't even know if classical computers can do it. So how could we know, you know, prove that quantum computers can't?

But, you know, it's generally believed today that the answer is no, okay, that for NP complete problems, quantum computers, they can get that square root speed up from Grover's algorithm, but probably not more than that, right? And that does not reduce exponential to polynomial. Okay. For those who have born with us for this long, Let's let where we, I mean, I hope, now I think they're fascinating questions, but, but the question that now is in the minds of everybody. All right. Terminator, the few, our future. And you had decided, and I was going to spend more time into, and you've written about how you got seduced into going into going in this.

You've taken at least one year off and working for open. Oh, yeah. It's now a second year also. Oh, you did. Okay. When I last read this, okay. So they seduced. It will be two years.

And after that, I'll have to decide how to spend the rest of my life to go back to quantum. So you've been drawn onto the dark side. I don't know if it's the – I mean, look, I'm working on the safety team. Yeah, I know. It's the light side. I'm talking. And anyway, this question of that – you know, I signed a petition about ChatGBT, B. Because – and by the way, I should tell you where I'm coming from.

I'm nowhere – I'm kind of like you. I'm not even a reformed alignment person. I'm kind of an agnostic alignment person. In the sense that I'm not as worried as many people are. I'm more interested in what AI can do than being worried about it destroying humanity. But there's no doubt that there are these questions. And so you're right that one needs to look. And the reason I signed that chat deep Titi thing was not, because I was worried about it.

I was worried it was being trained to be too rogue. Was it the six month? Was it the call for the six month? Yeah, yeah, yeah. I agree because at the time, I even wrote an article about how woke it was and I was a little upset about that. It wasn't being. No, no, no, the main people advocating for this. They are there, you know, I can, I can assure you that the woke people hate them and vice versa.

Yeah, yeah, yeah, yeah. Anyway, yeah, no, exactly. But you also point out, well, actually, kind of. of interestingly you say there's two aspects to AI safety there's the there's the AI ethics groups and there's the AI alignment groups and you point out that they hate each other yes that's right and it does and you did and you use the example that I use in many other cases which is the people's front for janeia people's front for yeah yeah exactly life of Brian exactly why don't want to want to want to in the little in the 20 minutes we have left or

so. Yes. Why don't you describe briefly A alignment versus ethics? And then I want to talk about alignment and chat GPT a little bit. And then I do want to talk about the two things you've been working on, which I find it fascinating, which is sort of watermarking and backdoor ways to control things. All right. Sure. So, you know, I would say that that AI ethics is the field where people are mostly worried about, you know, current or very near-term AI is being used to generate misinformation, to entrench the power of some groups over other groups, to, you know, output, you know, biased answers to be used for political propaganda campaigns, things like that. And then AI alignment is the field where people, people are worried about, you know, how do you get a really powerful AI to be aligned with our values?

So, you know, if you imagine that AI, you know, at some point just becomes able to do pretty much everything that we can do, you know, better than we do it, right? And, you know, you imagine that at some point it is, it is basically to us as we are to orangutans, right? And then, well, you know, how well do we treat orangutans, right? Well, they, you know, they mostly just survive in a few zoos and jungles at our pleasure, right? Yeah. So, so, you know, how do you get a superintelligence, you know, to, you know, prioritize human welfare or to, you know, to value humanity at all? Okay. And so, so the ethics people are mostly concerned about some people using AI as a tool to, you know, get power.

over other people. Or it becoming racist, whereas the alignment people are mostly concerned about like all of humanity is, you know, is in this together against the future AI. And they're both real worries. Let me minimize one. That's right. That's right.

I don't regard either as absurd things to worry about at all. And you know, I sort of wish that we were able to, you know, have a scientific field of AI safety that can address the full range of things that you might be worried about it's not it but the point is it's not really a fully scientific question which is interesting which is the reason you stayed away from it and um well and i mean i i i i usually

you know like was able to do the best with questions that i could formulate mathematically right well i mean that's the way it is physics you know yeah you know you got it my you know my my PhD supervisor once told me, don't think work. But, but, but yeah, in physics, graduate students and students want to solve these big problems, but, but first you have to solve the small problems. And the best thing to do is solve a problem that's actually solvable, or at least to which you can formulate and you know what the problem is,

which is itself a major. And so your point was, which I think is interesting is that, is that for a long time these things were quite theoretical. And I have to say, I attended a bunch of the early meetings. Were you at a CILOMAR? I can't, maybe we've met it to me. So anyway, I went to a CILOMAR, and I heard these meetings about, you know,

AI and all the worries that the philosophers had. And it was a lot of talk. And I just sort of felt it was just like, but yeah, well, chat, JPT and the new things you've pointed out to you that I'm sorry, I'm leading you through it, but I want to get to it. No, it's fine. It's fine. It's, um, is, you know, hey, here's a, here's a empirical example.

And now we can ask empirical questions and maybe make empirical progress. And maybe make empirical progress. instead of just talking. Yeah. Is that fair? Yeah, that is very fair. I mean, no, as soon as I saw, you know, GPT3, which was, you know, during the pandemic, right, it was, you know, like the, I think at the time there were people saying,

oh, this is just another chat fuck. This is like Eliza from the 1960s. Yeah. But, you know, I knew, you know, I tried Eliza and I tried this. And it's clear that this is a phase change in, you know, the capabilities that the, the, humans have. I think the only, you know, technological thing in my lifetime that produced, you know, a similar feeling in me was, you know, when I first saw the internet, you know, as, you know, or the web as a 12 or 13 year old. Well, exactly. I mean, it is, but it is and it

isn't. I mean, yeah. Well, let's let's let's get around. If we don't get to it, you and I both agree. And as is everyone but one person, the chaty PDD is not thinking. And, and, i mean uh... well wait wait i mean you know that that that that it all depends what you mean by thinking i mean well it's i don't i don't i don't personally regarded as conscious or as sentient yeah okay although although although even even that i don't think it's as obvious as many people make it out to be but you know i don't i don't personally regarded as sentience right but you know thinking well that you know that all depends what do you mean by thinking okay i meant sentient i did yeah okay okay i use the wrong work but let me let me step back a bit because you know

One of the things that I still don't understand about this alignment thing, I remember the very, I remember two well-known philosophers get up on stage and say we have to, you know, like make Asimov's rules. We have to make sure that computers are aligned with human values. And both me and Jeffrey Sachs got up at the same time, the economist Jeffrey Sachs. I don't know if you know him. Yeah. What do you mean by human values? I don't know what human values are.

Of course. So what the hell? If you want to look at human values by seeing what's happening in the world, you won't find any human values. What are we talking about when we talk about alignment? Of course there's the question of whose values, you know, and that's not, that's not lost on any anyone who was seriously thought about this. Well, some people, some people who were pretty serious. Yeah, yeah, but, you know, I mean, I mean, you know, we can, we can just, uh, crunch, you know, we can put this in very practical terms, right? Like, you know, uh, what should, you know, a company like open AI be doing,

know, you know, they don't want to unleash something that's going to, you know, be horrible for the world, right? You know, I guess the point is that the only human value. You can now ask, you know, there are, there are, you know, immediate, you know, already now sort of moral questions. Like some people think, you know, there's a moral obligation to open source, you know, these models, like give anyone access to them, let them thinker with them so that they're not in the control of a few companies. Other people think that that's utterly insane. It's like that it would be like open sourcing thermonuclear weapons, right? Yeah, exactly. And no, like we have to keep these things under very tight control, right?

So, you know, they're like, like, you know, you may not be able to scientifically answer a moral question, and yet it still doesn't relieve you from having to answer. Yeah, exactly. You said life isn't scientific. If it was, we'd all be scientists and the world would be an easier place to deal with. Yeah. But we could say. You hope that you do hope that science can inform these questions. Yeah, yeah, you do hope so.

That's where that's where AI safety comes in. Yeah, yeah. You do hope that. And I get to become more pessimistic over time. But one could say, though, that, you know, the only that a, clearly a universal human value is to preserve humanity so it doesn't end. But if you say that, then it's clear we do things that, you know, we built nuclear weapons. Yeah.

So it's not clearly a universal. universal human value. But yeah, but so I mean one one one one one idea that the you know, the you know, Eliezer Yadkowski who was sort of like the you know the the profit of this area, you know, that he likes to talk about is called coherent extrapolated volition, which basically means, you know, what you would really like once you have the super intelligent AI is not to tell it, you know, just copy the values that you see humans, enacting in real life.

That would be terrible. What you want to tell the AI is sort of like simulate the humans, you know, having a moral philosophy seminar for 10,000 years, you know, where they would refine their intuitions and get better and better and go through, you know, 10,000 years of the same process that led us, you know, to abolish slavery and to, you know, give women the right to vote. and all these things that we, you know, that we all regard as moral progress and, and simulate that process until it reaches some termination point. And then whatever values, you know, your simulation ends up with, then those are the values you should enact.

You know, that's, you know, that, that, that, that, that, I mean, that, I mean, that, even that idea can be criticized as well. But, but, but, you know, you could say they are, you could argue that that moral progress has led to a civilization that ultimately is bad for the planet. And you might say that the best, the ultimate end of that is to say, well, planet's going to be better off if there aren't humans on it. You might argue that that's illogical. And I mean, if you're thinking about, say, and talk about effective altruism, I know so you lecture to me. I just did a podcast with Peter Singer and might say that if you really think that the, the, the, the, the, the, the, the, well, being of all animals is equivalent. And you might say, well, then, you know, the human well being conflicts with that. Yeah, I mean, you could also imagine an AI that would reason that, you know, if humans survive and they colonize the galaxy, then they are more likely than not to become a scourge of the galaxy that will, you know, wipe out all the other civilizations. And therefore, you know, the whole, you know, universe will be happier if it, if it, if it, if it kills the humans, right? And so, you know, now, you know, I don't, you know, um, you know, um, you know, um, you know, you know, um, you know, you know,

I think that there is progress that can be made in making it, you know, AI's safer and the more immediate, you know. Yeah. And without needing to answer these cosmic. Those big questions. And in fact, I'm always amazed that people, just as I'm amazed when people see something, they don't understand the sky, they decide it's aliens. And I'm going to have to do a debate on that later this month. Yeah. But also, automatically, whenever they think of an quote unquote intelligent AI, they see Terminator.

They always see a dystopic future. They never see a future in which where human life is in many ways better or could be better. I mean, look, I mean, I certainly think about the good outcomes, right? Yeah, I know exactly. It's even possible, I mean, you know, if we think about previous technologies, right, like, like, you know, like some people say, well, well, you know, the internet has, you know, has ushered us into a dystopian reality, right? But I don't know, what I want to, what I want the internet to have never been invented, you know, I'm not at all store of that. No. Some people said, you know, like, like after 2016, they said, well, look, the original promise of the internet was that it was going to, you know, democratize, you know, speech and give, you know, everyone, you know, the ability to say with, you know, what they wanted and to influence, you know, the national conversation.

And it delivered on that promise. And the only problem is that what a lot of people want is absolutely horrifying. Yeah, yeah, absolutely. I mean, it's like saying, I mean, well, you know, this, there's a lot of information and misinformation, but yeah, but what, but you can't deny that, you know, and when I'm not, I was just on the tube in London and I remember me of being in Japan 30 years ago, wherever one was staring at games. That's never going to be asked, but of course, no one can be in the tube without

the phone. You might say that's bad, but on the other hand, look at what they can do and look, look at what you can do. So, so, you know, it's, it's, it's two sides of the. same coin. Yeah, but I think even even the people who are who are the most dumerous, like they completely agree that, you know, that, that, you know, they are generally pro technology, right? And they think that that AI will, will make life amazing before it kills us. Before it kills us. Now, but let me just, you know, if we don't get it right.

Let's let's, there's some reasons for hope. That tends to be their position. There are reasons for hope and I want to try and end an upbeat. No. I agree. I agree. One of them you point out, which I think is really important, is that the big concern is that there's a phase transition. And somehow things are moving along, then suddenly, you know, it's like in Terminator, suddenly, you know, one AI learns how to lie and, you know, and you point out, and this is very important. I mean, in some sense, there are current, current language models can already lie.

Yeah, they can lie. Of course they can. And they lie in silly ways, as you point out, as well as good ways. And you can often trip them up on as result. But no, but you like, you can, You can give them a goal and they can figure out to lie in pursuit of that. Yeah, yeah, exactly. But here's the point, but do it in a way where anyway.

So here's the question is, so now, but you point out, and this is important, that if you look at empirically, what's happening is as they learn, as you say, it's like your students. You get, it's not there's a face range. You see them make the mistakes as they're learning. It's not as if they're going to, they surprise you when suddenly having learned, uh, integral calculation, calculus when before the day before they were learning how to add. And, and, and, yeah, yeah, no, they do. They, they are sort of progressing through the curriculum, like a couple years ago,

they were in, you know, elementary school, maybe, in terms of their ability to do math problems. Now they're in high school or undergrad. They're still not in grad school, right? But, you know, but, like, you could say, that progress has been continuous, but it's also been extremely fast, right? And so, so, you know, well, like one, one, one. confusing thing about this discussion is that every phase transition right is actually continuous if you

zoom into it closely yeah yeah close right and so you know something could be technically continuous and yet on the scale of a human lifetime it could feel like a phase change i think physicists would say that that might be the situation that we're in right now that's not quite true though first order phase transitions really are but anyway but yeah anyway but but okay so that's a cause for hope but there's a statement you make I wish I could spend a half an hour on this instead of timid we've talked about one of the reasons for optimism. Another reason for pessimism, which is interesting quote from you, I think that for better or worse, we're going to see real harm from AI. We're going to see them used, unfortunately, to help plan terrorist attacks to do really nasty things. But those things

at least will be far short of the destruction of civilization. So there will be some bad, there will be some bad. And that's one of the reasons you've gotten involved, that and the fact you can empirically do things. Why do you talk briefly in five minutes about watermarking at the very least. Sure. Okay. Sure. So yeah, I mean, I mean, you know, in AI safety, like, you're constantly asked to prognosticate, like, what, you know, is going to happen, you know, 20, 30 years from now. And I can't do that. No one can. If I could do that, I wouldn't be a professor. I'd be an investor. Yeah, yeah. Yeah. Even investors do it. But, you know, I was, I was happy that, you know, in summer of 2022, that at least I was able to see three months.

ahead. Okay. So before chat GPT came out, like, I had this moment of terror where I was like, oh my God, like every student is going to be using this to cheat on their homework, aren't they? Or at least they're going to be sorely tempted to, right? And, you know, I get

all of these trolls on my blog, you know, some of whom put incredible energy into their craft. Right. But I'm like, wow, this is going to make, you know, attacking every discussion forum on the internet so trivial to do. right you know the the the the russian government for example could spam every comment section with pro-putin propaganda you know that seems responsive to whatever came before it right and you don't even need

a building full of people to to do this right you just you just just have gpt do it for you and so then you know for all of the you know and and you could also have gpt impersonate someone right if you have enough examples of of someone's writing you could say produce more writing in the same style where this person confesses to a crime, right? Or, you know, you could, you know, try to whip up a campaign to get someone fired, right? So, so, you know, so all of these different misuses all involved concealing the fact that an AI was involved, right? And I just thought, you know, if you could only make the outputs of a large language model detectable as such, right, then that would simultaneously address all these different misuse. uses. So how do we solve, you know, what's now called the provenance problem or the attribution

problem, right, of what came from a language model and what did it? You know, and there were different approaches that you could imagine. I mean, one approach, which actually has been tried over the last year, is to treat it as yet another AI problem. So you just train a discriminator model to say, you know, did this text come from a human or did it come from a language model? model, right? And, and, you know, you can get, you know, maybe 90, 95% accuracy with that sort of thing. But, you know, there's still too high a risk of false positives, right? Where, like, people were having fun, like, where, like, with some of these discriminator models where, like, they would say that passages from the Bible or Shakespeare were probably GPT generated,

right? And, you know, and, okay, but, but if you, you know, uh, um, um, um, um, you know, if your discriminator model is falsely accusing students of using GPT to cheat, right, then that's a huge problem, right? And we've already seen some of that in the last year. Okay. Now, a second approach would be, you know, as long as the models are controlled by just a few entities like OpenAI, Google, Anthropic, then they could just store all of the outputs they generate in some giant database.

and then they could let people make queries against that database. You know, is this a match for anything that you have generated? Now, it's not obvious how to do that in a way that would appropriately reassure people that their privacy is being preserved, right? That's the main drawback there. Okay, so then I got interested in a third approach, which is called statistical water market. Okay, and this is where you slightly change the way that the language, model operates. So you're not going inside the neural net and fiddling with the weights,

okay, but you are, you know, like, so, so, so how does a language model work, you know, to step back, right? It, well, what it's doing, you know, it's this big neural net, you know, called a transformer neural net, but it, uh, it's constantly taking his input a context, which is, let's say, you know, the previous thousand or so words, you know, which could be either, you know, the user's prompt, or it could be the words that it itself has already generated. Yeah. Right. And it feeds those in.

And then what it outputs is a probability distribution over the next word. Okay. Or technically the next token, you know, it could be a punctuation mark, you know, numeral, whatever. What happened in normal operation is just that you sample from that distribution, right? So you, you know, and, and, you know, people may have noticed that, like, you can submit the same prompt to GPT over and over and get a different output each time. And people like that, right?

It's, you know, the model is inherently probabilistic. Okay. But now we could imagine doing other things. Okay. You know, already in GPT as it now exists, there's a parameter called the temperature, right? And if you set the temperature to zero, then what you're telling GPT to do is always pick the token with the highest probability. Right. So in that way, you're making it deterministic.

Yeah. Okay. But now with watermarking, you would do yet another thing, which is you would use this probability distribution, okay, but generate the next token in a pseudo-random way, okay, a way that looks random, that looks, you know, to any ordinary user, like this is just, you know, regular GPT output. But secretly, you know, you're using a pseudo-random function to pick the next token, and And you're doing it in a way that biases some score, like some sum over all the tokens,

you know, over all the pairs or, you know, trigrams or whatever of tokens of some score, which, you know, if you know the key of the pseudo-random function and you have the text in front of you, then you can calculate that score. And you'll see, given enough words, given enough tokens, that score will just be systematically larger in a watermarked output. then it will be in an unwittermark. It's great. And the virtue of that, by the way, is, as you point out, that if you just change a few words, it doesn't change anything because you're looking. That's right.

That's right. Yeah, exactly. So we have an approach that is indistinguished, you know, where it produces output that is, you know, to the end user would just be indistinguishable from normal GPT output. And, you know, it produces this, this watermark where, you know, you can, you can be, you know, like with a few thousand, words, you could be statistically certain, basically, that, yeah, you know, this came from GPT. Even with a few hundred words, you're pretty confident. And it's robust to local modifications. Okay. Now, now what it's, I have to be honest here. Okay, what it's not robust to, you know,

the problem that we don't know how to solve is, for example, you know, a student asks GPT to write their term paper, but in French. Yeah. And then they put it into Google Translate. Right. Or, or even they ask GPD to write their term paper, but, you know, insert a random number of exclamation marks between each word and the next, you know, and then they take them out, right? And, you know, and GPT4, unfortunately, you know, is smart enough that it can usually follow such instructions, right? And, you know, I think that in order to, you know, have something that's robust against all of that, we're going to have to figure out how to watermark at the semantic class. Like not, you know, which would mean going inside of the neural net and doing

something to the weights. Okay. Well, okay. Yeah. And okay. So I look, I just, it's a small insight into something's doing, but what's great about it is it's real. It's not talk. And it, and just so people feel, look there are people like you who are actually thinking about how to do these things, which is important. Now, I want to end with the last question. Okay. Because this is the one I use a lot when I've written about it. I was going to say, you know, the alignment people would say that, you know, watermarking, you know, is a band-aid and like a, I know, they're going to, the world's over. A true super, a true super AI will laugh it off like so much, you know, tissue paper.

Yeah, absolutely. And they might well be right. They might be right. But it's baby steps. But, you know, the hope is that at least we can learn something. You know, at least we can. Yeah, and it's baby steps. You do what you can do. Exactly.

You don't buy anything. Then all you're doing is putting your head in the same. and saying wait for it to be over. Yeah, no, and I should say, you know, I'm not the only one who's trying to do something. I mean, you know, I have lots of colleagues at OpenAI who are trying lots of other things. This is speaking of the AIC. I'm excited that AI alignment is now, you know, at least partly an empirical subject. Yeah, absolutely.

And as well, I think when I hear you talk about it. Yeah. But speaking of the aligned problem and the doom, there's a not, there have been many time, a number of times when people have looked at technologies and said, is the end of the world. And one of the earliest ones which intrigued me when I first learned about this, and I've written, this is what I wrote about in my last book at the end, is when in the the 8th century or 9th century in Greek, BC in Greece, the introduction of the alphabet and writing came along. And everyone, Plato and others argued that it was the end of storytelling. It was

the end of storytelling because people wouldn't remember things anymore and they wouldn't have face-to-face conversations. And so it was the end. And of course, most people, especially those of us who write, would say that writing actually has improved storytelling, at least hasn't heard it. It's changed everything and it changed what means to be human. It really changed what it means to be human. You spent a lot of time. Arguably, yes. And so, so AI is going to change what it means to be human, but that's not such a bad thing. Yeah. And what's your comment on that? You know, like, you know, the the lower bound on, you know, how transfer

AI will be is that it will merely be like writing, like the printing press, you know, like the computer itself, right? It will merely be another, you know, transformative technology that, you know, does destroy, you know, the old world, you know, the world as it was before that technology existed, you know, but then there's a new world and we adapt to it, right? I think, you know, the one thing people are worried about that could be different about AI is, like, with every previous technology, you know, you could point to, okay, but obviously you still need humans for X, right? Like, you know, the printing press, you know, it, you know, it copies all the books, but obviously you still need a human to write the books, right?

Yeah, yeah, yeah. You know, with every previous thing, you could say, you know, but this is what you still need the humans for. And after AI, you know, if you truly have a human level, you know, AGI, and it's not obvious that there's any answer to that question anymore. Yeah, yeah. Okay. So yeah. I mean, the last, the really last question is, are you optimistic or pessimistic? I mean, I am, I, I, I, I often tend to be a pessimistic person. I mean, maybe it's just because, you know, I was, you know, like, like, you know, one of the first things I learned about, you know, as a child was, was, was the Holocaust. And that just sort of set my, you know, yeah my my my my my my my my my my my my my my my mental template for for for what the world is like um but

you know it's never obvious to me which things to be pessimistic about right so many like it may not be you know you know a you know a i that gets us in the end it may be something much more pedestrian but uh you know but like on a on a on a day to day level you know i'm i'm often pretty happy right i mean well you know i i want to i've said this people have heard me say this before i want to give you this because it changed my life when I first met Cormick McCarthy, my friend, the writer. And he was such a upbeat guy. And I'd read his books. And I feel like the road or I'm a control man and the others. And I said, how can you be so upbeat? And he looked at me and he said, well, I'm a pessimist, but that's no reason to be gloomy. I love that motto. And I hope it, look, all I can say

is I'm a little more optimistic about the world because there are people like you in it. And thank you so much. Thank you so much. That means a lot. that to me. Really, and I'm saying it's my heart. So it's been a pleasure. And we can spend a lot more time and I could learn a lot more. And I hope that people have. And thank you for taking the time. And Scott, I hope to see you in real life somewhere. But you take care and keep. Yeah. Yeah, like that. Take care. And thank you for having me on your podcast. Oh, it's been my pleasure. I hope you enjoyed today's conversation. This podcast is produced by the Origins Project Foundation.

a nonprofit organization whose goal is to enrich your perspective of your place in the cosmos by providing access to the people who are driving the future of society in the 21st century and to the ideas that are changing our understanding of ourselves and our world. To learn more, please visit Originsproject Foundation.org.