Scott Aaronson - Quantum Computing, Complexity, and Creativity

Scott Aaronson is a Professor of Computer Science at The University of Texas at Austin, and director of its Quantum Information Center. He's the author of one of the most interesting blogs on the internet: https://www.scottaaronson.com/blog/ and the book “Quantum Computing since Democritus”. https://www.amazon.com/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565 He was also my professor for a class on quantum computing. Watch on YouTube https://youtu.be/Uy5fvwdw8x4. Listen on Apple Podcasts https://podcasts.apple.com/us/podcast/12-scott-aaronson-quantum-computing-complexity-and/id1516093381?i=1000499639469, Spotify https://open.spotify.com/episode/7dGLr9ZJkY08shmB3nJcfR?si=mBFugcdvQIKtJ5z60ViRxw, or any other podcast platform. Episode website here https://www.dwarkeshpatel.com/p/ scott-aaronson. Follow me on Twitter https://twitter.com/dwarkesh_sp to get updates on future episodes and guests. Timestamps (0:00) - Intro (0:33) - Journey through high school and college (12:37) - Early work (19:15) - Why quantum computing took so long (33:30) - Contributions from outside academia (38:18) - Busy beaver function (53:50) - New quantum algorithms (1:03:30) - Clusters (1:06:23) - Complexity and economics (1:13:26) - Creativity (1:24:07) - Advice to young people This is a public episode. If you would like to discuss this with other subscribers or get access to bonus episodes, visit www.dwarkesh.com https://www.dwarkesh.com?utm_medium=podcast&utm_campaign=CTA_1

Speaker names marked ? are inferred from speaking time and the show’s known hosts — they are not voice-verified.

• 0:00Speaker 00

  You know, it might take, you know, years or decades to become, you know, an expert like in a whole field, uh, you know, and you might be very far from that. But it really doesn't take that long to become the world expert on one particular tiny little problem, right? And, um, you know, so, so try to, you know, become the world expert on, on something, you know, you know, even something very, very narrow.

• 0:28Dwarkesh Patel?

  So Professor Ernstson, can you tell us a bit about your early journey? You were a young prodigy. You graduated high school at the age of 15, got your PhD at 22. Can you tell us about that?

• 0:42Speaker 00

  Yeah, well, I, I didn't really graduate high school when I was 15. I got a GED from, from, from New York State. But, uh, I, um, I was not happy, uh, in, in high school for, for several reasons. I mean, uh, socially, academically, and I, I wanted to get out. And, uh, I mean, I, I had a, I was in a weird situation because my, um, I, I went to, um, uh, public school, uh, in, in the U.S. for, for, for, for junior high and then, and in Pennsylvania, actually.

• 1:24Speaker 00

  And then my parents, uh, moved to Hong, I, I lived in Hong Kong for one year because, uh, my, my, my dad was working there. And, uh, because of the, uh, miss, I, I went to an American international school there, but because of a mismatch between the way, uh, they said they did things in the U.S. and in Hong Kong, uh, you know, I was not able to do math, uh, that was, that was, uh, appropriate, I guess. I, I, you know, I had always been sort of ahead in math. And, uh, so the only way to deal with that was for me to skip, uh, a grade and skip and, and, and go to the high school. And once, um, well, well, once, once I had done that, that was, that was sort of a, uh,

• 2:09Speaker 00

  you know, something, something flipped for me, right? That, you know, I, I could actually do this. I could, uh, get out of this environment, you know, where, where, where, where I really wanted to be was college, right? I wanted to be in a, um, In a, in a, in a place where, where, you know, uh, you know, and, and, and, and, and of course, you know, I, I somewhat, uh, you know, had, had, had an idealistic view of what college was, but you know, but of a place where, where ideas would matter more than popularity and, uh, where, um, you know, you would be able to choose, uh, what to study and, and advance at your own pace and, you know, all of these, these wonderful things.

• 2:52Speaker 00

  And, and, you know, so then I went, I, I returned from Hong Kong to the U S and was in a, a public high school for, for a year and, um, you know, as I said, I didn't like it and, uh, you know, and then I, I ran out of math to take, right? I, I took the, uh, A P, uh, calculus and, and then, um, the, um, uh, you know, my, my, my parents basically suggested to the school, uh, well, why doesn't he just, uh, do, do online learning, right? And do like, uh, differential equations or whatever with the, the, you know, the, the Stanford has the E P G Y program, right?

• 3:34Speaker 00

  Where, uh, you can do these things and, uh, and, you know, my parents said they would pay for it. Uh, the school said, no, uh, that, that's, you know, uh, um, and, uh, so I, I sort of seized on that as my excuse. I, um, uh, um, uh, I, I, I think I had just seen a brochure for a place called the Clarkson School in upstate New York, uh, which is a part of Clarkson University, but you can, uh, live there for a year and take college courses. You know, and, but it's, it's, uh, it's for high school students, right? Uh, so, uh, um,

• 4:13Speaker 00

  I said, you know, I, you know, you know, even knowing very little about this, I think, you know, I want, I want to give this a try and, uh, My, my, uh, parents, you know, allowed me to do that. You know, we had the car all, you know, packed up to drive there. And while, you know, when we were, uh, about to leave, then finally, you know, there, there was one, you know, actually math teacher at my old high school who was very, very good and who was, you know, trying to advocate for me. And he was like, okay, I just, guess what? You know, I, I just got it so that, so that Scott can take the, uh, the EPGY program. And we said, too late, sorry.

• 4:52Speaker 00

  And, um, so I, I, I went to, to Clarkson and I, you know, and I, I generally had a very good experience there. Uh, I mean, um, uh, you know, I mean, I mean, I mean, I mean socially, there were a lot of the same problems as at, as at high school. But, you know, at least, you know, I was, uh, uh, you know, I was able to take courses that were a lot more interesting. I was able to sort of meet professors, get started doing research. And, uh, and you, you apply from, um, uh, you know, the, the idea is that after a year at this Clarkson program, then you apply to colleges as a freshman, but, you know, but with a year of college credit.

• 5:35Speaker 00

  So I, uh, I did that. Um, you know, I was, I was very, you know, just very disappointed in the time, at the time at, at how things turned out. Because, you know, I got rejected from almost every college that I applied to. You know, I had a very weird background. But, uh, I was lucky that, that, uh, Cornell and Carnegie Mellon were, were kind enough to accept me. And, um, so I, I decided to go to Cornell. But then there was one problem that they required a, a high school diploma before you could enroll there, which, which I didn't have. Uh, and so, so we needed, we realized that, that I, I needed a, a GED from, you know, well, well, okay.

• 6:15Speaker 00

  My, my, my old high school, you know, o- oftentimes one's old, one's, one's old high school will just give you a diploma after you've gone to Clarkson. My high school would not do that because they said I was missing phys ed. I would have to, you know, spend that summer doing phys ed. But uh um uh so uh yeah, and then New York State said uh we can't give him a GED because you have to be seventeen to have a GED and he's fifteen. And and I my my mom eventually convinced them to to make an exception and uh give me a GED so that. So I so so so then I went to Cornell. I mean, I've met other people who were homeschooled, who, you know, actually did things that were more radical than than what I did.

• 6:57Speaker 00

  I mean, I I was accelerated by three years, you know, that was all. And then after I was in college, I didn't really accelerate anymore. Because, you know, I felt like I was, you know, in an environment, you know, where I I wanted to be. And uh, you know, from now on, the these are the the main limitations were were internal. They were they were no longer external.

• 7:20Dwarkesh Patel?

  Hmm. What was it intimidating being in classes of people three or four years older than you?

• 7:24Speaker 00

  Uh, the truth is, you know, uh, I would say the majority of them didn't even know that I was younger. If if they knew it was uh uh like in uh, you know, maybe uh uh in in in oddity a little bit, but then they didn't care that much, right? I mean, because, you know, it's it's not like I was a ten year old, right? I was uh, you know, I mean, by the time I started at Cornell, I was sixteen by then. And um um, you know, I uh um uh so, you know, I I feel like um um um acad- academically, it was fine. I mean, you know, the main issue was was social, right? I mean, you know, and my my parents had, you know, had warned me that, okay, you know, if to uh skip grades

• 8:08Speaker 00

  is going to completely screw up my social life. And uh, you know, it's going to make dating, you know, incredibly difficult and and and so on and so on. And I I sort of brushed all of that aside, you know, in my my, you know, I mean, uh um um. Um, you know, of of of course, that all turned out to be true, you know. I got I got my PhD before, basically before I I learned how to drive, really, or or or learned how to have any kind of a social life, you know, to speak of. I mean, or, you know, any any kind of a dating life, really. But, um, you know, I I did things in a weird order, you could say.

• 8:51Speaker 00

  And and and and that did cause, you know, an enormous amount of of stress for me. But but my main argument was that, you know, I was already socially unhappy in in high school. Right? I was I I I was already miserable, you know, without having skipped grades. And so I felt like, you know, as long as I'm going to be miserable socially anyway, as it seemed at the time, you know, I would be, you know, at least I could be learning stuff. At least, uh, at least the academics could be better.

