### Recent papers by Susskind and Tao illustrate the long reach of computation

Sunday, March 2nd, 2014Most 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. 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. Maybe it’s because I’m in Berkeley now, visiting the new Simons Institute for Theory of Computing during its special semester on Hamiltonian complexity. And it’s tough to keep up my acerbic East Coast skepticism of everything new in the face of all this friggin’ sunshine. (Speaking of which, if you’re in the Bay Area and wanted to meet me, this week’s the week! Email me.) Or maybe it’s watching Lily running around, her face wide with wonder. 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* to be excited by actual scientific progress?

Which brings me to the third reason for my relatively-sunny disposition: two long and fascinating recent papers on the arXiv. 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. 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.

Recently, our always-pleasant string-theorist friend Luboš Motl described computational complexity theorists as “extraordinarily naïve” (earlier, he also called us “deluded” and “bigoted”). Why? 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≠NP. (Jokes about throwing stones from a glass house—or a stringy house—are left as exercises for the reader.) 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 to turbulent fluid flow.

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

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

Consider some standard, classical thermodynamic system, like a box filled with gas, with the gas all initially concentrated in one corner. Over time, the gas will diffuse across the box, in accord with the Second Law, until it completely equilibrates. Furthermore, if we know the laws of physics, then we can calculate exactly how fast this diffusion will happen. But this implies that we can use the box as a clock! 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.

But notice that this “clock” only works until the gas reaches equilibrium—i.e., is equally spread across the box. Once the gas gets to equilibrium, which it does in a reasonably short time, it *just stays there* (at least until the next Poincaré recurrence time). 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. 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. Namely, the probability distribution over all *possible* configurations of the gas particles will quickly converge to an equilibrium distribution. And if you all you knew was that the particles were in the equilibrium distribution, then there’s no *property* 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.

Interestingly, something very different happens if we consider a quantum pure state, in complete isolation from its environment. 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.” 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. On the other hand, the laws of unitary evolution assure us that *the quantum state is still evolving*, rotating serenely through Hilbert space, just like it was before equilibration! 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.

Lenny now asks the question: if the quantum state of the particles continues to evolve even after “equilibration,” then what physical *quantity* can we point to as continuing to increase? By the argument above, it can’t be anything simple that physicists are used to talking about, like coarse-grained entropy. 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! *If* there’s no “magic shortcut” to simulating this system—that is, *if* 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. *Eventually*, the complexity will “max out” at ~c^{n}, 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. After even longer amounts of time—like ~c^{c^n}—the circuit complexity will dip back down (sometimes even to 0), as the quantum state undergoes recurrences. But both of those effects only occur on timescales ridiculously longer than anything normally relevant to physics or everyday life.

Admittedly, given the current status of complexity theory, there’s little hope of *proving unconditionally* that the quantum circuit complexity continues to rise until it becomes exponential, when some time-independent Hamiltonian is continuously applied to the all-|0〉 state. (If we could prove such a statement, then presumably we could also prove PSPACE⊄BQP/poly.) But maybe we could prove such a statement modulo a reasonable conjecture. And we do have suggestive weaker results. In particular (and as I just learned this Friday), in 2012 Brandão, Harrow, and Horodecki, building on earlier work due to Low, showed that, if you apply S>>n *random* two-qubit gates to n qubits initially in the all-|0〉 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* by any quantum circuit with at most ~S^{1/6} gates.

OK, now on to the second question: what does any of this have to do with black holes? 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. 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. 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.” 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. Moreover, we get *mileage* this way, since a calculation that’s hard on the AdS side is often easy on the CFT side and vice versa.

As an example, suppose we’re interested in what happens inside a black hole—say, because we want to investigate the AMPS firewall paradox. 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 for the past forty! But what if we could put our black hole in an AdS box? 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* involve gravity and which would therefore hopefully be easier to answer?

In fact people *have* 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. (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?) Lenny’s paper explores a possible reason for this failure. 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*. In particular, if you want to know what’s going on at distance ε from the event horizon, then you need to run the CFT for an amount of time that grows like log(1/ε). And what if you want to know what’s going on *inside* the black hole? In line with the holographic principle, it turns out that you can express an observable *inside* the horizon by an integral over the entire AdS space *outside* the horizon. Now, that integral will include a part where the distance ε from the event horizon goes to 0—so log(1/ε), and hence the complexity of the CFT calculation that you have to do, diverges to infinity. For some kinds of calculations, the ε→0 part of the integral isn’t very important, and can be neglected at the cost of only a small error. For other kinds of calculations, unfortunately—and in particular, for the kind that would tell you whether or not there’s a firewall—the ε→0 part is *extremely* important, and it makes the CFT calculation hopelessly intractable.

Note that yes, we even need to continue the integration for ε much smaller than the Planck length—i.e., for so-called “transplanckian” distances! As Lenny puts it, however:

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.

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! 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. To explain this requires a digression about firewalls.

The original firewall paradox of AMPS could be phrased as follows: *if* 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* seeing a smooth, Einsteinian spacetime if you later jumped into the black hole to see what was there. (Technically, because you’d violate the monogamy of entanglement.) 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.”

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. But crucially—and here I have to disagree with Stephen Hawking—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. 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.*

On this last question, it seems to me that Susskind and Juan Maldacena achieved a major advance in their much-discussed ER=EPR paper last year. 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* do the experiment! In other words, doing the experiment sends a *nonlocal signal* 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). 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? 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* between the two. 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. However, if you did the AMPS experiment, then the wormholes would *become* traversable, and could carry a firewall (or an innocuous happy-birthday message, or whatever) from the Hawking radiation to the black hole interior. (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. “ER=EPR” is Susskind and Maldacena’s shorthand for their proposed connection between wormholes and entanglement.)

