.  Home  .  Lehre  .  Studentische Arbeiten  .  Bachelorarbeiten  .  ba-quantensudoku


Partitioning and Encoding strategies for solving Sudoku as a combinatorial problem with QAOA

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.

Überblick der Aufgaben:

  1. Literature search regarding QAOA, Encoding Strategies, Sudoku on Quantum Systems
  2. Literature search about partitioning of graph coloring problems
  3. Comparison of own ideas to the results of the literature search
  4. Comparison of different encoding strategies (average case, best case, worst case)
  5. Getting a deep understanding of the QAOA principles, implement it with different approaches
  6. Partitioning of larger problems to be solved in parts and be reassembled
  7. Implement the project in Python 3

Prof. Dr. D. Kranzlmüller

Dauer der Bachelor-Arbeit: 3 Monate

Anzahl Bearbeiter: 1