{"id":2586,"date":"2015-12-11T20:05:29","date_gmt":"2015-12-12T01:05:29","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=2586"},"modified":"2016-12-10T04:35:42","modified_gmt":"2016-12-10T09:35:42","slug":"ask-an-unbounded-question-get-an-uncomputable-answer","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=2586","title":{"rendered":"Ask an unbounded question, get an uncomputable answer"},"content":{"rendered":"

Just when I thought I could relax, as the waters slowly receded from the latest\u00a0D-Tsunami, my inbox and Facebook feed once again lit up with inquiries—this time, asking me to confirm or deny that\u00a0“A\u00a0Paradox at the Heart of Mathematics Makes a Physics Problem Unanswerable.”<\/a><\/p>\n

Uh-oh!<\/p>\n

Luckily for my blood pressure, though, this one turned out to\u00a0refer\u00a0to something that more-or-less\u00a0deserves<\/em>\u00a0the hype. \u00a0In particular, it’s about\u00a0a\u00a0phenomenal 146-page\u00a0paper\u00a0by Cubitt, Perez-Garcia, and Wolf<\/a>, which just appeared this week in Nature<\/em><\/a>\u00a0(in condensed form, of course). \u00a0Incidentally, yeah, his name really is\u00a0Toby Cubitt<\/a>, pronounced like “qubit.” \u00a0He’s a good guy.<\/p>\n

To those\u00a0in quantum computing, Cubitt et al.’s breakthrough is old news, having already been on the arXiv for almost a year (we’ve also had a talk at MIT about it). \u00a0The arXiv has created a funny\u00a0phenomenon, where you learn something new and cool, assimilate it, move on, and then a\u00a0year later, everyone is suddenly\u00a0asking you have you seen\u00a0this thing, is it for real<\/em>, etc. etc., just because the thing got some rubber stamp like\u00a0acceptance to Nature<\/em>\u00a0that caused the press to pick it up. \u00a0Like, dude, I was into the undecidability of the spectral gap way<\/em> before it went mainstream.<\/p>\n

One more amusing anecdote before we dive into the math. \u00a0In his\u00a0Nature News<\/em> piece popularizing Cubitt et al.’s result, the writer Davide Castelvecchi quotes Rebecca Goldstein<\/a>, the brilliant\u00a0novelist and biographer of Kurt G\u00f6del<\/a>, as saying: “Turing thought more clearly about the relationship between physics and logic than G\u00f6del did.” \u00a0Here’s what happened: Nature News<\/em> wrote to Rebecca\u00a0to ask what\u00a0G\u00f6del’s own thoughts\u00a0were about the relation between undecidability and\u00a0physics. \u00a0Rebecca passed the request along to me. \u00a0So I wrote back to her, arguing that they might\u00a0just\u00a0as well ask what Turing<\/em> thought, since the Cubitt et al. result is “really” about Turing-undecidability (with G\u00f6del-undecidability just an automatic corollary), and at any rate:<\/p>\n

I also think that Turing<\/span> thought more clearly about the relationship\u00a0between logic and physics than G\u00f6del did (indeed, G\u00f6del himself said\u00a0that it was only Turing<\/span>‘s analysis of the notion of computability, in\u00a0terms of actual physical machines that one could imagine building,\u00a0that convinced him that computability had been properly defined).<\/p>\n

Rebecca passed that\u00a0back\u00a0to Nature News<\/em>, agreeing with it, and then at some point the quote became hers. \u00a0Far from being miffed about this, I consider having my forgettable\u00a0words attributed to a genius like Rebecca to be one of the great honors of my life. \u00a0(By pure coincidence, she and I are having lunch next week; hopefully this will butter her up.)<\/p>\n

So, OK, let me restate Cubitt et al.’s great theorem in less pop-sciencey\u00a0terms than Nature News<\/em>\u00a0used. \u00a0(You could also just read the paper<\/a>‘s intro, which is exceedingly clear, but what the hell—I’m here to serve.)<\/p>\n

Suppose you have two-dimensional\u00a0material made of a bunch of stationary particles, each with local Hilbert space dimension d, which are arranged on an L\u00d7L square grid (so, there are L2<\/sup> particles in all). \u00a0And suppose there’s some fixed\u00a0d2<\/sup>-dimensional\u00a0Hamiltonian h, with\u00a0a local copy hi,j<\/sub>=h\u00a0acting on each\u00a0neighboring pair of particles (i,j). \u00a0(I.e., the material\u00a0is translationally invariant<\/em>, with the same laws of physics\u00a0acting throughout.) \u00a0Let H be the total Hamiltonian: that is, the sum of the hi,j<\/sub>‘s over all the neighboring (i,j)’s.<\/p>\n

Then a huge fraction\u00a0of all of physics—quantum field theory, condensed-matter physics, you name it—can be summarized as, you’re trying to figure out the eigenvalues and eigenvectors of H<\/em>. \u00a0The lowest\u00a0eigenvalue, \u03bb0<\/sub>, tells you your\u00a0material’s\u00a0ground energy<\/em>, while the higher eigenvalues, \u03bb1<\/sub>,\u03bb2<\/sub>,…, tell you the next discrete energy levels that the material\u00a0can jump up to. \u00a0The corresponding eigenvectors tell you which quantum states the material\u00a0is sitting in when it\u00a0has these energies:\u00a0the ground state<\/em> v0<\/sub>, and the excited states<\/em> v1<\/sub>,v2<\/sub>,… \u00a0Those, in turn, determine basically\u00a0everything you could want to know about the material: whether it superconducts, etc. etc.<\/p>\n

Of course, the eigenvalues and eigenvectors will\u00a0depend on the lattice size L. \u00a0Equally obviously, for any fixed<\/em> L, you could in principle compute all the eigenvalues and eigenvectors by just diagonalizing some huge-ass matrix. \u00a0(That matrix being\u00a0H.) \u00a0But physicists are usually more interested in the limiting behavior<\/em>\u00a0as L goes to infinity. \u00a0One of their most basic\u00a0distinctions is: the material is gapped<\/em> if \u03bb1<\/sub>-\u03bb0<\/sub>, the difference between the first excited energy and the ground energy, converges to some positive value or even grows with L as L\u2192\u221e. \u00a0It’s gapless<\/em> if \u03bb1<\/sub>-\u03bb0<\/sub>\u00a0converges to 0 as L\u2192\u221e. \u00a0(Actually, Cubitt et al. use more technical definitions of both of these concepts, but we’ll ignore that.)<\/p>\n

Cubitt et al.’s theorem now says the following: for some fixed, constant local dimension d, there is no algorithm that takes as input the local Hamiltonian h (say, as a d2<\/sup>\u00d7d2<\/sup> matrix of algebraic numbers), and that decides whether the material is gapped or gapless. \u00a0Indeed, you can reduce\u00a0the halting problem to that problem, in such a way that the material will be gapped if your Turing machine halts, or gapless if it runs forever.<\/strong><\/p>\n

As an immediate corollary, there’s some 2D\u00a0material—characterized by a translationally-invariant local Hamiltonian h on particles of local dimension d—such that whether the material is gapped or gapless is independent of the axioms of ZF set theory, or whatever else your favorite axioms might be. \u00a0(Proof: build a Turing machine M that halts if and only if it finds an inconsistency in set theory, then run Cubitt et al.’s\u00a0reduction from the halting problem. \u00a0By G\u00f6del, if set theory is consistent then it can’t prove whether M halts or not.)<\/p>\n

Cubitt et al. never\u00a0bother to\u00a0work out the local dimension d that suffices for them, but it could<\/em> be worked out, and it’s probably at least in the tens of thousands. \u00a0Thus, their result leaves open the possibility that there’s\u00a0an algorithm to decide gaplessness for 2D lattices of qubits<\/em> (i.e., the special case d=2), or other “reasonably low-dimensional” quantum systems. \u00a0We simply don’t know right now. \u00a0Another tantalizing open question is whether there’s an algorithm to decide gaplessness for one-dimensional<\/em>\u00a0spin chains—again, even in the special case d=2. \u00a0Right now, the best we have in that direction is a difficult recent result of Bravyi and Gosset<\/a>, which gives an algorithm to decide gaplessness for one-dimensional, frustration-free<\/em> chains of qubits. \u00a0(Here “frustration-free,” an amusing term that does not<\/em> well describe this subject as a whole, means that you can minimize the energy H by minimizing the energies of each hi,j<\/sub> individually. \u00a0Or, if you think of H as a SAT instance, it’s satisfiable.)<\/p>\n

But while the exact value of d where uncomputability\u00a0kicks in is still up for grabs, it’s extremely important that d is some<\/em>\u00a0fixed, universal constant, independent of the Turing machine. \u00a0Indeed, as Cubitt et al. point out in their paper, this is the only<\/em>\u00a0feature that makes their new result not a trivial corollary of the uncomputability of Wang tiling<\/a>. \u00a0The latter is a famous\u00a0result from 1966, which says that there’s no algorithm that takes as input a finite set\u00a0of tiles, and that tells you whether, using\u00a0unlimited copies of each tile, you could cover the entire plane (or equivalently, arbitrarily large finite regions\u00a0of the plane). \u00a0I.e., this is yet another “natural” math problem that secretly encodes the halting problem.<\/p>\n

The fact that d is fixed also means that, in order\u00a0to\u00a0encode larger and larger Turing machines into the local Hamiltonian h (as you must, if you want\u00a0to embed the halting problem), you need to use more and more bits of precision<\/em>\u00a0(!) in the ~d4<\/sup> real numbers that define h. \u00a0This then raises a\u00a0question: how do you actually extract<\/em> a description of a Turing machine from the binary expansions of the real numbers that define your\u00a0Hamiltonian? \u00a0To do this, Cubitt et al. use Kitaev’s phase estimation algorithm—which, interestingly, is the only<\/em> part of their construction that uses\u00a0quantum mechanics in any way. \u00a0One thing that I’d love to understand better is whether the phase estimation is really essential here, or whether the analogous classical<\/em> question, with the “Hamiltonian” given by a probability distribution over classical constraints, could also be proved to be undecidable for some fixed value of d—thereby showing that Cubitt et al.’s discovery\u00a0had nothing to do with quantum mechanics.<\/p>\n

(It’s possible that the answer to this is obvious; I didn’t think about it deeply. \u00a0Note that if the “classical Hamiltonian” is also deterministic<\/em>, then the problem must be decidable for every fixed d, since there are only finitely many possible h’s, and we could cache all the answers in a lookup table.)<\/p>\n

Anyway, it’s now my professional duty, as the prickly, curmudgeonly blogger I am, to end the post by\u00a0shooing you away\u00a0from two tempting misinterpretations of the Cubitt et al. result.<\/p>\n

First, the result does not say—or even suggest—that there’s any\u00a0real, finite physical system whose behavior is G\u00f6del- or\u00a0Turing-undecidable.<\/strong>\u00a0 Thus, it gives no\u00a0support to speculations like Roger Penrose’s, about\u00a0“hypercomputing” that would exceed the capabilities of Turing machines. \u00a0The reason, again, is that as soon as you fix a lattice size L, everything becomes computable. \u00a0The\u00a0Cubitt et al. result\u00a0applies only to questions about the limiting<\/em> behavior, as the number of particles goes\u00a0to infinity. \u00a0But we already knew lots\u00a0of\u00a0examples of physical systems for which predicting their behavior\u00a0in some infinite limit<\/em> is at least as hard as the halting problem: for instance, the Wang tiles discussed earlier, or Post rewrite systems, or even Turing machines themselves. \u00a0Local Hamiltonians are a profound, nontrivial addition to that list—one that will be particularly striking to physicists, many of whom calculate the spectral gaps of at least 50 Hamiltonians\u00a0between dinner and dessert. \u00a0But in some sense, there was no a-priori<\/em> reason why a problem this general, about physical systems of unbounded size,\u00a0ought to<\/em>\u00a0have been computable.<\/p>\n

Second, the result does not say that any particular\u00a0question physicists want an\u00a0answer to—for example, the million-dollar\u00a0Yang-Mills mass gap problem<\/a>—is G\u00f6del-undecidable.<\/strong> \u00a0“All it says,” is that the possibility that some real-world question of that kind could<\/em> be\u00a0undecidable\u00a0isn’t totally closed off. \u00a0The Nature News<\/em> piece stresses\u00a0this latter implication a lot—as, admittedly, do Cubitt et al.\u00a0themselves. \u00a0But to put things in perspective: four logicians\u00a0proved\u00a0around 1970<\/a> that there’s no algorithm to decide whether an arbitrary polynomial equation has an integer solution, thereby giving a negative solution to Hilbert’s Tenth Problem. \u00a0Yet with few exceptions, “working number theorists” barely even noticed this development, nor was (say)\u00a0Andrew Wiles dissuaded from proving Fermat’s Last Theorem, by the absence of\u00a0a\u00a0general<\/em> algorithm to do things like what he was trying to do. \u00a0(Indeed, the absence of a general algorithm was shown even earlier\u00a0for equations like FLT, which have variables in the exponent.) \u00a0So I doubt the mathematical physicists who calculate spectral gaps for a living will be any more terrified\u00a0than the number theorists were, to\u00a0learn that they’ve been laboring their entire lives on the shores of the halting problem. \u00a0“Good for us, then!” they could rightly reply. \u00a0“Maybe\u00a0our jobs won’t be so easy to automate.”<\/p>\n

Update (Dec. 20):<\/strong><\/span> My colleague Seth Lloyd calls my attention to a PRL paper of his from 1993<\/a>, which also<\/em> discusses the construction of physical systems that are gapped if a given Turing machine halts and gapless if it runs forever. \u00a0So this basic idea has been around for a while. \u00a0As I explained in the post, the main contribution of the Cubitt et al. paper is just to get undecidability into “the sort of system\u00a0physicists could plausibly care about” (or for which they could’ve plausibly hoped for an analytic solution): in this case, 2D translationally-invariant nearest-neighbor Hamiltonians with bounded local dimension.<\/p>\n","protected":false},"excerpt":{"rendered":"

Just when I thought I could relax, as the waters slowly receded from the latest\u00a0D-Tsunami, my inbox and Facebook feed once again lit up with inquiries—this time, asking me to confirm or deny that\u00a0“A\u00a0Paradox at the Heart of Mathematics Makes a Physics Problem Unanswerable.” Uh-oh! Luckily for my blood pressure, though, this one turned out […]<\/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],"tags":[],"class_list":["post-2586","post","type-post","status-publish","format-standard","hentry","category-complexity"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2586","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=2586"}],"version-history":[{"count":10,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2586\/revisions"}],"predecessor-version":[{"id":2611,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2586\/revisions\/2611"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2586"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2586"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2586"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}