Scott Aaronson - Quantum Computing, Complexity, and Creativity

1. 0:00 – 0:33

   Intro

   1. SAScott Aaronson0:00

      You know, it might take, you know, years or decades to become, you know, an expert like in a whole field. Uh, 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, you know, so, so try to, you know, become the world expert on, on something, you know, you know, even something very, very narrow. (instrumental music plays)

2. 0:33 – 12:37

   Journey through high school and college

   1. SAScott Aaronson0:33

   2. DPDwarkesh Patel0:33

      So Professor Aaronson, can you tell us a bit about your early j- 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-

   3. SAScott Aaronson0:42

      Um-

   4. DPDwarkesh Patel0:42

      ... that?

   5. SAScott Aaronson0:43

      Yeah. Well, I, I didn't really graduate high school when I was 15. I got a GED, uh, from, from, from New York State. Uh, but, uh, I, um, I was not happy, uh, in, in high school for, for several reasons. I mean, uh, just, you know, socially, uh, academically, and I, I wanted to, uh, get out. And, uh, I mean, I, I had a, uh, I was in a weird situation because my, um, my... I went to, um, uh, public school, uh, in, in the US for, for, for junior high, and then... uh, in Pennsylvania actually. And then my parents, uh, uh, moved to Hong K- I, I lived in Hong Kong for one year-

   6. DPDwarkesh Patel1:30

      Mm.

   7. SAScott Aaronson1:30

      ... uh, because, uh, my, my, my dad was working there. And, uh, because of the, uh, uh, mish... Uh, I, I went to an American international school there, but because of a mismatch between the way, uh, they say- they did things in the US 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, the only way to deal with that was for me to skip a, a grade and skip, and, and, and go to the high school. And once, um, once, once I'd done that, that was, that was sort of a, uh... You know, something, something flipped for me, right? That, you know, I, I could actually do this. I could, uh, 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, uh, you know, and, and, and, and, and, and, and of course, you know, I, I, I somewhat, uh, uh, you know, had, had, had an idealistic view of what college was. But, you know, but a, a place where, where ideas would matter more than popularity, and, uh, 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. Um, and, and, you know, so then I went... I, I returned from Hong Kong to the US and was in, uh, 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, and then I, I ran out of math to take, right? I, I took the, uh, um, AP, 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, uh, do, do online learning, right? And do like, uh, differential equations or whatever with the..." You know, the, the Stanford has this EPGY program, right? 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, 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, um, you know, but it, it's, it's, uh, it's for high school students, right? Uh, so, uh, um, I said, you know, I... You know, you know, even knowing very little about this, I think, you know, I wanna, I wanna 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, 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, 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." (laughs)

   8. DPDwarkesh Patel4:51

      (laughs)

   9. SAScott Aaronson4:51

      Uh, and, um, so I, I, uh, 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, 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. So I, uh, I did that. Um, you know, I was, I was dis- 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, whi- which I didn't have. Uh, and so, so, we need to... We realized th- that I, I needed a, a GED from, you know... Well, well, okay, my, my, my old high school, you know, o- o- oftentimes, one's o- one's, one's old high school will just give you a diploma after you've gone through Clarkson. My high school would not do that because they said I was missing phys ed. I would have to s- you know, spend a summer doing phys ed. But, uh, um, uh, so, uh, you know, and, and then New York State said, uh, "Well, we can't give him a GED because you have to be 17 to have a GED, and he's 15." Um, and, and I... Ma- 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. I mean, I w- 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 they... The sort of, the, the main limitations were, were internal. They were, they were no longer external.

   10. DPDwarkesh Patel7:20

       Mm-hmm. Was, was it intimidating being in classes with people three or four years older than you?

   11. SAScott Aaronson7:24

       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 an, uh, you know, maybe a, a, an, an, an 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 10-year-old, right? I was, uh, you know, I mean, by the time I started at Cornell, I was 16 by then. And, um, um, you know, I, uh, um, uh, so, you know, I, I feel like, um, um, um, ac- um, academically, it was fine. I mean, you know, the main issue was, was social, right? Y- you know, and my, my parents had... you know, had warned me that, okay, you know, if to, uh, skip grades is going to completely screw up my social life, and, uh, you know, it's going to make dating, you know, uh, uh, 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?

   12. DPDwarkesh Patel8:29

       (laughs)

   13. SAScott Aaronson8:29

       I got, I got my, uh, PhD, uh, bef- basically before, uh, 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. Uh, but, um, so, you know, I, I did things in a weird order, you could say. And, and, and, and, and that did cause, you know, an enor- enormous amount of, of stress for me. But, but my main argument was that, uh, you know, I was already socially unhappy in, in high school, right? I was... I wa- I wa- I was already-

   14. DPDwarkesh Patel9:03

       Mm-hmm.

   15. SAScott Aaronson9:04

       ... 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-

   16. DPDwarkesh Patel9:18

       Mm-hmm.

   17. SAScott Aaronson9:18

       ... academics could be better.

   18. DPDwarkesh Patel9:21

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

   19. SAScott Aaronson9:28

       Well, I mean, I, I, I don't get to rerun my life multiple times and, uh, and, and compare. Uh, um, but I, I, I think that, um, um, mai- you know, mainly I'm, I'm, I'm grateful that I had the opportunity to, uh, you know, to sort of, uh, learn about stuff that, that, that, that, that, that interested me, right? And, and it was not... It was not just, you know, that, you know, 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, uh, plenty of humanities in, in, in college, right? And, uh, uh, but, you know, I, I, I wanted to, uh, 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- uh, humanities means, uh, you know, uh, 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, uh, theoretical, right? (laughs) Uh, and, um, you know, so even, even, even the humanities, right? I was a lot happier with in college than I was in high school. Uh, 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, uh, 16 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, 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 teenager-hood, right? That, like, people are, are, you know, from the age of 12 to 18, or now maybe even 20 or so, are still basically children, right? I think that that's largely a modern construction, right?

   20. DPDwarkesh Patel11:40

       Yeah.

   21. SAScott Aaronson11:40

       If you go back even a few hundred years, you know, by the time someone is a teenager, right? They're, they're an apprentice, right? They can work, you know, uh, uh... you know, they can be learning while they're also, you know, working, or 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. I think... you know, I mean, you know, I may... you know, unusual in some respects, but, but not in, in, in wanting to sort of get started with life-When-

   22. DPDwarkesh Patel12:13

       Mm-hmm.

   23. SAScott Aaronson12:13

       ... I, you know, I was 15 or 16.

   24. DPDwarkesh Patel12:16

       Yeah. I, I had Tyler Cowen on the podcast, and he started, um, th- th-

   25. SAScott Aaronson12:19

       Mm-hmm.

   26. DPDwarkesh Patel12:19

       ... he knew he wanted to be a economics professor basically in his early teens, and he was reading and preparing for that-

   27. SAScott Aaronson12:24

       Mm-hmm.

   28. DPDwarkesh Patel12:24

       ... um, from that time on.

   29. SAScott Aaronson12:26

       Economics professor is not what, you know, one often thinks of as, like, a, a child, you know, or an adolescent realizing that they want, but that is the, that, that, that, that, uh, uh, for, for, uh, in, in the case of Tyler Cowen, I could

