Developing a Minor Embedding Algorithm for Oscillator based Ising Machines using Reinforcement Learning
Masterarbeit, Projektseminar, Bachelorarbeit
Oscillator based Ising Machines (OIMs) are a promising metaheuristic intended for solving NP-hard or NP-complete combinatorial optimization problems (e.g. the famous Traveling Salesman problem (TSP)). The advantage of an OIM compared to other approaches is speed and energy efficiency. Our OIM consists of a network of 1440 oscillators. In the context of ising machines an optimization problem can be reformulated in the ising model and therefore be represented as a graph. The vertices of the graph are mapped to the oscillators and the edgeweights of the graph determine the coupling strength between the oscillators. The system will then evolve toward a state of minimum energy. The phases of the oscillators in the energy minimum state constitute the solution.
However, to actually make use of an OIM one need to map the graph of the optimization problem to the oscillator network of the hardware. This process of embedding the graph of the optimization problem into our hardware topology is refered to as minor embedding. In general minor embedding is NP-complete.
