Ising formulations of many NP problems
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Frontiers Media S.A.
2014-02-01
|
| Series: | Frontiers in Physics |
| Subjects: | |
| Online Access: | http://journal.frontiersin.org/Journal/10.3389/fphy.2014.00005/full |
| _version_ | 1818550385325899776 |
|---|---|
| author | Andrew eLucas |
| author_facet | Andrew eLucas |
| author_sort | Andrew eLucas |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-12T08:45:45Z |
| format | Article |
| id | doaj.art-361397a1aee14c1f90e193c580946466 |
| institution | Directory Open Access Journal |
| issn | 2296-424X |
| language | English |
| last_indexed | 2024-12-12T08:45:45Z |
| publishDate | 2014-02-01 |
| publisher | Frontiers Media S.A. |
| record_format | Article |
| series | Frontiers in Physics |
| spelling | doaj.art-361397a1aee14c1f90e193c5809464662022-12-22T00:30:32ZengFrontiers Media S.A.Frontiers in Physics2296-424X2014-02-01210.3389/fphy.2014.0000574887Ising formulations of many NP problemsAndrew eLucas0Harvard UniversityWe 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.http://journal.frontiersin.org/Journal/10.3389/fphy.2014.00005/fullAlgorithmscomplexity theoryspin glassesadiabatic quantum computationNP |
| spellingShingle | Andrew eLucas Ising formulations of many NP problems Frontiers in Physics Algorithms complexity theory spin glasses adiabatic quantum computation NP |
| title | Ising formulations of many NP problems |
| title_full | Ising formulations of many NP problems |
| title_fullStr | Ising formulations of many NP problems |
| title_full_unstemmed | Ising formulations of many NP problems |
| title_short | Ising formulations of many NP problems |
| title_sort | ising formulations of many np problems |
| topic | Algorithms complexity theory spin glasses adiabatic quantum computation NP |
| url | http://journal.frontiersin.org/Journal/10.3389/fphy.2014.00005/full |
| work_keys_str_mv | AT andrewelucas isingformulationsofmanynpproblems |