Missed connections

Via Stan Carey, the UChicago press has put the History of Cartography online; I can't view some of the pdfs but this is probably because I'm using an old version of Acrobat. I was esp. fascinated by the chapters on surveying and mapping in the Roman Empire, with all the gromas and dioptras and portable sundials... Something that caught my eye was this bit about digging tunnels and aqueducts:

If [tunnels] were dug from both sides simultaneously, the result might be a near miss, as happened with the Siloam tunnel or that mentioned by Nonius Datus. To avoid this, the Greek mathematician Heron (Hero) of Alexandria, who was evidently writing at some time around A.D.62, shows by a plan the method he advocates.

Heron's construction looks like this:

The cartography book gives a rather opaque account of Heron's idea but it's actually quite simple (as Tom Apostol explains). Suppose you want to dig a tunnel from B to D through the amorphous blob that is the mountain. You have to know the angle at which you should be going in. Observe, first, that once you know the lengths of the two legs BM and DM of any right angled triangle (BMD) whose hypotenuse is BD you're in business, because you can construct triangles BNO and DQP that are similar to BMD but lie outside the mountain, so you can construct the lines OB and PD which are the lines along which you should dig. So how do you work out the dimensions of BMD? Heron's idea is to traverse the hillside making only strictly perpendicular turns and keeping track of how far you go. You can work out MD by adding up all the vertical legs, and BM by subtracting all the right-moving from the left-moving legs. Knowing MD/BM, as well as the direction of the lines BM and LD, allows you to construct similar triangles around the edges. [NB the lines are tangents to the hillside in this picture but this is entirely unnecessary.]

According to Tom Apostol, Heron suggested that this was how the tunnel of Samos was built, and for a long time historians accepted this story. The problem with the method is, however, glaringly obvious, once you realize that you've also got to worry about changes in height. (If only because the notion of a right angle only exists in flat space.) The area around a tunnel is typically hilly, which means that the right-angle-making traverse would look something like this:

It should be immediately obvious to any scientist that this won't work at all, barring some incredibly precise way of measuring right angles, because all the little deviations from 90 degrees will add up. Heron's proposed angle-measuring device, the dioptra, was nowhere near adequate:

In practice, each application of such a tool (the dioptra included) necessarily introduces an error of at least 0.1 degree in the process of physically marking the terrain. The schematic diagram on page 33 shows a level path with 28 right angles that lines up perfectly on paper, but in practice would produce a total angular error of at least two degrees. This would put the two crews at least 30 meters apart at the proposed junction. Even worse, several of these right angles would have to be supported by pillars 10 meters high to maintain constant elevation, which is unrealistic. A level path with pillars no more than one meter high would require hundreds of right angles, and would result in huge errors in alignment.

(One wonders, btw, why the Greeks considered it so important to dig a tunnel from both sides.) Heron was a profoundly interesting character, whose other achievements include an extremely useful formula for the area of a triangle, and (most strikingly) the first recorded vending machine:

The first vending machine was also one of his constructions, when a coin was introduced via a slot on the top of the machine, a set amount of holy water was dispensed. This was included in his list of inventions in his book, "Mechanics and Optics". When the coin was deposited, it fell upon a pan attached to a lever. The lever opened up a valve which let some water flow out. The pan continued to tilt with the weight of the coin until it fell off, at which point a counter-weight would snap the lever back up and turn off the valve.

And various theatrical contrivances

including an entirely mechanical play almost ten minutes in length, powered by a binary-like system of ropes, knots, and simple machines operated by a rotating cylindrical cogwheel. The sound of thunder was produced by the mechanically-timed dropping of metal balls onto a hidden drum.

(As a pioneer of cybernetics, Heron should have known that his tunnel-digging scheme was not self-correcting.)

PS I believe the standard form of the name nowadays is Hero, but my reasons for preferring the "Heron" variant  are too obvious to be worth mentioning.

Laughter and forgetting; correlation and causation

Earlier today I expressed some probably unwarranted puzzlement at noted druggie S.T. Coleridge's diary entry about laughter and memory loss:

Analyze the causes that the ludicrous weakens memory, and laughter, mechanically, makes it difficult to remember a good story.

Perhaps one should blame this on the ludicrousness of the connection, but I had forgotten that Coleridge was friends with noted druggie Sir Humphry Davy, who was the first person to study the effects of nitrous oxide on humans (i.e., himself), and appears to have quite liked it:

I have felt a more high degree of pleasure from breathing nitrous oxide than I ever felt from any cause whatever—a thrilling all over me most exquisitely pleasurable, I said to myself I was born to benefit the world by my great talents.

(Coleridge also told Davy he was going to "attack chemistry like a shark.")

It is not clear whether others who have addressed this topic, like Milan Kundera (The Book of Laughter and Forgetting) were also noted druggies. Regardless, it seems likely that Coleridge at least was confusing causation with correlation. (PS could Humphry D have been the person from Porlock?)

Adiabatic quantum computation in Egypt

I am amused by the recent proliferation of things Egypt-related but not Egypt-specific essentially related to the current mess. This is the case, e.g., with Hernando de Soto's [1] WSJ op-ed on property rights in Egypt, and, more benignly, with this old NASA photograph of Cairo and Alexandria that has been circulating about the internet. (Alexandria turns out to be one of those long skinny coastal cities like Santa Barbara.) I suppose there's no harm in using topical excuses to force one's longstanding obsessions down the casual reader's throat, though it's hard to do this in a way that's not misleading. So instead of parodying de Soto with "How Egyptian protesters used the laws of gravity to bring down the regime," I'll just write a physics-y post that I was meaning to anyway and add "in Egypt" the way one adds "in bed" at the end of a fortune cookie.

[NASA photo, Flickr, creative commons, etc.]


What follows really belongs on the defunct physics blog, being a little technical. But it isn't really physics, and has to do, besides, with the work of Dorit Aharonov, another of the squalid scholars.

---

1. Conventional quantum computers are structured like Turing machines. They consist of a (finite) set of internal states (logic gates, etc.) and a "tape" which (at the beginning of the computation) has the input string written on it, say in Arabic numerals. The tape is connected to the machine by a read-write head. At each step of the algorithm one can move the tape back and forth, change the internal state, and/or write on the bit of tape that's under the head. At some point the algorithm stops (assuming the problem is decidable); this happens when the internal state of the machine is the designated "end" state and the answer to the original problem is on the tape. Quantum computers differ from classical computers in that the number of allowed tape configurations is (in principle) much larger, as superpositions are allowed in intermediate steps. The complexity of an algorithm is related to how many steps it takes to process an input string of length N, and in particular how this grows with N (e.g., polynomially/exponentially). The complexity of a problem is the complexity of the asymptotically slowest-growing (at large N) algorithm that can solve it.

The problem with this construction is that, while it is easy to find upper bounds for complexity (just write down an algorithm), it is generally hard to establish lower bounds, because it is hard to make useful statements about all conceivable algorithms, or to rule out the possibility that one is just not being clever enough. Generally in this sort of situation one's instinct is to look for a way of talking about the "space of all problems," which (if one is lucky) has some degree of geometric structure -- so that, e.g., two problems are "near" or "far" in problem space.