• 9:20Dwarkesh Patel?

  Yeah. And as far as the academics go, um, what were the advantages and disadvantages of specializing so early?

• 9:28Speaker 00

  Well, I mean, I I I don't get to rerun my life multiple times and and and compare.

• 9:36Speaker 00

  But I I I think that, um, um, you know, mainly, I'm I'm I'm grateful that I had the opportunity to, uh, you know, to sort of learn about stuff that that that that that interested me. And and it was not, it was not just, you know, that, you know, I I I wanted to take only math and CS and nothing else. Right? It was not like that. I mean, I, uh, I took, uh, uh, you know, uh, plenty of humanities in in in college. Right? And, uh, but, you know, I I I wanted to sort of have some some freedom to, uh, you know, I I pick what to what to learn about, right? I mean, like, in in in in high school, uh, you know, hu- humanities means, uh,

• 10:20Speaker 00

  you know, the the five paragraph essay, right? It means, uh, uh, you know, you basically have to regurgitate what the teacher wants from you. Right? And, you know, if you try to, you know, do your own thing, write things in your own way, then you will actually fail, right? And, uh, you know, this, I I, uh, learned this from experience, you know, this is not theoretical, right? Uh, and, um,

• 10:47Speaker 00

  You know, so even, even, even the humanities, right, I was a lot happier with in college than I was in high school. So it, so it wasn't just a matter of, of specialization, but, but partly it was. I mean, I think that by the age of sixteen or so, I, I, I knew what, what I was passionate about. It was the fundamentals of, of computing, right, and understanding what computers could or couldn't do. And I was ready to be, to be learning about that and working on it. And, um, you know, I think that there, there is, you know, the, the, the entire concept of, you know, of, of sort of teenagerhood, right?

• 11:27Speaker 00

  That like people are, are, you know, from the age of twelve to eighteen, or now maybe even twenty or so, we're still basically children. Right? I think that that's largely a modern construction, right? If you go back even a few hundred years, you know, by the time someone is a teenager, they're, they're an apprentice, right? They can work, you know, uh, you know, they can be learning while they're also, you know, working. They can be, they can be learning, you know, the, the trade that they choose. And, um, so, so, so I think that that, that's actually natural, right? I don't, I don't feel like I'm that unusual in that respect.

• 12:05Speaker 00

  I think, you know, I mean, you know, may, you know, unusual in some respects, but, but not in, in, in wanting to sort of get started with life. When, you know, I was fifteen or sixteen.

• 12:15Dwarkesh Patel?

  Yeah, I, I had Tyler Cowen on the podcast and he started, um, the, you, he wanted to be a economics professor, basically in his early teens. And he was reading and preparing for that, um, from that time on.

• 12:26Speaker 00

  Economics professor is not what, you know, what often thinks of as like a, a child, you know, or an adolescent realizing that they won't. But that is, uh, that, that, that, uh, for, for, uh, in, in the case of Tyler Cowen, I could easily believe that.

• 12:38Dwarkesh Patel?

  Is, is there some special advantage of learning the fundamentals of the field you know you're going to go into early on? So instead of, except for the fact that you just get more years to accumulate knowledge? Is there the special advantage of learning it in your early years?

• 12:51Speaker 00

  You know, I'm not sure. It's a very interesting question. I mean, you know, one could imagine that, you know, while someone's brain is still developing, right, that it's good to be exposed to certain things at that age. And, you know, I mean, like, we know examples that are like this, right? Like, you know, an obvious one would be learning languages, right? Where, you know, there's a window where, you know, children can just soak up languages, you know, like a sponge. And, you know, after that window, okay, you know, you can learn a language, but it will be a difficult, you know, intellectual puzzle, and you'll never speak it as well as a native five-year-old will speak it, right?

• 13:34Speaker 00

  So, um, so it could be like that, but it could also be that, you know, like, our brains are not really adapted for learning any of this stuff, right? I mean, like, you know, when we get to, you know, theoretical physics, theoretical computer science, and so on, right? You know, all of it is like, you know, learning a language that we don't natively speak, right? And on that model, it would just be a question of getting a head start of, you know, of how much time you have to spend on it. I would love for someone to research that question, because I don't know the answer.

• 14:18Dwarkesh Patel?

  I have heard, well, so, as you know, like, many of the important discoveries in quantum mechanics were made by people who, at the time, were very young, right? And that's an interesting fact. Not only did they learn that stuff early on, but like, they made those contributions early on.

• 14:31Speaker 00

  Yeah, but that's not just quantum mechanics. I mean, that's all over, you know, math and physics, right? There are, I mean, I mean, Newton was, you know, about 22, right, when he, you know, had his miracle year, you know, of inventing calculus, you know, discovering the laws of mechanics.

• 14:52Speaker 00

  Yeah, I mean, no, I mean, I mean, you know, I'm I'm I'm already old by the standards of math and physics, right? You know, the, uh, um, uh, you know, which is, uh, which is weird to think about. But, um, uh, but, you know, there, there are also many examples of, of, you know, great contributions that were made by people in their 40s, their 50s, their 60s, right? So, so, you know, so that, that, that, that's another empirical question that I wonder about, right? Is it that people's brains actually slow down as they, as they get older? Or is it simply that they have less motivation or less free time, right?

• 15:33Speaker 00

  I mean, like, I, in, in my case, you know, ha- having two kids, you know, get clearly given me enormously less time for research, right? And, you know, like in those cases where I'm, you know, traveling, where I'm, you know, away from the kids for a week, you know, maybe like I can work again and it suddenly, you know, it feels a lot like it did when I was in my 20s, right? It, uh, and so, um, you know, you know, and, and, and then, and then there's also the, the issue of motivation, right? That like, uh, when I was, uh, before I was established, you know, like my, my entire conception of myself, you know, my entire, like, uh,

• 16:16Speaker 00

  goals for my life were wrapped up in, you know, succeeding in research, you know, and, uh, you know, doing whatever it took. And now, you know, it's more like, you know, I, I, I have all kinds of other concerns. I have my own students to worry about, you know, my, my postdocs, my, my, my kids, of course, uh, my, my, my blog, you know, the popular things I write. And, you know, research just feels like one more thing that I do, right? That my, my identity is not as much wrapped up in. So, you know, I, I, I, I may have also gotten dumber, right? That, that's certainly possible, right? But, you know, it's hard to disentangle from those other factors.

• 16:58Dwarkesh Patel?

  Yeah, you're the third person, and I promise we'll get to the technical questions eventually, but you're the third person on the podcast I'm about to ask this question because it fascinates me. Miracle years, as you mentioned. It's not just that, you know, people make like very important discoveries at young ages, but they make lots of seemingly uncorrelated important discoveries at young ages. So as you know, like Einstein did Brownian motion, special relativity, but what was the third one? There were three more.

• 17:25Speaker 00

  Well, there was the photoelectric.

• 17:27Dwarkesh Patel?

  Yeah, that's right. And these don't seem superficially at least to be related, and yet it's interesting to happen in the same year. What do you think explains that phenomenon?

• 17:35Speaker 00

  In the case of Einstein, I mean, you know, you're asking me to explain Einstein's miracle year. I mean, that's a tall order. I mean, I mean, one can say certain things, like, you know, one can say that, you know, physics in the early 20th century was ripe for these, you know, for these interrelated revolutions, right, of relativity and quantum mechanics, right? You know, I mean, you know, if it wasn't Einstein, it would have been someone else, you know, not long after with all of those things. General relativity, which, you know, which took Einstein a decade longer, you know,

• 18:19Speaker 00

  that was the one thing where if it hadn't been for Einstein, then, you know, for all we know, it might have been decades before anyone else did that. But, you know, the, you know, the stuff that he did in his, in 1905, I mean, you know, they were all things that physics was kind of ripe for. Maybe it took, you know, one person just looking at things in a sufficiently different way. You know, I'm not, I'm not, I'm not sure really, but. But also, it might be the confluence of all of those things is part of why we think of Einstein as Einstein. You know, there were many other great physicists around the same time,

• 19:04Speaker 00

  who may have done one or two things of that caliber. But only Einstein does those three or four of them.

• 19:15Dwarkesh Patel?

  I'm glad you brought up the topic of ideas being in the air and ready to pluck. Because this leads me directly to the next question. I was rereading the lecture notes from your quantum information science class, and there's the lecture on quantum teleportation. And you were answering, "How do people figure this kind of stuff out?" And you say, "It's worth pointing out that quantum mechanics was discovered in 1926, and that quantum teleportation was only discovered in the 90s." And of course, quantum computing, I'm a big fan of David Deutsch, and he discovered it, or he thought of it, in the 80s.

• 19:50Dwarkesh Patel?

  It seems like these ideas were ready to pluck, back when quantum mechanics was developed. Why did it take so long to have these ideas plucked?

• 19:58Speaker 00

  Yeah, that's an extremely interesting question.

