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

arXiv: https://arxiv.org/abs/2409.02135 · HTML: https://mlsanity.com/paper/2409.02135/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 73 references that are in the map.
- First posted on arXiv 2 Sep 2024.

## Builds on (most cited first, 29 of 29)

- [Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning](https://mlsanity.com/paper/1602.07261/) (2016)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions](https://mlsanity.com/paper/2102.04509/) (2021)
- [Learning What to Defer for Maximum Independent Sets](https://mlsanity.com/paper/2006.09607/) (2020)
- [Graph Neural Networks for Maximum Constraint Satisfaction](https://mlsanity.com/paper/1909.08387/) (2019)
- [A Langevin-like Sampler for Discrete Distributions](https://mlsanity.com/paper/2206.09914/) (2022)
- [What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization](https://mlsanity.com/paper/2201.10494/) (2022)
- [Rethinking Graph Regularization for Graph Neural Networks](https://mlsanity.com/paper/2009.02027/) (2020)
- [Finding Near-Optimal Independent Sets at Scale](https://mlsanity.com/paper/1509.00764/) (2015)
- [Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set](https://mlsanity.com/paper/2206.13211/) (2022)
- [Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation](https://mlsanity.com/paper/2207.05984/) (2022)
- [Graph Coloring with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2202.01606/) (2022)
- [Discrete Langevin Sampler via Wasserstein Gradient Flow](https://mlsanity.com/paper/2206.14897/) (2022)
- [Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning](https://mlsanity.com/paper/2301.03116/) (2023)
- [GAP: Generalizable Approximate Graph Partitioning Framework](https://mlsanity.com/paper/1903.00614/) (2019)
- [Annealed Training for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2207.11542/) (2022)
- [Controlling Continuous Relaxation for Combinatorial Optimization](https://mlsanity.com/paper/2309.16965/) (2023)
- [Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs](https://mlsanity.com/paper/1904.02231/) (2019)
- [Reply to: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set](https://mlsanity.com/paper/2302.03602/) (2023)
- [Scalable Kernelization for Maximum Independent Sets](https://mlsanity.com/paper/1708.06151/) (2017)
- [Continuous Parallel Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems](https://mlsanity.com/paper/2402.02190/) (2024)

## Built on by (most cited first, 7 of 7)

- [Quantization Error Propagation: Revisiting Layer-Wise Post-Training Quantization](https://mlsanity.com/paper/2504.09629/) (2025)
- [More Than Bits: Multi-Envelope Double Binary Factorization for Extreme Quantization](https://mlsanity.com/paper/2512.24545/) (2025)
- [Neural QAOA2: Differentiable Joint Graph Partitioning and Parameter Initialization for Quantum Combinatorial Optimization](https://mlsanity.com/paper/2605.13072/) (2026)
- [Test-Time Adaptation for Unsupervised Combinatorial Optimization](https://mlsanity.com/paper/2601.21048/) (2026)
- [Signs Beat Floats: Low-Rank Double-Binary Adaptation for On-Device Fine-Tuning](https://mlsanity.com/paper/2605.24058/) (2026)
- [From Sweep to Seam: Interleaved Cross-Block Post-Training Quantization](https://mlsanity.com/paper/2608.09595/) (2026)
- [Optimization for One, Feasibility for Most: Decoupling Optimization from Feasibility in Chance-Constrained Programs](https://mlsanity.com/paper/2610.19027/) (2026)

## Abstract (arXiv)

Learning-based methods have gained attention as general-purpose solvers due to their ability to automatically learn problem-specific heuristics, reducing the need for manually crafted heuristics. However, these methods often face scalability challenges. To address these issues, the improved Sampling algorithm for Combinatorial Optimization (iSCO), using discrete Langevin dynamics, has been proposed, demonstrating better performance than several learning-based solvers. This study proposes a different approach that integrates gradient-based update through continuous relaxation, combined with Quasi-Quantum Annealing (QQA). QQA smoothly transitions the objective function, starting from a simple convex function, minimized at half-integral values, to the original objective function, where the relaxed variables are minimized only in the discrete space. Furthermore, we incorporate parallel run communication leveraging GPUs to enhance exploration capabilities and accelerate convergence. Numerical experiments demonstrate that our method is a competitive general-purpose solver, achieving performance comparable to iSCO and learning-based solvers across various benchmark problems. Notably, our method exhibits superior speed-quality trade-offs for large-scale instances compared to iSCO, learning-based solvers, commercial solvers, and specialized algorithms.