Grover量子演算法的繁雜度分析

Abstract

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的結果。