Con en s lis s a ailable a ScienceDi ec
The Jou nal o Sys ems & So wa e
jou nal homepage: www.else ie .com/loca e/jss
Au oma ic gene a ion o e icien o acles: The less- han case✩
Ja ie Sanchez-Ri e o a,Daniel Tala án b,Jose Ga cia-Alonso c,∗,An onio Ruiz-Co és d,Juan
Manuel Mu illo b,c
aUni e sidad de Se illa, Se ille, Spain
bCOMPUTAEX, Cáce es, Spain
cUni e sidad de Ex emadu a, Cáce es, Spain
dSCORE Lab, I3US Ins i u e, Uni e sidad de Se illa, Se ille, Spain
ARTICLE INFO
Da ase link:h ps://gi hub.com/JSRi e o/Less
- han-o acle
Keywo ds:
Quan um compu ing
G o e ’s algo i hm
Ampli ude Ampli ica ion
O acle au oma ic gene a ion
Qiski
E iciency
ABSTRACT
G o e ’s algo i hm is a well-known con ibu ion o quan um compu ing. I sea ches one alue wi hin an
uno de ed sequence as e han any classical algo i hm. A undamen al pa o his algo i hm is he so-called
o acle, a quan um ci cui ha ma ks he quan um s a e co esponding o he desi ed alue. A gene alisa ion
o i is he o acle o Ampli ude Ampli ica ion, ha ma ks mul iple desi ed s a es. In his wo k we p esen
a classical algo i hm ha builds a phase-ma king o acle o Ampli ude Ampli ica ion. This o acle pe o ms
a less- han ope a ion, ma king s a es ep esen ing na u al numbe s smalle han a gi en one. Resul s o
bo h simula ions and expe imen s a e shown o p o e i s unc ionali y. This less- han o acle implemen a ion
wo ks on any numbe o qubi s and does no equi e any ancilla qubi s. Rega ding dep h, he p oposed
implemen a ion is compa ed wi h he one gene a ed by Qiski au oma ic me hod, Diagonal. We show ha
he dep h o ou less- han o acle implemen a ion is always lowe . In addi ion, a compa ison wi h ano he
me hod o o acle gene a ion in e ms o ga e coun is also conduc ed o p o e he e iciency o ou me hod.
The esul p esen ed he e is pa o a esea ch wo k ha aims o achie e eusable quan um ope a ions ha
can be composed o pe o m mo e complex ones. The inal aim is o p o ide Quan um De elope s wi h ools
ha can be easily in eg a ed in hei p og ams/ci cui s.
1. In oduc ion
We a e cu en ly on he noisy in e media e-scale quan um (NISQ)
e a (P eskill,2018) whe e quan um compu e s wi h se e al qubi s
(quan um bi s) a e a ailable (Zhu e al.,2022;Huang e al.,2020;Wang
e al.,2018). This has enabled quan um so wa e de elope s o es
he heo e ical wo k on quan um algo i hms on eal de ices (Figga
e al.,2017;Vande sypen e al.,2001). This has mo i a ed a signi i-
can esea ch e o de o ed o he op imisa ion o exis ing quan um
algo i hms and he c ea ion o new ones.
Quan um algo i hms y o le e age he quan um p ope ies o
qubi s o each a inal quan um s a e whe e some o he s a es ha e
inc eased ampli ude. These s a es a e he mos p obable solu ion o he
p oblem being add essed. The possibili y o ha ing supe posi ion s a es
and he way ampli udes a e manipula ed means ha ce ain p oblems
can be sol ed mo e e icien ly by quan um compu e s han by classical
ones (Vande sypen e al.,2001;Ce ezo e al.,2021). A well-known
example o his is G o e ’s algo i hm.
✩Edi o : Ra aela Mi andola.
∗Co esponding au ho .
E-mail add ess: [email p o ec ed] (J. Ga cia-Alonso).
G o e p esen ed (G o e ,1996) a quan um algo i hm ha sea ches
in an uno de ed sequence as e han any known classical algo i hm.
This algo i hm wo ks by combining wo quan um ope a ions. Fi s , i
ma ks (by gi ing i a 𝜋-phase) he desi ed quan um s a e. This ma king
ope a ion is known as o acle. Then, he second ope a ion aims o
ampli y he ampli ude o he ma ked s a e. This ope a ion is called
di usion ope a o o di use . In o de o each such ampli ica ion
i is o en needed o epea he pai o acle-di use se e al imes.
The gene alisa ion o G o e o ampli y mul iple s a es is known as
Ampli ude Ampli ica ion (AA) (B assa d e al.,2002;G o e ,1998).
In his pape we p esen an algo i hm o he au oma ic gene a ion
o o acles ha pe o m a less- han ope a ion. Taking as inpu a quan-
um s a e in which qubi s encode na u al numbe s (including 0), his
o acle gi es a 𝜋-phase o hose numbe s less han a gi en one.
The comple e less- han ope a ion is applied using his o acle in
G o e ’s algo i hm. I s complexi y unc ion is (√𝑁∕𝑀), whe e 𝑁is
he numbe o na u als encoded in he quan um s a e and 𝑀(1≤𝑀 <
𝑁) is he numbe o na u als less han he gi en numbe .
h ps://doi.o g/10.1016/j.jss.2024.112203
Recei ed 30 Sep embe 2023; Recei ed in e ised o m 30 July 2024; Accep ed 29 Augus 2024
The Jou nal o Sys ems and So wa e 219 (2025) 112203
A ailable online 4 Sep embe 2024
0164-1212/© 2024 The Au ho (s). Published by Else ie Inc. This is an open access a icle unde he CC BY-NC-ND license ( h p://c ea i ecommons.o g/licenses/by-
nc-nd/4.0/ ).
J. Sanchez-Ri e o e al.
Thus, he complexi y unc ion is bounded abo e by (√𝑁)(be e
han classical (𝑁) o an uno de ed sequence o na u als). Mo eo e ,
he p o ided implemen a ion a oids he use o ancilla qubi s.
The esul p esen ed he e is pa o a esea ch wo k ha aims o
achie e eusable and composable quan um ope a ions. Fo example,
om he less- han o acle, a g ea e - han o acle can be easily ob ained,
and by combining bo h, anges o in ege s can also be p oduced.
The es o he pape is o ganised as ollows. Nex , in Sec ion 2,
he backg ound o his wo k is p o ided. Then, a de ailed desc ip ion
o he classical algo i hm o he au oma ic gene a ion o he less-
han implemen a ion is p esen ed in Sec ion 3. A o mal p oo ha he
gene a ed implemen a ion ac ually ma ks he desi ed s a es is shown in
4. Resul s o simula ions and expe imen s on eal quan um ha dwa e
a e discussed on Sec ion 5. A s udy o he e iciency o he o acle and
compa isons wi h o he me hods a e p o ided in Sec ion 6. Finally, he
conclusions and u u e wo k a e p esen ed in Sec ion 7.
A p e ious e sion o his wo k was o iginally p esen ed as a con-
e ence pape (Sanchez-Ri e o e al.,2023). In his documen we ha e
added he o mal p oo o he o acle’s co ec ness on Sec ion 4. The
implemen a ion o mul i-qubi s ga es is changed o he linea -g ow h
om da Sil a and Pa k (2022) and in consequence he expe imen s
and simula ions ha e all been epea ed. Sec ion 6has been com-
ple ely upda ed o compa e e sus Qiski ’s bes me hod and e sus he
Phase- ole an me hod p esen ed in Seidel e al. (2023).
2. Backg ound
2.1. Ga e-based quan um-compu ing
A quan um logic ga e is each ope a ion pe o med on he quan um
ci cui , analogous o he classical logic ga es. Ma hema ically, each ga e
is ep esen ed by a 2𝑛× 2𝑛uni a y ma ix whe e 𝑛is he numbe o
qubi s and 𝑁= 2𝑛s a es which o m an o hono mal basis.
The ac ion o a ga e on a speci ic quan um sys em is de e mined
by mul iplying he s a e ec o by he ma ix ep esen a ion o he
ga e (Nielsen and Chuang,2000). The s a e ec o ep esen s he ampli-
ude o he quan um s a es o he sys em. The p obabili y o measu ing
one gi en s a e in he compu a ional basis is gi en by he squa ed
modulus o he ampli ude associa ed wi h ha s a e.
To illus a e hese concep s, conside a quan um sys em wi h wo
qubi s. The s a e ec o 𝝍 o such a sys em in he compu a ional basis
migh be ep esen ed as:
𝝍=⎛⎜⎜⎜⎜⎝
𝑐00
𝑐01
𝑐10
𝑐11
⎞⎟⎟⎟⎟⎠
=(𝑐00 𝑐01 𝑐10 𝑐11)𝑇
whe e each 𝑐𝑖𝑗 ep esen s he ampli ude associa ed wi h he basis s a e
|𝑖𝑗⟩. In his con ex , he basis s a es |00⟩,|01⟩,|10⟩, and |11⟩ o a
ou -s a e o hono mal basis. Fo example, i he sys em is in he s a e
𝜓= (1000)𝑇, his means ha he ampli udes a e 1 o he s a e |00⟩
and 0 o he emaining s a es |01⟩,|10⟩and |11⟩, and consequen ly,
he p obabili ies o measu ing each s a e in he compu a ional basis a e
gi en by he squa ed modulus o he espec i e ampli udes. In his case
|1|2= 1 o s a e |00⟩and |0|2= 0 o he emaining s a es. Thus, he
sys em has a 100% chance o being measu ed in he s a e |00⟩and no
chance o being measu ed in he s a es |01⟩,|10⟩, o |11⟩.
Le now conside he applica ion o he X ga e, which o a single
qubi is ep esen ed by he ma ix:
𝑋=(0 1
1 0)
To apply he X ga e o bo h qubi s in a wo-qubi sys em, we need
o use he enso p oduc o he X ga e wi h i sel . This is because
he enso p oduc allows us o cons uc a ma ix ha ope a es on
he combined s a e space o bo h qubi s. The combined ope a ion o
applying he X ga e o bo h qubi s is:
𝑋 ⊗ 𝑋 =⎛⎜⎜⎜⎜⎝
0001
0010
0100
1000
⎞⎟⎟⎟⎟⎠
Applying his ope a ion o he ini ial s a e ec o 𝝍:
𝝍′=⎛⎜⎜⎜⎜⎝
0001
0010
0100
1000
⎞⎟⎟⎟⎟⎠
⎛⎜⎜⎜⎜⎝
1
0
0
0
⎞⎟⎟⎟⎟⎠
=⎛⎜⎜⎜⎜⎝
0
0
0
1
⎞⎟⎟⎟⎟⎠
This means ha he new p obabili ies o measu ing each s a e a e:
|0|2= 0 o s a es |00⟩,|01⟩and |10⟩, and |1|2= 1 o s a e |11⟩. Thus,
a e applying he X ga e o bo h qubi s, he sys em has a 100% chance
o being measu ed in he s a e |11⟩, wi h no chance o being measu ed
in he o he s a es.
2.2. O acles
The o acle has been iden i ied as a pa e n o quan um algo-
i hms (Leymann,2019). An o acle can be hough as a black box
pe o ming a unc ion ha is used as an inpu by ano he algo i hm (Liu
and Zhou,2021). Thus, how an o acle wo ks is no a ma e o conce n
o he algo i hm ha uses i . These ea u es make o acles a good
ool o quan um so wa e euse. Apa om G o e ’s, many o he
algo i hms employ o acles. Some well known examples a e Deu sch and
Jozsa (1992), Simon (1997) o Be ns ein and Vazi ani (1997).
The e a e wo main ypes o o acles desc ibed in he li e a u e (Gi-
lyén e al.,2019), p obabili y o acles and phase o acles. On one hand,
p obabili y o acles a e common in quan um op imisa ion p ocedu es
and encode a unc ion in he ampli ude o he quan um s a es. On he
o he hand, phase o acles a e used in quan um algo i hms (such as
G o e ’s) and encode a unc ion in he phase o he quan um s a es. In
he case o G o e ’s algo i hm, he unc ion implemen ed by he o acle
ecognises he desi ed s a es. As men ioned abo e, he less- han o acle
de eloped in his wo k is a phase o acle.
Thinking o o acles in e ms o black boxes a ou s he eusabili y
o quan um so wa e. One would hen expec any eusable so wa e o
ha e he bes possible quali y a ibu es. Today’s quan um de ices a e
subjec o decohe ence. Thus, he dep h o he ci cui s is a key aspec
o maximise hei eliabili y. The g ea e he dep h o a ci cui , he
mo e i is exposed o decohe ence and he lowe i s eliabili y (Saki
e al.,2019). The e o e, i he dep h o he ci cui ha implemen s a
quan um algo i hm is no aken in o accoun , i can end up p oducing
a esul ha is indis inguishable om pu e noise (P eskill,2018).
So keeping dep h o o acles op imised, con ibu es o op imise hei
quali y a ibu es and hei chance o be eused.
To educe he dep h o he less- han o acle, he linea -dep h mul i-
con olled ga e p oposed in da Sil a and Pa k (2022) is eused as
a piece o exis ing quan um so wa e. The dep h o his ga e scales
linea ly on he numbe o qubi s, imp o ing he polynomial g ow h
o p e ious implemen a ions. I does no equi e any ancilla qubi s
and ou pe o ms Qiski ( A e al.,2021) implemen a ion om i e
qubi s onwa ds. In addi ion, esul s show ha he linea -dep h mul i-
con olled ga e is use ul on NISQ de ices and imp o es he accu acy o
esul s.
In o de o p ope ly con ex ualise he dep h o he ci cui associa ed
o he o acle p oposed in his pape , we compa e i o Diagonal, a
me hod implemen ed in Qiski ( A e al.,2021) which au oma ically
gene a es an implemen a ion o an o acle p o ided i s ma ix (Diagonal
Ga e,2020). This Diagonal me hod is based on (Shende e al.,2004).
The e a e o he au oma ic me hods o o acle gene a ion, such as Seidel
e al. (2023). Howe e , as Qiski is one o he mos used quan um
The Jou nal o Sys ems & So wa e 219 (2025) 112203
2
J. Sanchez-Ri e o e al.
SDKs, we ha e chosen o compa e he pe o mance o he less- han
implemen a ion wi h he Diagonal gene a ed ci cui .
Besides dep h, he ype o ga es is also key in he eliable execu ion
o quan um ci cui s (Lee e al.,2006) as p ecision di e s om one
ga e o ano he . A ga e coun compa ison is also conduc ed compa ing
ou me hod wi h bo h Diagonal me hod om Qiski and Phase Tole an
me hod om Seidel e al. (2023).
In his pape no only he concep o he o acle is p o ided, also
a classical algo i hm is de ailed o au oma ically gene a e an e icien
implemen a ion o he p oposed less- han o acle. This algo i hm could
be included as a pa e n o he less- han p oblem in in elligen code
gene a o s such as he one men ioned in Gemeinha d e al. (2021).
3. Algo i hm o he au oma ic gene a ion o he o acle
In his sec ion we de ail he classical algo i hm designed o au o-
ma e he building o he o acle ci cui . This o acle will ma k wi h a
𝜋-phase all quan um s a es which ep esen na u al numbe s s ic ly
smalle han a gi en one. The o acle is ep esen ed by a uni a y ma ix
o he o m:
⎛⎜⎜⎜⎜⎜⎜⎝
−1
⋱
−1
0
1
⋱
0
1
⎞⎟⎟⎟⎟⎟⎟⎠
(1)
whe e he ma ix ha e 2𝑛𝑞𝑢𝑏𝑖𝑡𝑠 ×2𝑛𝑞𝑢𝑏𝑖𝑡𝑠 elemen s, being 𝑛𝑞𝑢𝑏𝑖𝑡𝑠 he numbe
o qubi s. The diagonal hus has 2𝑛𝑞𝑢𝑏𝑖𝑡𝑠 elemen s. The diagonal has a
numbe o −1s equal o 𝑚and a numbe o 1s equal o 2𝑛𝑞𝑢𝑏𝑖𝑡𝑠 −𝑚, whe e
𝑚is he h eshold in ege .
The classical algo i hm we p opose is based on he idea ha , in
o de o compa e he bina y ep esen a ion o wo na u al numbe s
𝑛1and 𝑛2, i is needed o look o he i s bi (s a ing a he mos
signi ican one) which di e s in hese wo numbe s. Once his bi is
ound, i is compa ed o he wo numbe s, he one whose bi is 0is he
smalle one. E.g. when compa ing1𝑛1= 1112= 7 and 𝑛2= 1012= 5,
he mos signi ican bi s a e bo h equal o 1, he second mos signi ican
bi s di e . The bi which is 0 belongs o 𝑛2, hence 𝑛2is he smalle one.
Algo i hm 1shows he pseudocode o his algo i hm. The quan um
ci cui gene a ed by his algo i hm can be ound in he nex sec ion
in Eq. (8).
The algo i hm consis s o ou s eps, agged in he pseudocode. The
i s pa is ob aining he bina y exp ession o 𝑚. Secondly, a 𝜋-phase is
gi en depending on he mos signi ican bi , by means o he ope a o
𝑉. The hi d s ep is gi ing a 𝜋-phase o he emaining bi s, alues o
he index 𝑖 om 𝑛−2 o 0, by he ope a o s 𝑈𝑖. Las s ep is e u ning he
qubi s co esponding o bi s equal o 0 o he o iginal s a e by means
o 𝑋ga es.
The algo i hm needs as inpu s he numbe o qubi s 𝑛and a na u al
numbe 𝑚whe e 0< 𝑚 < 2𝑛. As s a ed be o e, he ou pu o ou
algo i hm p oduces a quan um ci cui wi h 𝑛qubi s which gi es a 𝜋-
phase o all s a es ep esen ing na u al numbe s s ic ly smalle han
𝑚.
The i s s ep o he algo i hm is con e ing he numbe 𝑚 o bina y
o m, 𝑚bina y =𝑏𝑛−1 …𝑏0, wi h 𝑛bi s.2This is always possible because
𝑚 < 2𝑛.
A e ha , i p oceeds o check he i s bi (mos signi ican ) o
𝑚bina y,𝑏𝑛−1. I i is 1, hence 𝑚≥2𝑛−1, hen he ga es 𝑋𝑍𝑋 a e applied
o he qubi 𝑞𝑛−1 o he quan um ci cui (2). This gi es a 𝜋-phase o he
1In numbe s like 1012 he 2 in he subindex means ha i is a bina y
numbe .
2In he case 𝑛= 4 and 𝑚= 3, he bina y o m would be 𝑚bina y = 0011.
s a es o he o m |0𝑞𝑛−2 …𝑞0⟩, which ep esen numbe s smalle han
2𝑛−1, hus smalle han 𝑚.
𝑋𝑍𝑋 ⊗ 𝐼⊗(𝑛−1)|𝑞𝑛−1 …𝑞0⟩= −𝛼0|0𝑞𝑛−2 …𝑞0⟩+𝛼1|1𝑞𝑛−2 …𝑞0⟩(2)
whe e 𝛼0and 𝛼1a e he ampli udes o he s a e |0𝑞𝑛−2 …𝑞0⟩and
|1𝑞𝑛−2 …𝑞0⟩ espec i ely, i.e. |𝛼0|2+|𝛼1|2= 1, and 𝐼⊗(𝑛−1) is he iden i y
ga e applied o he 𝑛− 1 leas signi ican qubi s.
Algo i hm 1: Less- han o acle classical builde
Inpu : Numbe o qubi s 𝑛and a na u al numbe 𝑚whe e
0<𝑚<2𝑛
Ou pu : Quan um Ci cui which gi es a 𝜋-phase o all s a es
ep esen ing bina y o ms o na u al numbe s smalle
han 𝑚
/* Bina y exp ession o 𝑚*/;
𝑚bina y ←bina y(𝑚);
𝑄𝑢𝑎𝑛𝑡𝑢𝑚𝐶𝑖𝑟𝑐𝑢𝑖𝑡 ←Ci cui o 𝑛qubi s;
𝑏𝑛−1 ←1s bi (mos signi ican ) o 𝑚bina y;
/* 𝑉ope a o */;
i 𝑏𝑛−1 = 0 hen
𝑋ga e o 𝑞𝑛−1;
else
𝑋ga e o 𝑞𝑛−1;
𝑍ga e o 𝑞𝑛−1;
𝑋ga e o 𝑞𝑛−1;
end
/* 𝑈𝑖ope a o */;
o 𝑖←𝑛− 2 o 0do
𝑏𝑖←𝑖- h bi o 𝑚bina y;
𝑞𝑖←𝑖- h qubi o 𝑄𝑢𝑎𝑛𝑡𝑢𝑚𝐶𝑖𝑟𝑐𝑢𝑖𝑡;
i 𝑏𝑖= 0 hen
𝑋ga e o 𝑞𝑖;
else
𝑋ga e o 𝑞𝑖;
𝐶⊗(𝑛−𝑖−1)𝑍ga e o qubi s 𝑞𝑛−1,…, 𝑞𝑖;
𝑋ga e o 𝑞𝑖;
end
end
/* 𝑋⊗𝑀0ope a o */;
o 𝑖←0 o 𝑛− 1 do
i 𝑏𝑖= 0 hen
𝑋ga e o 𝑞𝑖;
end
end
Else, i 𝑏𝑛−1 is 0, an 𝑋ga e is applied o 𝑞𝑛−1, which will be e e sed
a he end o he ci cui , 𝑋 ⊗𝐼⊗(𝑛−1). The e o e, he ope a o ega ding
𝑏𝑛−1 is he ollowing:
𝑉=𝛿𝑏𝑛−11(𝑋𝑍𝑋 ⊗ 𝐼⊗(𝑛−1))+𝛿𝑏𝑛−10(𝑋 ⊗ 𝐼⊗(𝑛−1))(3)
The ollowing ope a o ollows he same pa e n o he emainde
posi ions, 𝑖∈ {𝑛− 2,…,0}. I 𝑏𝑖is 0, an X ga e is applied o 𝑞𝑖,
𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋 ⊗ 𝐼⊗(𝑖). In case 𝑏𝑖is 1, he ga es
(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋)⋅𝐶⊗(𝑛−𝑖−1)𝑍⋅(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋)(4)
a e applied o {𝑞𝑛−1,…, 𝑞𝑖}. This gi es a 𝜋-phase o he s a es
|𝑏𝑛−1 …𝑏𝑖+1 0𝑞𝑖−1 …𝑞0⟩. As explained be o e, i he 𝑖 h bi o 𝑚bina y is
1, all numbe s wi h 0 in he 𝑖 h bi and he same 𝑛−𝑖− 1 i s bi s
as 𝑚bina y (𝑏𝑛−1 …𝑏𝑖+1) a e smalle han 𝑚. The ope a o ega ding 𝑏𝑖is
he ollowing:
𝑈𝑖=𝛿𝑏𝑖1((𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋)⋅𝐶⊗(𝑛−𝑖−1)𝑍⋅(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋))⊗ 𝐼⊗(𝑖)
+𝛿𝑏𝑖0(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋 ⊗ 𝐼⊗(𝑖))(5)
The Jou nal o Sys ems & So wa e 219 (2025) 112203
3
J. Sanchez-Ri e o e al.
Fig. 1. O acle gene a ed aking 𝑚= 11 = 10112wi h 4 qubi s.
Finally, an 𝑋ga e is applied o each 𝑞𝑖such ha 𝑏𝑖= 0,
𝑛−1
∏
𝑖=0 ∶ 𝑏𝑖=0
𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋 ⊗ 𝐼⊗(𝑖)(6)
This is done because ano he 𝑋ga e was applied o hem in p e ious
s eps o he algo i hm, so ope a ion (6) e u ns hese qubi s o he ini ial
s a e, excep o a possible 𝜋-phase.
Le 𝑀0= {𝑖∈ [0,…, 𝑛−1] |𝑏𝑖= 0 ∀𝑏𝑖∈𝑚bina y}, hen we deno e he
ope a o in Eq. (6) as 𝑋⊗𝑀0. Thus, he less- han o acle can be o mally
w i en as:
𝑉⋅(𝑛−2
∏
𝑖=0
𝑈𝑖)⋅𝑋⊗𝑀0(7)
As an illus a i e example o he algo i hm ou pu , we show he
o acle gene a ed aking 𝑚= 11 = 10112in Fig. 1.
I can be obse ed ha he quan um ci cui gene a ed by Algo i hm
1does no equi e ancilla qubi s o wo k as in ended. The only pa o
he gene a ed o acle whose dep h could be educed by he inclusion
o ancilla qubi s a e he mul i-con olled ga es. Howe e , o hese
ga es we use he implemen a ion desc ibed in da Sil a and Pa k (2022)
ha does no include he use o ancilla qubi s o dep h educ ion.
No equi ing ancilla qubi s allows he use o all a ailable qubi s o
encoding he na u al numbe s.
F om his poin , he implemen a ion o he g ea e - han o acle
men ioned abo e is i ial. E en mo e, he o acles g ea e - han and
less- han can be composed in a way ha , by combining hem, we
ob ain anges o in ege s. This o acle is ob ained ega dless o he
o de he g ea e - han and less- han o acles a e applied, so hey ul il
he commu a i e p ope y. Mo eo e , hey can be g ouped in di e en
o acles ob aining he same esul . Fo ins ance, i we apply a less-
han o acle and a g ea e - han (which become a ange) and a e wa ds
ano he less- han o acle is applied, he inal esul is he same as i a
less- han o acle is applied and, a e ha , a ange o in ege s (g ea e -
han and a less- han o acles) is applied. This can be unde s ood as
he associa i e p ope y o he o acles. Al hough his aspec is no
exploi ed in his wo k i is one o he key mo i a ions behind i . These
combina ions and u he examples o less- han o acles may be ound
in he eposi o y included in Code and Da a.
3.1. Algo i hm’s ime complexi y and ci cui ’s complexi y
The algo i hm’s ime complexi y de i es di ec ly om he pseu-
docode 1o he algo i hm. The e a e only wo o loops om 0 o 𝑛,
which a e (𝑛). Inside one o hose, a each i e a ion 𝑘∈ [1,…, 𝑛], a
ga e 𝐶𝑘𝑍is cons uc ed, which is (𝑘). The e o e, ime complexi y o
he classical algo i hm is (𝑛2).
Rega ding he quan um ci cui gene a ed, i s complexi y is he
dep h o he ci cui by he de ini ion o dep h (Nielsen and Chuang,
2000). This is analysed in dep h in Sec ion 6.
4. Ma hema ical p oo o he o acle’s co ec ness
P oposi ion 1. Le 𝑚be a non-nega i e in ege , 𝑚∈Z,𝑚 > 0. Le 𝑛be
an in ege such ha 2𝑛> 𝑚. Le 𝑚bina y =𝑏𝑛−1 …𝑏0be i s bina y o m wi h
𝑛bi s. Le he o acle be he nex se o ga es:
𝑉⋅(𝑛−2
∏
𝑖=0
𝑈𝑖)⋅𝑋⊗𝑀0(8)
whe e
•𝑀𝑘is he se o indices o bi s o 𝑚bina y whose alue is 𝑘∈ {0,1}.
In he case o 𝑀0, i is o med by he posi ions o he 0s in 𝑚bina y.
Fo mally:
𝑀𝑘= {𝑖|𝑏𝑖=𝑘∀𝑏𝑖∈𝑚bina y}
•𝑋⊗𝑀0is an ope a o which applies an 𝑋ga e o hose qubi s 𝑞𝑖such
ha 𝑏𝑖∈𝑀0, i.e, 𝑏𝑖= 0. Fo mally:
𝑋⊗𝑀0=∏
𝑖∈𝑀0
𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋 ⊗ 𝐼⊗(𝑖)
•𝑉is he ope a o which applies an 𝑋ga e o 𝑞𝑛−1 i 𝑏𝑛−1 = 0 and he
ga es 𝑋𝑍𝑋 o 𝑞𝑛−1 i 𝑏𝑛−1 = 1. Fo mally i can be w i en as ollows:
𝑉=𝛿𝑏𝑛−11(𝑋𝑍𝑋 ⊗ 𝐼⊗(𝑛−1))+𝛿𝑏𝑛−10(𝑋 ⊗ 𝐼⊗(𝑛−1))
whe e 𝛿𝑖𝑗 is he K onecke del a.
•𝑈𝑖,0< 𝑖 < 𝑛 − 1, is he ollowing ope a o :
𝑈𝑖=𝛿𝑏𝑖1((𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋)⋅𝐶⊗(𝑛−𝑖−1)𝑍⋅(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋))⊗ 𝐼⊗(𝑖)
+𝛿𝑏𝑖0(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋 ⊗ 𝐼⊗(𝑖))
The o acle (8) gi es a 𝜋-phase o all s a es which ep esen a na u al
numbe smalle han 𝑚.
P oo . The p oo ollows he nex o de : Fi s , we p o e ha |0⟩is
always ma ked (i ep esen s he 0 hence i is always smalle han
𝑚 > 0). Then we ake wo digi s 𝑏𝑖, 𝑏𝑗in 𝑚bina y,𝑖<𝑗, such ha
𝑏𝑖=𝑏𝑗= 1 and 𝑏𝑘= 0 o e e y 𝑘be ween 𝑖and 𝑗, i.e, 𝑏𝑖and 𝑏𝑗
a e consecu i e 1s in 𝑚bina y. And we p o e ha he ope a o s 𝑈𝑖and
𝑈𝑗, co esponding o 𝑏𝑖and 𝑏𝑗, gi e a 𝜋-phase o consecu i e s a es,
i.e., s a es which ep esen consecu i e in ege s. Finally, we p o e ha
he numbe o s a es ma ked a e 𝑚.
Le 𝑏𝑛−1 be he mos signi ican bi o 𝑚bina y. Because o hypo hesis,
𝑚bina y can be w i en wi h 𝑛bi s. In case ewe bi s a e needed, he
mos signi ican bi s no used a e 0. The bina y decomposi ion o 𝑚is:
𝑚=
𝑛−1
∑
𝑖=0
𝑏𝑖⋅2𝑖(9)
Le us ocus on he mos signi ican bi , 𝑏𝑛−1, i s . I 𝑏𝑛−1 = 1 ⇒𝑚≥
2𝑛−1, hen he ope a o 𝑋𝑍𝑋 ⊗ 𝐼⊗(𝑛−1) is
𝑋𝑍𝑋 ⊗ 𝐼⊗(𝑛−1)|𝑞𝑛−1 …𝑞0⟩= −𝛼0|0𝑞𝑛−2 …𝑞0⟩+𝛼1|1𝑞𝑛−2 …𝑞0⟩
whe e 𝛼0and 𝛼1a e he ampli udes o he s a e |0𝑞𝑛−2 …𝑞0⟩and
|1𝑞𝑛−2 …𝑞0⟩ espec i ely, i.e. |𝛼0|2+|𝛼1|2= 1.
The Jou nal o Sys ems & So wa e 219 (2025) 112203
4
J. Sanchez-Ri e o e al.
This gi es a 𝜋-phase o all he s a es ep esen ing numbe s s ic ly
smalle han 2𝑛−1, namely s a e |0⟩.
In case 𝑏𝑛−1 = 0, an X ga e is applied. So he ope a o 𝑉co espond-
ing o 𝑏𝑛−1, which is applied in he i s place, is:
𝑉=1{𝑏𝑛−1=1}𝑋𝑍𝑋 ⊗ 𝐼⊗(𝑛−1) +1{𝑏𝑛−1=0}𝑋 ⊗ 𝐼⊗(𝑛−1)
Le 𝑏𝑘be he i s bi equals o 1, so 𝑏𝑙= 0 o all 𝑘<𝑙≤𝑛− 1. Then,
all ope a o s applied up o his poin , 𝑉 , 𝑈𝑛−2,…, 𝑈𝑘+1, 𝑈𝑘3a e as i
ollows:
𝑉⋅𝑈𝑛−2 ⋯𝑈𝑘+1 ⋅𝑈𝑘=(𝑋(𝑛−1−𝑘)⊗ 𝐼(𝑘+1))⊗ 𝑈𝑘(10)
whe e
𝑈𝑘=(𝐼⊗(𝑛−𝑘−1) ⊗ 𝑋)⋅𝐶⊗(𝑛−𝑘−1)𝑍⋅(𝐼⊗(𝑛−𝑘−1) ⊗ 𝑋)⊗ 𝐼⊗(𝑘)(11)
as 𝑏𝑘= 1.
The ope a o desc ibed in (10) gi es a 𝜋-phase o he s a es which
ollow he nex pa e n:
|𝑏𝑛−1𝑏𝑛−2 …𝑏𝑘+1 0𝑞𝑘−1 …𝑞0⟩=|0 0 … 0 𝑞𝑘−1 …𝑞0⟩
This anges be ween he s a es
|𝛼𝑘⟩=|𝑏𝑛−1 …𝑏𝑘+1 0 0 … 0⟩=|00…00⟩
|𝛽𝑘⟩=|𝑏𝑛−1 …𝑏𝑘+1 0 1 … 1⟩=|0 … 0 0
⏟⏟⏟
𝑘 h
1 … 1⟩
whe e
𝛼𝑘= 0
𝛽𝑘=
𝑘−1
∑
𝑙=1
2𝑙−1
Be ween hese wo s a es, including hem as well, he e a e he ollow-
ing numbe o s a es:
𝑛[𝛼𝑘,𝛽𝑘]=𝛽𝑘−𝛼𝑘+ 1 =
𝑘−1
∑
𝑙=1
2𝑙−1 + 1 = 2𝑘−1
The ma ix associa ed wi h ope a o (10) is a diagonal ma ix wi h
0s ou side o he main diagonal:
diag{−1,…,−1
⏟⏟⏟
𝛽𝑘
,1,…,1}
This pa o he p oo has p o ided a comp ehension o he i s
ope a o and p o ed ha s a e |0⟩is in ac ma ked wi h a 𝜋-phase
ega dless o 𝑚.
Nex , we a e going o p o e ha , p o ided wo consecu i e bi s
equal o 1 in 𝑚bina y,𝑏𝑖and 𝑏𝑗, i.e. 𝑏𝑙= 0 o 𝑖 < 𝑙 < 𝑗,𝑈𝑖and 𝑈𝑗
gi e a 𝜋-phase o consecu i e s a es.4
Le 𝑘<𝑖<𝑛i 𝑏𝑛−1 = 0 o 2≤𝑖<𝑛i 𝑏𝑛−1 = 1. In case
𝑏𝑖= 0, an 𝑋ga e is applied o qubi 𝑞𝑖, which will be cancelled by
ano he 𝑋ga e a he end o he ci cui , which would be equi alen
o applying an iden i y ga e 𝐼. O he wise, i 𝑏𝑖= 1, he ope a o
(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋)⋅𝐶⊗(𝑛−𝑖−1)𝑍⋅(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋)is applied (as in (11)). The
combina ion o bo h cases is he ope a o 𝑈𝑖:
𝑈𝑖=𝛿𝑏𝑖1((𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋)⋅𝐶⊗(𝑛−𝑖−1)𝑍⋅(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋))⊗ 𝐼⊗(𝑖)
+𝛿𝑏𝑖0(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋 ⊗ 𝐼⊗(𝑖))
We ollow now he same easoning as in he i s pa . Ope a o 𝑈𝑖
gi es a 𝜋-phase o he s a es which ollow he nex pa e n:
|𝑏𝑛−1𝑏𝑛−2 …𝑏𝑖+1 0𝑞𝑖−1 …𝑞0⟩
3Plus he las 𝑋ga es applied a he end o qubi s co esponding o bi s
equal o 0, ope a o 𝑋⊗𝑀0, in his case on 𝑞𝑛−1, 𝑞𝑛−2 …, 𝑞𝑘+1.
4No e ha 𝑈𝑙in oduce no phase o any qubi , by de ini ion o he ope a o
𝑈𝑖, as 𝑏𝑙= 0.
This anges be ween he s a es
|𝛼𝑖⟩=|𝑏𝑛−1𝑏𝑛−2 …𝑏𝑖+1 0 0 … 0⟩
|𝛽𝑖⟩=|𝑏𝑛−1𝑏𝑛−2 …𝑏𝑖+1 0 1 … 1⟩
whe e
𝛼𝑖=
𝑛
∑
𝑙=𝑖+1
𝛿𝑏𝑙1⋅2𝑙−1
𝛽𝑖=
𝑛
∑
𝑙=𝑖+1
𝛿𝑏𝑙1⋅2𝑙−1 +
𝑖−1
∑
𝑙=1
2𝑙−1
Be ween hese wo s a es, including hem as well, he e a e his
numbe o s a es:
𝑛[𝛼𝑖,𝛽𝑖]=𝛽𝑖−𝛼𝑖+ 1 =
𝑛
∑
𝑙=𝑖+1
𝛿𝑏𝑙1⋅2𝑙−1 +
𝑖−1
∑
𝑙=1
2𝑙−1 −
𝑛
∑
𝑙=𝑖+1
𝛿𝑏𝑙1⋅2𝑙−1 + 1
=
𝑖−1
∑
𝑙=1
2𝑙−1 + 1 = 2𝑖−1
The ma ix associa ed wi h ope a o 𝑈𝑖is:
diag{1,…,1,−1
⏟⏟⏟
𝛼𝑖
,…,−1
⏟⏟⏟
𝛽𝑖
,1,…,1}
Le 𝑗 < 𝑖 be he nex index such ha 𝑏𝑗= 1 and he e a e no bi s
equal o 1 be ween 𝑏𝑖and 𝑏𝑗, i.e. 𝑏𝑙= 0 o 𝑖<𝑙<𝑗. Then we see ha
|𝛼𝑗⟩=|𝑏𝑛−1𝑏𝑛−2 …𝑏𝑖…𝑏𝑗+1 0 0 … 0⟩
=|𝑏𝑛−1𝑏𝑛−2 …𝑏𝑖0 … 0 0
⏟⏟⏟
𝑗 h
0 … 0⟩
|𝛽𝑗⟩=|𝑏𝑛−1𝑏𝑛−2 …𝑏𝑖…𝑏𝑗+1 0 1 … 1⟩
=|𝑏𝑛−1𝑏𝑛−2 …𝑏𝑖0 … 0 0
⏟⏟⏟
𝑗 h
1 … 1⟩
a e ex emes o he in e al con aining he s a es 𝑈𝑗gi es a 𝜋-phase o.
Mo eo e ,
𝛼𝑗=
𝑛
∑
𝑙=𝑗+1
𝛿𝑏𝑙1⋅2𝑙−1 =
𝑛
∑
𝑙=𝑖
𝛿𝑏𝑙1⋅2𝑙−1
𝛽𝑖=
𝑛
∑
𝑙=𝑗+1
𝛿𝑏𝑙1⋅2𝑙−1 +
𝑗−1
∑
𝑙=1
2𝑙−1 =
𝑛
∑
𝑙=𝑖
𝛿𝑏𝑙1⋅2𝑙−1 +
𝑗−1
∑
𝑙=1
2𝑙−1
whe e we ha e used ha 𝑏𝑖= 1 and 𝑏𝑖−1,…, 𝑏𝑗+1 a e 0. I can be no ed
ha :
𝛽𝑖+1 =
𝑛
∑
𝑙=𝑖+1
𝛿𝑏𝑙1⋅2𝑙−1+
𝑖−1
∑
𝑙=1
2𝑙−1+1 =
𝑛
∑
𝑙=𝑖+1
𝛿𝑏𝑙1⋅2𝑙−1+2𝑖−1 =
𝑛
∑
𝑙=𝑖
𝛿𝑏𝑙1⋅2𝑙−1 =𝛼𝑗
Hence, we obse e ha he ope a o s 𝑈𝑖and 𝑈𝑗ma k consecu i e
s a es. The e o e, gi en ha ope a o 𝑈𝑖ma ks 2𝑖−1 s a es and i is
only applied when 𝑏𝑖= 1, he numbe o s a es ma ked (which a e
consecu i e) a e:
𝑛
∑
𝑖=1
𝑏𝑖⋅2𝑖−1
I is clea ha his is exac ly 𝑚s a es (9). As hese s a es a e consecu i e
and he s a e |0⟩=|0 … 0⟩is ma ked, he o acle o med by all he
ope a o s desc ibed,
𝑉⋅(𝑛−2
∏
𝑖=0
𝑈𝑖)⋅𝑋⊗𝑀0(12)
gi es a 𝜋-phase o he i s 𝑚s a es, which a e he numbe s smalle
han 𝑚. We can conclude ha ope a o (8) gi es a 𝜋-phase o numbe s
smalle han 𝑚.□
The Jou nal o Sys ems & So wa e 219 (2025) 112203
5
J. Sanchez-Ri e o e al.
Fig. 2. Full ci cui implemen ing ope a ion less- han 42 wi h 6 qubi s.
5. Resul s
The bes way o show he unc ionali y o he less- han o acle im-
plemen a ion p esen ed in his wo k is h ough simula ions o di e en
examples o he gene a ed ci cui s and expe imen s on eal quan um
de ices.5Fo his pape , we ha e used Qiski ( A e al.,2021) o
gene a ing he quan um ci cui s and unning he expe imen s.
Fo he algo i hm o wo k as in ended is needed o ini ialise all
qubi s o a uni o m supe posi ion o 0s and 1s by applying a Hadama d
ga e o each one.
We show he esul s o ampli ying he desi ed s a es as desc ibed by
chap e 6 o Nielsen and Chuang (2000). To pe o m Ampli ude Ampli-
ica ion, i is needed o ini ialise all qubi s o a uni o m supe posi ion
o 0s and 1s by applying a Hadama d ga e o each one. Mo eo e , a
di usion ope a o is applied a e he o acle. Depending on he ac ion
𝑁∕𝑀(being 𝑀 he numbe o desi ed s a es and 𝑁 he o al numbe
o s a es), we need o epea he pai o acle-di use se e al imes, wi h
a maximum o ⌈𝜋∕4√𝑁∕𝑀⌉ imes. In Fig. 2, we show an example o
he ull ci cui implemen ing he ope a ion less- han 42 wi h 6 qubi s,
including he ini ialisa ion wi h Hadama d ga es, he wo epe i ions o
he pai o acle-di use and he measu e.
All ou esul s a e gene a ed by unning he ci cui se e al imes,
each o hose uns is called sho . Each sho is he esul p o ided by
measu ing a e unning he ci cui . Hence, he ou pu o one sho is
jus one s a e. Figu es in his sec ion ep esen he ela i e equency
(y-axis) o each s a e (x-axis) measu ed in he se e al sho s ealised. The
esul s shown a e gene a ed by unning 20,000 sho s o each ci cui .
This choice is based on he maximum numbe o sho s allowed in IBM
eal quan um de ices. This is done o p ope ly compa e simula ions and
eal expe imen s.
5.1. Simula ions
Simula ions shown in his sec ion we e un on a s anda d lap op6
and execu ion ime anged be ween 8 and 10 s o each o hem.
Figs. 3 and 4a e examples wi h 6-qubi ci cui s. Fig. 3 shows
he esul o he less- han 42 ampli ica ion. The desi ed s a e is a
supe posi ion o he i s 42 s a es:
1
√42
41
∑
𝑖=0|𝑖⟩(13)
The pai o acle-di use had o be epea ed 2 imes o each max-
imum ampli ica ion o he desi ed s a e. Full ci cui can be seen in
5The code o he au oma ic gene a ion and he da a o he simula ions
and expe imen s can be ound in Code and Da a.
6CPU: In el(R) Co e(TM) i5-7200U CPU @ 2.50 GHz, 2701 MHz. RAM: 8
GM.
Fig. 2. I can be seen ha he esul s a e exac ly as we would expec
sa e o mino equency di e ences. This is due o he numbe o sho s
simula ed. The equency o each numbe ends o he heo e ical alue
(1∕42 in his case) when he numbe o sho s ends o in ini y.
Fig. 4 displays esul s o he less- han 13 ope a ion. In con as wi h
esul s in Fig. 3, in his case he e a e some small occu ences o non-
desi ed s a es. The cause o his is ha he bes ampli ica ion possible,
which occu s wi h 1 i e a ion, is no exac ly 100%.
Resul s om less- han 4 ope a ion on a 4-qubi ci cui a e shown in
Fig. 5. In his case, he numbe o i e a ions o he pai o acle-di use
is also 1, howe e he ampli ica ion eaches 100% measu emen p ob-
abili y o he desi ed s a es. The main objec i e o his example is o
compa e a simula ion wi h an execu ion on a eal quan um de ice. Such
esul s a e a ailable in he nex sec ion.
The numbe s used o pe o m he less- han ope a ions in his sec ion
(42, 13 and 4) ha e been chosen o showcase ha Ampli ude Ampli i-
ca ion, e en in absence o noise, does no always pe ec ly ampli y he
desi ed s a es.
5.2. Expe imen s on eal quan um ha dwa e
We ha e un he las simula ion, less- han 4 ampli ica ion on a 4-
qubi ci cui , on a eal quan um de ice wi h 20,000 sho s as well.
We ha e chosen his ope a ion speci ically because o 4 qubi s he
ull ampli ica ion ci cui is he one wi h lowe dep h. Resul s o he
expe imen can be seen in Fig. 6. The e o is no iceable, which is an
expec ed beha iou wi h eal quan um ha dwa e.
Despi e hese e o s, he desi ed s a es ha e a combined equency
o ≈63%, e en hough hey a e 4 s a es ou o 16 in o al, 25%. Hence
we managed o ampli y he measu emen p obabili y o he desi ed
s a es by a ≈2.5 ac o on an ac ual quan um de ice.
The esul s o he expe imen s wi h mo e han 4 qubi s a e indis-
inguishable om pu e noise. The dep h o he mul i-con olled ga es
ha a ec s all qubi s in he ci cui ( o example, he mul i-con olled
Z-ga e in he di use ) scales hea ily wi h he numbe o qubi s and he
ideli y o he de ice is no enough o achie e a sa is ac o y esul .
The de ice used o his expe imen was an IBM machine,
ibm_nai obi, on No embe 18 h, 2022 13:22 UTC. This de ice uses a
Falcon 5.11H p ocesso . The calib a ion da a o he de ice a he ime
o he expe imen can be ound in he eposi o y in Code and Da a.
6. Compa ison wi h o he me hods
In his sec ion, we ealise se e al compa isons wi h o he me h-
ods, bo h in dep h and ype o ga es. In a p e ious wo k om he
au ho s (Sanchez-Ri e o e al.,2023), an ini ial, less e icien e sion
o he o acle gene a ion algo i hm p esen ed he e was compa ed wi h
he Qiski me hod Uni a yGa e al eady showing be e pe o mance in
e ms o ci cui dep h.
6.1. Dep h compa ison wi h diagonal me hod
Fi s ly, we show a compa ison o he dep h be ween ou me hod,
Less-Than, and he Diagonal me hod. In o de o do so wo di e -
en anspile s a e used, he s a e ec o anspile o Qiski , which
assumes all he qubi s a e connec ed wi h each o he , and he ake_
washing on_ 2,7a ake p o ide which has he same p ope ies, namely
he opology, as he eal de ice Washing on om IBM. F om now on we
will deno e his p o ide jus Fake Washing on.
In Fig. 7, we show he compa ison using he s a e ec o as a
anspile . The igu e depic s he mean plus and minus he s anda d
de ia ion (s d) o he dep h o bo h me hods, Less-Than in blue ci cle
and Diagonal in iole iangle. I can be obse ed ha om 12 qubi s
7h ps://qiski .o g/documen a ion/apidoc/p o ide s_ ake_p o ide .h ml.
The Jou nal o Sys ems & So wa e 219 (2025) 112203
6
J. Sanchez-Ri e o e al.
Fig. 3. Simula ion o less- han 42 ampli ica ion wi h 6 qubi s and 20,000 sho s.
Fig. 4. Simula ion o less- han 13 ampli ica ion wi h 6 qubi s and 20,000 sho s.
Fig. 5. Simula ion o less- han 4 ampli ica ion wi h 4 qubi s and 20,000 sho s.
Fig. 6. Real expe imen o less- han 4 ampli ica ion wi h 4 qubi s and 20,000 sho s.
onwa ds he di e ence be ween he me hods is mo e han 100%. Bo h
he mean and s d a e compu ed using all he numbe s o each numbe
o qubi s. Fo ins ance, wi h 𝑛= 6 qubi s he dep h is he mean o
he implemen a ions o he o acles Less-Than 1,2,…, and 26− 1 = 63.
Hence, he mean and s d o each numbe o qubi s 𝑛is made wi h 2𝑛−1
implemen a ions.
Gi en he opology o he s a e ec o anspile , in which e e y
pai o qubi s is connec ed, o some alues o 𝑚ou me hod does
The Jou nal o Sys ems & So wa e 219 (2025) 112203
7
J. Sanchez-Ri e o e al.
Fig. 7. Dep h compa ison be ween less- han and diagonal me hod using s a e ec o as a anspile . The 𝑦-axis ep esen s he dep h while he 𝑥-axis ep esen s he numbe o qubi s.
(Fo in e p e a ion o he e e ences o colou in his igu e legend, he eade is e e ed o he web e sion o his a icle.)
Fig. 8. Dep h compa ison be ween less- han and diagonal me hod using ake_washing on_ 2 as he anspile . The 𝑦-axis ep esen s he dep h while he 𝑥-axis ep esen s he numbe
o qubi s.
no ou pe o m Diagonal. S ill, on a e age, he dep h o he ci cui
gene a ed by ou me hod is smalle and g ows slowe han he one
gene a ed by Diagonal. The comple e da ase may be ound in he
eposi o y in Code and Da a.
Fig. 8 shows he compa ison using Fake Washing on as a anspile .
The main di e ence we obse e is ha he dep h is sligh ly la ge han
using he s a e ec o anspile . This is because o he opology o he
de ice, so mul i-con olled ga es need mo e ga es o be ca ied ou .
The di e ence be ween he me hods is no able om 12 qubi s onwa ds,
as in he p e ious case. Mo eo e , and con a y o he p e ious case,
om 12 qubi s (included) onwa ds, ou me hod ou pe o ms Diagonal
in e ms o dep h o e e y alue o 𝑚.
6.2. Coun ga es compa ison wi h diagonal me hod
We conduc he same compa ison as in he p e ious sec ion howe e
in his occasion wi h he numbe o ga es. As wo anspile s a e used,
wo compa isons a e shown. The ga es used when using he s a e ec o
anspile can be seen in Table 1 and depic ed in Fig. 9. I can be no iced
ha we ha e educed he ga es o only 𝐶𝑋, wo-qubi ga es, and one-
qubi ga es, deno ed by 𝑈. Fu he mo e, he anspiling ime in seconds
has also been added o he compa ison, which can be no iced in Fig. 10.
We can obse e ha , e en hough Diagonal ou pe o ms Less-Than in
amoun o ime and ga es o low numbe o qubi s, om 8 qubi s
onwa ds, he anspiling ime is smalle using Less-Than me hod. 𝐶𝑋
a e ewe om 10 qubi s onwa ds, wi h a linea g ow h agains he
exponen ial g ow h o he Diagonal me hod. Wi h espec o he one-
qubi ga es, we see an imp o emen om 12 qubi s onwa ds, apa
om he linea g ow h o he Less-Than me hod compa ed wi h he
exponen ial one o Diagonal me hod.
In Table 2 he same compa ison is shown aking he Fake Washing-
on as he anspile . As in he p e ious case, he compa ison can be
also obse ed as a g aph in Fig. 11. The esul s displayed a e simila
o he ones in he p e ious compa ison, howe e all he igu es a e
highe gi en he opology o he de ice. Time o e pe o mance begins
a 9 qubi s, as he 𝐶𝑋 ga e coun . Rega ding 𝑈ga es, i ep esen s he
sum o ga es 𝑅𝑍,𝑆and 𝑋, he one-qubi ga es he Fake Washing on
anspile uses. This numbe is lowe in he Less-Than me hod om 11
qubi s onwa ds. The disagg ega ed igu es can be ound in Table 3, also
ep esen ed in Fig. 12.
While ou me hod is be e in e ms o ga e coun and dep h, i
should be no ed ha Diagonal me hod is designed o implemen any
o acle gi en he s a es o be phase-ma ked and ou me hod is designed
only o he Less-Than ope a ion.
The Jou nal o Sys ems & So wa e 219 (2025) 112203
8
J. Sanchez-Ri e o e al.
Fig. 9. Compa ison o ga e coun be ween ou me hod less- han, diagonal and phase ole an using s a e ec o as anspile .
Fig. 10. Compa ison o anspiling ime be ween ou me hod less- han and diagonal using bo h anspile s.
6.3. Coun ga es compa ison wi h Phase Tole an (PT) syn hesis
The Phase Tole an syn hesis is p esen ed in Seidel e al. (2023) as
an au oma ic me hod o gene a ing o acles o a bi a y da a s uc-
u es. The au ho s ocus on ga e coun by ype used in he quan um
ci cui ins ead o he ci cui dep h. The ga e coun me ic is, as well
as he ci cui dep h, a measu e o he ci cui ’s complexi y. I p o ides
a deep unde s anding o he implemen a ion, as well as gi ing a clea
insigh o he gene a ed ci cui . The same me ic is used o conduc he
complexi y analysis o he Less-Than me hod and he compa isons a e
shown in Table 4. This compa ison is also depic ed in Fig. 9. Wi h e-
spec o he anspile , hey use he QASM Simula o om Qiski , which
assumes all qubi s a e connec ed o each o he . The e o e, we conduc
he compa ison wi h ou esul s using he s a e ec o anspile . I can
be seen ha he PT me hod equi es double he amoun o qubi s o
he same da a size.8Mo eo e , he coun o 𝐶𝑋 and 𝑈ga es is la ge
8This is he o al numbe o quan um s a es which can be encoded in he
non-ancilla qubi s. In ou case, he non-ancilla qubi s a e all he qubi s in he
ci cui .
The Jou nal o Sys ems & So wa e 219 (2025) 112203
9
