Navier-Stokes Fluid Computers

how-magneto-rheological-suspension-works-8947_2

Smart fluid

Terry Tao posted a very intriguing post on the Navier-Stokes equation, based on a recently uploaded paper Finite time blowup for an averaged three-dimensional Navier-Stokes equation.

The paper proved a remarkable negative answer for the regularity conjecture for a certain variants of the NS equations, namely (or, perhaps, more precisely) the main theorem demonstrates finite time blowup for an averaged Navier-Stokes equation. (This already suffices to show that certain approaches for a positive answer to the real problem are not viable.) The introduction ends with the following words.

“This suggests an ambitious (but not obviously impossible) program (in both senses of
the word) to achieve the same e ffect for the true Navier-Stokes equations, thus obtaining a negative answer to Conjecture 1.1 (the regularity conjecture for 3D NS equation)… Somewhat analogously to how a quantum computer can be constructed from the laws of quantum mechanics [Here Tao links to Benio ff’s 1982 paper: “Quantum mechanical Hamiltonian models of Turing machines,”], or a Turing machine can be constructed from cellular automata such as “Conway’s Game of Life” , one could hope to design logic gates entirely out of ideal fluid (perhaps by using suitably shaped vortex sheets to simulate the various types of physical materials one would use in a mechanical computer). If these gates were sufficiently “Turing complete”, and also “noise-tolerant”, one could then hope to combine enough of these gates together to “program” a von Neumann machine consisting of ideal fluid that, when it runs, behaves qualitatively like the blowup solution used to establish Theorem 1.4.[The paper’s main theorem] Note that such replicators, as well as the related concept of a universal constructor, have been built within cellular automata such as the “Game of Life.”

Once enough logic gates of ideal fluid are constructed, it seems that the main difficulties in executing the above program are of a “software engineering” nature, and would be in principle achievable, even if the details could be extremely complicated in practice. 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. 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 di fference of having a linear evolution rather than a nonlinear one) may prove to be useful. (Emphasis mine.)

Interesting idea!

And what Tao does go well beyond an idea, he essentially implement this program for a close relative of the NS equation!  I am not sure if universal computing is established for these systems but the proofs of the finite-time blow up theorem certainly uses some computational-looking gadget, and also as Terry explains some form of fault-tolerance.

Somewhat related ideas (unsupported by any results, of course,) appeared in the seventh post “Quantum repetition” of my debate with Aram Harrow on quantum computing.  (See, e.g., this remark, and this one, and this one.) The thread also contains interesting links, e.g. to Andy Yao’s paper “Classical physics and the Curch-Turing Thesis.”  In addition to the interesting question:

Does the NS-equation in three-dimension supports universal (classical) computation,

we can also ask what about two-dimensions?

Can NS-equations in two dimension be approximated in any scale by bounded depth circuits?

One general question suggested there was the following: “It can be of interest (and perhaps harder compared to the quantum case) to try to describe classical evolutions that do not enable/hide fault tolerance and (long) computation.”

Another interesting comment by Arie Israel is: “I was surprised to learn that experimental fluid mechanics people had thought of this analogy before. Apparently the key name is ‘Fluidics’ and those ideas date back at least to the sixties.”

cih2

Update: Here is the first paragraph from a nice article by  Erica Klarreich entitled A Fluid New Path in Grand Math Challenge on this development in Quanta Magazine:

In Dr. Seuss’s book “The Cat in the Hat Comes Back,” the Cat makes a stain he can’t clean up, so he calls upon the help of Little Cat A, a smaller, perfect replica of the Cat who has been hiding under the Cat’s hat. Little Cat A then calls forth Little Cat B, an even smaller replica hidden under Little Cat A’s hat. Each cat in turn lifts his hat to reveal a smaller cat who possesses all the energy and good cheer of the original Cat, just crammed into a tinier package. Finally, Little Cat Z, who is too small to see, unleashes a VOOM like a giant explosion of energy, and the stain disappears.

And here is a follow up post on Tao’s blog (and a few more II, III), and a post on Shtetl Optimized.

The flip side

