Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.04089 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910040963678208 |
|---|---|
| author | Li, Dan Wu, Xiang-Hui Liu, Ji-Rong |
| author_facet | Li, Dan Wu, Xiang-Hui Liu, Ji-Rong |
| contents | The Steiner Tree Problem (STP) is a well-known NP-hard combinatorial optimization problem, which has wide applications in network design, integrated circuit layout, bioinformatics, and other fields. However, traditional algorithms often struggle to balance efficiency and solution quality when dealing with large-scale STP instances. In this paper, we propose a new quantum annealing-based algorithm for solving the STP: we first model the STP into a quadratic unconstrained binary optimization (QUBO) form suitable for quantum annealing, then design a corresponding encoding strategy, and finally verify the algorithm through experimental tests. The results show that our quantum annealing-based method can obtain high-quality solutions with relatively low computational overhead for moderate-scale STP instances, providing a new feasible path for handling this intractable combinatorial optimization problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_04089 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Steiner Tree Problem: Novel QUBO Formulation and Quantum Annealing Implementation Li, Dan Wu, Xiang-Hui Liu, Ji-Rong Quantum Physics The Steiner Tree Problem (STP) is a well-known NP-hard combinatorial optimization problem, which has wide applications in network design, integrated circuit layout, bioinformatics, and other fields. However, traditional algorithms often struggle to balance efficiency and solution quality when dealing with large-scale STP instances. In this paper, we propose a new quantum annealing-based algorithm for solving the STP: we first model the STP into a quadratic unconstrained binary optimization (QUBO) form suitable for quantum annealing, then design a corresponding encoding strategy, and finally verify the algorithm through experimental tests. The results show that our quantum annealing-based method can obtain high-quality solutions with relatively low computational overhead for moderate-scale STP instances, providing a new feasible path for handling this intractable combinatorial optimization problem. |
| title | The Steiner Tree Problem: Novel QUBO Formulation and Quantum Annealing Implementation |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2603.04089 |