Quick design of feasible tensor networks for constrained combinatorial optimization

Hyakka Nakada; Kotaro Tanahashi; Shu Tanaka

doi:10.22331/q-2025-07-21-1799

Quick design of feasible tensor networks for constrained combinatorial optimization

Hyakka Nakada^1,2, Kotaro Tanahashi¹, and Shu Tanaka^2,3,4,5

¹Recruit Co., Ltd., Tokyo 100-6640, Japan
²Graduate School of Science and Technology, Keio University, Kanagawa 223-8522, Japan
³Department of Applied Physics and Physico-Informatics, Keio University, Kanagawa 223-8522, Japan
⁴Keio University Sustainable Quantum Artificial Intelligence Center (KSQAIC), Keio University, Tokyo 108-8345, Japan
⁵Human Biology-Microbiome-Quantum Research Center (WPI-Bio2Q), Keio University, Tokyo 108-8345, Japan

Published:	2025-07-21, volume 9, page 1799
Editor:	Yu Tong
Eprint:	arXiv:2409.01699v3
Doi:	https://doi.org/10.22331/q-2025-07-21-1799
Citation:	Quantum 9, 1799 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Quantum computers are expected to enable fast solving of large-scale combinatorial optimization problems. However, their limitations in fidelity and the number of qubits prevent them from handling real-world problems. Recently, a quantum-inspired solver using tensor networks has been proposed, which works on classical computers. Particularly, tensor networks have been applied to constrained combinatorial optimization problems for practical applications. By preparing a specific tensor network to sample states that satisfy constraints, feasible solutions can be searched for without the method of penalty functions. Previous studies have been based on profound physics, such as U(1) gauge schemes and high-dimensional lattice models. In this study, we devise to design feasible tensor networks using elementary mathematics without such a specific knowledge. One approach is to construct tensor networks with nilpotent-matrix manipulation. The second is to algebraically determine tensor parameters. We showed mathematically that such feasible tensor networks can be constructed to accommodate various types of constraints. For the principle verification, we numerically constructed a feasible tensor network for facility location problem, to find much faster construction than conventional methods. Then, by performing imaginary time evolution, feasible solutions were always obtained, ultimately leading to the optimal solution.

Featured image: Overview of proposed method. Feasible solutions can be systematically encoded by Tensor Networks (TNs) through nilpotent-matrix method and shared-matrix method. Then, imaginary time evolution is applied to TNs, to find the optimal solutions. Here, optimization methods are not limited to imaginary time evolution.

Popular summary

Combinatorial optimization is the process of identifying a set of discrete variables that minimizes or maximizes an objective function. Numerous real-world problems can be viewed as combinatorial optimization, which has a significant academic and industrial importance. In modern society, as the amount of data traffic increases due to technological advances, so does the size of the combinatorial optimization problems to be solved.

Quantum computers are expected to solve large-scale combinatorial optimization problems. However, the current quantum-gate hardware has a small number of quantum bits and errors during execution. Recently, a quantum-inspired solver using tensor networks has been proposed, which works on classical computers. Particularly, tensor networks have been applied to constrained combinatorial optimization problems for practical applications. By preparing a specific tensor network to sample states that satisfy constraints, feasible solutions can be searched for without the method of penalty functions. We define such tensor networks as “feasible” tensor networks. Previous studies on feasible tensor networks have been based on profound physics, such as U(1) gauge schemes and high-dimensional lattice models.

In this study, we devise to design feasible tensor networks using elementary mathematics without such a specific knowledge. One approach is to construct tensor networks with nilpotent-matrix manipulation. The second is to algebraically determine tensor parameters. We showed mathematically that such feasible tensor networks can be constructed to accommodate various types of constraints. For the principle verification, we numerically constructed a feasible tensor network for facility location problem, to find much faster construction than conventional methods. Then, by performing imaginary time evolution, feasible solutions were always obtained, ultimately leading to the optimal solution.

Proposed methods have advantages of user-friendly design of tensor networks and application to a wider range of constraints. Moreover, the results of this study may not only contribute to the development of optimization methods using tensor networks but also lead to that using quantum gates. In recent years, a technique for converting tensor networks into equivalent quantum circuits has been proposed. By combining such a technique and the proposed method, we can devise a new solver for constrained combinatorial optimization using quantum gates.

► BibTeX data

@article{Nakada2025quickdesignof,
  doi = {10.22331/q-2025-07-21-1799},
  url = {https://doi.org/10.22331/q-2025-07-21-1799},
  title = {Quick design of feasible tensor networks for constrained combinatorial optimization},
  author = {Nakada, Hyakka and Tanahashi, Kotaro and Tanaka, Shu},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1799},
  month = jul,
  year = {2025}
}

