跳到主要內容

臺灣博碩士論文加值系統

(44.222.218.145) 您好!臺灣時間:2024/02/26 23:19
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:蔣兆凱
研究生(外文):Chao-Kai Chiang
論文名稱:圖形中所有節點對間幾乎最短與小伸張路徑問題之量子演算解法
論文名稱(外文):Quantum Algorithms for All Pairs Almost Shortest and Small Stretch Paths Problems
指導教授:呂忠津蔡錫鈞蔡錫鈞引用關係
指導教授(外文):Chung-Chin LuShi-Chun Tsai
學位類別:碩士
校院名稱:國立清華大學
系所名稱:電機工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:中文
論文頁數:39
中文關鍵詞:所有節點對間最短路徑問題量子單起點最短路徑演算法
外文關鍵詞:All pairs shortest paths problemQuantum single source shortest paths algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:217
  • 評分評分:
  • 下載下載:15
  • 收藏至我的研究室書目清單書目收藏:0
  在圖上找尋最短路徑及最短距離的問題一直是演算法領域中的經典問題。在其長久的研究歷史中,演化出許多變化的類型與問題,同時許多雅致的演算法也被設計出來解決這些各式各樣的問題。本文藉由量子單起點最短路徑演算法(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 $\tilde{O}(\min(n^{3/2}m^{1/2}, n^{7/3}))$ time and that for the all pairs small stretch paths problem runs in $\tilde{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 \ref{THM:Qapasp2} and \ref{THM:Qstretch2}, both algorithms run in time $\tilde{O}\left(n^{11/6}m^{1/6}\right)$ and are faster than other known algorithms.
Contents i

List of Figures iii

1 Introduction 1
1.1 Single soure shortest paths problem ............. 3
1.2 All pairs shortest paths problem ............... 4
1.3 Grover's search algorithm and its applications .. 7
1.4 Thesis organization ............................ 11

2 Preliminaries 13
2.1 The classify algorithm ......................... 13
2.2 Quantum SSSP algorithm ......................... 15

3 A Quantum Surplus 2 Algorithm 20

4 A Quantum Stretch 2 Algorithm 25

5 Discussions and Further Works 32

A Output a Path in O(n) Time 35

Bibliography 37
[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.

[4] A. Ambainis, ``Quantum lower bounds by quantum arguments,'' in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp. 636--643, May 21--23, 2000.

[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. H\o yer, and A. Tapp, ``Tight bounds on quantum searching,'' Fortschritte der Physik, 46:493--505, 1998.

[7] G. Brassard, P. H\o yer, M. Mosca, and A. Tapp, ``Quantum amplitude amplification and estimation,'' in arXiv:quant-ph/0005055, 2000.

[8] H. Buhrman, R. Cleve, R. de Wolf, and C. Zalka, ``Bounds for small-error and zero-error quantum algorithms,'' in Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS'99), pp. 358--368, October 17--18, 1999.

[9] H. Buhrman, C. D\"{u}rr, M. Heiligman, P. H\o yer, F. Magniez, M. Santha, and R. de Wolf. ``Quantum algorithms for element distinctness,'' in Proceedings of 16th IEEE Complexity, pp. 131--137, 2001.

[10] H. Buhrman and R. \v{S}palek, ``Quantum verification of matrix products.'' in Proceedings of 17th ACM-SIAM SODA, pp. 880--889, 2006.

[11] E. Cohen, ``Polylog-time and near-linear work approximation scheme for undirected shortest paths,'' Journal of the ACM, 47(1):132--166, 2000.

[12] E. Cohen and U. Zwick, ``All-pairs small-stretch paths,'' Journal of Algorithms, 38:335--353, 2001.

[13] D. Coppersmith and S. Winogad, ``Matrix multiplication via alrithmetic progressions,'' Journal of Symbolic Computation, 9:42--49, 1990.

[14] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Intorduction to Algorithms. Cambridge, MA: The MIT Press, 2001.

[15] C. D\"{u}rr, M. Heiligman, P. H\o yer, and M. Mhalla, ``Quantum query complexity of some graph problems,'' SIAM Journal on Computing, 35(6):1310--1328, 2006.

[16] D. Dor, S. Halperin, and U. Zwick, ``All pairs almost shortest paths,'' SIAM Journal on Computing, 29:1740--1759, 2000.

[17] Z. Galil and O. Margalit, ``All paris shortest distances for graphs with small integer length edges,'' Information and Computation, 134:103--139, 1997.

[18] Z. Galil and O. Margalit, ``All paris shortest paths for graphs with small integer length edges,'' Jourmal of Computer and System Sciences, 54:243--254, 1997.

[19] L.K. Grover, ``A fast quantum mechanical algorithm for database search,'' in Proceedings of 28th Annual ACM Symposium on Theory of Computing, pp. 212--219, May 1996.

[20] L.K. Grover, ``Quantum mechanics helps in searching for a needle in a haystack,'' Physical Review Letters, 79:325--328, July 1997.

[21] M. Hirvensalo, Quantum Computing. Berlin, Germany: Springer-Verlag, 2003.

[22] F. Magniez, M. Santha, and M. Szegedy, ``Quantum algorithms for the triangle problem,'' in Proceeding of 16th ACM-SIAM SODA, pp. 1109--1117, 2005.

[23] R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge, U.K.: Cambridge University Press, 1995.

[24] M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information. Cambridge, U.K.: Cambridge University Press, 2000.

[25] R. Seidel, ``On the all-pairs-shortest-path problem,'' in Proceeding of the 24th Annual ACM Symposium on Theory of Computing, pp. 745--749, 1992.

[26] R. Seidel, ``On the all-pairs-shortest-path problem in unweighted undirected graphs,'' Journal of Computer and System Sciences, 51:400--403, 1995.

[27] M. Szegedy, ``Quantum speed-up of Markov chain based algorithms,'' in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), pp. 32--41, October 17--19, 2004.

[28] U. Zwick, ``Exact and approximate distances in graphs --- A survey,'' in Proceedings of the 9th Annual European Symposium on Algorithms, pp. 33--48, August 2001.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文