• 20:04Speaker 00

  I mean, the whole idea of thinking about quantum entanglement, not as something metaphysically weird, or spooky, or basically, "How do we explain this away? How do we get rid of this?" But in terms of how do we use it? How do we use it to improve information processing? I think that's a point of view that, as far as I know, really only started with John Bell in the 1960s. Bell having this remarkable insight, that you could do this experiment to test the prediction of entanglement

• 20:50Speaker 00

  and distinguish it from any possible theory involving local hidden variables.

• 20:59Speaker 00

  And then, a little bit later, Steven Wiesner had the idea of quantum money, or using the uncertainty principle for cryptography, although, again, he was not able to publish that until the 80s.

• 21:17Speaker 00

  You know, there are, there are a few things that I could say here. I mean,

• 21:22Speaker 00

  um, one is that when, when quantum mechanics was discovered in the, in the twenties, uh, it, it was not at all clear to the people who, who discovered it that this was sort of a, a, a final form that the laws of physics would take, right? You know, they thought, you know, I mean, uh, uh, that there was a, a large contingent that, that, that thought that, uh, you know, this, this is some, you know, uh, scheme that, that sort of represents our current knowledge. But, you know, but clearly one, one, you know, what, what, what, what has to improve on it, right? And then that, I mean, that was very much Einstein's point of view. And, and I think also Schrodinger's.

• 22:03Speaker 00

  Uh, and, and then, uh, you know, like Bohr and Heisenberg, uh, you know, they were very much, you know, opposed to, to looking for something beyond quantum mechanics, but, uh, but, but, but sort of not, um, uh, you know, they, they're like, like, they, they sort of, sort of not, not in a way that was sort of, you know, in, inspiring more research about what you could do with quantum mechanics, right? They just wanted everyone to just sort of shut up and stop, stop asking about these things, right? So you could say, you know, even though Bohr was right and, and Einstein was wrong, uh, on the issue of local hidden variables, uh, you know, there's a, there's a deeper sense in which,

• 22:46Speaker 00

  in which, you know, Einstein was the more right one and sort of putting his finger on, you know, there is something here that we do not yet understand and that we need to understand, right? And, you know, indeed, you know, that, I'm sorry, uh, you know, indeed, indeed, that, that, that, that thing would not be understood really until, until the discovery of the Bellan equality in the sixties. The other, um, You know, issue is that when quantum mechanics was was discovered and into the, you know, the the 30s, you know, there was so much to do in terms of, you know, figuring out how chemistry works, right, just just applying quantum mechanics to understanding the real

• 23:28Speaker 00

  world around us, right, that and and and you could say on on the other side in computer science, you know, the, I mean, for God's sakes, the entire notion of a universal computer was just being born, right, the whole, you know, the whole field of classical computing was only just being born, right, so there was sort of so much, you know, on the plates of both sides that that, you know, it was, you know, it it might have seemed wildly premature to anyone to to combine the two, right, and then, of course, World World War II, you know, intervened, you know, you know, and and the people who were doing fundamental science, a lot of them went to work, you know, either at the Manhattan Project or

• 24:12Speaker 00

  Bletchley Park, and, you know, and then after that, I mean, I I think theoretical physicists were very focused on just, you know, this zoo of new particles that were being discovered and in formulating quantum field theory, you know, it was very, very much out of fashion for for decades to think about the, you know, the the fundamentals of quantum mechanics itself, and, you know, in the meantime, you know, people were were finally, you know, building, commercializing, figuring out the uses for classical computers, that was, you

• 24:50Speaker 00

  know, a very young area itself, and I mean, the the entire theory of computational complexity, which, you know, is sort of an intellectual prerequisite to quantum computing, right, that only developed in the 1960s, right, you know, and then the theory of, you know, P and NP and NP completeness, that was only the 1970s, right, so.

• 25:14Speaker 00

  Now, you know, if we think about, you know, the, the people who could have combined these, these fields, I mean, I, I think of, you know, I think of John von Neumann as an obvious possibility because he was, you know, of course, in a, a, one of the, the great,

• 25:30Speaker 00

  pioneers of both of computer science and of quantum mechanics. Right. In fact, you know, he invented the notion of entropy of quantum states. And, uh, but you know, he just, he had a lot of other things on his plate and then he died early. He died in the fifties, right? I mean, you know, Alan Turing was also, you know, of course, a, you know, founder of computer science, who was also passionately interested in the foundations of quantum mechanics. You know, as we know from his, his letters to his friends, uh, you know, he, uh, he, he died when he was forty two.

• 26:08Dwarkesh Patel?

  Right.

• 26:10Speaker 00

  So, so, you know, what, what, what, whatever the case, you know, I, I feel like quantum mechanics and the theory of computing were both in place by the nineteen thirties. But there was a lot of other stuff on people's plates. And, you know, the, the, the idea of, you know, thinking of entanglement as a resource that only starts in the sixties. Computational complexity that only starts in the sixties and seventies. And then, you know, maybe a decade after that, people start thinking about quantum computation.

• 26:39Dwarkesh Patel?

  Interesting. Um, I've heard two other theories and I, I want to see how, what you think of them. So the first one is, I, I think, I, I might be misquoting him, but I think at some point David Deutsch said, the reason he was able to think seriously about, um, quantum computing was that he took the many worlds interpretation seriously. And because people before him hadn't taken many words seriously, they hadn't been able to quantum computing. And the second, sorry, go ahead.

• 27:00Speaker 00

  Go on, go on. Okay. Well, maybe, maybe, maybe should I respond to that one?

• 27:04Dwarkesh Patel?

  Yeah, yeah.

• 27:05Speaker 00

  Okay. So, so that is definitely true for Deutsch. Right, and I know, you know, Deutsch well, you know, and then, you know, and he actually, you know, became a big believer in the many worlds interpretation when he was here at UT Austin. Right. As a student, as you know, and he, he heard Hugh Everett himself give a lecture about it. Bryce DeWitt, who was, you know, one of the main early proponents of the many worlds interpretation, was also here at, at UT Austin and had a big role, had a, had a big influence on, on Deutsch. And, you know, and Deutsch was, was thinking about, you know, how would you sort of make, you know, sort of shake people?

• 27:49Speaker 00

  How would you sort of make them realize that quantum mechanics is universally valid? That it applies at all scales? Well, you know, if you could build a computer, right, that, you know, could do a superposition over, of different computations and then you could see the results of interference between them, right? That at that point, conceptually, it is almost like making a superposition over, you know, a brain that can think different thoughts, right? And, and then, you know, i- if you could have that, then, then, you know, the whole idea of the, that observers collapse the wave function just by being observers is, is no longer tenable. But, so one, one problem is that Richard Feynman had the idea of quantum computing around the same time as Deutsch did, right?

• 28:34Speaker 00

  And Feynman, I mean, he was certainly aware of the many worlds interpretation, he was aware of Everett, but, but that was not his motivation for thinking about quantum computing. He was, you know, as, as usual, he, he was much more practically focused. He was thinking about how do we simulate physics? You know, how do we simulate nature with a computer? And if we use classical computers, we suffer this exponential slowdown, right? And so can we build a new kind of computer that will, that will solve that problem and give us a, a, a universal quantum simulator?

• 29:13Speaker 00

  You know, people were, there was also a whole movement in the seventies and eighties to think about the physics of computation, including like the thermodynamics of computation. Can you make computation inherently reversible, you know, and all kinds of other issues, right, that are, that are, that are not about, you know, exponential speed ups. But that was also one of the intellectual streams that sort of led directly to, to quantum computation, right? So, but I think that what, what you said is very much true for Deutsch, but you know, there were others, you know, besides Deutsch who were thinking about these things. Feynman was only one, there were, there were others as well, I think, you know, Benioff, uh, you know, several others.

• 29:57Speaker 00

  And, um, you know, uh, um, you know, few, few people in this field are as, uh, are as, uh, um, uh, um, as, uh, as, as messianic as, as Deutsch is about the many worlds interpretation.

• 30:15Dwarkesh Patel?

  It, it's interesting that, that, uh, come to think of it, that both Deutsch and Turing were trying to solve a separate philosophical problem when they came up with their model of computation, um, or at least in part. Uh, okay, so the second theory I've heard is that, uh, since the 1970s, that academia has been less open to new ideas. And you mentioned, uh, Weisner, Everett, and both of them, I understand, were kind of, um, I, I don't know, looked down ostracized or something. Um, is there, is, has that, is that theory confirmed?

• 30:44Speaker 00

  I think that it, I mean, it, it is possible that in some parts of academia, you know, it has become harder to explore new ideas, you know, I, uh, than, than it, than it, than it once was. Um, you know, I could believe that about the social sciences, I could believe that, you know, about parts of medicine, you know, people used to do just completely crazy things, just, you know, invent some new concoction, inject themselves with it, you know, see what happens, you know, write an article about it, you know, whereas today, you know, it might take like a billion dollars of investment before you could even get to the point where, you know, anyone would consider it remotely ethical to do such a thing, right?

