Exploring Optimization Techniques for Large-scale Problems

My final year research project at department of Physics and Chemistry, University of Macau. We review using simulated annealing and quantum annealing algorithms to minimize the Hamiltonian of an Ising spin glass model to solve a corresponding MAX-CUT problem. We compared the efficiency between homogeneous and inhomogeneous simulated annealing based on the logarithm annealing schedule.

Abstract

Simulated Annealing (SA) is a heuristic algorithm that has been widely used to solve optimization problems over the past four decades. In this article, we provide an overview of SA, including its origins, properties, relationship with statistical mechanics, and controlled parameters. We also present a practical application of SA to optimize a 2000-nodes system using the Ising model. Additionally, we introduce an advanced algorithm derived from SA, known as Quantum Annealing (QA). We explain the theory behind SA and provide an introduction to the background of the Coherent Ising Machine (CIM), which serves as a specific example of SA’s application. In the future works section, we discuss QA and Adiabatic Quantum Computation (AQC) as a brief review and introduction.