量子運算上之多重目標搜尋演算法

Abstract

陳鞏與刁子健二人近來提出了新的量子運算演算法。此演算法能百分之百從隨意儲存的資料中搜尋到單一目標。這篇論文中，我們將此演算法推廣到多重目標物的搜尋。我們的演算法先搜尋那些儲存在資料列下半部的目標物，然後再搜尋那些儲存在資料列上半部的目標物。新的演算法建立在“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.