Today we will use a Quantum Annealer to solve our Sunday coffee-break Sudoku.
Even better: we will use the Sudoku game to benchmark the latest public accessible Quantum Annealer architecture. This way, we will know when the time has come to invest in this new technology.
But what is a Quantum Annealer?
I do not want to explain what several people already did, and can do better. So I will provide you with links to some great explanations at the bottom, and right now just state the baseline assumptions that we need:
How to formulate the goal of solving a Sudoku quiz?
A game of Sudoku can simply be stated as matrix containing numbers together with a simple set of rules.
Assume we have a 9x9 Sudoku grit, representing the board as a matrix would be done by constraining the matrix to have 9 rows and 9 columns and to contain only numbers from 1 to 9.
Then we could define the set of Sudoku rules as:
These are basically all the rules that we need. Pretty simple, eh?
If we now make sure that all these rules hold, while putting in numbers, we will end up having a valid Sudoku solution!
What are the (mathematical) constraints?
The problem of formulating constraints is tackled already for non-quantum optimization hardware (called digital-annealer) in a Top-Coder-Challenge Series, so we already handled the time-consuming cold start problem.
Before I show the constraints though, I want to introduce a small change in how we usually view the board. Because the mathematical formulations that the Quantum Annealer can solve are binary, we need to restrict the matrix, that represents our board, to be binary as well. We can achieve this by introducing a dimension for each of the numbers that a cell can have (9 in our case). Take a look at the picture below, for a better understanding.
Now let’s take a quick look at the constraints that we need:
This first constraint is a result of the dimensions for each possible number that we introduced right before. “cell” is a set that contains all the tuples of row,column combinations. Constraints 2–4 are just the Sudoku rules that we defined right in the beginning.
The 5th constraint is to ensure, that the algorithm does not start to change the numbers that are already given. This, of course, is obvious for a human, but a computer needs to know more explicitly what to do and to do not. The sum of the equation below iterates over a set, called “hint”, that contains all the cells that are initially given.
However, these constraints do not have the format that the Quantum Annealer can solve. Not yet. We need to reformulate the constraints as a QUBO (Quadratic Unconstrained Binary Optimization Problem), in order for the Quantum Annealer to solve it.
A QUBO basically expects a set of linear and quadratic terms, that represent the problem.
One way to reformulate our constraints as a QUBO, could be to introduce a so-called penalty term. With a penalty term we penalize “wrong” behavior so we kind of enforce the algorithm to give us the best solution.
Let us first see how those formulations look and talk a little bit about them afterwards.
Most of the above equations are using a squared distance of 1, since we have to make sure that each number can only be selected once per row and once per column. This way the best solution, which is the minimum, and in our case 0 (because of the square), is reached when the added up numbers under the sum are equal to 1. The logic of restating the constraints as a penalty function, with the optimal solution being the lowest possible value, applies to all of the terms.
If we ensemble all the QUBOs together, to get the final objective function for the Quantum Annealer, we end up with this equation:
This objective function leads to a final matrix that has a correct Sudoku game as an optimal solution. In the end, everything that the Quantum Annealer does is discrete optimization: Finding an optimal set of values (solution) in an unknown discrete problem space.
At this point we can solve a Sudoku board using our QUBO and the D-Wave Leap, which offers free access to a Quantum Annealer: the D-Wave Advantage with the new Pegasus-Architecture.
Limitations of the Quantum Annealer
It turns out that the Quantum Annealers hardware is yet to small to solve this whole 9x9 Sudoku QUBO. It was not possible for me to find an embedding for the QUBO to the D-Wave hardware graph, which is a necessary step before the sampling can happen.
However, with the reduced version of a 4x4 Sudoku I could find a valid embedding and so I will do the following performance measures with this smaller sized board.
Benchmarking the Quantum Annealer
Next to the time that is needed for a calculation, another widely used metric is called the success probability.
Since the Quantum Annealer works heuristically a valid result is not guaranteed. The success probability is just the ratio of correct solutions with respect to all calculations made.
Depending on the complexity of the problem the success probability can diminish quite rapidly, meaning that only once in a while the Quantum Annealer finds the optimal solution and ends up in (slightly) worse solutions the other times. To have something as a comparison, we use a Simulated Annealing algorithm on a classical computer. Simulated Annealing shares a lot of attributes with the Quantum Annealer.
Even with this experiment the biggest difference between the classical and quantum algorithm is already visible. While the Quantum Annealer needs roughly constant time (20µs for each sampling) to arrive at a solution, the time that the classical algorithm needs can vary. Furthermore, it seems that the Quantum Annealer is, in any case, faster than my home-computers CPU.
The success probability draws a different picture. While Simulated Annealing almost always finds the exact solution, the Quantum Annealer does it only in ~1% of the sampling runs. This is exactly the reason why we need sampling when calculating a solution — especially with quantum hardware.
Even though, 1% sounds like a pretty bad rate, it is more than sufficient if a sampling of, say 1000 runs, takes constant time in the magnitude of seconds — and one valid solution is usually all that we need.
Epilogue
The analysis of the Advantage™ Quantum Annealer shows that D-Wave made it pretty simple to submit problems to its system.
Even though the hardware is yet to small to solve big problems, there are already a lot of interesting applications, that can be investigated when the size of the problem is reduced. Furthermore, it might be possible to use a hybrid approach — that is: Split the problem into an easy calculable classical computing part and only outsource the harder computational part to the Quantum Annealer.
I hope my small experiment was able to show you the fun of investing a little bit of your time to dive into this very interesting intersection of computer science, math and physics.
You can find all the created code on GitHub
Useful resources:
[1] https://research.aimultiple.com/quantum-annealing/
[2] http://www.cs.cmu.edu/afs/cs.cmu.edu/project/learn-43/lib/photoz/.g/web/glossary/comb.html
[3] https://en.wikipedia.org/wiki/Quantum_annealing
[4] https://docs.ocean.dwavesys.com/en/stable/
[5] https://cloud.dwavesys.com/leap/
[6] https://www.youtube.com/watch?v=zvfkXjzzYOo
Originally published at https://towardsdatascience.com on March 4, 2021.