A Quantum Algorithm for Minimum Steiner Tree Problem
Masayuki Miyamoto ∗1 †1

Masakazu Iwamura2 ‡Koichi Kise2 §Department of Communications and Computer Engineering, Graduate School of Informatics, Kyoto University
Department of Computer Science and Intelligent Systems, Graduate School of Engineering, Osaka Prefecture
University2Abstract. Minimum Steiner tree problem is a well-known NP-hard problem. For the minimum Steinertree problem in graphs with n vertices and k terminals, there are many classical algorithms that takeexponential time in k. In this paper, to the best of our knowledge, we propose the first quantum algorithm for the minimum Steiner tree problem. The complexity of our algorithm is O∗ (1.812k ). A key torealize the proposed method is how to reduce the computational time of dynamic programming by using
a quantum algorithm because existing classical (non-quantum) algorithms in the problem rely on dynamicprogramming. Fortunately, dynamic programming is realized by a quantum algorithm for the travelling
salesman problem, in which Grover’s quantum search algorithm is introduced. However, due to difference
between their problem and our problem to be solved, recursions are different. Hence, we cannot apply
their technique to the minimum Steiner tree problem in that shape. We solve this issue by introducing adecomposition of a graph proposed by Fuchs et al.
The full version of this extended abstract is available at https://arxiv.org/abs/1904.03581.
THIS PAPER IS ELIGIBLE FOR BEST STUDENT POSTER AWARD
Keywords: Minimum Steiner Tree, The Dreyfus-Wagner Algorithm, Dynamic Programming, Grover
Search1

Introduction

Given an undirected graph G = (V, E), a weight w :E → R+ , and a subset of vertices K ⊆ V , usually referred
to as terminals, a Steiner tree is a tree that connects all
vertices in K. In this paper, let n = |V | be the size ofvertices and k = |K| be the size of terminals. A Steinertree T is the minimum
Steiner tree (MST) when the toP
tal edge weight e∈E(T ) w(e) is the minimum among all
Steiner trees of K. Note that all leaves of a Steiner tree
T are vertices in K. The task that finds a minimum
Steiner tree is called minimum Steiner tree problem, andthis problem is known as an NP-hard problem [1]. Notethat for fixed k, this problem can be solved in polynomial
time, which means that the minimum Steiner problem isfixed parameter tractable [2, 3].Although there are difficulties in solving the minimum Steiner tree problem,
this problem is applied to solve problems such as power
supply network, communication network and facility location problem [4]. Since these practical problems need
to be solved, researching the exponential algorithm thathas better base is significant.
A naive way to solve the minimum Steiner tree problem is to compute all possible trees. However, the number of all trees in the graph G = (V, E) is O(2|E| ) atworst. However, an exhaustive search is not realistic.
The Dreyfus-Wagner algorithm (the D-W algorithm) isa well-known algorithm based on dynamic programmingfor solving the Steiner problem in time O∗ (3k ) [5]. TheO∗ notation hides a polynomial factor in n and k. Thisalgorithm has been the fastest algorithm for decades. In
2007, Fuchs et al. [6] have improved this to O∗ (2.684k )∗This research was done when the first author studied in OsakaPrefecture University.
† miyamoto.masayuki.46s@st.kyoto-u.ac.jp‡ masa@cs.osakafu-u.ac.jp§ kise@cs.osakafu-u.ac.jp−1and Mölle et al. [7] to O((2 + δ)k nf (δ ) ) for any constant δ > 0. For a graph with a restricted weight range,
Björklund et al. have proposed an O∗ (2k ) algorithm using subset convolution and Möbius inversion [8]. An important thing is that the dynamic programming part ofthese algorithms [7, 6, 8] use the D-W algorithm.
In order to speed up classical algorithms, use of quantum algorithms is an effective technique. In particular,
Grover’s quantum search (Grover search) [9] and its generalization, quantum amplitude amplification [10, 11], arewidely applicable. Grover search brings quadratic speed
up to an unstructured search problem [9, 12]. This is oneof the advantages quantum algorithms have over classical algorithms. For NP-hard problems, speeding up using
Grover search [9] is a typical method. However, simplyapplying Grover search to a classical algorithm does notalways make faster than the best classical algorithm inmany problems. For example, in [13], by using quantum
computers, the Travelling Salesman Problem (TSP)√ fora graph which has n vertices is solved in time O∗ ( n!)which is the square root of the classical complexity O∗ (n!)
of an exhaustive search. However, the best classical algo∗ nrithm for TSP takes√ only O (2 ) [14, 15] which is clearly∗
faster than O ( n!).
In order to speed up algorithms for the minimum
Steiner tree problem, it is thought that use of Groversearch is also an effective technique. Combining classical algorithms with Grover search is one of the ways tomake an algorithm faster than the best classical algorithm. For example, Ambainis et al. [16] have combined
Grover search with algorithms for TSP, Minimum Set
Cover Problem and so on that use dynamic programming. A naive way is replacing the dynamic programming part of the algorithm of Ambainis et al. by D-W
algorithm. However, we cannot use the method of Ambainis et al. in the same way because the characteris-Table 1: Comparison of the algorithms.
Algorithm
Complexity
Dreyfus and Wagner [5]O∗ (3k )Fuchs [6]O∗ (2.684k )−1Mölle [7]O((2 + δ)k nf (δ ) )∗ kBjörklund [8] ( best known in the restricted weight case) O (2 )This paperO∗ (1.812k )tic of minimum Steiner tree problem differs from thatof TSP. Hence, we adapt this method to a method proposed by Fuchs et al. [6] for applying Grover search. The
decomposition method of Fuchs et al. is optimized fora classical computer. We optimize the decomposition
for a quantum computer. Our algorithm achieved thecomplexity O∗ (1.812k ). This improvement of complexity
brings more than 104 times speed up compared to O∗ (2k )even in the case of k = 100. Table 1 shows the complexityof classical algorithms for minimum Steiner tree problem
and our proposed algorithm.

