Ising formulations of many NP problems

2014 · Frontiers in Physics · 2,566 citations · 2 from inside this corpus

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.

5 of 5 neighbouring works in this corpus. Blue is what this paper cites; orange is what cites it, and a dashed line is one neighbour citing another. Only the largest labels are drawn — every node carries its full title on hover.

this paper works it cites works citing it node size = global citations · hover for the full title

What this paper cites, inside the corpus

Paper	Year	Cited
Spin Glass Theory and Beyond	1988	2,751
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Pro…	2001	2,110
Quantum annealing with manufactured spins	2011	1,952

What cites it, inside the corpus

Paper	Year	Cited
Noisy intermediate-scale quantum algorithms	2022	1,770
Adiabatic quantum computation	2018	1,597

Links

DOI · Open access copy · OpenAlex record

Topics

Quantum Computing Algorithms and Architecture	Computer Science
Complexity and Algorithms in Graphs	Computer Science
Machine Learning and Algorithms	Computer Science

Is this record sound?

complete

Nothing in this record contradicts itself and no field we check is missing.

supports1 author record(s) attached.
supports78 reference(s) recorded.
supportsThe DOI's year agrees with the publication year.
supportsA title is present.

Provenance

Everything above was read from one stored OpenAlex payload, fetched 2026-09-04T03:58:49+00:00.

sha256 a2172c1bbe00c44b…