Supercomputing India (SCI)
GPU-Based Digital Annealing for Accelerating Large-Scale Combinatorial Optimization
Nistala Krishna Vamsi, Ashutosh Kumar Singh, A K Prabhakar
Abstract
We present a GPU-based digital annealer (DA) implementation to efficiently solve large-scale combinatorial optimization problems mapped onto Ising spin models. Our implementation employs Metropolis-Hastings dynamics with simulated annealing on NVIDIA A-100 GPUs, achieving up to 40-fold speedup over sequential CPU implementations for 32,000 -spin problems and scaling to 65,025 spins. Comprehensive benchmarking on the standard maxcut “Gset” dataset reveals that our DA consistently outperforms the commercial Gurobi optimiser across most of density-topology classes, achieving superior solution quality (lower optimality gaps), computational efficiency ($2.4 \times$ to $40.8 \times$ speedup), and high success rates ($83.3 \%$ average, with perfect performance on sparse Erdős-Rényi and moderatedensity skewed graphs). For cryptographic bent function discovery, our DA successfully identifies solutions up to 12 variables within minutes, significantly outperforming D-Wave’s quantum annealer, which fails to report results beyond 4 variables due to hardware connectivity constraints.