(44.192.112.123) 您好!臺灣時間:2021/03/09 00:26
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:黎世傑
研究生(外文):Shyh-Jye Li
論文名稱:量子運算上之多重目標搜尋演算法
論文名稱(外文):A Quantum Algorithm for Multiobject Search
指導教授:劉晉良劉晉良引用關係
指導教授(外文):Jinn-Liang Liu
學位類別:碩士
校院名稱:國立交通大學
系所名稱:應用數學系
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:18
中文關鍵詞:量子演算法
外文關鍵詞:quantum algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:301
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:53
  • 收藏至我的研究室書目清單書目收藏:0
陳鞏與刁子健二人近來提出了新的量子運算演算法。此演算法能百分之百從隨意儲存的資料中搜尋到單一目標。這篇論文中,我們將此演算法推廣到多重目標物的搜尋。我們的演算法先搜尋那些儲存在資料列下半部的目標物,然後再搜尋那些儲存在資料列上半部的目標物。新的演算法建立在“AND”及“OR”這兩種邏輯運算上。利用此兩種邏輯運算,我們可以產生兩種輔助的oracle函數。在我們的演算法中,這兩種輔助的oracle函數所扮演的角色與陳、刁二人演算法中的輔助的oracle函數類似,而且能正確地讓動態疊代法運作。如果儲存在後半部的目標物的數目(數目假設是 )是四的指數次,那麼新的演算法同樣能百分之百從 筆資料中找出目標物之中的一個,而且呼叫了 次的oracle。如果目標物的數目不是四的指數次,那麼此演算法能以大於或等於二分之一的機率從 筆資料中找出目標物之中的一個,總共呼叫了 次的oracle,其中 為大於或等於 的四的指數次方的數之中最小的。這裡,我們提出的演算法是比傳統演算法快,但是卻比Grover的演算法慢。

Chen and Diao presented a quantum algorithm for searching an unsorted database capable of finding a single target item with certainty. In this paper, we generalize it to multiobject search. Our algorithm firstly searches for the target items residing in the lower portion of the database list and then for those in the upper portion. The new algorithm is based on the logic “AND” and “OR” operations that lead to two types of auxiliary oracle functions whose role in the algorithm is similar to that of Chen and Diao’s algorithm in terms of dynamical iteration properly. If the number of targets in the lower part, , is a power of four, the new algorithm will with certainty find one of the targets in a database of items using oracle calls. If is not a power of four, the algorithm will, with a probability of at least one-half, find one of the targets using no more than oracle calls, where is the smallest positive integer of power of four greater than or equal to . The algorithm we present here is faster than the classical one, but slower than Grover’s.

Contents
1 Introduction 3
2 Generalization of Chen and Diao’s Algorithmfor Multiobject
Search 3
3 Required Number of Oracle Calls 13
4 Conclusions 15
5 Summary 17

[1] G. Chen and Z. Diao,”Exponentially fast quantum search algorithm”,quant-ph/0011109 v3(2000)
[2] M. Boyer, G. Brassard, P. Hoyer, and A. Tapp,“Proc. of the Workshopon Physics and Computation”, (PhysComp96) 36 (1996)
[3] T. Hogg,“A framework for structured quantum search”, Physica D120 102(1998)
[4] M. Boyer, G. Brassard, P. Hoyer, and A. Tapp,“Tight bounds on quantum search”, Fortsch. Phys. 46 (1998), 493-506
[5] C. Zalka,“Grover’s quantum searching algorithm is optimal”, quant-ph/9711070 (1997)
[6] C. C. Tu and G. L. Long,“Chen and Diao’s quantum search algorithm isnot exponentially fast”, quant-ph/0110098 (2001)
[7] G. Chen, S. A. Fulling, and M. O. Scully,“Grover’s algorithm for multi-object search in quantum computing”, quant-ph/9909040 v2(1999)
[8] M. A. Rubin,“A quantum search algorithm for a speci…ed number of targets”, quant-ph/0104082 v2(2001)

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
系統版面圖檔 系統版面圖檔