Ising machines as hardware solvers of combinatorial optimization problems

• Hybrid quantum-classical and digital-analog algorithms may harness complementary advantages, making them promising for future development.Source: Key points · p. 1

Motivation

• Conventional computers struggle with hard combinatorial optimization, where finding an optimum among many configurations matters across applications including planning, logistics, finance, and drug design.Examples include the travelling salesman problem, SAT, and MaxCut; many such problems are NP-complete, and any NP problem can be mapped to an NP-complete problem in polynomial time [5,6].Source: Introduction · pp. 1–2

Ising formulation

• MaxCut illustrates the Ising encoding: assigning binary spins to graph vertices makes minimizing the Ising energy equivalent to maximizing cut edges, and the formulation is equivalent to QUBO.MaxCut also has applications in circuit design [7,8], machine learning [9], and computer vision [10,11].Source: Introduction · p. 2

Analog computing

• Interest in analog Ising solvers has revived as researchers explore alternatives to conventional high-performance computing and its Monte Carlo methods, particularly amid the demise of Moore’s law.Analog systems can evolve coupled components in parallel without digital-logic overhead, but analog information storage makes them more susceptible to error.Source: Introduction · pp. 2–3

Quantum simulation

• Quantum simulation helped motivate physical Ising simulators, and D-Wave produced the first large-scale quantum approach described here, a 128-qubit annealer followed by larger systems.The introduction notes that large-scale fault-tolerant quantum computers remain technologically challenging, while cold atoms, ions, and artificial qubits offer routes to quantum simulation [15,16,18–22].Source: Introduction · p. 3

Review scope

• The review covers classical thermal annealers, quantum annealers, and dynamical-system solvers such as coherent Ising machines, emphasizing their principles, technologies, and scaling with problem size.It treats suboptimal but practically useful solutions as acceptable and therefore focuses primarily on heuristic and approximate solvers.Source: Introduction · p. 3

Classical thermal annealing

• At thermal equilibrium, configurations follow Boltzmann statistics; lowering temperature increases the probability of obtaining the ground state among the 2^N Ising configurations.The configurations with the lowest energy have the highest probability.Source: Classical thermal annealing · p. 3
• Because local minima can make equilibration extremely slow, gradual cooling allows the system to equilibrate; inverse-logarithmic cooling guarantees the ground state [28].The guarantee is attributed to Geman and Geman.Source: Classical thermal annealing · pp. 3–4
• On digital computers, simulated annealing uses Monte Carlo sampling with Metropolis-Hastings rather than directly evolving the master equation, which requires exponential resources.The sampling approach seeks the desired Boltzmann distribution.Source: Classical thermal annealing · p. 4
• Parallel tempering, population annealing, and isoenergetic cluster moves can improve on simulated annealing; the first two use multiple copies while cooling and selecting or adjusting them.Parallel tempering changes temperatures for poorly or successfully performing copies, while population annealing removes poor copies and replicates successful ones.Source: Classical thermal annealing · p. 4
• Thermally fluctuating magnetic tunnel junctions act as probabilistic bits, with measured orientations and adjusted barriers realizing Ising couplings; they were used for adiabatic integer factoring [29, 44–46].Memristors instead perform analog matrix multiplication to evaluate energy, using intrinsic noise for highly parallel annealing [30].Source: Classical thermal annealing · p. 4
• Optical annealers encode spins in light phase and use recurrent feedback for Ising couplings, converging toward the Boltzmann distribution with fast parallel spin updates [34, 52, 53].Source: Classical thermal annealing · p. 4
• Digital CMOS machines include a 2×104-spin design with up to 5 local interactions and an 8192-spin fully connected design with parallel updates.Random thermal effects are introduced in the former; the latter's parallelism speeds updates relative to serial simulated annealing. CMOS ASICs and FPGAs have also been investigated as domain-specific hardware.Source: Classical thermal annealing · pp. 4–5
• An FPGA restricted Boltzmann-machine sampler maps Ising problems to a bipartite model and parallel-updates each spin group, enabling parallel sampling that substantially improves over simulated annealing.Boltzmann-machine hardware accelerators using CMOS ASICs, FPGAs, and GPUs may also be adapted as Ising solvers.Source: Classical thermal annealing · p. 5

