秀爾演算法

秀爾演算法（英語：Shor's algorithm）是一個于1994年發現的，以數學家彼得·秀爾命名，針對整數分解題目的的量子演算法（在量子計算機上面運作的演算法）。不正式地說，它解決的題目是：給定一個整數 ，找出它的質因數。在一個量子計算機上面，要分解整數，秀爾演算法的運作需要多項式時間（時間是 的某個多項式這麼長， 在這裡的意義是輸入的檔案長度）。准确来说，该演算法花費 的時間，展示出質因數分解問題可以使用量子計算機以多項式時間解出，因此在複雜度類BQP裡面。這比傳統上已知的最快的因數分解演算法普通數域篩選法所花費的次指數時間——大約 還要快了一個指數。 秀爾演算法非常重要，它意味着：假如有可用的量子計算機，我們可以破解基于公開密鑰加密的算法（比如RSA加密演算法）。RSA演算法的基礎在於假設了我們不能有效率的分解一個已知的整數。就目前所知，這假設對傳統（即非量子）的電腦為真；沒有已知的傳統演算法可以在多項式時間內解決這個問題。但秀爾演算法展示了因數分解問題在量子計算機上可以很有效率的解決，所以一個足夠大的量子計算機可以破解RSA。這對於建立量子計算機和研究新的量子計算機演算法是一個强大的動力。 2001年，IBM的一個小組展示了秀爾演算法的實例，使用的量子計算機及7個量子位元，將15分解成3×5。不过，对于IBM的實驗是否是量子計算的真實展示，有一些疑慮出現，因為沒有发现纏結現象。IBM的實驗之後，也有其他的團隊以光學量子位元實驗秀爾演算法，並強調可觀察到其纏結現象。