• 31:28Speaker 00

  So, uh, on the other hand, in, um, in, in physics and, and, uh, uh, let's say, uh, uh, you know, um, You know, speculation about, you know, the foundations of computing and cosmology and things like that. I think if anything, things have gone in the opposite direction. And, you know, and this is partly because we now have this pre-print server, this archive, where, you know, everyone can post, you know, all of their new research ideas, you know, with no filter, right?

• 32:13Speaker 00

  You know, and I think that that is, that has somewhat transformed the scientific landscape. You know, because, I mean, we still have journals, but, you know, journals are now just like a final stamp of approval that, you know, in many fields is, yeah, I mean, it's important when you're looking for jobs or things like that. But journals are no longer gatekeepers to, you know, that can sort of prevent people from seeing your paper, right? And so, so, you know, if you just look at the quantum physics, you know, archive every day, you will see so many far out ideas, right?

• 32:56Speaker 00

  It is so much crazy stuff that it's, you know, it's very hard to believe that a modern day Weisner or Everett, you know, would feel any barrier to, you know, to getting their their idea out there, right? I mean, today, the problem is more that, like, there are so many, you know, bold new ideas that, you know, of course, you know, most of them won't go anywhere, right? Most of them will fail, right? And, you know, and so there's, there's so much to sift through if you're, you know, looking for what is, what is, what is actually going to be revolutionary.

• 33:31Dwarkesh Patel?

  I'm sure your comment section and email fills up with these, but have you, how many of the important ideas, or do many important ideas in the field come from people outside academia? Or is it mostly the people with PhDs working within the system?

• 33:45Speaker 00

  Well, okay, I mean, I mean, those are, those are not exhaustive categories, right? Because, you know, there, there are, you know, there, there, there have been breakthroughs that have come from people who are not in academia. Very often, what you find is that these are people Who were sort of on the margin of academia, like they got a PhD and then they left, you know, the, the academic world, or they, uh, they did part of a PhD or, or, or, or things like that, right? There was a, uh, um, famous case of Yi Tangzhan, who was this mathematician

• 34:26Speaker 00

  from, from China, right, who, uh, um, proved that, that there are infinitely many pairs of primes at most seventy million apart, right? Uh, which was, you know, a, a, a major advance in number theory, right? And this was a guy who had, like, he had gotten a PhD in math in China, I think, but then moved to the US and then, uh, worked, um, uh, making, making sandwiches at Subway, uh, you know, just, you know, in order to like support his family and, and, you know, work, uh, of, of, of various other odd jobs, but, you know, but, but, but continued working on math. Uh, so, um, I don't, you know, I mean, I

• 35:06Speaker 00

  mean, uh, you know, I, I, I hear all the time from, you know, people who are, who are like complete, uh, uh, autodidacts, you know, who, uh, you know, taught themselves the S and, and, you know, that they think that they've solved the P versus NP problem or whatever, right? I, I've, uh, um, you know, that, that is, uh, um, you know, that, that, that is usually someone who just doesn't understand the question, who was just made some, you know, uh, um, you know, and, and, and, and then, you know, I mean, there, there is a, a distinction because some, sometimes people, you know, uh, who sort of teach themselves the field, they just, you know, they, they really want to learn. They just want an expert

• 35:51Speaker 00

  to talk to, you know, who will tell them like, here's, here's where you're on the right track, here's where, you know, you, you made a mistake. And they will thank you for that, right? Other times you get people who really dig in their heels and you know, you know, the establishment is is censoring me and, uh, you know, I had, uh, when, when, when I taught at MIT, I had people, you know, someone, uh, uh, like writing to the president of MIT to try to get me fired. Uh, uh, uh, you know, I had another one sending me death threats, you know, uh, because, um, um, you know, like very, very specific, you know, I had to actually contact the police about them, uh, you know, because I would not publish their, you know, uh, proof of P equals NP

• 36:35Speaker 00

  or their refutation of quantum computing on my blog, right? So you get, you get, you get, you get the whole spectrum. Uh, but, um, you know, the, the, the, the other thing you, you, you find is, uh, uh, you know, there are, you know, and, and, and a, a lot of the readership of my blog comes from people who, who studied, uh, technical subjects in college, studied CS or math or physics and then went out into industry, right? But maintain this connection, you know, maintain their sort of curiosity about fundamental questions. And some of those people, uh, uh, you know, actually want to continue to do research. And, uh, I'm actually, uh, co-authoring a paper with one of them right now.

• 37:21Speaker 00

  Uh, you know, I posted this survey article about the busy beaver function, uh, uh, on my blog recently. And, uh, uh, you know, there was a, um, um, you know, I guess a, a hobbyist who, who solved some of the open problems.

• 37:36Dwarkesh Patel?

  Really?

• 37:37Speaker 00

  A survey and, uh, yeah, and, and had a lot of new ideas and, and he and I are going to write a paper about it.

• 37:42Dwarkesh Patel?

  Oh, cool. Interesting. Oh, by the way, is that Shuang the same one that, uh, co-authored the Nielsen textbook on quantum information?

• 37:49Speaker 00

  No, no, no, no, there's, there's a, a Yi Tang Zhang and then there's a, uh, the mathematician and then Isaac Chwang.

• 37:56Dwarkesh Patel?

  Oh, okay.

• 37:57Speaker 00

  Is the physicist who co-authored the Nielsen Chwang textbook.

• 38:00Dwarkesh Patel?

  Okay, got it. My mistake. Um, so let me ask you about busy beaver. Um, I, I was, is the proposition three was that, uh, you can't?

• 38:10Speaker 00

  I, I, I have no memory for the numbering of propositions.

• 38:13Dwarkesh Patel?

  Okay. Uh, I was looking, can you actually just explain what the busy beaver function is before I ask this?

• 38:17Speaker 00

  Yes, okay, sure. So, so the busy beaver function is a really, really remarkable, uh, uh, uh, sequence of, of hyper rapidly growing, uh, integers. And the way that we we define it, you know, it was it was it was invented in nineteen sixty two by a mathematician named T. Borroto. And and and and basically what we do is what we what what what we would like to say, let me let me start with what we'd like to say. We'd like to say, you know, the, you know, if I want to name the biggest number that I could possibly think to define, then why not just say, you know, the biggest number

• 39:00Speaker 00

  that can be named using a thousand words or fewer. Okay, or something like that, right? And but then I have to be careful because there's an inherent paradox there, right? Which is I also could have said like one plus the biggest number that can be named with a thousand words or fewer. But then that that, you know, I just named that with fewer than a thousand words. Right? And so, uh, um, so so so so from this, you know, the the the conclusion that, you know, logicians, philosophers drew more than a hundred years ago is that the concept of naming a number, you know, in English is not as clear as we think it is. Right?

• 39:42Speaker 00

  It it it leads to paradox if you're if you're not careful about it. But but but but what what if we could name a number in a way that was completely unambiguous? Well, you know, since the since Alan Turing in the nineteen thirties, we've had such a way. That way is computer program, right? Or or Turing machines. And so we could say, um, think of the largest integer that can be generated by a computer program that is at most, let's say, a thousand bits in length. Okay? And, you know, now you have to be careful. What do you mean by by by that? Right? Because, of course, a computer program could run forever. Right?

• 40:25Speaker 00

  It could start to, you know, I could, we could easily write a program that says, do print not print nine loop, right? And it would just print an infinite sequence of nines. So what we do is we restrict attention to those computer programs that eventually halt.

• 40:43Speaker 00

  We say among, let's say for a given N, we consider all of the possible computer programs that are N bits long. And say there are 2 to the N power of them, or at most 2 to the N power, right? Many strings will just lead to things that are not even programs. You know, they won't even compile, so we'll throw those away, right? Now, among all of the valid N bit programs, some of them run forever. We just run them on a blank input, so we throw those away as well. Right? We consider only the ones that eventually stop. And now, among all of the ones that stop, we take the one that runs for the longest number of steps, the largest number of steps until it stops.

• 41:28Speaker 00

  And that number of steps, that is what we call the N busy beaver number.

• 41:33Dwarkesh Patel?

  Hmm, yeah.

• 41:34Speaker 00

  So, so, so, so, so the way that Rado defined this was using Turing machines, which is just one particular programming language, the one invented by Alan Turing in the 1930s. He said busy beaver of N is the largest finite number of steps that any N state Turing machine can run for. Right? And so, so, so, you know, the, the, the amazing thing is that one can prove that this function grows faster than any computable function. Right? So, so, you know, no matter what, you know, sequence of integers, you know, you can, you know, basically,

• 42:19Speaker 00

  if you are in a contest to name, name the largest number, and if you say busy beaver of 1,000, then you will utterly destroy any opponent who doesn't know about the busy beaver function or about anything similar to it. Okay? So. You know, so one can say further remarkable things about this function like that, you know, only a finite number of values of the function can actually be proven from the axioms of set theory, right, for reasons of Gödel's incompleteness theorem, basically, after a certain finite point, you know, the the values of this function,

