Gigabug

ising machine

Overview

The Ising model is of fundamental computational interest because any problem in the complexity class NP can be formulated as an Ising problem with polynomial complexity.

$$ FIXME H = \sum_{(i, j)} J_{ij}s_i s_j - h \sum_i s_i $$

where $\textbf{J}$ is the weight matrix and $\textbf{h}$ is the bias. The state probability is then determined by the Boltzmann distribution

$$ P(E) = \frac{e^{-E/k_BT}}{\sum_{i} e^{-E_i / k_B T}} $$

An Ising machine is a physic device obeying this distribution. It represents probablistic logic and has general applications across optimization and generative machine learning.

Objective (binary) -> Ising Model (spin) -> Ising Machine (voltage)

This post documents my development of an Ising machine. My plan is to open-source and ship a PCB that plugs into your laptop to solve combinatorial problems. This will encourage further hardware and software research to make these machines competitive.

Quality of obtained solutions remains an open problem.

This project is particularly inspired by current research. Lyapunov theory is applied to the generalized Kurumoto model to contruct an “energy function” for stability analysis of chaotic coupled oscillators. A control input synchronizes the oscillations to a “low energy” steady state, and induces locking to binarize the phases.

Implemented as a network of coupled electric oscillators. Oscillator network has the natural tendency of minimizing dissipated power by minimizing the amount of interactions between oscillators.

In-memory computation. Different fundamental architecture Spread in oscillators natural frequency contributes a linear term in the global Lyapunov function

Ising Machine

Code for this project is on my Github. The simulated Kuramoto oscillator converges to the maxcut when applied with square wave.

Developing locally on Macbook. Simulation jobs will be sent to my local Linux server.

Oscillator

Programmatic Coupling Coupling based on problem encoding. Can’t interfere with oscillators. Use digital pins to select channel. Use analog A0 to write Some of these models are deprecated for boardboard

Two approaches:

Quality Factor Perturbation characteristics of the oscillator. Various definitions across hardware

Synchronization Schedule Encode problem weights coefficien the tendencies of the network Map binary optimization problems to synchronization tendencies to encode problem. Sub-harmonic Injection Locking (SHIL) external signal. Some prototypes converge naturally.

References

There are many physical realizations of Ising-like hardware seen in the literature.

These are some particular ones of interest.

The injection locking signal, and its application in the context of LC-oscillator systems is mathematically similar to the case of the degenerate optical parametric oscillator used in optical Ising machines. The optical pump pulses at twice the optical oscillation frequency to binarize phases. The phase of pump and signal should be locked for amplitude (Figure from Stanford CIM).