量子複雜性理論

量子複雜性理論(Quantum complexity theory)是理論電腦科學計算複雜性理論的一部份。該理論使用量子電腦量子資訊來研究分析複雜性類別定義,量子資訊是基於量子力學計算模型。量子複雜性理論用來研究這些複雜性類別的問題的困難度,和量子複雜性類別與經典(非量子的)複雜性類別的關係。

複雜性類別是指的是一群複雜度類似的問題的集合,可以用滿足特定資源限制下的演算法求解。例如複雜性類別P就是可以用圖靈機多項式時間內求解的問題。也可以用量子演算法(如量子電腦量子圖靈機)定義量子複雜性,例如複雜度BQP就是可以用量子電腦在多項式時間內解決,其錯誤的機率小於一定比例的問題。

量子複雜性中二個比較重要的複雜性類分別是BQPQMA英語QMA,分別對應複雜度PNP (複雜度)。量子複雜性理論的一個主要目的是要找到對應傳統複雜性類(如P、NP、PSPACEPP等)的量子複雜性。

量子查詢複雜性

在量子查詢複雜性(Quantum Query Complexity)中,輸入由一預言機(黑箱)提供,演算法要用查詢預言機的方式得到和輸入相關的資訊,演算法由某個固定的量子狀態開始,當對預言機查詢時,其狀態隨之變化。

量子查詢複雜性是指要計算其對應函式,需要查詢預言機的最小次數,量子查詢複雜性是函式整體時間複雜性的下限。

像搜尋無結構資料庫的Grover演算法即為量子演算法,其量子查詢複雜性為O(N1/2),比已知最好的傳統查詢複雜度有二次方的差距。

參考資料

外部連結