{"id":613,"date":"2011-05-03T01:57:22","date_gmt":"2011-05-03T06:57:22","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=613"},"modified":"2017-01-12T17:06:06","modified_gmt":"2017-01-12T22:06:06","slug":"better-late-than-never","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=613","title":{"rendered":"Better late than never"},"content":{"rendered":"

No, I’m not talking about Osama, but about my reactions below to a New Yorker<\/em> article about quantum computing—reactions whose writing was rudely interrupted by last night’s news.\u00a0 Of all the possible times<\/em> in the past decade to get him, they had to pick one that would overshadow an important Shtetl-Optimized<\/em> discussion about complexity theory, the Many-Worlds Interpretation, and the popularization of science?\u00a0 Well, I guess I’ll let it slide.<\/p>\n

\n

As already discussed on Peter Woit’s blog<\/a>, this week’s New Yorker<\/em> has a long piece about quantum computing<\/a> by the novelist Rivka Galchen (unfortunately the article is behind a paywall).\u00a0 Most of the article is about the quantum computing pioneer David Deutsch: his genius, his eccentricity, his certainty that parallel universes exist, his insistence on rational explanations for everything, his disdain for “intellectual obfuscators” (of whom Niels Bohr is a favorite example), his indifference to most of the problems that occupy other quantum computing researchers, the messiness of his house, his reluctance to leave his house, and his love of the TV show House<\/em>.<\/p>\n

Having spent a wonderful, mind-expanding day with Deutsch in 2002—at his house in Oxford, of course—I can personally vouch for all of the above (except the part about House<\/em>, which hadn’t yet debuted then).\u00a0 On the one hand, Deutsch is one of the most brilliant conversationalists I’ve ever encountered; on the other hand, I was astonished to find myself, as a second-year graduate student, explaining to the father of quantum computing what BQP<\/a> was.\u00a0 So basically, David Deutsch is someone who merits a New Yorker<\/em> profile if anyone does.\u00a0 And I was pleased to see Galchen skillfully leveraging Deutsch’s highly-profilable personality to expose a lay audience (well, OK, a chardonnay-sipping Manhattan socialite audience) to some of the great questions of science and philosophy.<\/p>\n

However, reading this article also depressed me, as it dawned on me that the entire thing could have <\/em> been written fifteen years ago, with only minor changes to the parts about experiment and zero change to the theoretical parts.\u00a0 I thought: “has there really<\/em> been that little progress in quantum computing theory the past decade and a half—at least progress that a New Yorker<\/em> reader would care about?”\u00a0 Even the sociological observations are dated: Galchen writes about interest in quantum computing as the “Oxford flu,” rather than the “Waterloo flu” or “Caltech flu” that it’s been since 2000 or so (the latter two capitals of the field aren’t even mentioned!).\u00a0 A good analogy would be an article about the Web, published today<\/em>, that described the strange and exciting new world of Netscape, HotBot, and AltaVista.<\/p>\n

\n

A more serious issue is that the article falls victim to almost every misleading pop-science trope about quantum computing that some of us have trying to correct for the past decade.\u00a0 For example:<\/p>\n

With one millionth of the hardware of an ordinary laptop, a quantum computer could store as many bits of information as there are particles in the universe.<\/p>\n

Noooooo!\u00a0 That’s only for an extremely strange definition of “store”…<\/p>\n

Oxford’s eight-qubit quantum computer has significantly less computational power than an abacus, but fifty to a hundred qubits could make something as powerful as any laptop.<\/p>\n

Noooooo!\u00a0 <\/em>Fifty to a hundred qubits could maybe<\/em> replace your laptop, if<\/em> the only thing you wanted to use your laptop for<\/em> was simulating a system of fifty to a hundred qubits…<\/p>\n

In a 1985 paper, Deutsch pointed out that, because Turing was working with classical physics, his universal computer could imitate only a subset of possible computers.\u00a0 Turing’s theory needed to account for quantum mechanics if its logic was to hold.\u00a0 Deutsch proposed a universal quantum computer based on quantum physics, which would have calculating powers that Turing’s computer (even in theory) could not simulate.<\/p>\n

There are at least three problems here.\u00a0 The first is conflating simulation with efficient<\/em> simulation.\u00a0 At the risk of going hoarse, a classical Turing machine can calculate absolutely everything that a quantum computer can calculate! <\/strong>It might “merely” need exponentially more time.\u00a0 Second, no one has proved that a classical Turing machine really does<\/em> need exponentially more time, i.e., that it can’t efficiently simulate a quantum computer.\u00a0 That remains a (deep, plausible, and widely-believed) conjecture<\/em>, which will take enormous mathematical advances to resolve.\u00a0 And third, Deutsch’s landmark paper wasn’t among the ones to give evidence<\/em> for that conjecture.\u00a0 The first such evidence only came later, with the work of Bernstein-Vazirani, Simon, and Shor.<\/p>\n

To be fair to Galchen, Deutsch himself has often been inaccurate on these points, even though he ought to (and does!) know better.\u00a0 Specifically, he conflates the original Church-Turing Thesis<\/a> (which isn’t challenged in the slightest<\/em> by quantum computing) with its modern, polynomial-time version (which is), and he neglects to mention the conjectural<\/em> status of quantum computers’ speedup.\u00a0 Here are two examples out of many, from The Fabric of Reality<\/em>:<\/p>\n

“quantum computers can perform computations of which no (human) mathematician will ever, even in principle, be capable.”
\n“if the visible universe were the extent of physical reality, physical reality would not even remotely contain the resources required to factorize such a large number.”<\/p>\n

Am I just harping over technicalities here?\u00a0 In my view, the issue goes deeper.\u00a0 All of the above oversights can be understood as symptoms of complexophobia<\/strong><\/span>: the fear of acknowledging that one is actually making statements about computational complexity theory<\/em>.\u00a0 Again and again, I’ve seen science writers go through strange verbal contortions to avoid the question of how anyone could know that a computation inherently requires a huge amount of time<\/em>—as if the reader must be prevented, at all costs, from seeing such a claim as anything other than obvious.\u00a0 It can be fascinating to watch, in the same way it’s fascinating to watch a politician discuss (say) Confederate History Month without mentioning slavery<\/a>.\u00a0 How long can you poke and prod the P versus NP beast without rousting it?<\/p>\n

On the other hand, complexity theory does<\/em> show up in Galchen’s article, and in an extremely interesting context: that of explaining where Deutsch got the idea for quantum computing.<\/p>\n

According to Deutsch, the insight for [his famous 1985 paper] came from a conversation in the early eighties with the physicist Charles Bennett, of I.B.M., about computational-complexity theory, at the time a sexy new field that investigated the difficulty of a computational task.<\/p>\n

Is “at the time” meant to imply complexity theory is no longer sexy, or merely that it’s no longer new?\u00a0 Leaving that aside…<\/p>\n

Mass, for instance, is a fundamental property, because it remains the same in any setting; weight is a relative property, because an object’s weight depends on the strength of gravity acting on it … If computational complexity was like mass—if it was a relative property—then complexity was quite profound; if not, then not.<\/p>\n

“I was just sounding off,” Deutsch said.\u00a0 “I said they make too much of this”—meaning complexity theory—“because there’s no standard computer with respect to which you should be calculating the complexity of the task.”\u00a0 Just as an object’s weight depends on the force of gravity in which it’s measured, the degree of computational complexity depended on the computer on which it was measured.\u00a0 One could find out how complex a task was to perform on a particular computer, but that didn’t say how complex a task was fundamentally<\/em>, in reference to the universe … Complexity theorists, Deutsch reasoned, were wasting their time.<\/p>\n

The tale continues with Bennett pointing out that the universe itself<\/em> could be taken to be the “fundamental computer,” which leads Deutsch to the shocking realization that the complexity theorists weren’t complete<\/em> morons. Sure, they had a silly theory where all the answers depended on which computer you chose (which somehow none of them ever noticed), but luckily, it could be fixed by the simple addition of quantum mechanics!<\/p>\n

Over the anguished howls of my classical complexity-theorist friends, I should point out that this story isn’t completely<\/em> false.\u00a0 There’s no denying that merging quantum mechanics with theoretical computer science was a major advance in human knowledge, and that the people who first had the idea to merge the two were not<\/em> computer scientists, but physicists like Deutsch and Feynman (the latter’s role is completely left out of Galchen’s story).<\/p>\n

But complexity theory wasn’t so much a flawed early attempt at quantum computing as an essential prerequisite<\/em> to it: the thing that made it possible to articulate how quantum computers might differ from classical computers in the first place.\u00a0 Indeed, it occurs to me that Deutsch and Bennett’s conversation provides the key to resolving a puzzle discussed in the article:<\/p>\n

“Quantum computers should have been invented in the nineteen-thirties,” [Deutsch] observed near the end of our conversation.\u00a0 “The stuff that I did in the late nineteen-seventies and early nineteen-eighties didn’t use any innovation that hadn’t been known in the thirties.”\u00a0 That is straightforwardly true.\u00a0 Deutsch went on, “The question is why.”<\/p>\n

I used to go around saying the same thing: “someone like John von Neumann could have easily<\/em> invented quantum computing in the 1930s, had he just put the pieces together!”\u00a0 But I now suspect this view is a mistake, the result of projecting what’s obvious today onto a much earlier era.\u00a0 For there’s at least one<\/em> essential ingredient for quantum computing that wouldn’t enter scientific consciousness until the 1970s or so: complexity theory, and particularly the distinction between polynomial and exponential time.<\/p>\n

\n

Over the years, I’ve developed what I call the Minus-Sign Test<\/strong><\/span>, a reliable way to rate popularizations of quantum mechanics.\u00a0 To pass the Minus-Sign Test, all a popularization needs to do is mention the minus signs: <\/em>i.e., interference between positive and negative amplitudes, the defining feature of quantum mechanics, the thing that makes it different<\/em> from classical probability theory, the reason why we can’t<\/em> say Schr\u00f6dinger’s cat is “really either dead or alive,” and we simply don’t know which one, the reason why the entangled particles can’t<\/em> have just agreed in advance that one would spin up and the other would spin down.\u00a0 Another name for the Minus-Sign Test is the High-School Student Test<\/strong><\/span>, since it’s the thing that determines whether a bright high-school student, meeting quantum mechanics for the first time through the popularization, would come away thinking of superposition as<\/p>\n

(a) one of the coolest discoveries about Nature ever made, or
\n(b) a synonym used by some famous authority figures for ignorance.<\/p>\n

Despite the low bar set by the Minus-Sign Test, I’m afraid almost every popular article about quantum mechanics ever written has failed it, the present piece included.<\/p>\n

\n

Reading Not Even Wrong<\/a>, I was surprised at first that the discussion centered around Deutsch’s argument that quantum computing proves the existence of Many Worlds<\/a>.\u00a0 (More precisely, Deutsch’s position is that Many Worlds is an established fact with or without<\/em> quantum computing, but that for those who are too dense or stubborn to see it, a working quantum computer will be useful for hitting them over the head.)<\/p>\n

As others pointed out: yes, the state of the universe as described by quantum mechanics is a vastly, exponentially<\/em> bigger thing than anything dreamt of in classical physics; and a scalable quantum computer would be dramatic evidence that this exponentiality is really “out there,” that it’s not just an artifact of our best current theory.\u00a0 These are not merely truths, but truths worth shouting from the rooftops.<\/p>\n

However, there’s then the further question of whether it’s useful to talk about one quantum-mechanical universe<\/em> as an exponential number of parallel semi-classical universes.\u00a0 After all, to whatever extent the branches of a superposition successfully contribute to a quantum computation, to that extent they’re not so much “parallel universes” as one giant, fault-tolerantly-encoded, self-interfering blob; and to whatever extent those branches do<\/em> look like parallel universes, to that extent they’re now forever out of causal contact with each other—the branches other than our own figuring into our explanations for observable events only in the way that classical counterfactuals figure in.<\/p>\n

Anyway, I thought: does anyone still care<\/em> about these issues?\u00a0 Wasn’t every possible argument and counterargument explored to death years ago?<\/p>\n

But this reaction just reveals my personal bias.\u00a0 Sometime in graduate school, I realized that I was less interested in winning philosophical debates than in discovering new phenomena for philosophers to debate about.\u00a0 Why brood over the true meaning of (say) G\u00f6del’s Theorem or the Bell Inequality, when there are probably other such worldview-changing results still to be found, and those results might render the brooding irrelevant anyway?\u00a0 Because of this attitude, I confess to being less interested in whether Many-Worlds is true <\/em>than in whether it’s scientifically fruitful.\u00a0 As Peter Shor once memorably put it on this blog: why not be a Many-Worlder on Monday, a Bohmian on Tuesday, and a Copenhagenist on Wednesday, if that’s what helps you prove new theorems?<\/p>\n

Ironically, this attitude seems to me to mesh well with Deutsch’s own emphasis on explanation<\/em> as the goal of science.\u00a0 Ask not whether the parallel universes are “really there,” or whether they should really be called “parallel universes”—ask what explanatory work they do for you<\/em>!\u00a0 (That is, over and above the explanatory work that QM itself already does for you, assuming you accept it and know how to use it.)<\/p>\n

So for me, the single strongest argument in favor of Many-Worlds is what I call the “Deutsch argument”:<\/p>\n

Many-Worlds is scientifically fruitful, because it led David Deutsch to think of quantum computing.<\/em><\/p>\n

This argument carries considerable force for me.\u00a0 On the other hand, if we accept it, then it seems we should also accept the following argument:<\/p>\n

Bohmian mechanics is scientifically fruitful, because it led John Bell to think of the Bell inequality.<\/em><\/p>\n

Furthermore, consider the following facts:<\/p>\n

David Deutsch is a brilliant, iconoclastic theoretical physicist, who thought deeply about quantum foundations at a time when it was unfashionable to do so.\u00a0 His extraordinary (and not wholly-unjustified!) self-confidence in his own powers of reasoning has led to his defending not one but many heterodox ideas.<\/em><\/p>\n

Is it possible that these facts provide a common explanation for Deutsch’s certainty about Many-Worlds and<\/em> his pioneering role in quantum computing, without our needing to invoke the former to explain the latter?<\/p>\n

\n

Let me end with a few miscellaneous reactions to Galchen’s article.<\/p>\n

Physics advances by accepting absurdities.\u00a0 Its history is one of unbelievable ideas proving to be true.<\/p>\n

I’d prefer to say the history of physics is one of a vast number of unbelievable ideas proving to be false<\/em>, and a few specific<\/em> unbelievable ideas proving to be true—especially ideas having to do with the use of negative numbers where one might have thought only positive numbers made sense.<\/p>\n

[Robert Schoelkopf and his group at Yale] have configured their computer to run what is known as a Grover’s algorithm, one that deals with a four-card-monte type of question: Which hidden card is the queen?\u00a0 It’s a sort of Shor’s algorithm for beginners, something that a small quantum computer can take on.<\/p>\n

No, small quantum computers can and have taken on both Shor’s and <\/em> Grover’s algorithms, solving tiny instances in each case.\u00a0 The real<\/em> difference between Shor’s and Grover’s algorithms is one that complexophobia might prevent Galchen from mentioning: Shor gives you a (conjectured) exponential speedup for some highly-specific problems (factoring and discrete log), while Grover gives you “merely” a quadratic speedup, but for a much wider class of problems.<\/p>\n

“Look,” [Deutsch] went on, “I can’t stop you from writing an article about a weird English guy who thinks there are parallel universes.\u00a0 But I think that style of thinking is kind of a put-down to the reader.\u00a0 It’s almost like saying, If you’re not weird in these ways, you’ve got no hope as a creative thinker.\u00a0 That’s not true.\u00a0 The weirdness is only superficial.”<\/p>\n

This was my favorite passage in the article.<\/p>\n","protected":false},"excerpt":{"rendered":"

No, I’m not talking about Osama, but about my reactions below to a New Yorker article about quantum computing—reactions whose writing was rudely interrupted by last night’s news.\u00a0 Of all the possible times in the past decade to get him, they had to pick one that would overshadow an important Shtetl-Optimized discussion about complexity theory, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[5,4,17],"tags":[],"class_list":["post-613","post","type-post","status-publish","format-standard","hentry","category-complexity","category-quantum","category-speaking-truth-to-parallelism"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/613","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=613"}],"version-history":[{"count":11,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/613\/revisions"}],"predecessor-version":[{"id":3130,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/613\/revisions\/3130"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=613"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=613"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=613"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}