3. 12:37 – 19:15

   Early work

   1. SAScott Aaronson12:37

      easily believe that.

   2. DPDwarkesh Patel12:38

      Is, is there some special advantage of learning the fundamentals of the field you know you're gonna go into early on? So instead of... Exe- 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?

   3. SAScott Aaronson12:51

      You know, I'm not sure. Uh, it, it's a, it's a very interesting question. I mean, you know, one, one, one could imagine that, you know, while someone's brain is still developing, right, that it's, it's going to be exposed to, uh, uh, certain things at, at that age. And, you know, I mean, I mean, like, we, we, we, we, we know examples that are like this, right? Like, uh, you know, an, an obvious one would be learning languages, right, where, you know, there, there, there's a window where, you know, children can just soak up languages, you know, like a sponge. And, you know, after that window, uh, okay, one, 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, as a, as a native five-year-old will speak it, right? (laughs)

   4. DPDwarkesh Patel13:34

      Yeah.

   5. SAScott Aaronson13:34

      Uh, so, um, so it, it, it, it could be like that, but it, it could also be that, uh, you know, like, our, our, our, our, our, our, our brains are not, uh, really a- adapted for, for learning any of this stuff, right?

   6. DPDwarkesh Patel13:50

      (laughs)

   7. SAScott Aaronson13:50

      I mean, like, well, you know, uh, uh, when we get to, you know, theoretical physics, theoretical computer science and, and so on, right, you know, all of it is, is, uh, is, is like, you know, learning a, a language that we don't natively speak, right? And, and on, on that, on that model, it would just be a, a question of getting a head start of, of, you know, of how much time you have to spend on it. Uh, I would, I would love for someone to research that question because I, I, I don't know the answer.

   8. DPDwarkesh Patel14:18

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

   9. SAScott Aaronson14:30

      Yeah.

   10. DPDwarkesh Patel14:30

       ... contributions early on.

   11. SAScott Aaronson14:31

       Yeah, but, but that's not just quantum mechanics. I mean, that's, uh, uh, all over, you know, math and, and, and physics, right? There are... I mean, I mean, I mean, Newton was, uh, you know, about 22-

   12. DPDwarkesh Patel14:42

       Mm-hmm.

   13. SAScott Aaronson14:42

       ... right, when he, uh, you know, had his miracle year, uh, you know, of, uh, uh, inventing calculus, you know, discovering the laws of mechanics. Um, yeah, I mean, no. I mean, I mean, you know, by, uh, I'm, I'm, I'm already old by the standards-

   14. DPDwarkesh Patel14:56

       (laughs)

   15. SAScott Aaronson14:57

       ... of math and physics, right, uh, you know. The, uh, um, uh, well, you know, which is, uh, which, which is weird to think about. But, um, uh, but, you know, there, there are, there are also many examples of, of, you know, great contributions that were made by people in their 40s, their 50s, their 60s, right?

   16. DPDwarkesh Patel15:16

       Mm-hmm.

   17. SAScott Aaronson15:16

       So, so, you know, so that, so that, that, that's, that's another empirical question that I wonder about, right? That i- i- 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? I mean, like, I got... In my case, you know, ha- having two kids, you know, get, clearly given me enormously less time for research, right? And, you know, when a- 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 sudden... You know, it feels a lot like it did when I was in my 20s, right? It, uh... And so, um, you know, uh, yeah, and, and, and, and then, and then th- 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, uh, goals for my life were wrapped up in, you know, succeeding in research, you know, and, and, uh, 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, uh, to worry about, you know, my, uh, my post-docs, 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's, that's certainly possible, right? But, you know, it's hard to disentangle from those other factors.

   18. DPDwarkesh Patel16:58

       Yeah. You're, you're the third person, uh, and I promise we'll get to the technical questions eventually-

   19. SAScott Aaronson17:02

       Mm-hmm.

   20. DPDwarkesh Patel17:02

       ... but you're, you're the third person I'm about, uh, on the podcast I'm about to ask this question because it fascinates me.

   21. SAScott Aaronson17:06

       Hm. Hm.

   22. DPDwarkesh Patel17:06

       Miracle years, as you mentioned, it, it's not just that, you know, people make, like, very important discoveries at young ages-

   23. SAScott Aaronson17:11

       Mm-hmm, mm-hmm.

   24. DPDwarkesh Patel17:12

       ... but they make lots of seemingly uncorrelated important discoveries at young ages. So as you know-

   25. SAScott Aaronson17:17

       Mm-hmm.

   26. DPDwarkesh Patel17:17

       ... like, uh, Einstein did, um, Brownian motion, um, uh, special relativity, what, what was the third one?

   27. SAScott Aaronson17:23

       Yeah. Uh-

   28. DPDwarkesh Patel17:23

       The, there were two or three more.

   29. SAScott Aaronson17:25

       Well, well, uh, there was the photoelectric effect.

   30. DPDwarkesh Patel17:27

       Yeah, that's right. Uh, and these don't seem e- uh, superficially at least, to be related, and yet they-
