Quantum Sudoku Solver: A Quantum Annealing Approach for 2D and 3D Mega Sudoku Puzzles
Wednesday, June 1, 2022 1:12 PM to 1:16 PM · 4 min. (Europe/Berlin)
Hall D - 2nd Floor
Quantum Program Development and Optimization
Information
I have developed a quantum sudoku solver that can solve both 2D and 3D sudoku puzzles using the programming language of python along with D-Wave’s Ocean SDK. This was implemented in the remaining 3 weeks of my Quantum Computing course.
Traditionally, solving Sudoku is NP-complete by classical solvers, but a quantum approach may have the ability to offer some improvements over classical approaches by using a new method of computation. For this project, I specifically focused on applying the quantum method known as quantum annealing, a branch of quantum computing in which a quantum system attempts to solve a BQM (Binary Quantum Machine) by finding the lowest energy state. With quantum annealing, I was able to develop my 2D and 3D Sudoku solvers.
My approach to implementing the quantum Sudoku solver involved formulating Quadratic Unconstrained Binary Optimization (QUBO) equations for both 2-dimensional and 3-dimensional Sudoku puzzles and using the equations to write a program that would generate QUBO matrices based on arbitrary Sudoku puzzles. The QUBO matrix would then be converted into a BQM to be inputted into the sampler to obtain a solution. As an additional feature, I utilized the matplotlib tool to generate plots of solutions to assist with the visualization of the results.
Contributors:
Traditionally, solving Sudoku is NP-complete by classical solvers, but a quantum approach may have the ability to offer some improvements over classical approaches by using a new method of computation. For this project, I specifically focused on applying the quantum method known as quantum annealing, a branch of quantum computing in which a quantum system attempts to solve a BQM (Binary Quantum Machine) by finding the lowest energy state. With quantum annealing, I was able to develop my 2D and 3D Sudoku solvers.
My approach to implementing the quantum Sudoku solver involved formulating Quadratic Unconstrained Binary Optimization (QUBO) equations for both 2-dimensional and 3-dimensional Sudoku puzzles and using the equations to write a program that would generate QUBO matrices based on arbitrary Sudoku puzzles. The QUBO matrix would then be converted into a BQM to be inputted into the sampler to obtain a solution. As an additional feature, I utilized the matplotlib tool to generate plots of solutions to assist with the visualization of the results.
Contributors:
- Liwen Shih (U of Houston - Clear Lake)
- Mario Vega (U of Houston - Clear Lake)
Format
On-site
