3.5

Shor

算法給定一個(gè)正和(奇)數(shù)N，求出它的兩個(gè)質(zhì)數(shù)因子。例如：給出15，可求得兩個(gè)因子

3

和5給出21，可求得兩個(gè)因子

3

和7給出143，可求得兩個(gè)因子

11

和13plete問(wèn)題，可能是NP-hard問(wèn)題1

log

2

NN

22NP問(wèn)題，但還不是若試用1

~

N

去除，需要RSA

系統(tǒng)任意兩個(gè)質(zhì)數(shù)p,q算出積n=pq隨機(jī)找一個(gè)和Ｘ＝(p-1)(q-1)互質(zhì)的小奇數(shù)，e選取d,使de=1(mod(X))，d和n也互質(zhì)公鑰

P

=

(e,n)，密鑰

S

=

(d,n)加密

E(M)

= Me(mod

n)D(E(M))

=E(M)d(mod

n)Modular

exponentiation給定2個(gè)正整數(shù)x和N沒(méi)有公因子，X<N，當(dāng)一個(gè)最小正整數(shù)r

滿足xr

=1(modN)，xrmodN=1就定義x

modulo

N

的階是r。例如：求5

modulo

21

的階51

/

2152

2553

12554

62555

312556

15625除以21，余數(shù)是5余數(shù)是4余數(shù)是20余數(shù)是13余數(shù)是17余數(shù)是1求最大公約數(shù)的

得算法：定理1：如果被除數(shù)和除數(shù)都能被同一個(gè)整數(shù)整除，那么余數(shù)也能被該整數(shù)整除。定理2：如果一個(gè)整數(shù)除以另一個(gè)整數(shù)的余數(shù)不等于0，則這兩個(gè)數(shù)的最大公約數(shù)等于除數(shù)與余數(shù)的最大公約數(shù)。N1

k0

N2

R1N2

k1R1

R2得算法就是輾轉(zhuǎn)相除，需要次數(shù)2

log2

N1

，是有效算法。7

modulo

15

的階71

/157273

49

343

240174除以15，余數(shù)是7余數(shù)是4余數(shù)是13余數(shù)是11

501

48A

xr

/

2B

xr

/

21

74

/

21

74

/

2令if xr

/2

mod

N

1求A和N的最大公約數(shù),B和N的最大公約數(shù),定義為C

(A,

N)

D

(B,

N)N

C

D分解N=15，先隨機(jī)取x,1<x<N,例如x=7求隨機(jī)數(shù)階的量子算法求階對(duì)經(jīng)典計(jì)算是一個(gè)難解問(wèn)題，Shor的發(fā)現(xiàn)就在于找到了求階的有效量子算法N

2

q

2N

2假設(shè)運(yùn)算器由兩個(gè) 器組成，第一個(gè)由L個(gè)量子位組成存放初始輸入x值，第二個(gè)用于存放函數(shù)值，fa,N

(x)器最多也只能有L由于fa,N

(x)不可能大于N，第二個(gè)量子位。設(shè)要分解的數(shù)為N，取并且：q

2L12L

11

2L

/

2

x0

L和Simon算法相同，第一步首先在第一器用作用到

出

個(gè)數(shù)的等全加態(tài)：2LH

Lx0保持第二器仍處在態(tài)0

L

，下一步計(jì)算函數(shù)fa,N

(x)

ax

(mod

N)器，得到兩個(gè)器的糾纏并把計(jì)算結(jié)果寫(xiě)進(jìn)第二態(tài)：12L

/

2

x

ax

(mod

N

)2L

1x01

x

xL1

2

x

2L1

L2L2

...

x0如果，x

2L將x展開(kāi)為二進(jìn)制數(shù)表示：從而有L1ax

(mod

N)

(a2

)xx2L2

x(a

)L1L2

...(a)

0

(mod

N)注意到所以，中間j

一式可以取

j

=

0

到

j

=

L-1，每當(dāng)

xj

1

時(shí)，就乘上

a2

，

最多用L-1個(gè)計(jì)算步。j1