• 43:00Speaker 00

  you know, we can, we, you know, presumably it has definite values, right, because it's a this clearly defined function, and yet we could, we could no longer prove what they are. Okay, so, so right now, only, you know, if you, if you look, if you take the busy beaver function as Rado defined it in the 60s, only four values of the function are known. Okay, the busy beaver of 1 is 1, busy beaver of 2 is 6, busy beaver of 3 is 21, and busy beaver of 4 is 107. Busy beaver of 5, it is only known that it's at least 47 million. Right, you know, and we, we don't know how much bigger it might be.

• 43:41Speaker 00

  Busy beaver of 6, it's at least in about 10 to the 36,000. Okay, might be much bigger. Busy beaver of 7, it's at least 10 to the 10 to the 10 to the 10 to the 18 million. You know, and then it might be enormously larger still. Okay, just to, just to give people an idea of how this function grows.

• 44:03Dwarkesh Patel?

  Yeah, yeah. And by the way, I recommend everybody who's listening to check out the Busy Beaver frontier paper, because it was written in such a way that, I also want to ask you how you learned to write so well. It was written such a way that non-expert like me could understand it. And just to clarify from my own understanding, it's not that a busy, there isn't a function that for any n is greater than busy beaver of n. It's just that it, it won't, busy beaver will eventually be with more states than if you have to

• 44:31Speaker 00

  That's right.

• 44:31Dwarkesh Patel?

  It's that function, it will grow back bigger.

• 44:33Speaker 00

  That, that, that's exactly what I meant when I said grows faster than.

• 44:36Dwarkesh Patel?

  Right.

• 44:37Speaker 00

  Right. I mean, each particular value of busy beaver is just some positive integer, right?

• 44:42Dwarkesh Patel?

  Yeah.

• 44:43Speaker 00

  It's a very concrete thing, right? You know, like it's 6, or it's 21, right? But, you know, if you look at the rate of growth of these integers, right, it will dominate, eventually dominate any computable function.

• 44:56Dwarkesh Patel?

  Right.

• 44:57Speaker 00

  And and and in practice, not just eventually, but very, very quickly.

• 45:01Dwarkesh Patel?

  Yeah, and you show very elegantly in the paper that that means you can independently prove the halting problem and Gödel's incompleteness theorem.

• 45:08Speaker 00

  Yeah, yeah, I'm looking at, I mean, I mean, I mean, like, the the unsolvability of the halting problem, Gödel's theorem, like, these things are so intertwined, like, there are many, many different, you know, ways to prove them all, right, but the the busy beaver function gives you one way that, yeah, you can prove that, you know, that you can you can use it to prove independently that there is an uncomputable function, you can use it to prove Gödel's incompleteness theorem.

• 45:37Dwarkesh Patel?

  Right, okay, so my question, the proposition three was the one that said,

• 45:42Speaker 00

  Okay.

• 45:43Dwarkesh Patel?

  for any axiomatic theory, you can't prove all of busy beaver with it.

• 45:46Speaker 00

  Right.

• 45:47Dwarkesh Patel?

  But, so my question was, can you can keep, even though there's no systematic way to extend our set theory, is there plausibly a way that you can keep extending it such that you can prove higher and higher values of busy beaver?

• 46:04Speaker 00

  Uh, that's a, that's a, that's a wonderful question.

• 46:08Speaker 00

  You know, we, we, I, I would say, we, we, we don't really know yet, right, because right now, we can't even pin down busy beaver of five, okay? I know, now, now, my, my guess would be that the, the, the resources of, of, you know, existing set theory are perfectly enough to do that, right, but, but, you know, we don't even know that, right, so I, so, four years ago, a, a student of mine, named Adam Yedidia, and I decided to, you know, look into a question that, for some reason, no one had looked at before, which was, you know, like, what is the smallest n for which

• 46:50Speaker 00

  we can actually prove that the value of busy beaver of n is independent of set theory, right, like, it was clear that there is some n for which this is true, but are we talking about 10 million, or are we talking about 10? Right, so, so, so in practice, what this problem boils down to is, is, is almost like software engineering, like you have to construct a Turing machine that checks all of the theorems of set theory, and it halts only if it finds a contradiction, right? And you have to build such a Turing machine with as few states as possible, okay?

• 47:30Speaker 00

  If you can build such a machine with only N states, then you've proven that, that set theory cannot determine the value of busy beaver event, because if it did, then it would thereby determine its own consistency, which is exactly what Gödel's theorem does not allow, right? So, um, so what we managed to do is we managed to find such a machine with 8,000 states, okay? About 8,000 states, you know, that was after a lot of optimization, right? And, you know, a lot of coding and, and, and, and engineering and, and, and ideas, right? Since then, a, again, a, a hobbyist, to come back to your earlier question, someone

• 48:14Speaker 00

  outside academia by the name of Stefan Ohrer, has managed to improve our bound and got it to under 800 states.

• 48:23Dwarkesh Patel?

  Yeah.

• 48:24Speaker 00

  Okay? And that, that is the current record. Now, if you could get that down to like, you know, you know, I, you know, it, it is a wonderful question, could you get it down to like 10 states or something like that, right? And, you know, that, that would tell us that we have to already go beyond the current axioms of set theory, you know, even to just get the next few values of the busy beaver function, right? But maybe not, maybe, maybe, maybe you can even get 100 of them with, with, with existing set theory, right? We, we, we don't know. Now, what you can do is, um, you know, you know, at, at, at whatever point, you know, ZF set, Zermelo-Frankel set theory, you know, which is the, the...

• 49:08Speaker 00

  Accepted basis for, you know, most of math. At whatever point it runs out of steam, you know, we don't know exactly where that point is. But one can then extend it by what are called large cardinal axioms. Right, which basically assert that there exists an infinity that is bigger than any infinity that can be defined in ZF, that theory, right? Or, you know, you can, you can say, you know, you know, you know, or infinity is of various particular kinds, right? And, you know, and presumably one could then settle more values of the busy beaver function that way, right? But, but the issue is, you know, no matter what set theory you think of, right?

• 49:51Speaker 00

  As soon as you can build a touring machine that enumerates all of the theorems of that set theory, then however many states there are in that touring machine, that then sets a bound on how many busy beaver numbers that, that theory can ever determine. Yeah. So, so in some sense, the, the set theories that can determine more and more busy beaver numbers will have to become more and more complicated. Right. Right, right, we, we, we, we, we know that. And, and, and as, as you said, right, there will never be a systematic way to search for, for them, because if there were, then that would make the busy beaver function computable. Right. And, you know, and, and, and what it means for there to be no systematic way to

• 50:36Speaker 00

  search is that, you know, you could, we could keep like proposing more and more set theories. And if, if you look at modern, you know, mathematical logic, set theorists do this, right? They do propose more and more large cardinal axioms, but sometimes they actually discover that their axioms are inconsistent, right? Or, you know, they, they sort of provisionally, you know, adopt an axiom or use it, but the community is not really convinced that, that it won't lead to an inconsistency. Right, so that, you know, there's no surefire way to think of these axioms and be confident that, you know, that you actually still have a consistent system.

• 51:21Dwarkesh Patel?

  Hmm, okay, let me offer a very, very silly thought experiment.

• 51:24Speaker 00

  Yeah.

• 51:25Dwarkesh Patel?

  Okay, so this is inspired by that joke that if you shoot enough sunlight at the Earth, it'll shoot a Tesla back, right? Okay, so the idea is if the Turing principle is true, you can simulate the Earth and the solar system and everything on a very incomprehensibly big computer, right? With all the humans on it.

• 51:44Speaker 00

  Given the appropriate initial data.

• 51:47Dwarkesh Patel?

  Yeah, yeah, and so simulating all of that is a computable function. And if you can check in like every hundred years and see what is the biggest busy beaver number that humans have proven this century, what is the biggest busy number proved a hundred centuries, is that not a computable function where that tells you busy beaver of N indefinitely higher?

• 52:07Speaker 00

  Well, it would give you a way to compute arbitrary values of the busy beaver function if humans were indeed to continue, you know, you could say, under the assumptions that number one, you know, the, you know, everything in our physical world is computable. I mean, you know, we, we, we let that, you and I just let that assumption pass almost without comment, right? Although, you know, of course, that's an enormous question in itself, right? With some brilliant people like Penrose on the, on the other side of that. But all right, but, but, you know, and then, so assuming that, that, you know, everything

• 52:51Speaker 00

  we're doing is computable and also assuming that we could somehow, you know, continue finding more and more values of the busy beaver function indefinitely, right? If that were true, then we would have a contradiction.

• 53:05Dwarkesh Patel?

  Yeah.

• 53:06Speaker 00

  Yeah.

• 53:07Dwarkesh Patel?

  Yeah, so then either everything is not, either the Turing principle is false, or we can't indefinitely keep extending.

• 53:13Speaker 00

  Yeah, yeah, you could, yeah, you could say a very conservative way out would be to say, well, you know, our quest to compute more and more busy beaver numbers will come to an end.

• 53:23Dwarkesh Patel?

  Right, okay, that's very interesting.

