量子複雜性理論（Quantum complexity theory）是理論計算機科學中計算複雜性理論的一部分。
基本介紹
簡介,複雜性類,量子查詢複雜性,
簡介
量子複雜性理論（Quantum complexity theory）是理論計算機科學中計算複雜性理論的一部分。該理論使用量子計算機和量子信息來研究分析複雜性類定義，量子信息是基於量子力學的計算模型。量子複雜性理論用來研究這些複雜性類的問題的困難度，和量子複雜性類與經典（非量子的）複雜性類的關係。
複雜性類
複雜性類是指的是一群複雜度類似的問題的集合，可以用滿足特定資源限制下的算法求解。例如複雜性類P就是可以用圖靈機在多項式時間內求解的問題。也可以用量子算法（如量子計算機或量子圖靈機）定義量子複雜性，例如複雜度BQP就是可以用量子計算機在多項式時間內解決，其錯誤的機率小於一定比例的問題。
量子查詢複雜性
在量子查詢複雜性（Quantum Query Complexity）中，輸入由一預言機（黑箱）提供，算法要用查詢預言機的方式得到和輸入相關的資訊，算法由某個固定的量子狀態開始，當對預言機查詢時，其狀態隨之變化。
量子查詢複雜性是指要計算其對應函式，需要查詢預言機的最小次數，量子查詢複雜性是函式整體時間複雜性的下限。
像搜尋無結構資料庫的Grover算法即為量子算法，其量子查詢複雜性為O(N)，比已知最好的傳統查詢複雜度有二次方的差距。
