Explorations in Quantum Computing

Many NP-hard puzzles, including Sudoku, grow intractable as problem size increases, making them excellent benchmarks for testing quantum and quantum-inspired algorithms. Sudoku, when formulated on an N² × N² grid, can be represented as a Quadratic Unconstrained Binary Optimization (QUBO) problem, solvable by methods such as quantum annealing or the Quantum Approximate Optimization Algorithm (QAOA). However, previous studies have shown that quantum annealing underperforms while QAOA is constrained to small-scale problems.

In this work, we propose a novel quantum-inspired approach that effectively solves both Sudoku puzzles and more general QUBO problems. We introduce a refined QUBO formulation of the Sudoku puzzle, where constraints and clues are treated uniformly as "gauge constraints." We then solve the resulting spin model using tensor network algorithms from quantum many-body physics, including the density matrix renormalization group (DMRG) and time-dependent variational principle (TDVP). Remarkably, these methods rapidly converge to the ground state, despite the presence of long-range interactions in the spin model. We evaluate the algorithm's performance across a broad set of Sudoku puzzles and discuss potential improvements in Hamiltonian design. The insights gained here could extend to solving a wide range of QUBO problems in industrial applications.