(a2

)2ja2下一步是執(zhí)行第二 器態(tài)到計(jì)算基上的投影測(cè)量。假設(shè)測(cè)量結(jié)果是z，z

{ax

(mod

N)}設(shè)

fa,N

(x)

的周期為r,

若對(duì)某個(gè)最小的

l

<

r,

有z

al

(mod

N)那么對(duì)所有整數(shù)j，都有al

a

jr

l

(mod

N)于是，向計(jì)算基投影測(cè)量第二量子位，將在第一

器投影出：的態(tài)|z>等權(quán)z

l,l

r,l

2r,...,l

Ar加態(tài)。這里A是比（2L-1）/r小的最大整數(shù)。l值決定于z,由測(cè)量結(jié)果隨機(jī)決定，稱為偏移量：02133

7

11

...所以，測(cè)量第二器后，第一

器的態(tài)為，Aj

0A

1

1

jr

ll例如N=15，a=712L

/

21x02L

/

2

x

ax

(mod

N

)2L

12

第二(

0

1

1

7

2

4

3

13器僅有四個(gè)不同的態(tài)，測(cè)量第二器14713第一

器的態(tài)：0

4

8

...2

6

10

...1

5

9

...

4

1

5

7

...)1

,

7

, 4

,

13第一器的態(tài)具有共同形式，j

0jr

lA

1

1

Al有關(guān)周期r的信息包含在第一

器的態(tài)中，對(duì)第一器的測(cè)量由于l不確定，一般不能得到r。為了消除l，對(duì)第一 器態(tài)作量子Fourier變換，可以把l變成一個(gè)相位因子，不出現(xiàn)在測(cè)量結(jié)果中。分立變換（discrete

FT）x0

,

x1,...,

xN

1輸入一組復(fù)矢量k通過(guò)變換

y

expN

11

2ikj

x

N

jNj

0輸出一組復(fù)矢量（系數(shù)）y0

,

y1,...,

yN

11kx

kj

yN2iN

1j

0Nexp

j逆變換變換可以看成矩陣乘矢量，正反變換是互為逆矩陣，矩陣的計(jì)算需要N2

步21

y1

a11

a12...

y

a

2

...

...

y

a

k

k1aa1k

x1

x

2

...

x

kk

k

快速奇數(shù)和偶數(shù)j分離，如果N為偶數(shù)變換（FFT）221yk

N

/

2

N

/

2

N

1

N

1kl

xexp

2i

2iexp

2iN2l

12lkl

x

exp

N

k

l

0

l

0可以看成2個(gè)N/2矩陣的計(jì)算，需要N2/2

步，步驟減少了一半，如果N/2是偶數(shù)，可以再次分離。操作N=

2n

次，把操作次數(shù)從N2

降低到NlogN量子 變換（QFT）12iexpN

1k

0j

NNjkkN維空間算符對(duì)于任意態(tài)矢量N

1N

1

xjj

0j

yk

kk

0這個(gè)變換是幺正變換，因?yàn)楸３衷瓉?lái)態(tài)的歸一性量子變換（QFT）2N

12k

0N

1

N

1

N

1N

12*k

0

j

0

l

0l

01

N

1

N

1

1N(

j

l)k

ykNk

0

j

0

2j

lx

x

exp2ilx

N

jx

expjk

N

exp

2ijlN(

j

l)k

NN

1k

0

1

N2iexpN

1QFTk

U

kj

kj

Nk

00

1

1

011/

211/

21120

21122UQFTUQFT1

e2

i

0

j

/2j

0j

e2

i1

j

/

2j

0j

j

2n1

j

2n21

2j

:

j

j1

j2

...

jnnv1nvn...

j

20

vj

2n-qubit變換1

2i2n

1k

02n

/2nj

exp

2jk

k變換0

...

2n

1

n-qubit量子對(duì)于n-qubit，N=2n

，計(jì)算的基是任意一個(gè)基表示為二進(jìn)制序列分?jǐn)?shù)的二進(jìn)制表示221l

l

1

m

l

l

10.

j

j

...

j

j

2

jm...

j

2ml

