跳到主要內容

臺灣博碩士論文加值系統

(18.206.76.226) 您好!臺灣時間:2021/07/30 21:00
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:江勁涵
研究生(外文):Chiang, Ching-Han
論文名稱:量子最佳化演算法設計
論文名稱(外文):On the Design of Quantum Optimization Algorithm
指導教授:陳博現
指導教授(外文):Chen, Bor-Sen
學位類別:碩士
校院名稱:國立清華大學
系所名稱:電機工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:英文
論文頁數:34
中文關鍵詞:量子最佳化演算法量子搜尋演算法量子計數演算法排序估計
外文關鍵詞:quantum optimization algorithmquantum search algorithmquantum counting algorithmorder estimation
相關次數:
  • 被引用被引用:0
  • 點閱點閱:184
  • 評分評分:
  • 下載下載:10
  • 收藏至我的研究室書目清單書目收藏:0
本篇文章提出的量子最佳化演算法 (Quantum Optimization Algorithm) 將量子搜尋演算 (Quantum Search Algorithm) 法與量子計數演算法 (Quantum Counting Algorithm) 結合來解決最佳化問題。考慮一個含有N個元素的集合,並在此集合上定義一個函數使得集合內的每一個元素都對應一個函數值,而最佳化的目標即是在此集合內搜尋到具有最小或最大函數值的最佳元素。根據量子搜尋演算法,如果能建造一個最佳反相位量子閘擁有增加 相位到最佳元素的能力,則可以使用此最佳反相位量子閘O(√N) 次找到最佳元素。然而量子搜尋演算法並沒有提供製作最佳反相量子閘的方法,因此必須要另外尋找方法製作。觀察到最佳解同時具有最低的排序以及量子計數演算法可以用來製作排序估計演算法,這二觀察將有助於製作最佳反相位量子閘,方法如下:首先利用量子計數演算法設計一個排序估計演算法,接著利用此排序估計演算法辨識最佳原素進而製作最佳反向量子閘。然而排序估計演算法具有一些非理想的效應,且此效應將延續到量子最佳化演算法中而影響其效能,因此量子最佳化演算法的非理想效應與效能之分析亦在文中被討論。在最後的部分提供了一個數值範例驗證本篇論文的想法,此範例使用傳統電腦中的大矩陣乘法來模擬16個元素的量子最佳化演算法並得到了與推論相符合的結果。
In this study, we combine the quantum search algorithm and the quantum counting algorithm to perform a quantum optimization algorithm. We propose a method which applies the quantum counting algorithm to obtain the order of an element in a N-element set. Observing that the order information enable us to recognize the optimization solution, we employ the quantum search algorithm with order estimation algorithm to solve the optimization problem. Since the order estimation suffers a non-ideal effect that will affect the performance of quantum optimization algorithm, a performance analysis of quantum optimization algorithm is also provided. Finally, a numerical example is given to illustrate the proposed quantum optimization algorithm.
1 Introduction 3
2 Preliminaries 6
2.1 Boolean Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Quantum Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Quantum Gate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 Frequently Used Quantum Gates . . . . . . . . . . . . . . . . . . . . . . . 9
3 Methodology 15
3.1 Order Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Quantum Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Performance 26
5 Numerical Example 29
6 Conclusion 32
[1] M. Nielsen, I. Chuang, and L. Grover, “Quantum computation and quantum information,”American Journal of Physics, vol. 70, p. 558, 2002.
[2] L. Vandersypen and I. Chuang, “NMR techniques for quantum control and computation,”Reviews of modern physics, vol. 76, no. 4, pp. 1037–1069, 2005.
[3] J. Cirac and P. Zoller, “Quantum computations with cold trapped ions,” Physical Review Letters, vol. 74, no. 20, pp. 4091–4094, 1995.
[4] D. Loss and D. P. DiVincenzo, “Quantum computation with quantum dots,” Phys. Rev. A, vol. 57, no. 1, pp. 120–126, Jan 1998.
[5] D. P. DiVincenzo, “Two-bit gates are universal for quantum computation,” Phys. Rev. A, vol. 51, no. 2, pp. 1015–1022, Feb 1995.
[6] D. DiVincenzo, “Quantum computation,” Science, vol. 270, no. 5234, p. 255, 1995.
[7] R. Shankar, Principles of quantum mechanics. Springer, 1994.
[8] J. Sakurai and S. Tuan, Modern quantum mechanics. Addison-Wesley Reading (Mass.), 1994.
[9] P. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,”1994.
[10] L. Grover, “Quantum mechanics helps in searching for a needle in a haystack,” Physical Review Letters, vol. 79, no. 2, pp. 325–328, 1997.
[11] M. Boyer, G. Brassard, P. Høyer, and A. Tapp, “Tight bounds on quantum searching,”Fortschritte der Physik, vol. 46, no. 4-5, pp. 493–505, 1998.
[12] G. Brassard, P. Høyer, and A. Tapp, “Quantum counting,” Automata, Languages and Programming, pp. 820-831, 1998.
[13] C. Durr and P. Hoyer, “A quantum algorithm for finding the minimum,” Arxiv preprint quant-ph/9607014, 1996.
[14] C. Trugenberger, “Quantum optimization for combinatorial searches,” New Journal of Physics, vol. 4, p. 26, 2002.
[15] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, “Quantum computation by adiabatic evolution,” Arxiv preprint quant-ph/0001106, 2000.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
1. 李豐楙:〈唐人葵花詩與道教女冠——從道教史的觀點解說唐人詠葵花詩〉,收錄於《中外文學》,《中華民國第五屆比較文學會議論文專號‧上》第16卷第6期,1987年11月),後收錄於《憂與遊:六朝隋唐遊仙詩論集》,臺北:學生書局,1996年3月。
2. 楊莉:〈女冠芻議:一種宗教、性別與象徵的解讀〉,《漢學研究》,第19卷第1期,2001年6月。
3. 李甲孚:〈中唐的「女校書」——薛濤〉,《婦女雜誌》236期,1988年5月。
4. 張省卿:〈唐代名妓薛濤〉,《史苑》39期,1984年6月。
5. 陳玉萍:〈唐代女詩人薛濤之生活境遇及其詩作研究〉,《雲漢學刊》第5期,1996年5月。
6. 鄭志敏:〈唐代士人與妓女關係的演變—以「全唐詩」為中心〉,《中興史學》第1期,1994年12月。
7. 王桐齡:〈唐宋時代妓女考〉,《史學年報》第1卷第1期,1929年6月。
8. 江國貞:〈萬里橋邊女校書--薛濤:他真的是所謂的樂妓嗎?〉,《國文天地》,8卷11期,1993年4月。
9. 孫康宜:〈性別的困惑——從傳統讀者閱讀情詩的偏見說起〉,1998年8月發表於《近代中國婦女史研究》第6期,2000年由上海文藝出版社收入《耶魯‧性別與文化》出版。
10. 毛文芳:〈風光細膩的薛濤〉,《國文天地》,8卷11期,1993年4月。
11. 孫康宜:〈性別的困惑——從傳統讀者閱讀情詩的偏見說起〉,1998年8月發表於《近代中國婦女史研究》第6期。
12. 賴漢屏:〈營妓、女冠、詩人——唐代才女李冶、薛濤和魚玄機的詩作〉,《明道文藝》,第205期,1993年4月。
13. 張仁青:〈唐代詩壇兩紅顏——薛濤與魚玄機〉,《國文天地》,3卷10期,1988年。
14. 張修蓉:〈唐代女冠與娼妓詩歌〉,《聯合文學》,第2卷第5期,1986年3月。
15. 毛一波:〈女詩人薛濤〉,《東方雜誌副刊》,19卷2期,1985年8月。