Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling

Introduction Sampling-based Solvers (e.g., Simulated Annealing) Combinatorial optimization (CO) is interpreted as sampling from the corresponding distribution. Limitation: Local and sequential updates limit scalability and parallelism. Learning-based Solvers The methods learn heuristics without the need for manual design and leveraging GPUs. Supervised Learning (SL): Models are trained using labeled optimal solutions. Limitation Requires access high-quality labeled data (optimal solutions). Reinforcement Learning (RL): Learns policies by optimizing reward signals in CO tasks. Limitation: Often suffers from training instability and difficulties in exploration. Unsupervised Learning (UL): Optimizes model parameters to directly minimize CO objectives. Issue: Sensitive to model architecture and computationally expensive to train. Recent Advances: Revisiting Sampling-based Solvers (iSCO [2]) iSCO integrates discrete Langevin dynamics with simulated annealing. iSCO achieves performance comparable to learning-based methods without training. Enables efficient GPU-parallel updates, overcoming the limitation of sampling-based methods. Parallel Quasi-Quantum Annealing (PQQA): A Further Advancement in Sampling-based Solvers PQQA combines gradient-based transitions, quasi-quantum annealing, and parallel exploration facilitated by inter-process communication. PQQA outperforms both learning-based solvers and iSCO, with performance improvements becoming increasingly significant as problem size grows.