2. Adiabatic quantum computation begins with the observation that "satisfiability" problems in computer science [2] can be recast in terms of the physics of magnets. Magnets consist of spins that can either point up or down (i.e., true or false); depending on the details, spins might want either to line up or to point in opposite directions [3]. Depending on the interactions there might be a "good" configuration for the spins (i.e., one in which all pairs of spins that want to line up do so and all pairs that want to point in opposite directions do so) or not. (In the latter case the system is called "frustrated." A simple example of a frustrated system: three spins on a triangle that all want to point in opposite directions. If 1 is up, then 2 and 3 want to point down, but this doesn't work because 2 and 3 want to point in opposite directions. No configuration satisfies all the bonds in Egypt.) The lowest possible energy of a frustrated system is higher than that of an unfrustrated system, so the question of whether a spin system is frustrated reduces to that of what its lowest possible energy ("ground state energy") is. Obviously the question of whether a spin system is frustrated is closely related that of whether a set of statements can be satisfied, if you map the clauses onto spins (T/F = up/down). There are some explicit examples of this mapping in the original paper of Farhi et al.

3. This mapping isn't immediately useful as it just recasts the satisfiability problem in the language of magnetism. This is where the physics comes in. Farhi et al. observed that the quantum mechanical "adiabatic theorem" tells you that, if you change your Hamiltonian (the Hamiltonian of a system is an assignment of an energy to every possible configuration of the system) sufficiently slowly, the ground (lowest-energy) state of the original Hamiltonian goes into the ground state of the final Hamiltonian. How slowly you have to go depends on the energy gap between the ground and the next-lowest-energy (first excited) state all along the path in "Hamiltonian space" that leads from the initial to the final Hamiltonian. The bigger the minimum gap, the faster you can afford to go. Often the minimum gap vanishes in the large-system limit (this is called a quantum phase transition); in this case you have to go arbitrarily slowly as the number of spins increases. The minimum allowed speed might either vanish as a power-law or exponentially with the system size. Alternatively there might be exact "degeneracies" for finite systems in which case the algorithm is doomed.

4. The adiabatic algorithm works like this. You start the system off in some reference "trivial" state, let's say with a Hamiltonian that wants all the spins to point up. (E.g. spins in a strong external field.) Call this H_0. The problem Hamiltonian, which encodes the input -- the logical expression you want to check the satisfiability of -- is called H_1. You turn a hypothetical knob so that at time t, the Hamiltonian is H(t) = t/T H_1 + (1 - t/T) H_0. Or you use a curvier path. Assuming T is large enough, the ground state of H(T) is the answer to your problem. The complexity question becomes one of finding the path with the slowest-growing T(N); in general the slowness comes from segments of the path that are near the phase transitions between the initial and final states; the gaps here are given by the theory of critical slowing down; therefore you have mapped the complexity problem into a problem about phase transitions. To rephrase, what this approach does for you is it maps the space of problems onto the space of quantum Hamiltonians, the structure of which can be understood in terms of renormalization group flows.

5. Satisfiability problems aren't everything. The Aharonov et al. paper establishes that adiabatic quantum computation is equivalent to standard quantum computation. (I haven't read the proof.)

6. Of course, the Hamiltonians of conventional magnetic systems are what they are; you can't implement the adiabatic algorithm as stated, and it isn't likely to be terribly useful as a means of quantum computation. However, one does have a fair amount of control over the Hamiltonians describing cold atomic gases, and there's been a fair amount of work on actually implementing the algorithm. A variant that's been proposed is computation-through-dissipation, which is a clever mashup of the adiabatic algorithm and optical pumping. I'm a little skeptical about the practical prospects for this approach, but it is theoretically interesting because dissipative systems are hard to analyze and it would be nice if one were able to use the mapping in reverse and use computer science results to say something about them.

---
[1] Yes, I considered calling him Hernando de Stoato and posting this on STOATUSblog.
[2] Viz. questions about whether a very long logical string is true on any assignment of truth-values to its constituent particles, which, e.g., A or B is but A and not-A isn't
[3] In a physical system this depends on why the spins are interacting at all; there are various possible mechanisms. In the model one puts this in by hand by assigning an energy penalty to undesired configurations.

"Rotting oranges, used tissues and odd socks"

Maybe Empson and Auden are my favorite literary personalities because I can "identify" (dread word!) with their lifestyles. For instance, here is Frank Kermode reviewing a biography of Empson:

His victims were usually confident that his habits in controversy were in some measure aspects of a more general eccentricity: the strangled, oddly inflected voice or voices, the peculiar beard, the use of drink to lubricate all argument, to get something started. [...] Money worries in the final years required him to spend time at American universities, teaching, lecturing, and reinforcing his reputation for bizarre or clownish behaviour. A colleague at Penn State notes that ‘he went back at night to a place full of rotting oranges, used tissues and odd socks’, and records that ‘he once, for some minutes, watched my neighbour’s door lamp through my telescope, thinking it Mars.’ Dining with Marshall McLuhan, ‘I thought I had to explain to him that he was worshipping the devil, being a Roman Catholic. It was at his own dinner table, but the ladies had gone for their pee, so it wasn’t really rude.’ On a visit to Harvard he was ‘truculent and contradictory’ towards Richards.

