Abstract:
In recent years, adiabatic quantum computing (AQC) has established itself as a useful computing paradigm
which utilizes the underlying physical process of quantum annealing (QA) to help solve NP-hard problems.
The main enabler of this field has been the introduction of QA hardware by D-Wave Systems, the latest of
which has up to 5640 qubits arranged in the topology of a Pegasus graph. Solving NP-hard problems using QA
hardware typically involves a compilation (embedding) step which is equivalent to the graph minor embedding
problem; itself an NP-hard problem. This has spurred the development of heuristic algorithms which can find
valid minor embeddings for a given problem instance in a reasonable amount of time. This paper presents extensions to two papers: Clique Overlap Embedding implements an existing simulated annealing algorithm [1]
with an improved guiding pattern and shifting rule; Fault Tolerant Template Embedding extends an integer programming formulation [2] to allow embedding on Chimera graphs with faulty qubits. Benchmark results show
a marked improvement in embeddability for both approaches when compared to their original implementation,
with each approach also showing distinct areas where they outperform the state of the art.