Ising formulations of many NP problems

Article, Preprint English OPEN
Lucas, Andrew;
  • Publisher: Frontiers Media S.A.
  • Journal: Frontiers in Physics,volume 2 (issn: 2296-424X)
  • Related identifiers: doi: 10.3389/fphy.2014.00005/full, doi: 10.3389/fphy.2014.00005
  • Subject: complexity theory | Algorithms | NP | Computer Science - Computational Complexity | Computer Science - Data Structures and Algorithms | Physics | Condensed Matter - Statistical Mechanics | adiabatic quantum computation | QC1-999 | spin glasses | Quantum Physics

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 spin... View more
Share - Bookmark