There is something heartening about all the drunkenness and especially the squalor. (Remember the Auden martini?) Both W.E. and W.H.A. had Robert Lowell as a gleeful describer of their living habits; Kermode quotes Lowell on Empson:

Not that conditions in their Hampstead house were very different from those of the Sheffield ‘burrow’ – they were described by Robert Lowell as having ‘a weird, sordid nobility’

And there is a wonderful passage in one of Lowell's letters to Elizabeth Bishop -- collected in Words in Air, which btw is a must-read, but is in storage like most of my other books -- on Auden's Manhattan parties. (I find it interesting how much more natural it seems for nobility to be sordid than to be, say, hygienic: is it that we associate the aristocracy with decline or that we associate it with antiquity, which is automatically dirty [1]?  Empson is very "gentry" -- the legend has pushed this angle, referring to him as a squire etc. And isn't there a thing about bad teeth as well?)

I went back to the Kermode articles because Empson's been "in the news" lately, at least to the extent that my feed represents "the news" -- first of all there was that Michael Wood article on True Grit:

If traditional pastoral often idealises the simple life, it never quite chases the shadows of cruelty and corruption away, and what William Empson called the trick of simplification was always the thing. The mode kept remembering what it was ostensibly getting rid of.

The "trick of simplification" is a notion I'd like to associate with Empson's prehistory as a mathematician though I'm not sure this is right; certainly the Pastoral book is preoccupied with a kind of structural question that lends itself to "modeling," and I have sometimes wondered whether what one does as a theoretical physicist isn't related to pastoral in the sense that, instead of attacking a complex and idiosyncratic problem directly, one takes an entirely different, heavily simplified, and more "conventional" situation, treats it, and points out that the relations between certain entities in the original problem and the (asserted-to-be) analogous ones in the simplified one are -- unexpectedly as it were -- the same [2]. Mathematics is in this telling the individual or collective unconscious; it has many of the right properties for this role, and I suppose one can think of complex things like the weather as perversions of some submerged mathematical inclination. Of course none of this is useful as an account because there is no moral significance to the complexity of nature.

And then there was an article on "six types of clarity" that Marina sent me in response to my saying that something was an ambiguity of the second kind. ("I like it that you clarify which kind of ambiguity you're talking about." Admittedly an odd thing to do, but I do think Empson's types 1, 2, and 4 describe specific effects for which I don't know of any other terminology.) It's a very nice article and has some insightful things to say about an issue I blogged about sometime ago re "primitive" poetry. Of which more later.

---

[1] One is tempted to assume an association between messiness and vitality, but this falls apart after say the 17th century. The Rochester character in The Man of Mode doesn't use deodorant but is irresistible -- the expected pattern -- but generally the bourgeoisie and esp. the nonconformists are (a) on the rise, (b) not notably filthy, (c) not irresistible, at least qua bourgeoisie, (d) [possibly] breeding like rabbits. (Not sure about (d) in popular perception. Might be projecting backwards from the Mormons. Not sure either how far northern accents would stand in for filthiness -- the Chatterley line of reasoning, though gamekeepers were not bourgeois.) There's something odd about the fact that neatness is perceived as a diminishing virtue, even as far back as Johnson's comparison of Dryden and Pope. I suppose this is all linked in some tenuous way to the dissociation-of-sensibility thesis and the idea that poetry has never come to terms with modern life, has never found the right things poetical, etc.

[2] There are some areas, like string theory, to which this paradigm doesn't evidently apply. One probably wants to think of the Standard Model as the idiosyncratic, complicated system that is being simplified. But there isn't really a notion of "universality" there as there is elsewhere, so this isn't a natural description.