補充個例子，普通的FFT，能做到的複雜度是O（NLogN），但是在量子計算的時候，QFT可以做到Log^2N……（也就是平行計算，就好象對於排序網路來說，把一個數列排序的複雜度也是LogN，QFT可以做到類似的事情，而且在一定程度上，看起來能做的比現在的平行計算要好，不過目前來看嘛……）Shor演算法利用這點，首先把質因數分解轉換成函數週期問題，假如有隨機一個a，使得a，N互質，然後求的週期r。用QFT求r（FFT不是不行，但是這樣複雜度就太高了，因為有個指數，QFT一個Log直接把指數吃了……）。至於這個怎麼做……如果題主有興趣自己翻論文吧，兩句話寫不完的……然後這裡就得到一個r，之後，如果r不是偶數，就放棄它，重新算。得到這樣一個r，就可以分解N了。令，則。======================================================================這麼做的話，具體的證明……顯然，如果我們有那麼，他的週期r就意味著代入調整就會有，然後……上面的式子的兩個項（+1-1的）就隱含了兩個包含N因子的數字……所以他和N的最大公約數就會是N的一個因數……

這東西現在還是傻大黑粗的原始形態，你估計也不想看見。現在比最早的計算機艾尼亞克快10-100倍，根本沒法用。艾尼亞克是個三十噸的大傢伙。它的原理倒是比較簡單，就是用光子代替了電子傳輸資訊，用電子只有兩種狀態，高電平代表1，低電平代表0.用光子就好很多了，一個光子可以傳遞幾個甚至幾十個狀態。計算速度就從2^n變成了10^n或者100^n，同樣的傳輸單位傳達的資訊和計算的資訊增大多少應該很明顯吧。這種計算機的原理和演算法已經研究很多年了，都是虛擬研究，現在才有了象點樣的實物，應該會發展很快的。