Chapter 2: What is the Cost Function?
Section 1: Relationship between Annealing Machines and Cost Functions
To solve optimization problems, events must be expressed numerically. Similar to the way that the game world visualizes the strength of a character in terms of level or hit points, you need to formulate the problems to be solved as an equation by quantifying the state of the problem. In a complex problem, we often make a "model" which is an abstract simplified expression of the problem. An annealing machine is a system which assumes the optimal solution is in the lowest total energy of the Ising model expressed in the equation.
When studying variables in school, you may remember to apply the world to $x$ or $y$ and check how things change within the law at our desks. Annealing machines and ordinary computers are the same: repeating calculations under certain rules. Still, in the case of an annealing machine, you have to think of the problem you want to solve as "something with energy," which requires a bit of a shift of mind. This "something" is the Ising model (See Annealing Machine and Ising Model). It is not easy to imagine how this model works in detail. However, you may imagine that there are high or low energy cases.
For example, it might look like this.
But we are not allowed to draw these appropriately squishy graphs. The formula determines the shape of the graph.
Recall what you learned in school math.
Graph of $y=x^2$, Graph of $y=-x^2$
Thus, once the formula is determined, the shape of the graph is determined. However, there is no such thing as the only true graph because formulation can vary. We are looking for a single optimal solution (or something close to it = approximate solution), so it does not matter if other parts of the equation are slightly different, as long as such a solution can be derived. The optimal solution is the combination of variables that gives the energy at the top of the graph.
For example, let's assume the Ising model energy we want is $H=3 \times s_1s_2 - 2 \times s_3s_4$, where the $s_n$ is a spin that takes $+1$ or $-1$. The solution of the model is a combination of $s_1, s_2, s_3, s_4$ gives the lowest $H$. when such $H$ is lowest. The combination of spin values of the optimal solution is one of the following ones;
$$ (+1,-1,+1,+1) \\ (-1,+1,+1,+1) \\ (+1,-1,-1,-1) \\ (-1,+1,+1,+1) $$
Any of these combinations will give $H=-6$.
As shown before, once the cost function is determined, the optimal combination will be given in somewhere within the value of the range given by the function. There is not only one way to express an issue into an optimization problem, so the work of formulating the issue will be require some creativity. The only way to get used to the process to actually practice it. The cost function should be designed so that the top of its vertices represent the optimal value. Still, it is up to the person formulating the problem to decide whether the energy that gives the optimal solution is the "lowest" or the "highest" in the graph. It is also up to the person's creativity formulating the equation to determine the slopes between the vertices and how many peaks there are.
In addition, there is one more assumption you should be aware of regarding this method of solving optimization problems with energy functions. That is, it is not a method for "obtaining the single most correct solution." Combinatorial optimization problems are classified as very difficult problems to solve. Solving problems of this class requires either years of work on a conventional computer (at the expense of time) or a method called approximate solution (at the expense of accuracy).
Using annealing machine to obtain the optimal solution is one of the latter methods. So it does not guarantee to obtain the single most correct solution. For this reason, it is not suitable for tasks that require rigor, such as cryptography technology, but it is suitable for tasks where a "pretty good solution" is sufficient to achieve results.
