本講主要內(nèi)容1量子傅里葉變換2相位估計(jì)3求階4Shor算法5

Shor算法實(shí)現(xiàn)RnH

Rn-2

Rn-

1H—

10)+e220-·|1)10)+e2/2--·|1)R?10)+e2-Qn-Ln|I)H-10)+22-%i|)Li)

H

R?Li:Ln-1)一Ln—Rn-11量子傅里葉變換[1]Michael

A.Nielsen

&Isaac

L.,Quantum

Computation

and

QuantumInformation,Cambridge

University

Press,20102離散傅里葉變換Onesuch

transformation

is

the

discreteFourier

transform.In

the

usualmathematical

notation,the

discrete

Fourier

transform

takes

as

input

a

vector

of

complex

numbers,xo,…,xN-1where

the

length

N

of

the

vector

is

a

fixed

parameter.It

outputs

the

transformed

data,a

vector

of

complex

numbers

yo,…,YN-1,defined

by(n=0:N-1)(5.1)3量子傅里葉變換The

quantum

Fourier

transform

is

exactly

the

same

transformation,although

the

conventional

notation

for

the

quantum

Fourier

transform

is

somewhat

different.Thequantum

Fourier

transform

on

an

orthonormal

basis10>N-1)is

defined

to

be

alinear

operator

with

the

following

action

on

the

basis

states,where

the

amplitudes

yk

are

the

discrete

Fourier

transform

ofthe

amplitudes

x;.It

is

notobviousfrom

the

definition,but

this

transformation

is

a

unitary

transformation,and

thuscanbeimplementedasthedynamics

for

a

quantum

computer.

Ve

shall

demonstrateEquivalently,the

action

on

an

arbitrarystate

may

be

written酉變換(5.2)(5.3)4Inthefollowing,we

takeN=2”,where

n

is

some

integer,and

the

basis|0),...,|2n-

1〉

is

the

computationalbasis

for

an

n

qubit

quantum

computer.It

is

helpful

to

write

thestatelj)usingthebinaryrepresentationj=jij2…jn.Moreformally,j=j12n-11+j2n-2+…+jn2?.Itisalso

convenient

to

adopt

the

notation

0.jijt+1…jm

to

representthe

binary

fraction

ji/2+jl+1/4+…+jm/2m-I+1.With

a

little

algebra

the

quantum

Fourier

transtorm

can

be

given

the

following

useful

product

representation:QFT

(續(xù))證明見下頁(yè)5QFT

(續(xù))The

equivalence

of

the

product

representation(5.4)and

the

definition(5.2)follows

from

someelementary

algebra:(5.5)(5.6)(5.7)(5.8)(5.9)(510)——10)+e2π20i…n1〉—|0)+e2π20,/2m/n|1〉R?|0)+e2πO.jn-17n|1)10)+2H?in|1)Figure

5.1.Efficient

circuit

for

the

quantum

Fourier

transform.This

circuit

is

easily

derived

from

the

productrepresentation(5.4)for

the

quantum

Fourier

transform.Not

shown

are

swap

gates

at

the

end

ofthe

circuit

whichreverse

the

order

of

the

qubits,or

normalization

factors

of

1/√2in

the

output.QFT的實(shí)現(xiàn)in-1〉in)Rn-2

Rn-1-Rn-1

RnR?Li2)-Li〉HHH7…ToseethatthepicturedcircuitcomputesthequantumFouriertransform,considerwhathappenswhenthestate

|j?…jn〉

isinput.ApplyingtheHadamardgatetothefirstbit

producesthestateWe

continue

applying

the

controlled-R?,R?through

Rn

gates,each

ofwhich

adds

anextrabittothephaseof

theco-efficientof

thefirst

|1).Attheendof

thisprocedurewe

havethe

statesince

e2πi?.i=-1

whenj?=1,and

is+1

otherwise.Applying

the

controlled-R?gate

producesthestateNext,we

perform

a

similarprocedure

on

the

second

qubit.The

Hadamard

gate

puts

usandthecontrolled-R?throughRn-1gates

yield

the

state(5.15)(5.16)in

the

state(5.12)(5.13)(5.14)8Box5.1:ThreequbitquantumFouriertransformForconcretenessitmayhelptolookattheexplicitcircuit

for

the

three

qubit

quantumFouriertransform:H

S

TH

SHRecallthat

SandTarethephaseandπ/8gates(seepagexxiii).As