4. 19:15 – 33:30

   Why quantum computing took so long

   1. SAScott Aaronson19:15

      them. Yeah.

   2. DPDwarkesh Patel19:15

      I'm glad- I'm glad you brought up, uh, the topic of, like, eh, ideas being in the air and ready to pluck.

   3. SAScott Aaronson19:21

      Mm-hmm.

   4. DPDwarkesh Patel19:21

      Uh, 'cause this is- this leads me directly to the next question. I was, uh, rereading the lecture notes from your Quantum Information Science class, and there's the lecture on quantum teleportation, and you were answering, how is it- wha- 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-

   5. SAScott Aaronson19:42

      Yeah.

   6. DPDwarkesh Patel19:42

      ... quantum computing, uh, I- I'm- I'm a big fan of David Deutsch, and he discovered it- or he thought of it in the '80s.

   7. SAScott Aaronson19:49

      Mm-hmm.

   8. DPDwarkesh Patel19:49

      Um, it seems like these ideas were ready to pluck, you know, back when quantum mechanics was, uh, developed. Why did it take-

   9. SAScott Aaronson19:56

      Mm-hmm.

   10. DPDwarkesh Patel19:56

       ... so long to have these ideas plucked?

   11. SAScott Aaronson19:58

       Yeah, that's a- that's a- that's an extremely interesting question. Um, I- I- I mean, you know, the- the- the- the whole idea of- of thinking about quantum entanglement, you know, and not as something like metaphysically weird or- or s- you know, uh, uh, spooky or- or basically, how do we explain this away? How do we get rid of this? But in terms of how do we use it, right? How do we use it for, you know, to improve, uh, uh, information processing, right? I think that- that's- that's a point of view that, uh, uh, as far as I know, really only started with, uh, with John Bell in the 1960s, right? With, uh, you know, Bell having this remarkable insight, uh, that- that, you know, you could- you could te- you could do this, uh, uh, experiment to test the prediction of entanglement and- and distinguish it from any possible theory involving, you know, local hidden variables, right? And, uh, um, you know, and- and then, um, a little bit later, uh, Stephen Wiesner, you know, had the idea of, uh, um, uh, quantum money, right? Or using the uncertainty principle for cryptography, although he was, again, he was not able to publish that until the '80s. Uh, and, you know, there are- there are a few things that I could say here. I mean, um, um, one is that when- when quantum mechanics was discovered in the- in the '20s, 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, one- one- one has to improve on it, right? And then, I mean, that was very much Einstein's point of view, and- and- and I think also Schrodinger's. 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, um, but- but- but sort of not, um, you know, they- they 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- in which, you know, Einstein was the more right one in 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?

   12. DPDwarkesh Patel22:56

       Mm-hmm.

   13. SAScott Aaronson22:56

       And, you know, indeed, you know, that... I'm sorry. Uh, and, you know, indeed- indeed, that- that- that- that thing would not be understood r- really until- until the discovery of the Bell inequality in the '60s. The other, um, you know, issue is that when quantum mechanics was- was discovered into the- 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 world around us, right? The... And, uh, and- and you could say on- on the other side, in computer science, you know, the wh- I mean, for God's sakes, the entire notion of a universal computer was just being born then, right? The whole no- 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, uh, you know, it was, it- it... You know, it might have seemed wildly premature to anyone to- to combine the two, right? And then, uh, of course, World- World War II, you know, intervened, uh, uh, with, you know, um, um, you know, and- and, uh, uh, the people who were doing fundamental science, a lot of them went to work, you know, either at the Manhattan Project or Bletchley Park. And, uh, you know, and then after that, I mean, I- I think the theoretical physicists were very, uh, uh, uh, focused on just, you know, this d- 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, uh, um, um, you know, people were, were finally, you know, uh, building, uh, uh, commercializing, figuring out the uses for classical computers. That was a, you know, uh, 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 now, you know, if, 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, uh, uh, one of the, the great, uh, uh, uh, um, pioneers of both of computer science and of quantum mechanics.

   14. DPDwarkesh Patel25:34

       (laughs)

   15. SAScott Aaronson25:35

       Right? In fact, you know, he invented the, uh, notion of entropy of quantum states.

   16. DPDwarkesh Patel25:40

       Mm-hmm.

   17. SAScott Aaronson25:41

       You know, and, uh, 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 '50s, right? I mean, you know, Alan Turing was also, you know, of course a, a, a, you know, founder of computer science, who was also, uh, passionately interested in the foundations of quantum mechanics, you know, as we know from his, his letters, uh, to his friends. Uh, you know, he, uh, he, he died when he was 42.

   18. DPDwarkesh Patel26:08

       Right.

   19. SAScott Aaronson26:09

       Right? Uh, so, so, you know, w- w- w- wha- wha- whatever the case, you know, I, I feel like quantum mechanics and the theory of computing were both in place by the 1930s, 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 '60s. Computational complexity, that only starts in the '60s and '70s. And then, you know, maybe a decade after that, people start thinking about quantum computation.

   20. DPDwarkesh Patel26:40

       Interesting. Um, I've heard two other theories, and, uh, I wanna see how, what you think of them.

   21. SAScott Aaronson26:44

       Yeah, all right.

   22. DPDwarkesh Patel26:44

       Sure, sure. 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.

   23. SAScott Aaronson26:54

       Mm-hmm.

   24. DPDwarkesh Patel26:54

       And because people before him hadn't taken many-worlds-

   25. SAScott Aaronson26:56

       Mm-hmm.

   26. DPDwarkesh Patel26:56

       ... world seriously, they hadn't been able to do quantum computing.

   27. SAScott Aaronson26:58

       Yeah.

   28. DPDwarkesh Patel26:59

       And the second... Sorry, go ahead.

   29. SAScott Aaronson27:00

       Go on. Go on. Okay.

   30. DPDwarkesh Patel27:01

       I-
