量子群組測試

Abstract

我們將會在這篇論文中提出量子群組測試的演算法。 群組測試這個問題已有五十年的歷史。 Clementi et al. 於 2001 年提出了 k-selective family。 而 Indyk 則在 2002 年提出了一個較簡單的 k-selective family 造法。 這個 k-selective family 正好可以用來解決群組測試問題。 這篇論文中我們先介紹 Grover 的量子搜尋演算法, 然後我們將合併 $k$-selective family 及量子搜尋演算法, 來解決群組測試問題。 這樣可以得到更好的時間複雜度。

We describe the quantum group testing algorithm. Group testing problem has a history of research in the early days of computer science. In 2001, Clementi et al. introduce the k-selective family which can be used to solve this problem. Indyk provides a explicit construction method for the k-selective family in 2002. In this thesis, we first explain Grover's quantum search algorithm. Then we involve the k-selective system with quantum computation to solve the group testing problem with a better time complexity.