► References

[1] John Preskill. ``Quantum computing in the NISQ era and beyond''. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[2] Jacob C Bridgeman and Christopher T. Chubb. ``Hand-waving and interpretive dance: an introductory course on tensor networks''. Journal of Physics A: Mathematical and Theoretical 50, 223001 (2017).
https://doi.org/10.1088/1751-8121/aa6dc3

[3] Román Orús. ``Tensor networks for complex quantum systems''. Nature Reviews Physics 1, 538–550 (2019).
https://doi.org/10.1038/s42254-019-0086-7

[4] Kouichi Okunishi, Tomotoshi Nishino, and Hiroshi Ueda. ``Developments in the Tensor Network — from Statistical Mechanics to Quantum Entanglement''. Journal of the Physical Society of Japan 91, 062001 (2022).
https://doi.org/10.7566/JPSJ.91.062001

[5] Yuichiro Minato. ``Tensor Network Based HOBO Solver''. arXiv:2407.16106 (2024).
https://doi.org/10.48550/arXiv.2407.16106
arXiv:2407.16106

[6] Shoya Yasuda, Shunsuke Sotobayashi, and Yuichiro Minato. ``HOBOTAN: Efficient Higher Order Binary Optimization Solver with Tensor Networks and PyTorch''. arXiv:2407.19987 (2024).
https://doi.org/10.48550/arXiv.2407.19987
arXiv:2407.19987

[7] Aitor Morais, Eneko Osaba, Iker Pastor, and Izaskun Oregui. ``Comparative Analysis of Classical and Quantum-Inspired Solvers: A Preliminary Study on the Weighted Max-Cut Problem''. arXiv:2504.05989 (2025).
https://doi.org/10.48550/arXiv.2504.05989
arXiv:2504.05989

[8] Jin-Guo Liu, Lei Wang, and Pan Zhang. ``Tropical Tensor Network for Ground States of Spin Glasses''. Physical Review Letters 126, 090506 (2021).
https://doi.org/10.1103/PhysRevLett.126.090506

[9] Danylo Lykov, Roman Schutski, Alexey Galda, Valerii Vinokur, and Yuri Alexeev. ``Tensor Network Quantum Simulator With Step-Dependent Parallelization''. In Proceedings of the 2022 IEEE International Conference on Quantum Computing and Engineering (QCE), 582-593 (2022).
https://doi.org/10.1109/QCE53715.2022.00081

[10] Dimitri P. Bertsekas. ``Constrained optimization and Lagrange multiplier methods''. Academic press (1982).
https://doi.org/10.1016/C2013-0-10366-2

[11] David G. Luenberger and Yinyu Ye. ``Linear and Nonlinear Programming (Third edition)''. Springer (2008).
https://doi.org/10.1007/978-0-387-74503-9

[12] Andrew Lucas. ``Ising formulations of many NP problems''. Frontiers in Physics 2 (2014).
https://doi.org/10.3389/fphy.2014.00005

[13] Shu Tanaka, Ryo Tamura, and Bikas K. Chakrabarti. ``Quantum Spin Glasses, Annealing and Computation''. Cambridge University Press (2017).
https://dl.acm.org/doi/10.5555/3159044

[14] Kota Takehara, Daisuke Oku, Yoshiki Matsuda, Shu Tanaka, and Nozomu Togawa. ``A Multiple Coefficients Trial Method to Solve Combinatorial Optimization Problems for Simulated-annealing-based Ising Machines''. In Proceedings of the 2019 IEEE 9th International Conference on Consumer Electronics (ICCE-Berlin), 64-69 (2019).
https://doi.org/10.1109/ICCE-Berlin47944.2019.8966167

[15] Kensuke Tamura, Tatsuhiko Shirai, Hosho Katsura, Shu Tanaka, and Nozomu Togawa. ``Performance Comparison of Typical Binary-Integer Encodings in an Ising Machine''. IEEE Access 9, 81032-81039 (2021).
https://doi.org/10.1109/ACCESS.2021.3081685

[16] Kotaro Tanahashi, Shinichi Takayanagi, Tomomitsu Motohashi, and Shu Tanaka. ``Application of Ising Machines and a Software Development for Ising Machines''. Journal of the Physical Society of Japan 88, 061010 (2019).
https://doi.org/10.7566/JPSJ.88.061010

[17] Mashiyat Zaman, Kotaro Tanahashi, and Shu Tanaka. ``PyQUBO: Python Library for Mapping Combinatorial Optimization Problems to QUBO Form''. IEEE Transactions on Computers 71, 838-850 (2022).
https://doi.org/10.1109/TC.2021.3063618

