说明量子信息sqc

3.5

Shor

算法给定一个正和(奇)数N，求出它的两个质数因子。例如：给出15，可求得两个因子

3

和5给出21，可求得两个因子

3

和7给出143，可求得两个因子

11

和13plete问题，可能是NP-hard问题1

log

2

NN

22NP问题，但还不是若试用1

~

N

去除，需要RSA

系统任意两个质数p,q算出积n=pq随机找一个和Ｘ＝(p-1)(q-1)互质的小奇数，e选取d,使de=1(mod(X))，d和n也互质公钥

P

=

(e,n)，密钥

S

=

(d,n)加密

E(M)

= Me(mod

n)D(E(M))

=E(M)d(mod

n)Modular

exponentiation给定2个正整数x和N没有公因子，X<N，当一个最小正整数r

满足xr

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

modulo

N

的阶是r。例如：求5

modulo

21

的阶51

/

2152

2553

12554

62555

312556

15625除以21，余数是5余数是4余数是20余数是13余数是17余数是1求最大公约数的

得算法：定理1：如果被除数和除数都能被同一个整数整除，那么余数也能被该整数整除。定理2：如果一个整数除以另一个整数的余数不等于0，则这两个数的最大公约数等于除数与余数的最大公约数。N1

k0

N2

R1N2

k1R1

R2得算法就是辗转相除，需要次数2

log2

N1

，是有效算法。7

modulo

15

的阶71

/157273

49

343

240174除以15，余数是7余数是4余数是13余数是11

501

48A

xr

/

2B

xr

/

21

74

/

21

74

/

2令if xr

/2

mod

N

1求A和N的最大公约数,B和N的最大公约数,定义为C

(A,

N)

D

(B,

N)N

C

D分解N=15，先随机取x,1<x<N,例如x=7求随机数阶的量子算法求阶对经典计算是一个难解问题，Shor的发现就在于找到了求阶的有效量子算法N

2

q

2N

2假设运算器由两个 器组成，第一个由L个量子位组成存放初始输入x值，第二个用于存放函数值，fa,N

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

(x)不可能大于N，第二个量子位。设要分解的数为N，取并且：q

2L12L

11

2L

/

2

x0

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

出

个数的等全加态：2LH

Lx0保持第二器仍处在态0

L

，下一步计算函数fa,N

(x)

ax

(mod

N)器，得到两个器的纠缠并把计算结果写进第二态：12L

/

2

x

ax

(mod

N

)2L

1x01

x

xL1

2

x

2L1

L2L2

...

x0如果，x

2L将x展开为二进制数表示：从而有L1ax

(mod

N)

(a2

)xx2L2

x(a

)L1L2

...(a)

0

(mod

N)注意到所以，中间j

一式可以取

j

=

0

到

j

=

L-1，每当

xj

1

时，就乘上

a2

，

最多用L-1个计算步。j1

(a2

)2ja2下一步是执行第二 器态到计算基上的投影测量。假设测量结果是z，z

{ax

(mod

N)}设

fa,N

(x)

的周期为r,

若对某个最小的

l

<

r,

有z

al

(mod

N)那么对所有整数j，都有al

a

jr

l

(mod

N)于是，向计算基投影测量第二量子位，将在第一

器投影出：的态|z>等权z

l,l

r,l

2r,...,l

Ar加态。这里A是比（2L-1）/r小的最大整数。l值决定于z,由测量结果随机决定，称为偏移量：02133

7

11

...所以，测量第二器后，第一

器的态为，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器仅有四个不同的态，测量第二器14713第一

器的态：0

4

8

...2

6

10

...1

5

9

...

4

1

5

7

...)1

,

7

, 4

,

13第一器的态具有共同形式，j

0jr

lA

1

1

Al有关周期r的信息包含在第一

器的态中，对第一器的测量由于l不确定，一般不能得到r。为了消除l，对第一 器态作量子Fourier变换，可以把l变成一个相位因子，不出现在测量结果中。分立变换（discrete

FT）x0

,

x1,...,

xN

1输入一组复矢量k通过变换

y

expN

11

2ikj

x

N

jNj

0输出一组复矢量（系数）y0

,

y1,...,

yN

11kx

kj

yN2iN

1j

0Nexp

j逆变换变换可以看成矩阵乘矢量，正反变换是互为逆矩阵，矩阵的计算需要N2

步21

y1

a11

a12...

y

a

2

...

...

y

a

k

k1aa1k

x1

x

2

...

x

kk

k

快速奇数和偶数j分离，如果N为偶数变换（FFT）221yk

N

/

2

N

/

2

N

1

N

1kl

xexp

2i

2iexp

2iN2l

12lkl

x

exp

N

k

l

0

l

0可以看成2个N/2矩阵的计算，需要N2/2

步，步骤减少了一半，如果N/2是偶数，可以再次分离。操作N=

2n

次，把操作次数从N2

降低到NlogN量子 变换（QFT）12iexpN

1k

0j

NNjkkN维空间算符对于任意态矢量N

1N

1

xjj

0j

yk

kk

0这个变换是幺正变换，因为保持原来态的归一性量子变换（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量子对于n-qubit，N=2n

，计算的基是任意一个基表示为二进制序列分数的二进制表示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的二进制展开代入j2lnv1j

2nv

l

v...

j

j1

j2

...j

nl

.

jnl

1

jnl

2

n整数部分没有贡献，因为ei

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就是简单的相移，每个1态获得一个位相因子

e2

i0.jn

e2

i0.

jn1

jnnj

Rk控制目标

(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器的态量子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现在将测得2Ly

kr测得y后,由y/2L的连分式可以求出r。如果2L不能被r整除,同样可以证明利用连分式4可以有

2

log

N

的概率得到N的一个因子.重复log

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

1

2

1

2

12

1531

2

5

2

13

132

332

1

2211

1寻找阶的步骤输入：一个和数N=2L，需要qubit数目2L+1+log(2+1/2d)输出：最小r，xrmod(N)=1计算时间：O(L3)步操作，成功机率O(1)步骤：1.

初始化2.

叠加3.变换4.

对前寄存器作逆变换5.

测量前寄存器6.

用连续分数算法，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大数分解算法输入：一个和数N输出：N的一个非平庸因子计算时间：O((logN)3)步操作，成功机率O(1)步骤：如果N是偶数，因子是2检查N=an？如果是，因子是a随机选取x，1

<

x

<

N-1,

检查

(x,N)

>

1?,如果是，因子是

(x,N)调用求周期子程序找到xmodN的阶如果r是奇数，重选x，如果r是偶数，检查xr/2modN=-1？如果成立重选x，不成立计算

(xr/2-1,N)和

(xr/2+1,N)，检查这两者是否N的因子，如果是成功。不是，程序失败。量子相位估计量子 在量子算法中起关键作用，实际上量子信息的许多超出经典信息的新功能都可归结为利用了量子

，而量子

决定于相干量子态的相位。量子 变换的一个重要应用就是用于量子态相位估计。的本征值是e2

i

，即其中，0

1值是未知的。假设能在计算机中态态执行控制U，控制

21

，控制U

22

，可以得到

值的大小，精确到L位。假设算符U是n量子位Hilbert空间上的幺正变换，U算符对应本征矢量U

e2i

，能够对这个利用 变换进行量子态相位估计，需要2个量子 器。第一

器的量子位数目L取决于希望估计

的精度和相位估计成功的概率，第二器量子位数目等于要估计态的维度。00...0

，第二初始 第一 器处在态 器处于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第一 器处在态假如

可以严格用L个量子位表示为

0.12...L，上式可以重新写为1

2

Li

2

0.

...L L1

L

ei

2

0.

ei

2

0.

12L/2(

0 1

)(

0 1

)...(

0

e1

)这正好是相位态的

变换。

12...n对这个态执行逆变换，输出态就是

12...n

，然后进行计算基上的投影测量就得到相位角。量子搜索算法(Grover算法)有N(=2n)个元素，标为0-N-1，假设有M个解，这些解有一个特征函数f(x)f

(x)

10X是解X不是解通常寻找一个解，需要计算一次f(x)，如果M=1，经典算法平均需要N/2次计算量子算法，f(x)对应于一个幺正变换。定义O

x

q

x q

f

(x)X是索引比特，q是数据，O算符作用后x不变，q翻转如果是解，否则不变量子搜索算法(Grover算法)O作用于

(1)

f

(

x)

x20

12f

(x)

f

(x)20

1O

x

x要看到需要不考虑q，O在解的索引上做一个负号。后面次O