DTM），量子計算機則是非決定性的圖靈機（NDTM）。德義奇同時證明，它將具有比傳統的計算機大得多的效率。用術語來講，執行同一任務時它所要求的複雜性（complexity）要低得多。理由是顯而易見的，量子計算機執行的是一種並行計算，正如我們前麵舉的例子，當一個10bits的信息被處理時，量子計算機實際上操作了2^10個態！
在如今這個信息時代，網上交易和電子商務的浪潮正席卷全球，從政府至平民百姓，都越來越依賴於電腦和網絡係統。與此同時，電子安全的問題也顯得越來越嚴峻，誰都不想黑客們大搖大擺地破解你的密碼，侵入你的係統篡改你的資料，然後把你銀行裏的存款提得精光，這就需要我們對私隱資料執行嚴格的加密保護。目前流行的加密算法不少，很多都是依賴於這樣一個靠山，也即所謂的“大數不可分解性”。大家中學裏都苦練過因式分解，也做過質因數分解的練習，比如把15這個數字分解成它的質因數的乘積，我們就會得到15=5×3這樣一個唯一的答案。
問題是，分解15看起來很簡單，但如果要分解一個很大很大的數，我們所遭遇到的困難就變得幾乎不可克服了。比如，把10949769651859分解成它的質因數的乘積，我們該怎麼做呢？糟糕的是，在解決這種問題上，我們還沒有發現一種有效的算法。一種笨辦法就是用所有已知的質數去一個一個地試，最後我們會發現10949769651859＝4220851×2594209（數字取自德義奇的著作TheFabricofReality），但這是異常低效的。更遺憾的是，隨著數字的加大，這種方法所費的時間呈現出幾何式的增長！每當它增加一位數，我們就要多費3倍多的時間來分解它，很快我們就會發現，就算計算時間超過宇宙的年齡，我們也無法完成這個任務。當然我們可以改進我們的算法，但目前所知最好的算法（我想應該是GNFS）所需的複雜性也隻不過比指數性的增長稍好，仍未達到多項式的要求（所謂多項式，指的是當處理數字的位數n增大時，算法所費時間按照多項式的形式，也就是n^k的速度增長）。
所以，如果我們用一個大數來保護我們的秘密，隻有當這個大數被成功分解時才會泄密，我們應當是可以感覺非常安全的。因為從上麵的分析可以看出，想使用“暴力”方法，也就是窮舉法來破解這樣的密碼幾乎是不可能的。雖然我們的處理器速度每隔18個月就翻倍，但也遠遠追不上安全性的增長：隻要給我們的大數增加一兩位數，就可以保好幾十年的平安。目前最流行的一些加密術，比如公鑰的RSA算法正是建築在這個基礎之上。
但量子計算機實現的可能使得所有的這些算法在瞬間人人自危。量子計算機的並行機製使得它可以同時處理多個計算，這使得大數不再成為障礙！1994年，貝爾實驗室的彼得肖（PeterShor）創造了一種利用量子計算機的算法，可以有效地分解大數（複雜性符合多項式！）。比如我們要分解一個250位的數字，如果用傳統計算機的話，就算我們利用最有效的算法，把全世界所有的計算機都聯網到一起聯合工作，也要花上幾百萬年的漫長時間。但如果用量子計算機的話，隻需幾分鍾！一台量子計算機在分解250位數的時候，同時處理了10^500個不同的計算！≡本≡作≡品≡由≡思≡兔≡網≡提≡供≡線≡上≡閱≡讀≡