Back to search

University of British Columbia

Context-aware minor-embedding for quantum annealing processors

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Electrical and Computer Engineering
Grantor dc:publisher
University of British Columbia
Year dc:date
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pinilla Gomez, Jose Pablo
Contributors dc:contributor
  • Wilton, Steve

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/88270

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Pinilla Gomez, Jose Pablo. Context-aware minor-embedding for quantum annealing processors. doctoral thesis, University of British Columbia, 2024. http://hdl.handle.net/2429/88270