Oscillator-based computing

• Oscillator networks encode spins in oscillator phases and use coupling to converge to phase configurations from which spins can be read out.In the Kuramoto model, particular interaction strengths produce a transition from unsynchronized to synchronized oscillators.Source: Oscillator-based computing · p. 5
• Coupled LC circuits solved graph coloring for k = 2 but succeeded only on a subset of k = 3 instances; experiments also demonstrated oscillator networks for coloring, independent set, and Ising problems.Several studies found that adding noise and smoothly turning on interactions enabled low-energy Ising solutions.Source: Oscillator-based computing · p. 5
• CIMs encode spins in optical phases, and increasing DOPO gain can make the lowest-loss, minimum-energy configuration oscillate first for readout.However, even without noise, CIMs do not solve arbitrary Ising problems exactly in polynomial time; unequal oscillator amplitudes can also cause a broken mapping, for which feedback has been studied as a remedy.Source: Oscillator-based computing · p. 6
• At sufficiently low photon loss, CIM dynamics require a quantum model, but whether DOPO-network quantumness improves or impairs computational performance remains open.The quantum-regime interpretation represents spin configurations in superposition below threshold, while Goto’s related model acts as an adiabatic quantum computer when the pump rate increases sufficiently slowly.Source: Oscillator-based computing · p. 6

Chaos in dynamical-system solvers

• A limit-cycle-free k-SAT dynamical system designed to avoid local minima uses auxiliary variables that grow exponentially in time, implying exponentially growing analog energy or exponentially small digital timesteps.A prototype CMOS implementation capped auxiliary-variable signals at 1 V for problems of up to 50 variables.Source: Chaos in dynamical-system solvers · p. 7
• Numerical studies found transient chaos on difficult k-SAT instances but not easy ones; the auxiliary-variable approach was later adapted to Ising solving and implemented and benchmarked on an FPGA.A discrete-map optimization algorithm for k-SAT and Ising problems was also found to exhibit chaotic dynamics.Source: Chaos in dynamical-system solvers · p. 7

Quantum annealing

• Quantum annealing starts from a known ground state and gradually reduces quantum fluctuations to reach low-energy configurations of the problem Hamiltonian.Sufficiently slow sweeps can track the instantaneous ground state, with the time required for adiabaticity scaling as a negative power of the minimum energy gap.Source: Quantum annealing · p. 7
• For instances with tunneling barriers, quantum annealing and quantum-inspired classical algorithms that mimic tunneling have shown an advantage over simulated annealing, though tunneling’s role in speedup remains unclear.The D-Wave machine is the only quantum hardware described as having directly tested quantum annealing with a large number of qubits; it faces decoherence, control-error, and connectivity limitations.Source: Quantum annealing · p. 7

Hybrid Quantum-Classical Algorithms

• QAOA alternates problem- and mixer-Hamiltonian unitaries in a parameterized circuit, then uses a classical optimizer to minimize the energy expectation.Circuit depth p controls the 2p variational parameters, and computational power increases with p; however, practical benchmarking requires intermediate depths, where decoherence and gate errors are concerns.Source: Hybrid Quantum-Classical Algorithms · p. 8
• QAOA has been demonstrated only at small scale, with no experimental demonstrations for N > 50; classical p = 1 simulations have reached N = 105 spins.Demonstrations have used superconducting qubits, photonics, and trapped ions; large-scale quantum hardware is expected to be needed to evaluate QAOA’s general performance.Source: Hybrid Quantum-Classical Algorithms · p. 8

Other quantum algorithms

• Other proposed quantum approaches include amplitude-amplification methods and quantum simulated annealing, which prepares a coherent Gibbs state and gradually lowers its temperature to seek low-energy states.Quantum simulated annealing uses repeated quantum walks to obtain the coherent Gibbs state.Source: Other quantum algorithms · p. 8

