Mapping NP-hard and NP-complete optimisation problems to Quadratic Unconstrained Binary Optimisation problems

Quantum optimization of fully connected spin glasses

Original

D. Venturelli, S. Mandra, S. Knysh, B. O’Gorman, R. Biswas, and V. Smelyanskiy · 1911

Earlier work this paper cites.

Discrete-variable extremum problems

G. B. Dantzig · 1957

Earlier work this paper cites.

Reducibility among combinatorial problems

R. M. Karp · 1972

Earlier work this paper cites.

On the computational complexity of ising spin glass models

F. Barahona · 1982

Earlier work this paper cites.

A probabilistic heuristic for a computationally difficult set covering problem

T. A. Feo and M. G. Resende · 1989

Earlier work this paper cites.

Computers and Intractability; A Guide to the Theory of NP-Completeness

M. R. Garey and D. S. Johnson · 1990

Cited alongside, same era.

A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem

E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda · 2001

Cited alongside, same era.

Pseudo-boolean optimization

E. Boros and P. L. Hammer · 2002

Cited alongside, same era.

Anderson localization makes adiabatic quantum optimization fail

B. Altshuler, H. Krovi, and J. Roland · 2010

Cited alongside, same era.

Does adiabatic quantum optimization fail for np-complete problems?

N. G. Dickson and M. Amin · 2011

Cited alongside, same era.

Ising formulations of many np problems

A. Lucas · 2014

Later among the works it cites.

Defining and detecting quantum speedup

T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, and M. Troyer · 2014

Later among the works it cites.

Quantum versus classical annealing of ising spin glasses

B. Heim, T. F. Rønnow, S. V. Isakov, and M. Troyer · 2015

Later among the works it cites.

A case study in programming a quantum annealer for hard operational planning problems

E. G. Rieffel, D. Venturelli, B. O’Gorman, M. B. Do, E. M. Prystay, and V. N. Smelyanskiy · 2015

Later among the works it cites.

Hard combinatorial problems and minor embeddings on lattice graphs

A. Lucas · 2019

Closest in time.