Back

Ising formulations of many NP problems

"”Ising formulations of many NP problems"

Published by Andrew Lucas (Harvard University), 23rd February 2013

arXiv:1302.5843
Optimization
Ising formulations of many NP problems

Qu&Co comments on this publication:

In this paper, Andrew Lucas provides Ising formulations for many NP-complete and NP-hard problems, including all of Karp's 21 NP-complete problems. 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.