Insigh s and Limi a ions o Sho ’s Fac o iza ion
Algo i hm on IBM Real Quan um Compu e s
Au ho s: Juan Manuel Villa eal D’Angelo, Ge a d De Man esa, and Ad iano Camps
Tu o : Joseph Schindle
Quan um Enginee ing Pos -g adua e Cou se (2024-2025) - Final p ojec
Fundaci´o Poli `ecnica de Ca alunya, Ba celona, Spain
[email p o ec ed], [email p o ec ed], [email p o ec ed]
[email p o ec ed]
Abs ac —Quan um Sho ’s algo i hm o e s an exponen ial
speedup o e classical me hods o in ege ac o iza ion, a
cen al p oblem o mode n c yp og aphy, and he implica-
ions o Sho ’s algo i hm in ac o ing la ge numbe s. The
algo i hm le e ages on quan um pa allelism o compu e
he pe iod o a modula exponen ia ion unc ion, employ-
ing he In e se Quan um Fou ie T ans o m (IQFT) o
ex ac pe iodici y, and classical pos -p ocessing o de i e
he ac o s. This inal epo o he Quan um Enginee -
ing pos -g adua e cou se o he Fundaci´
o Poli `
enica de
Ca alunya, p esen s he main indings encoun e ed in he
implemen a ion and benchma king o Scho ’s algo i hm
in eal IBM quan um compu e s. To accomplish his, we
c ea ed a command line ool made in Py hon, ha allows
he in eg a ion o he ci cui s implemen ing he Sho ’s
algo i hm wi h he o e all se o con igu a ion pa ame e s
needed o pe o m he benchma k. In his epo , we i s
p o ide an o e iew o he quan um ac o ing p oblem,
ollowed by a de ailed desc ip ion o Sho ’s algo i hm, and
i s implemen a ion using he Qiski Py hon lib a y. The
ci cui dep h and noise e ec s a e analyzed ac oss di e en
backend ypes, also di e en alues o he op imiza ion
le el and app oxima ion deg ees a e con igu ed when
pe o ming he ci cui anspila ion. As men ioned ea lie
di e en backend ypes we e u ilized o pe o mance
compa ison, namely backend class wi h o wi hou a
noise model (Ae Sim), a ake backend class p o ided by
he Qiski lib a y ( ake p o ide ), and he eal quan um
ha dwa e (IBM Quan um P ocessing Uni s in Janua y-
June 2025).The s udy ollows by analyzing he di e en
e o mi iga ion echniques: dynamic decoupling, Pauli
wi ling, he SABRE Op imiza ion (S ochas ic Algo i hm
o Quan um Boolean Op imiza ion and Rou ing), and any
combina ion o hem. Once he op imum con igu a ion
is ound, he maximum numbe ha can be easonably
ac o ized wi h success is explo ed. Finally, he main
conclusions, indings, and possible u u e esea ch lines a e
p esen ed, including he ac o iza ion o a N≈1000 i
app op ia e pa ame e s o he algo i hm a e selec ed.
Index Te ms—Quan um Compu ing, Sho ’s Algo i hm,
Fac o iza ion, Quan um Fou ie T ans o m, Modula Ex-
ponen ia ion, C yp og aphy
I. INTRODUCTION
In ege ac o iza ion is a compu a ionally ha d p oblem
unde pinning he secu i y o widely used c yp og aphic
sys ems like RSA. Classical algo i hms, such as he
quad a ic sie e o gene al numbe ield sie e, ac o la ge
in ege s in sub-exponen ial ime, making hem ine icien
o la ge numbe s. Sho ’s algo i hm, in oduced by Pe e
Sho in 1994 [1], le e ages on quan um compu ing o
achie e polynomial- ime ac o iza ion, posing a po en ial
h ea o RSA-based enc yp ion. The i s expe imen al
demons a ion o Sho ’s algo i hm da es om 2001[2],
when N= 15 was ac o ed. In 2007 Lu e al.[3]
ac o ized N= 15 using a pho onic implemen a ion.
As o oday, he la ges numbe s ac o ized by ue
Sho ’s algo i hm is N= 21 on ac ual quan um ha dwa e
(2012)[4], and in an IBM quan um p ocesso in 2021 [5].
In [6] i is es ima ed ha ac o ing a secu i y-s anda d
2,048-bi numbe would equi e a quan um compu e
wi h 20 million qubi s.
This wo k explo es Sho ’s algo i hm, de ailing i s
componen s—modula exponen ia ion, Quan um Fou ie
T ans o m (QFT), and classical pos -p ocessing—and
hei oles in achie ing quan um speedup. We also ad-
d ess p ac ical challenges, including ci cui dep h and
noise in quan um ha dwa e, which limi cu en im-
plemen a ions. Addi ionally, a Py hon-based simula ion
using Qiski [10] is desc ibed o illus a e he algo i hm’s
mechanics o small in ege s. The signi icance o ci -
cui dep h and noise is analyzed o highligh ba ie s
o scaling Sho ’s algo i hm on eal quan um de ices,
emphasizing he need o ad ancemen s in quan um e o
co ec ion.
II. SHOR’SALGORITHM
Be o e en e ing in dep h in he desc ip ion o he algo-
i hm i sel , i s implemen a ion, and he esul s ob ained,
we will explain Sho ’s algo i hm in a simple way. Sho ’s
algo i hm is a way o b eak down la ge numbe s in o
hei smalle building blocks (called p ime ac o s), o
example, b eaking 15 in o 3 × 5. This is impo an
because mos o ou in e ne secu i y elies on he ac
ha ac o ing huge numbe s (wi h hund eds o digi s) is
nea ly impossible o egula compu e s, so i you can
ac o hese numbe s quickly, you can b eak enc yp ion.
A. Sho ’s Algo i hm o Dummies
Sho ’s algo i hm elies on inding a hidden pa e n. Le ’s
y o illus a e i wi h an example, ying o ac o ize he
numbe 15.
•Ini ializa ion: pick a andom numbe smalle han
15 ha doesn’ sha e ac o s wi h 15, o example
7.
•Finding he epe i ion pa e n: we look a powe s
o 7, bu we will only ca e abou he emainde
a e di iding i by 15. Fo example, 70= 1 ( he
emainde o 1 when di ided by 15 is 1), 71= 7
( emainde 7), 72= 49 ( emainde 4), 73= 343
( emainde 13), 74= 2401 ( emainde 1), so we a e
back o 1. I is clea now ha he pa e n epea s
e e y 4 s eps: 1 →7→4→13 →1→7...
•Fac o iza ion: He e, we use he pa e n o ind he
ac o s. Since he pa e n leng h is 4, we calcula e:
74/2= 7 = 49, hen we compu e 49 −1 = 48 and
49 + 1 = 50.
•Finding he g ea es common di iso : The inal
s ep is o ind he g ea es common di iso (gcd) o
he p e ious wo numbe s:
gcd(48,15) = 3, gcd(50,15) = 5,(1)
Finally, he esul is 15 = 3 × 5.
The quan um pa elies on supe posi ion o ind he
pa e n leng h much as e han a classical compu e
by es ing many possibili ies simul aneously, as opposed
o es each powe one by one, which is much slowe .
Real enc yp ion uses numbe s wi h hund eds o digi s.
Finding hei epea ing pa e ns would ake classical
compu e s o e e , bu quan um compu e s could po en-
ially do i in easonable ime. Howe e , oday’s quan um
compu e s can only handle simple examples like his
one, and we would need housands o e o -co ec ed
qubi s o h ea en eal enc yp ion ha uses 300+ digi
numbe s.
Figu e 1illus a es he implemen a ion o Sho ’s ac o -
iza ion algo i hm o N= 15 and a= 4. He e is a
desc ip ion o he ci cui a chi ec u e:
•Ini ializa ion o he qubi s and applica ion o
Hadama d ga es (le sec ion): Con ol Regis e
a e 9 qubi s labeled con ol0 o con ol8,
ha a e used o c ea e a supe posi ion o s a es and
s o e he inpu x o he unc ion (x). No e ha
he numbe o con ol qubi s should be la ge han
n1= 2⌈log215⌉+ 1 = 9. Ta ge Regis e a e 4
qubi s labeled a ge 0 o a ge 3. We need
enough qubi s o ep esen numbe s up o 15. Wi h
4 qubi s, we can ep esen alues om 0 o 15 (since
24= 16), which is su icien . These hold he ou pu
o he unc ion (x) = axmod 15. Finally, ou pu
(lowe line) is no a qubi , bu ep esen s he inal
Fig. 1: Quan um ci cui implemen ing Sho ’s algo i hm
o N= 15 and a= 4.
Fig. 2: Sample pe iodic unc ion axmod N,a= 4,
N= 15 whose pe iod we y o ind.
measu emen o he con ol egis e a e he In e se
Quan um Fou ie T ans o m (IQFT), which gi es
he pe iod.
•Modula exponen ia ion (middle sec ion): com-
pu es (x) = axmod 15 o each x(Figu e 2),
and he esul is s o ed in he con ol qubi s.
•In e se Quan um Fou ie T ans o m - IQFT
( igh Sec ion): The IQFT con e s he supe posi-
ion o x alues in o a supe posi ion o equencies.
Peaks in he equency domain co espond o he
pe iod , as illus a ed in igu e 3ob ained in a
eal QPU o di e en alues o a. Clean peaks a
0 and 0.5, i.e. sepa a ion equal o 1/2, co esponds
o = 2, and peaks a 0 and 0.25, 0.5, 0.75, i.e.
sepa a ion equal o 1/4, co espond o = 4.
•Measu emen ( igh mos sec ion): A e he IQFT,
measu ing he con ol qubi s (g ay gauges) gi es
a alue ela ed o 29/ , which can be used o
de e mine in a classical way.
This ci cui demons a es he co e quan um pa o Sho ’s
algo i hm: he use o supe posi ion and he IQFT o ind
he pe iod o a unc ion e icien ly.
B. Sho ’s Algo i hm: De ailed Explana ion
In his Sec ion we will explain in de ail he di e en
ope a ions ha ake place in he compu a ion o he
Sho ’s algo i hm.
2
(a) (b) (c)
Fig. 3: Es ima ed phases om he o de inding ci cui o di e en alues o ain a eal QPU (same pa ame e s
in all h ee cases, i ele an a his s age o unde s and he ope a ion o he algo i hm): a) Peak sepa a ion is 1/4.
= 4, b-c) Peak sepa a ion is 1/2. = 2
1) Modula Exponen ia ion: Modula exponen ia ion is
he compu a ional co e o Sho ’s algo i hm, enabling
he quan um speedup ha makes in ege ac o iza ion
exponen ially as e han classical me hods1. Gi en an
in ege N o be ac o ed and a andomly chosen in ege
asuch ha gcd(a, N) = 1, Sho ’s algo i hm aims o
ind he o de , he smalles posi i e in ege sa is ying
a ≡1 mod N. The unc ion (x) = axmod N
is pe iodic wi h o de , and compu ing his unc ion
quan umly exploi s supe posi ion o e alua e i o many
alues o xsimul aneously, a key ea u e dis inguishing
quan um om classical app oaches.
The quan um ci cui o modula exponen ia ion ope -
a es on wo egis e s. The i s egis e , wi h n1=
2⌈log2N⌉+ 1 qubi s2, encodes he inpu x. The second
egis e , wi h n2=⌈log2N⌉qubi s, s o es he ou pu
(x). The algo i hm begins by ini ializing he i s eg-
is e in a uni o m supe posi ion using Hadama d ga es
applied o each qubi :
|ψ0⟩=1
√2n1
2n1−1
X
x=0 |x⟩|+⟩.(2)
The modula exponen ia ion is implemen ed ia a uni a y
ope a o U , de ined as:
U |x⟩|y⟩=|x⟩|y·axmod N⟩,(3)
whe e yis ini ially |1⟩in he second egis e o handle
mul iplica i e ope a ions. Applying U o he ini ial s a e
p oduces:
|ψ1⟩=1
√2n1
2n1−1
X
x=0 |x⟩|axmod N⟩.(4)
1Fo a comp ehensi e in oduc ion o Sho ’s algo i hm and i s
quan um ounda ions, see [7].
2⌈ ⌉ deno es he ”ceil” unc ion: ound o he immedia ely la ge
in ege .
This en angled s a e encodes he pe iodic unc ion (x),
wi h he o de embedded in he i s egis e ’s al-
ues (con ol0 o con ol8), se ing he s age o
he subsequen pe iod inding ia he Quan um Fou ie
T ans o m. Classically, modula exponen ia ion is com-
pu ed e icien ly using he squa e-and-mul iply algo-
i hm, which educes he numbe o mul iplica ions o
O(log2x). Quan um implemen a ions o such a i hme ic
ope a ions a e discussed in [8]. Fo an exponen x ep e-
sen ed in bina y as x=Pn1−1
j=0 xj2j, he exponen ia ion
is:
axmod N=
n1−1
Y
j=0
(a2jmod N)xj.(5)
In he quan um ci cui , his is implemen ed as a sequence
o n1con olled modula mul iplica ions. Fo each qubi
|xj⟩in he i s egis e , a con olled ope a ion mul iplies
he second egis e by a2jmod N, i xj= 1. The
alues a2jmod Ncan be p ecompu ed classically o
educe quan um ga e coun , hough on- he- ly compu a-
ion is possible o gene ali y.
Each modula mul iplica ion is a e e sible quan um
ope a ion. To mul iply he second egis e by b=a2j
mod N, a quan um ci cui pe o ms:
|y⟩→|y·bmod N⟩,(6)
condi ioned on |xj⟩=|1⟩. Appendix 1 p esen s he
implemen a ion o he he exponen ial mul iplica ion,
and discusses ways o op imize i .
2) In e se Quan um Fou ie T ans o m: The In e se
Quan um Fou ie T ans o m (IQFT) is a c i ical com-
ponen o Sho ’s algo i hm, enabling he ex ac ion o
he o de o he unc ion (x) = axmod N, whe e
Nis he in ege o be ac o ed and ais a andomly
chosen in ege such ha gcd(a, N) = 1. The di ec
QFT ans o ms a quan um s a e encoding he inpu
3
egis e in o he equency domain, ampli ying s a es co -
esponding o mul iples o he pe iod’s ecip ocal, hus
acili a ing pe iod inding. This is a undamen al s ep o
achie e he exponen ial speedup o Sho ’s algo i hm o e
classical ac o iza ion me hods, as i e icien ly iden i ies
he pe iodici y ha leads o N’s ac o s.
The QFT is he quan um analog o he classical disc e e
Fou ie ans o m, ope a ing on an n-qubi egis e wi h
basis s a es |0⟩,...,|2n−1⟩. Fo an inpu s a e |x⟩, whe e
x=Pn−1
j=0 xj2jis he bina y ep esen a ion, he QFT is
de ined as:
QFT|x⟩=1
√2n
2n−1
X
k=0
e2πixk/2n|k⟩.(7)
In Sho ’s algo i hm, he IQFT is applied o he i s
egis e (wi h n1=⌈2 log2N⌉+1 qubi s) a e modula
exponen ia ion, which p oduces he s a e gi en in eqn.
(4). Since (x) = axmod Nis pe iodic wi h o de ,
he i s egis e ’s s a e can be app oxima ed (igno ing
phase o se s o simplici y) as a supe posi ion o s a es
|x⟩whe e (x) epea s. Because o he pe iodici y o
(x), he applica ion o he IQFT o |ψ1⟩makes he
ampli udes o ha e peaks a alues o k≈2n1j/ ,
whe e jis an in ege . Measu ing he i s egis e
yields k, which is used o es ima e ia classical
pos -p ocessing (e.g., con inued ac ion algo i hm).
Appendix 2 p esen s he QFT implemen a ion and some
ways o op imize i .
3) Classical Pos -P ocessing: Classical pos -p ocessing
is he inal s ep in Sho ’s algo i hm, ans o ming he
quan um measu emen ou pu in o he ac o s o he
composi e in ege N. A e modula exponen ia ion and
he In e se Quan um Fou ie T ans o m (IQFT), he
algo i hm measu es he i s egis e o ob ain a alue
k, which encodes in o ma ion abou he o de o he
unc ion (x) = axmod N, whe e ais a andomly
chosen in ege sa is ying gcd(a, N)=13. The classical
pos -p ocessing s ep uses he con inued ac ion algo-
i hm o ex ac , hen compu es he g ea es common
di iso (gcd) o de i e non- i ial ac o s o N. This
s ep is c i ical, as i connec s he quan um compu a ion’s
p obabilis ic ou pu wi h de e minis ic ac o ex ac ion,
comple ing he ac o iza ion p ocess wi h high p oba-
bili y. Measu ing he i s egis e yields k, an in ege
be ween 0 and 2n1−1. The goal is o es ima e om
he ac ion k/2n1, which app oxima es j/ o some j
3The selec ion o aplays a c i ical ole in he success o Scho ’s
algo i hm, as ahas o be a cop ime numbe o N. I i is no , he
anspila ion o he code gi es an e o , as he ma ices Uba e no
uni a y. Fo small alues o N, as he alues ha can be ac o ed in
oday’s QPU’s, we can know a p io i he lis o cop ime ac o s smalle
han N, bu o e y la ge numbe s, as he ones used in c yp og aphy,
he alues o aa e selec ed andomly.
cop ime o . The con inued ac ion algo i hm is used
o ind he con e gen j/ such ha :
k
2n1−j
≤1
2n1+1 .(8)
This ensu es is accu a ely eco e ed wi h high p oba-
bili y, p o ided n1is su icien ly la ge. The con inued
ac ion algo i hm expansion o a eal numbe α=
k/2n1is compu ed as:
α=a0+1
a1+1
a2+1
...
,(9)
whe e aia e in ege s ob ained ia:
•Se α0=α.
•Fo each i, compu e ai=⌊αi⌋,αi+1 = 1/(αi−ai),
un il αiis in ege o he expansion e mina es.
The con e gen s o he con inued ac ion a e ac ions
pm/qm, compu ed ecu si ely:
•Ini ialize: p0=a0,q0= 1;p1=a0a1+1,q1=a1.
•Fo m≥2:pm=ampm−1+pm−2,qm=
amqm−1+qm−2.
The con e gen pm/qmwi h qm≤Nand
gcd(pm, qm)=1is a candida e o j/ . The denom-
ina o qmis es ed as he pe iod .
Once is ound, i is checked o sui abili y:
• mus be e en (since odd pe iods do no yield
ac o s in his con ex ).
• alida es he equa ion: a ≡1 mod N.
•a /2≡ 1 mod N, o a oid i ial esul s.
I hese condi ions hold, he ac o s o Na e compu ed
as:
1= gcd(a /2−1, N), 2= gcd(a /2+1, N).(10)
The gcd is e icien ly compu ed using Euclid’s algo i hm,
which has complexi y O((log2N)2)4I 1o 2a e
non- i ial (i.e., 1< i< N), hey a e ac o s o N. I
is in alid o yields i ial ac o s, he algo i hm epea s
wi h a new a.
The success o classical pos -p ocessing depends on
he IQFT ou pu ing ksuch ha k/2n1≈j/ wi h
gcd(j, ) = 1. Sho ’s analysis shows his occu s wi h
p obabili y a leas ϕ( )/ ≥1/(2 log2log2 ), whe e
4The Euclidean Algo i hm is a me hod o ind he g ea es common
di iso (gcd) o wo non-nega i e in ege s. I is based on he p inciple
ha he gdc o wo numbe s also di ides hei di e ence. The p ocedu e
is as ollows: gi en wo non-nega i e in ege s aand b, whe e a≥b,
di ide aby b o ob ain a quo ien qand emainde , such ha a=
b·q+ , 0≤ < b. I = 0, hen bis he gcd, bu i = 0, hen
se a=b,b= , and epea he p e ious s ep, The gcd is he las
non-ze o emainde .
4
ϕis Eule ’s To ien unc ion 5Fo la ge , his p ob-
abili y is su icien ly high, and mul iple measu emen s
inc ease he likelihood o success. The choice o n1=
⌈2 log2N⌉+ 1 ensu es he con inued ac ion algo i hm
con e ges o he co ec wi h high p obabili y.
Classical pos -p ocessing is compu a ionally e icien ,
wi h he con inued ac ion algo i hm and gcd compu-
a ion bo h unning in polynomial ime (O((log2N)3)).
Unlike quan um s eps, his phase is obus , as i elies
on well-es ablished classical algo i hms. Howe e , he
quali y o he quan um ou pu kis c i ical. Noise in he
quan um ci cui (e.g., ga e e o s o 10−3 o 10−2in
2025 ha dwa e) can dis o k, leading o inco ec con e -
gen s. Faul - ole an quan um compu ing is hus essen ial
o la ge N. Fo small N(e.g., N= 15), simula ions in
Qiski demons a e success ul pe iod inding (e.g., = 4
o a= 7), bu scaling o c yp og aphic sizes (e.g., 2048-
bi N) equi es e o -co ec ed qubi s.
The algo i hm 1ou lines he Sho ’s algo i hm im-
plemen a ion, and algo i hm 2 he classical pos -
p ocessing.
III. COMMAND-LINE TOOL CREATED TO
BENCHMARK SHOR’S ALGORITHM QUANTUM
CIRCUIT
As we in oduced in he abs ac , in o de o accomplish
he main objec i e o pe o ming he benchma k o e he
Sho ’s algo i hm quan um ci cui , we c ea ed a command
line ool made in Py hon[11]. Among he main ea u es
a e:
•Accoun managemen (IBM cloud au hen ica ion).
•Pa ame iza ion o he quan um ci cui ins an ia ed
o pe o m he benchma k, p o iding he possibili y
o es di e en ci cui s implemen a ions o Sho ’s
algo i hm.
•Pa ame iza ion o he di e en backend ypes in-
s an ia ed, namely, backend class wi h o wi hou a
noise model (Ae Sim), a ake backend class p o-
ided by he Qiski lib a y ( ake p o ide ), and he
eal quan um ha dwa e (IBM Quan um P ocessing
Uni s).
•Pa ame iza ion o he di e en a ailables QPUs
o u ilize when sending he jobs o sample o
he IBM cloud. In his p ojec he UPC p o ided
5Eule ’s To ien Func ion, deno ed ϕ(n), coun s he numbe o
posi i e in ege s up o a posi i e in ege N ha a e cop ime o N.
Two in ege s a e cop ime i hei g ea es common di iso (gcd) is 1.
Thus, ϕ(N)is he numbe o in ege s kin he ange 1≤k≤Nsuch
ha gcd(k, N)=1. Fo a posi i e in ege N, he o ien unc ion is
de ined as ϕ(N) = |{k∈Z|1≤k≤N, gcd(k, N)=1}|. I N
has he p ime ac o iza ion N=pe1
1pe2
2···pek
k, whe e pia e dis inc
p imes and eia e hei exponen s, hen ϕ(N) = NQp|N1−1
p,,
whe e he p oduc is o e all dis inc p imes pdi iding N. Cases
o in e es : o a p ime p,ϕ(p) = p−1, o a p ime powe pk,
ϕ(pk) = pk−pk−1=pk−1(p−1), and o cop ime in ege s m
and n,ϕ(m·n) = ϕ(m)·ϕ(n).
Algo i hm 1 Sho ’s Algo i hm Implemen a ion
Inpu : Numbe N, a gumen s (a gs), a-coe icien s
Ou pu : Fac o s o N
Check i Nis e en o a p ime powe ; e u n ac o s
i ue
Compu e gcd(a, N); e u n ac o s i gcd = 1
Ini ialize Sho wi h backend, sample , anspile pa-
ame e s
o each ain a-coe icien s do
C ea e ci cui :
C ea e con ol (n1), a ge (n2=) egis e s
Apply Hadama d ga es o con ol egis e
Apply con olled modula exponen ia ion o
a2jmod N
Apply in e se QFT o con ol egis e
Measu e con ol egis e o ob ain k
T anspile ci cui (inlcuding SABRE op imiza ion
only i se )
Run sample wi h sho s (dynamical decoupling
and Pauli wi ling a e included on he sampling
only i se )
P ocess esul s: compu e ia con inued ac ions
Compu e ac o s: gcd(a /2±1, N)
i ac o s a e non- i ial hen
Re u n: Fac o s
end i
end o
Re u n: Failu e ( epea wi h new a)
ee and payed access o he ollowing IBM
QPUs: ibm_aachen,ibm_s asbou g,
ibm_b ussels o payed access, and
ibm_she b ooke,ibm_b isbane,
ibm_ o ino o ee access, all o hem
unde he FPC accoun on IBM cloud. I should be
no ed ha be o e his access was p o ided we had
access o ibm_kyi wi h ou pe sonal accoun s
be o e his decommission on Ap il 18 h 2025, his
is wo h o men ion because one o ou bes esul s
in e ms o ci cui anspila ion and esul s came
up om his QPU.
•Pa ame iza ion o he main anspila ion ea u es
when using Qiski anspile .
•Pa ame iza ion o he SABRE op imiza ion ea u e
when using Qiski anspile .
•Pa ame iza ion o he main sampling ea u es when
using Qiski sample .
•T anspile using a Fake p o ide (ibm kyi in his
case) and hen se ing he ini ial layou o he
anspiled ci cui in o ano he ibm qpu anspila ion
p ocess o ci cui dep h compa ison. The key poin
is ha , he QPU ake p o ide class and he a ge
QPU need o belong o he same amily o p ocesso
5
Algo i hm 2 Classical Pos -P ocessing in Sho ’s Algo-
i hm
Inpu : Measu ed alue k, numbe o qubi s n1, in ege
N, base a
Ou pu : Fac o s o No ailu e
Compu e α=k/2n1
Ini ialize con inued ac ion: α0=α,a0=⌊α0⌋,
p0=a0,q0= 1
Ini ialize: p1=a0a1+ 1,q1=a1, whe e a1=
⌊1/(α0−a0)⌋
o each m= 2,3, . . . un il qm> N do
Compu e αm= 1/(αm−1−am−1),am=⌊αm⌋
Upda e: pm=ampm−1+pm−2,
qm=amqm−1 + qm−2
i qm≤Nand gcd(pm, qm) = 1 hen
Se =qm
i is e en and a ≡1 mod N hen
Compu e 1= gcd(a /2−1, N),
2= gcd(a /2+ 1, N)
i 1< 1< N o 1< 2< N hen
Re u n: 1, 2
end i
end i
end i
end o
Re u n: Failu e ( epea wi h new a)
ype.
•Sa e anspiled ci cui s o disk in o de o a oid
anspiling hem again when sending hem o he
IBM QPU o sampling.
•Ob ain esul s om sampling jobs submi ed p e i-
ously.
•Gene a e all he isual ou pu s ha he cu en
wo k is p esen ing: quan um ci cui , quan um ci -
cui physical layou , p obabili y dis ibu ion o
no malized o de coun , wi h he ci cui s a is ics
and noise pe cen age included.
•Calcula e a se o op imal alues o abased on he
numbe ha we wan o ac o .
•Full in eg a ion wi h Qiski SDK, Qiski un ime
en i onmen , Qiski isualiza ion ools.
IV. DESCRIPTION OF THE IMPLEMENTED CODE
The implemen a ion o Sho ’s algo i hm p o ided le e -
ages Qiski , a Py hon-based quan um compu ing ame-
wo k, o simula e o execu e he algo i hm o ac-
o ing small (TBD) in ege s on quan um ha dwa e o
simula o s. The code o ches a es he algo i hm’s key
componen s: modula exponen ia ion, In e se Quan um
Fou ie T ans o m (IQFT), and classical pos -p ocessing.
I suppo s bo h classical p e-checks and quan um com-
pu a ion, wi h op imiza ions o eal quan um ha dwa e,
including anspila ion and e o mi iga ion. This sec ion
de ails he implemen a ion’s s uc u e, unc ionali y, and
p ac ical conside a ions, highligh ing i s alignmen wi h
Sho ’s algo i hm’s heo e ical amewo k.
The en y poin is main.py, which ini ializes he
p og am by loading se ings and pa sing command-
line a gumen s using CommandLinePa se and
Con igu a ionIni classes. I suppo s wo modes:
p ocessing esul s om a p e ious job ( ia job_id)
o unning Sho ’s algo i hm o ac o a num-
be N( ia Fac o ize ). The Fac o ize
class in a i hme ics.py coo dina es he ac o -
iza ion p ocess, pe o ming classical checks (e.g.,
i Nis e en o a p ime powe ) be o e in ok-
ing he quan um algo i hm ia he Sho class
in phase_es ima ion.py. The implemen a ion is
modula , wi h sepa a e modules o ci cui cons uc ion
(ci cui .py), sampling (sampling.py), and an-
spila ion ( anspila ion.py).
In a i hme ics.py, he Fac o ize class i s
a emp s classical ac o iza ion o a oid unnecessa y
quan um compu a ion. Fo an inpu numbe N, i checks:
•I Nis e en, i e u ns ac o s 2and N/2.
•I Nis a p ime powe (N=db), i iden i ies ac o s
dand db−1.
•Fo a chosen a, i compu es gcd(a, N). I
gcd(a, N)= 1, i yields he ac o s di ec ly.
I hese ail, i selec s he coe icien s aei he an-
domly, use -speci ied, o as cop imes o N), us-
ing ge _ci cui s_coe icien s me hod, hen
passes hem o he Sho class o quan um pe iod
inding.
The ci cui .py module de ines a QCi cui ab-
s ac base class and he Regis e QC ha inhe -
i s om he QCi cui class and implemen s he
c ea e_ci cui me hod. The c ea e_ci cui
me hod in Regis e QC builds he quan um ci cui o
a gi en Nand a:
•Regis e s: Ini ializes a con ol egis e wi h n1=
2⌈log2N⌉+ 1 qubi s, a a ge egis e wi h n2=
⌈log2N⌉qubi s, and a classical egis e o mea-
su emen s.
•Ini ializa ion: Applies an X ga e o he a ge
egis e ’s leas signi ican qubi (se ing i o |1⟩)
and Hadama d ga es o he con ol egis e o c ea e
a supe posi ion (eqn.(2)).
•Modula Exponen ia ion: Fo each con ol qubi j,
compu es b=a2jmod Nclassically and applies
a con olled uni a y ga e U , whe e: U |x⟩|y⟩=
|x⟩|y·axmod N⟩.(eqn. (3)). The uni a y is
cons uc ed as a pe mu a ion ma ix in b_mod_n,
mapping |y⟩→|b·ymod N⟩, which p oduces
|ψ1⟩.
6
•IQFT: Applies an in e se QFT o he con ol eg-
is e using Qiski ’s QFT lib a y, ans o ming he
s a e o ampli y ampli udes a k≈2n1j/ .
•Measu emen : Measu es he con ol egis e , yield-
ing k.
The anspila ion.py module’s T anspile
class adap s he ci cui o speci ic quan um ha dwa e. I
uses Qiski ’s pass_manage me hod wi h pa ame e s
like op imiza ion le el, basis ga es, and ou ing me hods
(e.g., SABRE). The Sab eLayou class op imizes
qubi mapping and ou ing, wi h op ions o mul iple
i e a ions and ials o minimize ci cui dep h and ga e
coun . The ge _isa_s a is ics me hod collec s
me ics (e.g., wo-qubi ga e coun , ci cui dep h), c i ical
o assessing ha dwa e easibili y. Fo example, a ci cui
o N= 15 may equi e hund eds o ga es, challenging
o NISQ de ices wi h e o a es o 10−3 o 10−2.
The sampling.py module de ines Sample classes
(Ae Sample o simula o s, IBMRun imeSample
o IBM Quan um ha dwa e). The Sho class in
phase_es ima ion.py o ches a es ci cui execu-
ion:
•C ea es ci cui s o mul iple a-coe icien s.
•T anspiles ci cui s using T anspile class.
•Submi s jobs o he sample wi h con igu able sho s
(e.g., 1024).
•Op ionally wai s o esul s, p ocesses measu e-
men coun s, and ex ac s candida e o de s ia
ge _candida e_ s me hod.
The _se _sample _pa ams include e o mi iga ion
echniques like dynamical decoupling and Pauli wi ling,
educing decohe ence and ga e e o s on eal ha dwa e.
Pos -p ocessing occu s in job_ esul s.py ia
ind_non i ial_ ac o s me hod, which:
•Uses he measu ed k o compu e α=k/2n1.
•Applies he con inued ac ion algo i hm o ind .
•Compu es ac o s as gcd(a /2±1, N).
The plo _ esul s_dis ibu ion unc ion isu-
alizes measu emen ou comes, aiding analysis o pe iod
candida es.
The implemen a ion is op imized o small (TBD) N
(e.g., N= 15), whe e a= 7 yields = 4, p oduc-
ing ac o s 3 and 5. Fo la ge N, he ci cui dep h
( housands o ga es o 2048-bi N) and noise (ga e
e o s ∼10−3) make execu ion in easible on cu en
ha dwa e, as i will be shown la e . The code mi iga es
his wi h anspila ion op imiza ions and e o mi iga ion,
bu aul - ole an quan um compu ing is equi ed o
c yp og aphic applica ions.
This implemen a ion e ec i ely simula es Sho ’s algo-
i hm o small N, bene i ing om Qiski ’s modula i y
and ha dwa e-awa e op imiza ions. Scaling o c yp o-
g aphic sizes would equi e ad ances in quan um ha d-
Fig. 4: Pe iodici y o axmod N o N= 15,a=
2,3,4...14. No e ha o a= 6,10 he plo is la , and
o a= 4,a= 11 and a= 14 he e is an in ege numbe
o pe iods.
wa e and e o co ec ion echniques. In he las sec ion
o his epo , he au ho s will explo e he maximum
achie able N ha can be ac o ized in he a ailable IBM
quan um compu e s.
In o de o gain a be e unde s anding on he pe -
o mance o Sho ’s algo i hm, Figu e 4 ep esen s he
pe iodici y o he unc ion axmod N o N= 15,
and a= 2,3,4...14. Valid alues o aa e hose ha
a e cop imes6o N, namely 2, 4, 7, 8, 11, 13 and 14.
Values o a ha a e no cop imes o Nwill lead o non-
uni a y ma ices and anspila ion e o s, bu in he igu e
we included hem all, as in he o iginal Sho ’s algo i hm
he alues o aa e andomly chosen, and he e a e high
chances ha he selec ed ais no ac ually a cop ime o
N.
Addi ionally, o ind he pe iod o he unc ion
axmod N,amus be la ge enough so ha a leas
wo pe iods o he unc ion i in [0, N −1], ha is:
aN−1
min ≥2N. Fo N≥4,amin = 2, so he condi ion is
always sa is ied. Table Ilis s all he semip ime numbe s
smalle han 77, and some o hei cop imes. On he
o he hand, an in e es ing case occu s when = 2, hen
o a=amax =N−1, hen he gcd(a /2±1, N) =
gcd(a±1, N) = gcd(N−1±1, N)is gcd(N−2, N) = 1,
and gcd(N, N) = N, which a e he i ial ac o s o N.
V. MATERIALS AND METHODS
In his Sec ion we i s analyze he Ci cui Dep h and he
To al Numbe o Ga es o he h e QPUs a ailable in he
ee IBM plan, namely ibm_Kyi ,ibm_B isbane,
ibm_She b ooke,ibm_To ino s. hose in
he pay pe use QPUs, namely ibm_Aachen,
ibm_B ussels,ibm_S asbou g... Then, we
e ise he quan um ha dwa e speci ica ions, and we
inalize wi h an analysis o he di e en e o mi iga ion
6Cop ime numbe s a e wo o mo e in ege s ha ha e no common
posi i e di iso o he han 1, i.e. hei g ea es common di iso (gcd)
is 1.
7
TABLE I: Semip ime numbe s smalle o equal han 145,
p ime ac o s, cop ime numbe s smalle han N.
NP ime ac o s Cop imes < N
42×2 1,3
62×3 1,5
93×3 1,2,4,5,7,8
10 2×5 1,3,7,9
14 2×7 1,3,5,9,11,13
15 3×5 1,2,4,7,8,11,13,14
21 3×7 1,2,4,5,8,10,11,...,20
22 2×11 1,3,5,7,9,13,15,...,21
25 5×5 1,2,3,4,6,7,8,...,24
26 2×13 1,3,5,7,9,11,15,...,25
33 3×11 1,2,4,5,7,8,10,...,32
34 2×17 1,3,5,7,9,11,13,...,33
35 5×7 1,2,3,4,6,8,9,...,34
38 2×19 1,3,5,7,9,11,13,...,37
39 3×13 1,2,4,5,7,8,10,...,38
46 2×23 1,3,5,7,9,11,13,...,45
49 7×7 1,2,3,4,5,6,8,...,48
51 3×17 1,2,4,5,7,8,10,...,50
55 5×11 1,2,3,4,6,7,8,...,54
57 3×19 1,2,4,5,7,8,10,...,56
58 2×29 1,3,5,7,9,11,13,...,57
62 2×31 1,3,5,7,9,11,13,...,61
65 5×13 1,2,3,4,6,7,8,...,64
69 3×23 1,2,4,5,7,8,10,...,68
74 2×37 1,3,5,7,9,11,13,...,73
77 7×11 1,2,3,4,5,6,8,...,76
82 2×41 1, 3, 5, 7, 9, 11, 13, ... 81
85 5×17 1, 2, 3, 4, 6, 7, 8, ... 84
86 2×43 1, 3, 5, 7, 9, 11, 13, ... 85
87 3×29 1, 2, 4, 5, 7, 8, 10, ... 86
91 7×13 1, 2, 3, 4, 5, 6, 8, ... 90
93 3×31 1, 2, 4, 5, 7, 8, 10, ... 92
94 2×47 1, 3, 5, 7, 9, 11, 13, ... 93
95 5×19 1, 2, 3, 4, 6, 7, 8, ... 94
106 2×53 1, 3, 5, 7, 9, 11, 13, ... 105
111 3×37 1, 2, 4, 5, 7, 8, 10, ... 110
115 5×23 1, 2, 3, 4, 6, 7, 8, ... 114
118 2×59 1, 3, 5, 7, 9, 11, 13, ... 117
119 7×17 1, 2, 3, 4, 5, 6, 8, ... 118
121 11 ×11 1, 2, 3, 4, 5, 6, 7, ... 120
122 2×61 1, 3, 5, 7, 9, 11, 13, ... 121
123 3×41 1, 2, 4, 5, 7, 8, 10, ... 122
129 3×43 1, 2, 4, 5, 7, 8, 10, ... 128
133 7×19 1, 2, 3, 4, 5, 6, 8, ... 132
134 2×67 1, 3, 5, 7, 9, 11, 13, ... 133
141 3×47 1, 2, 4, 5, 7, 8, 10, ... 140
142 2×71 1, 3, 5, 7, 9, 11, 13, ... 141
143 11 ×13 1, 2, 3, 4, 5, 6, 7, ... 142
145 5×29 1, 2, 3, 4, 6, 7, 8, ... 144
and op imiza ion echniques, namely he Dynamical
Decoupling, he Pauli Twi ling, and he SABRE
Op imiza ion, espec i ely. To do his, he ool p esen ed
in Sec ion III was used.
A. Quan um Ha dwa e
IBM quan um compu ing esou ces a ailable o his
wo k a e ca ego ized in o ee and paid ie s, each o e -
ing dis inc access le els and capabili ies o implemen -
ing algo i hms like Sho ’s. F ee- ie access, ypically p o-
ided h ough pla o ms like IBM Quan um Expe ience,
allows esea che s o expe imen wi h quan um ha dwa e
and simula o s a no cos , bu wi h signi ican limi a ions.
These include es ic ed access o a subse o quan um
p ocesso s (o en smalle sys ems wi h ewe qubi s, e.g.,
127-qubi sys ems like ibm_kyi ,ibm_b isbane
and ibm_she b ooke), limi ed mon hly un ime (e.g.,
10 minu es), and lowe p io i y in job queues, leading o
longe wai imes. Fo Sho ’s algo i hm, which equi es
deep ci cui s wi h housands o ga es o ac o ing e en
small numbe s (e.g., N= 15), ee- ie access o en
esul s in incomple e execu ions due o ime cons ain s
and noise accumula ion on NISQ de ices.
Paid- ie access, such as IBM Quan um’s P emium
o En e p ise plans, unlocks ad anced ha dwa e
like ibm_aachen,ibm_b ussels, and
ibm_s asbou g, wi h highe qubi coun s (156
qubi s) and imp o ed e o a es (e.g., 6.28 ×10−4 o
3.84 ×10−3 o wo-qubi ga es). These plans o e
dedica ed un ime, and highe queue p io i y. Fo
Sho ’s algo i hm, paid ha dwa e enables execu ion o
la ge ci cui s wi h be e ideli y, which is c ucial o
pe iod inding and ac o iza ion o numbe s beyond
oy examples. Howe e , e en paid- ie sys ems s uggle
wi h c yp og aphic-scale N(e.g., 2048-bi ), equi ing
aul - ole an quan um compu ing no ye a ailable in
2025. The choice be ween ee and paid ha dwa e
hus balances cos , accessibili y, and he easibili y o
execu ing Sho ’s algo i hm e ec i ely.
In his s udy we ha e used only he ollowing IBM Quan-
um p ocesso s o implemen Sho ’s algo i hm, speci i-
cally ibm_aachen,ibm_ o ino,ibm_b isbane,
and a he beginning o he semes e also ibm_Kyi
which exhibi ou s anding pe o mances. Thei speci-
ica ions, including p ocesso ype, numbe o qubi s,
wo-qubi ga e e o a es (bes , laye ed, and median),
cohe ence imes, CNOT-leng h ope a ions pe second
and basis ga es 7, a e summa ized in Table II.
Addi ionally, highligh s o ibm_kyi a e p o ided o
con ex , hough only used a he beginning o his s udy
while i was ac i e, bu no wi h he inal e sion o he
code. The speci ica ions in Table II e eal he capa-
bili ies and limi a ions o each sys em o implemen -
ing Sho ’s algo i hm. He on p ocesso s (ibm_aachen,
72 qubi ga es: ECR ga e (Echoed C oss-Resonance Ga e): a na i e
en angling ga e in IBM’s supe conduc ing QPUs, ha uses c oss-
esonance in e ac ions wi h an echo sequence o educe noise, modu-
la ing he a ge qubi based on he con ol qubi ’s s a e ia mic owa e
pulses. CZ (Con olled-Z Ga e): applies a Z (phase lip) ope a ion o
he a ge qubi i he con ol qubi is in he 1s a e, in oducing a π
phase shi o he 11 s a e, RZZ (Ro a ion a ound ZZ Axis): applies
a o a ion by an angle θa ound he ZZ axis o he wo-qubi Pauli
ope a o (Z⊗Z), in oducing a phase o he 11 s a e, used in a ia ional
algo i hms o e o co ec ion, educing ci cui dep h. 1 qubi ga es: ID
(Iden i y Ga e), RX (Ro a ion a ound X Axis o he Bloch sphe e by
an angle θ), RZ (Ro a ion a ound Z Axis) o he Bloch sphe e by an
angle θ, applying a phase shi . SX (Squa e-Roo o X ga e): applies
aπ/2 o a ion a ound he X axis, equi alen o he squa e oo o he
X ga e, and X (Pauli X ga e) used o bi lips
8
ibm_ o ino) ea u e lowe e o a es (e.g., 0.628 ×
10−3 o ibm_aachen) and highe qubi coun s (up o
156), suppo ing deepe ci cui s wi h up o 250K CLOPS
(Ci cui Laye Ope a ions Pe Second o numbe o
single-qubi o a ions and single se o andom wo-qubi
ga es applied ac oss a subse o qubi s pe second). Ea-
gle 3 sys ems (ibm_b ussels,ibm_s asbou g,
ibm_b isbane,ibm_she b ooke) o e consis en
pe o mance wi h 127 qubi s, bu highe e o a es
(e.g., 3.84 ×10−3 o ibm_s asbou g) and sho e
cohe ence imes (100–150 µs) limi hei abili y o
execu e la ge-scale Sho ’s ci cui s wi hou signi ican
e o mi iga ion. The ibm_kyi sys em, wi h mode a e
e o a es and 200K CLOPS, aligns wi h o he Eagle 3
sys ems in pe o mance. De ailed sys em speci ica ions
o hese QPUs a e a ailable om IBM Quan um [12].
B. E o Mi iga ion and Op imiza ion Techniques
1) E o Mi iga ion - Dynamical Decoupling: Dynam-
ical decoupling (DD) is an e o mi iga ion echnique
designed o ex end qubi cohe ence imes by supp essing
decohe ence and noise in quan um sys ems, c i ical o
execu ing deep ci cui s like hose in Sho ’s algo i hm[13]
[16]. This echnique is pa icula ly ele an o NISQ
de ices, such as IBM Quan um’s He on and Eagle
p ocesso s, which exhibi cohe ence imes o 100–300
µs and ga e e o a es o 10−3 o 10−2. In Sho ’s
algo i hm, whe e modula exponen ia ion and he In e se
Quan um Fou ie T ans o m (IQFT) equi e housands o
ga es, decohe ence om en i onmen al in e ac ions (e.g.,
magne ic luc ua ions) can co up he quan um s a e.
DD applies a sequence o as , pe iodic single-
qubi ga es (e.g., X,Y, o XX pulses) o
a e age ou noise, e ec i ely e ocusing he qubi
s a e. The implemen a ion in he p o ided code
(phase_es ima ion.py) con igu es DD ia
he DynamicalDecouplingOp ions class
wi hin _se _sample _pa ams. Pa ame e s
include enable=T ue,sequence_ ype (e.g.,
XX o XY 4), ex a_slack_dis ibu ion,
scheduling_me hod, and skip_ ese _qubi s,
allowing cus omiza ion o speci ic ha dwa e. Fo
example, he XY 4sequence applies X,Y,−X,−Y
pulses, mi iga ing low- equency noise wi h a cycle
ime sho e han he cohe ence ime.
The bene i s a e impo an : DD can ex end cohe ence
imes by 20–50% on de ices like ibm_aachen (He on
2, 200–300 µs), enabling deepe ci cui s (e.g., 250K
CLOPS) o execu e be o e decohe ence domina es [17]
[16]. The e ec i eness depends on p ecise iming and
ha dwa e calib a ion, and i is less e ec i e agains ga e-
speci ic e o s, necessi a ing complemen a y echniques
like Pauli Twi ling.
2) E o Mi iga ion - Pauli Twi ling: Pauli Twi ling
(PT) is an e o mi iga ion s a egy ha andomizes ga e
e o s o app oxima e hem as s ochas ic Pauli channels,
simpli ying e o co ec ion and imp o ing measu emen
ideli y[14]. This echnique is i al o Sho ’s algo i hm,
whe e he QFT and modula exponen ia ion ci cui s
a e e y sensi i e o cohe en e o s ha accumula e
o e housands o ga es on NISQ de ices. Cu en IBM
Quan um ha dwa e (e.g., ibm_b ussels, Eagle 3)
wi h e o a es o 2.86 ×10−3bene i s om PT o
mi iga e sys ema ic e o s.
In he code (phase_es ima ion.py),
PT is implemen ed ia Twi lingOp ions
in _se _sample _pa ams, wi h pa-
ame e s like enable_ga es=T ue,
enable_measu e,num_ andomiza ions,
sho s_pe _ andomiza ion, and s a egy.
Fo each ga e (e.g., CNOT, Rz), andom Pauli
ope a o s (I,X,Y,Z) a e inse ed be o e and a e ,
ans o ming cohe en e o s in o depola izing noise.
This andomiza ion a e ages ou phase e o s, aligning
he e o model wi h ze o-noise ex apola ion o
mi iga ion p o ocols.
The ad an age is imp o ed ideli y o expec a ion al-
ues, c i ical o ex ac ing he pe iod om QFT mea-
su emen s. On ibm_s asbou g (Eagle 3, 3.84 ×
10−3e o ), wi ling can educe e ec i e e o a es by
10–30%, enhancing he success p obabili y o Sho ’s
algo i hm o N= 15. Howe e , i inc eases un ime due
o addi ional sho s (e.g., 1024 pe andomiza ion) and
may no ully mi iga e high- equency noise o c oss alk,
limi ing i s impac on la ge-scale ci cui s. Combining
DD and wi ling, as suppo ed by he code, o e s a
obus mi iga ion s a egy o NISQ cons ain s.
3) Op imiza ion Techniques (Dep h Reduc ion): SABRE
T anspila ion: SABRE is a anspila ion op imiza ion
echnique ha educes ci cui dep h by op imizing qubi
mapping and ou ing, essen ial o execu ing Sho ’s
algo i hm on cons ained quan um ha dwa e[15]. Sho ’s
algo i hm ci cui s, wi h O((log2N)3)ga e complexi y,
ace dep h limi a ions on de ices like ibm_ o ino
(He on 1, 210K CLOPS, 150–200 µs cohe ence), whe e
ga e e o s (1.03 ×10−3) accumula e apidly.
The anspila ion.py module implemen s
SABRE ia he Sab eLayou pass wi hin
Qiski ’s pass_manage . Con igu ed in
_se _ anspile_op imiza ion_pa ams
(phase_es ima ion.py), SABRE uses pa ame e s
like sab e_op imiza ion,max_i e a ions,
layou _ ials, and swap_ ials. I dynamically
maps logical qubi s o physical qubi s based on
a coupling map (e.g., ibm_aachen’s 156-qubi
opology), minimizing he numbe o SWAP ga es
equi ed o wo-qubi in e ac ions (e.g., CNOTs in
9
N= 15 and a= 4 N= 15 and a= 14
(a)
(b)
(c)
(d)
(e)
( )
(g)
Fig. 6: Summa y Table o Op imiza ion and E o Mi iga ion Resul s (see ex o de ails)
16
TABLE IX: Ci cui dep h, o al ga es, his og am noise, and pe iod- inding ou comes o N= 15,a= 4,14 on
ibm_aachen QPU, wi h e o mi iga ion, app oxima ion deg ee 0.7, and op imiza ion le el 3. Techniques include
Dynamical Decoupling (DD), Pauli Twi ling (PT), SABRE op imiza ion (SO), and all hei combina ions. Noise
indica es his og am noise le el
Table 6aOp imiza ion Technique Ci cui Dep h To al Ga es His og am Noise Pe iod Ou come
a) 4 DD 157 1121 50.3% Pe iod ound
b) 4 PT 157 1121 10.5% Pe iod ound
c) 4 SO 201 1306 7.7% Pe iod ound
d) 4 DD + PT 157 1121 99.5% Pe iod ound
e) 4 DD + SO 201 1306 41.9% Pe iod ound
) 4 PT + SO 201 1306 29.0% Pe iod ound
g) 4 DD + PT + SO 201 1306 98.6% Pe iod ound
a) 14 DD 99 694 33.4% Pe iod ound
b) 14 PT 99 694 11.6% Pe iod ound
c) 14 SO 108 776 6.2% Pe iod ound
d) 14 DD + PT 99 694 96.9% Pe iod ound (w ong)
e) 14 DD + SO 108 776 46% Pe iod ound
) 14 PT + SO 88 686 15.3% Pe iod ound
g) 14 DD + PT + SO 88 686 97.6% Pe iod ound (w ong)
we success ully ac o ed up o N= 26 anspiling and
execu ing he ci cui s o all alues o acop ime o N,
and inding he co ec pe iod o a leas one alue o
a11.
The use o iden ical op imiza ion pa ame e s (op i-
miza ion le el 3, app oxima ion ac o 0.7, and Pauli
Twi ling) allows us o isola e he e ec s o p oblem size
on quan um ci cui complexi y and pe o mance. Using
hese pa ame e s, we also success ully ac o ed N= 51,
N= 55,N= 57, and N= 65, by sea ching a leas
a alue o aamong all he cop imes o N, o which
he co ec pe iod is ound, as sugges ed in Sho ’s
algo i hm. In he nex sec ions a mo e e icien app oach
is p esen ed ha allows o ac o e en la ge N’s.
Fo N= 51 all alues o acop ime o Nlead o easible
ci cui s. Resul s a e shown in Table X. We belie e his
is due o he ac ha all alues o a e powe s o 2. Fo
la ge alues o N he ac ion o he o al numbe o
ci cui s ha can be anspiled apidly dec eases. Resul s
o o N= 55,N= 57, and N= 65 a e p esen ed in
Tables XI,XII, and XIII. Figu es 7,8, and 9p esen he
ac ual ci cui layou s and hei p obabili y dis ibu ions,
espec i ely.
•Ci cui Feasibili y and Scaling: The ansi ion
11No e: Sho ’s algo i hm doesn’ need o wo k o all alues o a-
i only needs o wo k o a su icien ac ion o hem o be p ac ical.
When ac o ing an in ege N, a andom alue o acop ime o Nhas
o be selec ed and we ha e o y o ind he pe iod o he unc ion
(x) = axmod N. The algo i hm succeeds in ac o ing Nwhen his
pe iod is e en and a /21(modN), because hen gcd(a /21, N)
gi es a non- i ial ac o . The c ucial heo e ical esul is ha o any
odd composi e N ha is no a p ime powe , a leas hal o he alues
o acop ime o Nwill yield a pe iod ha leads o success ul ac o ing.
This means ha he e a e a leas a 50% chance o success on each
a emp . In p ac ice, i one choice o a ails, ano he andom ais
selec ed and he p ocess is epea ed. The expec ed numbe o a emp s
is a mos 2, and wi h high p obabili y i will succeed in a ew ies.
om N= 55 o N= 65 e eals signi i-
can scaling challenges in quan um ac o ing. Fo
N= 55, 7 ou o 40 cop ime alues (a=
12,21,23,32,34,43,54) p oduced easible ci cui s
ha could be anspiled and execu ed success ully,
equi ing be ween 14,819 and 81,641 o al ga es
and ci cui dep hs be ween 2,708 and 14,708. Fo
N= 57, only 3 ou o 36 cop imes (a= 20,37,56)
we e easible, wi h ga e coun s be ween 29,938 and
40,428 and dep hs be ween 5,723 and 7,494. Fo
N= 65, only 2 ou o 47 cop imes (a= 14,51)
we e easible, wi h ga e coun s o 161,286 and
166,981, and ci cui dep hs o 29,280 and 30,129,
espec i ely. Non- easible cases o N > 65 e-
qui ed o e 2 million ga es, a ∼13–15×inc ease
o e easible cases, highligh ing a bimodal dis i-
bu ion and ex eme dependence on he choice o
a.
•Ga e Dis ibu ion Pa e ns: Fo N= 55, RZ and
CZ ga es domina ed complexi y, wi h no RX o
RZZ ga es. Fo N= 57, SX ga es we e p ominen
alongside CZ ga es. Fo N= 65, a s a k shi
occu ed: no RZ o SX ga es we e used, wi h CZ
ga es (e.g., 62348 o a= 14, 64816 o a= 51)
and RX ga es (e.g., 29627 o a= 14, 30524 o
a= 51) domina ing, indica ing a change in ci cui
syn hesis s a egy o basis ga e decomposi ion on
he ibm_aachen QPU.
•Ci cui Dep h Analysis: Ci cui dep hs o N= 55
anged om 2,708 o 14,708 (a e age ∼11,600),
while N= 57 easible cases had lowe dep hs
(5,723–7,494). Fo N= 65, easible cases had
signi ican ly highe dep hs (29,280 o a= 14,
30,129 o a= 51), e lec ing inc eased ci cui
complexi y despi e ewe easible cases, possibly
17
due o la ge modula exponen ia ion equi emen s.
•Noise Pe o mance Compa ison: His og am noise
le els o N= 55 a ied widely (10.3%–55.2%),
while N= 57 easible cases showed be e con-
sis ency (13.7%–19.3%). Fo N= 65, noise le els
we e highe (56.3% o a= 14, 55.3% o a= 51),
sugges ing ha la ge N alues inc ease suscep ibil-
i y o decohe ence and ga e e o s, e en in easible
cases, likely due o deepe ci cui s.
•Success Ra e: Success a es dec eased wi h inc eas-
ing N: 17.5% (7/40) o N= 55, 8.3% (3/36)
o N= 57, and only 4.3% (2/47) o N= 65.
The consis en = 2 pe iod inding in success ul
N= 57 and N= 65 cases, compa ed o mixed
= 2 and = 4 o N= 55, sugges s ha
sho e pe iods p oduce mo e a o able quan um
in e e ence pa e ns, which will be used la e o
op imize he o e all algo i hm, al hough he educed
numbe o easible a alues o N= 65 indica es
igh e cons ain s.
These esul s highligh he exponen ial scaling chal-
lenges in nea - e m quan um ac o ing. The d as ic e-
duc ion in easible cases om N= 55 o N= 57
and N= 65 con i ms cu en ha dwa e limi a ions, wi h
N= 65 pushing he bounda ies o wha is achie able
unning Sho ’s algo i hm12. The sensi i i y o acould
be le e aged by de eloping classical p e-p ocessing o
iden i y ac able cases be o e anspila ion, as explo ed
in la e sec ions. This ac and u he unning o he
ci cui op imiza ions will show how o bea his eco d
much u he .
3) Ci cui Pe o mance Dependence on he pa icula
QPU: We s a ed pe o ming mos o ou s udies wi h
IBM Kyi QPU, ha ing achie ed al eady he capabili y
o ac o ize N= 51 (see Fig. 10). Howe e , on Ma ch
18 h, 2025, he machine was no longe a ailable, and we
had o use o he machines. Un o una ely, despi e ha ing
simila speci ica ions and heo e ical pe o mance, i
was no possible o ep oduce he esul s. I was
hypo hesized ha his was due o less noisy qubi s, o
mapping in o he ci cui layou , bu he cohe ence imes
a e e y simila . To add ess his issue, ibm_Kyi ’s
ci cui layou was li e ally ”implan ed” in ou o he
compu e s (ibm_B isbane,ibm_She b ooke,
ibm_B ussels and ibm_S asbou g), which
means ha he ci cui opology was exac ly he same.
Despi e his, esul s we e d ama ically di e en (Table
XIV ).
ibm_Kyi ’s dep h o 5,309 is app oxima ely i e imes
smalle han he o he s (25,325–25,326), which a e
nea ly iden ical. This sugges s ha ibm_Kyi ’s ci cui
12Recall ha he la ges alue o N ha has been ac o ized in an
IBM NISQ is N= 21 [5].
(a) N= 55,
a= 12
(a) N= 55,
a= 21
(a) N= 55,
a= 23
(a) N= 55,
a= 32
(a) N= 55,
a= 34
(b) N= 55,
a= 43
(c) N= 55,
a= 54
Fig. 7: Summa y Table o P obabili y Dis ibu ions o
N= 55 and a) a= 12, b) a= 21, c) a= 23, d) a= 32,
e) a= 34, ) a= 43, and g) a= 54, he only 7 a’s o
which he o al numbe o ga es is 50,000 ga es. = 4
in all cases, excep = 2 o a= 21 and a= 54. Fo
a= 54 he co ec non- i ial ac o s we e ound
18
TABLE X: Quan um Ci cui S a is ics o N= 51 and
all aCoe icien s, anspiled and success ully execu ed in
an ibm_aachen QPU wi h Op imiza ion Deg ee = 3,
App oxima ion Fac o = 0.7, and Pauli Twi ling. Numbe
o RX, RZ, SX, X, CZ, and RZZ ga es no shown o
he sake o simpli icy.
a To al Ga es Ci cui Dep h His og am Noise (%)
2 4 120545 21999 56.0%
4 4 7993 14377 54.1%
5 16 159739 28752 54.0%
7 16 167981 30384 10.4%
8 8 125261 22862 12.3%
10 16 165820 29740 50.8%
11 16 162097 29364 8.5%
13 4 83114 15222 55.7%
14 16 165516 30046 17.4%
16 2 40912 22464 15.6%
20 8 124846 22762 20.5%
22 16 168841 30405 11.0%
23 16 165424 30063 6.8%
25 8 121014 21991 53.1%
26 8 120188 21737 13.8%
28 16 168554 30523 12.3%
29 16 163706 29340 7.9%
31 16 167359 30516 15.3%
32 8 119874 21498 17.3%
35 2 36800 6641 19.8%
37 16 163522 29621 8.6%
38 4 78433 14041 13.8%
40 16 164321 29704 15.9%
41 16 159830 28623 13.7%
43 8 124186 22325 9.8%
44 16 169469 30758 16.0%
46 16 162817 29426 5.0%
47 4 81351 14835 16.0%
49 8 122173 21871 9.4%
50 2 22227 4001 22.4%
was op imized h ough a a mo e e icien anspila ion,
educed swap ga e inse ion, o a opology-aligned qubi
mapping. The uni o mi y among he o he QPUs indi-
ca es a mo e s anda dized compila ion app oach, wi h
mino a ia ions possibly due o QPU-speci ic connec-
i i y.
In e ms o he o al numbe o ga es ibm_Kyi ’s
46,447 ga es a e signi ican ly lowe han
ibm_S asbou g’s 189,416 o ibm_B isbane’s
209,487. The 10–15% a ia ion among he o he QPUs
sugges s di e ences in anspila ion o ou ing o e head.
RZ ga es domina e (˜
40% o he o al), ollowed by
SX ( 25–30%), ECR ( 12–15%), and X ( 5%) ga es,
e lec ing he s uc u e o Sho ’s algo i hm, which elies
hea ily on quan um Fou ie ans o ms and modula
a i hme ic.
All QPUs use he Eagle 3 a chi ec u e wi h he basis
ga e se {ec , id, z, sx, x}. Thus, di e ences a ise om
anspila ion, and a e no due o he se o na i e ga es.
In e ms o he e o a es ibm_She b ooke and
ibm_B isbane ha e he lowes e o a es, while
(a) N= 57,
a= 20
(b) N= 57,
a= 37
(c) N= 57,
a= 56
Fig. 8: Ci cui layou and P obabili y Dis ibu ions o
N= 57 and a) a= 20, b) a= 37, and c) a= 56.
(a) N= 65,
a= 14
(b) N= 65,
a= 51
Fig. 9: Ci cui layou and P obabili y Dis ibu ions o
N= 65 and a) a= 14, and b) a= 51.
ibm_S asbou g has he highes . ibm_Kyi ’s mod-
e a e e o s do no explain ei he i s compac ci cui .
Among he o he s, ibm_She b ooke’s lowe laye ed
e o may educe i s ga e coun by minimizing swap
ga es. ibm_S asbou g’s highe e o s may inc ease
ou ing o e head, bu i s has a lowe ga e coun which
sugges s ha anspila ion domina es.
Cohe ence imes and numbe o qubi s a e p e y uni o m
19
TABLE XI: Quan um Ci cui S a is ics o N= 55 and Di e en aCoe icien s, anspiled and success ully execu ed
in an ibm_aachen QPU wi h Op imiza ion Deg ee = 3, App oxima ion Fac o = 0.7, and Pauli Twi ling
a RX Ga es RZ Ga es SX Ga es X Ga es CZ Ga es RZZ Ga es To al Ga es Ci cui Dep h His og am Noise
2 20 0 157208 207123 1520 99718 0 540867 97577 –
3 20 0 128448 168759 1241 82130 0 443273 80240 –
4 10 0 157776 207743 1470 99736 0 541719 97416 –
6 10 0 160202 210171 1365 100747 0 548277 98428 –
7 20 0 157059 205616 1432 98474 0 536858 96030 –
8 20 0 160987 211291 1505 101461 0 551608 99152 –
9 10 0 160953 209666 1505 100006 0 547208 97585 –
12 4 0 22424 29764 220 14317 0 77707 13983 55.2 %
13 20 0 160229 210390 1473 101030 0 549068 98727 –
14 10 0 158188 208378 1448 100295 0 543846 97913 –
16 5 0 158489 209443 1436 100980 0 546469 98659 –
17 20 0 157520 207896 1534 100343 0 543092 98110 –
18 20 0 161023 211001 1547 101239 0 550867 98830 –
19 10 0 161848 212553 1484 102212 0 554871 99942 –
21 2 0 11768 15836 95 7710 0 41350 7548 11.5 %
23 4 0 23708 31171 216 15029 0 81641 14708 10.3 %
24 10 0 159993 210273 1403 100882 0 548393 98516 –
26 5 0 161906 211698 1444 101325 0 552441 98839 –
27 20 0 157804 207533 1484 99893 0 542094 97536 –
28 20 0 163940 214697 1360 102870 0 559992 100490 –
29 10 0 161899 212874 1442 102197 0 555055 99831 –
31 5 0 161352 210506 1560 100813 0 549877 98352 –
32 4 0 23998 31624 225 15157 0 82603 14827 11.5 %
34 2 0 10919 14591 139 7086 0 38299 6943 17.4 %
36 5 0 160071 211031 1521 101569 0 550640 99207 –
37 20 0 158598 207544 1456 99212 0 541350 96694 –
38 20 0 159748 210176 1505 101262 0 548950 98929 –
39 10 0 158917 207965 1533 99688 0 543025 97373 –
41 10 0 158216 209086 1391 100759 0 545424 98472 –
42 20 0 158271 207320 1432 99373 0 541137 96949 –
43 4 0 23479 31035 213 14947 0 81098 14658 55.0 %
46 10 0 162943 214242 1395 102824 0 558556 100490 –
47 20 0 161462 212062 1455 101386 0 552435 98950 –
48 20 0 159982 210329 1403 100979 0 548605 98605 –
49 10 0 163255 213794 1479 102408 0 557557 99896 –
51 10 0 165191 215721 1427 103214 0 562688 100643 –
52 20 0 158870 209726 1443 100878 0 546876 98600 –
53 20 0 163249 213981 1459 102752 0 558234 100354 –
54 2 0 4170 5612 31 2793 0 14819 2708 17.3 %
(100–150 µs) and numbe o qubi is he same (127), so
hey canno con ibu e o obse ed di e ences ei he .
CLOPS anges om 150K o 220K, wi h Kyi ’s ha ing a
mode a e CLOPS (200K). The e o e i does no explain
ei he i s e iciency.
A e all hese analyses, we disca d all possible causes
excep ha ibm_Kyi ’s mo e compac ci cui may
be likely due o a e y op imized anspila ion. This
highligh s he impo ance o anspila ion wi h NISQ and
shows di ec ions o enhance ci cui e iciency.
4) Op imizing o Sho ’s Algo i hm o Real Quan um
Ha dwa e: Classical P ep ocessing o Maximum Fac-
o able N, he Op ima aValues: In his sec ion, ou p i-
ma y objec i e is o in es iga e how a we could ex end
he ac o iza ion capabili ies o Sho ’s algo i hm beyond
he b u e o ce app oach o ying a alues andomly. To
do his we use he mos powe ul QPU a ailable o us
ibm_aachen’s quan um p ocesso , which ea u es 156
qubi s and employs a He on 2- ype QPU. Ideally, when
(a) N= 51,a= 4
Fig. 10: Ci cui layou and P obabili y Dis ibu ions o
N= 51 and a) a= 4 in Kyi QPU. Same ci cui
layou was implan ed in B isbane, She b ooke, B ussels
and S asbou g QPUs, bu i did no wo k.
execu ed on quan um ha dwa e, Sho ’s algo i hm would
andomly es mul iple alues o aun il i iden i ies one
ha yields a use ul pe iod, ideally, he smalles possible
pe iod ( = 2). Howe e , due o cu en ha dwa e
20
TABLE XII: Quan um Ci cui S a is ics o N= 57 and Di e en aCoe icien s, anspiled and success ully
execu ed in an ibm_aachen QPU wi h Op imiza ion Deg ee = 3, App oxima ion Fac o = 0.7, and Pauli Twi ling
a RX Ga es RZ Ga es SX Ga es X Ga es CZ Ga es RZZ Ga es To al Ga es Ci cui Dep h His og am Noise
2 18 0 150058 210092 1511 100605 0 537899 98288 –
4 9 0 155039 216480 1468 103706 0 554437 101234 –
5 18 0 154044 214057 1415 102035 0 547789 99487 –
7 3 0 125055 174430 1836 84400 0 450081 82001 –
8 6 0 147436 207160 1639 99530 0 529853 97120 –
10 18 0 145709 202668 1556 96995 0 520263 94657 –
11 6 0 145428 205146 1480 99044 0 525190 96693 –
13 18 0 153616 214271 1421 102386 0 548300 99927 –
14 18 0 154590 215664 1461 103191 0 552086 100785 –
16 9 0 155217 216668 1494 103521 0 554360 101081 –
17 18 0 151090 211148 1372 100937 0 540289 98420 –
20 2 0 9929 14399 96 7117 0 37146 6992 19.3%
22 18 0 153095 213698 1552 102085 0 546836 99608 –
23 18 0 153045 213893 1470 102406 0 547592 99954 –
25 9 0 151890 210513 1431 100419 0 539544 97885 –
26 6 0 146254 205214 1466 98969 0 525805 96445 –
28 9 0 150352 210133 1413 100494 0 537867 98127 –
29 18 0 151741 211981 1372 101196 0 542085 98696 –
31 6 0 148426 209586 1595 101553 0 536955 99212 –
32 18 0 152732 214500 1487 102834 0 548719 100417 –
34 18 0 152184 211835 1351 100990 0 542202 98520 –
35 18 0 135616 188128 1701 90164 0 484400 87693 –
37 2 0 11007 15716 112 7649 0 40428 7494 17.0%
40 18 0 150210 211526 1509 101733 0 541489 99411 –
41 18 0 153221 213952 1483 102328 0 547624 99900 –
43 9 0 150764 211621 1456 101718 0 542089 99494 –
44 18 0 149231 209170 1478 100117 0 535248 97709 –
46 6 0 144019 203294 1592 98177 0 520511 95809 –
47 18 0 153145 214086 1469 102691 0 548423 100290 –
49 3 0 149566 210474 1469 101475 0 538484 99012 –
50 6 0 149295 209577 1558 101115 0 536870 98706 –
52 18 0 151506 212377 1533 101885 0 543779 99671 –
53 18 0 152997 214160 1495 102465 0 547775 99938 –
55 9 0 149761 211135 1626 101400 0 540333 99115 –
56 2 0 7840 11695 61 5839 0 29938 5723 13.7%
limi a ions, his app oach is highly ime-consuming and
imp ac ical. In he p e ious sec ions, we adop ed a
me hodological app oach: o each alue o N o be
ac o ed, we gene a ed all cop ime alues o N, and
anspiled each o hem in he co esponding quan um
ci cui . Once we iden i ied he a ha p oduced he
lowes ci cui dep h numbe , we execu ed ha ci cui
on he eal ibm_aachen quan um p ocesso . Howe e ,
as Ninc eased, he p ocess became ex emely ime-
consuming. Fo example, when ac o ing N= 57, we
e alua ed 35 cop ime alues o a, speci ically (2, 4, 5,
7, 8, 10, 11, 13, 14, 16, 17, 20, 22, 23, 25, 26, 28,
29, 31, 32, 34, 35, 37, 40, 41, 43, 44, 46, 47, 49, 50,
52, 53, 55, 56). On a e age, each anspila ion equi ed
app oxima ely wo hou s, esul ing in a o al o nea ly 70
hou s o iden i y he op imal a. This exhaus i e p ocess
becomes inc easingly unsus ainable o la ge numbe s,
pa icula ly gi en cu en ha dwa e cons ain s. Despi e
wo king wi h a 156-qubi machine, he p ac ical limi-
a ions o ci cui dep h and ga e ideli y mean ha we
emained es ic ed o ela i ely small in ege s, a below
hose ele an o eal-wo ld c yp og aphic applica ions.
To o e come his bo leneck, based on ou p e ious
expe ience o anspiling all he admissible alues o a,
we ealized ha when sea ching o he a ha p oduces
he lowes ci cui dep h a pa e n appea ed. As you
can obse e in ables XI,XII, and XIII, he bolded
lines ma k he anspiled ci cui s ha possess he lowes
ci cui dep h, and o hose he co esponding alue
is always 2. So ou objec i e was come up wi h a
way o know in ad ance hose a alues ha p oduce
pe iods ( ) equal o 2, and ha as a consequence gene a e
ci cui s wi h he lowes ci cui dep h. To achie e his, we
de eloped a classical p e-p ocessing algo i hm designed
o iden i y alues o a ha a e mo e likely o yield he
smalles possible pe iod ( = 2). Speci ically, he sc ip
compu es he o de , he smalles posi i e in ege such
ha a ≡1 mod N, o all alues o a ha a e cop ime
o a gi en N. Fo example, when ac o ing N= 111,
he algo i hm iden i ied h ee alues o a (38, 73, and
110) ha yielded he minimal pe iod = 2.These
alues we e hen p io i ized o ci cui anspila ion and
execu ion. The pseudocode 4 ou lines he s eps o he
O de F inding Algo i hm.
21
TABLE XIII: Quan um Ci cui S a is ics o N= 65 and Di e en aCoe icien s, anspiled and success ully
execu ed in an ibm_aachen QPU wi h Op imiza ion Deg ee = 3, App oxima ion Fac o = 0.7, and Pauli Twi ling
a RX Ga es RZ Ga es SX Ga es X Ga es CZ Ga es RZZ Ga es To al Ga es Ci cui Dep h His og am Noise
2 12 501779 0 0 801352 1067092 3814 2745207 494956 –
3 12 493606 0 0 790288 1051119 3712 2702897 486471 –
4 6 500675 0 0 801224 1064951 3557 2740934 493856 –
6 12 494715 0 0 790745 1052929 3690 2707979 488012 –
7 12 388444 0 0 622867 821824 5455 2133977 380830 –
8 4 62192 0 0 98891 131754 448 339705 61398 –
9 6 494455 0 0 790234 1051727 3722 2706468 487558 –
11 12 493703 0 0 786674 1048440 3528 2698068 486934 –
12 4 60169 0 0 94070 126971 472 326722 59410 –
14 2 29627 0 0 46570 62348 255 161286 29280 56.3 %
16 3 499119 0 0 801622 1063634 3707 2737053 492187 –
17 12 490198 0 0 785547 1043214 3586 2684924 483500 –
18 4 59563 0 0 94725 126267 481 325607 58805 –
19 12 492384 0 0 788748 1047422 3739 2697183 485807 –
21 4 62024 0 0 98082 131503 502 338739 61248 –
22 12 487345 0 0 774785 1020404 4780 2648215 480529 –
23 12 483761 0 0 765402 1010165 4824 2623290 477198 –
24 12 493646 0 0 778364 1030721 4825 2673210 486868 –
27 4 59479 0 0 91739 122869 586 319407 58768 –
28 12 488873 0 0 771352 1021096 4715 2648383 482237 –
29 6 491283 0 0 779478 1028541 4639 2667700 484345 –
31 4 60512 0 0 93209 125114 528 324487 59770 –
32 12 408765 0 0 650431 853605 5862 2227898 401711 –
33 12 488508 0 0 772836 1020430 4684 2648578 481685 –
34 4 60920 0 0 96113 126928 596 329928 60047 –
36 6 498448 0 0 791834 1043665 5019 2707576 491257 –
37 12 502659 0 0 799816 1053434 4853 2732195 495348 –
38 4 59175 0 0 92340 122867 613 319439 58476 –
41 12 500031 0 0 794740 1048339 4698 2717560 492778 –
42 12 493457 0 0 784074 1033628 4836 2680857 486533 –
43 12 498278 0 0 794292 1059431 3758 2724257 491618 –
44 4 61510 0 0 97481 130095 463 335401 60707 –
46 12 488687 0 0 782823 1040982 3638 2678352 481904 –
47 4 58237 0 0 92234 123235 516 317657 57527 –
48 12 496332 0 0 794592 1057297 3639 2718189 489201 –
49 6 489532 0 0 783312 1042643 3556 2681457 482625 –
51 2 30524 0 0 48562 64816 211 166981 30129 55.3%
53 4 59830 0 0 94526 126313 549 326108 59108 –
54 12 490829 0 0 776372 1025957 4816 2661871 484122 –
56 6 496250 0 0 785113 1037350 4851 2691157 489460 –
57 4 60684 0 0 93657 125149 515 325409 59921 –
58 12 489736 0 0 768783 1020456 4908 2647082 483212 –
59 12 490126 0 0 777376 1026004 4789 2661668 483385 –
61 3 498438 0 0 795187 1045814 4761 2712417 491412 –
62 12 493043 0 0 781927 1031655 4775 2676686 486280 –
63 12 497617 0 0 791111 1042877 4781 2704992 490742 –
64 2 29012 0 0 45589 60240 262 157026 28587 –
This op imiza ion signi ican ly educed he numbe o
quan um ci cui s ha needed o be anspiled and exe-
cu ed. As a esul , we we e able o ac o la ge num-
be s, such as 111, 115, 123, di ec ly on he ha dwa e,
demons a ing a mo e scalable and e icien app oach o
implemen Sho ’s algo i hm wi hin cu en echnological
limi s. I is wo h men ioning ha o hese alues o
N, SABRE op imiza ion had o be ac i a ed in o de o
po en ially educe he ci cui dep h.
Using he abo e echnique, Fig. 11 shows he quan um
ci cui , ci cui layou , and he p obabili y dis ibu ions
o he maximum alue o Nwe ha e been able o ac o
N= 123 o a= 40 and a= 80 wi h and wi hou Pauli
Twi ling and wi h and wi hou SABRE op imiza ion.
An in e es ing ac ha has been obse ed in all he
op imum ci cui s analyzed is ha all he exponen ia ion
blocks excep he i s one a e equal o [1modN](e.g.
Fig. 11 (a) ) which is p obably he eason o he
signi ican ly smalle numbe o ga es, and signi ican ly
imp o ed pe o mance.
VII. DISCUSSION
The implemen a ion and e alua ion o Sho ’s algo i hm
p esen ed in his epo illus a es i s heo e ical powe
and i s cu en p ac ical limi a ions. While Sho ’s algo-
i hm p omises exponen ial speedup o e classical algo-
22
(a) N= 123,
a= 40 (b) N= 123,a= 83
(c) Quan um ci cui N= 123,a= 40 ( o a= 83 only
1s exponen ia ion block changes)
(d) a= 40, Pauli Twi ling, SABRE Op imiza-
ion
(e) a= 83, Pauli Twi ling, SABRE Op imiza-
ion
( ) a= 40, No Pauli Twi ling, No SABRE
Op imiza ion
(g) a= 83, No Pauli Twi ling, No SABRE
Op imiza ion
(h) a= 40, Pauli Twi ling, No SABRE Op i-
miza ion
(i) a= 83, Pauli Twi ling, No SABRE Op i-
miza ion
(j) a= 40, No Pauli Twi ling, SABRE Op i-
miza ion
(k) a= 83, No Pauli Twi ling, SABRE Op i-
miza ion
Fig. 11: Quan um ci cui ( op), and p obabili y dis ibu ions o N= 123 and a= 40 (le column) and a= 83
( igh column): a-b) wi h PT and SO, c-d) wi hou PT, wi hou SO, e- ) wi h PT and wi hou SO, and g-h) wi hou
PT and wi h SO. 23
TABLE XIV: Compa ison o Ci cui Pa ame e s Ac oss Di e en QPUs Fo N= 51, and a= 4
QPU Two-qubi ECR Ga es Single-qubi RZ Ga es Single-qubi SX Ga es Single-qubi X Ga es To al Ga es Ci cui Dep h
Kyi 5502 21 554 14 155 621 46 447 5309
B isbane 25 741 95 992 61 864 4710 209 487 25 326
She b ooke 25 743 91 728 59 566 5897 204 124 25 326
B ussels 25 740 96 312 59 777 6296 209 298 25 325
S asbou g 25 743 81 894 49 707 10 896 189 416 25 326
Algo i hm 4 O de Finding Algo i hm
Inpu : In ege N, base a
Ou pu : O de o None
o a om 2 o Ndo
i gcd(a, N) = 1 (check i a,Ncop ime) hen
= 1
o om 1 o Ndo
= ( ×a) mod N(upda e wi h mod
mul )
i = 1 (de ec o de ) hen
Re u n:
else(no o de ye )
Re u n: None
end i
i =None (p ocess alid ) hen
i < min ( ind smalles o de ) hen
min =
p= [(a, )]
else(handle o he o de s)
= min
p.append((a, ))
end i
end i
end o
end i
end o
Re u n: Failu e (no o de ound)
i hms o in ege ac o iza ion —in p inciple a di ec
h ea o RSA-based c yp og aphic sys ems— ou s udy
shows how a cu en quan um ha dwa e emains om
making his p omise ue.
A. P ac ical Feasibili y on Cu en Quan um Ha dwa e
Fac o ing ”small” numbe s, such as N= 15,N= 51,
and up o N= 123, se es as a p ac ical benchma k
o assessing quan um ci cui pe o mance on NISQ
de ices. Ou expe imen s ac oss IBM quan um p oces-
so s (ibm_b isbane,ibm_ o ino,ibm_aachen,
and ibm_kyi ) e eal signi ican a ia ions in ci -
cui pe o mance due o di e ences in ha dwa e a -
chi ec u e, qubi connec i i y, and anspila ion e i-
ciency. No ably, he He on-based ibm_aachen p o-
cesso consis en ly ou pe o med Eagle-based p ocesso s
(e.g. ibm_b isbane,ibm_ o ino) due o lowe
ga e e o a es (0.375% o CZ ga es), imp o ed co-
he ence imes (up o 450 µs wi h dynamical decou-
pling), and enhanced qubi connec i i y. Fo ins ance,
ibm_aachen achie ed success ul ac o iza ion o N=
123 wi h a= 40 and a= 83, as shown in Fig. 11,
wi h ci cui dep hs a ound 100,000 and o al ga e coun s
exceeding 500,000, e en wi h op imiza ions like SABRE
and e o mi iga ion echnique like Pauli Twi ling.
In e ms o noise, i is wo h no ing he he bes pe -
o mance a e achie ed o a= 40 when nei he Pauli
Twi ling, no SABRE op imiza ion a e used (2.6%),
and o a= 83 when only SABRE op imiza ion is
used (4.1%). The combined e ec o bo h leads o high
noise le els (22.2% and 45.6%). SABRE Op imiza ion
does no seem o show a consis en co ela ion wi h
lowe noise, i.e. he lowes noise (2.6%) occu s wi hou
SABRE (Fig. 11 ), while highe noise le els (80.6%)
also appea wi hou i (Fig. 11i), sugges ing SABRE’s
impac on noise is con ex -dependen . Wi h espec o
he case when Pauli Twi ling is used, he lowes noise
-al hough no he lowes absolu e alue- is 13.5% (Fig.
11h), bu also he highes one 80.6% (Fig. 11i), so i s
po en ial noise mi iga ion e ec s may be a guable in his
case. This highligh s ha i is di icul o in e gene al
ules o ci cui op imiza ion in e ms o noise.
Ci cui dep hs emain a c i ical limi a ion, and e en o
small N, ci cui s o en exceed 50,000 in dep h and
include ens o housands o ga es, pushing he cohe ence
limi s o cu en ha dwa e (100–150 µs). E o mi iga-
ion echniques, such as Pauli Twi ling and Dynamical
Decoupling, imp o ed success a es (e.g., 17.5% o
N= 55, 8.3% o N= 57, 4.3% o N= 65),
bu we e insu icien o aul - ole an execu ion. The
ibm_kyi QPU, be o e i s e i emen on Ma ch 18,
2025, demons a ed supe io pe o mance o N= 51
wi h a ci cui dep h o 1,383 and 14,256 ga es, likely
due o highly op imized anspila ion and opology-
aligned qubi mapping. Replica ing his ci cui layou
on o he QPUs (ibm_b isbane,ibm_she b ooke,
ibm_s asbou g, and ibm_b ussels) esul ed in
signi ican ly highe dep hs (a ound 25,326) and ga e
coun s (189,416–209,487), unde sco ing he c i ical ole
o anspila ion in pe o mance. The bes con igu a ions
on ibm_aachen QPU (e.g., a= 14 o N= 15,
al hough i leads o he i ial ac o iza ion) s ill yielded
mo e han 1000 ga es, indica ing ha aul - ole an quan-
24
um compu ing is essen ial o p og ess beyond small N.
B. Op imiza ion T ade-O s and Algo i hm Tuning
Ou anspila ion benchma king e eals ha op imiza ion
le el and app oxima ion deg ee signi ican ly impac ci -
cui complexi y. S udies on dynamical decoupling and
pulse-le el op imiza ions on IBM quan um compu e s,
as explo ed in [17], p o ide u he insigh s in o hese
e ec s. Highe op imiza ion le els (e.g., le el 3) educed
ci cui dep h by up o 40%, while an app oxima ion
deg ee o 0.7 dec eased ga e coun s by app oxima ely
25%. Howe e , hese op imiza ions o en comp omise
ideli y, as seen in cases whe e ex eme app oxima ions
led o un ealis ic ci cui dep hs (e.g., ci cui dep h=0).
The choice o he base aalso a ec s signi ican ly he
pe o mance. Fo N= 123, alues like a= 40 and
a= 83 yielded ci cui s wi h minimal pe iods ( = 2), e-
ducing modula exponen ia ion complexi y and imp o -
ing success a es. Ou classical p e-p ocessing algo i hm,
ou lined in Algo i hm 4, iden i ies such op imal a alues
by compu ing he o de o cop ime a, signi ican ly
educing he numbe o quan um ci cui s needed. This
enabled success ul ac o iza ion o la ge numbe s like
N= 111,N= 115, and e en N= 123 on 156-qubi
ha dwa e.
SABRE op imiza ion p o ed pa icula ly e ec i e o
la ge N, educing his og am noise (e.g., 10.7% wi h
SABRE s. 69.0% wi hou o N= 123,a= 40). Pauli
Twi ling was essen ial o inc easing maximum ci cui
dep h, hough, o smalle ci cui s, SABRE Op imiza ion
in oduced a mino o e head in e ms o numbe o ga es.
These indings highligh he delica e balance be ween
ci cui dep h, ga e ideli y, and success p obabili y, ne-
cessi a ing ca e ul uning o NISQ de ices.
C. Scalabili y Limi a ions and Requi emen s
Fo c yp og aphically signi ican in ege s (e.g., 2048-bi
RSA keys), Sho ’s algo i hm would equi e millions o
ga es, housands o qubi s, and long cohe ence imes,
all o which exceed cu en NISQ capabili ies by a .
E en wi h he bes IBM QPU (ibm_aachen), we a e
o de s o magni ude away om such equi emen s. The
exponen ial models i ed o ou anspila ion benchma k-
ing da a p edic ha e en a small inc ease in No
less a o able choices o awill d ama ically inc ease
ci cui equi emen s. This ein o ces he need o signi -
ican imp o emen s in aul - ole an QC, quan um e o
co ec ion (e.g., su ace codes), ha dwa e imp o emen s
in qubi connec i i y and ideli y, e c. Ou heo e ical
analysis in Appendix III es ima es maximum ci cui
dep hs o 97–119 o IBM QPUs unde op imis ic e o
ole ances (50% o e 100 laye s), ye obse ed dep hs
we e much highe . This sugges s undocumen ed e o
mi iga ion o highe ole ances in IBM sys ems.
The modula exponen ia ion s ep emains he p ima y
bo leneck, con ibu ing he majo i y o ga es and dep h
due o i s O((log2N)3)complexi y. Op imiza ions like
p ecompu ing a2jmod Nand app oxima e QFT educe
complexi y, bu canno b idge he gap o c yp og aphic
scales wi hou aul - ole an quan um compu ing. Su ace
codes, equi ing housands o physical qubi s pe logical
qubi , a e cu en ly in easible on 127–156-qubi sys ems.
VIII. CONCLUSIONS AND FUTURE RESEARCH LINES
This s udy has success ully implemen ed Sho ’s algo-
i hm on IBM quan um ha dwa e o small in ege s up
o N= 123, demons a ing i s heo e ical easibili y
on NISQ de ices while highligh ing signi ican p ac i-
cal limi a ions. The He on-based ibm_aachen QPU
ou pe o med Eagle-based p ocesso s due o lowe e o
a es, longe cohe ence imes, and be e connec i i y,
achie ing ac o iza ions like N= 123 wi h op imized a
alues (a= 40,83). Howe e , he algo i hm’s scalabili y
is se e ely cons ained by ci cui dep h, ga e coun ,
and noise, wi h modula exponen ia ion iden i ied as he
p ima y bo leneck due o i s cubic complexi y in log2N.
Key indings include he c i ical ole o anspila ion
and op imiza ion echniques. SABRE op imiza ion and
Pauli Twi ling signi ican ly educed noise and imp o ed
success a es, pa icula ly o la ge N, while classical
p e-p ocessing o selec op imal a alues minimized
ci cui complexi y, enabling ac o iza ion o N= 111,
N= 115, and N= 123. Despi e hese ad ance-
men s, cu en ha dwa e emains o de s o magni ude
away om ac o ing c yp og aphically ele an numbe s
(e.g., 2048-bi RSA keys), which would equi e mil-
lions o ga es and housands o e o -co ec ed qubi s.
The ibm_kyi QPU’s excep ional pe o mance o
N= 51 sugges s ha highly op imized anspila ion
and opology alignmen a e c ucial o maximizing NISQ
pe o mance.
The implemen a ion and benchma king o Sho ’s algo-
i hm on cu en quan um ha dwa e ha e e ealed c i ical
insigh s in o i s p ac ical execu ion and limi a ions. The
ollowing ecommenda ions and key obse a ions a e
de i ed om ou s udy o guide u u e implemen a ions
and op imiza ions o Sho ’s algo i hm on NISQ de ices:
•Ci cui Dep h and Ga e Coun Cons ain s: Em-
pi ical analysis indica es ha quan um ci cui s o
Sho ’s algo i hm pe o m eliably only when he ci -
cui dep h is ≤100,000 and he o al ga e coun is
≤500,000. These h esholds e lec he cohe ence
ime and ga e ideli y limi a ions o cu en NISQ
ha dwa e, necessi a ing ca e ul ci cui op imiza ion
o emain wi hin hese bounds.
•E o Mi iga ion and Op imiza ion S a egies:
Pauli Twi ling is essen ial o ex end he maxi-
mum achie able ci cui dep h by mi iga ing cohe -
25
