圖形中所有節點對間幾乎最短與小伸張路徑問題之量子演算解法

Quantum Algorithms for All Pairs Almost Shortest and Small Stretch Paths Problems

蔣兆凱(Chao-Kai Chiang)

指導教授 ： 呂忠津 ； 蔡錫鈞

國立清華大學/電機資訊學院/電機工程學系/碩士(2006年)

摘要

在圖上找尋最短路徑及最短距離的問題一直是演算法領域中的經典問題。在其長久的研究歷史中，演化出許多變化的類型與問題，同時許多雅致的演算法也被設計出來解決這些各式各樣的問題。本文藉由量子單起點最短路徑演算法(quantum single source shortest paths algorithm)的幫助，針對其中兩個衍生問題─在無向圖(undirected graph)上所有節點對間幾乎最短與小伸張路徑問題─分別設計一量子演算法並說明其在時間複雜度上的表現。
　　Aingworth等人[2]開啟傳統演算法上使用單起點最短路徑演算法來解決無權(unweighted)無向圖上所有節點對間幾乎最短路徑問題(all pairs almost shortest paths problem)的探討，Dor等人[16]繼承並推廣Aingworth等人的觀念，設計數種演算法去探討誤差和時間複雜度間的關係。另外，在無向圖上所有節點對間小伸張路徑問題(all pairs small stretch paths problem)的研究上，Cohen和Zwick [12]也使用類似的觀念建構了傳統的演算法來說明誤差和時間複雜度間的關係。
　　在量子計算中，Lov K. Grover在1996年提出的搜尋演算法(Grover’s search algorithm) 為量子計算展開新的里程碑。他的演算法在搜尋上提供了傳統時間複雜度平方根的改良，因此許多以此為基礎的演算法如雨後春筍般為了各種問題而因應而生。單起點最短路徑問題為其中一例。Dürr等人[15]便是利用Grover’s search algorithm的觀念，設計了一個量子單起點最短路徑演算法。
本文結合Aingworth，Dor及Cohen和Zwick等人的概念[2, 12, 16]與Dürr等人的量子單起點最短路徑演算法[15]，為無向圖上所有節點對間幾乎最短與小伸張路徑問題分別設計一個量子演算法，並且在文中證明新設計的演算法在時間複雜度上都有比傳統演算法更好的表現。

關鍵字

所有節點對間最短路徑問題 ； 量子單起點最短路徑演算法

並列摘要

The problem of finding distances and shortest paths on a given graph is one of the most classic problems in algorithmic graph theory. It has been studied for a long time and there are many elegant algorithms developed for various versions of this problem. We discuss the all pairs almost shortest paths problem and the all pairs small stretch paths problem --- both are variations of the all pairs shortest paths (APSP) problem --- with the help of quantum single source shortest paths (SSSP) algorithm on an undirected and connective graph.

For the all pairs almost shortest paths problem, the fastest classical algorithm up to the present runs in $ ilde{O}(min(n^{3/2}m^{1/2}, n^{7/3}))$ time and that for the all pairs small stretch paths problem runs in $ ilde{O}(n^{3/2}m^{1/2})$ time.

In this article we present two quantum algorithms $mathbf{Qapasp_{2}}$ and $mathbf{Qstretch_2}$ for the all pairs almost shortest paths problem and the all pairs small stretch paths problem, respectively. As shown in Theorems
ef{THM:Qapasp2} and
ef{THM:Qstretch2}, both algorithms run in time $ ilde{O}left(n^{11/6}m^{1/6}
ight)$ and are faster than other known algorithms.

並列關鍵字

All pairs shortest paths problem ； Quantum single source shortest paths algorithm

參考文獻

[1] S. Aaronson and Y. Shi, ``Quantum lower bounds for the collision and the element distinctness problems,'' Journal of the ACM, 51:595--605, 2004.

[2] D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani, ``Fast estimation of diameter and shortest paths (without matrix multiplicatoin),'' SIAM Journal on Computing, 28:1167--1181, 1999.

[3] A. Ambainis, ``Quantum walk wlgorithm for element distinctness,'' in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), pp. 22--31, October 17--19, 2004.

[5] A. Ambainis and R. v{S}palek, ``Quantum algorithms for matching and network flows,'' in arXiv:quant-ph/0508205, 2005.

[6] M. Boyer, G. Brassard, P. Ho yer, and A. Tapp, ``Tight bounds on quantum searching,'' Fortschritte der Physik, 46:493--505, 1998.