Dynamics-based Ising machines (IMs) are a promising substrate for high-speed combinatorial optimization and sampling. For problems that fit within their fixed capacity, they provide orders-of-magnitude speedups over conventional software algorithms. Once a problem exceeds hardware capacity, somewhat surprisingly, they become practically useless: Previous works generally relegate them to isolated sub-solvers. As our analysis will show, this approach produces no clear time or energy benefits, losing any inherent advantage of hardware IMs.After analyzing the shortcomings of previous hybrid proposals, we introduce a better method to extend IM advantage beyond hardware capacity. We call it the Stepped Large-neighborhood Annealing Method (SLAM), which drastically improves performance on combinatorial benchmarks with minimal host-side computation.We also propose novel architectural support to implement SLAM with low data movement overheads. The resulting augmented IM continues to exploit dynamical systems-enabled parallelism and thus maintains order of magnitude time-to-solution and energy-to-solution advantages over CPU-based algorithms. As a side benefit, our approach also significantly reduces the impact of device variation on solution quality, another perennial issue for analog optimizers.

Analog dynamical accelerators (DXs) are a growing sub-field in computer architecture research, offering order-of-magnitude gains in power efficiency and latency over traditional digital methods in several machine learning, optimization, and sampling tasks. However, limited-capacity accelerators require hybrid analog/digital algorithms to solve real-world problems, commonly using large-neighborhood local search (LNLS) frameworks. Unlike fully digital algorithms, hybrid LNLS has no non-asymptotic convergence guarantees and no principled hyperparameter selection schemes, particularly limiting cross-device training and inference. In this work, we provide non-asymptotic convergence guarantees for hybrid LNLS by reducing to block Langevin Diffusion (BLD) algorithms. Adapting tools from classical sampling theory, we prove exponential KL-divergence convergence for randomized and cyclic block selection strategies using ideal DXs. With finite device variation, we provide explicit bounds on the 2-Wasserstein bias in terms of step duration, noise strength, and function parameters. Our BLD model provides a key link between established theory and novel computing platforms, and our theoretical results provide a closed-form expression linking device variation, algorithm hyperparameters, and performance.

Ising machines have attracted significant attention for solving quadratic unconstrained binary optimization (QUBO) with high performance. Among them, CMOS-compatible dynamics-based designs are promising approaches with high efficiency, scalability, and potential extension to more general combinatorial optimization problems (COPs) beyond QUBO problems. However, these machines can be limited by poor solution quality due to variations and leakage, or by long solution times resulting from inefficient annealing. In this paper, we propose a novel all-to-all connected Ising machine based on charge redistribution, capable of solving generic QUBO problems. To enhance solution quality, we apply a stochastic cycling annealing technique. A 50-spin Ising machine was developed using commercial 65nm CMOS technology, with both system-level and circuit-level designs implemented. Additionally, behavior-level simulations were conducted to evaluate the performance of a larger system. Simulation results show that the proposed Ising machine delivers competitive solution quality with reduced time-to-solution, making it a strong candidate for solving COPs.

A prominent approach to solving combinatorial optimization problems on parallel hardware is Ising machines, i.e., hardware implementations of networks of interacting binary spin variables. Most Ising machines leverage second-order interactions although important classes of optimization problems, such as satisfiability problems, map more seamlessly to Ising networks with higher-order interactions. Here, we demonstrate that higher-order Ising machines can solve satisfiability problems more resource-efficiently in terms of the number of spin variables and their connections when compared to traditional second-order Ising machines. Further, our results show on a benchmark dataset of Boolean \textit{k}-satisfiability problems that higher-order Ising machines implemented with coupled oscillators rapidly find solutions that are better than second-order Ising machines, thus, improving the current state-of-the-art for Ising machines.