[18] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G. Rieffel, Davide Venturelli, and Rupak Biswas. ``From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz''. Algorithms 12, 34 (2019).
https://doi.org/10.3390/a12020034

[19] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy, and Eleanor G. Rieffel. ``$XY$ mixers: Analytical and numerical results for the quantum alternating operator ansatz''. Physical Review A 101, 012320 (2020).
https://doi.org/10.1103/PhysRevA.101.012320

[20] Andreas Bärtschi and Stephan Eidenbenz. ``Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation''. In Proceedings of the 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), 72-82 (2020).
https://doi.org/10.1109/QCE49297.2020.00020

[21] Atsushi Matsuo, Yudai Suzuki, Ikko Hamamura, and Shigeru Yamashita. ``Enhancing VQE Convergence for Optimization Problems with Problem-Specific Parameterized Quantum Circuits''. IEICE Transactions on Information and Systems E106.D, 1772-1782 (2023).
https://doi.org/10.1587/transinf.2023EDP7071

[22] Hyakka Nakada, Kotaro Tanahashi, and Shu Tanaka. ``Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization''. IEEE Access 13, 73096-73108 (2025).
https://doi.org/10.1109/ACCESS.2025.3563960

[23] Tianyi Hao, Xuxin Huang, Chunjing Jia, and Cheng Peng. ``A Quantum-Inspired Tensor Network Algorithm for Constrained Combinatorial Optimization Problems''. Frontiers in Physics 10 (2022).
https://doi.org/10.3389/fphy.2022.906590

[24] Javier Lopez-Piqueres, Jing Chen, and Alejandro Perdomo-Ortiz. ``Symmetric tensor networks for generative modeling and constrained combinatorial optimization''. Machine Learning: Science and Technology 4, 035009 (2023).
https://doi.org/10.1088/2632-2153/ace0f5

[25] Javier Lopez-Piqueres and Jing Chen. ``Cons-training tensor networks''. arXiv:2405.09005 (2024).
https://doi.org/10.48550/arXiv.2405.09005
arXiv:2405.09005

[26] Markus Bachmayr, Michael Götte, and Max Pfeffer. ``Particle number conservation and block structures in matrix product states''. Calcolo 59, 22 (2022).
https://doi.org/10.1007/s10092-022-00462-9

[27] Javier Alcazar, Mohammad Ghazi Vakili, Can B. Kalayci, and Alejandro Perdomo-Ortiz. ``GEO: Enhancing Combinatorial Optimization with Classical and Quantum Generative Models''. Nature Communications 15, 2761 (2024).
https://doi.org/10.1038/s41467-024-46959-5

[28] Manuel S. Rudolph, Jing Chen, Jacob Miller, Atithi Acharya, and Alejandro Perdomo-Ortiz. ``Decomposition of matrix product states into shallow quantum circuits''. Quantum Science and Technology 9, 015012 (2023).
https://doi.org/10.1088/2058-9565/ad04e6

[29] Frank Verstraete and J. Ignacio Cirac. ``Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions''. arXiv:cond-mat/0407066 (2004).
https://doi.org/10.48550/arXiv.cond-mat/0407066
arXiv:cond-mat/0407066

[30] Jacob D. Biamonte, Jason Morton, and Jacob Turner. ``Tensor network contractions for $\sharp$sat''. Journal of Statistical Physics 160, 1389–1404 (2015).
https://doi.org/10.1007/s10955-015-1276-z

[31] Stefanos Kourtis, Claudio Chamon, Eduardo R. Mucciolo, and Andrei E. Ruckenstein. ``Fast counting with tensor networks''. SciPost Physics 7, 060 (2019).
https://doi.org/10.21468/SciPostPhys.7.5.060

[32] Gleb Ryzhakov and Ivan Oseledets. ``Constructive tt-representation of the tensors given as index interaction functions with applications''. In Proceedings of the 11th International Conference on Learning Representations (ICLR) (2023).
https://openreview.net/forum?id=yLzLfM-Esnu

[33] Jin-Guo Liu, Xun Gao, Madelyn Cain, Mikhail D Lukin, and Sheng-Tao Wang. ``Computing solution space properties of combinatorial optimization problems via generic tensor networks''. SIAM Journal on Scientific Computing 45, A1239–A1270 (2023).
https://doi.org/10.1137/22M1501787

