量子复杂性理论

量子复杂性理论（Quantum complexity theory）是理论计算机科学中计算复杂性理论的一部份。该理论使用量子计算机和量子信息来研究分析复杂性类定义，量子信息是基于量子力学的计算模型。量子复杂性理论用来研究这些复杂性类的问题的困难度，和量子复杂性类与经典（非量子的）复杂性类的关系。

复杂性类是指的是一群複雜度類似的問題的集合，可以用滿足特定資源限制下的演算法求解。例如复杂性类P就是可以用图灵机在多項式時間內求解的問題。也可以用量子算法（如量子计算机或量子圖靈機）定義量子复杂性，例如複雜度BQP就是可以用量子计算机在多項式時間內解決，其錯誤的機率小於一定比例的問題。

量子复杂性中二個比較重要的复杂性類分別是BQP及，分別對應複雜度P及NP (複雜度)。量子复杂性理论的一個主要目的是要找到對應傳統复杂性類（如P、NP、PSPACE、PP等）的量子复杂性。

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

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

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

參考資料

 
 
 
 Watrous J. (2009) Quantum Computational Complexity . In: Meyers R. (eds) Encyclopedia of Complexity and Systems Science. Springer, New York, NY

外部連結
 MIT lectures  by Scott Aaronson

計算複雜性理論