Ising formulations of many NP problems

arXiv · PDF · Open in the Atlas

Code that ran

We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. If it links a repository, it is listed below.

Repositories linked to this paper

• PMosharev/SimCIM-simple-implementation
• bqth29/simulated-bifurcation-algorithm
• iQuHACK/2021_RS-3
• iQuHACK/2021_sycamore

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

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 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.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("1302.5843")
get_code_for_paper("1302.5843")
have("1302.5843")

Connect an agent — have() is free.