Context-aware minor-embedding for quantum annealing processors
department or school: Applied Science, Faculty of
department or school: Electrical and Computer Engineering, Department of
data provider: DSpace
degree campus: UBCV
creator: Pinilla Gomez, Jose Pablo
issued: 2024-05-09T22:56:42Z
issued: 2024
related degree: Doctor of Philosophy - PhD
degree grantor: University of British Columbia
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 p…
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/88270
note: Context-aware Minor-embedding forQuantum Annealing ProcessorsbyJose Pablo Pinilla GomezM.A.Sc., The University of British Columbia, 2016A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)May 2024© Jose Pablo Pinilla Gomez 2024The following individuals certify that they have read, and recommend tothe Faculty of Graduate and Postdoctoral Studies for acceptance, the thesisentitled:Context-aware minor-embedding for quantum annealing processorssubmitted by Jose Pablo Pinilla Gomez in partial fulfillment of therequirements for the degree of Doctor of Philosophyin Electrical and Computer EngineeringExamining Committee:Steve Wilton, Professor, Electrical and Computer Engineering, UBCSupervisorMieszko Lis, Professor, Electrical and Computer Engineering, UBCSupervisory Committee MemberKonrad Walus, Professor, Electrical and Computer Engineering, UBCSupervisory Committee MemberShahriar Mirabbasi, Professor, Electrical and Computer Engineering, UBCUniversity ExaminerRoman Krems, Professor, Chemistry, UBCUniversity ExaminerHausi Mu¨ller, Professor, Computer Science, UVicExternal ExamineriiAbstractA Quantum Annealing Processor (QAP) is a specialized quantum comput-ing device that can solve optimization problems that are hard to solve usingclassical systems. To use a QAP, the problem formulation needs to be con-verted into an Ising model with individual qubit and coupler settings; thisrequires a set of algorithms analogous to computer-aided design for classicaldevices. The minor-embedding stage is particularly important, as it involvesmapping each node in the problem formulation onto the physical lattice ofqubits. However, due to the limited connectivity of qubits, the mappingsoften result in qubit chains. These long chains can negatively affect thefidelity between the samples obtained from the QAP and th…
has type: Thesis/Dissertation
date issued: 2024-11
is shown at: 10.14288/1.0442426
language: eng
degree discipline: Electrical and Computer Engineering
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
rights: Attribution-NonCommercial-NoDerivatives 4.0 International
rights URI: http://creativecommons.org/licenses/by-nc-nd/4.0/
scholar level: Graduate
contributor: Wilton, Steve
type: Text
identifier URI: http://hdl.handle.net/2429/88270