BQP (複雜度)

维基百科,自由的百科全书
跳转至: 导航搜索

計算複雜度理論內,BQP (bounded error quantum polynomial time,有限錯誤量子多項式時間)是一個決定性問題的複雜度類,並且其內的問題可以在多項式時間內以量子電腦解決,錯誤的機率小於1/3。 BQP也可以視為是複雜度類BPP的量子電腦版。

換句話說,對BQP裡面的問題,存在一個使用量子電腦的演算法(量子演算法)花費多項式時間運作,並且有很高的機率回答正確的答案。對任何狀況,回答錯誤答案的機率小於三分之一。

與其他"有限錯誤"的機率演算法相同,這裡所提到的1/3是一個比較隨意的定義。如果原本演算法的錯誤機率比較大,我們可以運作多次該演算法,然後取多數回答正確的答案以取得比較高的準確率。詳細的分析顯示錯誤的下限可以高達1/2 − nc或者低達2nc,所包涵的題目範圍均不會有變化。這裡c是一個正數的常數,n是輸入的長度。

量子計算[编辑]

演算法所使用量子位元的數目可以為輸入大小的任何多項式。 舉例來說,因式分解 n位元整數的演算法使用大約2'n'個量子位元(參考秀爾演算法).

一般狀況之下,量子電腦的計算停止於量子測量上面。測量行為會導致量子位元塌縮到其中一個量子態上。我們可以說量子問原在經過運算之後,最終的測量會讓他有極高的機會出現正確的答案。

量子電腦受到許多矚目,因為有許多問題已知在BQP內,但是一般認為在P之外(換句話說,使用量子電腦比起一般電腦,能大幅縮短計算這些問題的時間)。一些註明的例子有:

參考資料[编辑]

  1. ^ 1.0 1.1 arXiv:quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor