复杂性类和秀爾演算法

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

复杂性类和秀爾演算法之间的区别

复杂性类 vs. 秀爾演算法

在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--： 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題（Function problem）的集合，例如'''FP'''。 許多複雜度類可被描述它的數學邏輯（mathematical logic）特徵化，請見可描述的複雜度（descriptive complexity）。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。. 演算法（Shor算法），以數學家彼得·秀爾命名，是一個在1994年發現的，針對整數分解這題目的的量子演算法（在量子計算機上面運作的演算法）。比較不正式的說，它解決題目如下：給定一個整數N，找出他的質因數。 在一個量子計算機上面，要分解整數N，秀爾演算法的運作需要多項式時間（時間是log N的某個多項式這麼長，log N在這裡的意義是輸入的檔案長度）。更精確的說，這個演算法花費的時間，展示出質因數分解問題可以使用量子計算機以多項式時間解出，因此在複雜度類BQP裡面。這比起傳統已知最快的因數分解演算法，普通數域篩選法，其花費次指數時間 -- 大約，還要快了一個指數的差異。 秀爾演算法非常重要，因為它代表使用量子計算機的話，我們可以用來破解已被廣泛使用的公開密鑰加密方法，也就是RSA加密演算法。RSA演算法的基礎在於假設了我們不能很有效率的分解一個已知的整數。就目前所知，這假設對傳統的（也就是非量子）電腦為真；沒有已知傳統的演算法可以在多項式時間內解決這個問題。然而，秀爾演算法展示了因數分解這問題在量子計算機上可以很有效率的解決，所以一個足夠大的量子計算機可以破解RSA。這對於建立量子計算機和研究新的量子計算機演算法，是一個非常大的動力。 在2001年，IBM的一個小組展示了秀爾演算法的實例，使用NMR實驗的量子計算機，以及7個量子位元，將15分解成3×5。.

多項式時間

多項式時間（Polynomial time）在計算複雜度理論中，指的是一個問題的計算時間m(n)不大於問題大小n的多項式倍數。任何抽象機器都擁有一複雜度類，此類包括可於此機器以多項式時間求解的問題。 以數學描述的話，則可說m(n).

复杂性类和多項式時間 · 多項式時間和秀爾演算法 · 查看更多 »

BQP (複雜度)

在計算複雜度理論內，有限錯誤量子多項式時間（bounded error quantum polynomial time，BQP）是一個決定性問題的複雜度類，並且其內的問題可以在多項式時間內以量子電腦解決，錯誤的機率小於1/3。BQP也可以視為是複雜度類BPP的量子電腦版。 換句話說，對BQP裡面的問題，存在一個使用量子電腦的演算法（量子演算法）花費多項式時間運作，並且有很高的機率回答正確的答案。對任何狀況，回答錯誤答案的機率小於三分之一。 與其他「有限錯誤」的機率演算法相同，這裡所提到的1/3是一個比較隨意的定義。如果原本演算法的錯誤機率比較大，我們可以運作多次該演算法，然後取多數回答正確的答案以取得比較高的準確率。詳細的分析顯示錯誤的下限可以高達1/2 − n−c或者低達2−nc，所包含的題目範圍均不會有變化。這裡c是一個正數的常數，n是輸入的長度。.

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

算法

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

复杂性类和算法 · 秀爾演算法和算法 · 查看更多 »