Graph Minor Embedding for Adiabatic Quantum Computing

Author: Liu, T; Li, Z; Dinneen, MJ

Date: 2021

Publisher: Department of Computer Science, The University of Auckland, New Zealand

Type: Report

Link to this item using this URL:

The University of Auckland Library


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.

Subjects: Fields of Research

Citation: ["CDMTCS Research Reports CDMTCS-549 (2021)"]

Copyright: Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.