4by12

Hypercubes and Hamilton Circuits

The Ising model is a simple model used to describe a magnet: It consists of a grid of spins. Each spin can be thought of as a tiny magnet, and can have the value +1 or -1 (called ‘up’ and ‘down’). Two neighboring spins interact, having positive energy if they are in opposite directions (e.g. up and down), and negative energy if they are in the same direction. So, neighboring spins ‘want’ to be in the same direction, to minimize energy.

This model is used to calculate various properties of magnets. For example, suppose we want to measure the average magnetization of the grid in a given temperature. The magnetization of a specific state is just the sum of all the spin values in that state. So if all the spins are up and the grid size is 5×5, the magnetization is 25. To calculate the average magnetization, we’d have to know the probability of each state. We’d then multiply each state’s magnetization by the probability of reaching that state, and sum over all the states. The probability distribution is given by the Maxwell-Boltzmann distribution, an important result of statistical physics.

If the grid size is sufficiently small (up to about 5×5), we can actually go over all the possible states and calculate an accurate average value for the magnetization. What is the most efficient way of going over all the states? It is very convenient to implement this algorithm by flipping just one spin at a time. In this case, the most efficient algorithm would iterate over the possible states by flipping just one spin in each step.

Let’s think of a state as a series of bits, 0 meaning a spin value of ‘down’ and 1 meaning a spin value of ‘up’. We can think of this series as a binary number, and iterate the states by incrementing this number. For example, if the grid size is 2×2, then we can iterate as follows: 0000, 0001, 0010, 0011, 0100, … This method works, but it takes more than one spin to switch states (on average). For example, going from 0111 to 1000 requires 4 flips. It is easy to see that the average number of flips per step for a series of length n is approximately:

With the limit taken as .

Let’s try to improve on this. In a previous post, I noted that we can think of a hypercube’s vertex as a series of bits. So iterating over all the spin states is like walking on a hypercube, visiting all of its vertices. We want to flip just one spin at each step — that would be the most efficient algorithm. In the hypercube analogy, this is the same as saying we are allowed to walk only on the graph’s edges, because edges only connect vertices that differ by exactly one bit. So now we’re trying to find an algorithm that walks the edges of a hypercube, vists all the vertices, and vists each vertex exactly once. This is almost the definition of a Hamilton circuit, except we don’t have to go back to the first vertex at the end.

Trying it out for a 3D cube, it’s obviously very easy to do this: We can start at the top face and walk through the 4 vertices there. Then we can ‘climb down’ to the bottom face, and finish walking through the bottom 4 vertices. We can generalize this concept inductively: Given such an algorithm for an (n-1)-hypercube, we can use it to build an algorithm for an n-hypercube: Start with the vertex 0000…0, and use the (n-1) algorithm to go over all the 0xxx..x vertices. Let’s say the algorithm finishes at vertex 0111…1. Next, ‘climb up’ to vertex 1111…1, and run the (n-1) algo. backwards to go through all the ‘upper’ states, reaching 1000…0. We can even complete a full Hamilton cycle by climbing back down to 0000…0.

Of course, we have an algorithm for n=0, so inductively we get an algorithm for every n. This algorithm goes over all the states, using just one flip (or edge) for each step.

When I told my girlfriend about my discovery, she told me this was a well-known method called Gray code. Party pooper.