Research map / Optimization / Optimizers
Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PQQA, which relaxes binary CO variables, anneals an alpha-entropy term from negative to positive weight (quasi-quantum annealing), and runs parallel Langevin-style gradient chains coupled by a diversity term on GPUs.
Problem
General-purpose solving of combinatorial optimization problems (MIS, max clique, max cut, balanced graph partition, graph coloring) at scale, where sampling and learning-based solvers have poor scalability and speed-quality tradeoffs.
Approach
Continuous relaxation with a convex-to-discrete entropy annealing (quasi-quantum annealing) driven by gradient-based Langevin-type updates, plus a communication term across parallel runs that rewards spread in relaxed variables, which pushes them toward binary values.
Key results
- On ER-[9000-11000] MIS, PQQA (S=1000, more steps) reaches ApR 1.043 versus iSCO's 1.008 and KaMIS as reference 1.000.
- On random regular graphs d=100 with 10^6 nodes, PQQA (more steps) gets ApR 0.966 vs SA 0.194 and GREEDY 0.664.
- On COLOR queen11-11 and queen13-13, PQQA uses 11 and 14 conflicts vs Tabucol's 20 and 35.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PQQA with more steps and S=1,000 instead of iSCO with more steps | MIS · ER-[9000-11000] | ApR: 1.008 -> 1.043 | Helped |
| Use PQQA with more steps and S=1,000 instead of iSCO with more steps | MIS · ER-[700-800] | ApR: 1.006 -> 1.009 | Helped |
| Use PQQA instead of iSCO | Max clique · RBtest | ApR: 0.857 $\pm$ 0.062 -> 0.868 $\pm$ 0.061 | Helped |
| Use PQQA instead of iSCO | Max clique · Twitter | ApR: 1.000 $\pm$ 0.000 -> 1.000 $\pm$ 0.000 | No clear effect |
| Use PQQA instead of GAP | Balanced graph partition · VGG | Edge cut ratio: 0.04 -> 0.04 | No clear effect |
| Use PQQA instead of iSCO | Max cut · Optsicom | ApR: 1.000 -> 1.000 | No clear effect |
| Use PQQA instead of Tabucol | Graph coloring · queen13-13 | Conflicts: 35 -> 14 | Helped |
| Use gradient-based QQA transitions instead of SA with Gibbs sampling (ablation) | MIS · Largest ER graphs | Sampling steps to reach solution quality: over 10^4 times | Helped |
| Skip the annealing phase with γ < 0 (ablation) | PQQA · MIS, largest ER graph | Solution quality | Hurt |
| Use faster annealing with 1,000 steps (ablation) | PQQA · MIS, largest ER graph | ApR: around 1.00 | No clear effect |
| Set the initial γ below -2 (ablation) | PQQA · MIS, largest ER graph | Solution quality | No clear effect |
| Increase communication strength α (ablation) | PQQA with S=1,000 · MIS, small ER graphs | Convergence speed | Helped |
Surprising findings
- Skipping the negative-gamma annealing phase yields poor outcomes, while even very fast annealing (10^3 steps) keeps ApR near 1.00 on large ERGs.
Limitations
- Gamma schedule and penalty coefficients require problem-specific tuning (learning rate chosen from {1,0.1,0.01}).
- Balanced graph partition took about 20 minutes on the largest graph and max-cut results are only comparable to iSCO, not clearly better.
Experimental setup
Datasets: SATLIB Erdos-Renyi graphs regular random graphs RB model graphs Twitter graph Optsicom COLOR dataset DNN computation graphs (MNIST, VGG, AlexNet, ResNet, Inception-v3)
Benchmarks: SATLIB MIS ER-[700-800] ER-[9000-11000] RRG MIS Twitter max clique RBtest Optsicom maxcut ER/BA maxcut balanced graph partition DNN graphs COLOR graph coloring
Metrics: approximation ratio runtime edge cut ratio balanceness conflicts
Baselines: iSCO KaMIS Gurobi DIMES LwD CRA-GNN GAP hMETIS Tabucol PI-SAGE
Builds on: iSCO simulated annealing alpha-entropy AdamW
Closest papers by meaning
- Regularized Langevin Dynamics for Combinatorial Optimization (ICML 2025 · similarity 0.87)
- PALQO: Physics-informed model for Accelerating Large-scale Quantum Optimization (NeurIPS 2025 · similarity 0.86)
- Quantum Optimization via Gradient-Based Hamiltonian Descent (ICML 2025 · similarity 0.85)
- Curriculum reinforcement learning for quantum architecture search under hardware errors (ICLR 2024 · similarity 0.85)
- Scalable Quantum-Inspired Optimization Through Dynamic Qubit Compression (AAAI 2025 · similarity 0.85)
- Q-MAML: Quantum Model-Agnostic Meta-Learning for Variational Quantum Algorithms (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.