Ising formulations of many NP problems
- Publisher: Frontiers Media S.A.
- Journal: Frontiers in Physics,volume 2 (issn: 2296-424X)
Related identifiers: ,
- 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