Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

A Quantum Algorithm for Minimum Steiner Tree Problem

Masayuki Miyamoto, Masakazu Iwamura, Koichi Kise

Published Apr 7, 2019• 0 citations
OpenAlex

Related papers

Quantum Speedup for the Minimum Steiner Tree Problem

Masayuki Miyamoto, Masakazu Iwamura, Koichi Kise +1 more

arXiv:1904.03581•Lecture notes in computer science•Jan 1, 2020•14 citations

The Steiner Tree Problem: Novel QUBO Formulation and Quantum Annealing Implementation

Dan Li, Xiang-Hui Wu, Ji-Rong Liu

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.

quant-pharXiv:2603.04089•Mar 5, 2026•0 citations

Quantum Computing for Graph Optimization: An Approach to the Shortest Path Problem

Aniket Bembale, Nagendra Singh, P. Vinayaka +1 more

Lecture notes in networks and systems•Dec 1, 2025•0 citations

Quantum Distributed Algorithms for Approximate Steiner Trees and Directed Minimum Spanning Trees

Phillip Kerger, David E. Bernal Neira, Zoe Gonzalez Izquierdo +1 more

We present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability; one for producing an approximately optimal Steiner Tree, and one for producing an exact directed minimum spanning tree, each of which uses$\overline{O}(n^{1/4})$rounds of communication and$\tilde{O}(n^{9/4})$messages, achieving a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithmic frameworks with quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms as well as related classical algorithms, otherwise obscured by$\overline{O}$notation, revealing that advances are needed to render both the quantum and classical algorithms practical.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•2 citations

Quantum Algorithms for Graph and Algebra Problems

Sebastian Dörn

Recent Advances in Computer Science and Communications•Jan 9, 2010•1 citation

Solving the Bounded-Depth Steiner Tree Problem using an Adiabatic Quantum Computer

Kai Liu, Michael J. Dinneen

We propose a quadratic unconstrained binary optimization (QUBO) formulation for the Bounded-Depth Steiner Tree problem suitable for adiabatic quantum computers. The numbers of qubits (dimension of QUBO matrices) required by our formulation is O(|V|3), where |V| represents the number of vertices. A D-Wave 2X computer consisting of 1098 active qubits is evaluated for a selection of known common graphs. Experimental results are shown and discussed. Our results are applicable to the Bounded-Depth Minimum Spanning Tree problem, as a special case.

IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE)•Dec 1, 2019•5 citations
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.
We present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability; one for producing an approximately optimal Steiner Tree, and one for producing an exact directed minimum spanning tree, each of which usesO‾(n1/4)\overline{O}(n^{1/4})O(n1/4)rounds of communication andO~(n9/4)\tilde{O}(n^{9/4})O~(n9/4)messages, achieving a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithmic frameworks with quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms as well as related classical algorithms, otherwise obscured byO‾\overline{O}Onotation, revealing that advances are needed to render both the quantum and classical algorithms practical.
We propose a quadratic unconstrained binary optimization (QUBO) formulation for the Bounded-Depth Steiner Tree problem suitable for adiabatic quantum computers. The numbers of qubits (dimension of QUBO matrices) required by our formulation is O(|V|3), where |V| represents the number of vertices. A D-Wave 2X computer consisting of 1098 active qubits is evaluated for a selection of known common graphs. Experimental results are shown and discussed. Our results are applicable to the Bounded-Depth Minimum Spanning Tree problem, as a special case.