Previous talks at the SCCS Colloquium

Arda Nacar: Quantum Algorithms for Solving Constraint Satisfaction Problems

SCCS Colloquium |


To this day quantum computing has tackled ways to accelerate various problem categories, including constraint satisfaction problems (CSP). Previous work has proposed ways to achieve quantum speed-up for problems such as boolean satisfiability (SAT) and graph coloring. These problems consist of boolean constraints and constraints of type a != b. In this presentation we will discuss the use of different quantum algorithms that fall under the category of quantum amplitude amplification to solve CSPs with sum constraints of the form a + b = c. Furthermore, a concrete example for the usage of Grover's algorithm will be presented for the case of Kakuro, a crossword-like puzzle, where the consecutive numbers in each row and column have to add up to a certain number. Lastly, the time and space complexity of the proposed implementation will be analyzed and compared to other classical Kakuro solvers to evaluate possible use cases of Grover's algorithm for sum-constrained CSPs in general.

Bachelor's thesis presentation. Arda is advised by Irene Lopez Gutierrez.