HackerPapers

arXiv:1302.5843cond-mat.stat-mech

Ising formulations of many NP problems

Andrew Lucas

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

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.

arXiv comments
27 pages; v2: substantial revision to intro/conclusion, many more references; v3: substantial revision and extension, to-be-published version
Journal reference
Frontiers in Physics 2, 5 (2014)
DOI
doi:10.3389/fphy.2014.00005
Subjects
cond-mat.stat-mechStatistical Mechanics cs.CCComputational Complexity cs.DSData Structures and Algorithms quant-phQuantum Physics

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from May 2020 to May 2020.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Breaking RSA Security with a Low Noise D-Wave 2000Q Quantum Annealer 1 comment

    • This. Essentially, all the quantum annealing stuff that D-Wave does follows the patter of mapping a problem onto a spin glass and then finding the ground state with annealing. The only really interesting theoretical aspect is finding good maps form hard problems to spin glasses.…

      conformistView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.