BQP (複雜度)
在計算複雜度理論內，有限錯誤量子多項式時間（英語：bounded error quantum polynomial time，BQP）是一個決定性問題的複雜度類，並且其內的問題可以在多項式時間內以量子電腦解決，錯誤的機率小於1/3。BQP也可以視為是複雜度類BPP的量子電腦版。
換句話說，對BQP裡面的問題，存在一個使用量子電腦的演算法（量子演算法）花費多項式時間運作，並且有很高的機率回答正確的答案。對任何狀況，回答錯誤答案的機率小於三分之一。
與其他「有限錯誤」的機率演算法相同，這裡所提到的1/3是一個比較隨意的定義。如果原本演算法的錯誤機率比較大，我們可以運作多次該演算法，然後取多數回答正確的答案以取得比較高的準確率。詳細的分析顯示錯誤的下限可以高達1/2 − n−c或者低達2−nc，所包含的題目範圍均不會有變化。這裡c是一個正數的常數，n是輸入的長度。
量子計算
演算法所使用量子位元的數目可以為輸入大小的任何多項式。舉例來說，因式分解n位元整數的演算法使用大約2'n'個量子位元（參考秀爾演算法）。
一般狀況之下，量子電腦的計算停止於量子測量上面。測量行為會導致量子位元塌縮到其中一個量子態上。我們可以說量子位元在經過運算之後，最終的測量會讓他有極高的機會出現正確的答案。
量子電腦受到許多矚目，因為有許多問題已知在BQP內，但是一般認為在P之外（換句話說，使用量子電腦比起一般電腦，能大幅縮短計算這些問題的時間）。一些著名的例子有：
- 整數分解（參考秀爾演算法）[1]
- 離散對數[1]
- 模擬量子系統（參考universalquantum simulator（英语：universal quantum simulator））
- 在特定根之下計算Jones polynomial（英语：Jones polynomial）
參考資料
- ^ 1.0 1.1 arXiv:quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor. [2012-12-02]. （原始内容存档于2014-12-04）.
外部連接
- Complexity Zoo link to BQP（页面存档备份，存于互联网档案馆）
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