5. 33:30 – 38:18

   Contributions from outside academia

   1. SAScott Aaronson33:30

      actually going to be revolutionary.

   2. DPDwarkesh Patel33:32

      I, I'm sure your comment section and email fills up with these. But, uh-

   3. SAScott Aaronson33:35

      Yeah. (laughs)

   4. DPDwarkesh Patel33:35

      ... have, have you, um... How, how many of the important ideas, or do many important ideas in the field come from people outside academia? Or is it mostly people with PhDs working within the system?

   5. SAScott Aaronson33:46

      Uh, well, okay, I mean, I mean those are, those are not, uh, uh, uh, e- exhaustive categories, right? Because, you know, there, there are, um, you know, there, there are, there are, there have been, uh, breakthroughs that have come from people who were not in academia. Um, uh, 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, uh, they did part of a PhD or, or, or, or things like that, right? There was a, uh, um, famous case of Yitang Zhang, who was this mathematician from, from China, right? Who, uh, uh, um, proved that, that there are infinitely many pairs of primes at most 70 million apart, right? Uh, which was, you know, a m- 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.

   6. DPDwarkesh Patel34:52

      Huh. Wow.

   7. SAScott Aaronson34:53

      Uh, you know, just, you know, in order to, like, support his family and, and, you know, work, uh, uh, uh 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 mean, uh, you know, I- I- I hear all of the time from, you know, people who are, who are, like, complete, uh, uh, autodidacts, you know, who, uh, you know, taught themselves, yes, and, and, you know, that they think that they've solved the P versus NP problem or whatever, right? I- I've, uh, uh, um... You know, that, that is, uh, uh, um... you know, that, that, that is usually someone who just doesn't understand the question, who has just made some, you know, uh, uh, uh, um... you know, and, and, and, and, and then, and then, you know, I mean, there, there is a, a distinction because some- sometimes people, you know, uh, uh, who sort of teach themselves the field, they just, you know, they, they really want to learn. They just want an expert 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, uh, you know, I had a... When, when, when I taught at MIT, I had p- you know, someone, uh, uh, like writing to the president of MIT-

   8. DPDwarkesh Patel36:16

      (laughs)

   9. SAScott Aaronson36:16

      ... 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, you know, 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, uh, proof of P equals NP, uh, 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 other thing you- you find is, uh, uh, you know, there are, you know... And, and, and 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, uh, because, you know, I posted this survey article about the busy beaver function, uh, on my blog recently, and, uh, uh, you know, there was a, um, um, you know, I guess, a, a, a hobbyist who, who solved some of the open problems-

   10. DPDwarkesh Patel37:36

       Really?

   11. SAScott Aaronson37:36

       ... that were on that 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 now.

   12. DPDwarkesh Patel37:43

       Oh, cool. Interesting.

   13. SAScott Aaronson37:44

       Yeah.

   14. DPDwarkesh Patel37:44

       And by the way, is that Chong the same one that, uh, co-authored the Nielsen textbook on quantum information?

   15. SAScott Aaronson37:49

       No, no, no. No, no. There- there's a- a- a Yitang Zhang, and then there's, uh, uh, it was the mathematician, and then Isaac Chuang-

   16. DPDwarkesh Patel37:56

       Oh, okay.

   17. SAScott Aaronson37:57

       ... is the, uh, is the physicist who co-authored the Nielsen-Chuang textbook.

   18. DPDwarkesh Patel38:00

       Okay, got it. Momenous, I think. Um, so let me ask you about busy beaver. Um, I- I was-

   19. SAScott Aaronson38:05

       Sure. (laughs)

   20. DPDwarkesh Patel38:05

       Is- the- proposition three was that, uh, you can't-

   21. SAScott Aaronson38:10

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

   22. DPDwarkesh Patel38:13

       Okay. Uh, well, can you actually just explain what the busy beaver function is before I ask any questions?

   23. SAScott Aaronson38:17

       Yeah.