amatrixthe

quantumFouriertransforminthisinstancemaybewrittenoutexplicitly,usingw=e2πi/8=√i,as3qubits

QFT(5.19)92相位估計(jì)[1]Michael

A.Nielsen

&Isaac

L.,Quantum

Computation

and

QuantumInformation,Cambridge

University

Press,201010問題的提出The

Fourier

transformis

the

key

toageneral

procedure

knownas

phaseestimation,which

in

turn

is

the

key

for

many

quantum

algorithms.

Suppose

a

unitary

operator

Uhas

an

eigenvector

|u〉with

eigenvalue

e2πi,where

the

value

of

φ

is

unknown.The

goalLofthephaseestimationalgorithmistoestimateφ

.To

perform

the

estimation

we

assume要估計(jì)的相位11U2-1

|u)Figure5.2.Thefirststageof

thephaseestimation

procedure.Normalizationfactorsof1/√Z

have

beenomitted,onthe

right.

Cu(10>+|1〉)|u〉=Cu|0>|u〉+Cu|1〉|u〉相位估計(jì)：第1步H,Controlled

U10)+e2mπi2-14)1)10)

+e2m=(22)1)10>+e2m=i2)|1)10)+e2mi(2°9)1)=|0>|u〉+|1〉U|u〉=|0>|u〉+|1〉e2πi|u〉=(|0>+e2πiφ|1〉)|u〉|0〉H|0)

H10)—HHFirstregister

t

qubits12Thesecondstageof

phaseestimationistoapply

the

inverse

quantum

Fourier

transform

on

the

first

register.This

is

obtained

by

reversing

the

circuit

for

the

quantum

Fouriertransformintheprevious

section(Exercise

5.5),and

canbe

done

in

Θ(t2)steps.Thethird

and

final

stage

ofphase

estimation

is

to

read

out

the

state

ofthe

first

register

bydoingameasurementinthecomputationalbasis.Wewillshowthatthisprovides

apretty

good

estimate

ofφ.An

overall

schematic

ofthe

algorithm

is

shown

in

Figure

5.3.To

sharpen

our

intuition

as

to

why

phase

estimation

works,suppose

φ

may

be

ex-pressedexactlyint

bits,asφ=0.1…φt.Then

the

state(5.20)resulting

from

the

firststage

of

phase

estimation

may

be

rewritten相位估計(jì)：第2步IQFT13相位估計(jì)過程H

FTUjFigure5.3.Schematic

of

the

overall

phase

estimation

procedure.The

topt

qubits(the'I'denotes

a

bundle

ofwires,as

usual)are

the

first

register,and

the

bottom

qubits

are

the

second

register,numbering

as

many

as

required

to

perform

U.|u)is

an

eigenstate

of

U

with

eigenvalue

e2πiφ.The

output

of

the

measurement

is

anapproximation

toφaccurate

to

bits,with

probability

of

success

at

least1-e.i)14相位估計(jì)算法Algorithm:QuantumphaseestimationInputs:

(1)A

black

box

wich

performs

a

controlled-Ui

operation,for

integer

j,qubits

initialized

to

|0).Outputs:

Ann-bitapproximationutoφu

·Runtime:

O(t2)operations

and

one

call

to

controlled-Ui

black

box.Succeeds

with

probabilityatleast

1-E.initial

statecreatesuperpositionapply

black

boxresult

ofblack

boxapply

inverse

Fourier

transformmeasure

first

register1.

|0>|u)2.3.4.

→

|Pu>|u〉5.

→u(2)an

eigenstate

|u)of

Uwith

eigenvalue

e2πiu,and(3

Procedure:15以|0)作為初態(tài)將待測(cè)量子門放入相位估計(jì)算法中，以較大概率得到了態(tài)|1101>,以態(tài)|1}作為初態(tài)將待測(cè)量子門放入相位估計(jì)算

法中，以較大概率得到了態(tài)|1010),則θ/π應(yīng)該為?(注意態(tài)的讀取順序)O

A.5/16○B(yǎng).11/16OD.11/4司南杯練習(xí)題163求階[1]Michael

A.Nielsen

&Isaac

L.,Quantum

Computation

and

QuantumInformation,Cambridge

University

Press,201017problem

is

to

determine

the

order

for

some

specified

x

andN.Order-finding

isbelieved

to

be

a

hard

problem

on

a

classical

computer,in

the

