This article was published in Scientific American\u2019s former blog network and reflects the views of the author, not necessarily those of Scientific American<\/p>\n
Scott Aaronson has one of the highest intelligence\/pretension ratios I\u2019ve ever encountered. I wasn\u2019t really aware of him before last fall, when I attended a conference at New York University on an ambitious new theory of consciousness, integrated information theory<\/a>. Most speakers touted IIT or tried to tease out its implications. The striking exception was Aaronson, a boyish (he turns 35 on May 21 but looks younger) computer scientist at MIT (soon leaving for the University of Texas<\/a>\u2014too bad, MIT!). Although at first he seemed nervous, even jittery, he proceeded to demolish IIT. He focused on a key IIT variable, phi, which denotes the inter-connectivity, or synergy, of the parts of a system. The more phi a system has, the more consciousness it has, supposedly. Aaronson argued\u2014or showed, actually–that IIT\u2019s mathematical definition of phi implies that a simple information-storage device, like a compact disc, can be more conscious than a human being. Proponents of IIT, including neuroscientists Guilio Tononi and Christof Koch and physicist Max Tegmark, raised objections to Aaronson\u2019s critique, but he amiably\u2014and devastatingly–rebutted them. Who is this guy? I wondered. Browsing Aaronson\u2019s blog, \u201cShtetl-Optimized<\/a>,\u201d I discovered that he writes not only about quantum computation, his specialty, but also about artificial intelligence, mathematics, cosmology, particle physics, philosophy\u2026 Aaronson has things to say about almost everything. Even when he is at his most technical, he expresses himself in a down-to-earth, funny, self-deprecating and above all clear way. He exudes the spunky enthusiasm and curiosity of a 10-year-old kid, a kid who happens to have a firm grasp of mathematics and physics. He thinks I\u2019m wrong about the end of science<\/a>, and that\u2019s fine with me. Hell, he might be right! [See Addendum.] I won\u2019t say more about him here, because I don\u2019t want to embarrass him–or myself–more than I already have, and because he reveals so much of himself in what follows. Warning: this is an extra-long Q&A, but if you read it, I predict, you too will become an Aaronson fan. \u2013John Horgan<\/p>\n 1. Have you become what you wanted to be when you were a kid?<\/p>\n Come on, that\u2019s too high a bar!\u00a0 When I was a kid, I wanted to be the founder and ruler of a rationalist space colony, who also wrote video games and invented the first human-level AI and led a children\u2019s liberation movement and discovered the mathematical laws underlying society.<\/p>\n On supporting science journalism<\/p>\n If you’re enjoying this article, consider supporting our award-winning journalism by subscribing<\/a>. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.<\/p>\n On the other hand, as far as childhood dreams go, I have no right to complain.\u00a0 I have a wonderful wife and three-year-old daughter.\u00a0 I get paid to work on engrossing math problems and mentor students and write about topics that interest me, to do all the things I\u2019d want to do even if I weren\u2019t getting paid.\u00a0 It could be worse.<\/p>\n 2. Why do you call your blog \u201cShtetl-Optimized\u201d?<\/p>\n I get that a lot.\u00a0 It\u2019s one of those things, like a joke, that dies a little when you have to explain it\u2014but when I started my blog in 2005, it was about my limitations as a human being, and my struggle to carve out a niche in the world despite those limitations.\u00a0 It also gestured toward the irony of someone whose sensibility and humor and points of reference are as ancient as mine are\u2014I mean, I already felt like a senile, crotchety old man when I was 16\u2014but who also studies a kind of computer that\u2019s so modern it doesn\u2019t even exist yet.<\/p>\n Shtetls were Jewish villages in pre-Holocaust Eastern Europe. \u00a0They\u2019re where all my ancestors came from\u2014some actually from the same place (Vitebsk) as Marc Chagall, who painted the fiddler on the roof.\u00a0 I watched Fiddler many times as a kid, both the movie and the play.\u00a0 And every time, there was a jolt of recognition, like: \u201cSo that\u2019s the world I was designed to inhabit.\u00a0 All the aspects of my personality that mark me out as weird today, the obsessive reading and the literal-mindedness and even the rocking back and forth\u2014I probably have them because back then they would\u2019ve made me a better Talmud scholar, or something.\u201d\u00a0 So as I saw it, the defining question of my life was whether I\u2019d be able to leverage these traits from a world that no longer existed, for the totally different world into which I was born.<\/p>\n Of course, there are pockets where the shtetl still does exist; there are orthodox Jews.\u00a0 As it happens, I went to an orthodox Hebrew day school, where I was exposed to that.\u00a0 But by the time I was 12, and was reading Bertrand Russell and Richard Dawkins and Carl Sagan and Isaac Asimov and so forth, it was obvious to me that I could never be a believer in any conventional sense, even if I\u2019m happy to use Einsteinian pseudo-religious language, as in \u201cwhy did God make the world quantum rather than classical?\u201d\u00a0 So from then on, the thing I yearned for was a community that would be as welcoming of intellectual obsessives as a yeshiva was\u2014but without any unquestioned dogmas or taboos, where absolutely anything could be revised based on evidence, and which was open to new ideas from anyone of any ethnicity.<\/p>\n In my quest for such a community, I could\u2019ve done a lot worse than where I ended up, namely academic computer science departments!\u00a0 The difference, of course, is that a university department covers only the intellectual aspects of life, whereas my idealized shtetl would be a place that welcomed intellectual oddballs and also helped them deal with birth, death, marriage, and everything else in their lives.<\/p>\n There are two other aspects to \u201cshtetl-optimized.\u201d\u00a0 The first is my preoccupation, not just with the past, but with one particular slice of the past.\u00a0 Even though I was born in 1981, for me, the first half of the twentieth century is and always will be \u201cthe present,\u201d and whatever this is now is the future!\u00a0 Granted, there are certain cool things about living in the future, like the Internet, and seedless watermelons.\u00a0 But as I don\u2019t need to tell you, the early twentieth century is when Einstein and G\u00f6del and Turing and so many others discovered things that could only be discovered once.\u00a0 It\u2019s when we went from horses and buggies to rockets that left the earth\u2019s atmosphere. \u00a0I spent my teenage years devouring dozens of biographies of early-twentieth-century scientists and mathematicians and philosophers, reliving their triumphs as well as the loss of everything they knew in the two world wars.\u00a0 In some sense, their world was more real to me than the stuff around me.<\/p>\n Which brings me to another aspect of \u201cshtetl-optimized\u201d: the grief over what was destroyed, and over the world\u2019s indifference while it was happening.\u00a0 The Holocaust has been the central event in my mental life since I was probably seven. \u00a0Like, if I see a digital clock that reads \u201c9:43,\u201d the first thought to cross my mind will be: \u201c1943\u2014over two million Jewish men, women, and children already lying dead in pits, but the Allies still could\u2019ve bombed the train tracks to Auschwitz and Sobibor, had they wanted to…\u201d\u00a0 In discussions about nuclear proliferation, global warming, and so forth, I never make the slightest apologies for being paranoid about humanity\u2019s future, because those members of my extended family who weren\u2019t sufficiently paranoid to flee to the United States were, as far as is known, all murdered.\u00a0 I never accept anyone\u2019s assurances that \u201ceverything will probably work out for the best.\u201d \u00a0The question, for me, is never whether to be paranoid, but only which things to be paranoid about!<\/p>\n I\u2019m gratified that many people have described me as warm and friendly and helpful (\u201csurprisingly so,\u201d one can almost hear them add, for such a socially-inept, self-obsessed nerd!).\u00a0 But there\u2019s a reason for that.\u00a0 If I meet a new person, and they aren\u2019t weird in the same ways I\u2019m weird, my brain\u2019s first questions tend to be: would this person be happy to rid the earth of me and everyone like me, regarding me as genetically defective?\u00a0 Is he or she merely temporarily prevented from doing so?\u00a0 In 1942, would he or she have smiled (as so much of Europe did smile) as I was loaded onto a cattle car?\u00a0 So then, if the person turns out\u2014as most often they do\u2014to be perfectly nice and decent, I\u2019m so relieved and grateful that it\u2019s like, how can I be anything but friendly and helpful in return?<\/p>\n And speaking of people who regard me as defective: because of a heated discussion around gender politics on my blog last year, some Internet commentators misinterpreted \u201cshtetl-optimized\u201d in the most vicious and spiteful way imaginable.\u00a0 They said it meant that I must be a misogynist monster, who yearned for a time and place when, if you were a boy who studied Talmud hard enough, society would just grant you a wife, regardless of her feelings about it.\u00a0 It shouldn\u2019t need to be said that forced marriage is monstrous, and that all decent people should oppose it always and everywhere\u2014not only in the distant past (shtetls or anywhere else), but in those parts of the world where it\u2019s still the norm.<\/p>\n It\u2019s true that, when I was a lonely, depressed young person, I yearned for a culture with clearer rules around courtship\u2014where there was an accepted, socially-sanctioned way to find out whether your romantic interest in another person might be reciprocated, without needing to get drunk first, or master vague protocols that are never explained in words, or speak in euphemisms with CIA-like plausible deniability, and with no guilt or shame or embarrassment attached to the thing.\u00a0 But it seems to me like such a courtship culture would benefit lots of people, male and female, gay and straight!\u00a0 So it\u2019s totally unclear to me that I was wrong to want that.\u00a0 Now, you could argue that the old clarity around courtship needed to go, because it stood in the way of women\u2019s liberation or individual freedom or other values that were ultimately more important.\u00a0 But you could also argue that these things have nothing to do with each other: that the loss of clarity was just a tragic byproduct of other social changes and could be reversed, consistently with modern values, if enough people wanted it to be.\u00a0 In any case, I suppose another thing it means to be \u201cshtetl-optimized,\u201d is that I never get tired of arguing that sort of question, even when getting tired of it would be to my benefit.<\/p>\n 3. Do you write a lot because your father (according to Wikipedia) was a science writer?<\/p>\n Both my parents were English majors; neither were scientists. \u00a0But my dad did start his career as a popular science writer in the 1970s. \u00a0Like you, I suppose, he interviewed famous physicists like Steven Weinberg and John Archibald Wheeler and Arno Penzias, who then became well-known names around the house.\u00a0 He even wrote for Playboy and Penthouse\u2014for the few who read the articles, I guess!\u2014about topics like the preponderance of matter over antimatter in the visible universe.\u00a0 He said they paid better than the science magazines.<\/p>\n So, my dad made me aware from an early age that there was a Big Bang, that there was a speed of light that you could approach but not exceed (and what its value was), all sorts of things like that, and he turned me on to popular science and science fiction (especially Isaac Asimov).\u00a0 My dad also made me yearn to explain all the math and computer science I was learning in plain English: if nothing else, I wanted to be able to explain it to him!\u00a0 Finally, my dad was my main writing critic, constantly telling me to be more concise (alas, judging from this interview, he should\u2019ve pushed even harder!).\u00a0 Obviously I can\u2019t do the experiment of replacing him by a \u201ccontrol dad\u201d and rerunning my life to see what happens\u2014but insofar as I can judge, he and my mother were both huge, positive influences on me.<\/p>\n 4. Do you see it as your duty to expose scientific bullshit?<\/p>\n On reflection, no\u2014because if I have such a duty, then presumably my colleagues do too, but I wouldn\u2019t want to impose such a duty on my colleagues!\u00a0 I have brilliant colleagues who choose to spend their time doing creative, original science, rather than refuting every charlatan who comes along: they figure the latter get handled automatically by the marketplace of ideas, or maybe even that acknowledging certain ideas gives them more legitimacy than they deserve.\u00a0 And that\u2019s a valid choice.<\/p>\n For me, it\u2019s more a matter of my emotional makeup.\u00a0 I see one of my genius colleagues labor for years on a deep theorem that maybe five or ten people will understand, and that not many more will care about.\u00a0 Then some know-nothing claims they\u2019ve built an analog computer that can solve NP-complete problems in polynomial time, or whatever, and their claim makes it onto Slashdot and Reddit and Twitter and news websites (but not Scientific American, of course!), where tens of thousands of people see it.\u00a0 And the juxtaposition just makes my blood boil.\u00a0 And because I happen to write a blog, people keep sending me emails or leaving comments to ask for my reaction to the news (as if they couldn\u2019t predict it).\u00a0 And I think: I can do something about this!\u00a0 And I\u2019m almost complicit if I don\u2019t.<\/p>\n There\u2019s also the issue of comparative advantage.\u00a0 I tell myself that I spend a lot of time on my blog arguing against BS precisely so that my smarter colleagues don\u2019t have to!\u00a0 Like, I\u2019m a damn good theoretical computer scientist (and modest too), but I\u2019m not at the absolute pinnacle of the field\u2014so rather than trying to ascend the summit myself, sometimes I can serve the interests of science better by staying on the lower slopes, and just trying to defend the mountain from the forces catapulting dung at it.<\/p>\n 5. How did you get interested in quantum computation?<\/p>\n As the author of The End of Science (which I read as a teenager), I\u2019m sure you can appreciate one reason: because quantum computing, in the 1990s, was this profound story at the intersection of computer science, physics, engineering, math, and philosophy that was only just beginning rather than ending.\u00a0 The field was, and remains, a major source of counterexamples to your thesis about everything fundamental already having been discovered!<\/p>\n But to step back a little: when I discovered BASIC programming as an 11-year-old, it wasn\u2019t like, this is a cool practical skill\u2014even though it had been a dream to create my own video games, and now I could finally do that.\u00a0 It was more of an intellectual revelation, like finding out where babies came from.\u00a0 I thought: so this is what it means to understand something.\u00a0 It means that you know how to express it in these lines of code, how to make a computer do it.\u00a0 So immediately I started asking myself: could there be other programming languages, or even other kinds of computers entirely, that would let you express things that could never be expressed in BASIC?\u00a0 And then I learned about the Church-Turing Thesis, which says that no, all sufficiently powerful computers and programming languages are fundamentally equivalent: they can all simulate each other, albeit faster or slower and using more or less memory.\u00a0 In learning the syntax of MS-DOS QBASIC, in that sense you\u2019ve learned the rules of the entire universe.<\/p>\n So that became a central part of my worldview.\u00a0 It told me that, even if I wanted to understand the physical world we inhabit, I didn\u2019t have to bother much with the details of physics!\u00a0 The Standard Model, general relativity, those are just yet more programming languages, more ways of combining simple mathematical building blocks into complicated emergent behavior.\u00a0 And the whole point of the Church-Turing Thesis is that once you know one programming language, you basically know them all.<\/p>\n But then, maybe when I was fourteen, I read a popular article about quantum computing, and about Peter Shor\u2019s quantum factoring algorithm, which had just recently been discovered.\u00a0 And my first reaction was, this sounds like crackpot nonsense.\u00a0 It\u2019s probably just physicists who don\u2019t understand the enormity of what it is that they\u2019re denying\u2014who don\u2019t get the overarching principle that everything around us, what we call \u201cspace\u201d and \u201cmatter,\u201d is just a huge, three-dimensional array of 1\u2019s and 0\u2019s being subjected to Boolean logic operations.\u00a0 That principle clearly overrides the physicists\u2019 grubby approximate theories of \u201cparticles\u201d and \u201cfields\u201d and whatnot, and it clearly implies that this business of \u201cfactoring numbers in trillions of parallel universes\u201d can\u2019t work, or at least can\u2019t scale to large numbers.<\/p>\n But then I learned basic quantum mechanics!\u00a0 And I found out that, yes, the discoverers of QM in the 1920s did know the enormity of what they were denying (some of them more than others), but they\u2019d found something else of comparable enormity.\u00a0 And that accepting quantum mechanics didn\u2019t mean giving up on the computational worldview: it meant upgrading it, making it richer than before.\u00a0 There was a programming language fundamentally stronger than BASIC, or Pascal, or C\u2014at least with regard to what it let you compute in reasonable amounts of time.\u00a0 And yet this quantum language had clear rules of its own; there were things that not even it let you do (and one could prove that); it still wasn\u2019t anything-goes.<\/p>\n But the real surprise was that I could learn the rules and start playing with them.\u00a0 I like to say that, after all the forbidding-sounding verbiage you read in popular books, quantum mechanics is astonishingly simple\u2014once you take the physics out of it!\u00a0 In fact, QM isn\u2019t even \u201cphysics\u201d in the usual sense: it\u2019s more like an operating system that the rest of physics runs on as application software.\u00a0 It\u2019s a certain generalization of the laws of probability. \u00a0It says nothing directly about electrons, photons, or anything like that. \u00a0It just talks about lists of complex numbers called amplitudes: how these amplitudes change as a physical system evolves, and how to convert them into the probability of seeing this or that result when you measure the system.\u00a0 And everything you\u2019ve ever heard about the \u201cweirdness of the quantum world,\u201d is simply different logical consequences of this one change to the rules of probability.\u00a0 This makes QM, as a subject, possibly more computer-science friendly than any other part of physics.\u00a0 In fact, even if our universe hadn\u2019t been described by QM, I suspect theoretical computer scientists would\u2019ve eventually needed to invent quantum computing anyway, just for internal mathematical reasons.\u00a0 Of course, the fact that our universe is quantum does heighten the interest!<\/p>\n On the biographical side, I was a teenager in the late 90s, doing a summer internship at Bell Labs in statistical software (one that had nothing to do with quantum computing), when I started studying the main quantum computing algorithms, namely Shor\u2019s and Grover\u2019s algorithms. \u00a0(Grover\u2019s algorithm, discovered in 1995, lets you search a list of N items for a desired item in only about N1\/2\u00a0steps.)\u00a0 My boss, thankfully, was also curious about quantum computing and let me follow my obsessions.\u00a0 Soon I learned that Lov Grover, the discoverer of Grover\u2019s algorithm, worked in the same building.\u00a0 So I sought Lov out, told him my crazy ideas for improving Grover\u2019s algorithm that didn\u2019t work\u2014and then for some reason he offered me an internship with him the next summer.<\/p>\n I spent that second internship trying to prove a lower bound on the number of steps a quantum computer would need to \u201cevaluate AND-OR trees\u201d (to take an example, deciding whether a square grid of black and white cells contains an all-black row).\u00a0 I failed miserably\u2014although by the end, I knew the existing tools for proving that sort of theorem inside and out. \u00a0That summer I also met Ashwin Nayak, a visiting student from Berkeley.\u00a0 Ashwin clued me in to what was happening right then in quantum computing theory, in the research group at Berkeley centered around Umesh Vazirani, who was one of the first computer scientists to study quantum computing.<\/p>\n After the summer ended, Ashwin wrote to me to tell me that Andris Ambainis, another student of Vazirani\u2019s at Berkeley, had solved the AND-OR problem, by inventing a completely new method.\u00a0 So I got an early draft of the paper from Andris, and I was blown away.\u00a0 And I thought: I must go to Berkeley for graduate school.\u00a0 I must learn whatever it is Andris and the others there know, so that someday I could prove theorems like these.\u00a0 I wrote to Vazirani to say I wanted to work with him, and he never responded, which of course worried me a lot.\u00a0 Only later did I learn that he\u2019s famous for not answering anyone\u2019s email!<\/p>\n As an undergrad at Cornell, I\u2019d also been extremely interested in artificial intelligence and machine learning\u2014so when I applied to Berkeley for graduate school, it was the AI people there who took an interest in my application and admitted me.\u00a0 But by then, my heart was in quantum computing.\u00a0 And after a year at Berkeley, I\u2019d fallen in with Vazirani\u2019s group.<\/p>\n I still had a fear that I\u2019d never do anything original in this field.\u00a0 But by the fall of my second year, after months of work, I\u2019d succeeded in solving one of Vazirani\u2019s favorite open problems, which was to rule out a fast quantum algorithm for the so-called collision problem.\u00a0 In that problem, you\u2019re given a long list of numbers, in which every number from 1 up to N appears many times, and you\u2019re just trying to find a single \u201ccollision pair\u201d: that is, two numbers in the list that are equal.\u00a0 The significance is that, if you had a fast enough quantum algorithm to find collision pairs, that would let you break all sorts of cryptographic codes using a quantum computer\u2014not just the special codes based on problems like factoring, which Shor showed how to break.\u00a0 Conversely, if you want any hope of fashioning the basic building blocks of modern cryptography so that they\u2019ll still be secure in a world with quantum computers, then you need to rule out such a quantum algorithm.<\/p>\n Anyway, it turned out that Andris Ambainis had invented his method\u2014the one that had bowled me over and lured me to Berkeley\u2014specifically to tackle the collision problem!\u00a0 And Andris\u2019s method had worked for lots of other problems, including the AND-OR problem, but not for the collision problem.\u00a0 But in an ironic turnabout, I found that an earlier method, called the \u201cpolynomial method\u201d\u2014the one I\u2019d tried unsuccessfully for the AND-OR problem\u2014worked for the collision problem.\u00a0 It worked because of some miraculous algebraic cancellations that I stumbled on after grueling trial and error, and that I still don\u2019t have a good intuitive explanation for.\u00a0 The result was that any quantum algorithm to find a collision pair, in a list of numbers from 1 up to N, needs at least about N1\/5 steps.\u00a0 Shortly afterward, Yaoyun Shi improved that to show that any quantum algorithm needs at least about N1\/3 steps.\u00a0 That turns out to be the right answer: there is a quantum algorithm, based on Grover\u2019s algorithm, that finds a collision pair in about N1\/3 steps.<\/p>\n (By comparison, a classical algorithm needs about N1\/2\u00a0steps.\u00a0 The reason for that N1\/2\u00a0is related to the famous \u201cbirthday paradox\u201d: you only need to gather about 30 people in a room, way fewer than 365, before there\u2019s an excellent chance that at least two of them share a birthday, because what matters is the number of pairs of people.)<\/p>\n After the collision lower bound, one thing led to another, and I\u2019m still doing quantum computing theory 15 years later.\u00a0 I dabble in various kinds of classical computer science too, and I\u2019m sometimes tempted to switch fields, maybe go back to AI and machine learning after all.\u00a0 But quantum computing remains so inconveniently interesting that it keeps pulling me back in!<\/p>\n If it were just about building devices to solve certain problems faster, I\u2019m sure my interest would be more limited.\u00a0 But by this point, quantum computing theory has broadened to include almost anything at the interface between theoretical computer science and physics, and whatever one field can tell the other.\u00a0 The modern-day collision of the Schr\u00f6dinger equation with the Turing machine just keeps throwing up more and more stuff, and I don\u2019t see it getting boring anytime soon.<\/p>\n 6. What hype about quantum computers really drives you nuts?<\/p>\n The biggest one is when quantum computers are described as processing an unimaginably vast number of answers in parallel\u2014so that Shor\u2019s famous quantum factoring algorithm, for example, would work simply by trying every possible divisor in a different parallel universe.\u00a0 As I like to say, if it were that simple, you wouldn\u2019t have needed Shor to discover it!\u00a0 The truth is that while, yes, quantum mechanics lets you create a superposition over an immense number of \u201cbranches,\u201d whenever you measure you see only one random \u201cbranch.\u201d\u00a0 And of course, if you\u2019d just wanted a random sequence of numbers, you could\u2019ve flipped a coin, and saved all the trouble of building the quantum computer!<\/p>\n Thus, the hope for a speed advantage from a quantum computer comes not from randomness, but rather, from the fact that quantum mechanics is based on amplitudes, and amplitudes work differently than probabilities.\u00a0 In particular, if an event can happen one way with a positive amplitude, and another way with a negative amplitude, those two amplitudes can \u201cinterfere destructively\u201d and cancel each other out, so that the event never happens at all.\u00a0 The goal, in quantum computing, is always to choreograph things so that for each wrong answer, some of the paths leading there have positive amplitudes and others have negative amplitudes, so they cancel each other out, while the paths leading to the right answer reinforce.<\/p>\n It\u2019s only for certain special problems that we know how to do that.\u00a0 Those problems include a few with spectacular applications to cryptography, like factoring large numbers, as well as the immensely useful problem of simulating quantum mechanics itself.\u00a0 But as far as we know today, they don\u2019t include all problems that involve trying a huge number of possible solutions.\u00a0 In particular, it looks likely that quantum computers will provide only limited advantages for the NP-complete problems (the Traveling Salesman Problem and so on), which are usually considered the holy grail of computer science.<\/p>\n It\u2019s true that, if you\u2019re trying to simulate a quantum computer using a classical computer, then as far as anyone knows, your simulation needs to keep track of exponentially many amplitudes.\u00a0 The trouble is that, unlike the classical simulation, which can read or modify any amplitude at will, a quantum computer is severely restricted in what it can do with its huge list of amplitudes.\u00a0 So, quantum algorithm design is all about how you can sometimes (but not always!) extract an answer to your problem even in the teeth of those restrictions.<\/p>\n A related misconception is that a thousand quantum bits, or qubits, are somehow equivalent to 21000 classical bits, with each additional qubit doubling the number of classical bits.\u00a0 Here\u2019s the tricky part: if you wanted to describe the state of a thousand qubits, even approximately, you would indeed need something like 21000 classical bits. \u00a0But you can\u2019t store 21000 classical bits in a thousand qubits and then reliably read them out later!\u00a0 In fact, a fundamental result called Holevo\u2019s Theorem says that the number of classical bits that you can reliably read out, by measuring a thousand qubits, is exactly one thousand: no better than if you\u2019d used a classical memory.\u00a0 Once again, what\u2019s going on is that there\u2019s this huge list of amplitudes, but quantum mechanics lets you access the list only by making a measurement, which is a destructive event that produces just a single random outcome.<\/p>\n There\u2019s a pattern here.\u00a0 In case after case, we find that if you wanted to simulate quantum mechanics classically, you\u2019d need some immense power.\u00a0 And that\u2019s given the hypesters and confuseniks this immense opening to mislead people into imagining that quantum mechanics itself must give you the same immense power.\u00a0 But that\u2019s a logical fallacy!\u00a0 It\u2019s like, maybe the only way human technology can simulate bird flight is by using propellers or jet engines.\u00a0 But even if so, that still wouldn\u2019t imply that birds themselves must use propellers or jet engines.\u00a0 They don\u2019t need to: they\u2019re birds!<\/p>\n Yet another example concerns quantum entanglement between distant particles. \u00a0John Bell famously proved in the 1960s that, if you wanted to simulate entanglement in a classical universe, then you\u2019d need faster-than-light communication.\u00a0 But, contrary to a misconception that refuses to die even today, that doesn\u2019t mean that quantum entanglement itself lets you communicate faster than light. \u00a0It doesn\u2019t!\u00a0 Our quantum universe scrupulously upholds Einstein\u2019s speed limit, even though a classical simulation of our universe would violate the limit.\u00a0 Indeed, that\u2019s a central piece of evidence that our universe really is quantum, and is not secretly classical behind the scenes.<\/p>\n This characteristic of quantum mechanics\u2014the way it stakes out an \u201cintermediate zone,\u201d where (for example) n qubits are stronger than n classical bits, but weaker than 2n classical bits, and where entanglement is stronger than classical correlation, but weaker than classical communication\u2014is so weird and subtle that no science-fiction writer would have had the imagination to invent it.\u00a0 But to me, that\u2019s what makes quantum information interesting: that this isn\u2019t a resource that fits our pre-existing categories, that we need to approach it as a genuinely new thing.\u00a0 Most of the hype that drives me nuts comes from rounding this fascinating reality down to the sorts of thing a science-fiction writer would invent, like \u201cparallelism free-for-all!\u00a0 Just try each answer in a different universe, and pick the best!\u201d<\/p>\n So far, I\u2019ve focused on \u201chype\u201d surrounding the conceptual basis of quantum computing.\u00a0 That\u2019s because I feel like, if you can just get people clear on the conceptual stuff, you\u2019ve given them 90% of what they need to think for themselves about any claimed breakthrough in quantum computing that makes it into the news\u2014to know the right questions to ask.<\/p>\n Needless to say, though, quantum computing has also seen plenty of hype of a more conventional nature.\u00a0 For example: \u201cCOMMERCIAL BREAKTHROUGH\u2014Company X has now used a quantum computer to solve real-world Problem Y a hundred million times faster than a classical computer!\u201d\u00a0 And then even the most cursory digging reveals that, no, sorry, that\u2019s only if you compare the quantum computer to a classical computer running one particular algorithm (which is far from the best known algorithm); in an apples-to-apples comparison, the quantum advantage disappears.\u00a0 And that in any case, this wasn\u2019t for a real-world instance of the \u201creal-world problem,\u201d but only for an instance tailored to the strengths of this specific piece of quantum hardware.\u00a0 And that the precise senses in which the hardware is \u201cquantum\u201d in the first place are still being debated.<\/p>\n In such cases, it\u2019s not usually that anybody lied: it\u2019s just that there was a game of \u201cTelephone,\u201d where the original company or research team explained the crucial caveats in Section 4.2 of its paper, but all the caveats had morphed into one ambiguous sentence by the press release, and had disappeared entirely by the time the thing hit the news websites.\u00a0 This sort of hype, which we\u2019ve now seen more than a decade of, might have had the ironic effect of inuring people to quantum-computing speedup claims\u2014so much that when we do finally get a genuine quantum-computing speedup, possibly in the near future, people will be less excited than they ought to be!<\/p>\n (As an analogy, the Wright Brothers\u2019 1903 flights at Kitty Hawk garnered almost no news at the time\u2014one reason being that, in the years leading up to them, there had been so many overblown claims about powered flight that newspaper readers had wearied of the subject.)<\/p>\n Anyway, my blog has dissected more examples of the latter kind of hype than is interesting to probably anyone, including me.<\/p>\n 7. Have quantum computers been in any way underappreciated?<\/p>\n Sure!\u00a0 (More generally, we could probably say: there\u2019s nothing so hyped that it doesn\u2019t have underappreciated aspects.)<\/p>\n One beautiful story, which hardly any journalists have written about, is how we\u2019ve often been able to use quantum computing to achieve a better understanding even of classical computing.\u00a0 For example, there are certain kinds of error-correcting codes that we know not to exist only because, if they did, then there would be even better quantum error-correcting codes\u2014but the latter we know how to rule out.\u00a0 That\u2019s just one of dozens of examples of how, even before practical quantum computers exist, the theory of quantum computing has become an important part of classical theoretical computer science.<\/p>\n More broadly, I\u2019d say that people underappreciate quantum computing by viewing it purely through the lens of applications.\u00a0 A quantum computer could be viewed as the most stringent test of quantum mechanics that we\u2019re going to see in our lifetimes.\u00a0 And there are smart people who believe it can\u2019t be done\u2014which to me, only heightens the interest in trying to do it still further!\u00a0 If it\u2019s worthwhile to build the LHC or LIGO\u2014wonderful machines that so far, have mostly triumphantly confirmed our existing theories\u2014then it seems at least as worthwhile to build a scalable quantum computer, and thereby prove that our universe really does have this immense computational power beneath the surface.\u00a0 Sure, there are some cool applications (with perhaps the most important being quantum simulation), but those are just icing!\u00a0 The case for building QCs would remain strong even if no applications had been found, and even if the applications that have been found turn out not to have great economic importance.\u00a0 But unfortunately, that reality has had a hard time making it to the press and funding bodies, who often want to shoehorn quantum computing into the \u201ctechnology\u201d category rather than the \u201cscience\u201d category\u2014as if it were just the latest, fastest microchip, rather than something fundamentally new.<\/p>\n 8. Could \u201cBig Data\u201d help social science become scientific?<\/p>\n I\u2019m no expert, but my impression is that in many cases it\u2019s already doing so.\u00a0 So for example, I follow with great interest the work of Jon Kleinberg, one of my former professors from Cornell, who\u2019s learned about the structure of communities by examining the Facebook graph. \u00a0Likewise, my friend Erez Lieberman-Aiden, along with Steven Pinker and others, pioneered the use of Google Books to analyze historical trends, by examining the rise and fall in the use of particular words over time.<\/p>\n On the other hand, we should be clear that a lack of data is only one factor that makes the social sciences so hard\u2014harder, I\u2019d say, than the natural sciences!\u00a0 The bigger factor, it seems to me, is that unlike (say) particle physics, no one ever approaches the social world de novo: we only ever approach it \u201calready knowing so much that ain\u2019t so.\u201d<\/p>\n In social sciences, there\u2019s an absolutely massive bias in favor of publishing results that confirm current educated opinion, or that deviate from the consensus in ways that will be seen as quirky or interesting rather than cold or cruel or politically tone-deaf.\u00a0 I have almost boundless admiration for the social scientists who are able to break through that and teach us something new\u2014as for example in the work of Judith Rich Harris, which showed how a child\u2019s \u201cnon-shared environment\u201d (the peer group and so forth) is much more important than any parenting practices in shaping personality, contrary to both \u201ccommon sense\u201d and a century of Freudian dogma.\u00a0 I couldn\u2019t do that myself.<\/p>\n 9. Do you ever worry, like some theoretical physicists, that our universe is a simulation created by superintelligent aliens?<\/p>\n Well, there are two cases: either we can communicate with these aliens, or otherwise get evidence for their existence by examining the universe, or else we can\u2019t.<\/p>\n If we can get evidence, then the aliens are basically just the gods of traditional religions, differing only in details like their motivations or how many arms they have.\u00a0 In that case, the reason to be skeptical of them is the same reason to be skeptical of traditional religions: namely, where\u2019s the evidence?\u00a0 Why have these gods\/aliens, just like the conspirators who set up Lee Harvey Oswald as a patsy, demolished the Twin Towers from the inside, etc. etc., done such a spectacular job of hiding themselves?<\/p>\n The second possibility is that the simulating aliens belong to a higher metaphysical realm, one that\u2019s empirically inaccessible to us even in principle.\u00a0 In that case, to be honest, I don\u2019t care about them!\u00a0 Given any theory of the world that we might formulate involving the aliens, we can simplify the theory by cutting the aliens out.\u00a0 They\u2019re explanatorily irrelevant.<\/p>\n 10. Could quantum-computation research help physicists achieve a unified theory?<\/p>\n There are some theoretical physicists who now think so!\u00a0 Ideas from quantum computing and quantum information have recently entered the study of the black hole information problem\u2014i.e., the question of how information can come out of a black hole, as it needs to for the ultimate laws of physics to be time-reversible.\u00a0 Related to that, quantum computing ideas have been showing up in the study of the so-called AdS\/CFT (anti de Sitter \/ conformal field theory) correspondence, which relates completely different-looking theories in different numbers of dimensions, and which some people consider the most important thing to have come out of string theory.\u00a0 I\u2019ve enjoyed being peripherally involved in these developments, as a \u201ccomputer science mercenary\u201d with little skin in the game, but who\u2019s happy to talk to anyone from any discipline (biologists, economists, string theorists, you name it) who\u2019s stumbled onto interesting theoretical computer science questions!<\/p>\n There are a few reasons why I think quantum computing ideas have been showing up lately in fundamental physics.\u00a0 Firstly, quantum computing has supplied probably the clearest language ever invented\u2014namely, the language of qubits, quantum circuits, and so on\u2014for talking about quantum mechanics itself.\u00a0 This is a language that\u2019s already seeped into optics and condensed-matter physics and quantum chemistry and various other things; no surprise to see it in quantum gravity too.\u00a0 Secondly, one of the most important things we\u2019ve learned about quantum gravity\u2014which emerged from the work of Stephen Hawking and the late Jacob Bekenstein in the 1970s\u2014is that in quantum gravity, unlike in any previous physical theory, the total number of bits (or actually qubits) that can be stored in a bounded region of space is finite rather than infinite.\u00a0 In fact, a black hole is the densest hard disk allowed by the laws of physics, and it stores a \u201cmere\u201d 1069 qubits per square meter of its event horizon!\u00a0 And because of the dark energy (the thing, discovered in 1998, that\u2019s pushing the galaxies apart at an exponential rate), the number of qubits that can be stored in our entire observable universe appears to be at most about 10122.<\/p>\n So, that immediately suggests a picture of the universe, at the Planck scale of 10-33 meters or 10-43 seconds, as this huge but finite collection of qubits being acted upon by quantum logic gates\u2014in other words, as a giant quantum computation.<\/p>\n (Having said that, I confess I\u2019m left cold by the interminable philosophical debates whether the universe \u201creally is\u201d a computation.\u00a0 Like, once you\u2019ve signed onto the reductionist program at all, it\u2019s completely obvious and unremarkable that the universe can be regarded as some sort of computation, so the only interesting questions concern which sort!\u00a0 Quantum or classical?\u00a0 How many qubits?\u00a0 Etc.)<\/p>\n Thirdly, and this is the part that\u2019s new in the last few years: some of the conceptual problems of quantum gravity turn out to involve my own field of computational complexity in a surprisingly nontrivial way.\u00a0 The connection was first made in 2013, in a remarkable paper by Daniel Harlow and Patrick Hayden.\u00a0 Harlow and Hayden were addressing the so-called \u201cfirewall paradox,\u201d which had lit the theoretical physics world on fire (har, har) over the previous year.<\/p>\n The firewall paradox involves a thought experiment where Alice\u2014it\u2019s always Alice\u2014sits outside of a black hole waiting for it to mostly but not completely evaporate, and scooping up all the Hawking radiation it emits as it does so.\u00a0 For a black hole the mass of our sun, this would take about 1067 years (we\u2019ll assume Alice has a really long grant).\u00a0 Then, Alice routes all the photons of Hawking radiation into her quantum computer, where she processes them in such a way as to prove that they did encode information about the infalling matter.\u00a0 Then, as the final step, Alice jumps into the black hole.\u00a0 The clincher is that, if you combine all the ideas about black holes that had previously been accepted, you can now make a firm prediction that Alice will encounter an end of spacetime right at the event horizon (in the physicists\u2019 colorful language, she\u2019ll \u201chit a firewall and burn up\u201d).\u00a0 But this is totally contrary to the prediction of general relativity, which says that Alice shouldn\u2019t notice anything very special at the event horizon, and should only encounter an end of spacetime at the singularity.<\/p>\n There are various ways out of this that aren\u2019t very satisfying: you could deny that information escapes from black holes. You could say that general relativity is wrong, and what we\u2019d previously called black holes are really just firewalls.\u00a0 You could argue that what happens inside a black hole isn\u2019t even within the scope of science\u2014since much like life after death, it\u2019s not empirically testable by anyone who \u201cremains on this side.\u201d\u00a0 Or\u2014and this seems like the \u201cconservative\u201d option!\u2014you could admit that Alice can create a firewall by doing this crazy processing of the Hawking radiation, but insist that, if she doesn\u2019t do the processing, then she\u2019ll pass through the event horizon just like general relativity always said she would.\u00a0 But if you take this last option, then what Alice perceives as the structure of spacetime\u2014whether she encounters an event horizon or a firewall\u2014will depend on what she programmed her quantum computer to do.<\/p>\n But we haven\u2019t even gotten yet to Harlow and Hayden\u2019s technical contribution.\u00a0 They asked, supposing Alice wanted to program her quantum computer to create a firewall, how hard of a problem would her quantum computer need to solve?\u00a0 And they gave strong evidence that the problem would require an amount of time that grows exponentially with the number of qubits in the black hole\u2014meaning, not a \u201cmere\u201d 1067 years, but 210^67 years!\u00a0 In other words: they said that if standard conjectures in theoretical computer science are true, then Alice couldn\u2019t have made a dent in the problem before the black hole had already evaporated anyway, and there was nothing to jump into.\u00a0 So maybe that makes us feel better about the whole thing!<\/p>\n Now, Harlow and Hayden\u2019s evidence that Alice\u2019s computational task was exponentially hard, even for a quantum computer, relied on the quantum lower bound for finding collision pairs that I\u2019d proved in 2002.\u00a0 Of course, when I\u2019d proved that bound, I had no idea it would have anything to do with black holes, or the computational intractability of mucking up the structure of spacetime, or anything like that!\u00a0 But once the connection was made, I sort of had no choice but to become interested.\u00a0 Recently, I\u2019ve strengthened Harlow and Hayden\u2019s result, so that now the hardness of creating a firewall no longer depends on the hardness of finding collision pairs\u2014something that I\u2019d proven was hard in the \u201cgeneric\u201d or \u201cblack-box\u201d case, but which we\u2019re less certain is hard in the case relevant to firewalls.\u00a0 Now the argument depends only on the existence of \u201cinjective one-way functions\u201d: that is, functions that are easy to compute, hard to invert even using a quantum computer, and free of all collision pairs.\u00a0 And that seems like almost as safe an assumption as NP-complete problems being hard for quantum computers.<\/p>\n More recently, in ongoing joint work with Leonard Susskind\u2014who\u2019s been sort of the godfather of this whole computational complexity \/ quantum gravity connection\u2014we\u2019ve given evidence that quantum computing theory also shows up in the AdS\/CFT correspondence.\u00a0 Specifically, if you take something geometric that happens in certain spacetimes\u2014say, a wormhole connecting two regions, which just stretches out, getting longer and longer forever\u2014there\u2019s a \u201cdual description\u201d in quantum field theory, involving a quantum state on a bunch of qubits that gets more and more complicated as time goes on.\u00a0 The way we measure \u201ccomplicated\u201d here is using what\u2019s called quantum circuit complexity: that is, the minimum number of elementary operations that a quantum computer would need to prepare the state in question, starting (let\u2019s say) from a state of all 0\u2019s.\u00a0 Susskind and I proved that, assuming certain problems (called the PSPACE-complete problems) are as hard for quantum computers as computer scientists believe they are, it follows that the circuit complexity of the state really does go up and up, in a way that matches the volume of the wormhole.<\/p>\n So, is this telling us that quantum circuit complexity plays some fundamental role in the laws of physics, analogous to more familiar quantities like length and volume and energy and entropy?\u00a0 I hesitate to say so, since the \u201cobserved correlation\u201d between complexity and volume might be explainable by some third factor.\u00a0 But at the least, quantum circuit complexity has established itself as a useful tool.<\/p>\n In summary, I predict that ideas from quantum information and computation will be helpful\u2014and possibly even essential\u2014for continued progress on the conceptual puzzles of quantum gravity. \u00a0But even if so, one thing I know for sure is that these ideas won\u2019t be sufficient!\u00a0 Even if quantum computing provides the best language ever devised for talking about quantum mechanics\u2014still, like any other language, it\u2019s only as good as what you do with it, and it\u2019s susceptible to the \u201cgarbage in \/ garbage out\u201d problem.\u00a0 Also, unlike (say) Stephen Wolfram or Ed Fredkin, I don\u2019t expect any progress to come from junking everything that\u2019s been learned in theoretical physics over the last century, and \u201cstarting afresh\u201d with classical bits and cellular automata.\u00a0 So much intelligence has already been expended on discovering the fundamental laws of nature that, if further definite progress is possible at all, I expect it to \u201ctake everything we\u2019ve got\u201d: that is, everything that\u2019s already understood about the Standard Model and general relativity, lessons from strings and AdS\/CFT and other quantum gravity proposals, insights from novel parts of mathematics (yes, possibly including theoretical computer science and quantum computation) \u2026 and needless to say, some new clues from experiment wouldn\u2019t hurt either.<\/p>\n 11. Will science ever explain why there\u2019s something rather than nothing?<\/p>\n By definition, I\u2019d say, a \u201cscientific explanation\u201d means a causal lever: that is, some aspect of reality that you could toggle in order to turn the thing you\u2019re trying to explain on or off.\u00a0 For example, the earth\u2019s tilt is a good explanation for the seasons, because if you untilted the earth, you\u2019d get no more seasons.\u00a0 But what lever could you toggle in order for there never to have been anything?\u00a0 Whatever it was, the lever itself would presumably be \u201csomething\u201d!\u00a0 Even if flipping the lever caused everything (including the lever itself) to blink out of existence, the lever still would have existed, and its previous existence would remain unexplained.<\/p>\n So that leaves only logical or mathematical explanations.\u00a0 I\u2019ve heard people wax poetic about the possibility of discovering equations of physics so compelling that they \u201cforce\u201d there to exist a universe for them to describe, or something like that.\u00a0 But that\u2019s always struck me as just a category error!\u00a0 The most beautiful equation is as happy as a clam for none of its solutions to have any physical reality, or any reality that\u2019s consciously experienced by anyone.\u00a0 (Of course, if nothing existed, then we wouldn\u2019t be here to talk about it\u2014but that observation, while correct, doesn\u2019t really deserve to be dignified with the name \u201cexplanation\u201d!)<\/p>\n So I\u2019d say no: because of the very nature of explanations, there can\u2019t be an explanation (scientific or otherwise) for why there\u2019s something rather than nothing.<\/p>\n 12. Could quantum-computation research help solve the mind-body problem?<\/p>\n What, so it\u2019s not enough to break most of the world\u2019s cryptography, simulate the universe at the atomic scale, and possibly even give crucial insights about quantum gravity?\u00a0 You also want us to solve the mind-body problem??<\/p>\n I should confess to extreme skepticism that there can even exist a \u201csolution\u201d to the mind-body problem. \u00a0The reason is that, no matter what scientific theory Alice proposed for consciousness, Bob could always come along and say \u201caha, but you\u2019ve merely given me another causal mechanism; you haven\u2019t explained what truly lights the spark of Mind!\u201d<\/p>\n On the other hand, I can tell you that David Deutsch, who along with Richard Feynman was one of the inventors of quantum computing, became interested in the subject for reasons that were deeply entangled (har, har) with the mind-body problem.\u00a0 Deutsch was, and remains, a diehard proponent of the Many-Worlds Interpretation of quantum mechanics. \u00a0The MWI, as you know, posits that quantum states never \u201ccollapse\u201d on being \u201cmeasured\u201d\u2014that instead, we should just apply quantum mechanics\u2019 equations consistently to the whole universe, in which case, the universe itself would have to be in a quantum superposition state, containing trillions of parallel copies of us living slightly different lives.\u00a0 And Deutsch asked the question, which I\u2019m sure resonates with you: how could one ever experimentally test the Many-Worlds picture?<\/p>\n Here Deutsch had the following thought: suppose you could do a quantum-mechanical interference experiment on yourself.\u00a0 That is, rather than sending a photon or a buckyball or whatever through Slit A with some amplitude and through Slit B with some other amplitude, suppose you could do the same thing with your own brain.\u00a0 And suppose you could then cause the two parallel \u201cbranches\u201d of your experience to come back together and interfere.\u00a0 In that case, it seems you could no longer describe your experience using the traditional Copenhagen interpretation, according to which \u201cthe buck stops\u201d\u2014the wave of amplitudes probabilistically collapses to a definite outcome\u2014somewhere between the system you\u2019re measuring and your own consciousness.\u00a0 For where could you put the \u201ccollapse\u201d in this case? \u00a0You can\u2019t have Bohr and Heisenberg\u2019s famous divide between \u201cthe observer\u201d and the \u201cthe quantum system\u201d if the observer is the quantum system!<\/p>\n Now, your brain is such a big, hot, wet object, with so many uncontrolled degrees of freedom coupled to the external environment, that even a hyper-advanced civilization of the far future might never be able to do the experiment I just described.\u00a0 But, OK, what if we could build an artificially-intelligent computer, have everyone agree that the computer was \u201cconscious,\u201d and then put it in a superposition of thinking two different thoughts and measure the interference pattern?\u00a0 At that point, everyone would have to accept that conscious entities can exist in superposition states, just like the Many-Worlds Interpretation always said!<\/p>\n As you can see, Deutsch wasn’t trying to \u201csolve\u201d the mind-body problem, but he was perhaps pointing out a new aspect of it.\u00a0 For hundreds of years people asked: is your having a mind, a soul, compatible with someone else knowing your complete \u201ccode\u201d: for example, the exact state of every subatomic particle in your brain?\u00a0 Quantum mechanics lets us ask a related question: is your having a mind compatible with someone else being able to manipulate you in superposition, with their seeing the interference between two versions of you that think different thoughts?<\/p>\n Now, after pondering the latter question for a while, we might want to step back and ask some \u201ceasier\u201d variants. \u00a0For example, could there be, if not a mind, then at least a computer that performed a superposition of several different computations, such that we could then learn something interesting by examining the interference between the branches?\u00a0 Could such a computer actually be built?\u00a0 So, that\u2019s sort of a cartoon version of how Deutsch came up with quantum computing.<\/p>\n To eliminate any chance of misunderstanding: my prediction is that yes, useful quantum computers will eventually be built, and their existence will probably have some impact on how quantum mechanics is perceived in our culture, and as a consequence, on how people talk about whether consciousness collapses the state vector and things of that kind.\u00a0 But on the whole, the mind-body problem will remain just as contentious and seemingly unresolvable as it was in the world with only classical computers and not quantum ones\u2014or as it was in our previous world, the one with no programmable computers at all.<\/p>\n 13. Why is the P versus NP Problem important? Is it solvable?<\/p>\n P versus NP is a contender for the most important unsolved problem in math.\u00a0 For those tuning in from home, P stands for Polynomial Time. \u00a0It\u2019s the class of all yes-or-no problems that a digital computer can solve \u201cefficiently\u201d\u2014meaning, using a number of steps that grows at most like the number of bits needed to specify the problem raised to some fixed power.\u00a0 Some examples are: I give you a map, and I ask whether every town is at most 200 miles from every other.\u00a0 Or I give you a positive integer, and I ask whether it\u2019s prime.\u00a0 NP stands for Nondeterministic Polynomial-Time.\u00a0 It\u2019s the class of yes-or-no problems for which, if the answer is \u201cyes,\u201d there\u2019s a short proof that a computer can efficiently check.\u00a0 An example of an NP problem is: I give you a positive integer, and I ask whether it has at least five divisors.\u00a0 No one knows a fast algorithm for the latter problem: indeed, the presumed hardness of this sort of problem (for classical computers, anyway!) is the basis for most modern cryptography.\u00a0 Still, if the answer is \u201cyes,\u201d you could prove it to someone by just showing them the divisors.<\/p>\n Clearly P is contained in NP, since if you can solve a problem yourself, you can also be convinced that it\u2019s solvable.\u00a0 The question is whether NP is contained in P: in other words, if computers can quickly check an answer to something, can they also quickly find an answer?\u00a0 Most people conjecture that the answer is no\u2014that is, P\u2260NP\u2014because it seems obvious that there are some puzzles, like (say) a giant Sudoku, where it\u2019s easy to check if someone else solved them, but solving them yourself would require examining an astronomical number of possibilities.\u00a0 I like to joke that if we were physicists, we would\u2019ve simply declared P\u2260NP to be a \u201claw of nature,\u201d and given ourselves Nobel Prizes for our \u201cdiscovery\u201d!\u00a0 Still, after more than half a century, no one has mathematically proven P\u2260NP: no one has ruled out that all these NP problems might have a super-fast algorithm that avoids brute-force search and cuts straight to the answer.<\/p>\n Why is the problem important?\u00a0 The Clay Mathematics Institute chose it as one of the seven great math problems of our time (alongside the Riemann Hypothesis and five others), each of which carries a million-dollar prize\u2014but that\u2019s honestly the least of it.\u00a0 For one thing, P vs. NP is the only one of the seven Clay problems that has obvious practical implications.\u00a0 For example, breaking almost any cryptographic code can be phrased as an NP problem.\u00a0 So if P=NP\u2014and if, moreover, the algorithm that proved it was \u201cpractical\u201d (meaning, not n1000 time or anything silly like that)\u2014then all cryptographic codes that depend on the adversary having limited computing power would be broken.\u00a0 Unlike with (say) Shor\u2019s factoring algorithm, this wouldn\u2019t apply only to special forms of cryptography that happen to be popular today, and it also wouldn\u2019t require the codebreakers to build a new kind of computer. \u00a0It would mean that we\u2019d grossly underestimated the abilities of our existing computers.<\/p>\n Beyond cryptography, a huge fraction of the \u201chardest\u201d things we try to do with computers\u2014for example, designing a drug that binds to a receptor in the right way, designing an airplane wing that minimizes drag, finding the optimal setting of parameters in a neural network, scheduling a factory\u2019s production line to minimize downtime, etc., etc.\u2014can be phrased as NP problems.\u00a0 If P=NP (and the algorithm was practical, yadda yadda), we\u2019d have a general-purpose way to solve all such problems quickly and optimally, which wouldn\u2019t require any special insight into individual problem domains.<\/p>\n But even those applications aren\u2019t what personally interest me, as much as the way P vs. NP asks about the nature of mathematical creativity itself. That\u2019s the motivation Kurt G\u00f6del offered in 1956, when he posed P vs. NP for possibly the first time, in a now-famous letter to John von Neumann.\u00a0 As G\u00f6del pointed out in his letter, if mathematical proofs are written in a sufficiently hairsplitting way (like in Russell and Whitehead\u2019s Principia Mathematica), then it\u2019s easy to write a fast computer program that checks, line-by-line, whether a given proof is valid.\u00a0 That means there\u2019s also a program to check whether a given statement has a proof that\u2019s at most n symbols long: such a program just needs to try every possible combination of symbols, one after the next (like in Borges\u2019 Library of Babel), and see whether any of them constitute a valid proof.\u00a0 What\u2019s not obvious is whether there\u2019s a program to find a proof of length n, whenever one exists, using a number of steps that grows only like n or n2, rather than like 2n.\u00a0 That question is essentially P vs. NP.<\/p>\n So if you found a fast computer program to find short proofs, then yes, that would solve one of the seven million-dollar prize problems.\u00a0 But it would also solve the other six!\u00a0 For it would mean that, if the Riemann Hypothesis, the Hodge Conjecture, and so forth had proofs of a reasonable length at all, then you could just program your computer to find those proofs for you.\u00a0 The way G\u00f6del put it was that, if P=NP in a practical way, then \u201cthe mental effort of the mathematician could be completely replaced by machines (apart from the postulation of axioms).\u201d<\/p>\n Indeed, it\u2019s easy to get carried away, and wax too poetic about the P vs. NP problem\u2019s metaphysical enormity\u2014as I\u2019ve sometimes been accused of doing!\u00a0 So let me be clear: P vs. NP is not asking whether the human mind can solve problems that digital computers can\u2019t, which is the much more familiar question surrounding artificial intelligence.\u00a0 Even if (as most of us think) P\u2260NP, that still might not prevent a Singularity or a robot uprising, since the robots wouldn\u2019t need to solve all NP problems in polynomial time: they\u2019d merely need to be smarter than us!\u00a0 Conversely, if P=NP, that would mean that any kind of creative product your computer could efficiently recognize, it could also efficiently create.\u00a0 But if you wanted to build an AI Beethoven or an AI Shakespeare, you\u2019d still face the challenge of writing a computer program that could recognize great music or literature when shown them.<\/p>\n So, that\u2019s the importance of P vs. NP.\u00a0 Is it solvable?\u00a0 The short answer: right now, there\u2019s no compelling reason to think it isn\u2019t!\u00a0 But it almost certainly won\u2019t get solved anytime soon.<\/p>\n For P vs. NP to be unsolvable would presumably mean that the truth, whatever it was, was unprovable from the usual axioms of set theory.\u00a0 G\u00f6del taught us that that\u2019s indeed a possibility for essentially any unsolved math problem, with a few exceptions (like the question of whether White has a forced win in chess, which reduces to a huge but finite calculation).\u00a0 But OK, it was just as much a possibility that Fermat\u2019s Last Theorem would be unsolvable before Andrew Wiles came along and solved it in 1993, and likewise with the Poincar\u00e9 Conjecture and pretty much everything else in this business!\u00a0 The truth is that, since its discovery in 1931, the \u201cG\u00f6delian gremlin\u201d has reared its head only very rarely, and then usually for questions involving transfinite set theory, which P vs. NP is not.<\/p>\n So I\u2019d say it\u2019s like anything else in science: sure, you can\u2019t know for sure that your problem is solvable until you\u2019ve solved it.\u00a0 But as long as you keep discovering interesting things along the way (as we have been, in this case), it would be silly to give up.<\/p>\n There are two further points.\u00a0 First, almost no one in theoretical computer science\u2014not counting the cranks, whose missives fill my inbox every week!\u2014spends their time directly trying to prove P\u2260NP.\u00a0 Why not?\u00a0 For the same reason why you wouldn\u2019t embark on a manned mission to another galaxy, if you hadn\u2019t even set foot on Mars yet.\u00a0 There are vastly \u201ceasier\u201d conjectures than P\u2260NP\u2014for example, focusing on severely restricted types of algorithms\u2014that we already don\u2019t know how to prove, so those are the obvious places to start.\u00a0 Mathematicians and computer scientists have made progress on those easier conjectures, though the progress has taken decades and has run up against profound barriers\u2014some of which were heroically circumvented, only to hit new barriers, and so on.\u00a0 On the one hand, this progress is what makes me optimistic that further breakthroughs are possible; on the other, it gives a sense for how far there still is to go.<\/p>\n Which brings me to the second point: even assuming P\u2260NP, I don\u2019t think there\u2019s any great mystery about why a proof has remained elusive.\u00a0 I mean, Fermat\u2019s Last Theorem took 350 years from the statement to the proof, while the impossibility of squaring the circle took two millennia.\u00a0 And here we\u2019ve only had, what, a half-century?\u00a0 And doesn\u2019t P\u2260NP itself tell us that even easy-to-recognize solutions can be astronomically hard to find?<\/p>\n More seriously, it was realized in the 1970s that techniques borrowed from mathematical logic\u2014the ones that G\u00f6del and Turing wielded to such great effect in the 1930s\u2014can\u2019t possibly work, by themselves, to resolve P vs. NP.\u00a0 Then, in the 1980s, there were some spectacular successes, using techniques from combinatorics, to prove limitations on restricted types of algorithms. \u00a0Some experts felt that a proof of P\u2260NP was right around the corner.\u00a0 But in the 1990s, Alexander Razborov and Steven Rudich discovered something mind-blowing: that the combinatorial techniques from the 1980s, if pushed just slightly further, would start \u201cbiting themselves in the rear end,\u201d and would prove NP problems to be easier at the same time they were proving them to be harder!\u00a0 Since it\u2019s no good to have a proof that also proves the opposite of what it set out to prove, new ideas were again needed to break the impasse.<\/p>\n By the mid-2000s, we had results that evaded both the logic barrier identified in the 1970s, and the combinatorics barrier identified in the 1990s.\u00a0 But then Avi Wigderson and I demonstrated in 2007 that there\u2019s a third barrier, to which even those new results were subject.\u00a0 And then in 2011, Ryan Williams achieved the next breakthrough: basically, he separated a class of problems that\u2019s vastly smaller than P from another class that\u2019s vastly larger than NP.\u00a0 This was important less because of the result itself\u2014which still looks pathetically weak compared to P\u2260NP\u2014but rather, because his proof circumvented all the known barriers to further progress.<\/p>\n Nowadays there are people trying to attack P-vs.-NP-like questions using some of the heaviest artillery available from algebraic geometry, representation theory, and other parts of mathematics, and we don\u2019t yet know where it\u2019s going to lead, but meanwhile there have been surprises every few years, and previously impossible-looking problems that suddenly get solved, and unexpected connections to other parts of math and to practical cryptography and to algorithm design, and of course quantum computing forcing us to reexamine the entire subject from a different angle, and altogether that\u2019s been more than enough to keep the field thriving.<\/p>\n In summary, I don\u2019t think P vs. NP presents a good example for your \u201cEnd of Science\u201d thesis!\u00a0 For one thing, there\u2019s no danger of \u201cironic science\u201d here: for all the broader issues that it touches on, P vs. NP is still \u201cjust a math problem,\u201d meaning that we understand exactly what\u2019s being asked and what would or wouldn\u2019t constitute a solution.\u00a0 And math is cumulative.\u00a0 With some problems there\u2019s a gap of two hundred years between one insight and the next; other times the ideas come every hour\u2014but either way, the ocean of mathematical understanding just keeps monotonically rising, and we\u2019ve seen it reach peaks like Fermat\u2019s Last Theorem that had once been synonyms for hopelessness.\u00a0 I see absolutely no reason why the same ocean can\u2019t someday swallow P vs. NP, provided our civilization lasts long enough.\u00a0 In fact, whether our civilization will last long enough is by far my biggest uncertainty.<\/p>\n 14. Do you believe in the Singularity?<\/p>\n I think that, if civilization lasts long enough, then sure: eventually we might need to worry about the creation of an AI that is to us as we are to garden slugs, and about how to increase the chance that such an AI will be \u201cfriendly\u201d to human values (rather than, say, converting the entire observable universe into paperclips, because that\u2019s what it was mistakenly programmed to want).\u00a0 Also, someday we might be able to transfer our consciousnesses into a computer cloud and live for billions of years in a simulated paradise.\u00a0 I don\u2019t know anything in the laws of math or physics to rule these things out, which is just another way of saying that for all I know, they\u2019re possible!<\/p>\n I even support a few people spending their lives thinking about these possibilities.\u00a0 I\u2019m friendly with many of the people who do spend their lives that way; I enjoy talking to them when they pass through town (or when I pass through the Bay Area, where they congregate).\u00a0 And maybe the work they\u2019re doing on \u201cAI safety\u201d will have unexpected spin-off applications for the world of today\u2014stranger things have happened.<\/p>\n One other thing: if you want me to rush to the Singularity community\u2019s defense, the way to do it is to tell me that they\u2019re a weirdo nerd cult that worships a high-school dropout and his Harry Potter fanfiction, so how could anyone possibly take their ideas seriously?\u00a0 It\u2019s not just the invalidity of the ad hominem argument that will turn my eyes red\u2014rather, it\u2019s that this particular kind of ad hominem (\u201cthese nerds violate our social norms, so we need not consider the truth or falsehood of what they say\u201d) has had such an abysmal track record over the centuries.<\/p>\n Look, I\u2019ve debated Eliezer Yudkowsky repeatedly; he and I have disagreed more often than we\u2019ve agreed (of course, that\u2019s partly a function of not needing to waste time on our many areas of agreement).\u00a0 But Eliezer is obviously someone you read<\/a> if you care about big questions!\u00a0 And not only is it irrelevant to that determination whether he graduated high school, but for all it matters he could wear a Spiderman costume while smearing his arguments in watercolor.<\/p>\n Having said that, my own view is that, if our sorry civilization is to survive long enough for unfriendly AI to become the main concern, there are many other existential dangers that we\u2019ll probably need to handle first.\u00a0 Like, I dunno, global warming, running out of fresh water, nuclear-armed theocrats, the constant backsliding on this Enlightenment business?\u00a0 In which case, working directly on AI safety might be like working directly on P vs. NP: why not start with \u201ceasier\u201d challenges that are probably prerequisites anyway?<\/p>\n Speaking of which, when I look at the thrilling advances being achieved today in AI, I see all sorts of ethical issues that will need to be dealt with soon\u2014like, how can a deep neural network justify to you why it turned down your loan application?\u00a0 Should self-driving cars handle crashes using utilitarian or deontological ethics?\u00a0 But these are all issues where we can try things out, learn from our mistakes, and iterate\u2014arguably, the only way human beings have ever mastered anything.\u00a0 And that gives these issues a very different character from the Singularity, which (it\u2019s often stressed) we have only one chance to get right.<\/p>\n The trouble, I\u2019d say, is that as a species, we have no idea how to get right things that we have only one chance to get right.\u00a0 Of course, if we needed to get something right (say) ten years from now, we\u2019d have no choice but to try anyway.\u00a0 But crucially, my Singularity friends\u2019 estimated timescales for developing a human-level AI have always struck me as \u2026 on the aggressive side.\u00a0 It\u2019s not like I have an alternate timescale, or even a probability distribution over timescales, about which I\u2019d profess more confidence.\u00a0 It\u2019s just that the uncertainties strike me as so large, right now, that I don\u2019t see how we can profitably use our estimates to guide our actions.\u00a0 So for example, whatever research I might do on friendly AI, how could I know that it wasn\u2019t actually increasing the probability of an AI cataclysm\u2014for example, by uncovering the secrets of AI too early, or by giving the world a false sense of security?\u00a0 (It\u2019s analogous to the old question: even if you agree in principle with Pascal about his Wager, how do you know you\u2019re not praying to the wrong god and thereby bringing down hellfire on yourself?)\u00a0 This isn\u2019t just one-size-fits-all skepticism: rather, it\u2019s specific to problems where I have neither rigorous math nor empirical data to show me what I\u2019m doing wrong and how to improve for next time.<\/p>\n Anyway, these are the reasons why, even though I completely agree that a Singularity is possible, it probably doesn\u2019t crack the top ten of the things that keep me awake at night.<\/p>\n 15. Do you believe in free will?<\/p>\n By definition, if you knew the complete state of the universe, you could use it to calculate everything I\u2019d do in the future.\u00a0 (Or at least, calculate the exact probabilities for everything I could do, which seems equally constraining for me!)\u00a0 In that sense, everything we do today was determined\u2014or at least, probabilistically determined\u2014by the universe\u2019s state at the Big Bang, and that\u2019s necessarily true regardless of any actual facts about what kind of world we live in.<\/p>\n On the other hand, precisely because this sort of determinism holds in any imaginable universe, my view is that it\u2019s not a determinism that has \u201cfangs,\u201d or that could credibly threaten any notion of free will worth talking about.\u00a0 To put it bluntly, I don\u2019t care if God knows my future choices, unless God\u2019s knowledge can somehow be made manifest in the physical world, and used to predict my choices!<\/p>\n For me, the interesting questions about free will all concern whether, as a being within the universe, you could know the state of the universe in enough detail to predict what I\u2019d do: whether, for example, you could get all the information about my brain without killing me in the process.\u00a0 For again, my choices are clearly determined by something physical.\u00a0 But it follows that \u201cdeterminism\u201d can\u2019t possibly be the relevant issue, because it\u2019s too trivial: the real questions concern someone else\u2019s ability to know what you\u2019re going to do before you do it.<\/p>\n Thus, suppose it were possible, in some remote future, to upload yourself to Google\u2019s cloud, make an unlimited number of copies of your brain state, run them forward or backward, and use the copies to predict exactly what you\u2019d do at a given time in response to which stimulus (or even just the probability that you\u2019d do one thing versus another).\u00a0 I\u2019m not talking about using some fMRI scan to guess which button you\u2019re going to push a few seconds in advance, two-thirds of the time: I\u2019m talking about nearly-perfect, science-fiction levels of accuracy.<\/p>\n In that case, it\u2019s hard for me to see what more science could say in favor of \u201cfree will not existing\u201d!\u00a0 And yes, I know there are people who passionately defend the position that, even if a computer in the next room perfectly predicted everything they would do before they did it, \u201cthey\u2019d still have free will,\u201d because what does the computer in the other room have to do with anything?\u00a0 But to me, that just seems like a failure to carry the thought experiment to its logical conclusion.\u00a0 The issue is that, by purely behavioral standards (let\u2019s say, the standards of the Turing Test), the computer has every bit as much right to be called \u201cyou\u201d as the flesh-and-blood version does!\u00a0 Whatever is the most the deepest, intimate thing you\u2019ll ever say\u2014a declaration of love for your spouse, whatever\u2014the computer (by assumption) would say it in just the same way, so that your spouse couldn\u2019t even tell which one they were talking to.<\/p>\n In short, it seems to me that the prediction machine would demolish many people\u2019s carefully-crafted two-state solution, where your choices are \u201cpredictable in theory, but not in practice,\u201d so it\u2019s \u201cjust as if you have free will\u201d even if you don\u2019t, and we can all go home happy.\u00a0 In a world with prediction machines, your choices would be predictable in practice, and it wouldn\u2019t seem as if you had free will.\u00a0 Everything you did could be fully traced to causal antecedents external to you, plus pure randomness\u2014not in some philosophical imagination, but for real, and on a routine basis.\u00a0 So rather than torture words, why not simply admit that in this world, free will would\u2019ve been unmasked as an illusion?<\/p>\n And conversely: if scanning my brain state, duplicating it like computer software, etc. were somehow shown to be fundamentally impossible, then I don\u2019t know what more science could possibly say in favor of \u201cfree will being real\u201d!<\/p>\n A few years ago, I wrote a long essay on these issues called \u201cThe Ghost in the Quantum Turing Machine<\/a>.\u201d\u00a0\u00a0There, I took the position that we simply don\u2019t know yet to what extent you can scan, copy, and predict something like a human brain without destroying its state: it\u2019s an open empirical question.\u00a0 On the one hand, quantum mechanics\u2019 No-Cloning Theorem says that you can\u2019t make an exact copy of an unknown physical system\u2014and even a microscopic detail that you missed could in principle get chaotically amplified, and could completely change someone\u2019s behavior.\u00a0 On the other hand, my Singularity friends expect that all the information in a brain that\u2019s relevant to cognition will be stored in macroscopic degrees of freedom\u2014like the strengths and connection patterns of synapses\u2014that we could easily imagine the nanotechnology of the far future scanning and copying to whatever accuracy is needed.\u00a0 So, I hope progress in science and engineering teaches us more\u2014just like progress in physics, biology, math, and other fields shifted the grounds of other philosophical debates that had once seemed ethereal.<\/p>\n (As I once saw it wonderfully put: after G\u00f6del\u2019s Theorem, all the different camps of mathematical philosophers were still at the table, but at least they all needed to reshuffle their cards!\u00a0 We can hope that scientific progress will cause a similar card-reshuffling among the various free-will camps.)<\/p>\n In summary, I\u2019d say that you can define \u201cfree will\u201d in boring, tautological ways where we either obviously have it or obviously don\u2019t, with no need to leave our armchairs and study the world!\u00a0 But there\u2019s also an interesting, fruitful way to define \u201cfree will\u201d\u2014as an in-principle unpredictability of some of our choices by external agents, going beyond the merely probabilistic\u2014where it\u2019s not known today whether we have that or not, but conceivably the science of the future could tell us.\u00a0 And that seems like a point worth appreciating.<\/p>\n 16. What\u2019s your utopia?<\/p>\n Since I hang out with Singularity people so much, part of me reflexively responds: \u201cutopia\u201d could only mean an infinite number of sentient beings living in simulated paradises of their own choosing, racking up an infinite amount of utility.\u00a0 If such a being wants challenge and adventure, then challenge and adventure is what it gets; if nonstop sex, then nonstop sex; if a proof of P\u2260NP, then a proof of P\u2260NP.\u00a0 (Or the being could choose all three: it\u2019s utopia, after all!)<\/p>\n Over a shorter time horizon, though, maybe the best I can do is talk about what I love and what I hate.\u00a0 I love when the human race gains new knowledge, in math or history or anything else.\u00a0 I love when important decisions fall into the hands of people who constantly second-guess themselves and worry that their own \u2018tribe\u2019 might be mistaken, who are curious about science and have a sense of the ironic and absurd.\u00a0 I love when society\u2019s outcasts, like Alan Turing or Michael Burry (who predicted the subprime mortgage crisis), force everyone else to pay attention to them by being inconveniently right.\u00a0 And whenever I read yet another thinkpiece about the problems with \u201cnarrow-minded STEM nerds\u201d\u2014how we\u2019re basically narcissistic children, lacking empathy and social skills, etc. etc.\u2014I think to myself, \u201cthen let everyone else be as narrow and narcissistic as most of the STEM nerds I know; I have no further wish for the human race.\u201d<\/p>\n On the other side, I hate the irreversible loss of anything\u2014whether that means the deaths of individuals, the burning of the Library of Alexandria, genocides, the flooding of coastal cities as the earth warms, or the extinction of species.\u00a0 I hate when the people in power are ones who just go with their gut, or their faith, or their tribe, or their dialectical materialism, and who don\u2019t even feel self-conscious about the lack of error-correcting machinery in their methods for learning about the world.\u00a0 I hate when kids with a passion for some topic have that passion beaten out of them in school, and then when they succeed anyway in pursuing the passion, they\u2019re called stuck-up, privileged elitists.\u00a0 I hate the \u201cmacro\u201d version of the same schoolyard phenomenon, which recurs throughout cultures and history: the one where some minority is spat on and despised, manages to succeed anyway at something the world values, and is then despised even more because of its success.<\/p>\n So, until the Singularity arrives, I suppose my vision of utopia is simply more of what I love and less of what I hate!<\/p>\n Addendum:\u00a0After I posted the Q&A, Aaronson emailed me the following clarification regarding\u00a0the end of science:<\/p>\n Incidentally, you say that I disagree with you about the end of science, but that\u2019s only partly true. \u00a0I actually think you’re more right than most scientists are willing to admit about how much of the science presented as \u201crevolutionary\u201d today consists of confirmations, minor tweaks, or applications of theories from the early 20th century or earlier that have remained stable since that time.<\/p>\n Having said that, I also think:<\/p>\n – Math (and its cousin computer science) are infinite, and are about as healthy as one would expect given their infinitude.<\/p>\n – Just in the fields that I know something about, NP-completeness, public-key cryptography, Shor\u2019s algorithm, the dark energy, the Hawking-Bekenstein entropy of black holes, and holographic dualities are six examples of fundamental discoveries from the 1970s to the 1990s that seem able to hold their heads high against almost anything discovered earlier (if not quite relativity or evolution).<\/p>\n – If civilization lasts long enough, then there\u2019s absolutely no reason why there couldn\u2019t be further discoveries about the natural world as fundamental as relativity or evolution. \u00a0One possible example would be an experimentally-confirmed theory of a discrete structure underlying space and time, which the black-hole entropy gives us some reason to suspect is there. \u00a0Another example would be a discovery of extraterrestrial life, and\/or a theory that successfully explained how common life is in our universe. \u00a0But of course, I have no idea whether we\u2019ll survive long enough for any of these things to happen, just like I don\u2019t know if we\u2019ll survive long enough to prove P\u2260NP.<\/p>\n Here I\u2019m setting aside the merely personal\/emotional aspects, of hoping you\u2019re wrong, and of directing my own energies toward parts of science where your thesis feels more wrong to me than it does elsewhere!<\/p>\n Further Reading:<\/p>\n See my Q&As with Sabine Hossenfelder<\/a>, Steven Weinberg<\/a>, George Ellis<\/a>, Carlo Rovelli<\/a>, Edward Witten<\/a>, Garrett Lisi<\/a>, Paul Steinhardt<\/a>, Lee Smolin<\/a>, Eliezer Yudkowsky<\/a>, Stuart Kauffman<\/a>, Christof Koch<\/a> and Rupert Sheldrake<\/a>.<\/p>\n Meta-post: Horgan Posts\u00a0on Brain and Mind Science<\/a>.<\/p>\n