%0 Generic %1 Lucas2013Ising %A Lucas, Andrew %D 2013 %K ising %T Ising formulations of many NP problems %U http://arxiv.org/abs/1302.5843 %X 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.

@misc{Lucas2013Ising, abstract = {{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.}}, added-at = {2019-02-26T15:22:34.000+0100}, archiveprefix = {arXiv}, author = {Lucas, Andrew}, biburl = {https://www.bibsonomy.org/bibtex/2eb75a0c6db1d11275a6051de8a06c402/rspreeuw}, citeulike-article-id = {12075873}, citeulike-linkout-0 = {http://arxiv.org/abs/1302.5843}, citeulike-linkout-1 = {http://arxiv.org/pdf/1302.5843}, day = 23, eprint = {1302.5843}, interhash = {dbc08bc6e9d7fa19c94e50824fe35d21}, intrahash = {eb75a0c6db1d11275a6051de8a06c402}, keywords = {ising}, month = feb, posted-at = {2013-08-28 15:20:35}, priority = {2}, timestamp = {2019-02-26T15:22:34.000+0100}, title = {{Ising formulations of many NP problems}}, url = {http://arxiv.org/abs/1302.5843}, year = 2013 }