BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:Europe/Stockholm
X-LIC-LOCATION:Europe/Stockholm
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20210527T134945Z
LOCATION:Digital
DTSTART;TZID=Europe/Stockholm:20200623T141500
DTEND;TZID=Europe/Stockholm:20200623T144000
UID:isc_hpc_ISC High Performance 2020_sess341_pap181@linklings.com
SUMMARY:Embedding Algorithms for Quantum Annealers with Chimera and Pegasu
s Connection Topologies
DESCRIPTION:Research Paper\n\nEmbedding Algorithms for Quantum Annealers w
ith Chimera and Pegasus Connection Topologies\n\nZbinden, Baertschi, Djidj
ev, Eidenbenz\n\nWe propose two new algorithms – Spring-Based MinorMiner (
SPMM) and Clique-Based MinorMiner (CLMM) – which take as input the connect
ivity graph of a Quadratic Unconstrained Binary Optimization (QUBO) proble
m and produce as output an embedding of the input graph on a host graph th
at models the topology of a quantum computing device. As host graphs, we t
ake the Chimera graph and the Pegasus graph, which are the topology graphs
of D-Wave’s 2000 qubit (first introduced in 2017) and 5000 qubit (expecte
d 2020) quantum annealer devices, respectively. We evaluate our algorithms
on a large set of random graph QUBO inputs (Erdős-Rényi Gn,p,
Barabási-Albert and d-regular graphs) on both host topologies again
st other embedding algorithms. For the Pegasus topology, we find that CLMM
outperforms all other algorithms at edge densities larger than 0.08, whil
e SPMM wins at edge densities smaller than 0.08 for Erdős-Rény
i graphs, with very similar transition densities for the other graph class
es. Surprisingly, the standard D-Wave MinorMiner embedding algorithm – whi
le also getting slightly outperformed by SPMM for sparse and very dense gr
aphs on Chimera – does not manage to extend its overall good performance o
n Chimera to Pegasus as it fails to embed even medium-density graphs on 17
5–180 nodes which are known to have clique embeddings on Pegasus.\n\nTag:
Pre-Recorded
URL:https://2020.isc-program.com/presentation/?id=pap181&sess=sess341
END:VEVENT
END:VCALENDAR