# A Quantum-Inspired Algorithm for Solving Sudoku Puzzles and the MaxCut Problem

arXiv: https://arxiv.org/abs/2510.19835 · HTML: https://mlsanity.com/paper/2510.19835/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 51 references that are in the map.
- First posted on arXiv 10 Oct 2025.

## Builds on (most cited first, 5 of 5)

- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Challenges and Opportunities in Quantum Optimization](https://mlsanity.com/paper/2312.02279/) (2023)
- [Dynamic Portfolio Optimization with Real Datasets Using Quantum Processors and Quantum-Inspired Tensor Networks](https://mlsanity.com/paper/2007.00017/) (2020)
- [Quantum-Inspired Machine Learning: a Survey](https://mlsanity.com/paper/2308.11269/) (2023)
- [A quantum-inspired tensor network method for constrained combinatorial optimization problems](https://mlsanity.com/paper/2203.15246/) (2022)

## Abstract (arXiv)

We propose and evaluate a quantum-inspired algorithm for solving Quadratic Unconstrained Binary Optimization (QUBO) problems, which are mathematically equivalent to finding ground states of Ising spin-glass Hamiltonians. The algorithm employs Matrix Product States (MPS) to compactly represent large superpositions of spin configurations and utilizes a discrete driving schedule to guide the MPS toward the ground state. At each step, a driver Hamiltonian -- incorporating a transverse magnetic field -- is combined with the problem Hamiltonian to enable spin flips and facilitate quantum tunneling. The MPS is updated using the standard Density Matrix Renormalization Group (DMRG) method, which iteratively minimizes the system's energy via multiple sweeps across the spin chain. Despite its heuristic nature, the algorithm reliably identifies global minima, not merely near-optimal solutions, across diverse QUBO instances. We first demonstrate its effectiveness on intermediate-level Sudoku puzzles from publicly available sources, involving over 200 Ising spins with long-range couplings dictated by constraint satisfaction. We then apply the algorithm to MaxCut problems from the Biq Mac library, successfully solving instances with up to 251 nodes and 3,265 edges. We discuss the advantages of this quantum-inspired approach, including its scalability, generalizability, and suitability for industrial-scale QUBO applications.