G adu amaie ako lana / T abajo in de g ado
Fisikako g adua / G ado en F´ısica
Quan um algo i hms in quan um compu e s
Discussion and simula ions o well-known quan um algo i hms
Egilea/ Au o /a:
Xabie Fe n´andez S´anchez
Zuzenda iak/ Di ec o es/as:
D . Mikel Sanz Ruiz
cc by 2024 Xabie Fe n´andez S´anchez
Leioa, 2024ko ekaina en 29a / Leioa, 29 de junio de 2024
Con en s
1 In oduc ion and objec i es 2
2 Quan um compu ing 3
2.1 Re iew o quan um mechanics . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Quan umci cui model............................. 4
2.3 Elemen a y quan um ga es . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4 Ci cui complexi y ............................... 6
2.5 Quan um Fou ie T ans o m . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.5.1 Semi-classical e sion . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.6 Quan um Phase Es ima ion . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.6.1 I e a i e Phase Es ima ion . . . . . . . . . . . . . . . . . . . . . . . 11
3 G o e ’s algo i hm 12
3.1 Sea chingp oblem ............................... 12
3.2 Quan umsea ching............................... 12
3.3 Quan umcoun ing ............................... 15
4 Sho ’s algo i hm 17
4.1 P ime ac o iza ion p oblem . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.2 Fundamen als o modula a i hme ics . . . . . . . . . . . . . . . . . . . . . 17
4.3 Sho ’salgo i hm................................. 18
4.3.1 Imp o emen s.............................. 19
4.4 Quan umPe iodFinding............................ 20
4.5 Implemen ing modula ga es . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.5.1 Adde ga e ............................... 23
4.5.2 Modula adde ga e . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.5.3 Modula p oduc ga e . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.6 Finalimplemen a ion.............................. 25
5 Algo i hm simula ions 27
5.1 Qiski ...................................... 27
5.2 G o e ’salgo i hm ............................... 27
5.2.1 Quan umsea ching........................... 28
5.2.2 Quan umcoun ing ........................... 30
5.3 Sho ’salgo i hm................................. 32
6 Conclusion 38
1
Chap e 1
In oduc ion and objec i es
The o mula ion and s udy o quan um mechanics ha e supposed a majo e olu ion in
he wo d o heo e ical and expe imen al Physics. Indeed, he co esponding disco e ies
in his a ea ha e impac ed bo h echnology and he way we unde s and he wo ld, shaping
many mode n echnologies o e e yday use nowadays.
O e he second hal o he 20 h cen u y, esea che s independen ly began conside ing
he idea o concei ing compu e s ( he e o e, machines ha can un algo i hms) unde
he p inciples o quan um mechanics: in he 80’s, Yu i Manin w o e abou ex ended
con en ional compu e s wi h quan um mechanical phenomena like supe posi ion and en-
anglemen , and Richa d Feynman conside ed he idea o simula ing quan um mechanical
sys ems unde a compu e which was i sel buil upon quan um mechanical p inciples [1].
The wo k o hese and many mo e esea che s began o gain ame in he 90’s, when heo-
e ical esul s showed some quan um algo i hms which e icien ly sol ed p oblems wi hou
an e icien algo i hm o a classical compu e . Cu en ly, quan um algo i hms a e imple-
men ed in he so-called NISQ/noisy in e media e-scale quan um compu e s, cha ac e ized
by medium-sized quan um p ocesses wi h ema kable noise p oblems.
In his wo k, wo o he mos well-known quan um algo i hms a e discussed and sim-
ula ed. An ini ial heo e ical in oduc ion is gi en, s a ing wi h some undamen als o
quan um mechanics which a e used in quan um compu ing. G o e ’s algo i hm is hen
in oduced, along wi h he ela ed quan um coun ing algo i hm. Sho ’s algo i hm is in o-
duced a e wa ds, wi h a pa icula implemen a ion ha is discussed, implemen ed and
simula ed. Quan ikz [2] L
A
T
EX package is used o ende ing all quan um ci cui s.
The majo i y o implemen a ions a e p og ammed wi h Py hon and Qiski . The p o-
g ammed sou ce code is a ailable in he eposi o y o he Uni e si y o he Basque Coun y
(ADDI). Simula ions co e he esul s o housands o ci cui uns in o de o es ima e
he p obabili ies o each possible measu emen . Simula ion esul s a e discussed and
compa ed wi h heo e ical p edic ions.
The s udy o such quan um algo i hms showcases he unique p ope ies ha quan um
compu ing has, compa ed o i s classical coun e pa . I is shown ha en anglemen
plays a key ole on he phase es ima ion p ocedu e, a base componen o bo h Sho ’s and
G o e ’s algo i hms. The na u e o quan um compu ing is illus a ed o e all, consis ing o
cle e ly c ea ing supe posi ions and des uc i e in e e ences o quan um s a es in o de
o be able o ob ain in o ma ion when quan um sys em qubi s a e measu ed.
2
Chap e 2
Quan um compu ing
2.1 Re iew o quan um mechanics
A quan um mechanical sys em is ma hema ically desc ibed by a Hilbe space Hwhe e
he sys em’s s a e is desc ibed using b as ⟨Ψ|and ke s |Ψ⟩. The ime e olu ion o he
sys em is subjec o a Hamil onian ep esen ed by a He mi ian ope a o H, and i is
desc ibed by he Sch ¨odinge equa ion,
H|Ψ⟩=iℏ∂|Ψ⟩
∂ .(2.1)
The sys em s a e can be exp essed as a no malized linea combina ion o elemen s om
a chosen basis {|ϕi⟩}:
|Ψ⟩=X
i
ci|ϕi⟩,X
i|ci|2= 1 .(2.2)
Acco ding o Bo n’s ule, measu emen s wi h espec o ha (and any o he ) basis
essen ially p ojec he s a e o e he i- h basis s a e wi h p obabili y |ci|2, hence collapsing
|Ψ⟩in o a pu e basis s a e. Fo ins ance, i he quan um s a e |Ψ⟩=1
2|ϕ1⟩+√2
2|ϕ2⟩+1
2|ϕ3⟩
is measu ed, i will collapse o |Ψ⟩=|ϕ1⟩wi h p obabili y 1
22= 25%.
The Sch ¨odinge equa ion can be al e na i ely exp essed o desc ibe he ime e olu ion
o a quan um s a e wi h a uni a y e olu ion ope a o ,
|Ψ( )⟩=e−iH
ℏ |Ψ⟩.(2.3)
This al e na i e o mula ion illus a es he concep o applying uni a y ope a o s Uin
o de o in e ac wi h s a es and ans o m hem.
An ope a o Umay be exp essed in ma ix o m Uij wi h espec o a ce ain basis
{|ϕi⟩}, so ha (Uij) = (⟨ϕi|U|ϕj⟩). Fo example, in a spin-1/2 pa icle sys em wi h basis
s a es |↑⟩and |↓⟩(eigens a es o he Z-componen o spin ope a o Sz), an ope a o ac ing
he ollowing way would ha e he ollowing ma icial exp ession,
U|↑⟩ =|↓⟩, U |↓⟩ =|↑⟩ −→ U=0 1
1 0.(2.4)
3
2.2. QUANTUM CIRCUIT MODEL
In ac , his is he exp ession o one o he Pauli ma ices, a use ul quan um ga e
in oduced below.
2.2 Quan um ci cui model
Following he pa allelism wi h classical compu ing, a wo-dimensional quan um sys em
wi h basis s a es |0⟩,|1⟩can be compa ed o a classical bi . Such quan um sys em is qui e
well known in quan um mechanics and pa icle physics, since i desc ibes he s a e o a
1/2-spin pa icle such as qua ks and lep ons. This sys em desc ibes he s a e o a qubi ,
wi h his basis known as he compu a ional basis, bu o he bases may be conside ed
o speci ic pu poses. F om now on, his will be conside ed as he de aul basis, and
compu a ional basis s a es will simply be e e ed o as basis s a es.
A quan um sys em composed o se e al qubi s a es cons i u es a mul i-qubi sys em,
whose basis s a es a e de ined and named as |0⟩⊗|1⟩=|01⟩,|1⟩⊗|1⟩=|11⟩ o wo-bi
sys ems, |011⟩ o h ee-bi sys ems and so on. An n-qubi s a e is he e o e a supe posi-
ion o 2nbasis elemen s.
Quan um s a es o mul i-qubi sys ems a e p oduc s a es i hey can be exp essed as a
enso p oduc o indi idual s a es, and a e en angled s a es o he wise. En anglemen is
a key p ope y in quan um mechanics, since measu emen s in one qubi may a ec o he
qubi s despi e no measu ing hem a all.
Fo ins ance, he wo-qubi s a e 1
√2(|0⟩+i|1⟩)⊗|0⟩is a p oduc s a e (measu emen s
on one o he qubi s does no a ec he s a e o he o he ) while he s a e 1
√2(|00⟩+|11⟩)
is an en angled s a e (measu ing one o he qubi s will also a ec he s a e o he o he
qubi ).
A single qubi basis s a e can be used o encode a bi and, analogously, an n-qubi basis
s a e can be used o encode an n-bi sequence. Such pa icula qubi g oupings encoding
bi sequences/bi s ings a e known as quan um egis e s and a e analogous o classical
n-bi egis e s.
F om now on, he no a ion o |x⟩nwill co espond o he n-qubi basis s a e encoding
an-bi in ege xin bina y. Fo example, he ou -qubi s a e |1001⟩may be deno ed as
|9⟩4. Mo eo e , |x⟩(k)will be used o index a pa icula qubi o a mul i-qubi egis e ,
whe e indexing begins om he leas signi ican bi ( he bi co esponding o he powe
20in base-2 ep esen a ion). In he p e ious example, |9⟩(0) would co espond o a qubi
|1⟩and |9⟩(2) would co espond o a qubi |0⟩.
Like wi h classical egis e s, a ce ain con en ion mus be ollowed o index o o o de
qubi s / hei encoded bi s in a egis e , usually known as he endianess. The usual
con en ion implici ly ollowed in ma h and physics is big-endian o de ing, cha ac e ized
by he leas signi ican bi as he las bi . Fo example, he in ege 11 is expanded as
1·23+0·22+1·21+1·20, i is ep esen ed in big-endian o de ing as 1011. The con en ion
ollowed he e is li le-endian o de ing, equen ly used in So wa e Enginee ing, whe e he
o de is he opposi e hus he leas signi ican bi being he i s . Unde his o de ing, 11
is ep esen ed as 1101.
Unde his model, n-qubi algo i hms a e cons uc ed by applying uni a y ope a o s o
one o se e al qubi s, also known as quan um ga es o simply ga es in his con ex , along
4
2.3. ELEMENTARY QUANTUM GATES
wi h po en ial qubi measu emen s in o classical bi s. Such algo i hms a e ep esen ed by
diag ams such as he example showcased in Fig. 2.1.
|0⟩A
C
|1⟩B
Space
Time
Figu e 2.1: Example o a wo-qubi quan um ci cui . The Aga e ac s on he i s qubi ,
he Bga e ac s on he second qubi , and he ga e Cac s on bo h qubi s.
By encoding in o ma ion in he basis s a es, ga es ac ing on he s a e ac “simul ane-
ously” on all basis s a es p esen in he supe posi ion:
U(|ϕ1⟩+|ϕ2⟩+... +|ϕn⟩) = U|ϕ1⟩+U|ϕ2⟩+... +U|ϕn⟩.(2.5)
This is he powe ul p ope y o quan um compu ing which may be ha nessed o con-
s uc algo i hms mo e e icien han hei classical coun e pa s. Ne e heless, since
measu emen s a e he only way o e ie e any in o ma ion om he quan um s a e, his
p ope y is se e ely limi ed in p ac ice due o he s a e being collapsed o he measu ed
basis s a e a e wa ds. The design o e icien quan um algo i hms he e o e consis s o
cle e ly ex ac ing in o ma ion om he quan um sys em.
The de ining p ope y o uni a y ga es is ha U†=U−1, whe e he dagge ope a o is a
conjuga e anspose ob ained by ansposing Uand hen applying complex conjuga ion o
each en y o i s ma icial exp ession. This p ope y o uni a i y implies ha all ga es a e
in e ible. Hence, unlike classical compu ing wi h con en ional logical ga es, quan um
compu ing is e e sible wi h he no o ious excep ion o measu emen s. Ne e heless,
in many quan um ci cui s measu ing is done a he end as a inal s ep o ex ac ing
in o ma ion.
2.3 Elemen a y quan um ga es
The wo-dimensional Pauli ma ices, widely used in quan um mechanics, a e well-known
single-qubi ga es. The e a e e e ed by a ious names in his model, such as X, Y, Z:
X=0 1
1 0, Y =0−i
i0, Z =1 0
0−1.(2.6)
In pa icula , he Xga e is also called he NOT ga e o i being iden ical o he classical
NOT logic ga e, since i s ac ion lips he qubi s a e: X|0⟩=|1⟩and X|1⟩=|0⟩
Ano he widely used quan um ga e is he Hadama d ga e, pa icula ly use ul o s a e
ini ializa ion since i c ea es equip obable supe posi ions om pu e basis s a es:
H=1
√21 1
1−1,
H|0⟩=1
√2(|0⟩+|1⟩),
H|1⟩=1
√2(|0⟩−|1⟩).
(2.7)
5
2.4. CIRCUIT COMPLEXITY
Phase ga es in oduce a complex phase eiϕ i he qubi is |1⟩and lea e he qubi un-
changed o he wise:
R±j=1 0
0e±i2π
2j,Rj(α|0⟩+β|1⟩) = α|0⟩+βei2π
2j|1⟩,
R−j(α|0⟩+β|1⟩) = α|0⟩+βe−i2π
2j|1⟩.(2.8)
A pa icula ly use ul ype o ga es a e con olled ga es, cons uc ed by gene alizing ex-
is ing ga es so ha hey a e con olled by an addi ional qubi . Such ga es a e ep esen ed
as shown in Fig. 2.2 in ci cui s.
. . .
. . .
|Φ⟩con ol
|Ψ⟩nU a ge
Figu e 2.2: G aphical ep esen a ion o a ga e Uac ing on he n-qubi egis e |Ψ⟩nand
con olled by he qubi |Φ⟩.
An n-qubi ga e Ucon olled by an a bi a y qubi and applied o an a bi a y n-qubi
egis e ( he wo may be en angled) has he ollowing exp ession,
CU (α|0⟩⊗|Φ⟩n+β|1⟩⊗|Ψ⟩n) = α|0⟩⊗|Φ⟩n+β|1⟩⊗U|Ψ⟩n.(2.9)
I ollows ha his addi ional qubi , known as he con ol qubi , is essen ially ac ing as
a condi ional Boolean alue ( ue o alse alue) ypically used on classical algo i hms:
i he con ol qubi is 0 ( alse), hen he ga e lea es he emaining qubi s unchanged,
and o he wise (1/ ue) i does ac on hem. The con ol qubi will be gene ally any
supe posi ion o |0⟩and |1⟩, in which case applying he con olled ga e may in oduce
en anglemen be ween he con ol qubi and he es .
Swap ga es, which can swap he s a es o wo qubi s (and may be combined/gene alized
o swap mo e) may be cons uc ed om o he elemen a y ga es.
2.4 Ci cui complexi y
Simila o classical compu ing, he esou ce equi emen s o a quan um ci cui a e a c ucial
aspec o s udy. The ele an quan i iable esou ces in he con ex o a quan um ci cui
a e memo y, which is de e mined by he equi ed qubi coun , and ime, ela ed o he
numbe o ga es i is composed o .
The dep h o a ci cui consis s o he numbe o dis inc imes eps a which ga es a e
applied in a ci cui . In se e al quan um ci cui s, ga es may be applied in pa allel du ing
he same imes ep, as can be seen in he quan um ci cui illus a ed in Fig. 2.3.
|0⟩H
U
X
|1⟩H
Figu e 2.3: Simple quan um ci cui in which he ini ial Hadama d ga es may be applied
in pa allel.
6
2.5. QUANTUM FOURIER TRANSFORM
2.5 Quan um Fou ie T ans o m
The Fou ie T ans o m is a widely known and used sub ou ine in Physics and Enginee ing.
The Disc e e Fou ie T ans o m pe o ms he ollowing ans o ma ion o a se o Ninpu
alues {x1, ..., xN}:
xj→
N−1
X
k=0
xke−i2πjk
N.(2.10)
By con enien ly combining Hadama d and con olled phase ga es, a quan um algo i hm
analogous he Disc e e Fou ie T ans o m can be cons uc ed as shown in Fig. 2.4.
. . . . . .
. . . . . . . . .
.
.
.
. . . . . .
. . . . . .
|ϕ⟩(n−1) HR2Rn−1Rn
|ϕ⟩(n−2) HRn−2Rn−1
|ϕ⟩(1) HR2
|ϕ⟩(0) H
QFT
Figu e 2.4: Gene al n-qubi ci cui o he Quan um Fou ie T ans o m sub ou ine
[3].
The ci cui ans o ms an n-qubi basis s a e |x⟩nin he ollowing equi alen o ms:
QFT |x⟩n=1
√2n
2n−1
X
k=0
ei2πkx
2n|k⟩n
=1
√2(|0⟩+ei2πx
2n|1⟩)⊗···⊗ 1
√2(|0⟩+ei2πx
21|1⟩).
(2.11)
The e o e, he applica ion o ci cui 2.4 is a ans o ma ion analogous o he classical
disc e e Fou ie ans o m o a se o N= 2ninpu s.
A o al o n(n−1)/2 ga es a e used o he n-qubi e sion, esul ing in size and
dep h o O(n2). The mos amous classical algo i hm is he as Fou ie ans o m o
FFT, which has complexi y O(Nlog N) whe e Nis he inpu alue coun . Compa ing
bo h complexi ies yields O(n2) o he QFT and O(n2n) o he FFT. The FFT has
exponen ial complexi y compa ed wi h he polynomial complexi y o QFT, hence showing
he exponen ial speedup ha he quan um e sion p o ides. No e, howe e , ha om
he QFT only a single alue may be measu ed and he quan um s a e will ha e collapsed
a e wa ds, while om any classical FT all ans o med alues a e e ie ed.
2.5.1 Semi-classical e sion
Any algo i hm composed o a QFT/in e se QFT immedia ely ollowed by a measu emen ,
and op ionally single-qubi ga es be o e/a e he (in e se) QFT, is subjec o a majo
imp o emen in qubi equi emen .
In he QFT ci cui illus a ed in Fig. 2.4, he e ec o he QFT ac ing on he i s qubi
7
2.6. QUANTUM PHASE ESTIMATION
|ϕ⟩(0) consis s o he applica ion o a single Hadama d ga e. This (along o he po en ial
single-qubi ga es be o e/a e he QFT, plus a inal measu emen ) means ha he qubi
is e ec i ely independen om he es and he ga es and measu emen ac ing on i could
be pe o med wi hou hem.
Applying he (in e se) QFT on he second qubi |ϕ⟩(1) in ol es applying a Hadama d
ga e and a phase ga e con olled by he i s qubi , bu i can be shown ha , i he i s
qubi is ac ed and measu ed be o ehand, he con olled phase ga e can be eplaced by a
egula phase ga e applied condi ionally by he i s qubi measu emen bi as shown in
Fig. 2.5.
|ϕ⟩(1) HR2
y(1)
|ϕ⟩(0) H
y(0)
|ϕ⟩(0) H
y(0)
|ϕ⟩(1) HR2
y(1)
y(0)
Figu e 2.5: Compa ison o he 2-qubi QFT ci cui ( op) and i s semi-classical e sion
(bo om), eusing a single qubi . The R2ga e is only applied i he measu ed bi y(0) is
1, deno ed by dashed lines.
The same hing ollows o all nqubi s, depending on p e ious qubi measu emen s.
This can be exploi ed o simpli y (in e se) QFT ci cui s by using a single qubi and
e ec i ely spli ing he p ocedu e in o ncycles, known as he semi-classical (in e se)
QFT and illus a ed in Fig. 2.6.
. . . . . .
|ϕ⟩(0) H
x(0)
|ϕ⟩(1) HR2
x(1)
|ϕ⟩(n−1) HRnR2
x(n−1)
Cycle 1 Cycle 2
x(0)
Cycle n
x(0) x(n−2)
. . . . . .
|ϕ⟩(0) H
x(0)
|ϕ⟩(1) R−2H
x(1)
|ϕ⟩(n−1) R−nR−2H
x(n−1)
Cycle 1 x(0)
Cycle 2 x(0)
Cycle n
x(n−2)
Figu e 2.6: Gene al n-qubi s o he semi-classical e sions o he QFT ( op) and in e se
QFT (bo om) espec i ely.
2.6 Quan um Phase Es ima ion
Any gi en uni a y ga e Uhas i s co esponding eigens a es {|ej⟩}and eigen alues {ei2πϕj}
whe e ϕj∈[0,1), so ha U|ej⟩=ei2πϕj|ej⟩. I we wish o ob ain he phase ϕjco e-
sponding o a ce ain eigens a e |ej⟩, no hing can be ob ained by simply applying he
8
3.3. QUANTUM COUNTING
. . . . . .
. . . . . .
.
.
.
. . . . . .
. . . . . .
|0⟩(n−1) H
O
H
J
H
x(n−1)
|0⟩(n−2) H H H
x(n−2)
|0⟩(1) H H H
x(1)
|0⟩(0) H H H
x(0)
G o e i e a ion G( epea ed R imes)
Di usion ope a o Q
Figu e 3.2: Gene al n-qubi ci cui o G o e ’s algo ihm wi h Ri e a ions. An n-bi
in ege xis measu ed co esponding o basis s a e |x⟩n.
Since he o acle que y coun is gi en by R, om Eq. 3.9 i ollows ha he ci cui has
an uppe bound o O√Non he que y complexi y, hence quad a ically imp o ing he
al eady discussed O(N) bound o classical sea ching.
3.3 Quan um coun ing
In a sea ching p oblem he amoun o sea chable a ge i ems Mis usually unknown.
The sepa a e p oblem o es ima ing Mis known as he coun ing p oblem. Fo una ely,
wi h he ga es desc ibed o he sea ching algo i hm, a s aigh o wa d p ocedu e o such
p oblem can be designed.
In he subspace Sand i s co esponding basis o {|α⟩,|β⟩}, he G o e i e a ion G
happens o ha e he ollowing wo eigen ec o -eigen alue pai s:
G1
√2(−i|α⟩+|β⟩)=e−i2θ1
√2(−i|α⟩+|β⟩),
G1
√2(i|α⟩+|β⟩)=ei2θ1
√2(i|α⟩+|β⟩).
(3.10)
The phases a e con enien ly 2θ/2πand −2θ/2π, whe e a nega i e phase −2θis equi -
alen o 2π−2θ o be made posi i e. Since |Ψ0⟩is an equip obable supe posi ion o |α⟩
and |β⟩, by Eqs. 3.10, i is also an equip obable supe posi ion o bo h Geigens a es.
The e o e, a phase es ima ion p ocedu e wi h Gas he uni a y and |Ψ0⟩as he ini ial
s a e allows he ex ac ion o ei he phases. The co esponding quan um ci cui s a e gi en
in Figs. 3.3 and 3.4 o o iginal and i e a i e phase es ima ion espec i ely.
15
3.3. QUANTUM COUNTING
. . .
. . .
. . .
. . .
. . .
|0⟩(m−1) H
QFT−1
(m−1)
.
.
.
|0⟩(1) H
(1)
|0⟩(0) H
(0)
|0⟩(n−1) H
G20G20G2m−1
.
.
.
|0⟩(0) H
Figu e 3.3: Quan um coun ing p oblem ci cui based on he o iginal Quan um Phase
Es ima ion p ocedu e. The ci cui has o al o m+nqubi s, o ganized as wo m-qubi
and n-qubi egis e s.
|0⟩H H
(0)
|0⟩HR−2H
(1)
...
|0⟩nH⊗nG2m−1G2m−2...
Cycle 1 Cycle 2
(0)
. . .... |0⟩HR−mR−2H
(m−1)
... G20
Cycle m
(0) (m−2)
Figu e 3.4: Quan um coun ing p oblem ci cui based on he i e a i e Quan um Phase
Es ima ion p ocedu e. The ci cui has o al o n+ 1 qubi s, o ganized as a n-qubi
egis e and a single qubi .
In he classical pos -p ocessing a e he phase es ima ion p ocedu e, an op imal mea-
su emen will yield an m-bi in ege = 2m2θ/2πo = 2m(2π−2θ)/2π. F om exp ession
3.6 Mmay be ob ained, since θcan be compu ed om he measu ed alue:
1≈2mθ
π= 2mϕ1
π, ϕ1=θ ,
2≈2m1−θ
π= 2mϕ2
π, ϕ2=π−θ .
(3.11)
These angles a e hence ela ed by ϕ2=π−ϕ1; by igonome ic iden i ies i ollows
ha sin ϕ1= sin ϕ2, so bo h measu emen s j esul in he same es ima ion o M:
M≈Nsin2π j
2m.(3.12)
16
Chap e 4
Sho ’s algo i hm
4.1 P ime ac o iza ion p oblem
The p ime ac o iza ion p oblem is a widely known p oblem in Compu e Science. The
idea is s aigh o wa d: gi en an in ege Nknown o be a p oduc o wo unknown p ime
in ege s pand q, he ask is o de e mine pand q, hence o ac o N. The opposi e
ask (gi en pand q, mul iply hem o ob ain N) is i ial and can be done e icien ly in
i ually any classical compu e as i consis s o a me e in ege mul iplica ion. This shows
ha , gi en po en ial guesses p′and q′, hey can be easily checked.
Se e al algo i hms exis o sol ing such a p oblem, bu none o he classical ones is
e icien . One o hese algo i hms, Sho ’s quan um algo i hm, is discussed in his
sec ion.
4.2 Fundamen als o modula a i hme ics
The p ocedu e o Sho ’s algo i hm is oo ed in numbe heo y and modula a i hme ics.
Unde modula a i hme ics, ope a ions wi h in ege alues w ap a ound he modulus.
The mos amilia example a e ime uni s, whe e hou s in a 12−hou clock ope a e un-
de mod-12, and minu es and seconds unde mod-60. Equi alence ela ions in modula
a i hme ics a e cong uen ela ions deno ed using mod.
Fo example: unde mod-12 a i hme ics, he addi ion ope a ion 5 + 8 equals 1. The
cong uence ela ion behind his ope a ion is 13 ≡1 (mod 12). Mo e gene ally, he con-
g uence ela ion a≡b(mod n) is equi alen o a=b+xn o some pa icula in ege x,
which can be seen as ha in ege alues aand bdi e by a mul iple o he modulus n.
Gi en any na u al numbe k, all na u al numbe s smalle han kand cop ime wi h k
(sha ing no p ime ac o s wi h k) along wi h 1 o m a g oup unde mod-kmul iplica ion
which will be deno ed by Gk. Fo ins ance, o k= 15 he co esponding g oup is G15 ≡
{1,2,4,7,8,11,13,14}.
Since Gkis a ini e g oup, i ollows ha e e y elemen ahas i s co esponding o de ,
which is he smalles posi i e in ege sa is ying he ollowing p ope y:
17
4.3. SHOR’S ALGORITHM
imes
z }| {
a·a·. . . ·a=a ≡1 (mod k) (4.1)
This p ope y illus a es he pe iodici y o mod-kp oduc s o e he g oup elemen s:
epea ed p oduc s by a pa icula g oup elemen awill e en ually loop and esul in
elemen 1, and applying u he p oduc s by awill epea he loop again. In ac , he
o de o ais p ecisely he amoun o p oduc s needed be o e he successi e p oduc
applica ions loop back o he s a ing alue.
An example o sequen ial mod-15 mul iplica ions is illus a ed in Fig. 4.1.
4·7 (mod 15) = 13
13 ·7 (mod 15) = 1
1·7 (mod 15) = 7
7·7 (mod 15) = 4
4
13
1
7
k= 15, a =7: = 4
Figu e 4.1: Loop esul ing by epea ed p oduc s by 7 unde mod-15 a i hme ics. The
co esponding o de is = 4.
The size o he g oup Gkwill always be smalle han k. This ollows since he la ges
g oup comp ises k−1 elemen s, which is he case o a p ime kwhe e e e y in ege
be ween 1 and k−1 is cop ime o k. Fo any non-p ime k, he g oup size will be smalle ,
since a leas one o hose k−1 smalle in ege s will sha e some p ime ac o wi h k. F om
he e, i also ollows ha < k o any g oup elemen a, since he e en ual loop eached
by successi e ap oduc s canno be la ge han he g oup i sel be o e elemen s s a o
epea .
4.3 Sho ’s algo i hm
This backg ound in modula a i hme ics may be used o ac o ou inpu in ege Nby
aking he ini e g oup GNco esponding o mod-Na i hme ics.
By aking a g oup elemen aand supposing i s co esponding o de is e en, Eq. 4.1
may be ac o ed as
a /2+ 1a /2−1≡0 (mod N).(4.2)
Such an exp ession is equi alen o s a ing ha a /2+ 1a /2−1is a mul iple o N,
i.e. nis con ained as a ac o be ween bo h ac o ed e ms.
The exp ession can be sa is ied in possible manne s: wo i ial cases and a emaining
non i ial case.
The wo i ial cases a e when he exp ession is indi idually sa is ied by a single e m:
18
4.3. SHOR’S ALGORITHM
a /2+ 1 ≡0 (mod N),
a /2−1≡0 (mod N).(4.3)
In such cases, Nis con ained as a ac o exclusi ely on one o he wo e ms. The la e
o such cases is equi alen o Eq. 4.1 wi h exponen /2. Howe e , his is no possible
since is by de ini ion he smalles posi i e in ege sa is ying he equa ion. Ne e heless,
he o me i ial case may be sa is ied: such a case gi es no use ul in o ma ion abou N
o i s p ime ac o s.
In he non i ial case, N=pq is a ac o o bo h e ms combined bu no indi idually
o a single e m. The e o e, pand qmus be ac o s o each e m sepa a ely, so hey can
be ex ac ed as he g ea es common di iso o Nand each e m:
p= gcda /2−1, N, q = gcda /2+ 1, N.(4.4)
The g ea es common di iso o wo in ege s can be e icien ly compu ed using Euclid’s
algo i hm. Thus, gi en an elemen a∈GNwhose o de is e en and assuming ha he
p ope y gi en by Eq. 4.2 is no i ially sa is ied, Ncan be success ully ac o ed. This
is he co e idea behind Sho ’s algo i hm, whose p ocedu e s ems om:
1. Choose an in ege a∈[2, N −1].
2. Check whe he a∈GN. I o he wise, aand Nsha e a ac o and hus pand qa e
s aigh o wa d o ob ain ( his, howe e , ge s ex emely unlikely he bigge Nis):
p= gcd(a, N), q =N/p . (4.5)
3. Find he o de o a.
4. Ve i y ha is e en and ha Eq. 4.3 is no sa is ied. I o he wise, epea he
p ocedu e wi h a di e en in ege a.
5. Ex ac pand qas in Eq. 4.4 and hus success ully ac o N.
All p ocedu e s eps happen o be clasically e icien , bu o he s ep ega ding compu -
ing he o de . Pe e W. Sho [4] de ised a quan um algo i hm which e icien ly inds
o de s: he Quan um Pe iod Finding ou ine. No e ha o de and pe iod will be used as
sinonyms, bo h e e ing o he same p ope y o a gi en g oup elemen a.
4.3.1 Imp o emen s
So a he o iginal Sho ’s algo i hm has been discussed, bu mino imp o emen s ha e
been made o e ime. One ele an imp o emen [5] elaxes he equi emen o e en
o de s: i ahappens o be a squa e in ege o he o m a=b2, hen exp ession 4.2 may
be s ill alid1in e ms o bdespi e being odd:
(b + 1) (b −1) ≡0 (mod N).(4.6)
This al e na i e exp ession may be again sa is ied by wo i ial cases and a gene al
non i ial one, bu he si ua ion is no en i ely he same as be o e. is no he o de o
1I a=b2,bis also a g oup elemen : b∈GN.
19
4.4. QUANTUM PERIOD FINDING
bbu he o de o a, since bwill ha e i s own o de which we shall name s. No e ha s
migh be a ac o o , in which case he e is no longe a o bidden i ial case, and bo h
need o be aken in o accoun .
This idea may be gene alized o elemen s o he o m a=b2k, whe e bis he i educible
oo o a. In Re . [5] i is shown ha ac o ing wi h bins ead o ais he same a wo s , o
p e e able a bes . In o he wo ds, o some elemen s a, ac o ing may ail (a i ial case
is sa is ied) bu ac o ing wi h hei oo bhappens o be success ul and does no ha e
ha p oblem. This will la e be shown wi h some explici examples.
4.4 Quan um Pe iod Finding
A quan um algo i hm o easonably es ima ing he o de o a gi en elemen acan be
cons uc ed using phase es ima ion, known as he Quan um Pe iod Finding algo i hm.
The algo i hm is designed by p o iding a q-qubi quan um ga e Ua,N pe o ming mod-N
mul iplica ion2by a alue a,
Ua,N |x⟩q=|(a·x) (mod N)⟩q.(4.7)
Such a ga e has eigens a e/eigen alue pai s, indexed wi h s= 0, ..., −1:
|ψs⟩q=1
√
−1
X
k=0
e−i2πk s
ak(mod N)q, Ua|ψs⟩q=ei2πs
|ψs⟩q.(4.8)
A pu e eigens a e canno be p epa ed as an ini ial s a e, since would need o be known
be o ehand, bu he ollowing p ope y o he sum o eigens a es can be exploi ed
1
√
−1
X
s=0 |ψs⟩n=|1⟩n.(4.9)
The e o e, he pu e basis s a e |0...01⟩≡|1⟩nis p ecisely he equip obable supe posi ion
o all Ua,N eigens a es. By s a ing wi h such s a e as he ini ial s a e and pe o ming
he phase es ima ion p ocedu e, a alue o 2ms/ may be ex ac ed. The co esponding
ci cui s, wi h i e a i e and egula phase es ima ion, a e ep esen ed in Figs. 4.2 and 4.3
espec i ely.
|0⟩H H
y(0)
|0⟩HR−2H
y(1)
...
|1⟩qUa2m−1,N Ua2m−2,N ...
Cycle 1 Cycle 2
y(0)
. . .... |0⟩HR−mR−2H
y(m−1)
... Ua20,N
Cycle m
y(0) y(m−2)
Figu e 4.2: Quan um Pe iod Finding (QPF) ci cui based on he i e a i e phase es ima-
ion p ocedu e. The ci cui has o al o q+ 1 qubi s, o ganized as a q-qubi egis e and
a single qubi .
2Mod-Nmul iplica ion is no an in e ible ope a ion. Fo ins ance, e e y mul iple o 15 (hence
x= 0,15,30,45,60,75...) sa is ies x≡0 (mod 15). Howe e , an implemen a ion o Ua,N is discussed in
his wo k, showing ha i can be cons uc ed wi h he aid o ancilla y/auxilia y qubi s.
20
4.4. QUANTUM PERIOD FINDING
. . .
. . .
. . .
. . .
. . .
|0⟩(m−1) H
QFT−1
y(m−1)
.
.
.
|0⟩(1) H
y(1)
|0⟩(0) H
y(0)
|1⟩(q−1)
Ua20,N Ua21,N Ua2m−1,N
.
.
.
|1⟩(0)
Figu e 4.3: Quan um Pe iod Finding (QPF) ci cui based on he o iginal phase es ima ion
p ocedu e. The ci cui has o al o m+qqubi s, o ganized as wo m-qubi and q-qubi
egis e s.
Ne e heless, ex ac ing s/ s ill does no gi e away he pe iod: sis an unknown alue
be ween 0, ..., −1, and is he desi ed alue o compu e, also unknown. Mo eo e , he
measu ed alue ymay no e en be exac ly 2ms/ , bu he closes in ege o i , p o ided
an op imal measu emen was pe o med. Thus, he measu ed alue needs o be p ocessed
in o de o easonably ex ac .
Con inued ac ion expansions may be used o his pu pose. Gi en he a ional numbe
y/2m, i can be expanded by i s con inued ac ion expansion which is desc ibed by a ini e
se o coe icien s {a1, a2, ..., a }
y
2m=1
a1+1
a2+1
a3+...
.(4.10)
F om now on, when discussing any pos -p ocessing o a Quan um Pe iod Finding mea-
su emen , he equi alence be ween a ac ion and i s con inued ac ion expansion coe i-
cien s will be s a ed as he ollowing ela ion
y
2m≡ {a1, a2, ..., a }.
The con e gen s o a con inued ac ion expansion a e de ined as unca ions o he
coe icien se : ac ions co esponding o coe icien s {a1},{a1, a2},{a1, a2, a3}and so on
a e con e gen s o y/2m.
As an example, ac ion 68/157 has expansion coe icien s {2,3,4,5},
68
157 =1
2 + 1
3+ 1
4+ 1
5
≡ {2,3,4,5}.(4.11)
I has been shown [6] ha , om all possible con e gen s o he expansion o y/2m, he
con e gen wi h he la ges denomina o smalle han Nis a good candida e o he a io
s/ wi h a p obabili y o a leas 4/π2≈40.5%, gi en ha he ollowing condi ion is
sa is ied
y
2m−s
≤1
2 2.(4.12)
21
4.5. IMPLEMENTING MODULAR GATES
Since he mos likely alue o measu e yis he closes in ege o 2ms/ , i ollows ha
y−2ms
≤1
2−→ y
2m−s
≤1
2m+1 .(4.13)
We ha e ha < N as discussed. By aking nas he leng h o bi s ing N(in o he
wo ds, he minimal numbe o bi s equi ed o ep esen N, i.e. n=⌊log2(N) + 1⌋), i
ollows ha < 2n, since 2n−1 is he la ges n-bi in ege . F om he e
< 2n→1
2 2>1
22n+1 .(4.14)
This, oge he wi h Eq. 4.12, leads o m≥2n. F om now on, he lowes alid qubi
coun o m= 2nwill be conside ed o QPF p ocedu es unless s a ed o he wise, and n
will always e e o he he leng h o bi s ing N. No e ha he qubi coun qs ill needs
o be discussed, since i will depend on how he ga e Ua,N is implemen ed.
This pos -p ocessing may be classically done. Howe e , he pe iod inding p ocedu e
and pos -p ocessing discussed so a has ca ea s o be discussed.
Fi s o all, he e will always be a likely measu emen o alue y= 0, co esponding o
phase s= 0. Such a measu emen p o ides no in o ma ion as no hing can be ex ac ed
h ough con inued ac ions.
Mo eo e , an unsuccess ul measu emen may be made. Since he success o he con in-
ued ac ion pos -p ocessing elies on pe o ming op imal measu emen s, pos -p ocessing
unsuccess ul measu emen s will lead o e o s in he es ima ion o .
An addi ional and mo e sub le ca ea o discuss co esponds o he case when s/ is
educible. In his cases, he discussed pos -p ocessing will yield a alse posi i e: i s′/ ′is
he i educible e sion, pos -p ocessing a good measu emen will yield ′as he es ima ed
o de , which is no bu me ely some ac o s o i ins ead. In ac , since smigh be any
alue be ween 0 and −1, he e is a ele an chance ha sand sha e ac o s.
Fo una ely, he ac ha ′is essen ially wi hou a ew ac o s can be exploi ed: i
one happens o measu e and ex ac mo e han one o hese alse posi i es, he e is a
decen chance ha hey oge he con ain all he ac o s o 3, which can be checked by
es ing a alue o gi en by hei leas common mul iple: = lcm( ′
1, ′
2, . . . )
4.5 Implemen ing modula ga es
Sho ’s algo ihm, as explained in he p e ious sec ion, is oo ed in he exis ence o a mod-
Nmul iplica ion uni a y ga e desc ibed in Eq. 4.7. The e is no a unique cons uc ion
o such a ga e. Bu , in his wo k, a pa icula implemen a ion is p o ided.
The p oposed implemen a ion ollows Re . [7], cons uc ing modula mul iplica ion om
modula addi ion and modula addi ion om egula addi ion. Mo e p ecisely, gi en wo
in ege s aand xo bi s ing leng h smalle o equal o n(in o he wo ds, bo h in ege s
can be s o ed/ ep esen ed wi h nbi s), hei mod-Np oduc (a·x) (mod N) may be
expanded by using he bina y exp ession o x(whe e x(j)co esponds o he j- h bi o
3As a ma e o ac [3], he e is a leas a 25% chance ha wo alues s′
1and s′
2sha e no common
ac o s. In ha case s1/ 1and s2/ 2we e educed by simpli ying a di e en ac o each, hence ′
1and ′
2
oge he con ain all ac o s o .
22
4.5. IMPLEMENTING MODULAR GATES
x):
a·x=a·20x(0) +a·21x(1) +···+a·2n−1x(n−1) ,
(a·x) (mod N)=(. . . ((20ax(0)) (mod N)+21ax(1)) (mod N)+
+···+ 2n−1ax(n−1)) (mod N).
(4.15)
4.5.1 Adde ga e
The s a ing poin o his implemen a ion is he e o e an adde ga e, a ga e whose ac ion
o e a basis s a e encoding an in ege |x⟩is o add a cons an in ege a, esul ing in he
basis s a e encoding |x+a⟩.
The e a e se e al exis ing implemen a ions o adde ga es, bu he adde ga e used in
his wo k ollows Re . [8] and i is desc ibed by he ci cui in Fig. 4.4.
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . .
a(q−1)
a(q−2)
.
.
.
a(1)
a(0)
|˜x⟩(q−1) R1R2Rq−1Rq]
x+aE(q−1)
|˜x⟩(q−2) R1Rq−2Rq−1]
x+aE(q−2)
.
.
.
|˜x⟩(1) R1P2]
x+aE(1)
|˜x⟩(0) R1]
x+aE(0)
ADDa
Figu e 4.4: Adde ci cui implemen a ion [8]ADDa, based on Fou ie space, o a q-qubi
egis e . The ci cui has a size o O(q2), and a dep h o O(q) since all phase ga es Rj o
a ixed jcan be applied in pa alell. Since ais known be o ehand, he “con olled” phase
ga es a e no eally con olled: when he ci cui is p epa ed o a, phase ga es a e only
p esen o nonze o bi s o a.
This adde ga e wo ks on Fou ie space. A QFT ga e mus be applied on a basis s a e
be o e, which is deno ed wi h a ilde:
|ex⟩ ≡ QFT |x⟩,
|x+a⟩=QFT−1ADDaQFT |x⟩.(4.16)
By s udying he op qubi |ex⟩(q−1), he e ec o he P1...Pq o a ions (condi ioned on bi s
o a, hus equi alen o Pa(q−1)
1...Pa(0)
qin oducing a o al phase o ei2πa(q−1)
21+...+a(0)
2q=
ei2π
2qa) shows how he adde wo ks:
|ex⟩(q−1) =1
√2(|0⟩+ei2πx
2q|1⟩)Pa(q−1)
1...Pa(0)
q
−−−−−−−−→ 1
√2(|0⟩+ei2πx+a
2q|1⟩) = ]
x+aE(q−1) .(4.17)
Since he e may be unde low issues, n+ 1 qubi s a e ac ually needed o n-bi numbe
addi ion. A sub ac ion (pe o med by an in e se adde ga e) esul ing in a nega i e
in ege −z(wi h z > 0) has a op qubi 1
√2|0⟩+ei2π−z
2n+1 |1⟩. The equi alen posi i e
phase has a alue o 2π−2π−z
2n+1 i.e. 2π2n+1−z
2n+1 . In ac , he sub ac ion esul ac ually
encodes he in ege 2n+1 −z, which has he op (n+ 1)- h bi se due o unde low.
23
4.5. IMPLEMENTING MODULAR GATES
4.5.2 Modula adde ga e
In a simila ashion, a mod-Madde ga e pe o ms modula addi ion on he in ege
encoded by a basis s a e, ans o ming |x⟩in o |(x+a) (mod N)⟩.
Gi en a<Nand x<Nin a basis s a e, he ci cui desc ibed in Fig. 4.5 pe o ms
modula addi ion p o ided a egula addi ion ga e.
.
.
.
|˜x⟩(n)
ADDaADD−1
NQFT−1QF T ADDNADD−1
aQFT−1
X X
QFT ADDa
^
(x+a) (mod N)E(n)
|˜x⟩(0) ^
(x+a) (mod N)E(0)
|0⟩X X |0⟩
MADDa,N
Nsub ac ion check asub ac ion check
Figu e 4.5: Mod-Nadde ci cui implemen a ion [7]MADDa,N . The ci cui has a o al
o n+ 2 qubi s, composed o an (n+ 1)-qubi egis e and an ancilla y qubi . The ci cui
has a size o O(n2) and a dep h o O(n) like he adde ga e since i is composed o a
cons an numbe o QFT, adde and elemen a y ga es.
The equi emen s in aand xallow o a simple way o pe o m modula addi ion. Unde
his cons ain s x+a < 2N, so in o de o wo k unde mod-Na i hme ics, a mos N
would need o be sub ac ed once (only i x+a≥N) aside om adding xand a.
The e o e, he i s hal o he ci cui is s aigh o wa d: ais added o xin he basis
s a e, Nis sub ac ed and a check is pe o med on whe he Nneeded o be sub ac ed in
i s place, adding Nback again o he wise. I he sub ac ion yielded a nega i e in ege
(when x+a<N), he ex a qubi would be lipped by he con olled-Xga e ( hus se
o |1⟩) due o unde low. No e ha his is essen ially ea ing he bi encoded in he
ancilla y qubi as a Boolean alue and s o ing whe he x+a<N(1 i ue o 0 i alse).
This lea es he op qubi egis e as he desi ed ou come o (x+a) (mod N). Howe e ,
addi ional s eps a e equi ed in o de o se he ancilla y qubi back o |0⟩, since his qubi
will be in an unknown s a e depending on he speci ic alues o xand a. The ollowing
modula a i hme ics p ope y is used:
(x+a) (mod N)≥a⇔x+a < N . (4.18)
The second hal checks whe he sub ac ing adoes no yield a nega i e numbe , hus
whe he (x+a) (mod N)≥a(no e he Xga es be o e and a e he con ol on he
ancilla y qubi , equi alen o wo king wi h he nega ed condi ion) adding aback again
o keep he esul in ac in he op qubi egis e .
The bi encoded in he ancilla y qubi s a s as 0, is hen lipped i x+a<Nin he
i s hal , and is lipped again i (x+a) (mod N)≥ain he second hal . Due o Eq.
4.18, i inmedia ely ollows ha hese condi ions a e ac ually he same (ei he bo h ue
o bo h alse), hence lipping he bi wo imes o no lipping i a all and hence ensu ing
i is always |0⟩by he end o he ci cui .
24
5.2. GROVER’S ALGORITHM
Figu e 5.5: Quan um coun ing algo i hm (iQPE) simula ion esul s o a lis wi h N= 32
i ems o which he las M= 5 a e a ge i ems, wi h a o al o 10 cycles. G een ba s
co espond o op imal measu emen s.
Bo h algo i hm simula ions, as expec ed, esul in simila p obabili y dis ibu ions. The
wo mos likely in ege s o ex ac a e = 892 and = 132 in bo h cases, co esponding
o he closes in ege s o he phase, wi h he wo nex likely in ege s neighbo ing alues
= 133 and = 891. Fo bo h measu ed in ege s, a alue o M= 4.967 is compu ed by
Eq. 3.12, which is a g ea es ima ion o he a ge i em coun . Fo he second mos -likely
in ege pai ( = 133 and = 891) a alue o M= 5.039 is compu ed, which is a e y
good es ima ion as well.
Mo eo e , since Mis an in ege , ha ing o ound he esul ing es ima ion leads o e en
be e odds o ob aining he igh alue as he e o ge s emo ed. Fo an a bi a y eal
alue, his would no be he case.
Fo compa ison, an addi ional simula ion is shown in Fig. 5.6 using a di e en amoun
o m= 5 phase es ima ion cycles. This and all ollowing quan um coun ing simula ions
will be pe o med wi h i e a i e phase es ima ion ou ines, since hey a e equi alen bu
less memo y in ensi e han egula phase es ima ion implemen a ions.
Figu e 5.6: Quan um coun ing algo i hm (iQPE) simula ion esul s, o a lis o N= 32
i ems o which he las M= 5 a e a ge i ems, wi h a o al o 5 cycles. G een ba s
co espond o op imal measu emen s.
While he p obabili y o op imal measu emen s imp o es, phases a e ex ac ed wi h less
p ecision, which impac s he es ima ed coun : ollowing Eq. 3.12, a alue o M= 4.686
is es ima ed o he wo op imal measu emen s.
In o de o simula e la ge lis s o i ems, a lis o N= 1024 i ems and M= 17 a ge
31
5.3. SHOR’S ALGORITHM
i ems is s udied in Fig. 5.7.
Figu e 5.7: Quan um coun ing algo i hm (iQPE) simula ion esul s, o a lis wi h N=
1024 i ems o which he las M= 17 a e a ge i ems, wi h a o al o 5 cycles. G een ba s
co espond o op imal measu emen s.
By Eq. 3.12, a alue o M= 9.83 is ob ained om he wo op imal (and again he mos
likely) measu emen s, yielding a bad es ima ion o 10 = 17. Too li le phase es ima ion
cycles we e used, and he phase was ex ac ed wi h oo small p ecision.
5.3 Sho ’s algo i hm
Wi h ega ds o he p ime ac o iza ion p oblem, Sho ’s algo i hm was discussed, which
elies on he Quan um Pe iod Finding algo i hm. The quan um algo i hm is simula ed o
some examples, explaining in de ail he classical pos -p ocessing needed o measu emen
esul s. Hence, we discuss an en i e applica ion o Sho ’s algo i hm o a gi en Nand
some chosen g oup elemen a.
The Quan um Pe iod Finding ou ine is mo e demanding in bo h qubi equi emen
and ci cui dep h. The simples in ege ypically ac o ed is N= 15, i.e. n= 4, which in
he discussed implemen a ion would equi e 4n+ 2 = 18 qubi s i pe o med wi h egula
phase es ima ion and 2n+ 3 = 11 qubi s wi h he i e a i e e sion. Since simula ing 18
qubi s is oo memo y in ensi e o he a ailable compu ing esou ces, simula ions will only
be compu ed o i e a i e phase es ima ion e sions. This is no a limi a ion wha soe e ,
since i has al eady been shown in p e ious simula ions ha he esul s a e he same.
As i was done wi h quan um coun ing simula ions, QPF simula ion esul s a e dis-
played as p obabili y es ima ions by collec ing he measu emen esul s o 1000 ci cui
simula ions. False posi i es may be easily disca ded wi hou knowing he eal o de , since
hey mus sa is y Eq. 4.1. The ollowing s eps o he algo i hm would ail o he wise, yield-
ing nonsense ac o s. Simula ions o he Quan um Pe iod Finding p ocedu e o N= 15
and a= 4 a e illus a ed in Fig. 5.8.
32
5.3. SHOR’S ALGORITHM
Figu e 5.8: Quan um Pe iod Finding (iQPE) simula ion esul s o N= 15 wi h elemen
a= 4. G een ba s co espond o op imal measu emen s.
This is a pa icula ly nice case, whe e he co esponding phases 22ns/ a e exac in ege s.
Measu ing y= 0 gi es no in o ma ion. Measu ing y= 128 yields a ac ion es ima e
y/22n= 128/256 = 1/2≡ {2}, whose pos -p ocessing is s aigh o wa d. The e is a single
con e gen , and hence, an inmedia e candida e o de o = 2, which is indeed he eal
o de since 42≡1 (mod 15). The i ial case is no sa is ied since 41+ 1 = 0 (mod N),
and hus he ac o s o Na e s aigh o wa dly ob ained,
p= gcd(41+ 1,15) = 5 , q = gcd(41−1,15) = 3 .(5.2)
The case o N= 15 wi h a di e en g oup elemen (a= 2) is illus a ed in Fig. 5.9.
Figu e 5.9: Quan um Pe iod Finding (iQPE) simula ion esul s o N= 15 wi h elemen
a= 2. G een ba s co espond o op imal measu emen s.
This is ano he ela i ely simple case, bu a pa icula measu emen may cause ouble
when pos -p ocessing as p e iously men ioned. I y= 128 (y/22n= 128/256 ≡ {2}) is
measu ed, pos -p ocessing will be he same as he p e ious one pe o med o a= 4 and
hus yield an o de o = 2. This u ns ou o be a alse posi i e, since 22= 1 (mod 15)
( he eal o de is = 4). The phase co esponding o his measu emen happens o be
s/ = 2/4=1/2, a educible a io which makes he pos -p ocessing ail. No e ha ,
ne e heless, a ac o o he o de is ex ac ed, since 2 is a ac o o he eal o de = 4.
A less simple esul is ob ained o N= 21 (i.e. n= 5) and a= 16, shown in Fig. 5.10.
33
5.3. SHOR’S ALGORITHM
Figu e 5.10: Quan um Pe iod Finding (iQPE) simula ion esul s o N= 21 wi h elemen
a= 16. G een ba s co espond o op imal measu emen s.
In his case, he e is a single op imal measu emen co esponding o in ege phase
ac o s (y= 0); he o he op imal measu emen s he e o e a e he closes in ege s. Fo
ins ance, o a measu emen o y= 683 (y/22n= 683/1024 ≡ {1,2,341}) he con e gen
{1,2} ≡ 2/3 has he la ges denomina o smalle han 21, om whe e a co ec o de o
= 3 is ob ained. The o de is odd, bu ac o ing may succeed wi h he oo s o a= 16
as p e iously discussed.
Fo he squa e oo a= 4, a i ial case is sa is ied (43−1≡0 (mod 21)). The
emaining oo o check is a= 2, o which simula ions o he Quan um Pe iod Finding
p ocedu e a e pe o med and showcased in Fig. 5.11.
Figu e 5.11: Quan um Pe iod Finding (iQPE) simula ion esul s o N= 21 wi h elemen
a= 2. G een ba s co espond o op imal measu emen s.
Op imal measu emen s a e he same as in he p e ious case. Fo a measu emen o
y= 171 (y/22n= 171/1024 ≡ {5,1,84,2}), pos -p ocessing yields a a ge con e gen
{5,1} ≡ 1/6, esul ing in a (co ec ) o de o = 6: 26≡1 (mod 21). The i ial case is
no sa is ied (23+ 1 = 0 (mod 21)), and hence 21 is success ully ac o ed,
p= gcd(23+ 1,21) = 3 , q = gcd(23−1,21) = 7 .(5.3)
Since measu emen s may no be op imal, le us check he case o an unsuccess ul mea-
su emen o y= 601 (y/22n= 601/1024 ≡ {1,1,2,2,1,1,1,10,2}). Pos -p ocessing yields
a a ge con e gen {1,1,2,2,1} ≡ 10/17 and an es ima ion o = 17, which can be dis-
ca ded by checking ha 217 = 1 (mod 21). As p e iously men ioned, he pos -p ocessing
34
5.3. SHOR’S ALGORITHM
echnique will p oduce ga bage i applied o an unsuccess ul measu emen : a measu e-
men o y= 299 es ima es = 17 as well, y= 707 es ima es = 13, y= 92 es ima es
= 11. . . all o which can be checked o be in alid o de candida es. The e o e, o he
emaining algo i hms only op imal measu emen s (i any) will be discussed.
All simula ions so a we e pe o med using m= 2ni e a i e phase es ima ion cycles.
Fo compa ison, his las case o N= 21 and a= 2 is now simula ed wi h an a ypical
cycle coun o m= 5 and shown in Fig. 5.12.
Figu e 5.12: Quan um Pe iod Finding (iQPE) simula ion esul s o N= 21 wi h elemen
a= 2, wi h a cycle coun o m= 5. G een ba s co espond o op imal measu emen s.
Fo measu emen s o y= 5 and y= 27, an inco ec o de o = 13 is es ima ed. Fo
y= 11 and y= 21, an inco ec o de o = 3 is es ima ed. Fo y= 16, he case o a
educible s/ phase, an inco ec o de o = 2 is ob ained.
The same case may be simula ed wi h an e en lowe cycle coun o m= 3, whose esul s
a e displayed in Fig. 5.13.
Figu e 5.13: Quan um Pe iod Finding (iQPE) simula ion esul s o N= 21 wi h elemen
a= 2, wi h a cycle coun o m= 3. G een ba s co espond o op imal measu emen s.
F om he 2m= 8 o al measu able alues, 6 (a majo i y o hem) a e op imal. Fo
measu emen s o y= 1, y= 3, y= 5 and y= 7 an inco ec o de o = 8 is es ima ed.
Fo y= 4, he case o a educible s/ phase, an inco ec o de o = 2 is ob ained.
As seen so a wi h he di e en phase es ima ion-based algo i hm esul s, lowe m
alues imply a mo e limi ed ange o po en ial measu emen s. Mo eo e , hese esul s
show he cons ain imposed by he pos -p ocessing condi ion gi en by Eq. 4.12: o
alues smalle han m= 2n, he con inued ac ions-based p ocedu e canno gua an ee
35
5.3. SHOR’S ALGORITHM
ha he co ec o de is encoded in a con e gen , since he ac ion y/2mwas ob ained
wi h oo li le p ecision. The emaining simula ions will be jus pe o med wi h m= 2n.
Mo ing in o la ge in ege s o ac o , simula ions o N= 33 (i.e. n= 6) and a= 5 a e
displayed in Fig. 5.14.
Figu e 5.14: Quan um Pe iod Finding (iQPE) simula ion esul s o N= 33 wi h elemen
a= 5. G een ba s co espond o op imal measu emen s.
Fo ins ance, o an op imal measu emen o y= 1229 (y/22n= 1229/4096 ≡ {3,3,204,2})
he co ec o de o = 10 is ob ained.
Addi ional simula ion esul s o la ge alues a e compiled below: o N= 39 (i.e.
n= 6) and a= 7 in Fig. 5.15;N= 51 (i.e. n= 6) and a= 5 in Fig. 5.16;N= 55 (i.e.
n= 6) and a= 7 in Fig. 5.17; and N= 77 (i.e. n= 7) and a= 5 in Fig. 5.18.
Figu e 5.15: Quan um Pe iod Finding (iQPE) simula ion esul s o N= 39 wi h elemen
a= 7. G een ba s co espond o op imal measu emen s.
36
5.3. SHOR’S ALGORITHM
Figu e 5.16: Quan um Pe iod Finding (iQPE) simula ion esul s o N= 51 wi h elemen
a= 5. G een ba s co espond o op imal measu emen s.
Figu e 5.17: Quan um Pe iod Finding (iQPE) simula ion esul s o N= 55 wi h elemen
a= 7. G een ba s co espond o op imal measu emen s.
Figu e 5.18: Quan um Pe iod Finding (iQPE) simula ion esul s o N= 77 wi h elemen
a= 5. G een ba s co espond o op imal measu emen s.
37
Chap e 6
Conclusion
In his wo k, heo e ical desc ip ions o wo widely known quan um algo i hms a e gi en,
ollowed by simula ions o he algo i hms illus a ing key concep s o hei implemen a-
ions, how hey wo k in p ac ice and how he desi ed ou pu is ob ained by pos -p ocessing
quan um measu emen s. I has been sugges ed why hey a e mo e e icien han hei clas-
sical coun e pa s, despi e hei p obabilis ic na u e ins ead o gua an eeing esul s like
he classical e sions. F om a physical poin o iew, hese algo i hms consis o ade-
qua e combina ions o uni a y ac ions on mul iple wo-dimensional quan um mechanical
sys ems, along wi h some classical p e-p ocessing and pos -p ocessing.
The discussed algo i hms cle e ly ake ad an age o unique p ope ies o quan um me-
chanics. Supe posi ion is an indispensable p ope y, i ually p esen om he e y be-
ginning in all discussed algo i hms: all o hem s a by cons uc ing an equip obable
supe posi ion o basis s a es, and ope a e by ans o ming he supe posi ion c ea ing de-
s uc i e in e e ences, inally yielding a sys em s a e whe e a inal measu emen will
ex ac some desi ed in o ma ion wi h decen p obabili y.
In G o e ’s algo i hm, he G o e i e a ion ans o ms he ini ial supe posi ion s a e
s ep by s ep. A e he igh amoun o i e a ions, he non- a ge s a e ampli udes ge
almos collapsed, while he desi ed a ge ampli udes a e ampli ied as much as possible.
In he o he wo, QPE-based algo i hms, he inal in e se QFT ga e nea ly collapses all
basis s a e ampli udes no con aining bina y encodings o some phase ac o , so ha a
measu emen will esul in a close in ege o one o hose ac o s wi h high p obabili y.
This wo k se ed as an in oduc ion o quan um compu ing and, specially, o he quan-
um ci cui model. All algo i hms we e explained in de ail and manually implemen ed
h ough Qiski , a s a e-o - he-a and widely used amewo k o implemen ing quan um
algo i hms. Such a hands-in implemen a ion o he algo i hms ga e me a g ea no ion o
how each o hei in e nal pa s wo k. The sou ce code is a ailable in he eposi o y o
he Uni e si y o he Basque Coun y (ADDI).
38
Bibliog aphy
[1] “40 yea s o quan um compu ing,” Na u e Re iews Physics, ol. 4, no. 1, pp. 1–1,
2022.
[2] A. Kay, Tu o ial on he quan ikz package, 2023. [Online]. A ailable: h ps://osl.
ug .es/CTAN/g aphics/pg /con ib/quan ikz/quan ikz.pd .
[3] M. A. Nielsen and I. L. Chuang, Quan um compu a ion and quan um in o ma ion.
Camb idge Uni e si y P ess, 2010.
[4] P. W. Sho , “Polynomial- ime algo i hms o p ime ac o iza ion and disc e e loga-
i hms on a quan um compu e ,” SIAM e iew, ol. 41, no. 2, pp. 303–332, 1999.
[5] T. Lawson, “Odd o de s in sho ’s ac o ing algo i hm,” Quan um In o ma ion P o-
cessing, ol. 14, pp. 831–838, 2015.
[6] J. Ba zen and F. Leymann, “Con inued ac ions and p obabili y es ima ions in sho ’s
algo i hm: A de ailed and sel -con ained ea ise,” AppliedMa h, ol. 2, no. 3, pp. 393–
432, 2022.
[7] S. Beau ega d, Ci cui o sho ’s algo i hm using 2n+3 qubi s, 2003.
[8] T. G. D ape , Addi ion on a quan um compu e , 2000. a Xi : quan -ph/0008033.
[9] A. Ja adi-Abha i, M. T einish, K. K sulich, e al.,Quan um compu ing wi h qiski ,
2024. a Xi : 2405.08810.
39