Quantum-inspired classical algorithms

• Simulated quantum annealing (SQA) uses quantum Monte Carlo to estimate low-energy states and can faithfully predict quantum-annealing performance for stoquastic Hamiltonians.It maps the stoquastic Hamiltonian to a classical one with an extra imaginary-time dimension; at sufficiently low temperatures, SQA can mimic tunneling and generate entangled ground states during adiabatic evolution.Source: Quantum-inspired classical algorithms · pp. 8–9
• Simulated coherent Ising machines have shown speedups over physical CIM implementations using FPGAs and GPUs, because their coupled-equation simulations scale with N rather than 2^N.The simulations model coupled oscillator variables, making them efficient in comparison with searching the configurational space.Source: Quantum-inspired classical algorithms · p. 9
• Simulated bifurcation (SB) uses adiabatic, ergodic search in classical nonlinear Hamiltonian systems, and its ballistic and discrete variants far outperform original SB in speed and solution accuracy.Toshiba developed an FPGA- and GPU-based SB machine; later, a multi-chip FPGA architecture using partitioned SB handled large-scale Ising problems. SB and CIM simulations support parallel updates of N coupled-oscillator variables, unlike canonical sequential updates in simulated annealing.Source: Quantum-inspired classical algorithms · p. 9
• Tensor networks have been used as ansätze for optimization problems, including dynamic portfolio optimization encoded as an Ising problem.Tensor networks represent complex quantum states based on their entanglement structure.Source: Quantum-inspired classical algorithms · p. 9

Machine learning approaches

• Machine-learning methods can boost classical solvers and quantum algorithms or serve as stand-alone solvers, with investigated approaches including reinforcement learning, graph neural networks, and neural attention.Applications include accelerating Monte Carlo simulations and portfolio optimization; more sample-efficient methods are described as enabling greater scalability to large-scale problems.Source: Machine learning approaches · p. 9

• Assuming P≠NP, exact ground states for all Ising instances are unlikely to admit polynomial-time algorithms, though this remains unproved for quantum or probabilistic computers.The section notes the conjectures P ⊆ BQP and P = BPP, and that quantum integer factorization helped spur interest in quantum computing.Source: Computational complexity · p. 9
• Exact algorithms guarantee optimality, approximation algorithms bound solution quality, and heuristics offer no quality guarantee but are trusted through empirical benchmarks.Approximation and heuristic algorithms both tend to be practical on large problems.Source: Computational complexity · pp. 9–10
• For MaxCut, Goemans–Williamson guarantees solutions within ≈12% of optimal, while approximating closer than ≈6% is NP-hard.Because MaxCut and thus the Ising model are APX-hard, assuming P≠NP no polynomial-time approximation can guarantee solutions arbitrarily close to exact; practical demand for better quality motivates heuristics.Source: Computational complexity · p. 10
• Most Ising machines are heuristic solvers without approximation-ratio guarantees, and near-optimal solutions are generally expected to require exponential runtime.Their potential advantage is a smaller exponential-scaling exponent or constant prefactor than conventional heuristic solvers; fast hardware clocks may also yield practical speedups.Source: Computational complexity · p. 10

Computation performance comparisons

