Main Topic: The conversation revolves around the concept of expertise, the importance of specializing early, and the potential for discovering new quantum algorithms. The discussion also touches on the history of quantum mechanics and the development of quantum computing.
Key Points:
Participants:
Takeaways:
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”.
He was also my professor for a class on quantum computing.
Watch on YouTube. Listen on Apple Podcasts, Spotify, or any other podcast platform.
Episode website here.
Follow me on Twitter 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
Host
It might take years or decades to become an expert in a whole field, 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. So try to become the world expert on something, even something very, very narrow.
Professor Aronson, 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?
Scott Aaronson
Yeah, well, I didn't really graduate high school when I was 15. I got a GED from New York State. I was not happy in high school for several reasons, socially and academically, and I wanted to get out.
I was in a weird situation. I went to public school in the US for junior high in Pennsylvania. Then my parents moved to Hong Kong for a year because my dad was working there. I went to an American international school, but because of a mismatch between the way they did things in the US and in Hong Kong, I was not able to do math that was appropriate. I had always been sort of ahead in math. The only way to deal with that was for me to skip a grade and go to the high school. Once I had done that, something flipped for me. I realized I could actually do this. I could get out of this environment.
Where I really wanted to be was college. I had an idealistic view of what college was, but I wanted to be in a place where ideas would matter more than popularity, where you could choose what to study and advance at your own pace.
I returned from Hong Kong to the US and was in a public high school for a year. I didn't like it. I ran out of math to take. I took the AP Calculus. My parents suggested to the school that I do online learning through Stanford's EPGY program for differential equations. They said they would pay for it. The school said no.
I seized on that as my excuse. I had just seen a brochure for a place called the Clarkson School in upstate New York, which is part of Clarkson University. You can live there for a year and take college courses, but it's for high school students. I told my parents I wanted to give it a try. They allowed me to do that. We had the car packed up to drive there. When we were about to leave, a math teacher at my old high school who was very good and had been trying to advocate for me said he got it so I could take the EPGY program. We said, "Too late, sorry."
I went to Clarkson and generally had a very good experience. Socially, there were a lot of the same problems as high school, but at least I was able to take courses that were a lot more interesting. I was able to meet professors and get started doing research. The idea is that after a year at this Clarkson program, you apply to colleges as a freshman with a year of college credit.
I was very disappointed at the time because I got rejected from almost every college I applied to. I had a very weird background. I was lucky that Cornell and Carnegie Mellon were kind enough to accept me. I decided to go to Cornell, but there was one problem: they required a high school diploma before you could enroll. I didn't have one. We realized I needed a GED. My old high school would not give me a diploma because they said I was missing phys ed. I would have had to spend the summer doing phys ed. New York State said they couldn't give me a GED because you have to be 17 to have a GED, and I was 15. My mom eventually convinced them to make an exception and give me a GED. So then I went to Cornell.
I've met other people who were homeschooled who did things more radical than what I did. I was accelerated by three years, that was all. After I was in college, I didn't really accelerate anymore because I felt like I was in an environment where I wanted to be. From then on, the main limitations were internal. They were no longer external.
Host
Was it intimidating being in classes with people three or four years older than you?
Scott Aaronson
The truth is, I would say the majority of them didn't even know that I was younger. If they knew, it was an oddity a little bit, but they didn't care that much. It's not like I was a 10-year-old. By the time I started at Cornell, I was 16. Academically, it was fine. The main issue was social.
My parents had warned me that skipping grades was going to completely screw up my social life. They said it would make dating incredibly difficult. I brushed all of that aside. Of course, that all turned out to be true. I got my PhD basically before I learned how to drive or how to have any kind of a social life or dating life. I did things in a weird order, and that did cause an enormous amount of stress for me.
But my main argument was that I was already socially unhappy in high school. I was already miserable without having skipped grades. I felt like, as long as I'm going to be miserable socially anyway, at least I could be learning stuff. At least the academics could be better.
Host
As far as the academics go, what were the advantages and disadvantages of specializing so early?
Scott Aaronson
I don't get to rerun my life multiple times and compare. I think that mainly I'm grateful that I had the opportunity to learn about stuff that interested me. It was not just that I wanted to take only math and CS and nothing else. I took plenty of humanities in college. But I wanted to have some freedom to pick what to learn about.
In high school, humanities means the five paragraph essay. You basically have to regurgitate what the teacher wants from you. If you try to do your own thing and write things in your own way, you will actually fail. I learned this from experience. Even the humanities, I was a lot happier with in college than I was in high school. So it wasn't just a matter of specialization, but partly it was.
By the age of 16 or so, I knew what I was passionate about. It was the fundamentals of computing, understanding what computers could or couldn't do. I was ready to be learning about that and working on it.
The entire concept of teenagerhood, that people from the age of 12 to 18, or now maybe even 20, are still basically children, is largely a modern construction. If you go back even a few hundred years, by the time someone is a teenager, they're an apprentice. They can work and learn the trade that they choose. I think that's actually natural. I don't feel like I'm that unusual in that respect. Unusual in some respects, but not in wanting to get started with life when I was 15 or 16.
Host
I had Tyler Cowen on the podcast and he started wanting to be an economics professor basically in his early teens. He was reading and preparing for that from that time on. An economics professor is not what you often think of as a child or an adolescent realizing they want. But in the case of Tyler Cowen, I could easily believe that.
Is there some special advantage of learning the fundamentals of the field you're going to go into early on? Aside from the fact that you just get more years to accumulate knowledge, is there a special advantage of learning it in your early years?
Scott Aaronson
I'm not sure. It's a very interesting question. One could imagine that while someone's brain is still developing, it's good to be exposed to certain things at that age. We know examples like this. An obvious one would be learning languages. There's a window where children can just soak up languages like a sponge. After that window, you can learn a language, but it will be a difficult intellectual puzzle and you'll never speak it as well as a native five-year-old will speak it.
It could be like that. But it could also be that our brains are not really adapted for learning any of this stuff. When we get to theoretical physics, theoretical computer science, and so on, all of it is like learning a language that we don't natively speak. On that model, it would just be a question of getting a head start 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.
Host
As you know, many of the important discoveries in quantum mechanics were made by people who at the time were very young. That's an interesting fact. Not only did they learn that stuff early on, but they made those contributions early on.
Scott Aaronson
That's not just quantum mechanics. That's all over math and physics. Newton was about 22 when he had his miracle year of inventing calculus and discovering the laws of mechanics. I'm already old by the standards of math and physics, which is weird to think about.
But there are also many examples of great contributions that were made by people in their 40s, their 50s, their 60s. That's another empirical question that I wonder about. Is it that people's brains actually slow down as they get older, or is it simply that they have less motivation or less free time?
In my case, having two kids has clearly given me enormously less time for research. In those cases where I'm traveling, away from the kids for a week, I can work again, and it suddenly feels a lot like it did when I was in my 20s.
There's also the issue of motivation. When I was before I was established, my entire conception of myself, my entire goals for my life were wrapped up in succeeding in research, doing whatever it took. Now, I have all kinds of other concerns. I have my own students to worry about, my postdocs, my kids, my blog, the popular things I write. Research just feels like one more thing that I do. My identity is not as much wrapped up in it.
I may have also gotten dumber. That's certainly possible. But it's hard to disentangle from those other factors.
Host
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 people make very important discoveries at young ages, but they make lots of seemingly uncorrelated important discoveries at young ages. As you know, Einstein did Brownian motion, special relativity, and the photoelectric effect. These don't seem, superficially at least, to be related. Yet it's interesting to happen in the same year. What do you think explains that phenomenon?
Scott Aaronson
In the case of Einstein, you're asking me to explain Einstein's miracle year. That's a tall order. One can say certain things. Physics in the early 20th century was ripe for these interrelated revolutions of relativity and quantum mechanics. If it wasn't Einstein, it would have been someone else not long after with all of those things. General relativity, which took Einstein a decade longer, was the one thing where if it hadn't been for Einstein, it might have been decades before anyone else did that. But the stuff he did in 1905 were all things that physics was kind of ripe for. Maybe it took one person just looking at things in a sufficiently different way.
I'm not sure really. But also, the confluence of all of those things is part of why we think of Einstein as Einstein. There were many other great physicists around the same time who may have done one or two things of that caliber. But only Einstein does those three or four of them.
Host
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. 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 thought of it in the 80s. 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?
Scott Aaronson
That's an extremely interesting question. The whole idea of thinking about quantum entanglement not as something metaphysically weird or spooky, not as "how do we explain this away" or "how do we get rid of this," but in terms of "how do we use it" to improve information processing, is a point of view that, as far as I know, really only started with John Bell in the 1960s. Bell had this remarkable insight that you could do an experiment to test the prediction of entanglement and distinguish it from any possible theory involving local hidden variables. Then a little bit later, Stephen Wiesner had the idea of quantum money, using the uncertainty principle from cryptography, although he was not able to publish that until the 80s.
There are a few things I could say here. One is that when quantum mechanics was discovered in the 20s, it was not at all clear to the people who discovered it that this was a final form that the laws of physics would take. There was a large contingent that thought this is some scheme that represents our current knowledge, but one has to improve on it. That was very much Einstein's point of view, and I think also Schrodinger's. Bohr and Heisenberg were very much opposed to looking for something beyond quantum mechanics, but not in a way that was inspiring more research about what you could do with quantum mechanics. They just wanted everyone to shut up and stop asking about these things. Even though Bohr was right and Einstein was wrong on the issue of local hidden variables, there's a deeper sense in which Einstein was more right in putting his finger on something here that we do not yet understand and that we need to understand. That thing would not be understood really until the discovery of the Bell inequality in the 60s.
The other issue is that when quantum mechanics was discovered into the 30s, there was so much to do in terms of figuring out how chemistry works, just applying quantum mechanics to understanding the real world around us. On the other side in computer science, the entire notion of a universal computer was just being born. The whole field of classical computing was only just being born. There was so much on the plates of both sides that it might have seemed wildly premature to anyone to combine the two.
Then World War II intervened. The people who were doing fundamental science, a lot of them went to work either at the Manhattan Project or Bletchley Park. After that, the theoretical physicists were very focused on the zoo of new particles being discovered and formulating quantum field theory. It was very much out of fashion for decades to think about the fundamentals of quantum mechanics itself.
In the meantime, people were finally building, commercializing, and figuring out the uses for classical computers. That was a very young area itself. The entire theory of computational complexity, which is an intellectual prerequisite to quantum computing, only developed in the 1960s. The theory of P and NP and NP completeness was only the 1970s.
If we think about the people who could have combined these fields, I think of John von Neumann as an obvious possibility. He was one of the great pioneers of both computer science and quantum mechanics. In fact, he invented the notion of entropy of quantum states. But he had a lot of other things on his plate, and he died early in the 50s. Alan Turing was also a founder of computer science who was passionately interested in the foundations of quantum mechanics, as we know from his letters to his friends. He died when he was 42.
Whatever the case, 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. The idea of thinking of entanglement as a resource only starts in the 60s. Computational complexity only starts in the 60s and 70s. Maybe a decade after that, people start thinking about quantum computation.
Host
I've heard two other theories and I want to see what you think of them. The first one is, I think I might be misquoting him, but I think at some point David Deutsch said the reason he was able to think seriously about quantum computing was that he took the many worlds interpretation seriously. Because people before him hadn't taken many worlds seriously, they hadn't been able to do quantum computing.
Scott Aaronson
Sorry, go ahead.
Host
Maybe I should respond to that one first?
Scott Aaronson
Yeah, yeah.
Host
Okay.
Scott Aaronson
That is definitely true for Deutsch. I know Deutsch well. He became a big believer in the many worlds interpretation when he was here at UT Austin as a student. He heard Hugh Everett himself give a lecture about it. Bryce DeWitt, who was one of the main early proponents of the many worlds interpretation, was also here at UT Austin and had a big influence on Deutsch.
Deutsch was thinking about how would you make people realize that quantum mechanics is universally valid, that it applies at all scales. If you could build a computer that could do a superposition over different computations, and then you could see the results of interference between them, at that point, conceptually, it is almost like making a superposition over a brain that can think different thoughts. Then the whole idea that observers collapse the wave function just by being observers is no longer tenable.
One problem is that Richard Feynman had the idea of quantum computing around the same time as Deutsch did. Feynman was certainly aware of the many worlds interpretation, but that was not his motivation for thinking about quantum computing. He was much more practically focused. He was thinking about how do we simulate physics, how do we simulate nature with a computer. If we use classical computers, we suffer this exponential slowdown. Can we build a new kind of computer that will solve that problem and give us a universal quantum simulator?
There was also a whole movement in the 70s and 80s to think about the physics of computation, including the thermodynamics of computation. Can you make computation inherently reversible? That was also one of the intellectual streams that led directly to quantum computation.
I think that what you said is very much true for Deutsch. But there were others besides Deutsch who were thinking about these things. Feynman was only one. There were others as well, like Benioff. Few people in this field are as messianic as Deutsch is about the many worlds interpretation.
Host
It's interesting that both Deutsch and Turing were trying to solve a separate philosophical problem when they came up with their model of computation, at least in part.
Okay, the second theory I've heard is that since the 1970s, academia has been less open to new ideas. You mentioned Wiesner and Everett, and both of them I understand were kind of looked down on or ostracized. Is that theory confirmed?
Scott Aaronson
It is possible that in some parts of academia, it has become harder to explore new ideas than it once was. I could believe that about the social sciences. I could believe that about parts of medicine. People used to do completely crazy things, invent some new concoction, inject themselves with it, see what happens, write an article about it. Whereas today, it might take a billion dollars of investment before anyone would consider it remotely ethical to do such a thing.
On the other hand, in physics and speculation about the foundations of computing and cosmology, if anything, things have gone in the opposite direction. This is partly because we now have this preprint server, the arXiv, where everyone can post all of their new research ideas with no filter. I think that has somewhat transformed the scientific landscape. We still have journals, but journals are now just a final stamp of approval that is important when you're looking for jobs or things like that. Journals are no longer gatekeepers that can prevent people from seeing your paper.
If you just look at the quantum physics archive every day, you will see so many far out ideas. There is so much crazy stuff that it's very hard to believe that a modern day Wiesner or Everett would feel any barrier to getting their idea out there. Today, the problem is more that there are so many bold new ideas that most of them won't go anywhere. Most of them will fail. There's so much to sift through if you're looking for what is actually going to be revolutionary.
Host
I'm sure your comment section and email fills up with these. But 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?
Scott Aaronson
Those are not exhaustive categories. There have been breakthroughs that have come from people who were not in academia. Very often, what you find is that these are people who were on the margin of academia. They got a PhD, and then they left the academic world, or they did part of a PhD, or things like that.
There was a famous case of Yitang Zhang, who was this mathematician from China who proved that there are infinitely many pairs of primes at most 70 million apart. That was a major advance in number theory.
Host
And this was a guy who had gotten a PhD in math in China, I think, but then moved to the U.S. and then worked making sandwiches at Publix, just to support his family and work various other odd jobs, but continued working on math. So I hear all the time from people who are complete autodidacts who taught themselves, and they think that they've solved the P versus NP problem or whatever. That is usually someone who just doesn't understand the question, who has just made some mistake.
There is a distinction, because sometimes people who sort of teach themselves the field, they really want to learn. They just want an expert to talk to who will tell them, "Here's where you're on the right track, here's where you made a mistake," and they will thank you for that. Other times, you get people who really dig in their heels and say the establishment is censoring me. When I taught at MIT, I had someone writing to the president of MIT to try to get me fired. I had another one sending me death threats, very specific ones. I had to actually contact the police about them because I would not publish their proof of P equals NP or their refutation of quantum computing on my blog. So you get the whole spectrum.
But the other thing you find is that a lot of the readership of my blog comes from people who studied technical subjects in college, studied CS or math or physics, and then went out into industry. But they maintain this connection, maintain their curiosity about fundamental questions. Some of those people actually want to continue to do research. I'm actually co-authoring a paper with one of them right now. I posted this survey article about the busy beaver function on my blog recently, and there was a hobbyist who solved some of the open problems in the survey and had a lot of new ideas. He and I are going to write a paper about it now.
Oh, cool. Interesting. But by the way, is that the same one that co-authored the Nielsen textbook on quantum information?
Scott Aaronson
No, no, no. There's a Yitang Zhang, the mathematician, and then there's Isaac Chuang, the physicist who co-authored the Nielsen-Chuang text.
Host
Okay, got it. My mistake. So let me ask you about Busy Beaver. Proposition three was that you can't... I have no memory for the numbering of propositions.
Scott Aaronson
Okay.
Host
Can you actually just explain what the Busy Beaver function is before I ask these questions?
Scott Aaronson
Yes, okay, sure. So the Busy Beaver function is a really remarkable sequence of hyper-rapidly growing integers. It was invented in 1962 by a mathematician named Tibor Rado. Basically, what we would like to say is, if I want to name the biggest number that I could possibly think to define, why not just say the biggest number that can be named using a thousand words or fewer? But then I have to be careful, because there's an inherent paradox there. I also could have said "one plus the biggest number that can be named with a thousand words or fewer," but then I just named that with fewer than a thousand words. From this, logicians and philosophers drew more than a hundred years ago that the concept of naming a number in English is not as clear as we think it is. It leads to paradox if you're not careful.
But what if we could name a number in a way that was completely unambiguous? Since Alan Turing in the 1930s, we've had such a way: computer programs or Turing machines. So we could say, think of the largest integer that can be generated by a computer program that is at most a thousand bits in length. Now you have to be careful. A computer program could run forever. It could start just printing an infinite sequence of nines. So we restrict attention to those computer programs that eventually halt. For a given n, we consider all of the possible computer programs that are n bits long. There are two to the n power of them, or at most two to the n power. Many strings will just lead to things that are not even programs, they won't even compile, so we throw those away. Now among all of the valid n-bit programs, some of them run forever. We run them on a blank input, so we throw those away as well. 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 largest number of steps until it stops. That number of steps is what we call the N busy beaver number.
The way 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. The amazing thing is one can prove that this function grows faster than any computable function. No matter what sequence of integers you can define, if you are in a contest to name the largest number, and if you say busy beaver of 1000, then you will utterly destroy any opponent who doesn't know about the busy beaver function or anything similar to it.
One can say further remarkable things about this function, like that only a finite number of values of the function can actually be proven from the axioms of set theory. For reasons of Gödel's incompleteness theorem, after a certain finite point, the values of this function presumably have definite values because it's a clearly defined function, and yet we could no longer prove what they are.
Right now, if you take the Busy Beaver function as Rado defined it in the 60s, only four values of the function are known. 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 is at least 47 million. We don't know how much bigger it might be. Busy Beaver of 6, it's at least about 10 to the 36,000. It 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, and might be enormously larger still.
Host
Just to give people an idea of how this function grows.
Scott Aaronson
Yeah.
Host
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 non-experts like me could understand it. And just to clarify from my own understanding, it's not that there isn't a function that for any n is greater than busy beaver of n, it's just that busy beaver will eventually be with more states than if you have...
Scott Aaronson
That's exactly what I meant when I said grows faster than. Each particular value of busy beaver is just some positive integer. It's a very concrete thing, like it's six or it's 21. But if you look at the rate of growth of these integers, it will eventually dominate any computable function. In practice, not just eventually, but very, very quickly.
Host
And you show very elegantly in the paper that that means you can independently prove the halting problem and Gödel's incompleteness theorem.
Scott Aaronson
The unsolvability of the halting problem, Gödel's theorem, these things are so intertwined. There are many, many different ways to prove them all. But the busy beaver function gives you one way that you can use it to prove independently that there is an uncomputable function. You can use it to prove Gödel's incompleteness theorem.
Host
Right, okay. So my question, the proposition three was the one that said, for any axiomatic theory, that you can't prove all of Busy Beaver with it. So my question was, can you keep extending it such that you can prove higher and higher values of Busy Beaver, even though there's no systematic way to extend our set theory?
Scott Aaronson
That's a wonderful question. I would say we don't really know yet. Right now we can't even pin down Busy Beaver of five. My guess would be that the resources of existing set theory are perfectly enough to do that, but we don't even know that.
Four years ago, a student of mine named Adam Yedidia and I decided to look into a question that for some reason no one had looked at before: what is the smallest N for which we can actually prove that the value of busy beaver of N is independent of set theory? 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? In practice, this problem boils down to almost like software engineering. 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. You have to build such a Turing machine with as few states as possible. If you can build such a machine with only n states, then you've proven 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.
What we managed to do was find such a machine with about 8,000 states, after a lot of optimization and coding and new ideas. Since then, a hobbyist, someone outside of academia by the name of Stefan O'Rear, has managed to improve our bound and got it to under 800 states. That is the current record. Could you get it down to like 10 states? That would tell us that we have to already go beyond the current axioms of set theory just to get the next few values of the busy beaver function. But maybe not. Maybe you can even get a hundred of them with existing set theory. We don't know.
At whatever point ZF set theory, Zermelo-Fraenkel set theory, which is the accepted basis for most of math, runs out of steam, we don't know exactly where that point is. But one can then extend it by what are called large cardinal axioms, which basically assert that there exists an infinity that is bigger than any infinity that can be defined in ZF set theory, or infinities of various particular kinds. Presumably one could then settle more values of the busy beaver function that way. But the issue is, no matter what set theory you think of, as soon as you can build a Turing machine that enumerates all of the theorems of that set theory, then however many states there are in that Turing machine, that sets a bound on how many busy beaver numbers that set theory can ever determine. The set theories that can determine more and more busy beaver numbers will have to become more and more complicated. There will never be a systematic way to search for them, because if there were, then that would make the busy beaver function computable.
We could keep proposing more and more set theories. Modern mathematical logic set theorists do this. They propose more and more large cardinal axioms, but sometimes they actually discover that their axioms are inconsistent. Or they provisionally adopt an axiom and use it, but the community is not really convinced that it won't lead to an inconsistency. There's no surefire way to think of these axioms and be confident that you actually still have a consistent system.
Host
Okay, let me offer a very simple thought experiment. This is inspired by that joke that if you shoot enough sunlight at the Earth, it'll shoot a Tesla back. 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, with all the humans on it.
Scott Aaronson
Given the appropriate initial data.
Host
Yeah. And so simulating all that is a computable function. And if you can check every 100 years and see what is the biggest busy beaver number that humans have proven this century, what is the biggest busy beaver number proved 100 centuries, is that not a computable function that tells you busy beaver of n indefinitely higher as well?
Scott Aaronson
It would give you a way to compute arbitrary values of the busy beaver function if humans were indeed to continue. Under the assumptions that everything in our physical world is computable — we let that assumption pass almost without comment, although that's an enormous question in itself, with some brilliant people like Penrose on the other side of that — and assuming that we could somehow continue finding more and more values of the busy beaver function indefinitely, if that were true, then we would have a contradiction.
Host
So then either the Turing principle is false or we can't indefinitely keep extending.
Scott Aaronson
A very conservative way out would be to say that our quest to compute more and more busy beaver numbers will come to an end.
Host
That's very interesting. In fact, there has not been another busy beaver number determined since the early 1980s, which is when the busy beaver four was pinned down. So I'm looking forward to the paper you published with the hobbyist.
Scott Aaronson
Bruce Smith is his name.
Host
Bruce Smith. Okay, very interesting. So let me ask you now. I remember in class last year, you said that basically we have a few very important quantum algorithms like Grover's and Shor's that were discovered in the 90s, and now a lot of stuff is just an extension of those algorithms. What do you think is the potential of finding other quantum algorithms that are as fundamental and important as Grover's and Shor's were?
Scott Aaronson
I would love it if there were. I would be thrilled to discover such an algorithm, or have one of my students discover it. That's the kind of discovery that we enter this field for. If we're being intellectually honest, we have to admit that it's been 25 years since Grover's algorithm was discovered. Maybe no other quantum algorithm as fundamental as Shor's or Grover's has been discovered in the last 25 years. What we have discovered, as you learned because you took my class, was an enormous number of generalizations and new applications and variations of Shor's and Grover's algorithms, including what are called quantum walk algorithms, including phase estimation-based algorithms. Some totally different quantum algorithms were also discovered, although the problems they solve are maybe more abstruse, or it's harder to explain what problem they're solving.
You could wonder, is it lack of imagination on our part? Another possibility is, if you look at the history of classical computer science, what you find is that there are a few basic techniques that were discovered very early on. One of them is dynamic programming, dividing your problem recursively into subproblems. Divide and conquer, greedy algorithms, convex programming, linear programming, Gaussian elimination. Most of the classical algorithms that we know are somehow built up out of these motifs that were discovered very early on. We don't normally think of that as a failure of classical algorithms. We just think of it as there are these fundamental features of the algorithmic universe that people noticed as soon as they started looking. You can go much further, but you go much further by building on the basic things that you have.
So maybe we should think of Shor's algorithm and Grover's algorithm not as just specific algorithms, but as some of the basic design motifs of the world of quantum algorithms. It's not surprising that they were discovered very early on, just like dynamic programming was discovered right at the beginning of the history of classical algorithms. That's one point of view.
Another point of view is, when people ask for more quantum algorithms or hold us to account for our failure to discover more, I like to answer that question with another question: what are the problems that you would like these algorithms for? Amazingly, that question almost always stops them. Because no matter what problem they name, there's an excellent chance that people in quantum algorithms have thought about it. We know something about how much speedup you can get from a Grover-type algorithm, but we have good reasons to think that you're not going to be able to get better than that. Or in the case of the graph isomorphism problem, maybe there's a polynomial time quantum algorithm, but probably just because there's a polynomial time classical algorithm that hasn't been discovered yet, although there's been major progress toward it.
No matter what problem they name, probably someone has studied it in the context of quantum algorithms, and I could tell them exactly what the current situation is and what people are stuck on. It might be that if we want to discover fundamentally new quantum algorithms, the way to do it will be to realize fundamentally new problems, problems that people hadn't even thought about designing an algorithm for previously.
Another way I like to put it is, in any given area of math or science, there is this phenomenon of low-hanging fruit that gets picked very early on. Those of us who come into the field a little bit later have to leap higher if we want to find any fruit. But I think the ultimate solution to the problem of low-hanging fruit being picked is to find a new orchard. Figure out what are potential problems that quantum computers could solve that no one has been thinking about before. 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 new problems or new applications.
Host
Just like with Grover's algorithm, is there some reason to expect from first principles that there are other algorithms that can be solved by quantum algorithms?
Scott Aaronson
Anything where it's as basic as Grover's algorithm, where you just look at the way that amplitudes are changing over time and think that an algorithm is going to exist, that probably would have been snapped up by now just because quantum algorithms have become so much more sophisticated compared to what they were 25 years ago. But there are some problems where there is some evidence that a quantum algorithm might exist, even though we don't yet know it. A good example is computing the edit distance between two strings, which means the minimum number of insertions, deletions, and changes to change one string to another. This is a fundamental problem for DNA sequence alignment. The best known algorithm for it takes quadratic time based on dynamic programming. 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 if so, it has not yet been discovered. There are cases like that.
Host
Gotcha. Okay. 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? You said on Sean Carroll's podcast that Shor and Grover were collaborators at Bell Labs.
Scott Aaronson
I'm not sure that they actually were collaborators. I think they worked in the same building. The discovery of Shor's algorithm created a lot of excitement all over the place, but certainly at Bell Labs, which is where Shor was. Grover worked also at Bell Labs, but in a completely different department. I think he was affected by that excitement. I'm not even sure if they knew each other prior to Grover's discovery of Grover's algorithm. But more broadly, it is certainly true that in the history of ideas, major innovation seemed to come in clusters all the time. Bell Labs was a huge example of that. Shor's and Grover's algorithms were really at the tail end of the heyday of Bell Labs, which was mostly the 40s, 50s, 60s, 70s. You had the invention of the transistor, of the communication satellite, and so many other things from this one place.
Another example would be Athens in the ancient world, Florence, Cambridge University at the turn of the 20th century, which had so many mathematicians, economists, philosophers, physicists who revolutionized the world. This might be because something about the environment, ideas bounce off of each other. People see someone achieve something spectacular and they are either inspired by that or they view it as a challenge and want to compete and come up with their own thing. Silicon Valley would be another big example, although more for technology than for science.
A different explanation would be that these certain places at certain points in time just attract all of the people who maybe anyway would have had these great ideas. That kind of person wants to go to these centers wherever they are, so these centers will just collect the kind of people who are likely to discover these things. Correlation doesn't equal causation in this case.
Host
Okay. Let me ask you now. I've interviewed a lot of economists on this podcast, and I think this question will be interesting to the listeners. In your paper on why philosophers should care about complexity, you talk about how the difficulty in finding Nash equilibrium might be relevant to discussions on economics. Can you explain this?
Scott Aaronson
There was a big advance in theoretical computer science 14 years ago when theoretical evidence was finally discovered for why computing a Nash equilibrium is a hard problem. I know that this confirmed a suspicion that people had had for a long time. If we look at a von Neumann equilibrium, which is an equilibrium of a two-player zero-sum game, this can be found easily using linear programming. But a Nash equilibrium is somehow a more complicated beast. The way that Nash proved that they exist in the 50s was using what's called the Kakutani fixed point theorem, some fixed point theorem from topology. If you try to actually unwind the existence proof into an actual algorithm to calculate the equilibrium, what you get is an algorithm that ends up taking exponential time. It eventually hits the equilibrium, but it may have to follow an exponentially long trail before it reaches it.
If you're interested in this, the best things that have been written about it are by Christos Papadimitriou. Papadimitriou was one of the discoverers in 2006, along with Goldberg and Daskalakis, of this hardness theorem. It doesn't prove that it's hard to find a Nash equilibrium. In fact, it doesn't even prove that it's NP hard. This problem 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. In order to be NP-complete in any way that we currently understand, there has to be a decision problem: is there a solution or is there not a solution? But for finding a Nash equilibrium, there always is a solution. There's only the problem of how to find it. What was shown is that basically finding a Nash equilibrium is at least as hard as any other problem for which a solution is guaranteed to exist because of the same kinds of principles. It is complete for that complexity class of problems for which a solution is guaranteed to exist for this sort of reason.
What does this mean for economics? It's not clear if it has a sort of direct implication, but it fits into this general narrative that just because an equilibrium exists, that's not the end of the story. If the market can't actually find the equilibrium, if calculating this equilibrium would take exponential time, then we shouldn't expect the market to be able to find it either. Economists are well aware that there are these issues, that people are not perfectly rational, even if they want to be perfectly rational, which they don't always. Being perfectly rational might involve computations that they're just not able to do. With varying degrees of success, they've tried to account for such phenomena. But Nash equilibria are so central to economic theory that the hardness of finding Nash equilibria is a non-trivial result underscoring that general point.
Host
That's incredibly interesting. Do you think Hayek's knowledge problem or the way he phrased it might be related to complexity as well?
So in terms of central planning, in order to satisfy some constraints set by bureaucrats, it might be like an NP-complete problem. I want to separate two different things: one is lack of knowledge about what is going on in the economy, and the other is lack of ability to do computations on the knowledge that you have. The hardness of Nash equilibria is talking about the latter issue.
Scott Aaronson
Yeah, I see what you're saying. They're related in a way, right? They're both different kinds of deviations from perfect omniscience. But there are different kinds of deviations from omniscience, and in theoretical computer science, we very often have to distinguish them.
People will ask me if some problem is NP-complete when what they really mean is how hard is it to collect the information. That's apples and oranges. It's a category mistake. Once you know, to even talk about whether a problem is in P or NP, we assume that an input is given to you. All of the information that you need is in front of you, and we are exclusively concerned with the difficulty of calculating something about that information.
Now there is also the difficulty that economic actors don't have the information that they need, or certainly central planners don't have the information that they need. There's actually a whole subfield of economics—the economics of information—about how much you pay to learn something about what is going on, or how you design an auction to elicit the information you want from participants. I think economists have an easier time dealing with those things. That stuff has been better integrated into economics than the computational consideration.
Host
Okay, that's incredibly interesting. Just a few more questions. I'm going to bring us back to David Deutsch and creativity. In the "Ask Me Anything" chapter of *Quantum Computing Since Democritus*, a student asks you what complexity class creativity is. Part of what you say is that we've got a billion years of natural selection giving us a very good toolbox of heuristics for solving certain kinds of search problems, like problems in NP. That makes it sound like we have more heuristics to solve these problems than chimpanzees do, and chimpanzees have more than ants. I don't know if this is how you meant it, but do you see the algorithm for creativity as a thing you have or you don't have? Or is it that you just have better heuristics for searching through different possibilities?
Scott Aaronson
I don't know that there is such a thing as the algorithm for creativity. In fact, the phrase is almost oxymoronic. If there were such an algorithm, whatever it output would no longer be creative, would it? It would just be the output of that algorithm.
I think there is such a thing as general-purpose reasoning ability, or general-purpose ability to invent creative solutions to problems. Einstein had more of it than some random person off the street, but the random person off the street has more than a chimpanzee, and a chimpanzee has more than an ant. But it is very hard to articulate what we mean by that in a way that would actually support these comparisons across vastly different evolutionary histories and goals in life.
Host
Do you buy David Deutsch's term "universal explainer"? That people are universal explainers, AIs will be universal explainers, but non-human animals aren't, and that's the only demarcation that matters?
Scott Aaronson
Deutsch is incredibly optimistic and also incredibly categorical in his thinking. I don't know anyone else who is as optimistic, and hardly anyone else who is as black and white. It does seem likely that there is some kind of threshold you cross in going from a chimpanzee to a human. A chimpanzee is smarter than a cow, but if you stare at both of them, it doesn't seem like the chimpanzee is noticeably closer than the cow to being able to land on the moon or prove Fermat's Last Theorem.
With humans, you had a few extremely important milestones that had not been crossed before in the animal kingdom. You have universality of language—the ability to have a recursive language that can express thoughts of unbounded complexity. You had the invention of writing, the ability to transmit those thoughts across generations. A number system that could refer to arbitrarily large numbers. And then computers, which are universal machines. All of this went along with being able to explain the world around us in explicit theories to an extent that no other animal species was ever able to do.
Having said that, I don't actually know if people are universal explainers. I have no idea if we can explain everything, or even if we can explain everything that is explainable. I hope we will continue being able to explain a lot more than we can explain right now.
Deutsch uses words in unusual ways. When he talks about why he is so optimistic, part of his optimism is that when he uses the word "people," he also includes extraterrestrials. He says it's possible that humans on Earth will kill themselves out through nuclear war or environmental catastrophe, but that's not a big deal because "people" in the broader sense—life elsewhere in the universe—will go and do all the amazing things anyway. That may be cold comfort to most of us here on Earth. When he says people are universal explainers, you always have to press him on what he means by "universal explainer" and even what he means by "people."
Host
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 postulate an arbitrary collapse—since we have no reason to expect there are things we cannot explain, the most parsimonious explanation is that we can explain everything.
Scott Aaronson
I don't know. There are certain questions—the hard problem of consciousness, or the question of why is there a universe at all—where it's not just that we don't have an explanation, it's that the mind spins in circles when we try to contemplate what could possibly consist of an explanation. What could an explanation possibly look like, even in principle? That could just be a lack of imagination, but it could be that there are limits.
We all know the two-year-old who asks "why," and you tell them, and they ask "why" again, and after a half dozen whys, you're all the way back at the Big Bang, and they continue asking "why." It could be that there are questions with the property that every explanation leads to further questions.
I think even Deutsch thinks there is no one time where we'll have an explanation of everything. He says that each question we answer will lead to further questions. Each time you explain something, there's the question of what the explanation is based on, and why that is. So just like that two-year-old, we can always dig deeper.
But to loop back to earlier in this conversation, if we think about the Busy Beaver function, we know it's not just that you need more and more resources to compute more values—you'll never know all of them. There are fixed values, like Busy Beaver of 800, where the existing axioms of set theory provably will not suffice to let you determine that. Likewise, for all I know, there could be fixed questions—maybe the hard problem of consciousness, maybe why is there a universe—where what we currently consider to be an explanation will not suffice to ever explain these things.
Unlike Deutsch, I don't want to assert that I know the answer from first principles. I want to continue looking for explanations. When you're searching for explanations, it can be psychologically helpful to assume that the explanation exists. But let's not make that into more than it is. Let's not take a useful heuristic and elevate it into a basic principle of reality.
Host
On this point, in *The Fabric of Reality*, Deutsch talks about how Gödel's incompleteness theorem actually verifies the importance of creativity. If we need to come up with new axioms to prove Busy Beaver of 800, that's the point of creativity. And as far as the hard problem of consciousness, I think he thinks it can be solved. But even if it can't be solved, the reason it's so hard is not because it's an artifact of our mind—it just seems like we can't imagine a possible way that you could solve it regardless of what kind of mind you had.
The final question: what advice would you give to a 20-year-old who's interested in technical subjects but maybe not doing a PhD program like you were at the time?
Scott Aaronson
Just learn all that you can. There has never been a time when more resources were available to anyone who wants to learn things. Take courses, talk to your professors, go on the internet and read books, delve deeply into a subject. You might be surprised at how low the barriers sometimes are.
Let's say it was quantum computing that you were interested in—it doesn't have to be, it could be anything else. The entire literature of quantum computing is available for free on arXiv.org. If you go and look every night at the new quantum computing papers that come out and flag the ones that are interesting to you and read them, each paper will raise new questions that the authors don't know the answer to yet. Sometimes they'll be explicitly listed in an open problem section, other times they'll be ones you could think of.
You can study those problems. If you have ideas about them, you can talk to the authors of the paper. It might take years or decades to become an expert in a whole field, 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. So try to become the world expert on something, even something very narrow. Once you've done that, you can write an article about it or do a project about it. That will lead to more things—maybe collaborations in the future—and it will lead to you being able to try to become an expert on something a little bit wider, then something a little bit wider, and so on.
Host
That's very excellent advice. I love that. Professor, thank you so much for your time.
Outro music begins
Hey, if you enjoyed 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 small podcast like this one. So thanks for watching.