在計算複雜度理論 內,有限錯誤量子多項式時間 (英語: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.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(页面存档备份,存于互联网档案馆 )
複雜度, 在計算複雜度理論內, 有限錯誤量子多項式時間, 英語, bounded, error, quantum, polynomial, time, 是一個決定性問題的複雜度類, 並且其內的問題可以在多項式時間內以量子電腦解決, 錯誤的機率小於1, bqp也可以視為是複雜度類bpp的量子電腦版, 換句話說, 對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 页面存档备份 存于互联网档案馆 取自 https zh wikipedia org w index php title BQP 複雜度 amp oldid 74531566, 维基百科,wiki ,书籍,书籍,图书馆,
文章 ,阅读,下载,免费,免费下载,mp3,视频,mp4,3gp, jpg,jpeg,gif,png,图片,音乐,歌曲,电影,书籍,游戏,游戏。