47-779 course syllabus - Fall 2020

Week of September 14th / Week 2

Ising, Quadratic Unconstrained Binary Optimization

Ising model basics

• Stephen G Brush. History of the Lenz-Ising model. Reviews of Modern Physics, 39(4):883, 1967.
• David Sherrington and Scott Kirkpatrick. Solvable model of a spin-glass. Phys. Rev. Lett., 35:1792-1796, Dec 1975. doi: 10.1103/PhysRevLett.35.1792. https://link.aps.org/doi/10.1103/
• P. Ray, B. K. Chakrabarti, and Arunava Chakrabarti. Sherrington-Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations. Phys. Rev. B, 39:11828-11832. Jun 1989 https://link.aps.org/doi/10.1103/PhysRevB

Simulated Annealing

• Scott Kirkpatrick, C Daniel Gelatt, and Mario P Vecchi. Optimization by simulated annealing. Science, 220(4598):671-680, 1983.
• Christos Koulamas, SR Antony, and R Jaen. A survey of simulated annealing applications to operations research problems. Omega, 22(1):41-56, 1994.

Markov-chain Monte Carlo methods

• Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21(6):1087-1092, 1953.
• Alfred B Bortz, Malvin H Kalos, and Joel L Lebowitz. A new algorithm for Monte Carlo simulation of Ising spin systems. Journal of Computational Physics, 17(1):10-18, 1975.
• Matthias Troyer and Uwe-Jens Wiese. Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations. Physical Review Letters, 94(17):170201, 2005.
• Peter Young, Sergey Knysh, and Vadim N Smelyanskiy. Size dependence of the minimum excitation gap in the quantum adiabatic algorithm. Physical Review Letters, 101(17):170503, 2008.

Benchmarking classical methods

• Iain Dunning, Swati Gupta, and John Silberholz. What works best when? a systematic evaluation of heuristics for max-cut and qubo. INFORMS Journal on Computing, 30(3):608-624, 2018.
• Carleton Coffrin, Harsha Nagarajan, and Russell Bent. Evaluating Ising processing units with integer programming. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 163-181. Springer, 2019.

Formulating combinatorial problems as QUBOs

• Andrew Lucas. Ising formulations of many NP problems. Frontiers in Physics, 2:5, 2014.