• 53:24Speaker 00

  And, you know, in fact, there has not been another busy beaver number determined since the early 1980s.

• 53:31Dwarkesh Patel?

  Yeah, that's interesting.

• 53:33Speaker 00

  Which is when Busy Beaver 4 was finished.

• 53:36Dwarkesh Patel?

  Okay, so I'm looking forward to the paper you published with the hobbyist.

• 53:41Speaker 00

  Yeah, Bruce Smith is his name.

• 53:44Dwarkesh Patel?

  Bruce Smith, okay, very interesting. Okay, so let me ask you now, I remember in class last year, you said, you know, that basically, we have a very, a few very important quantum algorithms like Grover's and Shor's that were discovered in the 90s, and now, a lot of our stuff now is just an extension of those algorithms. What do you think is the potential of finding, is there a good reason to think that there are other quantum algorithms to be discovered that are as fundamental and important as Grover's and Shor's were?

• 54:12Speaker 00

  I would, I would love it if there were, right? I'd be thrilled to, you know, discover such an algorithm, have one of my students discover it, right? You know, this is, this is, you know, I mean, that's the kind of discovery that we, that we enter this field for, right? I mean, you know, now, now, you know, if we're being intellectually honest, you know, we have to admit that, you know, it's, it's been 25 years since Grover's algorithm was discovered, right? And, you know, maybe, maybe no other quantum algorithm as fundamental

• 54:51Speaker 00

  as Shor's or Grover's has been discovered, you know, in the last 25 years. What we have discovered, you know, as you, as you learned, because you took my class, was, you know, a lot of, you know, an enormous number of generalizations and new applications and variations of Shor's and Grover's algorithms, you know, including what are called quantum walk algorithms, including, you know, phase estimation based algorithms.

• 55:28Speaker 00

  And, you know, and, and, and some, some totally different quantum algorithms were also discovered, although, you know, the problems they solve are maybe more abstruse, right? Or, you know, hard, you know, it's harder to explain what, what problem they're, they're, they're, they're solving. Uh, and, you know, so, so, you know, you could, you could wonder, you know, is it, is it, is it lack of imagination on, on, on, on, on our part? Or is it, you know, I mean, I, the, the, you know, another possibility is, you know, if you look at the history of classical computer science, you know, what you find is that there are a few basic techniques that were discovered very early on in the history of

• 56:12Speaker 00

  classical CS. One of them is dynamic programming, right? Like, uh, you know, dividing, you know, breaking down your problem, like recursively into sub-problems, right? I mean, we could say, you know, in general, recursion, right? Solving, you know, divide and conquer, greedy algorithms, uh, you know, uh, convex programming, you know, linear programming, uh, you know, um, um, Gaussian elimination, right? And, you know, and, and, and, and most of the, you know, I mean, the field of classical algorithms is enormous. And yet, you know, most of the classical algorithms that we know are somehow built

• 56:54Speaker 00

  up out of these motifs that are just, that were discovered very early on, right? And, and we don't normally think of that as a failure of classical algorithms, right? We just think of it as, you know, there are these fundamental features of the algorithmic universe that, you know, that people noticed as soon as they started looking, right? And then, you know, and then, you know, you can go much further, but, but you go much further by, by building on the basic things that you have, right? And so, so, uh, so, so maybe we should think of Shor's algorithm and Grover's algorithm not as just specific algorithms, but as sort of some of the basic design motifs of the world of quantum algorithms. I see. And then, you know, it's not, it's not surprising that they were discovered very

• 57:39Speaker 00

  early on, just like dynamic programming was discovered, you know, right at the beginning of the history of classical algorithms. So, um.

• 57:49Speaker 00

  You know, so, you know, I mean, I mean, that's, that's, that's, that's one point of view. Now, another point of view is, you know, if, like, when, when people ask for, for more quantum algorithms, or, you know, they, they, they, they hold us to account for our failure to discover more quantum algorithms, you know, I, I like to answer that question with another question, which is, well, well, well, what are the problems that you would like these algorithms for, right? And amazingly, that, that, that question almost always stops, you know, they ask it, right? Because like, they didn't even, you know, well, well, uh, because, because no matter what problem they name, you know, there's an excellent chance that people in quantum algorithms have thought about it, you know?

• 58:33Speaker 00

  And we know, you know, something about how much speed up you can get from a Grover-type algorithm, you know, but, uh, we have good reasons to think that you're not going to be able to get better than that, or, you know, I mean, or, you know, we, or, or we say, well, maybe there's, like, if, if, in the case of the graph isomorphism problem, yeah, sure, maybe there's a polynomial-time quantum algorithm, but probably just because there's a polynomial-time classical algorithm, right? And that, that, you know, and it's just, it's that that hasn't been discovered yet, right? Although, you know, there, there's been major progress toward it. Uh, so, so, uh, you know, no matter what problem they name, right? I mean, probably someone has studied it in the context of quantum algorithms, and I

• 59:16Speaker 00

  could then tell them for that problem, you know, exactly what is the current situation, and, you know, uh, what, what are people stuck on? You know, and, and so, it might be that if we want to discover fundamentally new quantum algorithms, that the way to do it will be to realize fundamentally new problems, right? Problems that people hadn't even thought about. There's Designing an algorithm for, you know, previously, right? You know, the way, um, you know, another thing, you know, another way that I like to put it is, you know, like, like, in, in any, you know, in any given area of math or science, right?

• 59:58Speaker 00

  There is this phenomenon of low-hanging fruit that gets picked very, very early on, right? And, uh, and then those of us who come into the field a little bit later have to ju- have to leap higher, you know, if, if we wanna, uh, find any fruit, right? But, uh, the, you know, I think the, the, the ultimate solution to the problem of low-hanging fruit being picked is to find a new orchard, you know? And, uh, so, so, you know, figure out, uh, what are, you know, potential problems that quantum computers could solve that, that, that, that no one has been thinking about, uh, before? You know, maybe people actually starting to get quantum computers, as they finally are today,

• 1:00:40Speaker 00

  that they can experiment with will help stimulate the discovery of those, you know, new problems or new applications.

• 1:00:47Dwarkesh Patel?

  Just like with Grover's algorithm, is there some reason to expect that from, if from first principles, there are other algorithms that can be solved by, uh, quantum algorithms?

• 1:00:56Speaker 00

  Yeah, so, so i- it is, um, uh, you know, I, I, I, anything where it's sort of as basic as Grover's algorithm, that you just look at, uh, you know, the way that amplitudes are changing over time and think that an algorithm is going to exist, right? That probably would have been snapped up by now, just because quantum algorithms have become so much more sophisticated, uh, compared to what they were 25 years ago, okay? But there are some problems where, uh, there is some evidence that a quantum algorithm might exist, uh, even though we don't, we don't yet know it, if, if it does exist. A good example is computing the edit distance between two strings, right?

• 1:01:40Speaker 00

  Which means the minimum number of, uh, insertions and deletions and changes that I have to make to change one string to another string. This is a fundamental problem, uh, for a DNA sequence alignment, for example. Uh, the best known algorithm for it takes quadratic time, based on dynamic programming, in fact.

• 1:02:00Speaker 00

  Uh, and you know, there is some evidence that there might be a quantum algorithm that would take N to the three halves time or something like that. But, but if so, uh, it has not yet been discovered. So, um, so, so, so, so, so there are cases like that. Um, um, no.

• 1:02:22Dwarkesh Patel?

  Gotcha. Okay. Um, the next question I wanted to ask you was, why do many of the important discoveries, not just in this field, but in many other fields, come from closely communicating groups of collaborators or people within such groups? Um, you said on Sean Carroll's podcast that, uh, uh, uh, Shore and Grover were collaborators at Bell Labs.

• 1:02:43Speaker 00

  I'm, I'm, I'm not sure that they actually were collaborators. I mean, they, they, uh, they, they worked in the same building, I believe. You know, I think they, they, you know, you know, I think the, the discovery of Shore's algorithm created a lot of excitement, you know, uh, well, you know, all over the place, but certainly at Bell Labs, which is where Shore was, right? And I think that Grover, who worked also at Bell Labs, but in a completely different department, I think he was affected by that excitement. And, uh, um, you know, I'm not, I'm not even, uh, uh, I'm not even sure if, if, if they knew each other prior to Grover's discovery of Grover's algorithm. But, uh, um, I could, I could, I could, I could ask them that. But, uh, uh, um,

• 1:03:29Speaker 00

  but, but, you know, I mean, more, more broadly, uh, you know, it is certainly true that, uh, in the history of, of, I, of ideas, like, you know, uh, uh, you know, major innovations seem to come in clusters all the time. Bell Labs was a huge example of that, right? I mean, the, um, um, you know, the Shores and Grover's algorithms were really, really at the tail end, right? Of the, you know, the, the heyday of Bell Labs, right? Which was mostly the, uh, you know, the, the 40s, 50s, 60s, 70s, right? But I mean, uh, you know, you had the invention of the transistor, you know, of the communication satellite, uh, and so many other things, right?

