Ising formulations of many NP problems

By Andrew Lucas. Front. Physics, 2013

2,833 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/d372de3869028723e91fca3136840759c63a1549

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Photonic matrix multiplication lights up photonic accelerator and beyond (2022, background): “In addition, multiple algorithms can be combined to jointly address optimization and decision issues, such as NP-hard problems and high-speed tracking problems 51,74,168 .”
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz (2017, background): “The general strategy is to incorporate the hard constraints as penalty terms in the cost function, and then convert the cost function to a cost Hamiltonian [9, 52, 65].”
Ising machines as hardware solvers of combinatorial optimization problems (2022, methodology): “An early example of such a dynamical solver was proposed by Hopﬁeld and collaborators 81,82 where electronic circuits were used to realize (1).”
Realizing the classical XY Hamiltonian in polariton simulators. (2016, positive): “Replacing the unit vectors in the XY Hamiltonian with complex numbers z j = cos θ j + i sin θ j leads to formulation as the continuous complex constant modulus quadratic optimization problem [12, 13], that is known to be NP-hard in general.”
Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems (2019, background): “In particular, “Ising machines” designed for finding a ground state of the Ising spin model (3) have recently attracted much attention because many combinatorial optimization problems can be mapped to the Ising problem (4), including very-large-scale integrated circuit design (5), drug design (6), a”
Quantum annealing for industry applications: introduction and review (2021, neutral): “The Ising model can be easily transformed into various other forms, such as the unconstrained binary quadratic program [65], the undirected graphical model [114], and the QUBO problem [113].”
Warm-starting quantum optimization (2020, background): “We expect warm-start to be applicable to other problems within Combinatorial Optimization and Integer Programming, for which a good solution can be found through randomized rounding [50], possibly following an encoding into a QUBO [69, 70, 94], a mixed-integer linear optimization problem [59], or a ”
Open Source (2014, positive): “…and its established capacity to function as a unified framework for combinatorial optimization, as documented in studies such as Kochenberger et al. (2004), Kochenberger et al. (2014), Lucas (2014) and Anthony et al. (2017), Aramon et al. (2019), Glover et al. (2022a) and Glover et al. (2022b).”
100,000-spin coherent Ising machine (2021, positive): “It is known that various types of these problems can be converted to ground-state search problems of the Ising model ( 27 ) with polynomial resources ( 28 , 29 ).”
Adiabatic Quantum Computing (2016, background): “We also remark that Ising formulations for many NP-complete and NP-hard problems, including all of Karp’s 21 NP-complete problems (Karp, 1972), are known (Lucas, 2014), but it is unknown whether they are amenable to a quantum speedup.”
Challenges and opportunities in quantum optimization (2023, neutral): “In the case that certain groups of decision variables are not correlated, QUBOs can be decomposed trivially into smaller sub-QUBOs to be solved independently.”