# Ising formulations of many NP problems

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

## Key facts

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

## Built on by (most cited first, 30 of 207)

- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Noisy intermediate-scale quantum (NISQ) algorithms](https://mlsanity.com/paper/2101.08448/) (2021)
- [A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2406.01661/) (2024)
- [Variational Neural Annealing](https://mlsanity.com/paper/2101.10154/) (2021)
- [Equivariant quantum circuits for learning on weighted graphs](https://mlsanity.com/paper/2205.06109/) (2022)
- [Graph Coloring with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2202.01606/) (2022)
- [Training an Ising Machine with Equilibrium Propagation](https://mlsanity.com/paper/2305.18321/) (2023)
- [Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics](https://mlsanity.com/paper/2502.08696/) (2025)
- [Link Scheduling using Graph Neural Networks](https://mlsanity.com/paper/2109.05536/) (2021)
- [Variational Annealing on Graphs for Combinatorial Optimization](https://mlsanity.com/paper/2311.14156/) (2023)
- [Application of QUBO solver using black-box optimization to structural design for resonance avoidance](https://mlsanity.com/paper/2204.04906/) (2022)
- [Agent-Q: Fine-Tuning Large Language Models for Quantum Circuit Generation and Optimization](https://mlsanity.com/paper/2504.11109/) (2025)
- [Controlling Continuous Relaxation for Combinatorial Optimization](https://mlsanity.com/paper/2309.16965/) (2023)
- [Feature Selection for Recommender Systems with Quantum Computing](https://mlsanity.com/paper/2110.05089/) (2021)
- [Noise-injected analog Ising machines enable ultrafast statistical sampling and machine learning](https://mlsanity.com/paper/2112.11534/) (2021)
- [Towards Feature Selection for Ranking and Classification Exploiting Quantum Annealers](https://mlsanity.com/paper/2205.04346/) (2022)
- [Q-Seg: Quantum Annealing-Based Unsupervised Image Segmentation](https://mlsanity.com/paper/2311.12912/) (2023)
- [QUASAR: Quantum Assembly Code Generation Using Tool-Augmented LLMs via Agentic RL](https://mlsanity.com/paper/2510.00967/) (2025)
- [Regularized Langevin Dynamics for Combinatorial Optimization](https://mlsanity.com/paper/2502.00277/) (2025)
- [Penalty Weights in QUBO Formulations: Permutation Problems](https://mlsanity.com/paper/2206.11040/) (2022)
- [Reinforcement Learning for Variational Quantum Circuits Design](https://mlsanity.com/paper/2409.05475/) (2024)
- [Black-box optimization for integer-variable problems using Ising machines and factorization machines](https://mlsanity.com/paper/2209.01016/) (2022)
- [Hybrid Approach for Solving Real-World Bin Packing Problem Instances Using Quantum Annealers](https://mlsanity.com/paper/2303.01977/) (2023)
- [Automated Metaheuristic Algorithm Design with Autoregressive Learning](https://mlsanity.com/paper/2405.03419/) (2024)
- [Generative quantum combinatorial optimization by means of a novel conditional generative quantum eigensolver](https://mlsanity.com/paper/2501.16986/) (2025)
- [Quantum-enhanced Markov chain Monte Carlo](https://mlsanity.com/paper/2203.12497/) (2022)
- [Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problems](https://mlsanity.com/paper/2207.08189/) (2022)
- [Quantum Graph Learning: Frontiers and Outlook](https://mlsanity.com/paper/2302.00892/) (2023)
- [Quantum Natural Language Processing](https://mlsanity.com/paper/2403.19758/) (2024)
- [Message Passing Variational Autoregressive Network for Solving Intractable Ising Models](https://mlsanity.com/paper/2404.06225/) (2024)

## 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.