• 1:04:14Speaker 00

  Uh, from this, this one place. Um, uh, um, you know, another example, uh, would be, um,

• 1:04:24Speaker 00

  You know, I mean, you know, we could take Athens and the ancient world, right? We could take Florence. We could, we could look at Cambridge University, right?

• 1:04:35Dwarkesh Patel?

  Right.

• 1:04:36Speaker 00

  Let's say, you know, at the, the, the turn of the 20th century, right? That had just so many mathematicians, economists, philosophers, physicists to, to revolutionize the world. Now, you know, this might be because, you know, something about the environment, right? That, uh, uh, you know, that, that, um, um, you know, ideas bounce off of each other, right? People see something, they, they see someone achieve something spectacular and they're either, you know, inspired by that or they, they, uh, they, they view it as a challenge, you know?

• 1:05:18Speaker 00

  They, they want to compete against that and come up with their own thing, right? You know, a, a, a Silicon Valley, of course, you know, would be another big idea. Although more for technology than for science, right? So that, that would, that would be one, one explanation. And a different explanation would be that, you know, the, the certain places at certain points in time just, you know, attract all of the people who, who, you know, maybe anyway would have had these great ideas. But, you know, that kind of person wants to go to these, you know, these, these centers, you know, wherever they are. And so, so, so, so, so, so these centers will just collect the kind of people who are likely to discover these things.

• 1:06:01Dwarkesh Patel?

  Right. Correlation doesn't equal causation in this case. Okay. All right. Let me ask you now, I've interviewed a lot of economists on this podcast. I think this question would be interesting to the listeners. In your paper on why philosophers should care about complexity, you talk about how the difficulty in finding natural equilibrium might be relevant to discussions on economics. Can you explain, uh, can you explain this?

• 1:06:23Speaker 00

  Yeah, okay, so so there was a big advance in theoretical computer science fourteen years ago when it was the theoretical evidence was finally discovered for why computing a Nash equilibrium is a hard problem, basically. And, you know, and this this confirmed a suspicion that people had had for a long time, right, because, you know, if we look at a von Neumann equilibrium, right, which is like an equilibrium of a, let's say, of a two-player zero-sum game, right, then, you know, this can be found easily, you know, using linear programming, right?

• 1:07:08Speaker 00

  But a Nash equilibrium is somehow a more complicated beast, right? And it's, you know, you know, the way that Nash proved that they exist in the 50s was using the, what's called the Kakutani fixed-point theorem, right? It's some fixed-point theorem from topology. And and if you try to actually unwind the existence proof into an actual algorithm to calculate the equilibrium, then what you get is an algorithm that ends up taking exponential time, right? You know, it eventually hits the equilibrium, but it, you know, it it it may have to follow an exponentially long trail before it reaches it.

• 1:07:53Speaker 00

  If you're interested in this, the best, by far, the best things that have been written about it, I think, are by by Christos Papadimitriou, right? Who, and when Papadimitriou was one of the discoverers in the, in 2006, along with Goldberg and Das Kalakis, of this this hardness theorem, which, you know, it doesn't prove that it's hard to find a Nash equilibrium, and it doesn't even prove that it's NP-hard. This problem kind of doesn't have the right structure to be an NP-complete problem, just because of Nash's theorem that tells us that a Nash equilibrium always exists, right?

• 1:08:34Speaker 00

  Like, in order to be NP-complete in any way that we currently understand, there has to there has to be a decision problem, you know, is there a solution or is there not a solution, right? But for finding a Nash equilibrium, there always is a solution, right? There's there's only the problem of how to find it.

• 1:08:53Speaker 00

  But what was shown is that basically finding a Nash equilibrium is at least as hard as any other problem for which, you know, a solution is guaranteed to exist because of the same kinds of principles.

• 1:09:07Dwarkesh Patel?

  Okay.

• 1:09:08Speaker 00

  So, so it's sort of, it is complete for that complexity class of problems for which, you know, a solution is guaranteed to exist for this, for this sort of reason. So, you know, what does this mean for, for economics? Well, it, it's not clear, right? If it has a sort of direct implication, but it, it sort of, it, it fits into this general narrative of, you know, just because an equilibrium exists, you know, that's, that's not the end of the story, right? I mean, you know, if, if the market can't actually find the equilibrium, right, in, in any, we could say, you know, if, if, if calculating this equilibrium would take exponential time, then we shouldn't expect the market to be able to find it either, right?

• 1:09:52Speaker 00

  And so, you know, now, now economists are, are well aware, right, that, that there are these issues, right, that, that, you know, you know, people are not perfectly rational, you know, even if, even if they want to be perfectly rational, which they don't always, you know, being perfectly rational might involve computations that they're just not able to deal, right? And, and, and, you know, and they've, they've, you know, with varying degrees of success, you know, they've tried to account for such phenomena. But, you know, I would say, you know, the, the, you know, Nash equilibrium are so central to economic theory, right, that, you know, the hardness of finding Nash equilibrium, I

• 1:10:34Speaker 00

  think, you know, is a, you know, maybe, maybe a, a non-trivial result, you know, underscoring that, that general point.

• 1:10:45Dwarkesh Patel?

  That's incredibly interesting. But do you think Hayek's knowledge problem, or the way he phrased it, might be related to complexity as well? So in terms of like, central planning in order to satisfy some constraints set by bureaucrats might be like an NP-complete problem where it's like...

• 1:11:00Speaker 00

  Well, I want to separate two different things. One is lack of knowledge about what is going on in the economy. And the other one is lack of ability to do computations on the knowledge that you have.

• 1:11:20Speaker 00

  So the hardness of Nash equilibrium is talking about the latter issue.

• 1:11:25Dwarkesh Patel?

  Yeah, I see what you're saying.

• 1:11:26Speaker 00

  You know, they're related in a way. They're both, you know, they're both different kinds of deviations from perfect omniscience. But there are different kinds of deviations from omniscience. And in theoretical computer science, you know, very, very often, we have to distinguish them.

• 1:11:50Speaker 00

  You know, I mean, often, like, people will ask me if some problem is, you know, is or isn't NP-complete, when, you know, what they really mean is like, how hard is it to collect the information? Which is, you know, it's kind of like apples and oranges. It's a category mistake. Once, you know, like, to even talk about whether a problem is NP or is NP or whatever, we assume that an input is given to you. So all of the information that you need, you know, you have it in front of you. And then, you know, we are exclusively concerned with the difficulty of calculating something about that information.

• 1:12:31Speaker 00

  Now, there is also, you know, the difficulty that, you know, people who are in, you know, economic actors, you know, don't have the information that they need. Or certainly, central planners, you know, don't have the information that they need. And there actually is a whole subfield of economics, you know, that's the economics of information. How much do you pay to learn something about, you know, what is going on? Or how do you hold a, how do you design an auction in a way that you elicit the information that you want from the participants in the auction and things like that? I think that economists maybe have an easier time dealing with those things or, you know,

• 1:13:16Speaker 00

  that that stuff has been better integrated into economics than the computational considerations.

• 1:13:21Dwarkesh Patel?

  Okay, that's incredibly interesting. Just a few more questions.

• 1:13:26Speaker 00

  Okay, sure.

• 1:13:27Dwarkesh Patel?

  Yeah, I'm going to bring us back to David Deutsch and creativity.

• 1:13:31Speaker 00

  Okay.

• 1:13:31Dwarkesh Patel?

  In the Ask Me Anything chapter of Quantum Computing since Democritus.

• 1:13:35Speaker 00

  Yeah.

• 1:13:35Dwarkesh Patel?

  You have a student ask you what, what complexity class is creativity in? And you say, part of what you say is, we've got a billion years of natural selection giving us a very good toolbox of heuristics of solving certain kinds of search problems like problems in NP. But that makes it kind of sound like we have more heuristics to solve these problems than chimpanzees do. Chimpanzees have more than ants. I don't know if this is how you meant it, but do you see like the algorithm for creativity as a thing you have or you don't have? Or is it like you, you just have better heuristics for searching through different?

• 1:14:09Speaker 00

  I don't, I don't, I don't know that there is such a thing as the algorithm for creativity, right? In fact, you know, the, the phrase is almost oxymoronic, right? That if, if there were such an algorithm, well then whatever output would no longer be creative, would it? Because it would just be the output of that algorithm, right? So, you know, I think that, you know, it, it, it, it seems like there is such a thing as, you know, general purpose reasoning ability or general purpose ability to invent creative

• 1:14:47Speaker 00

  solutions to problems, which, you know, let's say, you know, Einstein had more of than some random person off the street, but the random person off the street had more of than a chimpanzee and a chimpanzee has more of than an ant. But it is somehow very, very hard to articulate what we mean by that. You know, in a way that would actually support these, you know, comparisons across, you know, vastly different evolutionary histories and goals in life and all these things.

• 1:15:20Dwarkesh Patel?

  Do you, from the beginning to infinity, do you buy David Deutsch's term, a universal explainer, that people are universal explainers, AIs will be universal explainers, but non-human animals aren't, and that's like the only demarcation that matters?

• 1:15:34Speaker 00

  Um, I, yeah, I think Deutsch is like, he's like incredibly optimistic and also incredibly categorical in his thinking, right? You know, I don't know anyone else who was sort of as optimistic or, you know, and hardly anyone else who was as black and white, right? I mean, I, um, you know, it, it, it, it, it does seem likely that there is some kind of threshold that you cross in going from a chimpanzee to a human, right? Where like, yes, you know, a chimpanzee is smarter than a cow, right? But like, you know, if you stare at both of them, you know, it doesn't seem like, you

• 1:16:18Speaker 00

  know, the chimpanzee is noticeably closer than the cow is to, you know, being able to land on the moon, right? Or, or, or, um, um, proof from Osmo's theorem, right? Or, or, or any of these things, right? And, uh, uh, you know, with, with, um, um, um, humans, you know, you, you had like a, in, in, in succession, you had, you know, a few, you know, extremely important milestones that, you know, that had not been crossed before in the, in the animal kingdom, right? You have a universality of, of, of language, right? You, you know, I mean, the, the ability to have a recursive language that can sort of,

• 1:16:59Speaker 00

  um, um, you know, express thoughts of, you know, a, a, a unbounded complexity. You had, you know, the, the invention of, of, of writing, you know, the ability to transmit those thoughts across generations. You know, the, the, you know, a number system that could refer to arbitrarily large numbers, you know, and then, you know, computers, you know, which are, which are universal machines, right, the ability to build these kinds of machines and, you know, and all of this went along with, you know, being able to explain the world around us

• 1:17:39Speaker 00

  in, you know, in, in, you know, in explicit theories, you know, to, you know, to an, to an extent that no animal species, no other animal species was ever able to do. Having said that, you know, I don't, I don't actually know if people are, are, are universal explainers. That is, you know, I, I, I have, you know, I, I, I have no idea if we can explain everything or even if we can explain everything that is explainable. You know, I, of course, I, I hope that we will continue being able to explain a lot

• 1:18:22Speaker 00

  more than, than we can explain right now, right? But I mean, you know, Deutsch, you know, uses words in unusual ways, like the, like, like when he, he, he talks about why he is so optimistic, you know, part of his optimism is like, you know, when he uses the word people, he also includes extraterrestrials, right? So he does like, oh yeah, you know, it's possible that humans on earth will just all kill themselves out, you know, there will be a nuclear war or an environmental catastrophe, but that's not a big deal because people in the broader sense of, you know, life elsewhere in the universe will, will go and do all the amazing things anyway that we would have done.

• 1:19:05Speaker 00

  I mean, that, that may be called comfort to, to, to, to, to most of us here on earth, right? And so when he, when he says something like people are universal explainers, you know, you always have to press him on, you know, not only what does he mean by a universal explainer, but even what does he mean by people?

• 1:19:22Dwarkesh Patel?

  Right. His claim on the universal explainer part is that just as many worlds is the most parsimonious way to describe quantum mechanics, so you don't have to like postulate an arbitrary, you know, collapse. Since we have no reason to expect there's thing, since we have no proof that there are things we cannot explain, the most parsimonious explanation is that we can explain everything.

• 1:19:46Speaker 00

  Okay, I don't know. I mean, you know, there are, there are certain questions like, like the hard problem of consciousness, let's say, or a question, question of why is there a universe at all? Where, you know, it's not just that we don't have an explanation, it's that the, the mind sort of spins in circles when we try to contemplate what could possibly consist of an explanation, right? What, what, what, what, what could an explanation possibly look like, even in principle? Right? Uh, you know, that, that, that, that, that could just be a lack of imagination, right? But, you know, it could be that there are, you know, I mean, I mean, like, like we all know, you know, the two-year-old who just, you know,

• 1:20:31Speaker 00

  you, you know, asks why, and then you tell them, and they ask why, and you tell them, and you know, and then they ask why. And, you know, after, after, you know, a, a, a half dozen whys, you know, you're all the way back at the Big Bang, right? You know, you're, you're back at a, uh, you know, the, um, um, um, the, the beginning of the universe. And, you know, and they, they continue asking why, right? And, and, uh, it, it, it, it, it, it could be that, you know, there are, there are questions with, with the property that, you know, that every, um,

• 1:21:09Speaker 00

  so, okay, I mean, I mean, I mean, I mean, I mean, first of all, you know, I think even, even Deutsch thinks that, that we will not, you know, that there is no one time where we'll have an explanation of everything, right? Because, because Deutsch, you know, says that, that each, uh, each, each question that we answer will lead to further questions, right? You know, each, each time you explain something, uh, you know, there's, there's then the question of, you know, whatever the explanation is based on, you know, why is that, right? So just like that two-year-old, right, we can always dig deeper and deeper. Okay, but now, you know, just to, just to loop back to earlier in this conversation, like if we think about the busy beaver function, right, we know that, you know, it's not just that, um...

• 1:21:57Speaker 00

  You know, like with, with, with, uh, you know, you need more and more resources to, to compute more and more values of the busy beaver function. And so you'll never know all of them. It's that there are fixed values, like busy beaver of 800, right? Where the, the existing axioms of set theory, you know, provably will not suffice to let you determine that, right? And so likewise, for all I know, there could be fixed questions where, you know, may, maybe the hard problem of consciousness, maybe why is there a universe where what we currently consider to be an explanation just will not suffice to ever explain these things.

• 1:22:40Dwarkesh Patel?

  Right.

• 1:22:41Speaker 00

  But, but I, but I don't know, you know, uh, I feel like, um, unlike the way, you know, I don't want to assert that I know the answer from first principles. I, you know, I, I want to continue looking for explanations of these things. You know, it, it can be, when you're searching for explanations, you know, it can be psychologically helpful to, you know, assume that the explanation exists. But, you know, but, but, uh, let's, let's not make that into more than it is, right? Let's not take a, a useful heuristic and elevate it into a basic principle of reality.

• 1:23:19Dwarkesh Patel?

  Right. But on, on this point, um, Deutch wrote a book and called The Fabric of Reality where he talks about how Gödel's incompleteness theorem actually verifies the importance of creativity. So that if we need to come up with new axioms to prove busy beaver of 800, that's, that's the importance of creativity. And, um, as far as like, I, I think he thinks the hard problem of consciousness can be solved. But even if it can't be solved, like the reason it's so hard is not because, uh, it's not an artifact of our mind. It just seems like we can't imagine a possible mind. And that might, that might itself be an artifact of our mind. We can't imagine a possible way that you could solve it regardless of what kind of mind you had. The final question is, what advice would you give to a 20-year-old who is interested in technical subjects, but not, maybe he's not doing a PhD program like you were at the time, but just interested in technical subjects?

• 1:24:07Speaker 00

  Just learn all that you can. I mean, you know, there, there, you know, has never been a time when sort of more resources were available to anyone who wants to go to learn things. So, so, um, you know, take courses, talk to your professors, um, you know, go, go, go on the internet and, uh, you know, read, read, read books. Uh, you know, delve deeply into a, a subject and, um, uh, you know, and, and, uh, you know, you, you might be surprised at, uh, sort of how, how low the barriers sometimes are.

• 1:24:47Speaker 00

  Right. They're like, if you, you know, you know, let, let, let's say that it was quantum computing that you were interested in, right? It doesn't have to be. It could be anything else. But, you know, if you, you know, the entire literature of quantum computing, pretty much is available for free on, you know, on archive.org. And, uh, you know, if you go and like look every, every night at the new quantum computing papers that come out and just flag the ones that are interesting to you and read them. You know, each paper will raise new questions that, that the authors don't know the answer to or yet. Uh, and, you know, sometimes they'll be explicitly listed in an open problem section, you know, other times, you know, it'll be ones that you could think of.

• 1:25:32Speaker 00

  And, uh, you know, you can, um, uh, you know, you can study those problems, uh, you know, if you have ideas about them, you can, uh, you know, talk to, to the authors of the paper. And, uh, you know, you, you know, it, it, it, it might, you know, it might take, you know, years or decades to become, you know, an expert, like in a whole field. Uh, uh, you know, and you might be very far from that, but it really doesn't take that long to become the world expert on one particular tiny little problem. Right. And, um,

• 1:26:12Speaker 00

  You know, so, so try to, you know, become the world expert on, on something, you know, you know, even something very, very narrow, right? And, and, you know, once you've done that, then you can, you know, write an article about it, or, you know, do a, do a project about it, and then, you know, that will lead to more things, right? It will lead to, you know, maybe collaborations in the future, you know, and it will lead to, you know, you, you could then try to become an expert on something a little bit wider, something a little bit wider, and so on.

• 1:26:45Dwarkesh Patel?

  Yeah, that, that, that's very excellent advice. I love that. Okay, well, Professor, thank you so much for your time. Hey, if you enjoy this podcast, please consider sharing it with your friends and posting it on social media. Word of mouth is incredibly valuable for a new and a small podcast like this one. So, thanks for watching.