Ising formulations of NP-complete and NP-hard problems
Given a hard combinatorial problem, rewrite it as an Ising spin model whose lowest-energy spin configurations are exactly that problem's solutions, so that a machine which minimizes energy can be pointed at the problem at all.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
Given a hard combinatorial problem, rewrite it as an Ising spin model whose lowest-energy spin configurations are exactly that problem's solutions, so that a machine which minimizes energy can be pointed at the problem at all. An Ising formulation restates a combinatorial problem in the language of ±1 spins: the problem's degrees of freedom become spins, and its constraints and objective are carried by the couplings and fields of an Ising Hamiltonian whose ground states are the problem's solutions. The paper provides such formulations for many NP-complete and NP-hard problems, including all of Karp's 21 NP-complete problems, collecting and extending mappings to the Ising model from partitioning, covering and satisfiability. It reports that in each case the required number of spins is at most cubic in the size of the problem, so the encoding itself stays polynomial across the problems it covers. The stated purpose is downstream of the encoding: the author writes that the work may be useful in designing adiabatic quantum optimization algorithms, which makes the formulation the input such an algorithm consumes rather than an algorithm in its own right.
Circuit & simulation
problem
encodetransform
algorithm
transformmeasure
readout
measure
What this takes and returns
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
How it works
An Ising formulation restates a combinatorial problem in the language of ±1 spins: the problem's degrees of freedom become spins, and its constraints and objective are carried by the couplings and fields of an Ising Hamiltonian whose ground states are the problem's solutions. The paper provides such formulations for many NP-complete and NP-hard problems, including all of Karp's 21 NP-complete problems, collecting and extending mappings to the Ising model from partitioning, covering and satisfiability. It reports that in each case the required number of spins is at most cubic in the size of the problem, so the encoding itself stays polynomial across the problems it covers. The stated purpose is downstream of the encoding: the author writes that the work may be useful in designing adiabatic quantum optimization algorithms, which makes the formulation the input such an algorithm consumes rather than an algorithm in its own right. The Classiq library carries this subject under applications · logistics. Reported cost: At most cubic in the size of the problem, counted in spins — an encoding size, not a running time. No speedup is claimed: the abstract states no time to solution, no query or gate count and no comparison with classical solvers, and its only forward-looking statement is that the work may be useful in designing adiabatic quantum optimization algorithms..
Implementation
Unsupported
ising-formulations-np-problems.txt
ALGORITHM: Ising formulations of NP-complete and NP-hard problems
PROBLEM: Given a hard combinatorial problem, rewrite it as an Ising spin model whose lowest-energy spin configurations are exactly that problem's solutions, so that a machine which minimizes energy can be pointed at the problem at all.
IDEA: An Ising formulation restates a combinatorial problem in the language of ±1 spins: the problem's degrees of freedom become spins, and its constraints and objective are carried by the couplings and fields of an Ising Hamiltonian whose ground states are the problem's solutions. The paper provides such formulations for many NP-complete and NP-hard problems, including all of Karp's 21 NP-complete problems, collecting and extending mappings to the Ising model from partitioning, covering and satisfiability. It reports that in each case the required number of spins is at most cubic in the size of the problem, so the encoding itself stays polynomial across the problems it covers. The stated purpose is downstream of the encoding: the author writes that the work may be useful in designing adiabatic quantum optimization algorithms, which makes the formulation the input such an algorithm consumes rather than an algorithm in its own right.
REPORTED COST: At most cubic in the size of the problem, counted in spins — an encoding size, not a running time. No speedup is claimed: the abstract states no time to solution, no query or gate count and no comparison with classical solvers, and its only forward-looking statement is that the work may be useful in designing adiabatic quantum optimization algorithms.
BASIS: abstract of arXiv:1302.5843: "In each case, the required number of spins is at most cubic in the size of the problem." The scope of "each case" is set by the preceding clause, "Ising formulations for many NP-complete and NP-hard problems, including all of Karp's 21 NP-complete problems". The same abstract states no running time and no classical comparison; its closing claim is "This work may be useful in designing adiabatic quantum optimization algorithms." The Classiq index entry read for this record gives the directory path and its file names only, and states no bound.
DEMONSTRATED BY: the Classiq library entry applications/logistics/traveling_salesman_problem
PRIMARY SOURCE: Andrew Lucas (2013), Ising formulations of many NP problems — https://arxiv.org/abs/1302.5843
This is a literature reference record, not an executable circuit.
A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Quantum vs classical
Classical baseline
Compare Optimization · Ising encoding with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Declared gaps
Nobody has reviewed this record for gaps yet.
Literature & references
Ising formulations of many NP problems2013 · Andrew Lucas
Primary source. It collects and extends mappings to the Ising model from partitioning, covering and satisfiability into formulations for many NP-complete and NP-hard problems, including all of Karp's 21, and states that the required number of spins is at most cubic in the size of the problem in every case. Consult it for the individual constructions, their penalty terms and weights, and for which problems it treats: the abstract names them only as a class.