An Ising machine is a special-purpose computer that solves combinatorial optimization problems by mapping them onto the search for the ground state of an Ising model and letting a physical system, rather than an algorithm, find that ground state. The "spins" of the model are represented by bistable states of oscillators, light pulses, superconducting circuits or electronic devices, and the interactions between spins by programmable couplings. Ising machines have been an active field of research since the 2010s as an alternative to conventional computers for hard optimization tasks.
Principle The Ising model assigns to a configuration of spins the energy
where is the coupling between spins and and a local field. Finding the minimum-energy configuration is NP-hard for general couplings. Conversely, many classical optimization problems – the maximum cut of a graph, the partition problem, graph coloring or the travelling salesman problem – can be written as Ising problems by a suitable choice of the and .
An Ising machine realizes this energy function physically: each spin is an element with two stable states, and the couplings are set so that the total energy, or a loss function proportional to it, coincides with the Ising energy. The system is then released from an unstable or disordered initial state and relaxes into a low-energy configuration, which is read out. Since all spins interact simultaneously, the machine operates fully in parallel. The states found are in general good approximate solutions but not guaranteed to be the global minimum; as in simulated annealing, the result is improved by repeated runs. The idea of solving optimization problems by the relaxation of a physical system goes back to the Hopfield networks of John Hopfield and David Tank in the 1980s.
Implementations Quantum annealers In quantum annealing the Ising system is additionally subjected to a transverse field that induces quantum fluctuations; switching this field off slowly is intended to leave the system in the ground state of the classical Ising model. D-Wave Systems has built machines on this principle from superconducting flux qubits since 2011.
Coherent Ising machines In a coherent Ising machine (CIM) the spins are the two possible phases (0 or π) of degenerate optical parametric oscillators, which above threshold can oscillate only with one of these two phases. The concept was proposed in 2013 by Zhe Wang, Alireza Marandi, Yoshihisa Yamamoto and co-workers and demonstrated in 2014 with four time-multiplexed pulses in a fiber ring. In the time-multiplexed scheme all spins circulate as a pulse train through the same delay line; the coupling is implemented either optically or by measuring the pulses and feeding back electronically. Machines with 2000 and with 100 fully connected spins were reported in 2016, and a machine with 100,000 spins in 2021. A direct comparison with a quantum annealer showed the coherent Ising machine to be advantageous on densely connected problems, because it needs no embedding into a fixed coupling topology.
Oscillator-based and acoustic-wave machines The phase principle can be transferred to any self-sustained oscillator: when an oscillator is parametrically pumped at twice its natural frequency, its phase locks to one of two values differing by π, which serve as the spin states; networks of coupled oscillators then seek minima of the Ising energy. A machine presented in 2026 replaces the optical fiber ring by two serially connected quartz bulk-acoustic-wave delay lines at 20.5 MHz, in which 2048 spins circulate as time-multiplexed radio-frequency pulses; the coupling is implemented electronically with 15-bit resolution. The machine finds approximate solutions of number-partitioning problems and Sudoku puzzles at room temperature without optical or cryogenic components.
Digital emulation Some Ising machines emulate the dynamics of a physical system on conventional hardware, such as the simulated bifurcation algorithm developed at Toshiba, which integrates the equations of motion of coupled nonlinear oscillators on FPGAs or graphics processors.
Assessment Ising machines are analog computers for a single class of problems. Their advantage over general-purpose computers lies in massive parallelism and, for physical implementations, in the low energy cost per iteration; their drawbacks are the limited precision of the couplings and the fact that, while approximate solutions are found reliably, exact optima are found less and less often as the problem size grows. Whether, and for which problem classes, a fundamental advantage over the best classical heuristics exists remains an open research question.
See also Optical computing Quantum annealing Hopfield network
References