UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Context-aware minor-embedding for quantum annealing processors Pinilla Gomez, Jose Pablo


A Quantum Annealing Processor (QAP) is a specialized quantum computing device that can solve optimization problems that are hard to solve using classical systems. To use a QAP, the problem formulation needs to be converted into an Ising model with individual qubit and coupler settings; this requires a set of algorithms analogous to computer-aided design for classical devices. The minor-embedding stage is particularly important, as it involves mapping each node in the problem formulation onto the physical lattice of qubits. However, due to the limited connectivity of qubits, the mappings often result in qubit chains. These long chains can negatively affect the fidelity between the samples obtained from the QAP and the original low-energy states of the model. We introduce the concept of context-awareness for minor-embedding; the abstraction, creation, and use of information related to the problem graph, to assist the minor-embedding. We identified two scenarios: (a) layout information, both naturally existing in the formulation, or artificially generated; and (b) structural information, for example, indicating which edges can be omitted from a graph model without losing overall functionality. As proof-of-concept of layout-awareness in minor-embedding, we developed a diffusion-based migration method for global placement, and a Disperse detailed routing method. Adding layout-awareness to a state-of-the-art minor-embedding algorithm resulted in a reduction in runtime by 19%, maximum chain length by 16%, and average chain length by 3.6%. The success rate of a minor-embedding heuristic was increased to 93%, compared to 24-48% over the same set of benchmarks. We describe our novel QAML framework to train both restricted and general Boltzmann machines, using quantum annealing for sampling, and using unique features for structure-aware minor-embedding methods. We implement various qubit fault adaption methods, batched quantum sampling, and pruning. Our experiments show that pruning should be considered if it improves the quality of samples, for example, by simultaneously changing the minor-embedding.

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International