Quan um Machine In elligence (2022) 4:12
h ps://doi.o g/10.1007/s42484-022-00065-1
RESEARCH ARTICLE
Implemen able hyb id quan um an colony op imiza ion algo i hm
M. Ga cia de Andoin1,2,3 ·J. Echanobe3,4
Recei ed: 2 July 2021 / Accep ed: 10 Feb ua y 2022
©The Au ho (s) 2022
Abs ac
We p opose a new hyb id quan um algo i hm based on he classical An Colony Op imiza ion algo i hm o p oduce
app oxima e solu ions o NP-ha d p oblems, in pa icula op imiza ion p oblems. Fi s , we discuss some p e iously
p oposed Quan um An Colony Op imiza ion algo i hms, and based on hem, we de elop an imp o ed algo i hm ha can
be uly implemen ed on nea - e m quan um compu e s. Ou i e a i e algo i hm codi ies only he in o ma ion abou he
phe omones and he explo a ion pa ame e in he quan um s a e, while sub oga ing he calcula ion o he nume ical esul
o a classical compu e . A new guided explo a ion s a egy is used in o de o ake ad an age o he quan um compu a ion
powe and gene a e new possible solu ions as a supe posi ion o s a es. This app oach is specially use ul o sol e cons ained
op imiza ion p oblems, whe e we can implemen e icien ly he explo a ion o new pa hs wi hou ha ing o check he
co espondence o a pa h o a solu ion be o e he measu emen o he s a e. As an example o a NP-ha d p oblem, we choose
o sol e he Quad a ic Assignmen P oblem. The benchma ks made by simula ing he noiseless quan um ci cui and he
expe imen s made on IBM quan um compu e s show he alidi y o he algo i hm.
Keywo ds Quan um compu ing ·Hyb id quan um algo i hm ·Quan um an colony op imiza ion ·An colony
op imiza ion ·Quad a ic assignmen p oblem
1 In oduc ion
An Colony Op imiza ion (ACO) was p oposed by A. Col-
o ni and M. Do igo in he 1990s o sol ing combina ional
op imiza ion p oblems (Colo ni e al. 1991). This bio-inspi ed
algo i hm mimics he o aging s a egy, in which each indi-
idual ies o ind he sho es pa h o he ood based on he
in o ma ion o i s p edecesso s. This indi ec communica-
ion is made by placing phe omones along he pa h an indi-
idual a e ses. The phe omones will be s onge he be e
is he ood and he sho e he pa h o i . This way, he an s
M. Ga cia de Andoin
[email p o ec ed]
1Depa men o Physical Chemis y, Uni e si y o he Basque
Coun y UPV/EHU, Leioa, 48940 Spain
2TECNALIA, Basque Resea ch and Technology Alliance
(BRTA), De io, Bizkaia, 48160 Spain
3EHU Quan um Cen e , Uni e si y o he Basque Coun y
UPV/EHU, Leioa, 48940 Spain
4Depa men o Elec ici y and Elec onics, Uni e si y
o he Basque Coun y UPV/EHU, Leioa, 48940 Spain
will op imize he dis ance be ween he ood and he colony.
Using his me aheu is ic, esea che s ha e sol ed ins ances
o NP-ha d combina ional p oblems, many o hem o i-
en ed o g aphs, such as T a elling Salesman P oblem (TSP)
(Colo ni e al. 1991; Do igo and Gamba della 1997), Vehi-
cle Rou ing P oblem (VRP) (Bullnheime e al. 1999),
Quad a ic Assignmen P oblem (QAP) (Vi o io e al. 1995)
o unc ion op imiza ion (Toksa i 2006).
Quan um compu ing and Quan um algo i hms ha e been
apidly g owing since he i s e y success ul esul s we e
published in he ea ly 1990s. G o e ’s sea ching algo i hm
(G o e 1996) o Sho ’s ac o ing algo i hm (Sho 1997)
p o ed o ou pe o m any o he classical algo i hm in ega d
o ime complexi y. In 1996, Na ayanan and Moo e (1996)
p oposed gene ic algo i hms, in which mechanisms used in
quan um compu ing we e applied o imp o e e olu iona y
algo i hms. A ew yea s la e , Han and Kim (2000) p oposed
Quan um E olu iona y Algo i hms (QEA), which speedups
he classical e olu iona y algo i hms based on he same
p inciples.
BasedonQEAandACO,Wange al.(2007) p oposed
a quan um-inspi ed an colony op imiza ion algo i hm
(QIACO). The main no el y o QIACO is he phe omone
ep esen a ion on he quan um s a e, using a o a ion ga e
o di ec he measu emen o he sys em o he op imal
/ Published online: 17 June 2022
Quan um Machine In elligence (2022) 4:12
solu ion. Simila ly, P. Li and H. Wang p oposed a QIACO
algo i hm based on he Bloch sphe ical sea ch (BQIACO)
(Li and Wang 2012). This algo i hm akes ad an age o
he Bloch sphe e ep esen a ion, applying o a ion ga es in
o de o mo e he s a e o he op imal solu ion. Mimicking
he andom sea ch pa e n in ACO, bo h algo i hms
implemen ed o ced explo a ion s a egies, using CNOT
ga es in QIACO and Hadama d ga es in BQIACO o shi
a ound he qubi s one by one.
Howe e , nei he QIACO o BQIACO can be imple-
men ed on a eal quan um compu e . Due o he limi a ions
o he in o ma ion quan um mechanics allows us o e ie e
om a quan um s a e, he phe omone upda e s a egies ha
bo h p opose canno be used. In his a icle, we p opose a
new quan um e sion o ACO ha is implemen able on a
quan um compu e .
In Sec ion 2we in oduce he o iginal QIACO algo i hm
and a ecen ly p oposed QACO algo i hm. Sec ion 3
de elops he new algo i hm and a discussion on he
pa ame e op imiza ion. Sec ion 4p esen s he esul s
ob ained sol ing QAP bo h by simula ing he algo i hm and
implemen ing i on he cu en ly a ailable IBM quan um
compu e s (IBM 2020). Finally, Sec ion 5discusses
conclusions, possible imp o emen s and u u e wo k.
The e is some con usion in he names, as he o iginal
au ho s o en label hei algo i hms as “quan um” despi e
being ully classical. Ins ead, we e e o hese algo i hms
as “quan um inspi ed”. To label ou algo i hm we ollowed
he c i e ion used by o he au ho s (O’D iscoll e al. 2019;
Yuan e al. 2021). This is be e sui ed o he ac ha he
hyb id quan um algo i hms ake ad an age o he quan um
mechanical p ope ies o he s a es, while sub oga ing some
calcula ions o classical algo i hms.
2 P e ious wo ks
The algo i hm p esen ed in his a icle is an imp o emen
based on he wo k o Wang e al. (2007). The e, hey p oposed
a quan um app oach o he classic An Colony Op imiza-
ion algo i hm, in which each s a e o he compu a ional
basis ep esen s a possible solu ion o he p oblem.
The in o ma ion abou he phe omones is hen coded in
he quan um s a e o he sys em. To ma ch he qubi and
he phe omone ep esen a ion, hey used he Hype -Cube
F amewo k (HCF) p oposed by Blum and Do igo (2004).
As he HCF limi s he phe omone alues o he ange [0,1],
he p obabili y o measu ing he exci ed s a e o a qubi can
be se o be he same as he p obabili y o an an o choosing
said edge.
To achie e ha , hey used a o a ion ga e a ound he Y-
axis on he Bloch sphe e. This way, e e y qubi is assigned
an angle, his being π/4 assuming he ini ial s a e o he
qubi s is |0. F om his poin on, we suppose ha all qubi s
s a always a he s a e |0. Each ime a solu ion is ob ained,
i is compa ed o he bes solu ion so a . The o a ion angle
o he nex gene a ion is hen upda ed using a lookup able.
As in ACO, he algo i hm mus allow andom explo a ion
o new solu ions. This is achie ed by gene a ing a andom
numbe 0 <p<1 o each qubi . I pis g ea e han he
explo a ion pa ame e pe, he ou come o he qubi will be
andom. Else, i will ollow he phe omones as in ACO.
La ely, ACO has been imp o ed and used o sol e
di e en p oblems mo e e icien ly. Fo example, o
au oma ed guided ehicles (Li e al. 2020), o opology-
based link p edic ion (Cao e al. 2018) and o que y
op imiza ion (Mohsin e al. 2021). These implemen a ions
a e based on he pa allel na u e o quan um sys ems. The
abili y o ha ing supe posed quan um s a es ha ep esen
di e en possible solu ions enhances he abili y o a oid
alling in o local minima.
Ne e heless, QIACO is no implemen able in a quan um
compu e . On one hand, in o de o use he lookup able,
one has o know exac ly he s a e o each qubi . As he e is
no way o achie e his ou o a simula ion o epea ing he
expe imen un il ob aining he s a is ics o he dis ibu ion
o s a es, he e sion o QACO we p opose in his a icle
uses a sligh ly di e en app oach o he phe omone upda e
s a egy. On he o he hand, he explo a ion s a egy o
QIACO canno be implemen ed wi h quan um ga es. The
s a egy hey p oposed akes a measu emen o he qubi s,
consequen ly des oying he quan um s a e.
Recen ly, a quan um algo i hm o ACO has been
p oposed, he MNDAS algo i hm (Ghosh e al. 2020). This
algo i hm uses xqubi s o code all possible pa hs, d o
he phe omones and 3 qubi s as egis e s. The qubi s a e
ini ialized in a supe posi ion s a e using Hadama d ga es in
o de o gi e each pa h he same weigh . Then, he algo i hm
akes an i e a i e app oach o he p oblem using an o acle.
I s main unc ion is o selec npossible pa hs as in ACO and
o upda e he phe omone ails acco dingly. Be o e ending
each i e a ion, he o acle pe o ms an ope a ion o e apo a e
he phe omones on he selec ed ails. The con e gence
o he algo i hm is assu ed by p e en ing e apo a ion o
occu on he bes pa h ound so a . A e a ixed numbe
o i e a ions, a quan um ampli ude ampli ica ion p ocedu e
is made in o de ampli y he p obabili y densi y o he
solu ion, and hen measu ed.
One p oblem o MNDAS is i s lack o implemen abili y
in nea - e m quan um compu ing sys ems. The numbe o
qubi s and he couplings i employs is a om achie able.
The implemen a ion o he algo i hm on any cu en ly
a ailable quan um compu e would need an una o dable
amoun o SWAP ga es, in oducing a la ge amoun o
noise in he sys em. Ano he p oblem wi h his algo i hm
is he in oduc ion o a highly demanding o acle. The
12 Page 2 o 14
Quan um Machine In elligence (2022) 4:12
amoun o calcula ions i needs o pe o m in each
i e a ion makes i di icul o a quan um compu e o
main ain cohe ence a e all he ga es ha a e applied.
In con as , ou algo i hm ackles his p oblem by using
an i e a i e quan um algo i hm ha does no ely on
pe ec ly e o co ec ed qubi s. The amoun o ga es ou
algo i hm pe o ms in each i e a ion makes is sui able o be
implemen ed in cu en quan um compu e s.
Fu he mo e, he ini ializa ion o MNDAS equi es o
compu e he weigh s o all possible pa hs. This comple ely
de ea s he pu pose o using a me aheu is ic algo i hm.
Once he pa hs weigh s a e ob ained, he op imal solu ion
can be ob ained using a egula sea ch algo i hm O(n),o
a G o e algo i hm O(n1/2). In con as , MNDAS has a
complexi y o O(Kn +n1/2), wi h Ka cons an , so i alls
behind al eady exis ing solu ions.
3 P oposed implemen able QACO algo i hm
The main eason why we de eloped his algo i hm is o
p o ide a p ac ical applica ion o he well-known ACO
algo i hm on a quan um compu e (Fig. 1). Al hough no eal
implemen a ion is men ioned in his sec ion, we designed i
so ha he s eps and he ga es used a e easily implemen able
on he a ailable compu e s o he da e his is w i en.
Following an almos iden ical schema used in ACO,
his algo i hm can be di ided in o 4 main s eps:
phe omone applica ion, explo a ion o new solu ions, pos -
measu emen checks and phe omone upda e.
The qubi s a e di ided in o wo g oups: an and
explo a ion qubi s. The an qubi s a e he ones in which
he in o ma ion abou phe omone ail is in oduced, while
he explo a ion qubi s a e de e mined by he explo a ion
pa ame e .
3.1 Algo i hm s ep de elopmen
3.1.1 Phe omone applica ion
The an qubi s a e he a ge s o he con olled ga es o he
explo a ion p ocess. The codi ica ion o he solu ions mus
be gi en as a map om he solu ion space S o he Hilbe
space H. The numbe o qubi s used (n) mus be su icien
so ha he map :S→Hcan be a bimo phism, his is
−1( (s)) =s, ∀s∈S.
Con a y o he usual codi ica ion o ACO, in QACO we
encode he phe omones no in o he edges o a g aph, bu in
i s nodes. Then, he p obabili y o isi ing each node is gi en
by he phe omones deposi ed in o hem. This in o ma ion
is in oduced on he quan um s a e ia a o a ion ga e. Bu ,
while he p e ious algo i hm uses a o a ion on he eal
plane, we apply a Y- o a ion (RY) ga e on each qubi . To
con ol he possible ou comes, we limi all he o a ion
angles o he an qubi s o 0 <θ
i<π. This way, he s a e
o each an qubi a e we apply he o a ion ga e is
|i=Ry(θi)|0=sin (θi/2)|0+cos (θi/2)|1.(1)
We can ex end his o he ull quan um s a e o he an
qubi s, jus by aking he enso p oduc o each qubi . The
esul is a supe posi ion o all he s a es o he Hilbe space
canonical basis
|an =|1⊗···⊗|n=
2n
k=0
αk|k,(2)
whe e |kis he s a e ep esen ed by he bina y expansion
o kon nbi s and αkis he ampli ude o he co esponding
s a e.
On he i s i e a ion, each possible s a e has o ha e
he same p obabili y o be measu ed, his is |αk|=1/2n.
Fig. 1 G aphic ep esen a ion o he pa hs in ACO and QACO in a
2 node g aph o a pa h inding p oblem. In ACO, he an a i es a
he end by choosing a non isi ed node a each s ep. In his example,
he maximum s eps o he classical an a e 3, wi h 5 di e en pa hs.
Howe e , 2 o hese pa hs yield he same esul , since he codi ica ion
only depends on he isi ed nodes, no in he o de hey a e isi ed. In
QACO, he an li es in a s a e ha is a supe posi ion o each possible
pa h. Using 2 qubi s, we can assign each one o a node, whe e |1iand
|0i ep esen s he an isi ing and no he node i espec i ely. In he
momen he an is measu ed, one o he pa hs is selec ed
Page 3 o 14 12
Quan um Machine In elligence (2022) 4:12
The e o e, he s a ing alues o he o a ion angles mus be
θ0
i=π/2.
3.1.2 Explo a ion o new solu ions
Explo a ion pa ame e The p obabili y o explo a ion o
new solu ions can be de ined by one pa ame e , 0 ≤βe≤1.
In his case, we use he angle o a RY ga e o code his
pa ame e as he p obabili y o measu e he exci ed s a e
o ha qubi . On an ideal quan um compu e in which he
g aph o connec i i y be ween qubi s is ully connec ed,
we would only need one qubi . Bu mos o he quan um
compu e s cu en ly a ailable ha e a mos 4 pai ings o
each qubi , as his is he case o he IBM Yo k own-ibmqx2.
In o de o a oid he use o SWAP ga es o implemen he
con olled ga es, his qubi can be “duplica ed” simply by
applying he same RY ga e o di e en qubi s.
These qubi s con ol he ga es o he explo a ion p ocess.
As he p obabili y o apply a ga e depends on he p obabili y
o measu e he exci ed s a e and he s a e o a qubi mus be
no malized, he explo a ion qubi s a e can be w i en as
|e=1−βe|0±βe|1⇒|1|e|2=βe.(3)
We can gene a e his s a e using an RY ga e wi h an angle
o θe=2 a csin(√βe).
To co ec ly implemen he explo a ion s a egy, we mus
ese he explo a ion qubi a e each con olled ga e is
applied. This way, we a oid he en anglemen be ween he
an and he explo a ion qubi s. I we do no ese he qubi ,
he sys em would only ha e wo possible ou comes, one
wi h all con olled ga es applied and he o he wi hou . We
u he explain his e ec on Appendix 2.
An explo a ion s a egy In an colony algo i hms, he
mechanism which allows o ha e new solu ions is based
on andom explo a ion. The classical s a egy decides o
andomly explo e based on an explo a ion pa ame e , ha
gi es he equency a which his andom explo a ion
happens. This decision is made a e e y s ep on he pa h,
a oiding back acking on al eady isi ed edges.
In QACO, we can in oduce his mechanism explici ly
using con olled ga es. When he p oblem is uncons ained,
his can be implemen ed using CNOT ga es. This allows he
sys em o a i e o e e y possible solu ion om any node
in he g aph. Using he explo a ion qubi s as he con ol
qubi , we can a ge each o he an qubi s. This way, he
p obabili y o a qubi o change i s s a e is βe. Applying
his o e e y o he qubi , he p obabili y o lipping kqubi s
is P(k) =βk
e(1−βe)n−k. Thus, in each i e a ion he e is a
non-ze o p obabili y o he algo i hm o yield an a bi a y
solu ion. Howe e , he p obabili y o explo ing k imes
dec eases wi h k; hus, we a o he local explo a ion o
solu ions.
This s a egy is use ul when he p oblem is uncon-
s ained, ha is, when all he possible ou comes a e a alid
solu ion o he p oblem. Bu when he e a e es ic ions,
his s a egy may esul in measu ing inco ec solu ions.
To imp o e he e iciency o he explo a ion in hese cases,
we p opose using ga es ha ac on he s a e aking i om
an allowed solu ion o ano he . This way, i we conside an
ideal quan um compu e , we keep he p obabili y o mea-
su ing an allowed solu ion cons an . Equi alen ly, he leak
o p obabili y o a non allowed s a e is ideally 0. Then, one
would ha e o design a s a egy o he speci ic cons ain
se o he p oblem o sol e.
In o de o illus a e his concep , le us suppose ha he
cons ain we wan o add ess allows solu ions wi h m1’s.
Fo his pa icula p oblem, lipping 1 qubi would u n a
alid solu ion o a non alid one. Howe e , lipping 2 qubi s
a he same ime p ese e he numbe o ones o he s a e.
To apply his change o a s a e, we can apply a F edkin
ga e. The F edkin ga e can be unde s ood as a con olled
SWAP ga e be ween 2 a ge qubi s. This ga e main ains he
p obabili y o measu ing a ce ain numbe o exci ed qubi s.
The numbe o ga es needed o explo e he whole space is
n(n −1)/2−1, as we need one ga e o each di e en pai
o qubi s and applying all possible swap ga es would yield
he same s a e as he ini ial.
Being he F edkin ga e wi h he con ol qubi cand wo
a ge s 1and 2(CSWAP(c, 1,
2)), he commu a ion ule
be ween 2 F edkin ga es wi h he same con ol qubi is
[CSWAP(c, m, n), CSWAP(c,x,y)]⎧
⎪
⎨
⎪
⎩
=0i {m, n}∩{x,y}=∅,
=0i {m, n}={x,y},
= 0 o he wise.
(4)
As he F edkin ga es do no commu e, he o de in which
he ga es a e applied de e mines he s a es he sys em can
jump o. As he e a e mul iple ways o explo e, he o de in
which he ga es a e applied mus be andomized. This way,
e en hough he explo a ion is biased on each gene a ion,
he e ec is a e aged ou h ough all he i e a ions. In
addi ion o his, he i e a i e na u e o he explo a ion
p ocess could also a e age ou he possible e o s gene a ed
while applying any o he ga e h oughou he p ocess.
This explo a ion s a egy gene a es an en angled s a e
ha e icien ly encodes he pa hs o he an s as a
supe posi ion. The en anglemen is made so ha in an ideal
quan um compu e , he measu emen o all he an qubi s
co esponds o a pa h.
3.1.3 Pos -measu emen checks: solu ion gene a o
In he cases when he p oblem is cons ained o ce ain
solu ions, he measu emen o he an qubi s can u n ou o
be an in alid solu ion. This in alid esul comes om he
12 Page 4 o 14
Quan um Machine In elligence (2022) 4:12
in o ma ion abou he phe omone s a e o he e ec o noise.
Ins ead o disca ding he solu ion, we p opose o gene a e a
new esul .
The new solu ion mus be as close o he p e ious one
as possible. Following his idea, we choose o use he
Hamming dis ance be ween he solu ions o dis ibu e he
p obabili ies, so ha he close ones a e a o ed. We se he
p obabili y o choosing a solu ion as in e sely p opo ional
o he Hamming dis ance om he o iginal measu emen , pi
∝1/di.Wede inepi·di=pj·dj∀i, j. Wo king wi h bo h
equa ions, and he condi ion ha he sum o he p obabili ies
is 1, one a i es o
p−1
i=di
j
1
dj
.(5)
The algo i hm o choose a solu ion is p esen ed in
Algo i hm 1.
3.1.4 Phe omone upda e
A he end o each gene a ion a solu ion is p oduced. I he
s opping c i e ia a e no me , we upda e he phe omones
using a new lookup able (Table 1). This able akes in o
accoun he bes solu ion ob ained so a ( (b)
)and he
solu ion o he cu en gene a ion ( (x)
). The idea benea h
hese alues is o implemen he same mechanism used
in ACO. We ein o ce he bes solu ions by upda ing he
o a ion angle so ha in he nex gene a ion he p obabili y
o measu e i inc eases. Bu when a be e solu ion is ound,
he o a ion angle upda e is highe . This way, we ein o ce
posi i ely he explo a ion o new bes solu ions.
To upda e he angle alue, he angle o he nex i e a ion
o each an qubi (θ
i) is calcula ed by summing he alue
ob ained om he lookup able (Table 1) o he alueused
in he cu en i e a ion (θi), θ
i=θi+θi. The elec ion o
alues on he able is discussed on Sec ion 4.2.
In his algo i hm we o ce he alues o he o a ion angle
o he in e al [0, π]. I an angle is ou o his in e al,
he nex upda e will y o co ec he angle back. When
he algo i hm is nea con e gence, he o a ion angle will
Table 1 Lookup able o he phe omone o a ion angle upda e θi.
xiis he s a e o he qubi ion he cu en gene a ion, and bi he s a e
o he qubi ion he bes solu ion so a . (x)and (b)a e he alues
o he i ness unc ion o he cu en gene a ion and he bes solu ion
so a espec i ely. Values wi h * a e mul iplied by −1i cos(θi/2)<0
xibi (x)be e han (b)? θi
00T ue −0.01π*
0 0 False 0.04π
01T ue −0.05π*
0 1 False 0.07π
10T ue 0.05π*
10False −0.07π
11T ue 0.01π*
11False −0.04π
oscilla e a ound 0 o π, and he s a e o he qubi a e
applying he RY ga e will oscilla e as well a ound |0o |1.
No e ha we ha e de ined he angle upda e alues in
e ms o a single an . In ACO he e is a choice o s a egies
o upda ing he phe omone ails. In his ega d, QACO
could bene i om explo ing o he upda e s a egies, in
which he phe omone o a ion angles could depend on
he i ness alue o in mo e han one an , among o he
possibili ies. Howe e , as i will be shown in Sec ion 3.4 one
an su ices o he algo i hm no o con e ge o subop imal
solu ions. This s a emen ag ees wi h he esul s ound o
ano he hyb id quan um algo i hm in Sweke e al. (2020).
3.2 S opping c i e ia
In ACO, we ha e o de ine a e mina ion condi ion o he
algo i hm o exi he i e a ion loop. When we ha e no p io
in o ma ion abou a lowe bound o he op imal solu ion,
we can de ine 2 di e en condi ions (p. 105 Do igo and
S ¨u zle 2004). One can be o se a ixed maximum ime
o i e a ions he algo i hm can un. Using his c i e ion,
making an in ini e numbe o i e a ions will yield he co ec
esul o he p oblem, as e e y possible pa h is allowed o
be ob ained in e e y i e a ion. This way, he p obabili y
o ge ing he esul a e in ini e i e a ions will be 100%.
Al hough alid, his e mina ion c i e ion is no use ul, as i
is di icul o se he co ec numbe o i e a ions a p io i.
Besides, he numbe o i e a ions could be se highe han
necessa y, lowe ing he e iciency o he algo i hm.
The o he e mina ion condi ion can be se o de ine
a con e gence o s agna ion condi ion. This can be
unde s ood as ha ing a si ua ion in which no be e esul s
a e ound on consecu i e i e a ions. To ake his in o
accoun , we in oduced a new pa ame e con e Condi ion.
A he end o each i e a ion, he algo i hm checks i he
esul is be e han he bes solu ion so a . I his is ue, he
Page 5 o 14 12
Quan um Machine In elligence (2022) 4:12
Fig. 2 Example o he diag am o he ci cui ha implemen s he j h i e a ion o QACO o a cons ained p oblem size n=3. The phe omone
upda e is made once he solu ion o he i e a ion is selec ed. The solu ion checking and condi ional solu ion gene a ion is sho en as “GenS”
condi ion coun e is ese o 0. Else, he coun e inc eases
in 1. When his coun e is equal o con e Condi ion he
algo i hm s ops and e u ns he bes solu ion so a .
3.3 Algo i hm
The implemen a ion o he algo i hm is e y simila o he
classical ACO. Ha ing discussed he s eps in he p e ious
sec ions, he algo i hm is p esen ed in Algo i hm 2. In Fig. 2
we expand an example o he diag am o he quan um
ci cui ha implemen s one i e a ion o he algo i hm.
Figu e 3shows a lux diag am showing he wo k low o he
algo i hm.
The quan um s a e o he an qubi s is measu ed each
i e a ion. A e he pos -measu emen checks and he
phe omone upda e, a new quan um s a e is gene a ed a he
s a o a new i e a ion. Hence, he i e a i e na u e o he
p oposed algo i hm.
3.4 Con e gence o QACO
I is easy o see ha he algo i hm we p opose he e will
a i e a he op imal solu ion gi en enough i e a ions,
since he e is a non-ze o p obabili y o measu ing e e y
possible solu ion a each i e a ion. Fo analyzing he
con e gence beha io o QACO, le ’s analyze i in a wo s -
case scena io whe e he algo i hm is apped in a local
minimum.
I QACO is apped in a subop imum poin , he
phe omones will ini ially guide he an s owa ds a subop-
imal con igu a ion s. This means ha he s a e o he an
qubi s will be close o he co esponding s a e o he com-
pu a ional basis, |an s=Ryθk,j ⊗n|0⊗n≈|s.In
his case, he algo i hm comple ely depends on he explo-
a ion s a egy o sea ch o a be e solu ion. As we ha e
shown in Sec ion 3.1.2, he algo i hm a o s he local sea ch
o new solu ions. Le ’s again ake he wo s scena io in
which he an has only sea ched once. Mos likely, he
new solu ion will ha e a wo se i ness alue han he local
minimum. Howe e , he ac ha we ha e ob ained a di -
e en solu ion in oduces a a ia ion in he phe omones.
This way, he p obabili y o sea ching new solu ions has
inc eased compa ed o he p e ious i e a ion. We can check
his by calcula ing he p ojec ion o he s a e a e apply-
ing he phe omones o he s a e encoding he subop imal
con igu a ion, and no icing ha he s a e o he nex gen-
e a ion has dec eased p obabili y o being in he |ss a e,
|s|an s(k)|2>|s|an s(k +1)|2.
The likelihood o exi ing a local minimum and inding a
be e solu ion is a leas βq
e(1−βe)p−q, wi h p he numbe
o di e en explo a ion ope a ions and q he numbe
o explo a ion ope a ions ha sepa a es he local and
global minimum solu ions. Fu he mo e, due o he small
p obabili y o he an in a gi en explo a ion no o explo e
o (1−βe)p, ou explo a ion s a egy does no equi e mo e
han one an o s a escaping he minimum poin . Gi en
ha each ime he algo i hm inds a di e en solu ion he
p obabili y o sea ching new ones inc eases, i is p o en ha
QACO will ne e con e ge o a local minimum.
12 Page 6 o 14
Quan um Machine In elligence (2022) 4:12
Fig. 3 Flux diag am o he p oposed QACO algo i hm. The s eps
wi hin he box a e pe o med in a quan um compu e , and he dashed
lines indica e ha he in o ma ion be ween s eps is in a quan um s a e
4 Implemen a ion o QACO
An Colony algo i hms a e usually cons uc ed o ob ain an
app oxima e solu ion o NP-comple e p oblems (Kleinbe g
and Ta dos 2006, pp. 463–465). E e y NP-p oblem is
equi alen o e e y o he p oblem in he se up o a
polynomial ime ans o ma ion (Knu h 1974). This means
ha we can choose o sol e one se o hem, in his case
we ha e chosen o sol e he Quad a ic Assignmen P oblem
(QAP) (Loiola e al. 2007).
In o de o co ec ly analyze he esul s we ha e ob ained,
we ha e o keep in mind he “No F ee Lunch Theo em”
(Ho and Pepyne 2002). This heo em s a es ha a global
op imiza ion s a egy does no exis o e he comple e se o
p oblems. We can only ob ain a be e e iciency i we limi
ou sel es o sol e a pa icula kind o p oblem.
4.1 Quad a ic Assignmen P oblem (QAP)
The QAP consis on sea ching he inpu X ha maximizes
he unc ion gi en by
(X,M)=X MX=
n
i=1
i
j=1
XiMij Xj,Mij ∈R,(6)
whe e Xis a column ec o wi h alues 1 o 0 and Mis
he p oblem ma ix. Fo simplici y, and wi hou losing any
gene ali y, we can choose M o be a iangula ma ix. Fo
he p oblem no o be i ial, Mhas o ha e bo h posi i e
and nega i e elemen s. The solu ion may be allowed o
ha e any numbe o 1’s in i s solu ion o may ha e some
cons ain s. We will be e e ing o he i s case as UQAP
(Uncons ained QAP) and he la es CQAP (Cons ained
QAP).
Fo UQAP, he solu ion se has size 2n,whe enis he
size o he ma ix. Any known exac algo i hm will ha e
an exponen ial complexi y O(2n). This apid g ow h in
complexi y limi s ou capaci y o simula e bigge p oblems,
in which ou algo i hm would come in use ul. The e is also
a limi in he numbe o qubi s we can simula e o o which
we ha e access o.
4.2 Pa ame e op imiza ion
Be o e unning he algo i hm, we ha e o selec he
inpu pa ame e s: con e Condi ion,maxI e ,and he
phe omone o a ion angles. Fo his, we ha e decided o
sea ch o he se o pa ame e s ha e u ns a good quali y
o solu ions o QAP p oblems gene a ed wi h uni o mly
andom numbe s. In pa icula , we ha e aimed o minimize
he numbe o i e a ions be o e s opping needed o ob ain an
op imal solu ion. On op o his, we ha e added an addi ional
cons ain o he inpu pa ame e s o be conside ed. The
c i e ion we used o deciding i he quali y is accep able
o no is o ha e a leas 98.5% o co ec esul s a e
unning he algo i hm a numbe o imes (100 uns pe
ins ance) o di e en p oblem ins ances (100 ins ances).
I he pa ame e s ob ained yield esul s wi h lowe success
a io, hen hey a e disca ded. The p oblems employed
a e gene a ed as andom iangula ma ices, so ha he
diagonal elemen s ha e he same weigh as he elemen s
ou side he diagonal on he solu ion. To ully es QACO, we
ha e sol ed bo h he uncons ained e sion o QAP (UQAP)
and he cons ained e sion (CQAP).
Page 7 o 14 12
Quan um Machine In elligence (2022) 4:12
Fo he op imiza ion, we ha e used he su oga e op i-
miza ion algo i hm implemen ed in he “Global Op imiza-
ion Toolbox” in Ma lab 2019b. We un he p og am o
e e y dis inc p oblem o ma ices size n=3 on=7. As
he cons ain o ha ing m1’s on he solu ion is equi alen
o ha ing n−min e ms o he size o he solu ion se , we
omi ed he alues o m>n/2+1. We se he maximum
unc ion e alua ion pa ame e o 500. In he ollowing pa a-
g aphs, we discuss he op imiza ion o each pa ame e using
he esul s shown in Table 2.
4.2.1 Phe omone o a ion angle upda e
The esul s ob ained a e no su icien o de e mine
an op imum pa ame e ela ion. The esul s seem o
ollow a andom dis ibu ion, wi h no co ela ion be ween
pa ame e s. As he e is no clea way o se he pa ame e s,
we decided o use he median alues unca ed o he second
decimal (Table 1).
4.2.2 Explo a ion pa ame e
In he o iginal algo i hm (Wang e al. 2007), hey p oposed
o use a a ying explo a ion pa ame e , as i is usual in
o he ACO algo i hms. We ha e ied linea βepa ame e s,
wi h posi i e and nega i e g adien and wi h cons an alues.
The bes esul is ob ained wi h nega i e g adien . Howe e ,
he di e ences be ween he esul s a e so simila , ha hey
migh be caused pu ely by andom luc ua ions. Taking
his in o accoun , we ha e chosen o use he posi i e
g adien βebecause i yielded he mos consis en esul s
and o keeping he same a gumen ha can be made o
classic ACO algo i hm. A i s , he an s explo e he pa hs
andomly. As he numbe o i e a ions inc eases, some
subop imal pa hs a e ound. To disca d he subop imal
esul s, he inc ease o he explo a ion pa ame e o ces
he algo i hm o sea ch o new pa hs. In gene al, he
explo a ion pa ame e is
βe(i) =βe0+1−βe0
maxI e i, (7)
wi h βe0 he explo a ion pa ame e a he i s i e a ion,
maxI e he maximum i e a ion coun , and i he numbe
o he cu en i e a ion. Using his o mula, he pa ame e
is es ic ed o alues 0 ≤βe≤1. The pa ame e s chosen
a e he median o he di e en alues ob ained ounded
up o he second decimal, βe0=0.13 and maxI e =
1.05 ·con e Condi ion.
4.2.3 Con e gence condi ion
Using he same c i e ia as be o e, we ied o op imize he
con e Condi ion pa ame e . Using he same alues o he
Table 2, we see ha he bes i alue o his pa ame e
g ows as an po en ial unc ion o he numbe o possible
solu ions o a p oblem (nComb). Fi ing he esul s (Fig. 4)
o a unc ion dependan o nComb we ob ain
con e Condi ion(nComb)=23.3 ·nComb0.5 −35.1. (8)
Table 2 Values o he pa ame e s in QACO ha op imizes he mean numbe o i e a ions o ge a solu ion which is inco ec a mos 1.5% o he
imes o e 100 uns o each o he 100 andomly gene a ed p oblems
nmCombI e M CC βeI e F 00T 00F 01T 01F
3 1 3 7.00 7 0.964 1.000 0.001 0.090 0.100 0.005
3 3 8 25.87 24 0.070 1.038 0.002 0.063 0.100 0.091
4 1 4 12.48 11 0.211 1.144 0.006 0.037 0.052 0.070
4 2 6 18.61 17 0.001 1.073 0.039 0.076 0.005 0.037
4 4 16 48.56 45 0.123 1.067 0.009 0.036 0.051 0.066
5 1 5 16.70 14 0.241 1.249 0.002 0.032 0.053 0.093
5 2 10 34.89 34 0.793 1.028 0.057 0.064 0.067 0.044
5 5 32 91.97 91 0.087 1.004 0.062 0.030 0.025 0.042
6 1 6 19.83 19 0.133 1.020 0.003 0.029 0.055 0.077
6 2 15 55.00 55 0.998 1.000 0.021 0.020 0.083 0.026
6 3 20 63.45 59 0.001 1.068 0.024 0.050 0.022 0.064
6 6 64 156.80 129 0.082 1.475 0.033 0.046 0.054 0.091
Comb is he numbe o alid solu ions o each p oblem, I e M is he mean numbe o i e a ions un il con e gence, CC is con e Condi ion,βeis
he explo a ion pa ame e , I e F is he ac o so ha he maximum numbe o i e a ions is gi en by maxI e =con e Condi ion ·I e F,and
00T,00F,01Tand 01Fa e he alues o he o a ion angle upda e o de ed as shown in Table 1. Each ow shows he esul s o each p oblem
size n, m
12 Page 8 o 14
Quan um Machine In elligence (2022) 4:12
4.3 Simula ion o QACO
In o de o simula e hese p oblems we ha e used Ma lab
2019b. We ha e simula ed an ideal quan um compu e , in
which he e is no noise and he ga es a e also ideal. We
can use he ma ix ep esen a ion o he ga es and column
ec o s in he compu a ional basis o he s a e. As e e y
ga e o he ci cui is uni a y, we can apply he ga es in
b ake no a ion main aining he no maliza ion condi ion,
Uga e|=|,whe e|is he s a e be o e and |
a e we apply he ga e. As we ha e p e iously men ioned,
as no all he ga es commu e wi h each o he , he o de in
wi h we apply hem a ec s he esul .
The simula ion o he measu emen is implemen ed
by choosing andomly a inal s a e o he compu a ional
basis. Fo his, we use he p obabili y dis ibu ion gi en
by |||. Apa om hese pa icula i ies, he algo i hm
ollows he same s eps as explained in Sec ion 3.
4.4 Expe imen on IBM’s quan um compu e s
Fo implemen ing ou algo i hm on a eal quan um
compu e , we ha e chosen o use IBM’s compu e s. Ou
main goal wi h his implemen a ion is o minimize he
numbe o quan um ga es needed in each i e a ion. As
he decohe ence ime is s ill a cons ain , a smalle se o
ga es would help o main ain he in o ma ion on he sys em
wi h as less pe u ba ions as possible. Fo his, we ha e o
co ec ly analyze he opology o he compu e we will use.
IBM’s quan um compu e s a e based on supe conduc ing
sys ems ha ha e hei qubi s on a 2D la ice, we
ha e a plane g aph ep esen ing he possible coupling
be ween qubi s, being he nodes he qubi s and he
e ex he couplings. Di e en compu e s ha e di e en
con igu a ions, some o which ha e a connec i i y g aph
mo e sui ed o his algo i hm. Fo implemen ing QACO we
ha e chosen he 2 wi h he con igu a ions ha maximizes
he numbe o an qubi s pe explo a ion qubi (Fig. 5):
ibmq 5 yo k own - ibmqx2 and ibmq 16 melbou ne.
Depending on he p oblem size and ype (cons ained
o uncons ained) one has o ind he co ec compu e
and a angemen o qubi s. In he case o uncons ained
p oblems, he aim is o maximize he numbe o an qubi s
while ha ing hem connec ed o a leas one explo a ion
qubi . This way, we can apply CNOT ga es wi hou ha ing
o use SWAP ga es ha in oduce e o s on he sys em.
As we can see in Fig. 5, squa e la ices migh be he
bes con igu a ions o sol e hese p oblems. In he cu en
gene a ion supe conduc ing ci cui s, squa e la ices le us
connec up o 3 an qubi o a single explo a ion qubi . The
downside o his a angemen is ha we lose some o he
en anglemen o he sys em. This could lead o a wo se
con e gence eloci y, as he inal measu emen is allowed
o be a combina ion o di e en pa hs. A solu ion o his
p oblem could be o assign each qubi o a andom posi ion
in he sys em in each i e a ion. Simila ly o he explo a ion
s a egy wi h F edkin ga es, his de ec could be a e aged
o e all i e a ions.
I we ha e cons ained p oblems, we need mo e connec-
i i y be ween qubi s. As we need o apply F edkin ga es,
we need 3 qubi cycles in he connec i i y g aph. This high
connec i i y is a p oblem in la ge-scale supe conduc ing
Fig. 4 Resul s o he pa ame e
op imiza ion. Mean i e a ions
un il con e gence I e m
(ci cle), con e Condi ion
(squa e) and MaxI e ( iangle)
s nComb. The solid cu e is
he i ing cu e o
con e Condi ion om Eq. 8
Page 9 o 14 12
