1302.5843 (Andrew Lucas)

Ising formulations of many NP problems    [PDF]

Andrew Lucas

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 classic results relating partitioning problems to Ising spin glasses, as well as work describing exact covering algorithms and satisfiability. In each case, the state space is at most polynomial in the size of the problem, as is the number of terms in the Hamiltonian. This work may be useful in designing adiabatic quantum optimization algorithms.

View original: http://arxiv.org/abs/1302.5843