One approach to establishing the relevance of Grothendieck-style mathematics to complexity theory is by way of tensor networks (a.k.a., tree states, product-sum states, Kronecker states, etc.). These networks can be alternatively understood in algebraic terms, or combinatoric terms, or geometric terms, or even (via sparse reconstruction theory, for example) information-theoretic terms.

Nowadays, we increasingly appreciate that there are strong connections among these points-of-view (for example, that the manifold of tensor network states has negative Ricci-Kähler curvature is important to the numerical tractability of quantum-state reconstruction from sparse random projections).

Just to mention, Grothendieck did write at considerable length on tensor product spaces … albeit without the advantageous informatic perspective on product spaces that modern QIT is providing. Hey … this means that our generation has at its disposal a crucial mathematical tool that Grothendieck’s generation lacked!

The Grothendieck point of view is that all of the preceding ideas can be understood as different aspects of *one* rising tide of theory. And perhaps this happy conception will even turn out to be true. ðŸ™‚

Grothendieck describes two styles in mathematics. If you think of a theorem to be proved as a nut to be opened, so as to reach “the nourishing flesh protected by the shell”, then the hammer and chisel principle is: “put the cutting edge of the chisel against the shell and strike hard. If needed, begin again at many different points until the shell cracks–and you are satisfied”. He says:

“I can illustrate the second approach with the same image of a nut to be opened. The first analogy that came to my mind is of immersing the nut in some softening liquid, and why not simply water? From time to time you rub so the liquid penetrates better, and otherwise you let time pass. The shell becomes more flexible through weeks and months–when the time is ripe, hand pressure is enough, the shell opens like a perfectly ripened avocado!

“A different image came to me a few weeks ago. The unknown thing to be known appeared to me as some stretch of earth or hard marl, resisting penetration. . . the sea advances insensibly in silence, nothing seems to happen, nothing moves, the water is so far off you hardly hear it. . . yet it finally surrounds the resistant substance. [Grothendieck 1985Â1987, pp. 552-3]1

“Softening the nut with water” referred to Grothendieck’s approach of building new abstractions to study a problem with.

]]>Specially for this post, I did a literature search and found that there are diverse opinions regarding the role that these practical geodetic investigations played in Gauss’ research (see the appended BibTeX references.)

IMHO, the best single article to read is Gauss’ own article *Disquisitiones generales circa superficies curvas*, which is available on-line in English translation as *General Investigations of Curved Surfaces*.

This celebrated article introduced the concept of what is now called Gaussian curvature, and established by Gauss’ *Theorema Egregium* (his name for the theorem) that this curvature is an intrinsic property of surfaces. Gauss thought so highly of the *Theorema Egregium* that he published it multiple times.

An additional reason that the *Disquisitiones generales* is well-worth reading for students, is that in it Gauss pretty much *invents* the modern academic style and idioms of academic writing (“it follows”, “we then have”, “it can be shown”, etc.). Hey, *someone* had to invent the idioms that nowadays every mathematician, scientist, and engineer uses … students might as well learn these idioms by studying the classics.

Oh yeah … did Gauss’ practical surveying work strongly influence his mathematical work in non-Euclidean geometry? Undoubtedly. Did Gauss envision, not only that the earth’s surface was curved, but that 3D space might be curved too? And did he experimentally test this idea? There is no definitive evidence either way. My own opinion, based on reading the *Disquisitiones generales*, is that Gauss found no evidence for 3D spatial curvature in his geodetic data, and in keeping with his general conservatism in such matters, declined to publish, as a mere speculation, a mathematical possibility of which he was well-aware.

Nowadays, of course, things are different, and vast herds of speculative theories roam the landscape. ðŸ™‚

To summarize: very roughly speaking, attempts to construct highly entangled states can be viewed as analogous to Gauss’ geodetic triangulations. In both cases, the technical difficulties are immense. In both cases, the practical applications are important (and pay the bills). And in both cases, the local structure always looks Euclidean/Hilbert, but it is mathematically and physically possible for the large-scale structure to significantly depart from linear extrapolation of the small-scale structure.

—-

@article{Breitenberger:1984qy, Author = {Breitenberger, Ernst}, Journal = {Archive for History of Exact Sciences}, Number = {3}, Pages = {273–289}, Title = {Gauss’s geodesy and the axiom of parallels}, Volume = {31}, Year = {1984}}

@article{1972, Author = {Miller, Arthur I.}, Journal = {Isis}, Number = {3}, Pages = {345–348}, Title = {The Myth of Gauss’ Experiment on the Euclidean Nature of Physical Space}, Volume = {63}, Year = {1972}}

]]>On the main topic of the thread, regarding new quantum algorithms: 1) In most of scientific computing algorithms moving from an nlogn time algorithm to a linear algorithm would be a sensational progress theoretically and practically. Is there some work on quantum speed-up for these and others “low-complexity” algorithms? 2) one quantum algorithm fantasy that I (and others) have (which never got off the ground) would be to come up with quicker quantum algorithm for linear programming or LP-type problems. For exmple: consider the discrete n-dimensional cube and a unique sink acyclic orientation of its edges. (This mean that for every subcube there is a unique sink.) The question is how quickly can you find the sink. Classical random-walk-based algorithms are exponential (the best known is exp (sqrt n) ) and any quantum or clasical improvement would be great. 3) I am sure that the quantum-subroutine allowing sampling the Fourier transform of an n variable function in polynomial time will have many additional applications.

]]>Gil, I hadn’t met you at the time I wrote that paper. ðŸ™‚

]]>Perhapas a relevant lesson from history is that Gauss—working as a civil engineer—attempted (seriously) to observe departures from Euclidean geometry in large-scale surveying, just as we presently attempt to observe departures from from Euclidean quantum mechanics in large-scale physical dynamics.

In both cases, the looked-for phenomenon was defined only vaguely: tiny departures from spherical geometry in Gauss’ case, tiny departures from linear quantum superposition in the present case.

In both cases, the immediate practical challenge was noise in measurements, sufficient to mask the (tiny) expected effects.

In both cases, the required revision of physical theory was far more radical than was originally foreseen: the geometry of classical state-space needed to be treated dynamically in Gauss’ case, and (perhaps) the geometry of quantum state-spaces needs to be treated dynamically in the present case.

It both cases, it was not obvious that departures from classical values could occur in a logically consistent way (geometric consistency was the tough issue in Gauss’ case, causal and informatic consistency are the tough issues in the present case).

In both cases, the development of stronger physical theories awaited the development of stronger physical insights and stronger mathematical tools. In Gauss’ case, progress awaited the physical principle of relativity as embodied in Riemannian geometry, and in the present case, progress awaits the physical principle of (????) as embodied in the mathematics of (????).

So just fill in the (????), and your achievements surely will be as celebrated as those of Gauss and Einstein.

Thus, in asking us to fill in the (????), Scott has set the bar *very* high … which is why this is a truly great weblog topic!

Another (less dramatic) lesson from history is that the physical principle of (????) and the mathematical principle of (????)—whatever they turn out to be—are likely to have considerable value in practical engineering. So perhaps it is not a complete waste of time, to try to do some practical engineering along the way (as Gauss did).

My own best candidate for the physical principle of (????) is Choi’s Theorem (which Thm. 8.2 of Nielsen & Chuang), but as for its generalized mathematical expression in (????), there I have no clear ideas (except “just start coding”) … but perhaps some other *Shtetl Optimized* reader does. ðŸ™‚