COMBINATORIAL OPTIMIZATION WITH D-WAVE OCEAN SDK

Solving Sudoku Puzzles with D-Wave Quantum Annealing

Fill the Grid Without Breaking the Rules!

Backstory

In 2017, I wrote about Sudoku Solver by Peter Norvig, a concise and elegant Python program that systematically solves Sudoku puzzles. You can read the original article here.

So, there is no need to bring up quantum annealing to solve Sudoku puzzles. Just for fun, we will solve Sudoku puzzles using it. To achieve this, we use the following steps:

1. Formulate Sudoku as a constraint satisfaction problem (CSP).
2. Create a QUBO (Quadratic Unconstrained Binary Optimization) model.
3. Write an optimization code with D-Wave’s Ocean SDK.
4. Execute the code with a local sampler and D-Wave Leap’s QPU.

As in the knapsack problem article, we’ll compare approaches like CQM and BQM.

We’ll see that using the QPU directly presents challenges with embedding dense constraints but offers valuable insights into the current capabilities of quantum annealing hardware. Furthermore, hybrid solvers like the KerberosSampler complement this by combining classical and quantum resources, making it…