Source-linked AI summary
Ising machines as hardware solvers of combinatorial optimization problems
Naeimeh Mohseni, Peter L. McMahon, Tim Byrnes
TL;DR
Hard combinatorial optimization problems challenge conventional computers and matter across many applications. This review surveys Ising-machine architectures and compares their performance, finding that diverse approaches generally show similar scaling in error probability and time to solution.
Problem
Hard combinatorial optimization problems require selecting optimal configurations from very large candidate spaces and include many practically relevant NP-complete problems.
Method
The review surveys classical annealing, quantum annealing, and dynamical-system Ising machines, comparing operating principles and performance metrics including success probability and time to solution.
Results
Most Ising-machine approaches exhibit similar scaling of error probability and time to solution with the number of spins.
Takeaways & Limitations
The review identifies three dominant Ising-machine strategies that are in principle compatible with analog, parallel natural computing.
Takeaways & Limitations
The extent to which quantumness in coherent Ising-machine oscillator networks improves their operation remains an open question.
Abstract
from arXiv · showhide
Ising machines are hardware solvers which aim to find the absolute or approximate ground states of the Ising model. The Ising model is of fundamental computational interest because it is possible to formulate any problem in the complexity class NP as an Ising problem with only polynomial overhead. A scalable Ising machine that outperforms existing standard digital computers could have a huge impact for practical applications for a wide variety of optimization problems. In this review, we survey the current 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.
Key points
Hybrid quantum-classical and digital-analog algorithms are promising directions for future development because they may combine complementary advantages.
- Hybrid quantum-classical and digital-analog algorithms are promising for future development and may harness complementary advantages.
Introduction
Hard combinatorial optimization problems challenge conventional computers across many applications, motivating alternative hardware approaches. This review examines Ising machines as primarily heuristic and approximate solvers, emphasizing their operating principles and technologies.
- Motivation: Combinatorial optimization seeks an optimal configuration among a very large number of candidates and appears in planning, logistics, finance, machine learning, and other applications.Examples include travelling salesman, Boolean satisfiability, bioinformatics, drug design, and materials problems.
- Complexity: Many combinatorial optimization problems are NP-complete, while any problem in NP can be mapped to an NP-complete problem.
- Ising formulation: MaxCut illustrates the connection: minimizing the Ising Hamiltonian is equivalent to maximizing the number of edges between two vertex groups.MaxCut is relevant to circuit design, machine learning, and computer vision; the Ising formulation is equivalent to QUBO under σ_i = 1 − 2x_i.
- Alternative computing: Large-scale classical computers commonly solve these problems with Monte Carlo variants, but the demise of Moore’s law motivates unconventional computing methods.
- Review scope: The review surveys hardware devices called Ising machines, focusing on their operating principles and primarily considering heuristic and approximate solutions when suboptimal results are acceptable.
Operating Principles of Ising Machines · Classical thermal annealing
Classical thermal annealing searches for low-energy Ising configurations by gradually lowering effective temperature, increasing ground-state probability as the system approaches equilibrium. Its implementations range from simulated annealing on digital computers to dedicated digital and analog hardware that exploit parallelism and physical stochasticity.
- Classical thermal annealing: Annealing lowers effective temperature so configurations with the lowest cost-function values become more likely.The principle is motivated by statistical mechanics and Boltzmann or Gibbs statistics.
- Classical thermal annealing: 2^N energy configurations exist, and lowering temperature increases the probability of obtaining the ground state.The configurations are labeled by spin assignments n = {σ1,...,σN}.
- Classical thermal annealing: Local minima can trap the dynamics, making thermal equilibrium require extremely long times on particular energy landscapes.Sufficiently long evolution at sufficiently low temperature guarantees low-energy solutions under the stated dynamics.
- Classical thermal annealing: Inverse-logarithmic temperature reduction with time guarantees obtaining the ground state.This schedule gradually lowers temperature while allowing equilibration at each temperature.
- Classical thermal annealing: Simulated annealing uses Monte Carlo methods, typically Metropolis-Hastings, because directly evolving the dynamics requires exponential resources on digital computers.The algorithm targets the desired Boltzmann distribution.
- Classical thermal annealing: Dedicated digital accelerators and analog physical implementations can exploit hardware parallelization and analog computing for Ising-model optimization.Simulated annealing is commonly implemented on conventional programmable digital computers but also on specialized hardware.
- Classical thermal annealing: 2×10^4 Ising spins were implemented in CMOS with each spin interacting with up to 5 local spins.Randomness came from random spin flips or low supply voltage applied to memory cells.
- Classical thermal annealing: 8192-spin full-connectivity CMOS annealing performs spin updates in parallel, providing a large speedup over serial simulated annealing.CMOS ASICs and FPGAs have both been investigated as domain-specific Ising-model computing platforms.
Dynamical system solvers
Dynamical-system Ising solvers encode spins in oscillator phases and converge toward configurations from which spin assignments can be read. Implementations include coupled oscillators, optical coherent Ising machines, and chaotic dynamics proposed to address trapping in local minima.
- Oscillator-based solvers: Oscillator phase encodes each Ising spin, with nonlinear phase locking producing two stable phases, 0 and π, that represent binary information.This principle underlies parametron-style analog computers and oscillator-based dynamical solvers.
- Oscillator-based solvers: The coupled-phase dynamics converge to a configuration of in-phase or out-of-phase oscillators, enabling direct spin readout.For constant Jij and hi = 0, the Kuramoto model exhibits a dynamical phase transition from unsynchronized to synchronized oscillators at particular interaction strengths.
- Oscillator-based solvers: For k = 2, coupled LC circuits correctly found graph-coloring solutions, whereas for k = 3 they succeeded only on a subset of problem instances.The graph-coloring formulation is NP-complete for k ≥3.
- Coherent Ising machines: Coherent Ising machines encode spins in optical-mode phases and use degenerate optical parametric oscillators to enforce the binary values φi = 0,π.Their equations include oscillator amplitudes, gain, loss, nonlinear saturation, Ising coupling, and Langevin noise.
- Chaotic dynamics: Because thermal relaxation is strongly nonergodic, proposed dynamical modifications include chaos; simulations observed transient chaos on difficult k-SAT instances but not easy ones.A discrete-map optimization algorithm also exhibited chaotic dynamics on both k-SAT and Ising problems.
Quantum approaches
Quantum approaches seek low-energy or ground states of optimization Hamiltonians through adiabatic evolution, variational circuits, and other quantum algorithms. Quantum annealing relies on slowly reducing quantum fluctuations, while QAOA combines alternating Hamiltonian evolutions with classical parameter optimization but remains experimentally demonstrated only at small scale.
- Quantum annealing: Quantum annealing gradually reweights an initial Hamiltonian with a known ground state toward the problem Hamiltonian, reducing quantum fluctuations during the evolution.If the sweep is sufficiently slow, the quantum adiabatic theorem implies that the system remains in its instantaneous ground state.
- Variational quantum algorithms: Variational quantum algorithms combine parametrized quantum circuits with classical optimizers to seek the lowest-energy state of a Hamiltonian.The circuit prepares a variational state, while the classical optimizer determines parameters that minimize the energy expectation.
- QAOA: QAOA is a Trotterized version of quantum annealing that alternates problem- and initial-Hamiltonian unitaries along a parametrized annealing pathway.Its circuit depth is set by p, with 2p variational parameters optimized classically.
- QAOA: No large-scale QAOA demonstrations with N > 50 have been experimentally performed, although single-layer p = 1 classical simulations have reached N = 105 spins.Small-scale demonstrations span superconducting qubits, photonics, and trapped ions.
- Other quantum algorithms: Other proposed quantum optimization methods include amplitude amplification and quantum simulated annealing aimed at preparing quantum Gibbs states.Quantum simulated annealing uses quantum walks to prepare a superposition whose amplitudes follow Boltzmann probabilities.
Other classical algorithms
Other classical algorithms include quantum-inspired methods implemented on conventional computers or digital accelerators, using quantum concepts without quantum hardware. These approaches include simulated quantum annealing, dynamical-system simulations, simulated bifurcation, tensor networks, and machine-learning solvers.
- Quantum-inspired algorithms: Quantum-inspired algorithms run on conventional computing hardware or digital accelerators while using concepts originating from quantum mechanics.They therefore remain classical approaches despite their quantum-inspired design.
- Simulated quantum annealing: SQA uses quantum Monte Carlo and imaginary-time mapping to estimate low-energy states of stoquastic quantum-annealing Hamiltonians.The mapping introduces an extra spatial dimension, corresponding to imaginary time, and requires nonpositive off-diagonal elements in the computational basis.
- Simulated quantum annealing: At sufficiently low temperatures, SQA can mimic tunneling, generate entangled ground states, and faithfully predict QA performance for stoquastic Hamiltonians.Continuous-time quantum Monte Carlo samples equilibrium thermal states and can generate Boltzmann-distributed states.
- Dynamical-system algorithms: Simulated coherent Ising machines and simulated bifurcation use classical dynamical-system evolution, with the former scaling with spin-variable count and the latter benefiting from FPGA and GPU parallelizability.Simulated bifurcation models adiabatic evolution of classical nonlinear Hamiltonian systems, with two oscillator branches representing each Ising spin state.
- Other approaches: Tensor networks represent complex quantum states through entanglement structure and have been used as optimization ansätze, including for dynamic portfolio optimization encoded as an Ising problem.Machine-learning methods can also accelerate Monte Carlo simulations or act as stand-alone solvers, showing excellent portfolio-optimization performance and improved scalability with sample-efficient methods.
Computational complexity
Exact Ising optimization is widely conjectured to be harder than polynomial-time computation, while approximate and heuristic solutions remain practical alternatives. Most Ising machines therefore operate as heuristic solvers without approximation guarantees, with potential advantages arising from scaling or constant-prefactor improvements over conventional heuristics.
- Computational complexity: P ≠ NP is widely conjectured, implying that exact Ising ground-state problems are fundamentally harder than problems in P.The P ?= NP question remains open.
- Computational complexity: Approximate solutions with energy near the true ground state are often acceptable, while heuristic algorithms provide no quality guarantees but are practical on large problems.Approximation and heuristic algorithms tend to be practical to run on large problems.
- Computational complexity: Assuming P ≠ NP, APX-hardness rules out any polynomial-time approximation algorithm guaranteeing an Ising solution arbitrarily close to the exact solution.The MaxCut problem, and hence the Ising model, is APX-hard.
- Computational complexity: Most Ising machines are heuristic solvers without approximation-ratio guarantees, but may offer polynomially improved scaling or constant-prefactor advantages over conventional heuristic algorithms.These potential advantages largely lie outside complexity theory.
Computation performance comparisons
The comparison benchmarks experimentally tested Ising solvers on relatively large systems (N ≥50) using success probability and time-to-solution. Current results suggest that performance depends strongly on runtime optimization, hardware connectivity, problem class, and implementation.
- Performance metrics: Success probability measures the chance of obtaining the exact ground state in one run, whereas time-to-solution accounts for repeated runs and their durations.Machines may achieve higher single-run success by using longer annealing times, even when shorter runs optimize overall performance.
- Success probability: SA-based approaches, including digital-hardware RBMs, show the best success-probability scaling with N at current technological levels.This comparison carries an interpretational caveat because success probability can be increased at the expense of very long runtimes.
- Time-to-solution: For SK, RBM and TBM achieve the lowest time-to-solution, while RBM is the fastest physically implemented method for MaxCut.The MRT, PRIS, and CIM3 time-to-solution curves use theoretical predictions rather than direct measurements.
- Connectivity effects: D-Wave results are better approximated by Tsol ∝ e^(cN), requiring ∝N^2 physical qubits because of limited Chimera connectivity.This scaling reflects a hardware implementation limitation rather than the computational mechanism itself; sparse-connectivity D-Wave instances showed more favorable scaling.
- Problem-class dependence: For 3R3X problems, SATonGPU performs best, while the Fujitsu Digital annealer and Toshiba bifurcation machine have almost similar scaling with larger prefactors.SATonGPU is a highly parallelized SAT algorithm implemented on a GPU.
- Problem-class dependence: Logical-planted problems are constructed to promote tunneling barriers, for which quantum annealing is expected to traverse barriers more effectively than some classical methods.The comparison uses optimum time-to-solution for logical-planted instances.
Coherent Ising machine
Benchmarking shows that Ising-machine performance depends strongly on the problem class and solver dynamics. For the cited comparisons, D-Wave outperformed simulated annealing, while simulated quantum annealing performed better than current quantum-annealing hardware.
- Benchmarking results: D-Wave outperformed SA, but SQA performed better than current QA hardware, indicating that present hardware remains dominated by classical dynamics.The passage links this result to a need to improve current quantum-annealing hardware.
- Benchmarking results: Performance is problem dependent across Ising-machine benchmarks, with TBM showing the best performance for SK-model instances.The cited benchmark compared the D-Wave hybrid solver, TBM, FDA, and SA across three problem-instance classes, including SK.
Discussion and Outlook
The review identifies classical annealing, quantum annealing, and dynamical-system evolution as the three dominant Ising-machine strategies, all compatible in principle with analog, parallel natural computing. Their performance remains governed by exponential scaling, while classical digital methods currently perform best and no unqualified quantum speedup has been demonstrated for real-world problems.
- Operating principles: Three dominant strategies are classical annealing, quantum annealing, and dynamical system evolution, all compatible in principle with analog and parallel natural computing.Natural computing uses physics to drive the system toward a ground state.
- Operating principles: Annealing uses thermal or quantum noise to escape local minima, whereas dynamical systems evolve far from equilibrium toward particular configurations.The approaches differ in whether they aim to avoid high-energy states or attract the system to selected configurations.
- Scaling and performance: Exponential complexity is expected for all approaches; competing methods primarily differ in the exponent and prefactors, with small exponent differences producing large time-to-solution differences.This follows from the NP-complete complexity of the Ising problem.
- Scaling and performance: Classical digital methods were still the best-performing approaches at the time of writing, although rapidly developing analog and quantum technologies could change the landscape.Digital methods benefit from decades of development and, in many cases, high parallelization.
- Quantum advantage: No evidence of an unqualified quantum speedup has been found for any real-world problem of interest, despite advantages over certain classical methods for selected problem classes.The cited comparisons include simulated annealing and the Hamze–de Freitas–Selby algorithm.
- Outlook: More precise quantification of time-to-solution and other metrics is needed to compare competing Ising machines and determine their suitability across problem classes.The review characterizes Figs. 3 and 4 as extremely preliminary for this purpose.
Author’s note
This document is a preprint of a review paper scheduled for publication in Nature Reviews Physics and does not include subsequent journal editing and production changes.
- Author’s note: The preprint is scheduled to appear in Nature Reviews Physics but excludes changes made during journal editing and production.This version should not be treated as the final published paper.