LfD Logo

Assessing QAOA and Warm-Starting QAOA for Sudoku as a Graph Coloring Problem and Various Encodings Thereof

The game of Sudoku is very interesting, as it is a specific representative within the group of graph coloring problems. The general problem is about finding a valid combination of color arrangements such that two adjacent nodes do not share the same color. Graph coloring is one of the several well-known families of problems to be NP-complete, which are known to be hard to solve. But with the recent rise of quantum computing and their suited ability to solve combinatorial problems, new algorithms were discovered, which could approximate the optimal solution very time efficiently.

This work aims to solve the Sudoku problem with one of those algorithms, the Quantum Approximate Optimization Algorithm (QAOA) from 2014. For prerequisites, a fitting encoding strategy has to be found, which transmutes the Sudoku into a executable QAOA circuit, while trying to minimize the amount of used qubits. Different conversion strategies for deriving a workable binary optimization problem from the Sudoku problem are presented and compared by the amount of qubits needed. This includes representations as a quadratic unconstrained binary optimization problem (QUBO), despite the not necessary quadratic limitation for QAOA. Besides the standard QAOA, two variants of a warm-starting QAOA (WS-QAOA) version are implemented and assessed on a 4 × 4 Sudoku using a single binary encoding strategy.

The results show a strong stability of standard QAOA, while both WS-QAOA versions have a high variance in almost all assessed categories. The high deviation from the median is present in the repetition of each algorithm, as well as in the set of measured states within each WS-QAOA repetition. The most probable state to be measured in WS-QAOA has a much higher probability than in standard QAOA, making WS-QAOA a fitting candidate for solving graph coloring problems, where only one valid solution is oftentimes enough to satisfy the problem. Largest drawback of WS-QAOA seems to be the speed of approximation until a certain tolerance threshold is reached.