6. 38:18 – 53:50

   Busy beaver function

   1. SAScott Aaronson38:18

      Sh- okay, sure. So- so the busy beaver function is a really, really remarkable, uh, uh, uh, sequence of hyper-rapidly growing, uh, integers. And the way that, uh, we, we define it, uh, you know, it was, it w- it was, it was invented in 1962 by a mathematician named Tibor Radó. And, uh, and- and- and basically what we do is, um... Well, what we, what- what- what- what we would like to say... Well, let me, let me start with what we'd like to say. We'd like to say, you know, the, um, uh, 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 that can be named using a thousand words or fewer, okay? (laughs) Or something like that, right? And- but then, uh, I have to be careful because there's an inherent paradox there, right? Which is like 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, uh, um, so, so- so- so from this, you know, the, the, the, uh, conclusion that, uh, you know, logicians, philosophers drew more than 100 years ago is that the concept of naming a number, you know, in English is not as clear as we think it is, right? It, it, it leads to paradox if you're, if you're not careful about it. Uh, but- but, uh, uh, but- but what- what- what if we could, uh, name a number in a way that was completely unambiguous? Uh, well, you know, since the, since Alan Turing in the 1930s, we've had such a way. That way is computer programs, 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- in length. Okay. And, uh, you know, now you have to be careful. What do you mean by, by that, right? Because of course, a computer program could run forever, right? It could start just... It, you know... I could, we could easily write a program that says, "Do print non- print nine loop." Right? And then we just print an infinite sequence of nines. So what we do is we restrict attention to those computer programs that eventually halt, right? We say among... L- l- let's say, for a given end, we consider all of the possible computer programs that are n bits long, and say there are two to the n power of them, or at most two to the n power, right? Many strings will just, uh, uh, lead to, to things that are not even programs, you know, they won't even compile. So we'll, 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, and that number of steps, that is what we call the n-th busy beaver number.

   2. DPDwarkesh Patel41:33

      Mm-hmm. Yeah.

   3. SAScott Aaronson41:34

      Right? So, uh, uh, so, so, so the way that Radó 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 end state Turing machine can run for, okay? And, uh, uh, the- so, so, so, you know, the, the, the amazing thing is one can prove that this function grows faster than any computable function. Okay? So, uh, uh, so, you know, no matter what, uh, uh, uh, sequence of integers, you know, you can, uh... You know, b- b- b- basically, uh, uh, uh, if- if you are- are in a contest to name, uh, name the largest number, and if you say busy beaver of a thousand, then you will utterly destroy any opponent who doesn't know about the busy beaver function or about anything similar to it. Okay? So, um, eh, you know, so one, one can say further remarkable things about this function, like that, you know, only a finite number of values of the function can actually, uh, uh, be proven, uh, from the axioms of set theory.Right, for reasons of Gödel's incompleteness theorem, basically. Uh, uh, after a certain finite point, you know, the, the values of this function, you know, we, we can, we, well, you know- presumably, it has definite values, right, 'cause 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? That busy beaver of one is one, busy beaver of two is six, busy beaver of three is 21, and busy beaver of four is, uh, 107. Busy beaver of five, it is only known that it's at least 47 million.

   4. DPDwarkesh Patel43:38

      (laughs)

   5. SAScott Aaronson43:38

      Okay? You know, and we, we don't know how much bigger it might be. Busy beaver of six, uh, it's at least, I think about 10 to the 36,000. Okay? Might be much bigger. Busy beaver of seven, uh, 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, of how this function grows.

   6. DPDwarkesh Patel44:03

      Yeah. Yeah. And, uh, uh, by the way, I recommend everybody who's listening to, uh, check out the busy beaver frontier paper 'cause it was written in such a way that I, I also wanna ask you how you, uh, learned to write so well. It was written in such a way so that a non-expert like me could understand it. And, um, just to clarify from my own understanding-

   7. SAScott Aaronson44:18

      Mm-hmm. Mm-hmm.

   8. DPDwarkesh Patel44:18

      ... it's not that, uh, busy, for, uh, there isn't a function that for any n is greater than busy beaver of n. It's just that-

   9. SAScott Aaronson44:26

      Well-

   10. DPDwarkesh Patel44:26

       ... it, it won't, uh, busy beaver will eventually bec- with more states than, uh, if you have ƒ in x is that function, it will grow quite bigger.

   11. SAScott Aaronson44:33

       That's right. I mean, that, well, that, that, that, that's exactly what I meant when I said grows faster though, right?

   12. DPDwarkesh Patel44:37

       Right. Yeah.

   13. SAScott Aaronson44:37

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

   14. DPDwarkesh Patel44:42

       Yeah.

   15. SAScott Aaronson44:43

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

   16. DPDwarkesh Patel44:56

       Right. And-

   17. SAScott Aaronson44:58

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

   18. DPDwarkesh Patel45:01

       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. Um-

   19. SAScott Aaronson45:08

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

   20. DPDwarkesh Patel45:37

       Right. Okay. Uh, so my que- the, the proposition three was the one that said, um-

   21. SAScott Aaronson45:42

       Okay.

   22. DPDwarkesh Patel45:43

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

   23. SAScott Aaronson45:46

       Right.

   24. DPDwarkesh Patel45:47

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

   25. SAScott Aaronson46:04

       Uh, that's a, that's a, that's a wonderful question. Uh, um, you know, we, we, I, 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? (laughs) Uh, I mean, now, now, now, my, my guess would be that the, the, the, the resources of, of s- you know, existing set theory are, are, are perfectly enough to do that, right? But, but, you know, we don't even know that, right? So I, so four years ago, uh, uh, a, um, uh, a student of mine, uh, named, uh, Adam Yedidia and I, uh, decided to, uh, you know, look into a question that for some reason no one had looked at before, which was, uh, uh, uh, you know, like, what is the smallest n for which we can actually prove (computer notification sound) 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-

   26. DPDwarkesh Patel47:00

       Mm-hmm.

   27. SAScott Aaronson47:00

       ... but are we talking about 10 million or are we talking about 10, right? (laughs) So, uh, so, so in, in practice, what this problem boils down to is, is, is almost like software engineering. Like, you have to construct a Turing machine that, uh, 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.

   28. DPDwarkesh Patel47:30

       Mm-hmm.

   29. SAScott Aaronson47:30

       Okay? If you can build such a machine with only, uh, n states, then you've proven that the, uh, uh, that set theory cannot determine the value of busy beaver of n 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? (laughs) And, you know, a lot of coding and, and, and so- and, and engineering and, and new- and, and ideas, right? Uh, since then, uh, uh, again, a, uh, again, a, a, a, a hobbyist, to come back to your earlier question, someone outside o- a- academia by the name of Stephan O'Rear, uh, has managed to improve our bound and got it to under 800 states.

   30. DPDwarkesh Patel48:23

       Yeah.
7. 53:50 – 1:02:24

   New quantum algorithms

   1. DPDwarkesh Patel54:40

      to

   2. SAScott Aaronson55:28

      And, uh, you know, and, 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, 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, uh, on our part, or is it... You know, I mean, I, the, the wh-, you know, an- another, uh, possibility, uh, 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 classical CS. One of them is dynamic programming-

   3. DPDwarkesh Patel56:16

      Mm-hmm.

   4. SAScott Aaronson56:16

      Like, uh, 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, uh, greedy algorithms, uh, you know, uh, uh, convex programming, you know, linear programming-

   5. DPDwarkesh Patel56:36

      Right.

   6. SAScott Aaronson56:36

      Uh, you know, uh, um, um, Gaussian elimination, right? Uh, and, you know, and, and, and most of the, you know, uh, I mean, the field of classical algorithms is enormous, and yet, you know, most of the classical algorithms that we know are somehow built up out of these motifs that are dis- that were discovered very early on, right?

   7. DPDwarkesh Patel56:59

      Mm-hmm.

   8. SAScott Aaronson56:59

      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-

   9. DPDwarkesh Patel57:32

      Mm-hmm.

   10. SAScott Aaronson57:32

       ... design motifs of the world of quantum algorithms.

   11. DPDwarkesh Patel57:36

       I see.

   12. SAScott Aaronson57:36

       And then, you know, it's not, it's not surprising that they were discovered very early on, just like dynamic programming was discovered, you know, right at the beginning of the history of classical algorithms.

   13. DPDwarkesh Patel57:46

       Mm-hmm.

   14. SAScott Aaronson57:46

       So, um, uh, you know, so, you know, I mean, I mean that's, that, 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'll say 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, 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? 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 what 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 could then tell them for that problem, you know, exactly what is the current situation and, you know, uh, wh- 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 this designing an algorithm for, you know, uh, 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 any, you know, in any given area of math or science, right? 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 jump, have to leap higher, you know, if we want to, uh, 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? (laughs) 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 that they can experiment with, will help stimulate the discovery of those, you know, new problems or new applications.

   15. DPDwarkesh Patel1:00:48

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

   16. SAScott Aaronson1:00:56

       Uh, yeah, so, so it, it is, um, uh, uh, you know, like 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, uh, there's 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? 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. Uh, and, you know, there is some evidence that there might be a quantum algorithm that would take n to the 3/2ths time, or something like that. But, but if so, uh, uh, it has not yet been discovered.

   17. DPDwarkesh Patel1:02:11

       Mm.

   18. SAScott Aaronson1:02:12

       So, um, so, so, so, so, so there are cases like that. Um, um, no.

   19. DPDwarkesh Patel1:02:22

       Gotcha. Okay. Um,

