text: 量子複雜性理論複雜性類的關係。複雜性類是指的是一群複雜度類似的問題的集合，可以用滿足特定資源限制下的演演算法求解。例如複雜性類P就是可以用圖靈機在多項式時間內求解的問題。也可以用量子演算法定義量子複雜性，例如複雜度BQP就是可以用量子計算機在多項式時間內解決，其錯誤的機率小於一定比例的問題。量子複雜性中二個比較重要的複雜性類分別是BQP及，分別對應複雜度P及NP (複雜度)。量子複雜性理論的一個主要目的是要找到對應傳統複雜性類的量子複雜性。量子查詢複雜性.在量子查詢複雜性提供，演演算法要用查詢預言機的方式得到和輸入相關的資訊，演演算法由某個固定的量子狀態開始，當對預言機查詢時，其狀態隨之變化。量子查詢複雜性是指要計算其對應函式，需要查詢預言機的最小次數，量子查詢複雜性是函式整體時間複雜性的下限。像搜尋無結構資料庫的Grover演演算法即為量子演演算法，其量子查詢複雜性為"O"("N"1/2)，比已知最好的傳統查詢複雜度有二次方的差距。
metadata.dataset: erhwenkuo/wikipedia-zhtw
metadata.title: 量子複雜性理論
metadata.url: https://zh.wikipedia.org/wiki?curid=4287606