Quick design of feasible tensor networks for constrained combinatorial optimization
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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2025-07-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2025-07-21-1799/pdf/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1839622870569844736 |
|---|---|
| author | Hyakka Nakada Kotaro Tanahashi Shu Tanaka |
| author_facet | Hyakka Nakada Kotaro Tanahashi Shu Tanaka |
| author_sort | Hyakka Nakada |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-12d6f543a34d45f4bc2a5fda8d8590c8 |
| institution | Matheson Library |
| issn | 2521-327X |
| language | English |
| publishDate | 2025-07-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj-art-12d6f543a34d45f4bc2a5fda8d8590c82025-07-21T12:07:28ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2025-07-019179910.22331/q-2025-07-21-179910.22331/q-2025-07-21-1799Quick design of feasible tensor networks for constrained combinatorial optimizationHyakka NakadaKotaro TanahashiShu TanakaQuantum 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.https://quantum-journal.org/papers/q-2025-07-21-1799/pdf/ |
| spellingShingle | Hyakka Nakada Kotaro Tanahashi Shu Tanaka Quick design of feasible tensor networks for constrained combinatorial optimization Quantum |
| title | Quick design of feasible tensor networks for constrained combinatorial optimization |
| title_full | Quick design of feasible tensor networks for constrained combinatorial optimization |
| title_fullStr | Quick design of feasible tensor networks for constrained combinatorial optimization |
| title_full_unstemmed | Quick design of feasible tensor networks for constrained combinatorial optimization |
| title_short | Quick design of feasible tensor networks for constrained combinatorial optimization |
| title_sort | quick design of feasible tensor networks for constrained combinatorial optimization |
| url | https://quantum-journal.org/papers/q-2025-07-21-1799/pdf/ |
| work_keys_str_mv | AT hyakkanakada quickdesignoffeasibletensornetworksforconstrainedcombinatorialoptimization AT kotarotanahashi quickdesignoffeasibletensornetworksforconstrainedcombinatorialoptimization AT shutanaka quickdesignoffeasibletensornetworksforconstrainedcombinatorialoptimization |