Ising machines as hardware solvers of combinatorial optimization problems

Abstract

Ising machines are hardware solvers that aim to find the absolute or approximate ground states of the Ising model. The Ising model is of fundamental computational interest because any problem in the complexity class NP can be formulated as an Ising problem with only polynomial overhead, and thus a scalable Ising machine that outperforms existing standard digital computers could have a huge impact for practical applications. We survey the status of various approaches to constructing Ising machines and explain their underlying operational principles. The types of Ising machines considered here include classical thermal annealers based on technologies such as spintronics, optics, memristors and digital hardware accelerators; dynamical systems solvers implemented with optics and electronics; and superconducting-circuit quantum annealers. We compare and contrast their performance using standard metrics such as the ground-state success probability and time-to-solution, give their scaling relations with problem size, and discuss their strengths and weaknesses. Minimizing the energy of the Ising model is a prototypical combinatorial optimization problem, ubiquitous in our increasingly automated world. This Review surveys Ising machines — special-purpose hardware solvers for this problem — and examines the various operating principles and compares their performance. Dedicated hardware solvers for the Ising model are of great interest, owing to their many potential practical applications and the end of Moore’s law, which motivate alternative computational approaches. Three main computing methods that Ising machines use are classical annealing, quantum annealing and dynamical system evolution. A single machine can operate on the basis of multiple computing approaches. Today, Ising hardware based on classical digital technologies is the best performing for common benchmark problems. However, the performance is problem-dependent, and alternative methods can perform well for particular classes of problems. For particular crafted problem instances, quantum approaches have been observed to have superior performance over classical algorithms, motivating quantum hardware approaches and quantum-inspired classical algorithms. Hybrid quantum–classical and digital–analogue algorithms are promising for future development; they may harness the complementary advantages of both. Dedicated hardware solvers for the Ising model are of great interest, owing to their many potential practical applications and the end of Moore’s law, which motivate alternative computational approaches. Three main computing methods that Ising machines use are classical annealing, quantum annealing and dynamical system evolution. A single machine can operate on the basis of multiple computing approaches. Today, Ising hardware based on classical digital technologies is the best performing for common benchmark problems. However, the performance is problem-dependent, and alternative methods can perform well for particular classes of problems. For particular crafted problem instances, quantum approaches have been observed to have superior performance over classical algorithms, motivating quantum hardware approaches and quantum-inspired classical algorithms. Hybrid quantum–classical and digital–analogue algorithms are promising for future development; they may harness the complementary advantages of both.