臺灣博碩士論文加值系統

Grover於1996年提出一量子演算法，能在資料庫有N筆資料的情況下需疊代多少次才能達到機率1/2。Zalka證明此量子演算法是最理想的，龍桂魯等人改良此演算法以達到百分之百能找到目標物。在這篇論文中，我們分析Grover量子演算法在機率分別為1/2、接近1以及等於1的情況。當目標物數目已知時，Grover量子演算法能在疊代約根號N次後分別達到機率1/2、接近1以及等於1的情況；而當目標物數目未知時，Grover量子演算法能在疊代約根號N次後達到機率1/2，但需疊代約N次才達到機率接近1以及等於1的情況。另外，Boyer等人僅證明當目標物數目介於1到3N/4時的結果，我們將證明目標物數目介於1到N的結果，並推廣Zalka的結果。

中文摘要 i
英文摘要 ii
誌謝 iii
Content iv
1. Introduction of Grover-based Quantum
Search Algorithm 1
1.1. Original Grover’s algorithm for single target 2
1.2. Original Grover’s algorithm for single targets 3
1.3. General Grover’s algorithm 3
1.4. Grover’s algorithm for unknown targets 4
2. Complexity Analysis 6
2.1. For P=1/2 6
2.1.1. t=1 6
2.1.2. t>1 and known 10
2.1.3. The number of targets is unknown 13
2.2. For P->1 16
2.2.1. t=1 16
2.2.2. t>1 and known 16
2.2.3. The number of targets is unknown 16
2.3. For P=1 17
2.3.1. The number of targets is known 17
2.3.2. The number of targets is unknown 19
3. Conclusion 20
4. Bibliography 21

Lov K.Grover,"Quantum Mechanics Helps in Searching for a needle in aHaystack", Phys. Rev. Lett. 79(1997), 325-328
M.Boyer, G.Brassard, P.Hoyer, and A.Tapp,"Tight bounds on Quantum Searching", Fortschr, Phys. 46(1998) 4-5, 493-505
Charles H.Bennett, E.Berstein, G.Brassard, U.Vazirani,"Strengths and Weaknesses of Quantum Computing", SIAM Journal on Computing, Volume 26, Issue 5(Octorber 1997), 1510-1523
C.Zalka,"Grover's quantum search algorithm is optimal", Phys. Rev. A, vol.60, no.4(1999), pp.2746-2751
C.Zalka,"A Grover-based quantum search of optimal order for an unknown number of marked elements", quant-ph/9902049 v1
G.L.Long,"Grover Algorithm with zero theoretical failure rate", Phys. Rev. A64, 022307(2001)
C.R.Hu,"A Famliy of Sure-Success Quantum Algorithms for Solving a Generalized Grover Search Problem", quant-ph/0201049 v1
J.Y.Hsieh, and C.M.Li,"A General SU(2) Formulationfor Quantum Searching with Certainty", Phys. Rev. A, Vol.65(5), 052322