Noise-augmented Chaotic Ising Machines for Combinatorial Optimization and Sampling
arXiv:2408.04744 · doi:10.1038/s42005-025-01945-1
Abstract
Ising machines, hardware accelerators for combinatorial optimization and probabilistic sampling problems, have gained significant interest recently. A key element is stochasticity, which enables a wide exploration of configurations, thereby helping avoid local minima. Here, we refine the previously proposed concept of coupled chaotic bits (c-bits) that operate without explicit stochasticity. We show that augmenting chaotic bits with stochasticity enhances performance in combinatorial optimization, achieving algorithmic scaling comparable to probabilistic bits (p-bits). We first demonstrate that c-bits follow the quantum Boltzmann law in a 1D transverse field Ising model. We then show that c-bits exhibit critical dynamics similar to stochastic p-bits in 2D Ising and 3D spin glass models, with promising potential to solve challenging optimization problems. Finally, we propose a noise-augmented version of coupled c-bits via the adaptive parallel tempering algorithm (APT). Our noise-augmented c-bit algorithm outperforms fully deterministic c-bits running versions of the simulated annealing algorithm. Other analog Ising machines with coupled oscillators could draw inspiration from the proposed algorithm. Running replicas at constant temperature eliminates the need for global modulation of coupling strengths. Mixing stochasticity with deterministic c-bits creates a powerful hybrid computing scheme that can bring benefits in scaled, asynchronous, and massively parallel hardware implementations.
References in corpus (29)
- Large-scale photonic Ising machine by spatial light modulation
- Universality of Phase Transition Dynamics: Topological Defects from Symmetry Breaking
- Quantum critical dynamics in a 5000-qubit programmable spin glass
- Massively Parallel Probabilistic Computing with Sparse Ising Machines
- Optimized simulated annealing for Ising spin glasses
- Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond
- Critical parameters of the three-dimensional Ising spin glass
- Probabilistic computing with p-bits
- Hardware emulation of stochastic p-bits for invertible logic
- CMOS + stochastic nanomagnets: heterogeneous computers for probabilistic inference and learning
- Weighted p-bits for FPGA implementation of probabilistic circuits
- Efficient CMOS Invertible Logic Using Stochastic Computing
- Autonomous Probabilistic Coprocessing with Petaflips per Second
- Dissipative quantum bifurcation machine: Quantum heating of coupled nonlinear oscillators
- 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
- Training Deep Boltzmann Networks with Sparse Ising Machines
- Scalable Emulation of Sign-ProblemFree Hamiltonians with Room Temperature p-bits
- Low-rank combinatorial optimization and statistical learning by spatial photonic Ising machine
- Accelerated Quantum Monte Carlo with Probabilistic Computers
- All-to-all reconfigurability with sparse and higher-order Ising machines
- Memristor-based hardware and algorithms for higher-order Hopfield optimization solver outperforming quadratic Ising machines
- Monte Carlo simulation of classical spin models with chaotic billiards
- On computational capabilities of Ising machines based on nonlinear oscillators,
- Memcomputing Numerical Inversion with Self-Organizing Logic Gates
- Emulating Quantum Interference with Generalized Ising Machines
- Markov Chain Monte Carlo for Koopman-based Optimal Control: Technical Report
- Machine Learning Quantum Systems with Magnetic p-bits
- Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization
- Combinatorial Reasoning: Selecting Reasons in Generative AI Pipelines via Combinatorial Optimization