量子复杂性理论 量子复杂性理论Quantum complexity theory是理论计算机科学中计算复杂性理论的一部份该理论使用量子计算机和量子信息来研究分析复杂性类定义量子信息是基于量子力学的计算模型量子复杂性理论用来研究这些复杂性类的问题的困难度和量子复杂性类与经典非量子的复杂性类的关系 复杂性类是指的是一群複雜度類似的問題的集合可以用滿足特定資源限制下的演算法求解例如复杂性类P就是可以用图灵机在多項式時間內求解的問題也可以用量子算法如量子计算机或量子圖靈機定義量子复杂性例如複雜度BQP就是可以用量子计算机在多項式時間內解決其錯誤的機率小於一定比例的問題 量子复杂性中二個比較重要的复杂性類分別是BQP及QMA英语QMA分別對應複雜度P及NP 複雜度量子复杂性理论的一個主要目的是要找到對應傳統复杂性類如PNPPSPACEPP等的量子复杂性