Update (June 14): It is worth noting that while the purpose of Tao’s program is to show finite-time blow up of the 3D Navier Stokes equations (as is often the case) these lines of ideas can potentially be useful also toward a positive solution of the regularity conjectures. Specifically, one can try to show that 3D Navier-Stokes equations do not support universal classical computation and even more specifically do not support classical fault-tolerance and error correction. Also here some analogy with quantum computation can be useful: It is expected that for adiabatic processes computation requires “spectral gap” and that gapped evolutions with local Hamiltonians support only bounded depth computation. Something analogous may apply to NS equations in bounded dimensions.

There are many caveats, of course,  the quantum results are not proved for D>1, NS equations are non-linear which weakens the analogy, and showing that the evolution does not support computation does not imply, as far as we know, regularity.

Three more remarks: 1) On the technical level an important relevant technical tool for the results on gapped systems with local Hamiltonians is the Lieb-Robinson inequality. (See, e.g. this review paper.)  2) for classical evolutions a repetition mechanism (or the “majority function”) seems crucial for robust computation and it will be interesting specifically to test of 3D Navier-stokes support it; 3) If computation is not possible beyond bounded depth this fact may lead to additional conserved quantities for NS, beyond the classical ones. (One more, June 28): It looks to me that the crucial question is if NS equations only support bounded computation or not. So this distinction captures places where circuit complexity gives clear mathematical distinctions.

Pictures from Recent Quantum Months

akm2

A special slide I prepared for my lecture at Gdansk featuring Robert Alicki and I as climber on the mountain of quantum computers “because it is not there.”

It has been quite a while since I posted here about quantum computers. Quite a lot happened in the last months regarding this side of my work, and let me devote this post mainly to pictures. So here is a short summary going chronologically backward in time. Last week – Michel Dyakonov visited Jerusalem, and gave here the condensed matter physics seminar on the spin Hall effect. A couple of weeks before in early January we had the very successful Jerusalem physics winter school on Frontier in quantum information. (Here are the recorded lectures.) Last year I gave my evolving-over-time lecture on why quantum computers cannot work in various place and different formats in Beer-Sheva, Seattle, Berkeley, Davis (CA), Gdansk, Paris, Cambridge (US), New-York, and Jerusalem. (The post about the lecture at MIT have led to a long and very interesting discussion mainly with Peter Shor and Aram Harrow.) In August I visited Robert Alicki, the other active QC-skeptic, in Gdansk and last June I took part in organizing a (successful) quantum information conference Qstart in Jerusalem (Here are the recorded lectures.).

And now some pictures in random ordering

2013-08-01 10.09.28

With Robert Alicki in Gdynia near Gdansk

seattle

With (from left) Connie Sidles, Yuri Gurevich, John Sidles and Rico Picone in Seattle  (Victor Klee used to take me to the very same restaurant when I visited Seattle in the 90s and 00s.) Update: Here is a very interesting post on GLL entitled “seeing atoms” on John Sidles work.

photo

With Michel Dyakonov (Jerusalem, a few days ago)

Gil+Mihai

With Michal Horodecki in Sopot  near Gdansk (Michal was a main lecturer in our physics school a few weeks ago.)

aramgil2

Aram Harrow and me meeting a year ago at MIT.

2013-08-01 10.12.45

2013-08-01 10.12.52

Sometimes Robert and I look skeptically in the same direction and other times we look skeptically in opposite directions. These pictures are genuine! Our skeptical face impressions are not staged. The pictures were taken by Maria, Robert’s wife. Robert and I are working for many years (Robert since 2000 and I since 2005) in trying to examine skeptically the feasibility of quantum fault-tolerance. Various progress in experimental quantum error-correction and other experimental works give good reasons to believe that our views could be examined in the rather near future.

QS

A slide I prepared for a 5-minute talk at the QSTART rump session referring to the impossibility of quantum fault-tolerance as a mild earthquake with wide impact.

GTprod2This is a frame from the end-of-shooting of a videotaped lecture on “Why quantum computers cannot work” at the Simons Institute for the Theory of Computing at Berkeley. Producing a videotaped lecture is a very interesting experience! Tselil Schramm (in the picture holding spacial sets of constant width) helped me with this production.