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