Solving Constraint Satisfaction Problems with Quantum Computing

Constraint Satisfaction Problems, or CSPs for short, are mathematical problems whose solution is a state satifying a number of constraints or limitations. Two very popular examples would be Sudokus or Kakuros. In Kakuros, you are given an empty grid which must be filled with non-repeating numbers such that each column and row add up to a specific amount. As a simple example, consider the following Kakuro:

In each green cell, a number below the diagonal refers to the required total sum of the column, while a number above the diagonal refers to the row. By trial and error we can find a possible solution (but note that there may be others):

Solving Kakuros in known to be an NP-complete problem.

We can formulate the problem as a set of contraints that need to be satisfied. For example, for the kakuro presented above, let us name the numbers in the white cells as {x1, x2, ..., x7} (from left to right and top to bottom). Then, our constraints on the first cell are:

  • x1 != x2 
  • x1 != x3
  • x1 + x2 = 3
  • x1 + x3 = 3

What does this have to do with Quantum Computing?

Given that this is an NP-complete problem, and quantum computing offers theoretical speed-ups on some other problems of this kind, it is natural to wonder if there exists a more efficient quantum algorithm capable of solving kakuros. In fact, research shows that quantum computers could provide an advantage when solving CSPs. However, the proposed algorithms are often limited to applications of the Grover's search algorithm.

If you choose to work on a thesis on this topic you will be applying quantum arithmetic operations and quantum autoencoders as a way to enforce the constraints.


If you have some experience with quantum computing (e.g. have taken the Introduction to Quantum Computing course) and find this topic interesting, please contact Irene Lopez Gutierrez.