Shor算法核心是利用數(shù)論中的一些定理，將大多數(shù)因式分解轉(zhuǎn)化為求某一個函數(shù)的周期，其基本思想是：利用量子并行性通過一步計算獲得所有的函數(shù)值，然后通過測量函數(shù)得到相關(guān)聯(lián)的函數(shù)自變量的疊加態(tài)，并對其進行量子快速傅立葉變換。其實質(zhì)就是將大數(shù)因子分解轉(zhuǎn)化為量子FFT在多項式步驟內(nèi)完成的求一個函數(shù)的周期問題。由于在量子環(huán)境下可以以極高的效率實現(xiàn)量子傅立葉變換，從而使對大多數(shù)因子分解成為可能。

Shor算法之所以能進行大數(shù)因數(shù)分解，是因為量子計算具有高度并行能力。這種高度并行能力來源于子計算機的基本單元-量子比特，它具有奇妙的性質(zhì)，這種性質(zhì)必須用量子力學(xué)來解釋，因此稱為量子特性。

1、量子比特：在經(jīng)典計算機中，運算的基本單元是比特，它的基本狀態(tài)是二值布爾邏輯狀態(tài)0或在量子計算機中，運算的基本單元是量子比特（q-bit），它的基本狀態(tài)是兩種狀態(tài)的疊加，如果規(guī)定原子在基態(tài)時記為∣0＞，在激發(fā)態(tài)時記為∣1＞，則原子除了保持上述兩種狀態(tài)之外，還可以處于兩種態(tài)的線性疊加，記為∣Φ＞a∣0＞+b∣1＞。一個量子比特能同時表示0和1，兩個量子比特能同時表示00、01、10、11，三個比特能同時表示8個二進制數(shù)000、001、011、100、101、110及111，更多的以此類推。

2、量子寄存器：存儲一系列量子比特的體系稱為量子寄存器。假如有一個由三個量子比特構(gòu)成的寄存器，則在某一時刻一個量子寄存器可以存儲8個狀態(tài)，而不是經(jīng)典的計算機中有1個狀態(tài)。
例如：若要求一個函數(shù)f(n),n=0－7,如果是用量子計算機來求解則在原理上要簡潔的多，只需要用一個量子存儲器，把各q-bit制備到（∣0＞+∣1）/（√2）態(tài)上就一次完成了對8個數(shù)的賦值，此時存儲器成為疊加態(tài)∣Φ＞，然后對其運行進行相應(yīng)的幺正變換已完成函數(shù)f(n)的功能，變換后的存儲器內(nèi)就保存了所需的8個結(jié)果。這種同時進行的多態(tài)操作，即量子并行計算，正是量子計算的奧秘所在。也是Shor算法的特殊所在。

ice

收藏 海報分享