Quantum Information & Computation
Volume 25, Issue 5
RESEARCH ARTICLE Open access

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

Max B. Zhao, Fei Li

Author affiliations
  • Max B. Zhao1
  • Fei Li2
  1. Thomas Jefferson High School for Science and Technology, Alexandria, USA
  2. Department of Computer Science, George Mason University, Fairfax, USA

pp. 397-420 · 10.2478/qic-2025-0023

Read PDF View on Reference Global
On this page

Abstract

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.
Open accessCC BY-NC-ND 4.0

Keywords

  • Quantum-Inspired Algorithm
  • Quadratic Unconstrained Binary Optimization
  • Matrix Product States
  • Density Matrix Renormalization Group

Suggested citation

Max B. Zhao, Fei Li (2025). A Quantum-Inspired Algorithm for Solving Sudoku Puzzles and the MaxCut Problem †. Quantum Information & Computation, 25(5), 397-420. https://doi.org/10.2478/qic-2025-0023

Download BibTeX

References (57)

  1. C.H. Papadimitriou, K. Steiglitz (1998). Combinatorial Optimization: Algorithms and Complexity. Dover Publications.Google Scholar
  2. B.H. Korte, J. Vygen, B. Korte, and J. Vygen (2011). Combinatorial Optimization, Volume 1. Springer.DOI: 10.1007/978-3-642-24488-9_1Google Scholar
  3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (2022). Introduction to Algorithms. MIT Press.Google Scholar
  4. F. Glover, G. Kochenberger, R. Hennig, and Y. Du (2022). “Quantum bridge analytics I: a tutorial on formulating and using QUBO models.” Annals of Operations Research, 314: 1, 141–183.DOI: 10.1007/s10479-022-04634-2Google Scholar
  5. A. P. Punnen, ed. (2022). The Quadratic Unconstrained Binary Optimization Problem. Springer Cham.DOI: 10.1007/978-3-031-04520-2Google Scholar
  6. F. Barahona (1982). “On the computational complexity of Ising spin glass models.” Journal of Physics A: Mathematical and General, 15: 10, 3241.DOI: 10.1088/0305-4470/15/10/028Google Scholar
  7. A. Abbas, A. Ambainis, B. Augustino, A. Bärtschi, H. Buhrman, C. Coffrin, G. Cortiana, V. Dunjko, D. J. Egger, B. G. Elmegreen, N. Franco, F. Fratini, B. Fuller, J. Gacon, C. Gonciulea, S. Gribling, S. Gupta, S. Hadfield, R. Heese, G.-h. Kircher, T. Kleinert, T. Koch, G. Korpas, S. Lenk, J. Marecek, V. Markov, G. Mazzola, S. Mensa, N. Mohseni, G. Nannicini, C. O’Meara, E. P. Tapia, S. Pokutta, M. Proissl, P. Rebentrost, E. Sahin, B. C. B. Symons, S. Tornow, V. Valls, S. Woerner, M. L. Wolf-Bauwens, J. Yard, S. Yarkoni, D. Zechiel, S. Zhuk, and C. Zoufal. (2024) “Challenges and opportunities in quantum optimization.” Nature Reviews Physics, 6: 12, 718–735.DOI: 10.1038/s42254-024-00770-9Google Scholar
  8. A. Lucas (2014). “Ising formulations of many NP problems.” Frontiers in Physics, 2.DOI: 10.3389/fphy.2014.00005Google Scholar
  9. N. Mohseni, P. L. McMahon, and T. Byrnes (2022). “Ising machines as hardware solvers of combinatorial optimization problems.” Nature Reviews Physics, 4: 6, 363–379.DOI: 10.1038/s42254-022-00440-8Google Scholar
  10. A. Das and B. K. Chakrabarti (2008). “Colloquium: Quantum annealing and analog quantum computation.” Reviews of Modern Physics 80, 1061–1081.DOI: 10.1103/RevModPhys.80.1061Google Scholar
  11. A. B. Finnila, M. A Gomez, C Sebenik, C. Stenson, J. D. Doll. (1994). “Quantum annealing: A new method for minimizing multidimensional functions.” Chemical Physics Letters, 219:5-6, 343–348.DOI: 10.1016/0009-2614(94)00117-0Google Scholar
  12. T. Kadowaki and H. Nishimori (1998). “Quantum annealing in the transverse Ising model.” Physical Review E, 58, 5355–5363.DOI: 10.1103/PhysRevE.58.5355Google Scholar
  13. E. Farhi, J. Goldstone, and S. Gutmann. “A quantum approximate optimization algorithm.” arXiv preprint arXiv:1411.4028, 2014.Google Scholar
  14. S. Hadfield, Z. Wang, B. O’gorman, E. G. Rieffel, D. Venturelli, and R. Biswas. (2019). “From the quantum approximate optimization algorithm to a quantum alternating operator ansatz.” Algorithms, 12: 2, 34.DOI: 10.3390/a12020034Google Scholar
  15. The D-wave Advantage system: An overview. Available at: https://www.dwavequantum.com/media/s3qbjp3s/14-1049a-a_the_d-wave_advantage_system_an_overview.pdf (Accessed on 1 September 2024).Google Scholar
  16. K. Blekos, D. Brand, A. Ceschini, C.-H. Chou, R.-H. Li, K. Pandya, and A. Summer (2024). “A review on quantum approximate optimization algorithm and its variants.” Physics Reports, 1068, 1–66.DOI: 10.1016/j.physrep.2024.03.002Google Scholar
  17. G. Pagano, A. Bapat, P. Becker, K. S. Collins, A. De, P. W. Hess, H. B. Kaplan, A. Kyprianidis, W. L. Tan, C. Baldwin, et al. (2020). “Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator.” Proceedings of the National Academy of Sciences, 117: 41, 25396–25401.DOI: 10.1073/pnas.2006373117Google Scholar
  18. Y. Du, H. Wang, R. Hennig, A. Hulandageri, G. Kochenberger, and F. Glover. (2025). “New advances for quantum-inspired optimization.” International Transactions in Operational Research, 32: 1, 6–17.DOI: 10.1111/itor.13420Google Scholar
  19. T. Hao, X. Huang, C. Jia, and C. Peng. (2022). “A quantum-inspired tensor network algorithm for constrained combinatorial optimization problems.” Frontiers in Physics, 10.DOI: 10.3389/fphy.2022.906590Google Scholar
  20. L. Huynh, J. Hong, A. Mian, H. Suzuki, Y. Wu, and S. Camtepe. (2023). “Quantum-inspired ma-chine learning: a survey.” arXiv preprint arXiv:2308.11269.Google Scholar
  21. S. Mugel, C. Kuchkovsky, E. Sánchez, S. Fernández-Lorenzo, J. Luis-Hita, E. Lizaso, and R. Orús. (2022). “Dynamic portfolio optimization with real datasets using quantum processors and quantum-inspired tensor networks.” Physics Review Research, 4, 013006.DOI: 10.1103/PhysRevResearch.4.013006Google Scholar
  22. S. Mücke. (2024). “A simple QUBO formulation of sudoku.” In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’24 Companion, pp. 1958–1962, New York, NY. Association for Computing Machinery.DOI: 10.1145/3638530.3664106Google Scholar
  23. F. Verstraete, V. Murg, and J. I. Cirac. (2008). “Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems.” Advances in Physics, 57: 2, 143–224.DOI: 10.1080/14789940801912366Google Scholar
  24. U. Schollwöck (2005). “The density-matrix renormalization group.” Reviews of Modern Physics, 77, 259–315.DOI: 10.1103/RevModPhys.77.259Google Scholar
  25. S. R. White. (1992). “Density matrix formulation for quantum renormalization groups.” Physical Review Letters, 69, 2863–2866.DOI: 10.1103/PhysRevLett.69.2863Google Scholar
  26. R. Orús. (2014). “A practical introduction to tensor networks: Matrix product states and projected entangled pair states.” Annals of Physics, 349, 117–158.DOI: 10.1016/j.aop.2014.06.013Google Scholar
  27. T. Yato and T. Seta. (2003). “Complexity and completeness of finding another solution and its application to puzzles.” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 86: 5, 1052–1060.Google Scholar
  28. N. Ueda and T. Nagao. (1996). “NP-completeness results for NONOGRAM via parsimonious reductions.” Technical Report TR96-0008, Department of Computer Science, Tokyo Institute of Technology.Google Scholar
  29. D. Sherrington and S. Kirkpatrick. (1975). “Solvable model of a spin-glass.” Physical Review Letters, 35, 17921796.DOI: 10.1103/PhysRevLett.35.1792Google Scholar
  30. J. Vannimenus and G Toulouse. (1977). “Theory of the frustration effect. II. Ising spins on a square lattice.” Journal of Physics C: Solid State Physics, 10: 18, L537.DOI: 10.1088/0022-3719/10/18/008Google Scholar
  31. S.Patra, S. Singh, and R. Orús. (2025). “Projected entangled pair states with flexible geometry.” Physical Review Research, 7, L012002.DOI: 10.1103/PhysRevResearch.7.L012002Google Scholar
  32. M. Fishman, S. R. White, and E. M. Stoudenmire. (2022). “The ITensor Software Library for tensor network calculations.” SciPost Physics Codebases, 4.DOI: 10.21468/SciPostPhysCodeb.4Google Scholar
  33. R. Martoňák, G. E. Santoro, and E. Tosatti. (2002). “Quantum annealing by the path-integral Monte Carlo method: The two-dimensional random Ising model.” Physical Review B, 66, 094203.DOI: 10.1103/PhysRevB.66.094203Google Scholar
  34. G. E. Santoro, R. Martonak, E. Tosatti, and R. Car. (2002). “Theory of quantum annealing of an Ising spin glass.” Science, 295: 5564, 2427–2430.DOI: 10.1126/science.1068774Google Scholar
  35. Available at: https://www.nytimes.com/puzzles/sudoku (Accessed on 1 September 2024).Google Scholar
  36. Available at: https://nytsudoku.net (Accessed on 1 September 2024).Google Scholar
  37. R. M. Karp. (1972). Reducibility among Combinatorial Problems, pp. 85–103. Boston, MA: Springer US.DOI: 10.1007/978-1-4684-2001-2_9Google Scholar
  38. F. Barahona, M. Grötschel, M. Jünger, and G. Reinelt. (1988). “An application of combinatorial optimization to statistical physics and circuit layout design.” Operations Research, 36: 3, 493–513.DOI: 10.1287/opre.36.3.493Google Scholar
  39. Available at: https://biqmac.aau.at/(Accessed on 1 September 2024).Google Scholar
  40. Available at: http://bqp.cs.uni-bonn.de/library/html/instances.html (Accessed on 1 September 2024).Google Scholar
  41. Available at: https://people.brunel.ac.uk/ mastjjb/jeb/info.html (Accessed on 1 September 2024).Google Scholar
  42. Available at: https://web.stanford.edu/ yyye/yyye/Gset/(Accessed on 1 September 2024).Google Scholar
  43. Y. Kim, A. Eddins, S. Anand, K. X. Wei, E. van den Berg, S. Rosenblatt, H. Nayfeh, Y. Wu, M. Zaletel, K. Temme, and A. Kandala. (2023). “Evidence for the utility of quantum computing before fault tolerance.” Nature, 618: 7965, 500–505.DOI: 10.1038/s41586-023-06096-3Google Scholar
  44. J. Tindall, M. Fishman, E. M. Stoudenmire, and D. Sels. (2024). “Efficient tensor network simulation of IBM’s Eagle kicked Ising experiment.” PRX Quantum, 5, 010308.DOI: 10.1103/PRXQuantum.5.010308Google Scholar
  45. M. Streif and M. Leib. (2020). “Training the quantum approximate optimization algorithm without access to a quantum processing unit.” Quantum Science and Technology, 5: 3, 034008.DOI: 10.1088/2058-9565/ab8c2bGoogle Scholar
  46. I. A. Luchnikov, E. S. Tiunov, T. Haug, and L. Aolita. (2024). “Large-scale quantum annealing simulation with tensor networks and belief propagation.” arXiv preprint arXiv:2409.12240.Google Scholar
  47. A. Bou-Comas, M. P3odzieñ, L. Tagliacozzo, and J. J. García-Ripoll (2025). “Quantics Tensor Train for solving Gross-Pitaevskii equation.” arXiv preprint arXiv:2507.03134.Google Scholar
  48. Q.-C. Chen, I.-K. Liu, J.-W. Li, and C.-M. Chung. (2025). “Solving the Gross-Pitaevskii equation with quantic tensor trains: ground states and nonlinear dynamics.” arXiv preprint arXiv:2507.04279.Google Scholar
  49. R. J. J. Connor, C. W. Duncan, and A. J. Daley. (2025). “Tensor network methods for the Gross-Pitaevskii equation on fine grids.” arXiv preprint arXiv:2507.01149.DOI: 10.1088/1367-2630/ae2b05Google Scholar
  50. M. Niedermeier, A. Moulinas, T. Louvet, J. L. Lado, and X. Waintal. (2025). “Solving the Gross-Pitaevskii equation on multiple different scales using the quantics tensor train representation.” arXiv preprint arXiv:2507.04262.DOI: 10.1103/zwn1-f981Google Scholar
  51. G. M. Crosswhite and D. Bacon (2008). “Finite automata for caching in matrix product algorithms.” Physical Review A, 78, 012356.DOI: 10.1103/PhysRevA.78.012356Google Scholar
  52. I. Arad, A. Kitaev, Z. Landau, and U. Vazirani. (2013). “An area law and sub-exponential algorithm for 1D systems.” arXiv preprint arXiv: 1301.1162.Google Scholar
  53. M. B. Hastings. (2007). “An area law for one-dimensional quantum systems.” Journal of Statistical Mechanics: Theory and Experiment 2007: 08, P08024.DOI: 10.1088/1742-5468/2007/08/P08024Google Scholar
  54. A. Kay. (2007). “Quantum-Merlin-Arthur-complete translationally invariant Hamiltonian problem and the complexity of finding ground-state energies in physical systems.” Physical Review A, 76, 030307.DOI: 10.1103/PhysRevA.76.030307Google Scholar
  55. N. Schuch, M.M. Wolf, F. Verstraete, and J. I. Cirac. (2008). “Entropy scaling and simulability by matrix product states.” Physical Review Letters, 100, 030504.DOI: 10.1103/PhysRevLett.100.030504Google Scholar
  56. F. Verstraete and J. I. Cirac. (2006). “Matrix product states represent ground states faithfully.” Physical Review B, 73, 094423.DOI: 10.1103/PhysRevB.73.094423Google Scholar
  57. T. Kuwahara and K. Saito (2020). ”Area law of noncritical ground states in 1D long-range interacting systems.” Nature Communications, 11: 1, 4478.DOI: 10.1038/s41467-020-18055-xGoogle Scholar