1n-qubit量子變換11

11

n1

111k

...k2n

/22...exp

2exp

22n

/

22n

/

212n

/2nnnnlk1

0

kn

0... exp

2i

j

k

2

l

1nn

1

llk

0k

0

l

1

ijk

2

kl

1

llijk

2

klnllj

l

l

1

k

0l

0

exp2

ij2

1l

1

l

把k的二進(jìn)制展開(kāi)代入j2lnv1j

2nv

l

v...

j

j1

j2

...j

nl

.

jnl

1

jnl

2

n整數(shù)部分沒(méi)有貢獻(xiàn)，因?yàn)閑i

2

k

1

e2

i0.

jn1

jn

e2

i0.

j1

j2

...

jn1101

0

e2

i0.jn221

...

02n

/21nnj

1exp2n

1

2ij

2n

/22njk

kk

0121...2222nnH

nxn

0

1

0

1

0

1

x

0

exp

i

j

2k

k

k

k1

21

2121

121

2

1

2k

0

k

011

2k

0

k

01

122j

12

1

1

12

2

1lk

22l

k1k2lijk

2kl2

k

0

k

0

l

1exp

2exp

ijk

exp

i

jk

k

k

2

2

lk1

0

k2

0exp

i

j

l

1

2

1

1

1

例如n=2n-qubit量子變換

k

1

0e2

i

2Rk

0e2

i0.

j1

e2

ij1

21

e2

i0.

j1

j2

...

jn1

12

11

00

1

...

01n2n

/2因此，QFT就是簡(jiǎn)單的相移，每個(gè)1態(tài)獲得一個(gè)位相因子

e2

i0.jn

e2

i0.

jn1

jnnj

Rk控制目標(biāo)

(1)

j1

H j1

j2

...

jn

1

012

i0.

j

e

1

j2

...

jn2n-qubit量子變換

e2

i0.

j1

j2

...

jn

e2

i0.jn101221

01

...

02n

/2

e2

i0.

jn1

jn1nnj

11

2222

n2

i0.

jC

R

1

0

e

1

j

...

j2

i0.

j

j

e

1

j2

...

jn

1

0k

1

01

j2

...

jn122

3221

2

n2

i

0.

j

j

...

jk

k2

i0.

jC

R

C

R

...

1

0n

e

1

j

...

j

e

Hj1j2jnR2RnHR2RnH邏輯操作:n+n-1+…1~n23-qubit量子變換

e2

i

0.

j3

e2

i

0.

j2

j3

e2

i

0.

j1j2

j31011

022

03323/

211j

11

22

31

j

j2

322

i0.

jC

R

1

0

e2

22

i0.

j

j

e

1

j

j

1

02

311

2

32

32

322

i

0.

j

e

1

j

jC

R

C

R

1

0122

i

0.

j

j

j

0

e

1

j

jj1

Hj2j3R2R3HR2H

ei

2

0.

j1

j2

j30101

ei

2

0.

j2

j301

ei

2

0.

j30kR

1

2i

2

k

0

e第一j

02L器的態(tài)量子Fourier變換，初始

Ain

r

jr

l給出：2L被r整除：2L

1

e2

ixy

/

2Ly

012L

/2QFTU

x

y2L

1

y

02L2LLLLAout2L

1

y

0Are2i

(

jr

l

)

y

/

2j

0yre2ily

/2e2ijry

/

2j

0yk

0Lk

2outrrr

1

1

e2

ilk

/

r現(xiàn)在將測(cè)得2Ly

kr測(cè)得y后,由y/2L的連分式可以求出r。如果2L不能被r整除,同樣可以證明利用連分式4可以有

2

log

N

的概率得到N的一個(gè)因子.重復(fù)log

N次,可以得到任意高成功率的分解.11

1

2

1

2

12

1531

2

5

2

13

132

332

1

2211

1尋找階的步驟輸入：一個(gè)和數(shù)N=2L，需要qubit數(shù)目2L+1+log(2+1/2d)輸出：最小r，xrmod(N)=1計(jì)算時(shí)間：O(L3)步操作，成功機(jī)率O(1)步驟：1.

