並行式與分散式量子可滿足性問題之求解器
陳盈如教授成功大學電機工程學系 15:30 – 17:00 鴻經館 M107
Abstract：
布林可滿足性問題（Boolean Satisfiability Problem, SAT）是第一個被證明為 NP-Complete 的問題。如果能夠找到更有效率地求解 SAT 問題的計算方法，對於計算機科學及數位電路的驗證，在求解效率上將非常有利。近年來，由於量子電腦的問世，也愈來愈多研究著手於量子 SAT 求解器的設計，試圖解決在傳統電腦中求解 SAT 問題時所遇到的狀態空間爆炸問題。其中，基於格羅弗演算法 (Grover's algorithm) 的 SAT 求解器也成為了熱門的研究對象。雖然現有的量子 SAT 求解器已經可以一次考慮所有可能的輸入，但它們必須照順序求解函式中的每個子句，使得時間複雜度為 O(m)，與子句的數量 m 呈線性的關係。 為此，我們開發了並行式的量子 SAT 求解器，利用額外的量子位元將每次格羅弗迭代的時間複雜度減少到 O(1)。並且為了更進一步解決並行式 SAT 求解器使用過多量子位元，以及待驗證設計資訊過於集中的問題，我們利用量子遙傳（Quantum Teleportation）提出了分散式量子 SAT 求解器，使得所需的量子位元能夠被分配在各台量子電腦中，並透過這些不同的量子電腦共同完成 SAT 問題。