Graph Minor Embedding for Adiabatic Quantum Computing

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.