Anyway, these heady ideas raise an obvious question: *how hard would it be* to do the AMPS experiment? Is sending a nonlocal signal to the interior of a black hole via that experiment actually a realistic possibility? 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. 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 (Quantum Statistical Zero Knowledge). In followup work (not yet written up, though see my talk at KITP and my PowerPoint slides), 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.

All of this suggests that, even *supposing* we could surround an astrophysical black hole with a giant array of perfect photodetectors, wait ~10^{69} 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* wouldn’t be a realistic prospect, even if the equations formally allow it! There’s no way to sugarcoat this: **computational complexity limitations seem to be the only thing protecting the geometry of spacetime from nefarious experimenters.**

Anyway, Susskind takes that amazing observation of Harlow and Hayden as a starting point, but then goes off on a different tack. For one thing, he isn’t focused on the AMPS experiment (the one involving monogamy of entanglement) *specifically*: he just wants to know how hard it is to do *any* experiment (possibly a different one) that would send nonlocal signals to the black hole interior. For another, unlike Harlow and Hayden, Susskind isn’t trying to show that such an experiment would be *exponentially* hard. 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. In other words, Susskind only wants to argue that creating a traversable wormhole would be “thermodynamics-complete.” 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.” (This state involves *two* entangled black holes in otherwise-separated spacetimes; according to ER=EPR, we can think of those black holes as being connected by a wormhole.) 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. Susskind wants to show that *even so* (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.

So that’s the setup. What new insights does Lenny get? This, finally, is where we circle back to the view of quantum circuit complexity as a clock. 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.** (Indeed, the length of the wormhole increases linearly with time, growing like the circuit complexity divided by the total number of qubits.) And the wormhole getting longer and longer is what makes it non-traversable—i.e., what makes it impossible to send a signal through.

Why has quantum circuit complexity made a sudden appearance here? Because in the CFT description, the circuit complexity continuing to increase is the only thing that’s obviously “happening”! From a conventional physics standpoint, the quantum state of the CFT very quickly reaches equilibrium and then *just stays there*. 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. And yet we know that the CFT state *is* evolving, for two extremely different reasons. 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. And secondly, because in the dual AdS description, the wormhole is continuing to get longer!

From this connection, at least three striking conclusions follow:

- 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*. We know that it’s physically relevant, because in the AdS dual description, it corresponds to the wormhole getting longer! - 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*. 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). 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. But in the CFT picture, stopping the wormhole from stretching corresponds to stopping the quantum circuit complexity from increasing! 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. 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. 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. (How exactly do Alice’s actions in the “bulk” affect the evolution of the CFT state? That’s an excellent question that I don’t understand AdS/CFT well enough to answer. All I know is that the answer involves something that Lenny calls “precursor operators.”) - The third and final conclusion is
*that there can be a physically-relevant difference between pseudorandom n-qubit pure states and “truly” random states*—even though, by the definition of pseudorandom, such a difference can’t be detected by any small quantum circuit! Once again, the way to see the difference is using AdS/CFT. It’s easy to show, by a counting argument, that almost all n-qubit pure states have*nearly-maximal*quantum circuit complexity. But if the circuit complexity is already maximal, that means in particular that it’s not increasing! Lenny argues that this corresponds to the wormhole between the two black holes no longer stretching. But if the wormhole is no longer stretching, then it’s “vulnerable to firewalls” (i.e., to messages going through!). It had previously been argued that*random*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. But Lenny rejects this argument, on the ground that the CFT states that arise in realistic situations are*not*random pure states. And what distinguishes them from random states? Simply that they have non-maximal (and increasing) quantum circuit complexity!

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. My question is: **could you ever learn the answer to an otherwise-intractable computational problem by jumping into a black hole?** Of course, you’d have to *really* 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! But never mind that. 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. 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. (It’s also possible that you *can* 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. I.e., that for real black holes, you’ll just see a smooth, boring, Einsteinian black hole interior no matter *what* polynomial-size quantum circuit you applied to the Hawking radiation.)

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 by Terry Tao. (See also the excellent *Quanta* article by Erica Klarreich.) 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.

Navier-Stokes existence and smoothness is one of the seven Clay Millennium Problems (alongside P vs. NP, the Riemann Hypothesis, etc). 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.

Expanding on ideas from his earlier blog posts and papers about Navier-Stokes (see here 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.” Why? Well, it’s not the computational universality *per se* 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.

Strikingly, building on an earlier construction by Katz and Pavlovic, Tao shows that** this is actually possible** for an “averaged” version of the Navier-Stokes equations! 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. In his paper, though, Tao hints at the possibility (or dare one say likelihood?) that the truth might go the other way. That is, maybe the “universal computer” construction can be ported from the averaged Navier-Stokes equations to the real ones. 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. Of course, such a result wouldn’t imply that real, physical water was in any danger of “blowing up”! It would simply mean that the discrete nature of water (i.e., the fact that it’s made of H_{2}O molecules, rather than being infinitely divisible) was essential to understanding its stability given arbitrary initial conditions.

So, what are the prospects for such a blowup result? Let me quote from Tao’s paper:

One minor point that I’d love to understand is, *what happens in two dimensions?* Existence and smoothness are known to hold for the 2-dimensional analogues of the Navier-Stokes equations. If they also held for the *averaged* 2-dimensional equations, then it would follow that Tao’s “universal computer” must be making essential use of the third dimension. How? 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.

I see that, in blog comments here and here, 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. 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.

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. But that’s what the comments section is for. Right now I’m going outside to enjoy the California sunshine.