  A recent breakthrough by Ambainis, Balodis, Iraids, Kokainis, Pr\=usis and
Vihrovs (SODA'19) showed how to construct faster quantum algorithms for the
Traveling Salesman Problem and a few other NP-hard problems by combining in a
novel way quantum search with classical dynamic programming. In this paper, we
show how to apply this approach to the minimum Steiner tree problem, a
well-known NP-hard problem, and construct the first quantum algorithm that
solves this problem faster than the best known classical algorithms. More
precisely, the complexity of our quantum algorithm is
$\mathcal{O}(1.812^k\poly(n))$, where $n$ denotes the number of vertices in the
graph and $k$ denotes the number of terminals. In comparison, the best known
classical algorithm has complexity $\mathcal{O}(2^k\poly(n))$.
