Enhanced Convergence in p-bit Based Simulated Annealing with Partial Deactivation for Large-Scale Combinatorial Optimization Problems

Abstract

This article critically investigates the limitations of the simulated annealing algorithm using probabilistic bits (pSA) in solving large-scale combinatorial optimization problems. The study begins with an in-depth analysis of the pSA process, focusing on the issues resulting from unexpected oscillations among p-bits. These oscillations hinder the energy reduction of the Ising model and thus obstruct the successful execution of pSA in complex tasks. Through detailed simulations, we unravel the root cause of this energy stagnation, identifying the feedback mechanism inherent to the pSA operation as the primary contributor to these disruptive oscillations. To address this challenge, we propose two novel algorithms, time average pSA (TApSA) and stalled pSA (SpSA). These algorithms are designed based on partial deactivation of p-bits and are thoroughly tested using Python simulations on maximum cut benchmarks that are typical combinatorial optimization problems. On the 16 benchmarks from 800 to 5,000 nodes, the proposed methods improve the normalized cut value from 0.8% to 98.4% on average in comparison with the conventional pSA.

17 pages

References in corpus (18)

• Quantum Annealing in the Transverse Ising Model
• Parallel Tempering: Theory, Applications, and New Perspectives
• Quantum annealing with more than one hundred qubits
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• A Coherent Ising Machine Based On Degenerate Optical Parametric Oscillators
• VLSI Implementation of Deep Neural Network Using Integral Stochastic Computing
• p-Bits for Probabilistic Spin Logic
• Massively Parallel Probabilistic Computing with Sparse Ising Machines
• Hardware emulation of stochastic p-bits for invertible logic
• Hardware-aware $insitu$ Boltzmann machine learning using stochastic magnetic tunnel junctions
• Annealing by simulating the coherent Ising machine
• Weighted p-bits for FPGA implementation of probabilistic circuits
• Efficient CMOS Invertible Logic Using Stochastic Computing
• Autonomous Probabilistic Coprocessing with Petaflips per Second
• Experimental quantum annealing: case study involving the graph isomorphism problem
• Spintronics-compatible approach to solving maximum satisfiability problems with probabilistic computing, invertible logic and parallel tempering
• Memory-Efficient FPGA Implementation of Stochastic Simulated Annealing
• Physics-inspired Ising Computing with Ring Oscillator Activated p-bits

Cited by in corpus (4)

• GPU-accelerated simulated annealing based on p-bits with real-world device-variability modeling
• pc-COP: An Efficient and Configurable 2048-p-Bit Fully-Connected Probabilistic Computing Accelerator for Combinatorial Optimization
• Metrics for spin-based computing
• Energy-Efficient p-Bit-Based Fully-Connected Quantum-Inspired Simulated Annealer with Dual BRAM Architecture