在計算複雜性理論中,BQP(bounded-error quantum polynomial time)是量子計算機在多項式時間內可以解決的一類決策問題,所有實例的錯誤機率至多為1/3。它是複雜類BPP的量子類比。
基本介紹
- 外文名:bounded-error quantum polynomial time
- 縮寫:BQP
介紹,量子計算,與其他複雜類的關係,
介紹
![](/img/7/3dc/4583659bac7757c5e5524ed37fc5.jpg)
![](/img/a/0cf/e16416837222d87bae0c7f8224e3.jpg)
![](/img/4/114/0552560d7e1939eabcac588cc526.jpg)
![](/img/7/3dc/4583659bac7757c5e5524ed37fc5.jpg)
對於全部
,
取
個比特作為輸入並輸出1比特;
![](/img/4/114/0552560d7e1939eabcac588cc526.jpg)
![](/img/a/0cf/e16416837222d87bae0c7f8224e3.jpg)
![](/img/8/327/24fa42c665e020db8dc767480a6c.jpg)
對於L中的所有x,
;
![](/img/9/b12/f172f55ba89a52c02a92a7f42896.jpg)
對於L中的所有x,
.
![](/img/d/277/f46b0cab9ff38e7ffebc16f2fd21.jpg)
量子計算
計算機中的量子比特數允許為實例大小的多項式函式。 例如,已知用僅超過2n個量子位(Shor算法)來分解n位整數的算法。
通常,量子計算機上的計算以測量結束。 這導致量子態向基態的崩潰。 可以說量子態被測量的機率很高,處於正確的狀態。
量子計算機已經引起了廣泛的興趣,因為已知一些實際感興趣的問題在
中,但被懷疑在
之外。一些突出的例子是:
![](/img/7/3dc/4583659bac7757c5e5524ed37fc5.jpg)
![](/img/d/e00/ef4bfc19c1c5a481b4c8a84a4838.jpg)
a.整數因子分解(參見Shor算法);
b.離散對數;
c.量子系統的模擬(見通用量子模擬器);
d.在統一的某個根逼近瓊斯多項式;
b.離散對數;
c.量子系統的模擬(見通用量子模擬器);
d.在統一的某個根逼近瓊斯多項式;
與其他複雜類的關係
該類是為量子計算機定義的,其普通計算機(或圖靈機加隨機源)的自然對應類是
。就像
和
一樣,
本身就很低,這意味著
=
。非正式地說,這是因為多項式時間算法在組合下是閉合的。如果一個多項式時間算法作為子程式調用多項式多項式時間算法,則所得到的算法仍然是多項式時間。
![](/img/1/b9f/2226e065cc545e410d955e820e7e.jpg)
![](/img/d/e00/ef4bfc19c1c5a481b4c8a84a4838.jpg)
![](/img/1/b9f/2226e065cc545e410d955e820e7e.jpg)
![](/img/7/3dc/4583659bac7757c5e5524ed37fc5.jpg)
![](/img/e/739/749ef1b7d64259e8d657b7f3490a.jpg)
![](/img/f/a92/7c2057d2a95b58375dc1abe57a0d.jpg)
![](/img/7/3dc/4583659bac7757c5e5524ed37fc5.jpg)
![](/img/d/e00/ef4bfc19c1c5a481b4c8a84a4838.jpg)
![](/img/1/b9f/2226e065cc545e410d955e820e7e.jpg)
![](/img/a/9ed/60c7fcc7511bc86c3025599587c0.jpg)
![](/img/3/431/da18d175c65f643d806fe1309f2d.jpg)
![](/img/f/ef2/01d95dc1d3cb3adad715f97248fc.jpg)
![](/img/7/3dc/4583659bac7757c5e5524ed37fc5.jpg)
![](/img/3/431/da18d175c65f643d806fe1309f2d.jpg)
![](/img/7/3dc/4583659bac7757c5e5524ed37fc5.jpg)
![](/img/5/872/4524f7337fc42cdb509b2ab3b501.jpg)
由於
的問題還沒有解決,
和上述類別之間不平等的證明應該是困難的。
和
之間的關係尚不清楚。
![](/img/7/df9/b935d684ac3d53a7ce19f57d4488.jpg)
![](/img/7/3dc/4583659bac7757c5e5524ed37fc5.jpg)
![](/img/7/3dc/4583659bac7757c5e5524ed37fc5.jpg)
![](/img/d/706/959edf66811b943036b9d36b2242.jpg)
將後期選擇添加到
會導致複雜性類Post
於
。
![](/img/7/3dc/4583659bac7757c5e5524ed37fc5.jpg)
![](/img/7/3dc/4583659bac7757c5e5524ed37fc5.jpg)
![](/img/3/431/da18d175c65f643d806fe1309f2d.jpg)