References[1] Richard M Karp. Reducibility among combinatorial
problems. In Complexity of computer computations,pages 85–103. Springer, 1972.
[2] Rodney G Downey and Michael Ralph Fellows. Parameterized complexity. Springer Science & BusinessMedia, 2012.
[3] Jörg Flum and Martin Grohe. Parameterized complexity theory. Springer Science & Business Media,2006.
[4] Frank K Hwang and Dana S Richards. Steiner treeproblems. Networks, 22(1):55–89, 1992.
[5] Stuart E Dreyfus and Robert A Wagner. The steiner
problem in graphs. Networks, 1(3):195–207, 1971.
[6] Bernhard Fuchs, Walter Kern, and Xinhui Wang.
Speeding up the Dreyfus–Wagner algorithm for minimum Steiner trees. Mathematical methods of operations research, 66(1):117–125, 2007.
[7] Daniel Mölle, Stefan Richter, and Peter Rossmanith.
A faster algorithm for the Steiner tree problem. In
Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science, pages 561–570.
Springer, 2006.
[8] Andreas Björklund, Thore Husfeldt, Petteri Kaski,and Mikko Koivisto. Fourier meets Möbius: fastsubset convolution. In Proceedings of the thirty-ninth
annual ACM symposium on Theory of computing,pages 67–74, 2007.
[9] Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of thetwenty-eighth annual ACM symposium on Theory ofcomputing, pages 212–219, 1996.

classical or quantum
classical
classical
classical
classicalquantum[10] Gilles Brassard, Peter Hoyer, Michele Mosca, andAlain Tapp. Quantum amplitude amplification andestimation. Contemporary Mathematics, 305:53–74,2002.
[11] Michele Mosca et al. Quantum searching, counting
and amplitude amplification by eigenvector analysis.
In MFCS98 workshop on Randomized Algorithms,
pages 90–100, 1998.
[12] Michel Boyer, Gilles Brassard, Peter Høyer, andAlain Tapp. Tight bounds on quantum searching.
Fortschritte der Physik: Progress of Physics, 46(45):493–505, 1998.
[13] Karthik Srinivasan, Saipriya Satyajit, Bikash K. Behera, and Prasanta K. Panigrahi. Efficient quantumalgorithm for solving travelling salesman problem:
An IBM quantum experience, 2018.
[14] Richard Bellman. Dynamic programming treatment of the travelling salesman problem. J. ACM,
9(1):61–63, 1962.
[15] Michael Held and Richard M Karp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1):196–210, 1962.
[16] Andris Ambainis, Kaspars Balodis, Jānis Iraids,
Martins Kokainis, Krišjānis Prūsis, and Jevgēnijs
Vihrovs. Quantum speedups for exponential-time
dynamic programming algorithms. arXiv preprint
arXiv:1807.05209, 2018.