{"id":1697,"date":"2014-03-02T18:25:26","date_gmt":"2014-03-02T23:25:26","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=1697"},"modified":"2016-12-10T04:26:23","modified_gmt":"2016-12-10T09:26:23","slug":"recent-papers-by-susskind-and-tao-illustrate-the-long-reach-of-computation","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=1697","title":{"rendered":"Recent papers by Susskind and Tao illustrate the long reach of computation"},"content":{"rendered":"

Most of the time, I’m a crabby, cantankerous ogre, whose only real passion in life is using this blog to shoot down the wrong ideas of others.\u00a0 But alas, try as I might to maintain my reputation as a pure bundle of seething negativity, sometimes events transpire that pierce my crusty exterior. \u00a0Maybe it’s because I’m in Berkeley now, visiting the new Simons Institute for Theory of Computing<\/a> during its special semester on Hamiltonian complexity<\/a>.\u00a0 And it’s tough to keep up my acerbic East Coast skepticism of everything new in the face of all this friggin’ sunshine.\u00a0 (Speaking of which, if you’re in the Bay Area and wanted to meet me, this week’s the week!\u00a0 Email me.)\u00a0 Or maybe it’s watching Lily running around, her face wide with wonder.\u00a0 If she’s so excited by her discovery of (say) a toilet plunger or some lint on the floor, what right do I have not<\/em> to be excited by actual scientific progress?<\/p>\n

Which brings me to the third reason for my relatively-sunny disposition: two long and fascinating recent papers on the arXiv.\u00a0 What these papers have in common is that they use concepts from theoretical computer science in unexpected ways, while trying to address open problems at the heart of “traditional, continuous” physics and math.\u00a0 One paper uses quantum circuit complexity to help understand black holes; the other uses fault-tolerant universal computation to help understand the Navier-Stokes equations.<\/p>\n

Recently, our always-pleasant string-theorist friend Lubo\u0161 Motl described computational complexity theorists as “extraordinarily na\u00efve”<\/a> (earlier, he also called us “deluded” and “bigoted”).\u00a0 Why?\u00a0 Because we’re obsessed with “arbitrary, manmade” concepts like the set of problems solvable in polynomial time, and especially because we assume things we haven’t yet proved such as P\u2260NP.\u00a0 (Jokes about throwing stones from a glass house—or a stringy house—are left as exercises for the reader.)\u00a0 The two papers that I want to discuss today reflect a different perspective: one that regards computation as no more “arbitrary” than other central concepts of mathematics, and indeed, as something that shows up even in contexts that seem incredibly remote from it, from the AdS\/CFT correspondence<\/a> to turbulent fluid flow.<\/p>\n

\n

Our first paper is Computational Complexity and Black Hole Horizons<\/a>, by Lenny Susskind.\u00a0 As readers of this blog might recall, last year Daniel Harlow and Patrick Hayden made a striking connection<\/a> between computational complexity and the black-hole “firewall” question, by giving complexity-theoretic evidence that performing the measurement of Hawking radiation required for the AMPS experiment<\/a> would require an exponentially-long quantum computation.\u00a0 In his new work, Susskind makes a different, and in some ways even stranger, connection between complexity and firewalls.\u00a0 Specifically, given an n-qubit pure state |\u03c8\u232a, recall that the quantum circuit complexity<\/em> of |\u03c8\u232a is the minimum number of 2-qubit gates needed to prepare\u00a0|\u03c8\u232a starting from the all-|0\u232a state.\u00a0 Then for reasons related to black holes and firewalls, Susskind wants to use the quantum circuit complexity of |\u03c8\u232a as an intrinsic clock<\/em>, to measure how long\u00a0|\u03c8\u232a has been evolving for.\u00a0 Last week, I had the pleasure of visiting Stanford, where Lenny spent several hours explaining this stuff to me.\u00a0 I still don’t fully understand it, but since it’s arguable that no one<\/em> (including Lenny himself) does, let me give it a shot.<\/p>\n

My approach will be to divide into two questions.\u00a0 The first question is: why, in general<\/em> (i.e., forgetting about black holes), might one want to use quantum circuit complexity as a clock?\u00a0 Here the answer is: because unlike most other clocks, this one should continue to tick for an exponentially long time!<\/p>\n

Consider some standard, classical thermodynamic system, like a box filled with gas, with the gas all initially concentrated in one corner.\u00a0 Over time, the gas will diffuse across the box, in accord with the Second Law, until it completely equilibrates.\u00a0 Furthermore, if we know the laws of physics, then we can calculate exactly how fast this diffusion will happen.\u00a0 But this implies that we can use the box as a clock!\u00a0 To do so, we’d simply have to measure how diffused the gas was, then work backwards to determine how much time had elapsed since the gas started diffusing.<\/p>\n

But notice that this “clock” only works until the gas reaches equilibrium—i.e., is equally spread across the box.\u00a0 Once the gas gets to equilibrium, which it does in a reasonably short time, it just stays there<\/em> (at least until the next Poincar\u00e9 recurrence time).\u00a0 So, if you see the box in equilibrium, there’s no measurement you could make—or certainly no “practical” measurement—that would tell you how long it’s been there.\u00a0 Indeed, if we model the collisions between gas particles (and between gas particles and the walls of the box) as random events, then something even stronger is true.\u00a0 Namely, the probability distribution over all possible<\/em> configurations of the gas particles will quickly converge to an equilibrium distribution.\u00a0 And if you all you knew was that the particles were in the equilibrium distribution, then there’s no property<\/em> of their distribution that you could point to—not even an abstract, unmeasurable property—such that knowing that property would tell you how long the gas had been in equilibrium.<\/p>\n

Interestingly, something very different happens if we consider a quantum pure state, in complete isolation from its environment.\u00a0 If you have some quantum particles in a perfectly-isolating box, and you start them out in a “simple” state (say, with all particles unentangled and in a corner), then they too will appear to diffuse, with their wavefunctions spreading out and getting entangled with each other, until the system reaches “equilibrium.”\u00a0 After that, there will once again be no “simple” measurement you can make—say, of the density of particles in some particular location—that will give you any idea of how long the box has been in equilibrium.\u00a0 On the other hand, the laws of unitary evolution assure us that the quantum state is still evolving<\/em>, rotating serenely through Hilbert space, just like it was before equilibration!\u00a0 Indeed, in principle you could even measure that the evolution was still happening, but to do so, you’d need to perform an absurdly precise and complicated measurement—one that basically inverted the entire unitary transformation that had been applied since the particles started diffusing.<\/p>\n

Lenny now asks the question: if the quantum state of the particles continues to evolve even after “equilibration,” then what physical quantity<\/em> can we point to as continuing to increase?\u00a0 By the argument above, it can’t be anything simple that physicists are used to talking about, like coarse-grained entropy.\u00a0 Indeed, the most obvious candidate that springs to mind, for a quantity that should keep increasing even after equilibration, is just the quantum circuit complexity of the state!\u00a0 If<\/em> there’s no “magic shortcut” to simulating this system—that is, if<\/em> the fastest way to learn the quantum state at time T is just to run the evolution equations forward for T time steps—then the quantum circuit complexity will continue to increase linearly with T, long after equilibration.\u00a0 Eventually<\/em>, the complexity will “max out” at ~cn<\/sup>, where n is the number of particles, simply because (neglecting small multiplicative terms) the dimension of the Hilbert space is always an upper bound on the circuit complexity.\u00a0 After even longer amounts of time—like ~cc^n<\/sup>—the circuit complexity will dip back down (sometimes even to 0), as the quantum state undergoes recurrences.\u00a0 But both of those effects only occur on timescales ridiculously longer than anything normally relevant to physics or everyday life.<\/p>\n

Admittedly, given the current status of complexity theory, there’s little hope of proving unconditionally<\/em> that the quantum circuit complexity continues to rise until it becomes exponential, when some time-independent Hamiltonian is continuously applied to the all-|0\u232a state.\u00a0 (If we could prove such a statement, then presumably we could also prove PSPACE\u2284BQP\/poly.)\u00a0 But maybe we could prove such a statement modulo a reasonable conjecture.\u00a0 And we do have suggestive weaker results.\u00a0 In particular (and as I just learned this Friday), in 2012 Brand\u00e3o, Harrow, and Horodecki<\/a>, building on earlier work due to Low<\/a>, showed that, if you apply S>>n random<\/em> two-qubit gates to n qubits initially in the all-|0\u232a state, then with high probability, not only do you get a state with large circuit complexity, you get a state that can’t even be distinguished from the maximally mixed state<\/em> by any quantum circuit with at most ~S1\/6<\/sup> gates.<\/p>\n

OK, now on to the second question: what does any of this have to do with black holes?\u00a0 The connection Lenny wants to make involves the AdS\/CFT correspondence, the “duality” between two completely different-looking theories that’s been the rage in string theory since the late 1990s.\u00a0 On one side of the ring is AdS (Anti de Sitter), a quantum-gravitational theory in D spacetime dimensions—one where black holes can form and evaporate, etc., but on the other hand, the entire universe is surrounded by a reflecting boundary a finite distance away, to help keep everything nice and unitary.\u00a0 On the other side is CFT (Conformal Field Theory): an “ordinary” quantum field theory, with no gravity, that lives only on the (D-1)-dimensional “boundary” of the AdS space, and not in its interior “bulk.”\u00a0 The claim of AdS\/CFT is that despite how different they look, these two theories are “equivalent,” in the sense that any calculation in one theory can be transformed to a calculation in the other theory that yields the same answer.\u00a0 Moreover, we get mileage<\/em> this way, since a calculation that’s hard on the AdS side is often easy on the CFT side and vice versa.<\/p>\n

As an example, suppose we’re interested in what happens inside a black hole—say, because we want to investigate the AMPS firewall paradox.\u00a0 Now, figuring out what happens inside a black hole (or even on or near the event horizon) is a notoriously hard problem in quantum gravity; that’s why people have been arguing about firewalls for the past two years, and about the black hole information problem<\/a> for the past forty!\u00a0 But what if we could put our black hole in an AdS box?\u00a0 Then using AdS\/CFT, couldn’t we translate questions about the black-hole interior to questions about the CFT on the boundary, which don’t<\/em> involve gravity and which would therefore hopefully be easier to answer?<\/p>\n

In fact people have<\/em> tried to do that—but frustratingly, they haven’t been able to use the CFT calculations to answer even the grossest, most basic questions about what someone falling into the black hole would actually experience.\u00a0 (For example, would that person hit a “firewall” and die immediately at the horizon, or would she continue smoothly through, only dying close to the singularity?)\u00a0 Lenny’s paper explores a possible reason for this failure.\u00a0 It turns out that the way AdS\/CFT works, the closer to the black hole’s event horizon you want to know what happens, the longer you need to time-evolve the quantum state of the CFT to find out<\/em>.\u00a0 In particular, if you want to know what’s going on at distance\u00a0\u03b5 from the event horizon, then you need to run the CFT for an amount of time that grows like log(1\/\u03b5).\u00a0 And what if you want to know what’s going on inside<\/em> the black hole?\u00a0 In line with the holographic principle<\/a>, it turns out that you can express an observable inside<\/em> the horizon by an integral over the entire AdS space outside<\/em> the horizon.\u00a0 Now, that integral will include a part where the distance\u00a0\u03b5 from the event horizon goes to 0—so\u00a0log(1\/\u03b5), and hence the complexity of the CFT calculation that you have to do, diverges to infinity.\u00a0 For some kinds of calculations, the \u03b5\u21920 part of the integral isn’t very important, and can be neglected at the cost of only a small error.\u00a0 For other kinds of calculations, unfortunately—and in particular, for the kind that would tell you whether or not there’s a firewall—the\u00a0\u03b5\u21920 part is extremely<\/em> important, and it makes the CFT calculation hopelessly intractable.<\/p>\n

Note that yes, we even need to continue the integration for \u03b5 much smaller than the Planck length—i.e., for so-called “transplanckian” distances!\u00a0 As Lenny puts it, however:<\/p>\n

For most of this vast sub-planckian range of scales we don’t expect that the operational meaning has anything to do with meter sticks … It has more to do with large times than small distances.<\/p>\n

One could give this transplanckian blowup in computational complexity a pessimistic spin: darn, so it’s probably hopeless to use AdS\/CFT to prove once and for all that there are no firewalls!\u00a0 But there’s also a more positive interpretation: the interior of a black hole is “protected from meddling” by a thick armor of computational complexity.\u00a0 To explain this requires a digression about firewalls.<\/p>\n

The original firewall paradox of AMPS could be phrased as follows: if<\/em> you performed a certain weird, complicated measurement on the Hawking radiation emitted from a “sufficiently old” black hole, then the expected results of that measurement would be incompatible with also<\/em> seeing a smooth, Einsteinian spacetime if you later jumped into the black hole to see what was there.\u00a0 (Technically, because you’d violate the monogamy of entanglement.)\u00a0 If what awaited you behind the event horizon wasn’t a “classical” black hole interior with a singularity in the middle, but an immediate breakdown of spacetime, then one says you would’ve “hit a firewall.”<\/p>\n

Yes, it seems preposterous that “firewalls” would exist: at the least, it would fly in the face of everything people thought they understood for decades about general relativity and quantum field theory.\u00a0 But crucially—and here I have to disagree with Stephen Hawking<\/a>—one can’t “solve” this problem by simply repeating the physical absurdities of firewalls, or by constructing scenarios where firewalls “self-evidently” don’t arise.\u00a0 Instead, as I see it, solving the problem means giving an account of what actually happens when you do the AMPS experiment, or of what goes wrong when you try to do it.<\/em><\/p>\n

On this last question, it seems to me that Susskind and Juan Maldacena achieved a major advance in their much-discussed ER=EPR paper<\/a> last year.\u00a0 Namely, they presented a picture where, sure, a firewall arises (at least temporarily) if you do the AMPS experiment—but no firewall arises if you don’t<\/em> do the experiment!\u00a0 In other words, doing the experiment sends a nonlocal signal<\/em> to the interior of the black hole (though you do have to jump into the black hole to receive the signal, so causality outside the black hole is still preserved).\u00a0 Now, how is it possible for your measurement of the Hawking radiation to send an instantaneous signal to the black hole interior, which might be light-years away from you when you measure?\u00a0 On Susskind and Maldacena’s account, it’s possible because the entanglement between the Hawking radiation and the degrees of freedom still in the black hole, can be interpreted as creating wormholes<\/em> between the two.\u00a0 Under ordinary conditions, these wormholes (like most wormholes in general relativity) are “non-traversable”: they “pinch off” if you try to send signals through them, so they can’t be used for faster-than-light communication.\u00a0 However, if you did the AMPS experiment, then the wormholes would become<\/em> traversable, and could carry a firewall (or an innocuous happy-birthday message, or whatever) from the Hawking radiation to the black hole interior.\u00a0 (Incidentally, ER stands for Einstein and Rosen, who wrote a famous paper on wormholes, while EPR stands for Einstein, Podolsky, and Rosen, who wrote a famous paper on entanglement.\u00a0 “ER=EPR” is Susskind and Maldacena’s shorthand for their proposed connection between wormholes and entanglement.)<\/p>\n

Anyway, these heady ideas raise an obvious question: how hard would it be<\/em> to do the AMPS experiment?\u00a0 Is sending a nonlocal signal to the interior of a black hole via that experiment actually a realistic possibility?\u00a0 In their work a year ago on computational complexity and firewalls, Harlow and Hayden already addressed that question, though from a different perspective than Susskind.\u00a0 In particular, Harlow and Hayden gave strong evidence that carrying out the AMPS experiment would require solving a problem believed to be exponentially hard even for a quantum computer: specifically, a complete problem for QSZK<\/a> (Quantum Statistical Zero Knowledge).\u00a0 In followup work (not yet written up, though see my talk at KITP<\/a> and my PowerPoint slides<\/a>), I showed that the Harlow-Hayden problem is actually at least as hard as inverting one-way functions, which is even stronger evidence for hardness.<\/p>\n

All of this suggests that, even supposing<\/em> we could surround an astrophysical black hole with a giant array of perfect photodetectors, wait ~1069<\/sup> years for the black hole to (mostly) evaporate, then route the Hawking photons into a super-powerful, fault-tolerant quantum computer, doing the AMPS experiment (and hence, creating traversable wormholes to the black hole interior) still<\/em> wouldn’t be a realistic prospect, even if the equations formally allow it!\u00a0 There’s no way to sugarcoat this: computational complexity limitations seem to be the only thing protecting the geometry of spacetime from nefarious experimenters.<\/strong><\/p>\n

Anyway, Susskind takes that amazing observation of Harlow and Hayden as a starting point, but then goes off on a different tack.\u00a0 For one thing, he isn’t focused on the AMPS experiment (the one involving monogamy of entanglement) specifically<\/em>: he just wants to know how hard it is to do any<\/em> experiment (possibly a different one) that would send nonlocal signals to the black hole interior.\u00a0 For another, unlike Harlow and Hayden, Susskind isn’t trying to show that such an experiment would be exponentially<\/em> hard.\u00a0 Instead, he’s content if the experiment is “merely” polynomially hard—but in the same sense that (say) unscrambling an egg, or recovering a burned book from the smoke and ash, are polynomially hard.\u00a0 In other words, Susskind only wants to argue that creating a traversable wormhole would be “thermodynamics-complete.”\u00a0 A third, related, difference is that Susskind considers an extremely special model scenario: namely, the AdS\/CFT description of something called the “thermofield double state.”\u00a0 (This state involves two<\/em> entangled black holes in otherwise-separated spacetimes; according to ER=EPR, we can think of those black holes as being connected by a wormhole.)\u00a0 While I don’t yet understand this point, apparently the thermofield double state is much more favorable for firewall production than a “realistic” spacetime—and in particular, the Harlow-Hayden argument doesn’t apply to it.\u00a0 Susskind wants to show that even so<\/em> (i.e., despite how “easy” we’ve made it), sending a signal through the wormhole connecting the two black holes of the thermofield double state would still require solving a thermodynamics-complete problem.<\/p>\n

So that’s the setup.\u00a0 What new insights does Lenny get?\u00a0 This, finally, is where we circle back to the view of quantum circuit complexity as a clock.\u00a0 Briefly, Lenny finds that the quantum state getting more and more complicated in the CFT description—i.e., its quantum circuit complexity going up and up—directly corresponds to the wormhole getting longer and longer in the AdS description.<\/strong>\u00a0 (Indeed, the length of the wormhole increases linearly with time, growing like the circuit complexity divided by the total number of qubits.)\u00a0 And the wormhole getting longer and longer is what makes it non-traversable—i.e., what makes it impossible to send a signal through.<\/p>\n

Why has quantum circuit complexity made a sudden appearance here?\u00a0 Because in the CFT description, the circuit complexity continuing to increase is the only thing that’s obviously “happening”!\u00a0 From a conventional physics standpoint, the quantum state of the CFT very quickly reaches equilibrium and then just stays there<\/em>.\u00a0 If you measured some “conventional” physical observable—say, the energy density at a particular point—then it wouldn’t look like the CFT state was continuing to evolve at all.\u00a0 And yet we know that the CFT state is<\/em> evolving, for two extremely different reasons.\u00a0 Firstly, because (as we discussed early on in this post) unitary evolution is still happening, so presumably the state’s quantum circuit complexity is continuing to increase.\u00a0 And secondly, because in the dual AdS description, the wormhole is continuing to get longer!<\/p>\n

From this connection, at least three striking conclusions follow:<\/p>\n

    \n
  1. That even when nothing else seems to be happening in a physical system (i.e., it seems to have equilibrated), the fact that the system’s quantum circuit complexity keeps increasing can be “physically relevant” all by itself<\/em>.\u00a0 We know that it’s physically relevant, because in the AdS dual description, it corresponds to the wormhole getting longer!<\/li>\n
  2. That even in the special case of the thermofield double state, the geometry of spacetime continues to be protected by an “armor” of computational complexity<\/em>.\u00a0 Suppose that Alice, in one half of the thermofield double state, wants to send a message to Bob in the other half (which Bob can retrieve by jumping into his black hole).\u00a0 In order to get her message through, Alice needs to prevent the wormhole connecting her black hole to Bob’s from stretching uncontrollably—since as long as it stretches, the wormhole remains non-traversable.\u00a0 But in the CFT picture, stopping the wormhole from stretching corresponds to stopping the quantum circuit complexity from increasing!\u00a0 And that, in turn, suggests that Alice would need to act on the radiation outside her black hole in an incredibly complicated and finely-tuned way.\u00a0 For “generically,” the circuit complexity of an n-qubit state should just continue to increase, the longer you run unitary evolution for, until it hits its exp(n) maximum.\u00a0 To prevent that from happening would essentially require “freezing” or “inverting” the unitary evolution applied by nature—but that’s the sort of thing that we expect to be thermodynamics-complete.\u00a0 (How exactly do Alice’s actions in the “bulk” affect the evolution of the CFT state?\u00a0 That’s an excellent question that I don’t understand AdS\/CFT well enough to answer.\u00a0 All I know is that the answer involves something that Lenny calls “precursor operators.”)<\/li>\n
  3. The third and final conclusion is that there can be a physically-relevant difference between pseudorandom n-qubit pure states and “truly” random states<\/em>—even though, by the definition of pseudorandom, such a difference can’t be detected by any small quantum circuit!\u00a0 Once again, the way to see the difference is using AdS\/CFT.\u00a0 It’s easy to show, by a counting argument, that almost all n-qubit pure states have nearly-maximal<\/em> quantum circuit complexity.\u00a0 But if the circuit complexity is already maximal, that means in particular that it’s not increasing!\u00a0 Lenny argues that this corresponds to the wormhole between the two black holes no longer stretching.\u00a0 But if the wormhole is no longer stretching, then it’s “vulnerable to firewalls” (i.e., to messages going through!).\u00a0 It had previously been argued that random<\/em> CFT states almost always correspond to black holes with firewalls—and since the CFT states formed by realistic physical processes will look “indistinguishable from random states,” black holes that form under realistic conditions should generically have firewalls as well.\u00a0 But Lenny rejects this argument, on the ground that the CFT states that arise in realistic situations are not<\/em> random pure states.\u00a0 And what distinguishes them from random states?\u00a0 Simply that they have non-maximal (and increasing) quantum circuit complexity!<\/li>\n<\/ol>\n

    I’ll leave you with a question of my own about this complexity \/ black hole connection: one that I’m unsure how to think about, but that perhaps interests me more than any other here.\u00a0 My question is: could you ever learn the answer to an otherwise-intractable computational problem by jumping into a black hole?<\/strong>\u00a0 Of course, you’d have to really<\/em> want the answer—so much so that you wouldn’t mind dying moments after learning it, or not being able to share it with anyone else!\u00a0 But never mind that.\u00a0 What I have in mind is first applying some polynomial-size quantum circuit to the Hawking radiation, then jumping into the black hole to see what nonlocal effect (if any) the circuit had on the interior.\u00a0 The fact that the mapping between interior and exterior states is so complicated suggests that there might be complexity-theoretic mileage to be had this way, but I don’t know what.\u00a0 (It’s also possible that you can<\/em> get a computational speedup in special cases like the thermofield double state, but that a Harlow-Hayden-like obstruction prevents you from getting one with real astrophysical black holes.\u00a0 I.e., that for real black holes, you’ll just see a smooth, boring, Einsteinian black hole interior no matter what<\/em> polynomial-size quantum circuit you applied to the Hawking radiation.)<\/p>\n

    \n

    If you’re still here, the second paper I want to discuss today is Finite-time blowup for an averaged three-dimensional Navier-Stokes equation<\/a> by Terry Tao.\u00a0 (See also the excellent Quanta<\/em> article<\/a> by Erica Klarreich.)\u00a0 I’ll have much, much less to say about this paper than I did about Susskind’s, but that’s not because it’s less interesting: it’s only because I understand the issues even less well.<\/p>\n

    Navier-Stokes existence and smoothness<\/a> is one of the seven Clay Millennium Problems<\/a> (alongside P vs. NP, the Riemann Hypothesis, etc).\u00a0 The problem asks whether the standard, classical differential equations for three-dimensional fluid flow are well-behaved, in the sense of not “blowing up” (e.g., concentrating infinite energy on a single point) after a finite amount of time.<\/p>\n

    Expanding on ideas from his earlier blog posts and papers about Navier-Stokes (see here<\/a> for the gentlest of them), Tao argues that the Navier-Stokes problem is closely related to the question of whether or not it’s possible to “build a fault-tolerant universal computer out of water.”\u00a0 Why?\u00a0 Well, it’s not the computational universality per se<\/em> that matters, but if you could use fluid flow to construct general enough computing elements—resistors, capacitors, transistors, etc.—then you could use those elements to recursively shift the energy in a given region into a region half the size, and from there to a region a quarter the size, and so on, faster and faster, until you got infinite energy density after a finite amount of time.<\/p>\n

    Strikingly, building on an earlier construction by Katz and Pavlovic, Tao shows that this is actually possible<\/strong> for an “averaged” version of the Navier-Stokes equations!\u00a0 So at the least, any proof of existence and smoothness for the real Navier-Stokes equations will need to “notice” the difference between the real and averaged versions.\u00a0 In his paper, though, Tao hints at the possibility (or dare one say likelihood?) that the truth might go the other way.\u00a0 That is, maybe the “universal computer” construction can be ported from the averaged Navier-Stokes equations to the real ones.\u00a0 In that case, we’d have blowup in finite time for the real equations, and a negative solution to the Navier-Stokes existence and smoothness problem.\u00a0 Of course, such a result wouldn’t imply that real, physical water was in any danger of “blowing up”!\u00a0 It would simply mean that the discrete nature of water (i.e., the fact that it’s made of H2<\/sub>O molecules, rather than being infinitely divisible) was essential to understanding its stability given arbitrary initial conditions.<\/p>\n

    So, what are the prospects for such a blowup result?\u00a0 Let me quote from Tao’s paper:<\/p>\n

    Once enough logic gates of ideal fluid are constructed, it seems that the main difficulties in executing the above program [to prove a blowup result for the “real” Navier-Stokes equations] are of a “software engineering” nature, and would be in principle achievable, even if the details could be extremely complicated in practice.\u00a0 The main mathematical difficulty in executing this “fluid computing” program would thus be to arrive at (and rigorously certify) a design for logical gates of inviscid fluid that has some good noise tolerance properties.\u00a0 In this regard, ideas from quantum computing (which faces a unitarity constraint somewhat analogous to the energy conservation constraint for ideal fluids, albeit with the key difference of having a linear evolution rather than a nonlinear one) may prove to be useful.<\/div>\n

    One minor point that I’d love to understand is, what happens in two dimensions?<\/em>\u00a0 Existence and smoothness are known to hold for the 2-dimensional analogues of the Navier-Stokes equations.\u00a0 If they also held for the averaged<\/em> 2-dimensional equations, then it would follow that Tao’s “universal computer” must be making essential use of the third dimension. How?\u00a0 If I knew the answer to that, then I’d feel for the first time like I had some visual crutch for understanding why 3-dimensional fluid flow is so complicated, even though 2-dimensional fluid flow isn’t.<\/p>\n

    I see that, in blog comments here<\/a> and here<\/a>, Tao says that the crucial difference between the 2- and 3-dimensional Navier-Stokes equations arises from the different scaling behavior of the dissipation term: basically, you can ignore it in 3 or more dimensions, but you can’t ignore it in 2.\u00a0 But maybe there’s a more doofus-friendly explanation, which would start with some 3-dimensional fluid logic gate, and then explain why the gate has no natural 2-dimensional analogue, or why dissipation causes its analogue to fail.<\/p>\n

    \n

    Obviously, there’s much more to say about both papers (especially the second…) than I said in this post, and many people more knowledgeable than I am to say those things.\u00a0 But that’s what the comments section is for.\u00a0 Right now I’m going outside to enjoy the California sunshine.<\/p>\n","protected":false},"excerpt":{"rendered":"

    Most of the time, I’m a crabby, cantankerous ogre, whose only real passion in life is using this blog to shoot down the wrong ideas of others.\u00a0 But alas, try as I might to maintain my reputation as a pure bundle of seething negativity, sometimes events transpire that pierce my crusty exterior. \u00a0Maybe it’s because […]<\/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_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],"tags":[],"class_list":["post-1697","post","type-post","status-publish","format-standard","hentry","category-complexity","category-quantum"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1697","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=1697"}],"version-history":[{"count":21,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1697\/revisions"}],"predecessor-version":[{"id":1719,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1697\/revisions\/1719"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1697"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1697"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1697"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}