sense

that

no

algorithm

is

known

to

solve

the

problem

using

resources

polynomial

in

the

O(L)bits

needed

to

specify

theproblem,where

L=[log(N)]is

the

number

of

bits

needed

to

specify

N.Inthis

sectionwe

explainhowphase

estimationmaybe

used

to

obtain

an

efficient

quantum

algorithmfor

order-finding.For

positive

integers

z

and

N,x<N,with

no

common

factors,the

order

of

z

modulo

Nis

defined

to

be

the

least

positive

integer,r,such

that

x?=1(mod

N).

The

order-finding階

(order)

的定義Exercise5.10:

Show

that

the

order

of

x=5modulo

N=21

is

6.gcd(126,21)=721=7*35?-1mod21=018確定order與相位估計(jì)U|y〉=|xy(mod

N)》,Using

the

phase

estimation

procedure

allows

us

to

obtain,with

high

accuracy,the

cor-responding

eigenvalues

exp(2πis/r),from

which

we

can

obtain

the

order

r

with

a

littlebit

more

work.0≤y≤N-1.)for

integer(5.37)(5.38)(5.39)A

simple

calculation

shows

that

the

states

defined

by

O≤s≤r-1

are

eigenstates

of

U,since19Figure

5.4.Quantum

circuit

for

the

order-finding

algorithm.The

second

register

is

shown

as

being

initialized

tothe

|1〉

state,but

ifthe

method

ofExercise

5.14

is

used,it

can

be

initialized

to

|0>instead.This

circuit

can

also

beused

for

factoring,using

the

reduction

given

in

Section

5.3.2.H⑧t

6rimodNThe

order-finding

algorithmisRegister

1t

qubitsRegister2L

qubitsFTt20求階Algorithm:Quantumorder-findingInputs:(1)AblackboxUa,nwhichperformsthetransformation|j>|k)→

|j〉|x3k

mod

N),for

a

co-prime

to

the

L-bit

number

N,(2) qubits

initialized

to

|0),and(3)L

qubits

initialized

to

the

state

|1).Outputs:Theleastinteger

r>0

such

that

x=1(modN).Runtime:

O(L3)operations.SucceedswithprobabilityO(1).Procedure:1.

|0>|1〉

initial

state2.

createsuperposition3.

apply

Ur,NapplyinverseFouriertransformtofirst4.

register5.

→

8/r

measure

first

register6.

→T

apply

continued

fractionsalgorithm4Shor算法的一般過程22Shor算法Algorithm:Reduction

offactoringtoorder-findingInputs:Acomposite

numberNOutputs:A

non-trivial

factor

of

N.Runtime:O(logN)3)operations.SucceedswithprobabilityO(1).Procedure:1.IfN

is

even,return

the

factor

2.2.DeterminewhetherN=a?forintegers

a≥1

andb≥2,and

ifsoreturnthefactora(usesthe

classical

algorithm

of

Exercise

5.17).3.RandomlychoosezintherangeltoN-1.If

gcd(r,N)>1thenreturnthefactor

gcd(z,N).4.Usethe

order-finding

subroutineto

findthe

order

r

ofxmodulo

N.5.Ifrisevenand

r?/2≠-1(mod

N)then

compute

gcd(x"/2-1,N)andgcd(x/2+1,N),and

test

to

see

if

one

of

these

is

a

non-trivial

factor,returningthatfactorif

so.Otherwise,thealgorithmfails.235Shor算法的實(shí)現(xiàn)24Afull-scaleimplementationofShor'salgorithmtofactoran

L-bitnumberwould

require

aquantum

circuit

with

72L3quantum

gates

acting

on

5L+1

qubits

for

the

order-findingroutine2?

,i.e.factoring

N=21would

require

9000

elementary

quantum

gates

acting

on

26qubits.The

overhead

in

quantum

gates

comes

from

the

modular

exponentiation

function

parBeckman,D.,Chari,A.N.,Devabhaktuni,S.&Preskill,J.Efficient

networks

for

quantumfactoring.Phys.Rev.A54,1034-1063(1996)資源需求25Results■Here

we

present

the

realization

ofa

scalable

Shoralgorithm,as

proposed

by

Kitaev.We

factor

the

number15

by

effectively

employing

and

controlling

seven

qubits

andfour“cache

qubits”and

by

implementing

generalizedarithmetic

operations,known

asmodular

multipliers.This

algorithm