mlsanityData to 14 Oct 2026

Ising formulations of many NP problems

arXiv 1302.5843 ↗First posted 23 Feb 2013cond-mat.stat-mech cs.CC cs.DScited by 207

Not on the map. Why?

Abstract (arXiv)

We provide Ising formulations for many NP-complete and NP-hard problems, including all of Karp's 21 NP-complete problems. This collects and extends mappings to the Ising model from partitioning, covering and satisfiability. In each case, the required number of spins is at most cubic in the size of the problem. This work may be useful in designing adiabatic quantum optimization algorithms.

Key facts. Cited by 207 papers in the map (data through 14 Oct 2026). First posted on arXiv 23 Feb 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 18; 2022: 25; 2023: 26; 2024: 33; 2025: 52; 2026: 53.

207 papers.

Sort:

By area:

  1. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 108
  2. 2021Noisy intermediate-scale quantum (NISQ) algorithmscited by 79
  3. 2024A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimizationcited by 59
  4. 2021Variational Neural Annealingcited by 47
  5. 2022Equivariant quantum circuits for learning on weighted graphscited by 41
  6. 2022Graph Coloring with Physics-Inspired Graph Neural Networkscited by 29
  7. 2023Training an Ising Machine with Equilibrium Propagationcited by 29
  8. 2025Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physicscited by 29
  9. 2021Link Scheduling using Graph Neural Networkscited by 26
  10. 2023Variational Annealing on Graphs for Combinatorial Optimizationcited by 21
  11. 2022Application of QUBO solver using black-box optimization to structural design for resonance avoidancecited by 17
  12. 2025Agent-Q: Fine-Tuning Large Language Models for Quantum Circuit Generation and Optimizationcited by 17
38 more
  1. 2023Controlling Continuous Relaxation for Combinatorial Optimizationcited by 16
  2. 2021Feature Selection for Recommender Systems with Quantum Computingcited by 14
  3. 2021Noise-injected analog Ising machines enable ultrafast statistical sampling and machine learningcited by 11
  4. 2022Towards Feature Selection for Ranking and Classification Exploiting Quantum Annealerscited by 11
  5. 2023Q-Seg: Quantum Annealing-Based Unsupervised Image Segmentationcited by 11
  6. 2025QUASAR: Quantum Assembly Code Generation Using Tool-Augmented LLMs via Agentic RLcited by 11
  7. 2025Regularized Langevin Dynamics for Combinatorial Optimizationcited by 10
  8. 2022Penalty Weights in QUBO Formulations: Permutation Problemscited by 9
  9. 2024Reinforcement Learning for Variational Quantum Circuits Designcited by 9
  10. 2022Black-box optimization for integer-variable problems using Ising machines and factorization machinescited by 8
  11. 2023Hybrid Approach for Solving Real-World Bin Packing Problem Instances Using Quantum Annealerscited by 7
  12. 2024Automated Metaheuristic Algorithm Design with Autoregressive Learningcited by 7
  13. 2025Generative quantum combinatorial optimization by means of a novel conditional generative quantum eigensolvercited by 7
  14. 2022Quantum-enhanced Markov chain Monte Carlocited by 6
  15. 2022Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problemscited by 6
  16. 2023Quantum Graph Learning: Frontiers and Outlookcited by 6
  17. 2024Quantum Natural Language Processingcited by 6
  18. 2024Message Passing Variational Autoregressive Network for Solving Intractable Ising Modelscited by 6
  19. 2024Qubit-efficient Variational Quantum Algorithms for Image Segmentationcited by 6
  20. 2021Deep Learning and Spectral Embedding for Graph Partitioningcited by 5
  21. 2025Demonstrating Real Advantage of Machine-Learning-Enhanced Monte Carlo for Combinatorial Optimizationcited by 5
  22. 2021Lossy compression of statistical data using quantum annealercited by 4
  23. 2022From Quantum Graph Computing to Quantum Graph Learning: A Surveycited by 4
  24. 2022Implementation of Trained Factorization Machine Recommendation System on Quantum Annealercited by 4
  25. 2022FrozenQubits: Boosting Fidelity of QAOA by Skipping Hotspot Nodescited by 4
  26. 2023Low-rank combinatorial optimization and statistical learning by spatial photonic Ising machinecited by 4
  27. 2024Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Updatecited by 4
  28. 2024Solving QUBO on the Loihi 2 Neuromorphic Processorcited by 4
  29. 2024MG-Net: Learn to Customize QAOA with Circuit Depth Awarenesscited by 4
  30. 2025SWIFT-FMQA: Enhancing Factorization Machine with Quadratic-Optimization Annealing via Sliding Windowcited by 4
  31. 2021Focusing on the Hybrid Quantum Computing -- Tabu Search Algorithm: new results on the Asymmetric Salesman Problemcited by 3
  32. 2021Quantum Approximate Optimization Algorithm applied to the binary perceptroncited by 3
  33. 2022Multi-objective QUBO Solver: Bi-objective Quadratic Assignmentcited by 3
  34. 2022Black Box Optimization Using QUBO and the Cross Entropy Methodcited by 3
  35. 2022Quantum Sparse Codingcited by 3
  36. 2022Feature Selection for Classification with QAOAcited by 3
  37. 2023Clustering Method for Time-Series Images Using Quantum-Inspired Computing Technologycited by 3
  38. 2023Projected Stochastic Gradient Descent with Quantum Annealed Binary Gradientscited by 3

50 most cited of 207 All 207 (JSON)