2019/04/07 by Miyamoto, Masayuki, Iwamura, Masakazu, Kise, Koichi +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.1904.03581
A recent breakthrough by Ambainis, Balodis, Iraids, Kokainis, Prūsis 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 O(1.812k\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 O(2k\poly(n)).