• The comparison focuses on experimentally tested systems with N ≥50 and uses ground-state success probability per run plus time-to-solution, combining per-run success probability and run time for 99% collective success.Success probability depends on algorithmic parameters and practical constraints; the comparison generally reports the best value available in the literature.Source: Computation performance comparisons · p. 10
• For dense SK and MaxCut success probabilities, digital-hardware RBM shows the best scaling with N, while the benchmarked D-Wave annealer performs particularly poorly.RBM's high success probability is attributed to parallel simulated-annealing updates; D-Wave's Chimera connectivity requires an embedding using ∝N^2 physical qubits, yielding a relation resembling p_suc ∝ e^−bN^2.Source: Computation performance comparisons · p. 11, Figure 3 · p. 11
• For SK, RBM and TBM on classical digital hardware have the lowest time-to-solution; for dense MaxCut, RBM is lowest among physically implemented machines.MRT, PRIS, and CIM3 curves include theoretical time-to-solution predictions rather than direct measurements.Source: Computation performance comparisons · p. 11, Figure 4 · p. 12
• D-Wave's dense-problem time-to-solution is approximated by T_sol ∝ e^cN and requires ∝N^2 physical qubits, while sparse-connectivity instances showed more favorable scaling.The dense-problem scaling difference is attributed to a hardware implementation limitation, not the computational mechanism, and may improve in the future.Source: Computation performance comparisons · pp. 11–12
• For 3R3X problems, SATonGPU performs best, while Fujitsu's Digital Annealer and Toshiba's bifurcation machine have almost similar scaling but larger prefactors.The memcomputing results come from classical simulation of a proposed system; dedicated hardware might improve performance.Source: Computation performance comparisons · p. 12, Figure 4 · p. 12
• For logical-planted problems designed to promote tunneling barriers, D-Wave and SQA show a time-to-solution scaling advantage over SA.SQA's superior performance indicates that tunneling through barriers is not necessarily exclusive to quantum hardware; SQA cannot be applied to non-stoquastic Hamiltonians with a sign problem.Source: Computation performance comparisons · p. 12, Figure 4 · p. 12

Discussion and Outlook

• Classical annealing, quantum annealing, and dynamical-system evolution are the three strategies; annealers use noise to escape local minima, while dynamical systems evolve far from equilibrium toward low-energy configurations.All three are in principle compatible with natural computing, encoding information in analog, parallel form so that the underlying physics drives the system toward a ground state.Source: Discussion and Outlook · p. 13
• Despite different technologies, approaches tend to show similar error-probability and time-to-solution scaling with spin count, and their complexity scales exponentially with system size.The competition is over achievable exponents and prefactors; even a small exponent difference can greatly affect time-to-solution at large sizes, as expected for the NP-complete Ising problem.Source: Discussion and Outlook · pp. 13–14
• At the time of writing, classical digital methods performed best, but problem structure can change machine performance and may favor choosing or combining methods by suitability.For example, small spectral gaps that challenge quantum annealing may not limit QAOA162, and hybrid quantum-classical or digital-analog algorithms could combine complementary advantages210.Source: Discussion and Outlook · p. 14
• Coherent Ising machines have quantum-mechanical models, but experimental high-photon-loss regimes are accurately described classically, and mean-field simulations can achieve similar demonstrated performance.CIMs can enter the quantum regime with sufficiently high OPO nonlinearity relative to loss, while making quantum effects crucial and performance-enhancing experimentally remains an active research topic114,117,35,115,116,121,125,119,178,179,211,212,120.Source: Discussion and Outlook · p. 14
• Quantum annealing has shown advantages over certain classical methods for some problem classes, but no unqualified real-world quantum speedup has been established.For deceptive cluster loops, D-Wave outperformed tested classical heuristics in time-to-solution, but the speedup was approximately constant-factor with no strong scaling advantage203; QA also does not sample all low-lying states uniformly, and entanglement’s role remains unclear. These uncertainties have motivated quantum-inspired classical algorithms144,154–157,203,42,213,214,41,216,217,218.Source: Discussion and Outlook · p. 14
• More precise scaling measurements across problem classes and accuracy levels are needed, while large-scale quantum machines with high connectivity and low decoherence remain an outstanding challenge.The review describes existing scaling comparisons as preliminary; classical digital approaches often support full connectivity, and continued Ising-machine development is expected amid collaboration across hardware engineering, computer science, statistical physics, and quantum mechanics.Source: Discussion and Outlook · p. 14

Author’s note

• This preprint does not include changes made during the journal’s editing and production process.It is scheduled to appear in Nature Reviews Physics.Source: Author’s note · p. 23