Davide Gessa has demonstrated how to use Qlasskit, an open-source Python library, to create a quantum circuit that can search for Sudoku puzzle solutions. Qlasskit, supported by a Unitary Fund microgrant, allows standard Python code to be translated into invertible quantum circuits. However, due to the limitations of current quantum computers, only a 2×2 Sudoku puzzle can be solved, not a standard 9×9 one. The solution is found using the Grover search algorithm and the Qiskit framework. The resources required for more complex puzzles would scale exponentially.
Quantum Computing and Sudoku Puzzles
Davide Gessa, a developer and researcher, has demonstrated how to use Qlasskit, an open-source Python library, to create a quantum circuit capable of searching for Sudoku puzzle solutions. Qlasskit, which was developed with the support of a Unitary Fund microgrant, allows for the direct translation of standard Python code into invertible quantum circuits without any modification to the original code.
Quantum Circuits and Sudoku
Gessa’s demonstration involves using Qlasskit to write and execute a quantum circuit using only Python code, without any quantum-related primitives. However, due to the limitations of current quantum computers, the demonstration does not solve a full 9×9 Sudoku puzzle. Instead, it uses a 2×2 matrix as a toy example, where a valid solution is when every row and column do not contain repeated values (0 or 1). These values are encoded by xor-ing the values for each row and column.
Constraints and Quantum Algorithms
To seek a specific solution, Gessa adds a constraint: the [0][0] element must be True. After defining this oracle, he instantiates the Grover search algorithm, a quantum algorithm known for its ability to search unsorted databases with quadratic speedup over classical algorithms.
Quantum Simulation and Results
Gessa then uses a preferred framework and simulator for sampling the result. In this case, he uses qiskit with aer_simulator. The solution for this puzzle is the matrix [[True, False], [False, True]]. The results are visualized using matplotlib, a popular Python library for data visualization.
Scaling Up and Limitations
While the demonstration is successful with a 2×2 matrix, Gessa notes that creating a more realistic Sudoku game using numbers instead of booleans would require resources that scale exponentially. For instance, recreating the sudoku_check function with a 4×4 matrix would require more than 100 qubits, which is beyond current simulation capabilities. This highlights the challenges and potential of quantum computing in solving complex problems.
