The Ising on the Cake

Just when you thought you knew all the possible foundations for computing, along comes another one. Forget von Neumann, this approach models Ising machines, systems built on solving a statistical ensemble model of ferromagnetism. The concept is quite simple. Imagine a lattice of magnetic dipoles/spins, each of which can only be in a “north-up” or “north-down” state. The coupling, in various states, when summed over adjacent magnets represents an energy and the goal is to minimize this energy.

As you might expect, this model maps neatly to various kinds of optimization problem. The travelling salesman problem (TSP) is one example, encountered in chip place and route tools, network routing, aircraft and truck routing and many other problems. TSP is considered an NP-hard problem though heuristic solutions are known and widely used. But improving on any of these solutions is always challenging since scaling up parallelism is quickly defeated by exponential growth in combinational complexity as the problem size grows.

While neural net and quantum annealing approaches are also being explored, advances based on Ising modelling have been reported recently. Rather than building spin lattices this approach uses laser pulses circulating through a ring cavity. Pulses are generated from a pumping laser as optical parametric oscillators (OPOs), a particular form of squeezed light. Each of these, above an oscillation threshold, splits into one of two possible phases which can model Ising spins. The ring cavity is designed to allow a fixed number of evenly-spaced OPOs to circulate through the ring at any one time, thus modelling a set of spins.

Next you have to model the coupling between the spins. In one approach, optical taps into the cavity take a small percentage of an OPO, delay it for an integral number of OPOs in the chain and couple that percentage back into the next OPO in line. There are N-1 taps for a cavity supporting N OPOs. This enables modeling a coupling between the i[SUP]th[/SUP] and j[SUP]th[/SUP] spins for any (non-equal) i and j. (The optical tap approach becomes very cumbersome with increasing N, so recent approaches have switched to electronic methods to add delay.)
Of course this ring of OPOs decays over time and the decay rate for any OPO depends on the phase states in the OPO. The decay rate of the system of OPOs can be engineered through couplings to model the energy profile (Hamiltonian) of a target Ising problem. (You’ll have to take that on trust or follow the 3[SUP]rd[/SUP] link below.) Now the OPO system is pumped by a laser, starting below the oscillation threshold. As the gain through pumping is slowly increased, it will eventually reach the lowest point in that profile which is a threshold for oscillation/resonance and that will self-reinforce. This by the way is known as the minimum gain principle, intuitively reasonable but not provably true. Finally, by observing the relative phase state of OPOs, resonances and hence minima in the problem space can be detected.

So there you have it. Technically, I don’t imagine other optimization techniques are in great danger in the near future. This is a very complex technique requiring some very sophisticated control of laser optics, probably not reducible (near-term) to a chip. Still, it does have one very interesting characteristic. All optimization techniques I know start on the problem curve and move around to (hopefully) find the lowest point. This technique starts below the problem curve and effectively moves a global metric (OPO system gain) up towards the curve. By construction the first thing it will hit is the global minimum (at least if the minimum gain principle is valid).

As a footnote, I checked a number of articles on this topic and found all the “popular” articles (Wired, a Stanford report, IEEE Spectrum) ducked any real attempt at explaining the method, which left me feeling cheated. This blog is my attempt to go at least a little deeper. Apologies in advance to experts in the field if I butchered the explanation – feel free to correct me. You can read a lightweight write-up HERE and the arXiv papers I relied on most HERE and HERE.

More articles by Bernard…