8. 1:02:24 – 1:06:23

   Clusters

   1. DPDwarkesh Patel1:02:24

      I, 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, uh, uh, you said on Sean Carroll's podcast that, uh, uh, uh, Shor and Grover were collaborators at Bell Labs, and-

   2. SAScott Aaronson1:02:43

      Well, I, 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 Shor'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 Shor 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.

   3. DPDwarkesh Patel1:03:11

      Mm-hmm.

   4. SAScott Aaronson1:03:12

      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.

   5. DPDwarkesh Patel1:03:22

      Oh, okay.

   6. SAScott Aaronson1:03:22

      But, uh, um, I could, I could, I could, I could ask them that. But, uh-

   7. DPDwarkesh Patel1:03:26

      (laughs)

   8. SAScott Aaronson1:03:26

      ... uh, um, 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, uh, um, um, you know, the Shor's and Grover's algorithms were really, really at the tail end, right? Of, you know, the, the heyday of Bell Labs, right? Which was mostly the, uh, uh, uh, you know, the, uh, 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? Uh, from this, this one place. Um, uh, um, you know, another example, uh, uh, would be, um, um, you know, I mean, we, you know, we could take, um, Athens in the ancient world, right? We could take, uh, uh, Florence. Uh, we could, we could look at, uh, uh, uh, Cambridge University, right?

   9. DPDwarkesh Patel1:04:36

      Right.

   10. SAScott Aaronson1:04:36

       Let's say, you know, the, the, the turn of the 20th century, right? That had just so many mathematicians, economists, uh, philosophers, uh, physicists who, who revolutionized the world. Uh, now, uh, uh, you know, this might be because, you know, something about the environment, right? That, uh, uh, uh, uh, you know, that, that, uh, um, um, you know, i- 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, uh, they, they view it as a challenge, you know? They, they want to compete against that, uh, and come up with their own thing, right? You know, a, a, a, a, a Silicon Valley, where it's, you know, would be another good example, although more for technology than for science, right? Uh, uh, so that, that would, that would be one, one explanation. And a different explanation would be that, you know, these, these 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.

   11. DPDwarkesh Patel1:06:01

       Right. Correlation doesn't equal causation in this case.

   12. SAScott Aaronson1:06:04

       Mm-mm.

   13. DPDwarkesh Patel1:06:04

       Okay. All right. Uh, let me ask you now, I've interviewed a, a lot of economists on this podcast.

   14. SAScott Aaronson1:06:09

       Uh-huh.

   15. DPDwarkesh Patel1:06:09

       So I think this question will be interesting to the listeners.

   16. SAScott Aaronson1:06:11

       Uh-huh.

   17. DPDwarkesh Patel1:06:11

       In your, uh, paper on Why Philosophers Should Care About Complexity-

   18. SAScott Aaronson1:06:15

       Mm-hmm.

   19. DPDwarkesh Patel1:06:15

       ... um, you talk about how the difficulty in finding Nash equilibria might be relevant to discussions on economics. Can you explain, uh, can you explain this?