[34] Alejandro Mata Ali, Iñigo Perez Delgado, Marina Ristol Roura, and Aitor Moreno Fdez. de Leceta. ``Polynomial-time Solver of Tridiagonal QUBO and QUDO problems with Tensor Networks''. arXiv:2309.10509 (2024).
https://doi.org/10.48550/arXiv.2309.10509
arXiv:2309.10509

[35] Alejandro Mata Ali, Iñigo Perez Delgado, and Aitor Moreno Fdez. de Leceta. ``Traveling Salesman Problem from a Tensor Networks Perspective''. arXiv:2311.14344 (2023).
https://doi.org/10.48550/arXiv.2311.14344
arXiv:2311.14344

[36] Reza Zanjirani Farahani, Maryam SteadieSeifi, and Nasrin Asgari. ``Multiple criteria facility location problems: A survey''. Applied Mathematical Modelling 34, 1689-1709 (2010).
https://doi.org/10.1016/j.apm.2009.10.005

[37] Nicholas Chancellor. ``Domain wall encoding of discrete variables for quantum annealing and QAOA''. Quantum Science and Technology 4, 045004 (2019).
https://doi.org/10.1088/2058-9565/ab33c2

[38] Salvador E. Venegas-Andraca, William Cruz-Santos, Catherine McGeoch, and Marco Lanzagorta. ``A cross-disciplinary introduction to quantum annealing-based algorithms''. Contemporary Physics 59, 174-197 (2018).
https://doi.org/10.1080/00107514.2018.1450720

[39] Nike Dattani. ``Quadratization in discrete optimization and quantum mechanics''. arXiv:1901.04405 (2019).
https://doi.org/10.48550/arXiv.1901.04405
arXiv:1901.04405

[40] Egon Balas. ``Disjunctive programming''. Springer (2018).
https://doi.org/10.1007/978-3-030-00148-3

[41] Wayne L. Winston. ``Operations research: applications and algorithm''. Thomson Learning, Inc. (2004).
https://books.google.co.jp/books/about/Operations_Research_Applications_and_Alg.html?id=Y9NYEAAAQBAJ&redir_esc=y

[42] Matthew Fishman, Steven R. White, and E. Miles Stoudenmire. ``The ITensor Software Library for Tensor Network Calculations''. SciPost Physics Codebases, 4 (2022).
https://doi.org/10.21468/SciPostPhysCodeb.4

[43] J. Forrest, T. Ralphs, S. Vigerske, Haroldo G. Santos, J. Forrest, L. Hafer, B. Kristjansson, and et al. ``coin-or/Cbc: Release releases/2.10.12''. Zenodo (2024).
https://doi.org/10.5281/zenodo.13347261

[44] S. Mitchell, A. Kean, A. Mason, M. O’Sullivan, A. Phillips, and F. Peschiera. ``Optimization with PuLP — PuLP 2.4 documentation''. https://coin-or.github.io/pulp/.
https://coin-or.github.io/pulp/

[45] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and et al. ``Variational quantum algorithms''. Nature Reviews Physics 3, 625-644 (2021).
https://doi.org/10.1038/s42254-021-00348-9

[46] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, ManHong Yung, Xiao-Qi Zhou, Peter J. Love, Alán AspuruGuzik, and Jeremy L. O’brien. ``A variational eigenvalue solver on a photonic quantum processor''. Nature Communications 5, 4213 (2014).
https://doi.org/10.1038/ncomms5213

[47] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A Quantum Approximate Optimization Algorithm''. arXiv:1411.4028 (2014).
https://doi.org/10.48550/arXiv.1411.4028
arXiv:1411.4028

Cited by

[1] Guillermo Preisser, Conor Mc Keever, and Michael Lubasch, "Variational matrix product states for combinatorial optimization", Physical Review Research 8 3, 033027 (2026).

[2] Hyakka Nakada, Kotaro Tanahashi, and Shu Tanaka, "Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization", IEEE Access 13, 73096 (2025).

[3] Aitor Morais, Eneko Osaba, Iker Pastor, and Izaskun Oregui, "Comparative Analysis of Classical and Quantum-Inspired Solvers: A Preliminary Study on the Weighted Max-Cut Problem", arXiv:2504.05989, (2025).

[4] Hyakka Nakada and Shu Tanaka, "Systematic and Efficient Construction of Quadratic Unconstrained Binary Optimization Forms for High-order and Dense Interactions", Journal of the Physical Society of Japan 94 9, 094801 (2025).

[5] Ryo Sakai and Chen-Yu Liu, "Tensor Network Generator-Enhanced Optimization for Traveling Salesman Problem", arXiv:2602.20175, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 13:36:55) and SAO/NASA ADS (last updated successfully 2026-08-10 13:36:56). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.