Fetching the paper…
Reading the bibliography…
We provide Ising formulations for many NP-complete and NP-hard problems, including all of Karp's 21 NP-complete problems.
X. Peng, Z. Liao, N. Xu, G. Qin, X. Zhou, D. Suter, and J. Du · 1935
Earlier work this paper cites.
“Reducibility among combinatorial problems”, in Complexity of Computer
R.M. Karp · 1972
Earlier work this paper cites.
“Every planar map is four colorable. I. Discharging”, Illinois Journal of Mathematics
K. Appel and W. Haken · 1977
Earlier work this paper cites.
“Every planar map is four colorable. II. Reducibility”, Illinois Journal of Mathematics
K. Appel, W. Haken, and J. Koch · 1977
Earlier work this paper cites.
Computers and Intractability: a Guide to the Theory of
M.R. Garey and D.S. Johnson · 1979
Earlier work this paper cites.
“On the computational complexity of Ising spin glass models”, Journal of Physics
F. Barahona · 1982
Earlier work this paper cites.
“Neural networks and physical systems with emergent collective computational abilities”, Proceedings of the National Academy of Sciences
J.J. Hopfield · 1982
Earlier work this paper cites.
“The Potts model”, Reviews of Modern Physics
F-Y. Wu · 1982
Earlier work this paper cites.
“Optimization by simulated annealing”, Science
S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi · 1983
Earlier work this paper cites.
“Application of statistical mechanics to NP-complete problems in combinatorial optimisation”, Journal of Physics
Y. Fu and P.W. Anderson · 1986
Earlier work this paper cites.
Spin Glass Theory and Beyond
M. Mézard, G. Parisi, and M. Virasoro · 1987
Earlier work this paper cites.
“Spin glasses and the statistical mechanics of protein folding”, Proceedings of the National Academy of Sciences
J.D. Bryngelson and P.G. Wolynes · 1987
Earlier work this paper cites.
“A decomposition method for minimizing quadratic pseudo-Boolean functions”, Operations Research Letters
A. Billionnet and B. Jaumard · 1989
Earlier work this paper cites.
“The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds”, Annals of Operations Research
E. Boros and P.L. Hammer · 1991
Earlier work this paper cites.
“A random polynomial-time algorithm for approximating the volume of convex bodies”, Journal of the ACM
M. Dyer, A. Frieze, and R. Kannan · 1991
Earlier work this paper cites.
“Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete”, Journal of Computational Biology
B. Berger and T. Leighton · 1998
Earlier work this paper cites.
“Finding a large hidden clique in a random graph”, Random Structures & Algorithms
N. Alon, M. Krivelevich, and B. Sudakov · 1998
Earlier work this paper cites.
Theory of Integer and Linear Programming
A. Schrijver · 1998
Earlier work this paper cites.
Quantum Computation and Quantum Information
M.A. Nielsen and I.A. Chuang · 2000
Earlier work this paper cites.
“A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem”, Science
E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda · 2001
Earlier work this paper cites.
“Theory of quantum annealing of an Ising spin glass”, Science
G.E. Santoro, R. Martonak, E. Tosatti, and R. Car · 2002
Cited alongside, same era.
“Pseudo-Boolean optimization”, Discrete Applied Mathematics
E. Boros and P.L. Hammer · 2002
Cited alongside, same era.
“Finding cliques by quantum adiabatic evolution”, Quantum Information and Computation
A.M. Childs, E. Farhi, J. Goldstone, and S. Gutmann · 2002
Cited alongside, same era.
Approximation Algorithms
V.V. Vazirani · 2003
Cited alongside, same era.
Knapsack Problems
H. Kellerer and U. Pferschy · 2004
Cited alongside, same era.
“Random knapsack in expected polynomial time”, Proceedings of the 35 th {}^{\text{{th}}} Annual ACM Symposium on the Theory of Computing
R. Beier and B. Vöcking · 2004
Cited alongside, same era.
“Does adiabatic quantum optimization fail for NP-complete problems?”, Physical Review Letters
N.G. Dickson and M.H.S. Amin · 2011
Later among the works it cites.
“Unstructured randomness, small gaps and localization”, Quantum Computation and Information
E. Farhi, J. Goldstone, D. Gosset, S. Gutmann, and P. Shor · 2011
Later among the works it cites.
I. Hen and A.P. Young · 2011
Later among the works it cites.
“Quantum annealing with manufactured spins”, Nature
M.W. Johnson et. al · 2011
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
“The NP-completeness column”, ACM Transactions on Algorithms
D.S. Johnson · 2005
Cited alongside, same era.
Phase Transitions in Combinatorial Optimization Problems: Basics,
A.K. Hartmann and M. Weigt · 2006
Cited alongside, same era.
“Preprocessing of unconstrained quadratic binary optimization”, RUTCOR Research Report
E. Boros, P.L. Hammer, and G. Tavares · 2006
Cited alongside, same era.
“Solving random satisfiable 3CNF formulas in expected polynomial time”, Proceedings of the 17 th {}^{\text{{th}}} Annual ACM-SIAM Symposium on Discrete Algorithms
M. Krivelevich and D. Vilenchik · 2006
Cited alongside, same era.
“Randomized algorithms for the low-rank approximation of matrices”, Proceedings of the National Academy of Sciences
E. Liberty, F. Woolfe, P.G. Martinsson, V. Rokhlin, and M. Tygert · 2007
Cited alongside, same era.
“ Colloquium: Quantum annealing and analog quantum computation”, Reviews of Modern Physics
A. Das and B.K. Chakrabarti · 2008
Cited alongside, same era.
V. Choi · 2011
Later among the works it cites.
N. Halko, P. Martinsson, and J.A. Tropp · 2011
Later among the works it cites.
E. Farhi, D. Gosset, I. Hen, A.W. Sandvik, P. Shor, A.P. Young, and F. Zamponi · 2012
Later among the works it cites.
“Ground state spin logic”, Europhysics Letters
J.D. Whitfield, M. Faccin, and J.D. Biamonte · 2012
Later among the works it cites.
N. Xu, J. Zhu, D. Lu, X. Zhou, X. Peng, and J. Du · 2012
Later among the works it cites.
A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, and A. Aspuru-Guzik · 2012
Later among the works it cites.
V. Denchev, N. Ding, S.V.N. Vishwanathan, and H. Neven · 2012
Later among the works it cites.
“Solving the graph isomorphism problem with a quantum annealer”, Physical Review
I. Hen and A.P. Young · 2012
Later among the works it cites.
V. Bapst, L. Foini, F. Krzakala, G. Semerjian, and F. Zamponi · 2013
Closest in time.
“Experimental signature of programmable quantum annealing”, Nature Communications
S. Boixo, T. Albash, F.M. Spedalieri, N. Chancellor, and D.A. Lidar · 2013
Closest in time.
J-P. Bouchaud · 2013
Closest in time.
“Multistable binary decision making on networks”, Physical Review
A. Lucas and C.H. Lee · 2013
Closest in time.
“Experimental determination of Ramsey numbers”, Physical Review Letters
Z. Bian, F. Chudak, W.G. Macready, L. Clark, and F. Gaitan · 2013
Closest in time.
R. Babbush, B. O’Gorman, and A. Aspuru-Guzik · 2013
Closest in time.
“Spin glass approach to the feedback vertex set problem”, European Physical Journal
H-J. Zhou · 2013
Closest in time.