BQP(複雜度)

佇咧算複雜度理論內，有限錯誤量子多項式時間（英語：bounded error quantum polynomial time，BQP）是一个決定性問題的複雜度類，而且其內的問題會使佇咧多項式時間內以量子電腦解決，錯誤的機率細漢三分之一。BQP 嘛會當看做是複雜度類 BPP 的量仔電腦版。

嘛會使講，著 BQP 內底的問題，存在一个使用量電腦的演算法（量仔演算法）真濟項式時間運作，並且有誠懸的機率回答正確的答案。對任何狀況，回答錯誤答案的機率細於三分之一。

佮其他「有限錯誤」的機率演算法相仝，遮所講著的三分之一是一个較凊彩的定義。若原本演算法的錯誤機率較大，咱會當振動濟擺這个欲演算法，才閣取多數回答正確的答案以取較懸的準確率。詳細的分析顯示錯誤的下限會當懸到二分之一 − _ n _ − _ c _ 或者是低達二 − _ nc _，所包含的題目範圍攏袂有變化。遮 _ c _ 是一个正數的常數，_ n _ 是輸入的長度。

量仔計算

演算法所使用量子位元的數目會當為輸入大細的任何多項式。比如講伊，因為分解 _ n _ 位元整數的演算法使用大約二'n'個量子位元（參考秀爾演算法）。

一般狀況之下，量仔電腦的計算停止佇量仔測量頂頭。測量行為會致使量子位元崩去其中一个量子態上。咱會當講量子位元佇經過運算了後，上尾的測量會予伊有足懸的機會出現正確的答案。

量仔電腦受著誠濟注目，因為有真濟問題已經知影BQP內，但是一般認為講佇P以外（嘛會使講，使用量電腦比起來一般電腦，會當大幅度縮短計算遮的問題的時間）。 一寡出名的例有：

• 整數分解（參考秀爾演算法）
• 離散對數
• 模擬量子系統（參考 universalquantum simulator）
• 佇咧特定根之下計算 Jones polynomial

外部共接

• Complexity Zoo link to BQP