Claim record · edition 0.1.0
tn-007Established result
Quadratic unconstrained binary optimization problems map exactly onto Ising spin models, and explicit Ising formulations exist for a catalogue of NP-hard problems.
The substitution between binary variables and ±1 spins is exact and invertible, and published formulations give the couplings, fields, and penalty structures for a range of NP-hard families.
Limits of this claim
An exact encoding does not make a problem easy. Penalty multipliers widen the energy scale and worsen conditioning, and the hardness of the original problem survives the change of variables intact.
Supporting sources
primary paper · identifier verified
Ising formulations of many NP problems
Andrew Lucas · 2013
arXiv:1302.5843
Catalogues explicit Ising encodings for NP-hard problems — the step that turns a combinatorial problem into a spin model a tensor network can act on.
Source record →