9. 1:06:23 – 1:13:26

   Complexity and economics

   1. DPDwarkesh Patel1:06:23

   2. SAScott Aaronson1:06:23

      Yeah. Okay. So, so there was a, uh, big advance in theoretical computer science, uh, 14 years ago when, uh, it, it was, uh, uh, uh, uh, uh, theoretical evidence was finally, uh, discovered for why computing a Nash equilibrium is a hard problem, basically. Uh, and, you know, and this, this, this, this confirmed a, a suspicion that people had had for a long time, right? Because, uh, you know, if we look at, uh, uh, uh, a von Neumann equilibrium, right, which is like an equilibrium of a, uh, um, let's say of, of a, of a two-player zero-sum game, right? Then, you know, this can be found easily, you know, using linear programming, okay? Um, but, uh, uh, a Nash equilibrium is somehow a more complicated beast, right? And, uh, uh, it's, you know, i- i- you know, the way that Nash proved that they exist in the '50s was, uh, using the, uh, what's called the Kakutani fixed-point theorem, right? It's, um, fixed-point theorem from, uh, topology. Uh, 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?Like, it, you know, it eventually hits the equilibrium, but it- it, you know, it- it, uh, it may have to follow an exponentially long trail before it reaches it. Uh, 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, okay. Uh, who, uh, and, um, and, um, Papadimitriou was one of the discoverers in the, uh, uh, uh, in 2006, uh, along with Goldberg and Daskalakis 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. Uh, this problem kind of doesn't have the right structure to be an NP complete problem, uh, just because of Nash's theorem that tells us that a Nash equilibrium always exists, right? Like, in order to be NP complete in any way that we currently under- understand, there has to, there has to be a decision problem, you know? Is- 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. Um, but what was shown is that basically finding a Nash equilibrium is at least as hard as any other problem, uh, for- for which, you know, a solution is guaranteed to exist because of the same kinds of principles.

   3. DPDwarkesh Patel1:09:07

      Okay.

   4. SAScott Aaronson1:09:07

      Okay? So, uh, so it sort of, it- it is complete for that complexity class of-

   5. DPDwarkesh Patel1:09:13

      Sure.

   6. SAScott Aaronson1:09:13

      ... 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?

   7. DPDwarkesh Patel1:09:22

      Yes.

   8. SAScott Aaronson1:09:22

      Well, it- it- it's not clear, right? Uh, if it has a sort of direct implication, but it, it sort of, it- it fits into this general narrative of, uh, 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? And so, uh, you know, now- now economists are- are well aware, right? That- that there are these issues, right? That- that, you know, uh, uh, uh, you know, people are not perfectly rational, you know, even if- even if they want to be perfectly rational, which they don't always. Uh, you know, being perfectly rational might involve computations that they're just not able to do, right? And- and- and, you know, and- 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- the, you know, Nash equilibria are so central to economic theory, right? That, you know, the hardness of finding Nash equilibria, I think, you know, is a, uh, um, you know, maybe- maybe a- a non-trivial result, you know, u- underscoring that- that general point.

   9. DPDwarkesh Patel1:10:45

      That- that- that's incredibly interesting. Um, but- but do you think, uh, Hayek's knowledge problem or the way he phrased it might be related to, uh, uh, complexity as well? So in terms of like, uh, central planning in order to satisfy some constraints-

   10. SAScott Aaronson1:10:57

       Yeah.

   11. DPDwarkesh Patel1:10:57

       ... set by bureaucrats might be like an NP complete problem where it's like-

   12. SAScott Aaronson1:11:00

       Well, I- I- I-

   13. DPDwarkesh Patel1:11:01

       ... you know, verified.

   14. SAScott Aaronson1:11:02

       ... I want, I want, I- I wanna separate two, uh, two different things, right? One is lack of knowledge, right? Uh, uh, about what is going on in the economy, so forth. And the other one is lack of ability to do computations on the knowledge that you have, right?

   15. DPDwarkesh Patel1:11:19

       Mm-hmm.

   16. SAScott Aaronson1:11:20

       So- so, you know, the- the- the hardness of Nash equilibria is talking about the latter issue.

   17. DPDwarkesh Patel1:11:26

       Yeah, I see what you're saying.

   18. SAScott Aaronson1:11:26

       I mean, you know, they're- they're- they're related in a way, right? They're both, you know, they're- they're- they're- they're both different kinds of deviations from perfect omniscience, right? But they're, but they're different kinds of deviations from- from omniscience.

   19. DPDwarkesh Patel1:11:41

       Okay.

   20. SAScott Aaronson1:11:41

       And, you know, in- in- in theoretical computer science, you know, very, very often we have to distinguish them. Uh, so, uh, um, you know, I mean, o- o- often, like people will ask me if some problem is, you know, is or isn't NP complete when, you know, what they, what they really mean is like, how hard is it to collect the information, right? Which is, you know, it's kind of like a apples and oranges. It's a- it's a category mistake, right? Once, you know, it's for- for like, to even talk about whether a problem is in P or is in NP or whatever, we assume that an input is given to you, right? 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, right? Uh, now there is, there is also, you know, the- the difficulty that, uh, uh, you know, people who are in, uh, uh, you know, um, um, economic actors, you know, don't, uh, uh, have the information that they need, or- or certainly central planners, you know, don't have the information that they need, right? And there's act- there actually is a whole subfield of economics, you know, that's the economics of information, right? How much do you pay to- to learn something about, you know, what is going on? Or how do you hold a- 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, that- that stuff has been better integrated into economics than the computational considerations have been.

   21. DPDwarkesh Patel1:13:23

       Okay. That- that's incredibly interesting. Um, I just, just a

