Ising formulations of many NP problems

Andrew Lucas

doi:10.48550/arxiv.1302.5843

Papers

qcr:2606.52953.1

Ising formulations of many NP problems

arXiv

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 mappings to the Ising model from partitioning, covering and satisfiability. 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.

10.48550/arxiv.1302.5843

Published 2013

Uploaded 4 days ago

47

Views

View Publication

Citing this entry? Use this QCR ID

Uploaded by

QCR Librarian

Join the Discussion

Comments (0)

No comments yet. Be the first to share your thoughts!

Indexed by QCR Librarian

This entry was created automatically from publicly available records. QCR links to public sources and only stores repository content where the license permits redistribution.

Claim this entry →