The game of sudoku is a very interesting and tangible kind of graph coloring problem. These problems can become very complex and expensive to calculate as the number of colors, nodes and edges scales. Quantum Computers are structurally well suited to solve combinatorial problems like graph coloring. Due to the limited number of available stable qubits on NISQ systems, an optimization is necessary regarding the encoding, the practicability of the executed circuit and the possibilities to divide problems in smaller subproblems.
This work aims at maximizing the size of Sudoku games that can be solved on today's Quantum systems. Different encoding approaches should get compared and a general circuit with the hybrid quantum algorithm QAOA should be implemented. Further there will be a discussion on how a problem that is too big for current hardware can be divided in smaller sub problems to be solved.
Aufgabensteller:
Prof. Dr. D. Kranzlmüller
Dauer der Bachelor-Arbeit: 3 Monate
Anzahl Bearbeiter: 1
Betreuer_innen: