量子複雜性理論

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

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

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

量子查詢複雜性

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

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

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

參考資料

• John Watrous. Quantum Computational Complexity. 2008. arXiv:0804.3401v1  [quant-ph].
• Artem Kaznatcheev. Quantum query complexity. [2015-05-03]. （原始內容存檔於2020-11-27）.
• Nielsen, Michael; Chuang, Isaac. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. 2000. ISBN 978-0-521-63503-5. OCLC 174527496.
• Arora, Sanjeev; Barak, Boaz. Computational Complexity: A Modern Approach. Cambridge University Press. 2016: 201–236. ISBN 978-0-521-42426-4.
• Watrous, John. Quantum Computational Complexity. 2008. arXiv:0804.3401v1  [quant-ph].
• 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