What this covers
Scott Aaronson, a professor of computer science at the University of Texas and director of its Quantum Information Center, speaks with host Dwarkesh Patel about the historical arc of quantum computing and its relationship to fundamental theory. The conversation traces why quantum computing and teleportation emerged so long after quantum mechanics itself was formalized—not due to intellectual suppression, but because the necessary conceptual and mathematical scaffolding had to be built first. Aaronson argues that Bell's work in the 1960s made entanglement legible as a usable resource, and that complexity theory developed in parallel, creating the preconditions for algorithms like Shor's and Grover's to be discovered. Rather than viewing these as isolated breakthroughs, he positions them as fundamental design motifs of the quantum-algorithmic universe—basic architectural patterns, much as dynamic programming and divide-and-conquer anchor classical computing.
The conversation branches into several distinct areas. Aaronson uses the busy beaver function as a concrete window into Gödel's incompleteness—only four busy beaver values are currently provable from set theory, with BB(5) exceeding 47 million, demonstrating that any fixed axiom system hits a ceiling. He connects computational hardness to economics, distinguishing Nash equilibrium computation (a solved-but-hard problem) from Hayek's knowledge problem, and argues that market actors face real computational limits, not just rationality constraints. The discussion also covers whether breakthroughs come more often from academia's margins or its outsiders, the role of geographic clusters like Bell Labs in driving innovation, and whether anything like an algorithm for creativity is even coherent as a question.
Aaronson argues that breakthrough ideas in quantum computing and complexity theory were delayed not by suppression but by intellectual prerequisites and competing priorities, and that fundamental algorithms like Shor's and Grover's are better understood as basic design motifs of the quantum-algorithmic universe rather than isolated discoveries.
- Quantum mechanics and computing both existed by the 1930s, but viewing entanglement as a usable resource only began with Bell in the 1960s and complexity theory in the 1960s-70s
- Shor's and Grover's algorithms function like the early-discovered basic motifs of classical algorithms (dynamic programming, divide and conquer)
- The busy beaver function concretely demonstrates Gödelian limits on what any fixed axiom system can prove
This asset isn't compiled yet
You're seeing its claims, ranked. Compile it to build the argument threads, weight them, and check each claim against your library — the full view.
Lack of knowledge about the economy and lack of ability to compute on the knowledge you already have are distinct kinds of deviation from omniscience; Nash equilibrium hardness concerns the latter (computation), whereas Hayek's knowledge problem and the economics of information concern the former, and economists have integrated information problems more successfully than computational ones.
“i i want to separate two two different things right one is lack of knowledge ... and the other one is lack of ability to do computations on the knowledge that you have ... economists maybe have an easier time dealing with those things ... than the computational considerations”
Computing a Nash equilibrium is a hard problem (PPAD-complete, shown by Daskalakis, Goldberg and Papadimitriou in 2006): it is not NP-complete because a solution always exists by Nash's theorem, but it is at least as hard as any problem whose solution is guaranteed to exist; unwinding Nash's Kakutani fixed-point existence proof yields an algorithm that may follow an exponentially long trail before reaching the equilibrium.
“papademitria was one of the discoverers in the uh uh in 2006 uh along with goldberg and dos kalakas of this this hardness theorem ... this problem kind of doesn't have the right structure to be an np complete problem ... finding a nash equilibrium is at least as hard as any other problem for which you know a solution is guaranteed to exist”
David Deutsch was able to think seriously about quantum computing because he took the many-worlds interpretation seriously, motivated by wanting to demonstrate quantum mechanics is universally valid at all scales — a quantum computer doing interference between computations is conceptually like a superposition over a brain thinking different thoughts.
“that is definitely true for deutsch right ... deutsche was was thinking about uh you know how would you sort of make you know sort of shake people how would you sort of make them realize that quantum mechanics is universally valid that it applies at all scales”
Set theories that determine more and more busy beaver numbers must become more and more complicated (e.g. via large cardinal axioms asserting larger infinities), and there is no surefire systematic way to discover such axioms while being confident they remain consistent — sometimes proposed large cardinal axioms turn out inconsistent.
“these set theories that can determine more and more busy beaver numbers will have to become more and more complicated ... sometimes they actually discover that their axioms are inconsistent ... there's no surefire way to think of these axioms and and be confident that ... you actually still have a consistent system”
Only a finite number of busy beaver values can be proven from the axioms of set theory because of Gödel's incompleteness theorem; currently only four values are known (BB(1)=1, BB(2)=6, BB(3)=21, BB(4)=107), with BB(5) known only to be at least about 47 million.
“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 girdles in completeness theorem ... only four values of the function are known ... busy beaver of one is one busy beaver of two is six busy beaver three is 21 and busy beaver of four is uh a hundred and seven”
The busy beaver function BB(n) is defined as the largest finite number of steps any n-state Turing machine can run before halting (on a blank input), and it provably grows faster than any computable function, so naming BB(1000) would utterly defeat any opponent in a largest-number contest who doesn't know the function.
“busy beaver of n is the largest finite number of steps that any end state touring machine can run for ... one can prove that this function grows faster than any computable function”
Shor's and Grover's algorithms should be viewed not as isolated specific algorithms but as basic design motifs of the quantum-algorithmic universe, analogous to how classical algorithms (dynamic programming, divide and conquer, greedy, linear programming, Gaussian elimination) are mostly built from a few motifs discovered early in classical CS — so their early discovery is unsurprising, not a failure of imagination.
“maybe we should think of shore's algorithm and grover's algorithm not as just specific algorithms but as sort of some of the basic design motifs of the world of quantum algorithms and ... 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”
Although Bohr was right and Einstein wrong on the issue of local hidden variables, there is a deeper sense in which Einstein was the more right one, because he correctly insisted there was something about quantum mechanics not yet understood that needed to be understood — a question only resolved by Bell's inequality in the 1960s.
“even even though bohr was right and and einstein was wrong uh on the issue of local hidden variables ... there's a there's a deeper sense in which which you know einstein was the more right one and sort of putting his finger on you know there is something here that we do not yet understand”
If calculating a Nash equilibrium would take exponential time, we shouldn't expect a real market to find it either; thus the hardness of finding equilibria underscores that an equilibrium's mere existence is not the end of the story, reinforcing the recognized point that economic actors face computational, not just rationality, limits.
“if if the market can't actually find the equilibrium ... if if calculating this equilibrium would take exponential time then we shouldn't expect the market to be able to find it either”
The smallest n for which BB(n) is provably independent of set theory can be bounded by constructing a Turing machine that searches for a contradiction in set theory and halts only if it finds one; Aaronson and Adam Yedidia achieved ~8,000 states, later improved by hobbyist Stefan O'Rear to under 800 states, and getting it down to ~10 states would prove existing set theory cannot even determine the next few busy beaver values.
“what we managed to do is we managed to find such a machine with 8 000 states ... a hobbyist ... by the name of stefan o'rier uh has managed to improve our bound and got it to under 800 states”
Richard Feynman conceived of quantum computing around the same time as Deutsch but with a different, practically-focused motivation: simulating physics, where classical computers suffer an exponential slowdown, prompting the idea of a universal quantum simulator — showing many-worlds was not necessary to arrive at quantum computing.
“richard feynman had the idea of quantum computing around the same time as deutsche did ... that was not his motivation for thinking about quantum computing ... he was thinking about how do we simulate uh physics ... if we use classical computers we suffer this exponential slowdown”
There is probably no 'algorithm for creativity' because the phrase is almost oxymoronic — whatever such an algorithm output would no longer be creative since it would merely be that algorithm's output.
“i don't know that there is such a thing as the algorithm for creativity ... the phrase is almost oxymoronic right that if there were such an algorithm well then whatever it output would no longer be creative would it because it would just be the output of that algorithm”
The theory that academia since the 1970s has become less open to new ideas may hold in social sciences and parts of medicine, but in physics, foundations of computing, and cosmology the opposite has happened — the arXiv preprint server removed journal gatekeeping, so the real problem now is too many bold ideas to sift through rather than barriers to publishing them.
“in um in in physics and ... speculation about ... the uh foundations of uh of of computing and ... cosmology ... i i think if anything things have gone in the opposite direction ... we now have this pre-print server this archive where you know everyone can post you know all of their new research ideas you know with no filter”
The reason quantum teleportation (1990s) and quantum computing (1980s) came decades after quantum mechanics (1926) is that viewing entanglement as a usable resource only began with John Bell in the 1960s, computational complexity theory only developed in the 1960s-70s, and meanwhile both physics and the nascent field of classical computing had enormous other priorities, plus WWII diverted fundamental scientists.
“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 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 ... a decade after that people start thinking about quantum computation”
Just as the busy beaver function has fixed values (like BB(800)) that existing set theory provably cannot determine, there may be fixed questions — perhaps the hard problem of consciousness or why there is a universe at all — that what we currently consider an explanation will never suffice to answer; unlike Deutsch, Aaronson refuses to assert from first principles that all such things are explainable.
“just like that two-year-old right we can always dig deeper ... if we think about the busy beaver function ... there are fixed values like busy beaver of 800 ... where the the existing axioms of set theory ... provably will not suffice ... likewise for all i know there could be fixed questions where ... what we currently consider to be an explanation just will not suffice”
Combining the Church-Turing principle (the physical world is computable) with the assumption that humans could indefinitely keep finding more busy beaver values produces a contradiction, since simulating humanity would then compute an uncomputable function; therefore either the world is not fully computable or our ability to compute new busy beaver values must eventually halt — and notably no new busy beaver value has been determined since the early 1980s.
“assuming that that you know uh everything we're doing is computable and also assuming that we could somehow you know continue finding more and more values of the busy beaver function indefinitely right if that were true then we would have a contradiction”
Breakthroughs do come from people outside academia, but most often these are people on academia's margins (who got or partially got a PhD then left), as with Yitang Zhang who proved infinitely many prime pairs at most 70 million apart while working odd jobs including making sandwiches; by contrast, untrained autodidacts who claim to have solved P vs NP usually simply don't understand the question.
“there was a uh famous case of yi tang zhang ... who uh proved that that there are infinitely many pairs of primes at most 70 million apart ... this was a guy who ... worked um making and making sandwiches ... in order to like support his family ... but continued working on math”
The modern concept of an extended 'teenagerhood' in which people aged roughly 12-18 are still children is largely a recent social construction; historically teenagers were apprentices learning a trade while working.
“the the entire concept of you know of sort of teenager hood right that like people are are you know from the age of 12 to 18 ... we're still basically children right i think that that's largely a modern construction”
Early 20th-century physics was 'ripe' for the relativity and quantum revolutions, so if Einstein hadn't made his 1905 discoveries someone else would have soon after — except general relativity, which took Einstein a decade longer and might otherwise have been delayed by decades.
“if if it wasn't einstein it would have been someone else you know uh uh not long after with all of those things i'm general relativity which you know which took einstein a decade longer ... it might have been decades before anyone else did that”
Whether older scientists' brains actually slow down or whether they simply have less motivation and free time is an open empirical question; Aaronson notes that when away from family obligations he can work as he did in his 20s, suggesting time and motivation may dominate over cognitive decline.
“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”
Humans crossed a threshold from other animals via a succession of universality milestones — recursive language able to express thoughts of unbounded complexity, writing to transmit thoughts across generations, a number system referring to arbitrarily large numbers, and universal computing machines — all tied to explaining the world in explicit theories as no other animal can.
“you have you know a universality of of language ... the ability to have a recursive language that can ... express thoughts of you know uh unbounded complexity ... the invention of writing ... a number system that could refer to arbitrarily large numbers ... computers ... which are universal machines”
There is evidence a quantum algorithm might exist for computing edit distance between two strings (a fundamental problem in DNA sequence alignment) in roughly n^(3/2) time versus the best known quadratic-time classical dynamic-programming algorithm, though such a quantum algorithm has not yet been discovered.
“a good example is computing the edit distance between two strings ... The best known algorithm for it takes quadratic time it's based on dynamic programming ... there is some evidence that there might be a quantum algorithm that would take n to the three halves time”
Major innovations cluster in particular places and times (Bell Labs, ancient Athens, Renaissance Florence, turn-of-century Cambridge, Silicon Valley), and this is either because ideas bounce off each other and inspire competition, or because such centers simply attract the kind of people who would have had great ideas anyway — making it a correlation-vs-causation problem.
“major innovations seem to come in clusters all the time bell labs was a huge example of that ... another explanation would be that you know these certain places at certain points in time just you know attract all of the people who ... would have had these great ideas ... correlation doesn't equal causation in this case”
The way to find fundamentally new quantum algorithms may be to discover fundamentally new problems no one had thought of applying an algorithm to — the solution to picked-over low-hanging fruit is to find a new orchard, and access to real quantum hardware may stimulate the discovery of such new problems.
“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 ... the ultimate solution to the problem of low-hanging fruit being picked is to find a new orchard”
It does not take long to become the world expert on one particular tiny narrow problem, and once you've done that it leads to articles, projects, collaborations, and then expertise on progressively wider topics.
“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”
Never has more learning resources been available; one can learn deeply by taking courses, talking to professors, and reading freely-available literature (e.g. all quantum computing papers on arXiv), and the barriers to becoming the world expert on one tiny problem are surprisingly low.
“they're uh you know has never been a time when sort of more resources were available to anyone who wants to to learn things ... the entire literature of quantum computing pretty much is available for free on you know on archive.org”
There is a developmental window in which children absorb languages effortlessly, after which learning a language becomes a difficult intellectual puzzle and one will never speak it as well as a native five-year-old.
“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 ... you'll never speak it as well as a as a as a native five-year-old”
Aaronson's social and dating life were severely disrupted by skipping grades — he got his PhD before learning to drive or having any social/dating life — but he reasoned that since he was already socially miserable in high school, he might as well at least be learning more.
“i got i got my uh phd uh before basically before uh i i learned how to drive really or ... learned how to have any kind of a social life ... my main argument was that ... i was already socially unhappy in high school”
Aaronson did not graduate high school at 15 but got a GED from New York state, having skipped grades to escape an environment he found socially and academically unhappy, and his parents had to convince the state to make an exception to the age-17 GED rule.
“i i didn't really graduate high school when i was 15. i got a ged uh from from from new york state”