Cook-Levin for Physicists

It’s a late night, and you’re getting tired. You’ve just written down a very complicated and large Hamiltonian. Sure it’s a classical Hamiltonian, but it’s still rather beastly. A big beast which takes as input the configuration of a bunch of subsystems and outputs and energy of the system when it is in that configuration. And like all respectable Hamiltonians it’s got some of the standard features. It is local in nature and, this being the good old classical world, if someone gives you a classical configuration you can go through and calculate all of these local contributions to the energy and figure out the total energy. Your Hamiltonian isn’t very uniform, so you really do have to go through and calculate what each of these terms are. A long calculation, but not one you’re much worried about carrying out. And really it isn’t just a Hamiltonian for one system, but for a system of growing and growing size. But really this doesn’t bother you much as doing things like calculating the energy of a configuration doesn’t seem to grow too fast as a function of the system size.
On the other hand, what you’re most interested in, what you’re doing up so late at night, is that you really want to find the ground state configuration of this Hamiltonian (or if there are multiple ground states, at least one of them.) Actually since it is late at night you’ll settle for even less. You know that for each term in your Hamiltonian which couples a few subsystems, you can go through each local configuration on these few subsystems and calculate the possible energies that comes from this term. From this list we can write down the minimal value of the energy coming from this term. And because it’s late at night, what you really want to know is not necessarily the ground state, but instead you want to know whether the ground state energy of the system is the sum of all of these minimum energies. Can each separate term in you energy take on its minimal value?
Well it’s late and you’ve downed more coffee than a truck driving mathematician, but even in this state you realize that this isn’t going to be an easy problem. But wait! Who is that sitting across the room from you? You didn’t notice him come in. Strange. What? He’s trying to say something to you. A bunch of numbers he’s reciting. Hmm, strange. Those numbers seem to be related to configurations of the local subsystems in your Hamiltonian. Strange. Okay, well you are a physicist, so your halucinations are not usually what other people would call normal. Well you’d better write the configuration down before your halucination ends. Okay, now you’ve got a configuration for your system. What to do with it? What to do with it? Oh, obvious! Calculate its energy. Cool. Now what? What about calculating whether this energy minimizes each individual term in your Hamiltonian? Hmm, that’s a simple computation. So do it! What? Why yes, yes it is a configuration which minimizes each term in your Hamiltonian! Wonder of wonder this halucination has done all your hard work for you and given you a ground state which minimizes each individual term in your Hamiltonian. And while you know you are halucinating, you are certain that the calculation is true, because even during periods of mental inebriation, you’re calculating abilities are first rate and since you checked each that each term individually attained its minimal value. Holy moly, what an awesome halucination. Instead of having to try every single configuration (a task which scaled elephantly, err exponentially it is late you know), or even being smart about doing the calculation in a clever fashion, this halucination has provided you with a witness to the fact that your energy can minimize each term individually and all you have to do is do the individual local energy calculation. You need to start having more dreams like this.
A few weeks later.
You’ve written down your Hamiltonian and know that it has a ground state which minimizes each term in the Hamiltonian. Fame and fortunate has, strangely, however not descended upon you for this great achievement. However, for each Hamiltonian you write down it seems that you can put yourself in this halucinatory state and then low and behold a magical proof appears about whether your system has a configuration which minimizes each term individually. Sometimes, of course there isn’t such a configuration and your halucinations produce configurations which you quickly calculated don’t have minimal energies for each term. You’re never fooled and always right. Life ain’t that bad.
A few months later.
Why don’t these physicists recognize your genius? Sure it was a halucination which led you to your ansatzes, but I heard that Bethe guy was on something when he came up with his ansatz too. Uh oh, time to apply for faculty jobs. This might get ugly.
A few years later.
Ouch. Well that physics thing didn’t pan out. But this new computer industry is kind of interesting. Just the other day you were fiddling around with an interesting little simulator. This thing simulated what is called a Turing machine. Now why the computer scientists are so obsessed with this Turing fellow and his simple machine, you certainly can’t fathom. But it’s a cool little gadget. Basically you’ve got yourself a big long tape where you can write symbols into little cells and a machine which moves from cell to cell, writes into cells, and changes its internal configuration in a manner depending on what the current cell reads and the internal configuration of the machine. There is this big old table that you can write down all the information about the Turing machine in a nice small manner. It says, if you read symbol X and your internal state is Y, then write symbol S on the tape, move according to rule R, and change your internal state to S. Cool little gadgets these Turing thingamabobers.
So now that you’re employed in the computer industry you get to spend you days programming these little Turing thingamabobers. Hours of your day spent toiling over the design of the table. Yes, it is a painful existence. But the pay is better than in physics, so that is some consolidation. And your boss doesn’t make you work too many hours. On the other hand he wants you to design Turing thingamagigs that do their dastardly calculations pretty quickly. Like just recently you were designing the Turing machine for Jet Blue’s airline and employee scheduling machine and you had a great design, but your boss complained that it worked fine for a few airplanes in the fleet, but as the number of airplanes and employees grew, your algorithm scaled fairly poorly. Okay, well horribly poorly, like it would take the age of the universe to finish calculating for today’s airline fleet. And so you got chewed out by your boss who yelled the word “polynomial” at you so many times that you finally got the point that he wanted Turing machines that finished in a time polynomial in the number of airplanes and employees. What a strange concept to see those polynomials which were your great friends when calculating trajectories, show up between swear words in your boss’ family unfriendly diatribe.
So now you spend hours in your office each day, writing these Turing tables, and watching your Turing machines calculate away. Ticking away the moments that make a Turing day, you fritter and waste the hours in an offloaded way. Mostly you spend your time with the machines which have a polynomial running time, the ones your boss really likes. I mean you really don’t want to tick him off and have him shout exponential swear words at you. Now for a given problem your boss gives you, you come up with a little Turing machine which says, this problem has the answer “yes” or “no.” Your boss is big on these types of answers, you’re not sure quite why but perhaps it has something to do with his childhood spent communicating in a secret binary code with the surogate robotic sister his parents had designed for him after they learned they couldn’t have any more children.
Even more years later
Well the computer job has been real solid. You can retire now since your Turing machines helped bring peace between Facebook and MySpace. But lately you find your mind wandering. You’ve been thinking about these nice polynomial running time Turing gadgets which you design. You run the program and it tells you “yes” or “no.” Reminds you somehow, about what…. About your halucinations? Of course!
So you think a little bit more about this analogy. Before you had a Hamiltonian and could verify yes or no whether it had a ground state which minized each term individually. Now you have a Turing table which answers yes and no. Might there be a connection. Oh, this is going to hurt your head.
A few hours later
You’ve been daydreaming about these Turing gadgets all day now. Days spent lounging on the beach beside your mansion since, yeah, your computer job hit paydirt. You imagine the big long Turing tape with some initial scribbles on it representing the problem your boss gave you. Then you picture the Turing machine hacking away at this tape, creating for each of its new steps, a new long tape, perhaps with new symbols, but at one time step later. You imagine in your head the entire history of the Turing tape. You imagine also along this tape a history of the location of the Turing machine along with a record of the internal state of the machine on this space time diagram.
How might it be possible to connect this to your Hamiltonian hallucinations? Might it be possible to write down a Hamiltonian which has or does not have a ground state which minimizes each term in the Hamiltonian individually but this is related to that spacetime moviescript you were just imagining? First you imagine that the spacetime diagram is now a space-space diagram. Then you think about your Turing table. It is a specification of valid transitions your Turing machine can make. And if you ponder that spacetime diagram made up of Turing tape cells and Turing tape locations and Turing tape internal states, you think: well I could give to configurations in my space-space which have entries on the table zero energy and all other configurations in my space-space not in the table (invalid evolutions) energy one. And I could do this in a totally local way on this space-space diagram, so that the Hamiltonian I would write down would be local and only act on a few subsystems. Further I could set up the Hamiltonian at the beginning slice of time, which is now, say, the bottom slice of space in my space-space picture, such that the intial state of the Turing machine and Turing tape and Turing location only has energy zero and other states have energy one. Since I know this initial state I can write down that Hamiltonian locally. Finally at some point we’ll want an answer so we can assign an energy penalty for being in that last terminating configuration and outputing “no”, but if we are in that output configuration and outputing “yes” we can assign no energy penalty. Easy enough.
Bam. Cool! So it is possible to take your Turing time which runs in polynomial time along with its polynomial sized input and convert it to a Hamiltonian which is local and acts on a few subsystems at a time. Then answering whether that Turing machine will answer yes or no is the same as solving that problem your halucinations solved ages ago when you were poor and a physicist. Of course answering that question without your powerful halucinations isn’t possible without the magic of you going into a trance, but still! I mean all this work your boss has been having you do is related to a problem about the existence of a certain type of ground state of a Hamiltonian. Take that(!) computer science day job that has been so lucrative.
“Deus Ex Machina” years later, graveside
Well it’s been a good life. Why can you still hear me, aren’t I dead? Yes I’m dead, but this is a blog post so why be constrained by reality? Cool, it now seems that the people gathered for my funural are all giving some speaches about me. Better listening in.
“He was an obstinate man. So obstinate I always thought that when Death came to claim him he would plug his ears so as to escape Death’s entropic death chant. And probably stick his tongue out at Death at the same time. What killed him? We shall never truely know, I think, and the story is so strange. A few of us were sitting around talking about the golden days of classical computers and somehow the subject of complexity classes came around. Here was an icon of the MySpace/Facebook Middle Internet peace agreement, and he had never heard of the complexity class NP. So we patientily explained to him the class of problems which could be efficiently verified in polynomial time. And how all the problems in NP could be converted to a problem called satisfaction having to do with the whether a boolean function had an input which evaluated to one. And that this satisfaction problem itself was in NP. Everything in NP was effectively a SAT and every SAT was in NP. And he sat there tapping his head. Chanting ‘SAT was my Hamiltonian problem.’ And then he kicked over dead. So strange. Does anyone know what this Hamiltonian problem is? What Hamiltonian path was he speaking of? It must have been an interesting problem. Because he died with a smile on his face.”
Inspired by the Optimizer’s ‘Physics for Doofuses’ whose opposite is clearly ‘Computer Science for Physicists’.