量子復雜性理論是計算復雜性理論的一個子領域，涉及使用量子計算機定義的復雜性類別，這是一種基于量子力學的計算模型。它研究計算問題的硬度與這些復雜性類的關系，以及量子復雜性類與經典（即非量子）復雜性類之間的關系。兩個重要的量子復雜性類是BQP和QMA。

復雜度類是一個計算模型在某些資源約束下可以解決的計算問題的集合。例如，復雜性類P被定義為圖靈機在多項式時間內可解決的問題的集合。類似地，量子復雜性類可以用計算的量子模型來定義，如量子電路模型或等價的量子圖靈機。量子復雜性理論的主要目的之一是找出這些類與經典復雜性類的關系，如P、NP、BPP和PSPACE。研究量子復雜性理論的原因之一是量子計算對現代教會-圖靈論的影響。簡而言之，現代教會-圖靈論指出，任何計算模型都可以用概率圖靈機在多項式時間內進行模擬。然而，圍繞教會-圖靈論的問題在量子計算的背景下出現了。目前還不清楚丘吉爾-圖靈論對于量子計算模型是否成立。有很多證據表明該論題不成立。概率圖靈機可能不可能以多項式時間模擬量子計算模型。函數的量子計算復雜性和函數的經典計算復雜性都經常用漸近符號來表達。一些常見的函數漸近概念的形式是{displaystyleω(T(n))}表示某物在下面有界限的情況下，可以用T(n)表示。表示有東西在下面被限定為cT(n){displaystylecT(n)}表示某物被cT(n)約束在下面。

一些重要的復雜性類是P、BPP、BQP、PP和P-空間。為了定義這些，我們首先定義一個承諾問題。承諾問題是一個決策問題，它的輸入被假定為從所有可能的輸入字符串的集合中選擇。一個承諾問題是一對{displaystyleA_{text{yes}}capA_{text{no}}==varnothing}。.前面所有的復雜度類都包含承諾問題。BQP可以由量子計算機有效解決的有界誤差的問題類被稱為BQP（有界誤差，量子，多項式時間）。

更正式地說，BQP是指錯誤概率最多為1/3的多項式時間量子圖靈機可以解決的一類問題。作為一類概率問題，BQP是BPP（有界誤差，概率，多項式時間）的量子對應物，是一類可以由有界誤差的概率圖靈機有效解決的問題。已知的是，這在直覺上意味著量子計算機在時間復雜性方面比經典計算機更強大。BQP是PP的一個子集。BQP與P、NP和PSPACE的確切關系尚不清楚。然而，已知的是P?BQP?PSPACE{displaystyle{mathsf{PsubseteqBQPsubseteqPSPACE}}。;也就是說，能被量子計算機有效解決的問題類別包括所有能被確定性的經典c有效解決的問題。