10. 1:13:26 – 1:24:07

    Creativity

    1. DPDwarkesh Patel1:13:26

       few more questions. Um-

    2. SAScott Aaronson1:13:27

       Okay, sure.

    3. DPDwarkesh Patel1:13:28

       Yeah. I'm gonna bring us back to, um, uh, David Deutsch and creativity.

    4. SAScott Aaronson1:13:31

       Okay.

    5. DPDwarkesh Patel1:13:31

       Uh, in the Ask Me Anything chapter of Quantum Computing since Democritus.

    6. SAScott Aaronson1:13:35

       Yeah.

    7. DPDwarkesh Patel1:13:35

       Um, you have a student ask you, uh, what- what complexity class is creativity in? And you say, uh, uh, well, part of what you say is, um, "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 MP. Um, but if, that makes it kind of sound like we have more heuristics to solve these problems than chimpanzees do, chimpanzees have more than ants. Uh, 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? Uh, or is it, like, you- you just have better heuristics for searching through different (inaudible)

    8. SAScott Aaronson1:14:10

       I- I don't, I don't, I don't know that there is such a thing as the algorithm for creativity, right?

    9. DPDwarkesh Patel1:14:15

       Right.

    10. SAScott Aaronson1:14:15

        In fact, yeah, the, you know, it- it- uh, it- it- the- the phrase is almost oxymoronic, right? That if- if there were such an algorithm, well, then whatever it output would no longer be creative, would it-

    11. DPDwarkesh Patel1:14:26

        (laughs)

    12. SAScott Aaronson1:14:26

        ... because it would just be the output of that algorithm, right?

    13. DPDwarkesh Patel1:14:29

        Yeah.

    14. SAScott Aaronson1:14:30

        Uh, so, you know, I think that, uh, um, you know, the, uh, uh, uh, uh, 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 solutions to problems which, uh, you know, let's say, you know, uh, uh, Einstein had more of than some random person off the street, uh, but the random person off the street has more of than a chimpanzee, and a chimpanzee has more of than an ant. But it is somehow very, very hard to- to articulate what we mean by that, you know, in- in a way that would actually support these, you know, comparisons across, you know, vastly different evolutionary histories and- and goals in life and all- all these things.

    15. DPDwarkesh Patel1:15:20

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

    16. SAScott Aaronson1:15:34

        Um, I, yeah, I- I think, um, Deutsch is like, he's incr- uh, like, in- incredibly optimistic and also incredibly categorical in his thinking, right? (laughs) You know, I don't know anyone else who is sort of as optimistic or, you know, and- and hardly anyone else who is as black and white, right? Uh, I mean, I- I, um, uh, you know, it- 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, it, you know, a chimpanzee is smarter than a cow, right? But, like, you know, if you use stare at both of them, you know, it doesn't seem like, you know, the chimpanzee is noticeably closer than the cow is to, you know, being able to land on the moon, right? Or- or, uh, or- or, um, um, prove Fermat's Last Theorem, right? Or- or any of these things, right? And, uh, uh, you know, with- with, um, 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, uh, universality of- of- of language, right? You have, you know, I mean, the- the ability to have a- a recursive language that can sort of, uh, um, um, you know, uh, uh, express thoughts of, you know, uh, uh, unbounded complexity. Uh, you had, uh, you know, the- the- the invention of- of- of writing, you know, the ability to transmit those thoughts across generations. Uh, you know, the- the, uh, um, um, you know, a number system that could refer to- to arbitrarily large numbers, you know, and then, you know, uh, uh, uh, uh, computers, you know, which are, which are universal machines, right? The ability to, uh, uh, 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, uh, in, you know, in- in, uh, uh, you know, in- in explicit theories, you know, to, uh, uh, uh, you know, to an- to an extent that no animal species, no- no other animal species, uh, uh, was ever able to do. Um, 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- I have, um, you know, uh, uh, I- I- I have no idea if we can explain everything or even if we can explain everything that is explainable. Uh, you know, I- I, of course, I- I hope that we will continue being able to explain a lot more than- than we can explain right now, right? But I mean, you know, Deutsch, you know, uses words in unusual ways. Like, he, uh, um, like- like when he- he- he talks about why he is so optimistic, you know, part of his optimism is like w- you know, when he uses the word people, he also includes extraterrestrials, right? So he says 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 uh, go and do all of the amazing things anyway that we would have done." I mean, that- that may be cold comfort to, uh, 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?

    17. DPDwarkesh Patel1:19:24

        Right. Uh, his- his claim on the universal explainer part is that, um, just as many worlds is the most parsimonious way to describe quantum mechanics so you don't have to like postulate an arbitrary, uh, uh, you know, collapse.

    18. SAScott Aaronson1:19:38

        Yeah.

    19. DPDwarkesh Patel1:19:38

        Uh, since we have no reason to expect there's thing... Or since we have no proof that there are things we cannot explain, the most parsimonious explanation is that we can explain everything.

    20. SAScott Aaronson1:19:47

        Okay. Uh, I- I- I don't know. I mean, you know, there are...There, there are certain questions, like, like the hard problem of consciousness, let's say, or the ques- question of w- 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 explan- right? What, what, what, what, what, w- what could an explanation possibly look like even in principle, right? Uh, no, that, that, that, that, that, that could just be a lack of imagination, right? But, you know, i- i- i- it could be that th- there are, you know... I mean, I mean, like, like we all, we all know, you know, the two-year-old who just, you know, you, you, you know, asks why and then you tell them, and they ask why, and you tell them and, you know, and then, e- and, and they ask why. And, you know, after, after, you know, uh, uh, a, a half-dozen whys, you know, you're all the way back at the Big Bang, right? (laughs) You know, you're, you're back at a, uh, uh, you know, the, uh, um, um, um, uh, th- the, the beginning of the universe, and, you know, they, they continue asking why, right? And, and, uh, it, it, it, i- i- i- it, it could be that, you know, there are, there are questions with, with the property that, you know, that every, um, um, um... So, okay. I mean, I mean, I mean, I mean, I mean, I mean, first of all, you know, uh, 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?

    21. DPDwarkesh Patel1:21:21

        Mm-hmm.

    22. SAScott Aaronson1:21:21

        Because, because Deutsch, you know, says that, that each, uh, 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 w- 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, uh, um, uh, you know, like with, with, with, uh, uh, us, um, 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.

    23. DPDwarkesh Patel1:22:40

        Right.

    24. SAScott Aaronson1:22:40

        Um, but, but I, but I don't know. Uh, you know, uh, uh, I feel like I, um, um, um, unlike Deutsch, you know, I don't want to assert that I know the answer from first principles. I, you know, I, uh, I wanna continue looking for explanations of these things. Uh, 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. Uh, 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.

    25. DPDwarkesh Patel1:23:19

        Right. Uh, but on ju- uh, on this point, um, De- Deutsch wrote a book in, uh, called The Fabric of Reality where he talks about how Godel's incompleteness theorem actually, um, verifies the importance of creativity. So that if we need to come up with new axioms to prove a busy beaver of 800, that's-

    26. SAScott Aaronson1:23:33

        Mm-hmm.

    27. DPDwarkesh Patel1:23:34

        ... that's the entire point 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-

    28. SAScott Aaronson1:23:50

        Mm-hmm. Mm-hmm.

    29. DPDwarkesh Patel1:23:50

        We can't imagine a possible way that you could solve it regardless of what kind of minds you had.

    30. SAScott Aaronson1:23:54

        Yeah.
11. 1:24:07 – 1:26:45

    Advice to young people

    1. SAScott Aaronson1:24:07

       just, uh, learn all that you can. I mean, you know, there, there, uh, you know, has never been a time when sort of more resources were available to anyone who wants to, to, to learn things. So, so, uh, um, you know, take courses, talk to your professors. Um, um, you know, go g- go, go on the internet and, uh, or you know, re- re- read books. Uh, you know, delve deeply into a, a, a subject. And, um, uh, you know, and, and, and, uh, you know, you, you might be surprised at, uh, sort of how, how low the barriers sometimes are, right? Like, if you, you know, you know, let's, let's, 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, I, 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. 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. Um, 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, 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, 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, uh, you know, maybe collaborations in the future. Uh, you know, and it will lead to, you know, you, you can then try to become an expert on something a little bit wider and something a little bit wider and so on.

Episode duration: 1:27:05