Ising formulations of many NP problems

2013/02/28 by Andrew Lucas · 4 citations
Physics and Astronomy · Computer Science · #cond-mat.stat-mech #cs.CC #cs.DS #quant-ph

paper · pdf · doi:10.3389/fphy.2014.00005

published as Frontiers in Physics 2, 5 (2014) · 27 pages; v2: substantial revision to intro/conclusion, many more references; v3: substantial revision and extension, to-be-published version

arxiv created 2014/01/24 · arxiv updated 2014/01/28

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.

Cited by

• Quantum Annealing Algorithms for Estimating Ising Partition Functions
• Irreversibility Enhances Quantum-Enhanced Markov-Chain Monte Carlo
• Solving Classical and Quantum Spin Glasses with Deep Boltzmann Quantum States
• Warm-Starting QAOA with XY Mixers: A Novel Approach for Quantum-Enhanced Vehicle Routing Optimization