Influence of annealing schemes on the success rate of Ising machines
Toon Sevenants1, Guy Van der Sande1, Guy Verschaffelt1
1

Applied Physics Research Group (APHY), Vrije Universiteit Brussel, Belgium

Summary. An Ising machine is a radical new computing platform that has the potential to solve
hard optimization problems more efficiently than traditional digital computers. Unfortunately, forspecific tasks, the relatively low success rate of finding the optimal solution remains an issue. Our
research investigates novel annealing schemes that could drastically improve the success rate ofthese highly anticipated Ising machines.

Combinatorial optimization problems play an important role in different industries of our society. They
can be found in logistics, drug development, electronic circuit-design (VLSI) and even in finance. However,traditional computing platforms require large amounts of time and resources to find the solution to such
optimization problems, because the amount of possible solutions increases very strongly with the numberof variables. To solve these optimization problems more efficiently, a renewed interest in novel computing
platforms has emerged [1]. Our research group focuses on one of the most promising platforms, called theIsing machine (IM) [2].
An IM is a natural computing system that uses a network of analog artificial spins to emulate the Ising
1model of which the energy is given by 𝐻𝐼𝑠𝑖𝑛𝑔 = − 2 ∑𝑖𝑗 𝐽𝑖𝑗 𝜎(𝑥𝑖 )𝜎(𝑥𝑗 ), where 𝜎(𝑥𝑖 ) represents the sign ofthe i-th spin amplitude 𝑥𝑖 and 𝐽𝑖𝑗 the matrix that describes how the spins are interconnected. An optimization
problem can then be encoded through this interconnection matrix and driven by their coupling, the spin
network will tend to evolve towards its lowest energy state. This energy state (i.e. the ground state) thencorresponds to the optimal solution of the encoded problem [1]. The artificial spin-network of an IM canbe implemented in numerous ways, but all of them consist of three essential buildings blocks: a nonlinearity, a spin coupling mechanism and a feedback mechanism. This feedback signal contains twocontributions: the self-feedback and the mutual coupling feedback. To regulate their respective strengths,
we use two parameters, which we call here a and b. Our group has proposed and build an opto-electronic
IM (OE-IM) that is made out of opto-electronic oscillators (OEO) [2]. The optical part of the OEO includes
a Mach-Zehnder modulator (MZM) that takes up the role of non-linear system. In electronic part, an FPGA
is used for calculating the spin coupling signal which is then electrically fed back to the MZM. Theevolution of a spin amplitudes 𝑥𝑖 is described by the following equation:
𝑥̇ 𝑖 = cos2( 𝑎𝑥𝑖 + 𝑏 ∑ 𝐽𝑖𝑗 𝑥𝑗 + 𝛾 − 𝜋/4) − 1/2𝑗where 𝜋/4 and 1/2 are two bias terms, a and b are the previously discussed feedback strengths, 𝐽𝑖𝑗 represents
again the interconnection matrix and 𝛾 the gaussian white noise.
Although IMs are promising, they still face a number of challenges. One difficulty is that the successrate of finding the optimal solution, which depends on the value of both a and b, can be relatively small [3].
Physically this means that the IM has a high probability of getting stuck in a local minimum, of which thespin configuration does not corresponds to the desired optimal solution. As a consequence, numerous runsare required in order to have at least one instance that reaches the ground-state. This strongly increases theaverage time-to-solution.
To tackle this problem, annealing schemes are being investigated as a tool to navigate around these
local minima and increase the overall success rate of IMs [4]. These annealing schemes gradually change
at least one feedback parameter of the system towards a certain target value. Annealing schemes typicallyoperate by scanning the feedback strengths through the operating threshold of the IM, which depends onthe value of both a and b, as there are less excited states near this region in which the IM could get stuck.
However, there are various methods to do this. In this contribution, we use numerical simulations to study
two of these schemes, namely linear annealing (LA) and linear adiabatic annealing (LAA).
In a LA scheme, at least one of the two feedback parameters increases linearly with time from a startvalue towards a target value. Although we keep the noise strength fixed in our simulation, its importancein the dynamics of the system will decrease if we drive the IM further away from the operating thresholdby increasing a and/or b. Our simulations indicates that when such annealing is performed slow enough, it
is possible to significantly increase the maximum success rate of some specific benchmark problems.
However, as mentioned, annealing will increase the time that is needed to perform a single run, meaning
there is a trade off between finding the ground state over several runs without annealing, or doing one longrun with annealing. At the conference, we will discuss what the optimal ratio is between the annealing time
and the success rate.
In the case of LAA, we change the Hamiltonian of a system over time instead of the value of thefeedback parameters. At the start, the system is initialized in the (known) ground state of an easy-to-solve
problem. Next, the system’s Hamiltonian is transformed linearly over time, by changing the interconnection
matrix elements 𝐽𝑖𝑗 , towards the Hamiltonian of the actual problem to be solved. This evolution isschematically illustrated in Fig.1. The idea behind this technique is that when the system is initialized in
the ground state of the easy Hamiltonian, the system will remain in the ground state of an interpolated
Hamiltonian if the transition happens slow enough. Eventually, the system should end up in the groundstate of the target Hamiltonian. The principle of adiabatic evolution has already been proven in quantum
mechanics but not in classical mechanics, which is the regime in which our IM operates. Therefore, weinvestigate in this contribution the computational performance of this scheme using the IM described above.

Figure 1. This figure shows a simplistic illustration of the concept of LAA. The system starts at theground state configuration at t = 0 of a simple problem of which the ground state is known. As timeincreases, the energy landscape changes towards a complex landscape that contains more local minima.
We investigate if, and up to which extent, these types of annealing can be beneficial in classical IM byapplying it to several benchmark tasks (e.g., biqmac-library, g-set). We quantify the performance based on
the success rate of finding the optimal solution and the average time-to-solution. The code behind thesenumerical simulations is based on the dynamical equation of our OE-IM that was discussed above.
To summarize, our research uses numerical simulations to investigates how LA and LLA schemes
near the operation threshold of an OE-IM could improve the success rate and time-to-solution of different
benchmark problems.

References[1] N. Mohseni, P. L. McMahon, and T. Byrnes, “Ising machines as hardware solvers of combinatorial optimization
problems,” ArXiv, 2022
[2] F. Böhm, G. Verschaffelt, and G. Van der Sande, “A poor man’s coherent Ising machine based on optoelectronic feedback systems for solving optimization problems,” Nat. Comm., 2019[3] F. Böhm, et al., “Order-of-magnitude differences in computational performance of analog Ising machines
induced by the choice of nonlinearity,” Comm. Phys., 2021
[4] D. Pierangeli, G. Marcucci, and C. Conti, “Adiabatic evolution on a spatial-photonic Ising machine,” Optic.,
2020