初始化2.

疊加3.變換4.

對(duì)前寄存器作逆變換5.

測(cè)量前寄存器6.

用連續(xù)分?jǐn)?shù)算法，r0

112t2t

1

j

1j

0112st2t

1

j x

j

mod

N

j

0tr2r

1

2t

1e2

isj

/

rs

0

j

0j

ur

1s

0s

1

s

/

r

urs

/

r大數(shù)分解算法輸入：一個(gè)和數(shù)N輸出：N的一個(gè)非平庸因子計(jì)算時(shí)間：O((logN)3)步操作，成功機(jī)率O(1)步驟：如果N是偶數(shù)，因子是2檢查N=an？如果是，因子是a隨機(jī)選取x，1

<

x

<

N-1,

檢查

(x,N)

>

1?,如果是，因子是

(x,N)調(diào)用求周期子程序找到xmodN的階如果r是奇數(shù)，重選x，如果r是偶數(shù)，檢查xr/2modN=-1？如果成立重選x，不成立計(jì)算

(xr/2-1,N)和

(xr/2+1,N)，檢查這兩者是否N的因子，如果是成功。不是，程序失敗。量子相位估計(jì)量子 在量子算法中起關(guān)鍵作用，實(shí)際上量子信息的許多超出經(jīng)典信息的新功能都可歸結(jié)為利用了量子

，而量子

決定于相干量子態(tài)的相位。量子 變換的一個(gè)重要應(yīng)用就是用于量子態(tài)相位估計(jì)。的本征值是e2

i

，即其中，0

1值是未知的。假設(shè)能在計(jì)算機(jī)中態(tài)態(tài)執(zhí)行控制U，控制

21

，控制U

22

，可以得到

值的大小，精確到L位。假設(shè)算符U是n量子位Hilbert空間上的幺正變換，U算符對(duì)應(yīng)本征矢量U

e2i

，能夠?qū)@個(gè)利用 變換進(jìn)行量子態(tài)相位估計(jì)，需要2個(gè)量子 器。第一

器的量子位數(shù)目L取決于希望估計(jì)

的精度和相位估計(jì)成功的概率，第二器量子位數(shù)目等于要估計(jì)態(tài)的維度。00...0

，第二初始 第一 器處在態(tài) 器處于HHHHU

20U

21U

22L1U

2………

…0

ei

2

(2L1

)01

ei

2

(22

)

ei

2

(21

)

ei

2

(20

)010011

ei

2

20

1

)2L

1ei

2

yy012L/2(

0

ei

2

2L1

1

)(

0

ei

2

2L2

1

)...(

012L/2y第一 器處在態(tài)假如

可以嚴(yán)格用L個(gè)量子位表示為

0.12...L，上式可以重新寫(xiě)為1

2

Li

2

0.

...L L1

L

ei

2

0.

ei

2

0.

12L/2(

0 1

)(

0 1

)...(

0

e1

)這正好是相位態(tài)的

變換。

12...n對(duì)這個(gè)態(tài)執(zhí)行逆變換，輸出態(tài)就是

12...n

，然后進(jìn)行計(jì)算基上的投影測(cè)量就得到相位角。量子搜索算法(Grover算法)有N(=2n)個(gè)元素，標(biāo)為0-N-1，假設(shè)有M個(gè)解，這些解有一個(gè)特征函數(shù)f(x)f

(x)

10X是解X不是解通常尋找一個(gè)解，需要計(jì)算一次f(x)，如果M=1，經(jīng)典算法平均需要N/2次計(jì)算量子算法，f(x)對(duì)應(yīng)于一個(gè)幺正變換。定義O

x

q

x q

f

(x)X是索引比特，q是數(shù)據(jù)，O算符作用后x不變，q翻轉(zhuǎn)如果是解，否則不變量子搜索算法(Grover算法)O作用于

(1)

f

(

x)

x20

12f

(x)

f

(x)20

1O

x

x要看到需要不考慮q，O在解的索引上做一個(gè)負(fù)號(hào)。后面次O