Given an optimization problem, SA takes into account the relative configuration energies and a fictitious time-dependent temperature when exploring the immense search space probabilistically.
Specifically, we assign the physical system a temperature that can be regarded as a control parameter introduced artificially.
By slowly driving the temperature from a high value to zero, we are able to move the physical system to the state with the lowest value of energy, hence also arrive at the solution of the optimization problem
[1]}, [2]}, [3]}.
Quantum annealing constructs on the physical process of a quantum system whose lowest energy or equivalently, the ground state of the system, represents the solution to an optimization problem posed.
It first establishes a simple quantum system initialized in its ground state, and then gradually moves the simple system to the target complex system.
Quantum adiabatic theorem [4]}, [5]}, [6]}, [7]} indicates that the system will likely to stay in the ground state during the gradual evolution, thus, under certain probability, we can find the solution of the original optimization problem by measuring the system at its final state.
That is, quantum annealing replaces thermal fluctuations in SA by quantum tunneling to keep the system close to its instantaneous ground state during the evolution.
It is similar to a quasi-equilibrium state being maintained during the evolution of SA.
See [8]}, [9]}, [10]}, [3]} for more details.
Both the classical and quantum annealing methods are powerful tools for solving hard optimization problems, whether achieved by physical devices or simulation methods.
The physical scheme either employs a natural system or builds a device to engineer a physical system where the ground state of the system represents the sought-after solution of an optimization problem [12]}.
The simulation approach applies “escape” rules in computer simulations to prevent the system from getting trapped in local minima given a cost function, and eventually, reach the global minimum with some probability
[13]}, [14]}.
In both situations, the system can probabilistically explore its the huge configuration space, and finally freeze in the global minimum with certain probability.
Through sufficient repeated attempts, we can find the global minimum and solve the optimization problem.
