BQP (複雜度)和秀爾演算法

快捷方式: 差异，相似，杰卡德相似系数，参考。

BQP (複雜度)和秀爾演算法之间的区别

BQP (複雜度) vs. 秀爾演算法

在計算複雜度理論內，有限錯誤量子多項式時間（bounded error quantum polynomial time，BQP）是一個決定性問題的複雜度類，並且其內的問題可以在多項式時間內以量子電腦解決，錯誤的機率小於1/3。BQP也可以視為是複雜度類BPP的量子電腦版。 換句話說，對BQP裡面的問題，存在一個使用量子電腦的演算法（量子演算法）花費多項式時間運作，並且有很高的機率回答正確的答案。對任何狀況，回答錯誤答案的機率小於三分之一。 與其他「有限錯誤」的機率演算法相同，這裡所提到的1/3是一個比較隨意的定義。如果原本演算法的錯誤機率比較大，我們可以運作多次該演算法，然後取多數回答正確的答案以取得比較高的準確率。詳細的分析顯示錯誤的下限可以高達1/2 − n−c或者低達2−nc，所包含的題目範圍均不會有變化。這裡c是一個正數的常數，n是輸入的長度。. 演算法（Shor算法），以數學家彼得·秀爾命名，是一個在1994年發現的，針對整數分解這題目的的量子演算法（在量子計算機上面運作的演算法）。比較不正式的說，它解決題目如下：給定一個整數N，找出他的質因數。 在一個量子計算機上面，要分解整數N，秀爾演算法的運作需要多項式時間（時間是log N的某個多項式這麼長，log N在這裡的意義是輸入的檔案長度）。更精確的說，這個演算法花費的時間，展示出質因數分解問題可以使用量子計算機以多項式時間解出，因此在複雜度類BQP裡面。這比起傳統已知最快的因數分解演算法，普通數域篩選法，其花費次指數時間 -- 大約，還要快了一個指數的差異。 秀爾演算法非常重要，因為它代表使用量子計算機的話，我們可以用來破解已被廣泛使用的公開密鑰加密方法，也就是RSA加密演算法。RSA演算法的基礎在於假設了我們不能很有效率的分解一個已知的整數。就目前所知，這假設對傳統的（也就是非量子）電腦為真；沒有已知傳統的演算法可以在多項式時間內解決這個問題。然而，秀爾演算法展示了因數分解這問題在量子計算機上可以很有效率的解決，所以一個足夠大的量子計算機可以破解RSA。這對於建立量子計算機和研究新的量子計算機演算法，是一個非常大的動力。 在2001年，IBM的一個小組展示了秀爾演算法的實例，使用NMR實驗的量子計算機，以及7個量子位元，將15分解成3×5。.

算法

-- 算法（algorithm），在數學（算學）和電腦科學之中，為任何良定义的具體計算步驟的一个序列，常用於計算、和自動推理。精確而言，算法是一個表示爲有限長列表的。算法應包含清晰定義的指令用於計算函數。 算法中的指令描述的是一個計算，當其時能從一個初始狀態和初始輸入（可能爲空）開始，經過一系列有限而清晰定義的狀態最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在内的一些算法，包含了一些隨機輸入。 形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，並在其后尝试定义或者中成形。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義爲形式化算法的情況。.

BQP (複雜度)和算法 · 秀爾演算法和算法 · 查看更多 »

量子位元

量子位元（又稱為Q位元、qubit ，量子比特），在量子資訊科學中是量子信息的計量單位。傳統電腦使用0和1，量子電腦也是使用0跟1，但與之不同的是，其0與1可同時計算。古典系统中，一个位元在同一时间，不是0，就是1，但量子位元是0和1的量子疊加。这是量子電腦计算的特性。.

BQP (複雜度)和量子位元 · 秀爾演算法和量子位元 · 查看更多 »

量子測量

在量子力學之中，所謂的「測量」需要有較嚴謹的定義，而特別稱之為量子測量。量子测量不同于一般经典力学中的测量，量子测量会对被测量子系统产生影响，比如改变被测量子系统的状态；处于相同状态的量子系统被测量后可能得到完全不同的结果，这些结果符合一定的概率分布。量子测量是量子力学解释体系的核心问题，而量子力学的解释目前还没有统一的结论。.

BQP (複雜度)和量子測量 · 秀爾演算法和量子測量 · 查看更多 »