Applied Science, Faculty of
Electrical and Computer Engineering, Department of
DSpace
UBCV
Pinilla Gomez, Jose Pablo
Doctor of Philosophy - PhD
University of British Columbia
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.
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 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 problemgraph, to assist the minor-embedding. We identified two scenarios: (a)layout information, both naturally existing in the formulation, or artificiallygenerated; and (b) structural information, for example, indicating whichedges can be omitted from a graph model without losing overall functionality.As proof-of-concept of layout-awareness in minor-embedding, we devel-oped a diffusion-based migration method for global placement, and a Dis-iiiAbstractperse 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 suc-cess rate of a minor-embedding heuristic was increased to 93%, comparedto 24-48% over the same set of benchmarks.We describe our novel QAML framework to train both restricted andgeneral Boltzmann machines, using quantum annealing for sampling, andusing unique features for structure-aware minor-embedding methods. Weimplement various qubit fault adaption methods, batched quantum sampling,and pruning. Our experiments show that pruning should be considered if itimproves the quality of samples, for example, by simultaneously changingthe minor-embedding.ivLay SummaryThe usability and performance of a computing device is closely tied to thesoftware tools and methods available to program them. As new quantumcomputing paradigms become available, new challenges become relevant intheir programming flow.Quantum annealing processors (QAPs) are a specialized type of device,useful for optimization and to collect samples from machine learning models.Minor-embedding, or mapping, from a user-defined graph onto the qubitfabric graph of each device is a crucial part of programming QAPs.Our work uses contextual information associated with the problem graphto guide the minor-embedding algorithms and improve the quality of results.Our contributions include a set of novel context-aware methods and modi-fications to the minor-embedding step that result in improvements in run-time, success rate, and quality of the samples obtained from QAPs availabletoday.vPrefaceThis dissertation is original, independent work by the author, Jose P. Pinilla,under the supervision of Prof. Steven J. E. Wilton. The work presented herehas led to the following publications:• [Poster] Jose P. Pinilla and Steven J.E. Wilton., Layout-Aware Em-bedding of Quantum-dot Cellular Automata Networks onto a Quan-tum Annealer at the 55th Design Automation Conference (DAC55) in2018 [140]• [Conference / Proceedings] Jose P. Pinilla and Steven J.E. Wilton.,Layout-Aware Embedding for Quantum Annealing Processors at the34th International Supercomputing Conference (ISC High Performance)in 2019, and published in the Lecture Notes in Computer Science(LNCS) Vol. 11501, pp. 121–139 [142]• [Symposium / Book Chapter] Jose P. Pinilla and Steven J.E. Wilton.,Structure-Aware Minor-Embeddings for Machine Learning in Quan-tum Annealing Processors at the International Symposium on Quan-tum Computing: Circuits Systems Automation and Applications (QC-CSAA) in 2022 and published in the book of the same name in 2023,1st edition, pp. 89-99 [141]viPreface• [Conference / Proceedings] Jose P. Pinilla and Steven J.E. Wilton.,Positive-phase Temperature Scaling for Quantum-Assisted BM Train-ing at the International Conference on High Performance Computing,Networking, Storage and Analysis (SC’22) in 2022 [143]Access to the D-Wave Leap [43] quantum application environment anduse of the quantum annealing processors in our experiments, was enabledby D-Wave Systems Inc. Our contributions were prototyped using the D-Wave Ocean software [40], Pytorch [132], and packaged into two open-sourcerepositories for minor-embedding tools [138] and a quantum-assisted ma-chine learning framework [139].viiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xivList of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . xviiList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . xviiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . xx1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Quantum Computing Technologies . . . . . . . . . . . . . . . 31.2 Quantum Computing Models . . . . . . . . . . . . . . . . . . 31.2.1 Quantum Gates . . . . . . . . . . . . . . . . . . . . . 41.2.2 Quantum Annealing . . . . . . . . . . . . . . . . . . . 5viiiTABLE OF CONTENTS1.3 Quantum Annealing Applications . . . . . . . . . . . . . . . 61.4 The Minor-Embedding Problem . . . . . . . . . . . . . . . . 81.5 Overall Goal and Objectives . . . . . . . . . . . . . . . . . . 91.5.1 Research Objectives . . . . . . . . . . . . . . . . . . . 101.6 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.6.1 Layout-Awareness for Optimization Problems . . . . 111.6.2 Structure-Awareness for ML applications . . . . . . . 121.7 Significance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.8 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.1 Quantum Computing Principles . . . . . . . . . . . . . . . . 162.2 Adiabatic Quantum Computing . . . . . . . . . . . . . . . . 172.3 Quantum Annealing Processors . . . . . . . . . . . . . . . . 192.3.1 D-Wave Topologies . . . . . . . . . . . . . . . . . . . 232.4 QAP Programming Flow . . . . . . . . . . . . . . . . . . . . 272.4.1 Problem Modelling . . . . . . . . . . . . . . . . . . . 292.4.2 Graph Embedding . . . . . . . . . . . . . . . . . . . . 312.4.3 Parameter Setting . . . . . . . . . . . . . . . . . . . . 352.4.4 Anneal Scheduling . . . . . . . . . . . . . . . . . . . . 392.4.5 Sample Resolution . . . . . . . . . . . . . . . . . . . . 412.5 Related work on Minor-Embedding for QAPs . . . . . . . . . 422.5.1 Systematic . . . . . . . . . . . . . . . . . . . . . . . . 422.5.2 Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . 472.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51ixTABLE OF CONTENTS3 Context-Awareness: Layout Information . . . . . . . . . . . 533.1 Motivating Examples . . . . . . . . . . . . . . . . . . . . . . 543.1.1 Antenna Selection . . . . . . . . . . . . . . . . . . . . 543.1.2 Quantum-dot Cellular Automata (QCA) . . . . . . . 553.1.3 Artificial Location Information . . . . . . . . . . . . . 583.2 Layout-Aware Minor-Embedding Methods . . . . . . . . . . 583.2.1 Global Placement . . . . . . . . . . . . . . . . . . . . 593.2.2 Disperse Router . . . . . . . . . . . . . . . . . . . . . 643.2.3 Combined Approach . . . . . . . . . . . . . . . . . . . 653.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663.3.1 Embedding Results . . . . . . . . . . . . . . . . . . . 693.3.2 Sampling Results . . . . . . . . . . . . . . . . . . . . 713.4 Conclusions and Discussion . . . . . . . . . . . . . . . . . . . 734 Quantum-Assisted Machine Learning . . . . . . . . . . . . . 784.1 Boltzmann Machines . . . . . . . . . . . . . . . . . . . . . . 804.1.1 Learning Rules . . . . . . . . . . . . . . . . . . . . . . 824.1.2 Restricted Boltzmann Machine (RBM) . . . . . . . . 844.1.3 Quantum-Assisted Boltzmann Machines . . . . . . . 864.2 QAML Software Framework . . . . . . . . . . . . . . . . . . 884.2.1 Framework Components . . . . . . . . . . . . . . . . 884.2.2 Framework Configurations . . . . . . . . . . . . . . . 964.3 Temperature Estimation . . . . . . . . . . . . . . . . . . . . 984.3.1 Physical Temperature Approximation . . . . . . . . . 994.3.2 Exact Computation . . . . . . . . . . . . . . . . . . . 100xTABLE OF CONTENTS4.3.3 Adaptive Hyperparameter . . . . . . . . . . . . . . . 1014.4 Negative-Phase Temperature Scaling . . . . . . . . . . . . . 1014.4.1 Limitations of Negative-Phase Temperature Scaling . 1024.5 Evaluation: Range Scaling . . . . . . . . . . . . . . . . . . . 1044.6 Contribution: Positive-Phase Temperature Scaling . . . . . . 1094.6.1 Evaluation: Positive-phase Temperature Scaling . . . 1114.6.2 Conclusions: Temperature Scaling . . . . . . . . . . . 1134.7 Discussion: QAML Framework . . . . . . . . . . . . . . . . . 1185 Context-Awareness: Structure Information in QAML . . 1205.1 Structure-Aware Minor-Embedding for RBMs . . . . . . . . 1235.1.1 Heuristic vs Systematic . . . . . . . . . . . . . . . . . 1245.1.2 Evaluation: Heuristic vs Systematic . . . . . . . . . . 1245.1.3 Adaption Methods for RBMs . . . . . . . . . . . . . . 1275.1.4 Evaluation: RBM Training with Pruning . . . . . . . 1345.1.5 Related Work . . . . . . . . . . . . . . . . . . . . . . 1395.1.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . 1405.2 Structure-Aware Minor-Embedding for General BMs . . . . 1415.2.1 QABM negative-phase sampling . . . . . . . . . . . . 1445.2.2 QABM positive-phase sampling . . . . . . . . . . . . 1445.2.3 Batched Quantum Sampling . . . . . . . . . . . . . . 1465.2.4 Heuristic vs Systematic . . . . . . . . . . . . . . . . . 1505.2.5 Pruning ratios . . . . . . . . . . . . . . . . . . . . . . 1575.2.6 Related Work . . . . . . . . . . . . . . . . . . . . . . 1615.2.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . 163xiTABLE OF CONTENTS5.3 Discussion: Structure-awareness in QAML minor-embedding 1646 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1676.1 Layout-Awareness . . . . . . . . . . . . . . . . . . . . . . . . 1686.2 QAML Framework . . . . . . . . . . . . . . . . . . . . . . . . 1686.3 Structure-Awareness . . . . . . . . . . . . . . . . . . . . . . . 1696.4 Applicability . . . . . . . . . . . . . . . . . . . . . . . . . . . 1726.5 Future Work: Short-term . . . . . . . . . . . . . . . . . . . . 1736.6 Future Work: Exploratory directions . . . . . . . . . . . . . 175Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177AppendicesA The Chimera Family . . . . . . . . . . . . . . . . . . . . . . . . 209xiiList of Tables3.1 Benchmarks. . . . . . . . . . . . . . . . . . . . . . . . . . . . 684.1 QAP configuration sheet. . . . . . . . . . . . . . . . . . . . . 1074.2 Dataset datasheet. . . . . . . . . . . . . . . . . . . . . . . . . 1124.3 Training datasheet . . . . . . . . . . . . . . . . . . . . . . . . 1125.1 Dataset datasheet. . . . . . . . . . . . . . . . . . . . . . . . . 1265.2 Training datasheet. . . . . . . . . . . . . . . . . . . . . . . . . 1265.3 Quality of systematic embeddings. . . . . . . . . . . . . . . . 136xiiiList of Figures1.1 QAML overview. . . . . . . . . . . . . . . . . . . . . . . . . . 132.1 Example of an annealing schedule. . . . . . . . . . . . . . . . 222.2 Chimera [73] topology. . . . . . . . . . . . . . . . . . . . . . . 242.3 Pegasus [27] topology. . . . . . . . . . . . . . . . . . . . . . . 252.4 Zephyr [89] topology. . . . . . . . . . . . . . . . . . . . . . . . 262.5 The programming flow for QAPs. . . . . . . . . . . . . . . . . 282.6 Example demonstrating chains during embedding. . . . . . . 322.7 Example demonstrating coupler strengths after embedding. . 372.8 Timing diagram for each QPU call. . . . . . . . . . . . . . . . 402.9 Timing diagram breakdown of the sampling time. . . . . . . . 402.10 Systematic K12,12 onto Chimera C(3, 3, 4). . . . . . . . . . . . 432.11 Systematic K12,12 onto Pegasus P(3). . . . . . . . . . . . . . . 442.12 Systematic K12,12 onto Zephyr Z(2). . . . . . . . . . . . . . . 452.13 Systematic K12 onto Chimera C(3, 3, 4). . . . . . . . . . . . . 463.1 The antenna interference problem. . . . . . . . . . . . . . . . 543.2 QCA components and circuits. . . . . . . . . . . . . . . . . . 563.3 Layout-aware embedding flow. . . . . . . . . . . . . . . . . . . 61xivLIST OF FIGURES3.4 Comparison of embedding methods. . . . . . . . . . . . . . . 673.5 Comparison of chain metrics. . . . . . . . . . . . . . . . . . . 703.6 D-Wave energy statistics. . . . . . . . . . . . . . . . . . . . . 723.7 (continued) D-Wave energy statistics. . . . . . . . . . . . . . 753.8 (continued) D-Wave energy statistics. . . . . . . . . . . . . . 763.9 (continued) D-Wave energy statistics. . . . . . . . . . . . . . 774.1 Boltzmann Machine. . . . . . . . . . . . . . . . . . . . . . . . 814.2 Restricted Boltzmann Machine. . . . . . . . . . . . . . . . . . 854.3 Bars-And-Stripes (BAS) dataset. . . . . . . . . . . . . . . . . 904.4 OptDigits dataset. . . . . . . . . . . . . . . . . . . . . . . . . 914.5 QAML framework. . . . . . . . . . . . . . . . . . . . . . . . . 974.6 Boltzmann distance without range-scaling. . . . . . . . . . . . 1064.7 Boltzmann distance with range-scaling. . . . . . . . . . . . . 1084.8 Accuracy tests with negative-phase β scaling. . . . . . . . . . 1144.9 (Continued) Accuracy tests with negative-phase β scaling. . . 1154.10 Accuracy tests with positive-phase β scaling. . . . . . . . . . 1164.11 (Continued) Accuracy tests with positive-phase β scaling. . . 1175.1 Quality of heuristic embeddings. . . . . . . . . . . . . . . . . 1255.2 Comparison between systematic and heuristic. . . . . . . . . . 1285.3 Systematic minor-embedding with faults. . . . . . . . . . . . 1305.4 Minor-embedding adaption flow. . . . . . . . . . . . . . . . . 1315.5 Adaptions made to the RBM graph . . . . . . . . . . . . . . . 1335.6 Classical RBM testing accuracy with adaptions. . . . . . . . . 1365.7 QARBM testing accuracy with adaptions. . . . . . . . . . . . 138xvLIST OF FIGURES5.8 Creating the hidden node subgraph. . . . . . . . . . . . . . . 1455.9 Batch embedding in the positive-phase. . . . . . . . . . . . . 1485.10 Batch embedding in the negative-phase. . . . . . . . . . . . . 1495.11 Heuristic minor-embedding quality. . . . . . . . . . . . . . . . 1515.12 Systematic minor-embedding quality. . . . . . . . . . . . . . . 1525.13 Heuristic vs systematic precision. . . . . . . . . . . . . . . . . 1555.14 Heuristic vs systematic recall. . . . . . . . . . . . . . . . . . . 1565.15 Heuristic vs systematic score. . . . . . . . . . . . . . . . . . . 1575.16 Sampling precision with pruning . . . . . . . . . . . . . . . . 1595.17 Sampling recall with pruning . . . . . . . . . . . . . . . . . . 1605.18 Sampling score with pruning . . . . . . . . . . . . . . . . . . 161A.1 The Chimera graph C(3, 3, 4). . . . . . . . . . . . . . . . . . . 209A.2 The Pegasus graph P(2) . . . . . . . . . . . . . . . . . . . . . 210A.3 The C(12, 12, 2) equivalent of the P(2) . . . . . . . . . . . . . 210A.4 The Zephyr graph Z(1). . . . . . . . . . . . . . . . . . . . . . 211A.5 The C(3, 3, 8) equivalent of the Z(1) . . . . . . . . . . . . . . 211xviList of Algorithms2.1 Path-search heuristic example. . . . . . . . . . . . . . . . . . . 493.1 Layout-aware minor-embedding. . . . . . . . . . . . . . . . . . 593.2 Diffusion-based migration. . . . . . . . . . . . . . . . . . . . . 604.1 Gradients using negative-phase β scaling. . . . . . . . . . . . . 1034.2 Gradients using positive-phase β scaling. . . . . . . . . . . . . 110xviiList of AbbreviationsAPI: Application Programming InterfaceAQC: Adiabatic Quantum ComputationBAS: Bars-And-StripesBM: Boltzmann MachineBQM: Binary Quadratic ModelCAD: Computer-Aided DesignCD: Contrastive DivergenceCD-k: Contrastive Divergence with Gibbs-k samplingCSP: Constraint Satisfaction ProblemDBM Deep Boltzmann MachineDBN Deep Belief NetworkDNN Deep Neural NetworkDQM Discrete Quadratic ModelFPGA: Field-Programmable Gate ArrayGPU: Graphics Processing UnitGS: Ground StateHPC: High-Performance ComputingISG: Ising Spin GlassLBM: Limited Boltzmann MachinexviiiList of AbbreviationsMAE: Mean Absolute ErrorMCMC: Markov-Chain Monte CarloML: Machine LearningNISQ: Noisy Intermediate-Scale QuantumNP: Non-deterministic PolynomialQABM: Quantum Assisted Boltzmann MachineQAML: Quantum Assisted Machine LearningQAOA: Quantum Approximate Optimization AlgorithmQAP: Quantum Annealing ProcessorQARBM: Quantum Assisted Restricted Boltzmann MachineQBM: Quantum Boltzmann MachineQC: Quantum ComputingQCA: Quantum-dot Cellular AutomataQIP: Quantum Information ProcessingQPU: Quantum Processing UnitQUBO: Quadratic Unconstrained Binary OptimizationQVAE: Quantum Variational AutoEncoderRBM: Restricted Boltzmann MachineSA: Simulated AnnealingSGD: Stochastic Gradient DescentTPU: Tensor Processing UnitTTS: Time-To-SolutionVLSI: Very Large Scale IntegrationxixAcknowledgementsI thank my advisor, Prof. Steve Wilton, for the support and guidance thatmade this work possible. His commitment, knowledge, and perspicacity areadmirable. I am lucky to be his student, and I enjoyed going through thelearning experience of this new and exciting research together with him.This work was funded by the National Sciences and Engineering ResearchCouncil of Canada (NSERC), and in-kind contributions from D-Wave Sys-tems Inc. in the form of free access to their hardware and, far more valuable,the insights from their research staff. Special thanks to Dr. Kelly Boothbyand Dr. Pau Farre´ for our monthly conversations, and to Professors YairLinn, Mieszko Lis, Konrad Walus, Wayne Luk, and Olivia di Matteo, whoprovided me with fulfilling teaching assistantships, and/or enlightening lec-tures and technical discussions.I also appreciate the input and inspiration I received from colleaguesand friends including Jenny Mun˜oz, Marta Zonno, Gigi Ma´rquez, KristtySchneider-Beltran, Davide Tortora, Daniel Holanda Noronha, Giulia Natal-ini, Mirtha Gamiz, Hector Go´mez, Dave Evans, Al-Shahna Jamal, EddieHung, Jacob Retallick, John Deppe, Kahlan Gibson, Nikhil Ghanathe, Za-kary Nafziger, Esther Roorda, Martin Chua, and Andrew David Gunter,among many others.xxAcknowledgementsI am forever thankful to my parents for their unwavering care, strongdedication to my well being, and for supporting my every choice. To mybrothers, sisters-in-law and nephews, who are all my role models, for settingthe highest bars for professionalism and witticism. And to Tiffany Ngo, forher contagious empathy, honesty, and curiosity.xxiChapter 1IntroductionThe growing demand for high-performance computing (HPC) systems, andthe physical limitations encountered when scaling the fabrication of elec-tronic devices,1 has brought unprecedented attention to Quantum Informa-tion Processing (QIP) research, with the long-term goal of creating quantumcomputers and their associated frameworks and software stacks. Already,many large companies are investing in quantum computing in an attempt tounderstand the potential disruptive benefits and limitations of this emergingtechnology.Research into QIP includes (a) developing algorithms that exploit thenature of emerging quantum computers (e.g., Grover’s search [72], Shor’s fac-torization [157], or Quantum Approximate Optimization Algorithm (QAOA) [62]),(b) creating systems that make use of quantum effects (e.g., quantum an-nealing [86], measurement-based quantum computing [148], quantum-dotcellular automata (QCA) [77], or quantum communication and cryptogra-phy [20]), and (c) work that borrows from quantum theory, such as quantum-inspired software and hardware [8, 70, 177, 184].A “quantum race” for the demonstration of applicable quantum advan-1Smaller (nano-scale) transistors have increasing leakage currents due to quantum tun-nelling, signalling the end of Dennard’s scaling and, with it, Moore’s law.1Chapter 1. Introductiontage motivates major private and public [60, 71, 81, 169] investments in thefield. At the time of writing, some of the most impactful companies withQC devices (and their corresponding software frameworks) include IBM(Qiskit) [170], Google (Cirq) [37], D-Wave (Ocean) [39], Xanadu (Penny-Lane) [21], and Rigetti (QCS) [87].Regardless of the underlying technology, the goal is to create a control-lable system that can emulate the real world at the quantum level, and iscapable of implementing those specialized algorithms. In its simplest form,quantum computing takes an array of qubits in a device, and subjects themto a sequence of transformations. The term qubit refers to both the physicaltwo-state quantum system, and the unit of quantum information. At thefinal state of the system, the configuration of the qubits is described by aquantum state vector that encodes the solution to a higher level problemor part of a problem. Quantum computing, in practice, can be regarded asa heuristic approach because the behaviour of a quantum system is inher-ently probabilistic. Measuring a qubit effectively “collapses” its state ontoa binary value; therefore, samples are collected by re-running the system tobuild a probability distribution of the outcomes.The following sections give a brief description of the quantum comput-ing landscape, including quantum technologies and models of computation.This is provided as context, and to highlight the scope of this work. Thisdissertation is focused on the quantum annealing model of quantum com-puting, and addresses challenges found in the efficient use of resources andits impact on the performance of real-world quantum annealing devices.21.1. Quantum Computing Technologies1.1 Quantum Computing TechnologiesThe most adopted technology in quantum computing devices, so far, is thesuperconducting qubit [61]. This is the only approach that uses a macro-scopic system, i.e., does not require controlling single atoms, electrons, orphotons. Instead, magnetic fields are used to control the phase, charge, orflux in a superconducting circuit [9, 66, 78, 84, 154]. This has the significantbenefit of using a manufacturing approach that is similar to what is used inconsumer electronics today. However, it has the added complexity of havingto operate at a temperature of near absolute zero to effect superconductivity.The maturity and viability of a quantum computing technology canbe measured by the scalability, connectivity, volatility,2 and fidelity of itsqubits. Other QC technologies, such as those controlling photons [109],electrons [110], ions or atoms [59], have also been demonstrated but arecurrently less mature. In the future, however, it is unclear which of thesequbit technologies will prevail; or if the most viable one has not yet beendiscovered. Because of the current state of these technologies, this is cur-rently considered the NISQ era, for Noisy Intermediate-Scale Quantum [144]devices.1.2 Quantum Computing ModelsTwo different models of quantum computing stand out: quantum gates andquantum annealing. Although both models use interconnected qubits, the2Measured by the decoherence time of a qubit, i.e., how long it can remain in a quantumstate, not explained by classical effects.31.2. Quantum Computing Modelsmanner in which these qubits are used to perform computation is differ-ent. We believe these models are complementary – just like CPUs, GPUs,FPGAs, and other classical compute accelerators can coexist, so can thedifferent models in quantum computing. In this dissertation, we focus onquantum annealing. However, we hope that some of the lessons learned maymotivate similar ideas for gate model quantum computers. We return to thiscomment in Section 6.5 Future Work.1.2.1 Quantum GatesMost of the effort in developing quantum computers has focused on thegate-based model, also known as the circuit model. In this model, a setof transformations, referred to as “gates”, are applied to single qubits ormultiple qubits. A sequence of quantum gates is a quantum circuit. Thecapability of the gates to transform the system from/to any quantum state,makes this a universal model of computation. In theory, quantum algo-rithms (or circuits) can be executed with significant speedup, and scale withfewer resources than purely classical systems [72, 157], due to their use ofsuperposition and entanglement.The current state of the quantum gates devices shows promise, withdemonstrations of quantum advantage for experimental sampling problems [50,109]. However, gate-model quantum computers rely heavily on the non-volatility, and fidelity of the qubits, i.e., if an error occurs at any point inthe sequence, it propagates to the final state. These errors can be mitigatedwith the use of error correction methods [106], which use redundancy andtherefore require even more scalability.41.2. Quantum Computing Models1.2.2 Quantum AnnealingThis dissertation focuses on devices created using the quantum annealingmodel of quantum computing. Such devices are often referred to as quan-tum annealers or quantum annealing processors (QAPs). Unlike the univer-sal gate model, quantum annealers offer a specialized approach to quantumcomputation. Based on the principles of Adiabatic Quantum Computation(AQC), quantum annealers are more lenient in their requirements for scal-ability, because they are limited to the continuous evolution of the qubitsstate while subjected to one parameterized Hamiltonian operator. This con-cept is explained in more detail in Chapter 2.In 2010, the company D-Wave Systems Inc. commercialized the firstQAP using flux superconducting qubits [73, 84]. To this day, D-Wave is theonly commercial provider of QAPs. Other notable efforts have been madein the improvement and search for alternatives of quantum annealing from,for example: USC-IARPA [26, 127, 173], Qilimanjaro [32], NEC [59], andothers [11, 166]; as well as quantum-inspired hardware for digital anneal-ing [8, 70, 114, 177].The quantum annealing devices from D-Wave have been shown to have acomputational advantage in the simulation of the dynamics of a 3D spin glasson thousands of qubits [50, 93]. However, these experimental demonstrationsare not proof of a practical advantage over classical computers. One ofthe reasons is because the problems created in those experiments use thenative connectivity of the QAPs, which have topological properties thatmay be exploited by specialized classical algorithms. One important aspect51.3. Quantum Annealing Applicationsin the effort to make quantum computing a real-world alternative to classicaldevices, is the ability to efficiently map arbitrary problems onto qubits.1.3 Quantum Annealing ApplicationsThe applicability of QAPs has been shown in multiple real-world scenarios.An extensive inventory of applications can be found in D-Wave’s FeaturedApplications website [44] and the independent survey by Yarkoni et al. [179].This section presents a high-level view and the references included below arenot exhaustive, but only to give a flavour of what can be done using quantumannealing.Computational Physics and ChemistrySome of the most sought-out applications in quantum computing are inthe realm of computational physics and chemistry. This is because thereis a close match between the model of the system being simulated, and thecomputing model [74, 92, 103, 105, 152]. Additionally, some of these projectscould have significant impact, i.e., from the discovery of new drugs [67, 94],to applications in particle physics [118].LogisticsQuantum annealing machines have been used for logistics applications span-ning real-time traffic [80] and scheduling [79, 180] because of the complexityand recurrent nature of optimization problems in these environments. Thesolutions are often not required to be a global minimum, but instead a61.3. Quantum Annealing Applicationsgood and fast solution that allows the continuous operation of the processinvolved, e.g., airport gate assignment [162], or any other resource realloca-tion in transport-network-design problems [54].FinanceApplications in finance are commonly framed in terms of optimization frame-works; e.g., portfolio optimization [171], risk analysis [51], market genera-tors [137], anomaly detection [161], and more [75]. These problems havegained attention due to the scale, in terms of the number of variables thatare needed to make these models. This allows researchers to test large-scaleproblems using hybrid quantum-classical methods, which partition the prob-lems to map them onto current generation devices (e.g., 1272 fully-connectednodes [119]).Machine Learning (ML)Machine learning is transformative, and the use of QAPs for these modelshas been the focus of a significant amount of research. QAPs may be a goodfit for some ML tasks due to the probabilistic nature of quantum computing,which is seen as beneficial for generalization. Two distinct approaches in thisfield are optimization-based [29, 118, 124, 125, 159] and sampling-based [2,18, 52, 57, 58, 90, 97, 102–105, 117, 123, 137, 155, 156, 160, 161, 172, 174].Section 2.4.1 and Chapter 4 are dedicated to sampling-based methods, andthe particular case of Boltzmann machine (BM) training, respectively.71.4. The Minor-Embedding Problem1.4 The Minor-Embedding ProblemCommercial implementations of QAPs from D-Wave Systems Inc., havebeen made available for over a decade [73], with sustained open access forthe general public [43]. Central to the use of QAPs is the formulation ofa Quadratic Unconstrained Binary Optimization (QUBO) (i.e., over vari-ables x ∈ {0, 1}) or Ising Spin Glass (ISG) graphical models (i.e., over spinvariables s ∈ {−1,+1}); collectively known as Binary Quadratic Models(BQMs). The BQM minimization problem is NP-Complete3 and, conse-quently, many known NP problems can be mapped onto it [68, 74, 107, 130].The variables (binary or spin) in these problems must be mapped onto arelatively sparse fabric of qubits available in the QAP, and repeatedly sub-jected to the quantum annealing process to collect samples that minimize thetotal energy of the ISG formulation, or Ising model. This mapping step, orminor-embedding, typically requires the use of extra qubits solely to provideconnections between qubits which are otherwise not coupled in the archi-tecture, leading to “qubit chains”. The terms minor-embedding, embedding,and mapping are used interchangeably throughout this dissertation.The sparsity of the QAP fabric, as well as the presence of defective qubits(due to imperfections in manufacturing) makes finding an optimal mappingNP-Hard4 [31]. Nonetheless, finding a good solution to the problem is vitalfor at least two reasons: (a) the capabilities of the mapping algorithm canimpact the size (or complexity) of the problems that can be solved, and(b) the quality (energy levels) of the annealing samples depends on the3Can be solved (at best) with non-deterministic methods in polynomial time4At least as hard as NP-complete, but not necessarily verifiable in polynomial time.81.5. Overall Goal and Objectivesstructure of the mapping. Sections 2.4 and 2.5 describe in more detail theconsiderations and state-of-the-art in minor-embedding algorithms.Future QAP architectures will likely achieve several improvements overthe current generation, e.g., number of qubits, higher connectivity, lowernoise, and more control on the annealing schedule (required for fair sam-pling [96, 111]), but will likely continue to require the step ofminor-embeddingdue to the graph’s connectivity not being complete [30, 35]. In the longterm, minor-embedding algorithms will be as critical to quantum annealingas placement algorithms are to digital circuit design today; i.e. Computer-aided design (CAD) for Very-Large-Scale Integration (VLSI) chip design,and Field-Programmable Gate Array (FPGA) programming.1.5 Overall Goal and ObjectivesThis dissertation is focused on new methods to minor-embed Binary QuadraticModels onto the qubit fabric of quantum annealing devices. As described inSection 2.5, the state-of-the-art in minor-embedding algorithms for QAPs isdominated by heuristics that are context-agnostic, i.e., only informed by theadjacency of the input graph and target graph [28, 31, 48]. Our approachwill be different in that our overall goal is to find information, in differ-ent problem formulations or problem types, that can be given as input to acontext-aware minor-embedding method, such that the process of finding aminor is improved.With that in mind, two areas were identified in which the use of contex-tual information can provide useful insight to the minor-embedding methods:91.5. Overall Goal and Objectiveslayout information in the problem instance, and structural information thatallows modifications to the graph, without losing overall functionality.1.5.1 Research ObjectivesMore precisely, this dissertation is focused on the problem of minor-embeddingas a means to improve the usability and the results obtained from quantumannealing devices. To achieve this, there are three main objectives:Layout-Awareness in Minor-Embedding Methods: To design andevaluate the effectiveness of layout-aware minor-embedding algorithms usedin the mapping of problem graphs onto the qubit fabric of quantum annealingdevices.Quantum-Assisted Machine Learning Framework: To implement afirst-of-its-kind software framework that allows for the training and evalu-ation of quantum-assisted machine learning models using D-Wave’s QAPsas Boltzmann machine samplers. This framework has the unique ability tomodify the minor-embedding methods and allows for structural modifica-tions of the network.Structure-Awareness in BM Minor-Embedding Methods: To in-corporate and evaluate the effects of modifications to the training methodsfor QAML models, that take into account their structural properties andsimultaneously modify the graph and its minor-embedding onto the QAP.101.6. Challenges1.6 ChallengesThe overarching challenges addressed in this research are: (1) designing andimplementing methods that can take advantage of the contextual informa-tion, and (2) observe and quantify the impact on the quality of samplescaused by the changes made to the programming flow. Both of these chal-lenges manifest differently for each of the two areas of work: layout andstructure awareness.1.6.1 Layout-Awareness for Optimization ProblemsThe idea of using the 2D coordinates of nodes in a graph to allocate nodesonto hardware resources predates the existence of QAPs; placement methodsin digital logic CAD-tools for VLSI and FPGA are long standing examplesof this approach [108, 158]. Generally, optimization problems have naturallocation information, or have an innate spatial locality that can be exposedby a graph drawing algorithm. However, challenges arise in the formulationof an efficient method that generates a global placement from the input2D location coordinates, such that it meets the requirements of the minor-embedding problem, and minimizes the overall cost.In comparison with the digital logic scenario, where each logic unit (e.g.,gate, register, memory block, etc.) is mapped to a single hardware resource,the result of the quantum annealing minor-embedding is a mapping in whicheach graph node is assigned to one or (more likely) multiple qubits. This ismade more difficult by the fact that, even though there is a symmetry andregularity in the architecture design of QAPs, because of the sensitivity to111.6. Challengeserrors, these systems are designed such that some of the resources can bedecommissioned. Individual qubits or couplers that do not satisfy an errorrate, after calibration, are disabled to allow chips to remain functional atimperfect yields.Moreover, the “quality” of the mapping does not adhere to the samemetrics (e.g., critical path delay, design frequency). Instead, the length andconnectivity of the resulting “qubit chains” determines the size of problemthat can be mapped, and the performance of the sampling device. Sec-tion 2.4.2 describes the problem of minor-embedding in more detail.1.6.2 Structure-Awareness for ML applicationsThis part of the work exists at the intersection of two major research fields:machine learning and quantum computing. As such, it is open to signifi-cant opportunities for novel contributions while, simultaneously, presentingsignificant challenges.The field of quantum-assisted machine learning (QAML), similarly toclassical ML, expands through many different models and training methods.Figure 1.1 is an overview of the building blocks found in a typical QAMLtraining and testing flow, and the specific methods and attributes that aretargeted in this work. As the name implies, QAML includes a quantumcomputing device in the loop, to assist the process of training and/or testingof the ML model. In this case, the QAP graph represents the fabric of qubits.Initially, a substantial challenge to develop the proposed contributionsin this work is that a standardized QAML framework does not exist. Thisis a requirement to be able to provide baseline metrics and comparables,121.7. SignificanceBoltzmann Machine (BM )or Restricted BM (RBM)Heurisc orSystemacStochascGradient DescentBars-And-Stripes (BAS) orOptDigits or MNISTFigure 1.1: QAML overview.as well as identifying weaknesses in the underlying theory. As an example,Section 4.4 describes an opportunity for improvement found in the trainingalgorithm, with the proposed solution in Section 4.6.Regarding minor-embedding specifically, the biggest challenge in QAMLis that the “adaption” of the machine learning model, together with theassignment of nodes to qubits, is an unexplored area. Therefore, new meth-ods and resources were developed to achieve this type of training, as well asmeans to evaluate the impact that can be observed during and as a resultof training.1.7 SignificanceThis work presents various systems and methods that achieve significantprogress in enabling the quantum annealing technology to solve otherwiseintractable problems, i.e., problems for which a solution cannot be foundin a practical amount of time. This progress is directly reflected in meth-ods that allow larger problem formulations to be mapped more efficiently in131.8. OrganizationChapter 3, improvements in the performance of QAPs for Boltzmann ma-chine sampling in Chapter 4, and demonstrations of QAML model pruningand its effects on the training performance in Chapter 5.Further, this dissertation demonstrates the impact that the quality of aqubit mapping can have on the fidelity between the QAP samples and thesolution to the original problem, whether it is the energy minimization ofan Ising model or the probability distribution of a Boltzmann machine. Un-derstanding the relationship between qubit mapping quality and the fidelityof QAP sampling will be important to develop new and better mappingalgorithms, maximizing the utility of this technology.The software framework and experiments presented throughout this dis-sertation have been made available to the public as open-source code repos-itories online [138, 139]. Additional contributions have been made to D-Wave’s open-source software and are now part of the standard D-Wave CADtools [42, 46, 48].1.8 OrganizationThis chapter presented a high-level overview of this thesis, the motivationand objectives, as well as the challenges behind them. Chapter 2 is a self-contained description of the most relevant concepts relating to the theoryof quantum annealing, as well as the programming flow that a potentialQAP user interacts with. Chapter 3 details the contributions made onlayout-aware minor-embedding methods, with evaluations and discussionpertinent to optimization problems. Chapter 4 describes the details of the141.8. Organizationalgorithms and components of the QAML framework, as well as the con-tributions made throughout its development. Chapter 5 describes the in-tegration of structure-awareness to the minor-embedding methods used inQAML. Lastly, Chapter 6 summarizes the overall accomplishments of thisthesis, and outlines some possible avenues of future work.15Chapter 2BackgroundThis chapter provides an overview of the theory behind quantum computingand quantum annealing. We describe the hardware specifications and theCAD flow (or software stack) used to program quantum annealing devices,with special attention to the minor-embedding process. Minor-embeddingrepresents a significant bottleneck in the run-time and performance of QAPs,and is the focus of this thesis.2.1 Quantum Computing PrinciplesA quantum computing device is an array of programmable qubits, fabri-cated in any of the technologies mentioned in Section 1.1. Symbolically, aquantum state vector (|Ψ⟩ ∈ C2N ) has a value for each of the binary qubitcombinations. For example, a two-qubit system is shown in Equation (2.1),with its corresponding Dirac notation which is the linear combination (orsuperposition) of the basis states. Transformations of |Ψ⟩ are representedby 2N × 2N unitary matrices, called operators, which guarantee that nor-malization is preserved; i.e.,∑Ni=0 |cn|2 = 1.162.2. Adiabatic Quantum Computing|Ψ⟩ =c0c1c2c3 = c0 |00⟩+ c1 |01⟩+ c2 |10⟩+ c3 |11⟩ (2.1)At equilibrium, and in accordance with the time-independent Schro¨dingerequation (2.2), |Ψ⟩ is an eigenfunction for the energy observable opera-tor (a.k.a. the Hamiltonian Hˆ). This means that the possible outcomes,when measuring the energy of the system, are discretized as the scalarsE ∈ {E0, E1, . . . , E2N−1}, at eigenstates |Ψ⟩ ∈ {|ψ0⟩ , |ψ1⟩ , . . . , |ψ2N−1⟩}.Hˆ |Ψ⟩ = E |Ψ⟩ (2.2)The eigenstate (or eigenstates) associated with the lowest energy valueis a ground state (ψGS, EGS), and any other state is an excited state. Theground state, therefore, is a superposition of states, and the probability offinding each binary state at readout is Pn = |cn|2.With that in mind, a quantum computer is a physical realization of aparameterizable system that “quantum-mechanically” (i.e., subject to quan-tum tunnelling and entanglement) evolves towards its ground state. Simu-lating these systems classically is not practical because these require solvingfor the eigenstates and eigenvalues of a Hamiltonian with dimensions thatscale exponentially with the number of qubits.2.2 Adiabatic Quantum ComputingThe operating principle of quantum annealing (QA) is inspired by the adi-abatic theorem which states that a quantum-mechanical system will remain172.2. Adiabatic Quantum Computingin its ground state as long as the environment changes slowly. The theoryof adiabatic quantum computing (AQC) [5] describes a system of intercon-nected qubits that are set up such that the Hamiltonian operator describingthe system in its idle state (Hˆd) has a trivial ground state, and is slowly5manipulated to introduce a user-programmable Hamiltonian (Hˆp).The time evolution of the system is described by Equation (2.3) where,over time, A(S) decreases, thereby decreasing the contribution of the systemHamiltonian; and B(S) increases, thereby increasing the contribution of theprogrammable (or problem) Hamiltonian. Correspondingly, A(0) >> B(0)and A(1) << B(1).Hˆ = A(s)Hˆd +B(s)Hˆp; s =tta; ta : anneal time (2.3)In its ideal closed-system form, the system goes through an “avoidedenergy-level crossing”, i.e., if the system is prepared in an eigenstate of Hˆ,it will remain in the corresponding energy-level eigenstate throughout theadiabatic (slow) evolution of the system.AQC is equivalent to the universal quantum circuit model, up to thepolynomial overhead of the circuit-to-Hamiltonian construction [4, 5]. How-ever, physical implementations of AQC, known as quantum annealers [83,86], are limited to the open-system dynamics and, therefore, have no guar-antee of finding the ground state, and are not designed for “universality”.Nonetheless, further discoveries in the theoretical foundations of AQC can5In practice, a slow time evolution corresponds to runtimes between 0.5− 2000µs [43].182.3. Quantum Annealing Processorsadvance the understanding and development of physical quantum anneal-ing devices, regardless of the qubit technology, topology, or Hamiltonianoperator.2.3 Quantum Annealing ProcessorsAs mentioned above, the principle of AQC does not depend on a specificHamiltonian operator. In practice, there are physical challenges in buildinga system with a complex Hamiltonian [83, 129]. For this reason the onlycommercial implementation of quantum annealing (so far), is the one fromD-Wave Systems Inc., which uses the device and programmable Hamiltoni-ans modelled by the expressions in Equation (2.4).Hˆd = −N∑iσˆ(i)x ; Hˆp =N∑ihiσˆ(i)z +∑⟨i,j⟩Jij σˆ(i)z σˆ(j)z (2.4)In this model, the state of the i-th qubit is acted on by the Pauli operatorsσˆ(i)α defined in Equation (2.5); where α is the operator basis, as seen inand (2.6), along with identity operator Iˆ.σˆ(i)α =i−1︷ ︸︸ ︷I ⊗ ...⊗ I ⊗ σˆαN−i︷ ︸︸ ︷⊗I ⊗ ...⊗ I; α = {x, y, z}; (2.5)σˆx =0 11 0 σˆy =0 -ii 0 σˆz =1 00 -1 Iˆ =1 00 1 (2.6)In its simplest form, the control parameters of the Hamiltonian Hˆd are192.3. Quantum Annealing Processorsset homogeneously on the x-basis; while Hˆp is parameterized by the linearh = [h0, . . . , hN−1] ∈ RN , and quadratic biases J = [Jij∀{i ∈ N, j ∈ N} :i ̸= j] ∈ RN×N on the computational z-basis. Physical implementationsallow more complex controls [3, 13, 166], which are briefly described inSection 2.4.4.Essentially, this describes a system that starts in a superposition ofall possible configurations, and “quantum-mechanically” evolves into theground-state configuration of an Ising Spin Graph model.Therefore, solving for the ground state of Hˆp is the same as finding theconfigurations with the lowest dimensionless energy E of the correspondingIsing model:E(s) =N∑i=1hisi +∑i<jJijsisj ; si ∈ {−1,+1}. (2.7)The origin of quantum annealing on the Ising model, as it exists today,is attributed to Kadowaki and Nishimori [86]. In 1999 D-Wave Systems Inc.was founded, and in 2011, the company launched its first commercial im-plementation of a QAP [83]; D-Wave remains the only organization offeringaccess to quantum annealing devices.Despite the focused nature of quantum annealing services and devices,there has been continuous research on this area. Contemporary work onQuantum Enhanced Optimization (QEO) has been funded by the Intelli-gence Advanced Research Projects Activity (IARPA), and led by the Uni-versity of Southern California (USC) until 2019 [127]. This has been con-tinued by the Defense Advanced Research Projects Agency (DARPA), now202.3. Quantum Annealing Processorsunder the Quantum Annealing Feasibility Study (QASF) project [38]. Also,in 2021, Qilimanjaro [32] announced their independent work on a full-stackquantum annealing solution and, in 2022, NEC Corporation announced earlyexperiments of a new technology for quantum annealing [122]. Other no-table mentions are the QC research groups from Los Alamos National Lab-oratory (LANL) [178], NASA’s Quantum Artificial Intelligence Laboratory(QuAIL) [121], and the Ju¨lich Supercomputing Centre (JSC) [85]; all ofwhich have access to D-Wave devices and have active research personnelworking on the topic of quantum annealing.The quantum annealing processors (QAPs) from D-Wave Systems Inc.use superconducting flux qubits. These are wires of superconducting mate-rial laid out as a loop and joined by a Josephson Junction (JJ) to create themeasurable phenomenon that distinguishes the two states of the system [73],i.e., the direction of the current on the loop. A transverse field controls Hˆd,while Hˆp is controlled by local longitudinal magnetic fields (for linear bi-ases), and the pairwise magnetic interactions between qubits (for quadraticbiases).As an example, D-Wave provides the energy curves in the annealingschedule of their devices [45]. Figure 2.1 is a plot made from the annealingschedule of the D-Wave Advantage System4.1. Energy values are providedin GHz vs. the annealing ratio s, and the temperature of the device TDWis provided as a reference in the same units of energy; where kB is theBoltzmann constant, and h is Planck’s constant.Superconducting qubits require an operating temperature close to abso-lute zero (e.g., TDW = 15.4mK for D-Wave’s Advantage System4.1). Despite212.3. Quantum Annealing ProcessorsFigure 2.1: Example of the annealing schedule relative to the physical tem-perature TDW = 15.4mK of the D-Wave Advantage System4.1. Graph cre-ated from data in [45].that, during the anneal, long annealing times ta expose the system to increas-ing thermal noise from the environment, which limits how “slow” the systemcan be evolved. Moreover, the existence of a small energy gap between theground state(s) and the next excited states increases the probability of atransition between these states. This lowers the probability of samplingfrom the ground state pGS. The energy-level transitions are governed by thenon-adiabatic level-crossings Landau-Zener effect [101, 183].In terms of performance, harder problems (with smaller energy gaps)will require longer run-times to obtain better solutions. As an example, thetime-to-solution (TTS) metric,TTS(ta) = talog(1− ptarget)log(1− pGS(ta)) , (2.8)222.3. Quantum Annealing Processorsuses the probability of finding the ground state pGS(ta) with a particularannealing time ta to measure the time it would take to obtain the groundstate with some certainty, e.g., ptarget = 0.99. As a result, these systems arerun through the annealing schedule multiple times (typically thousands oftimes) for each BQM.2.3.1 D-Wave TopologiesD-Wave quantum annealers consist of a collection of qubits connected usingcouplers. Due to manufacturing limitations, it is not possible to provide acoupler between each pair of qubits. Instead, qubits are connected in a pre-determined pattern. This limited connectivity between qubits is reminiscentof the interconnect network in Field-Programmable Gate Arrays (FPGA) orsystolic arrays.The topology of the fabric, which determines how qubits are directlyconnected to each other, is critical in the ability of a quantum annealer tosolve optimization problems. A good topology not only provides sufficientconnectivity, but also lends itself to systematic qubit mapping algorithmsthat are able to make effective use of the fabric. Initial proposals for suitabletopologies described sparse graphs created by interconnecting qubits in bi-partite subgraphs [34, 35]. One of the advantages of such a topology is thatit is easy to find cliques as minors of the graph; more details are providedin Section 2.4.2.The evolution of D-Wave architectures is shown in Figures 2.2 to 2.4.The Chimera topology, which is the result of replicating a simple 2D lay-out of overlapping superconducting wires [73], is shown in Figure 2.2. This232.3. Quantum Annealing ProcessorsFigure 2.2: Chimera [73] topology.topology divides the fabric into a grid of 8-qubit tiles; each tile is connectedto neighbouring tiles (lighter edges in the diagram). The diagram also illus-trates the symmetry of the graph which makes it evident how the patterncan be scaled to larger grids. A limitation of this topology is that it does notallow for any native clique minor-embeddings; that is, a minor-embeddingof K3 (fully connected graph of three nodes) will require at least four qubitsdue to the limited connectivity.The notation to refer to a graph of Chimera topology is C(m,n, t); wherethe graph is an m×n grid of tiles, and each tile is a Kt,t with t qubits oneach “shore” or side of the biclique. An 8 qubit tile has 4 qubits per shore.The lineup of Chimera topology D-Wave devices has had: D-Wave One(C(4, 4, 4)), D-Wave Two (C(8, 8, 4)), and D-Wave 2000Q (C(16, 16, 4)).The Pegasus topology, illustrated in Figure 2.3, was introduced in 2019,and expands the size of each basic tile to 24 qubits [27]. This topology can be242.3. Quantum Annealing ProcessorsFigure 2.3: Pegasus [27] topology.seen as a three-dimensional version of the Chimera graph, with depth three.The extra connectivity in this graph provides the ability to implement K3and K4 graphs (cliques with three and four nodes, respectively) withoutrequiring extra qubits. Note that due to physical limitations, some tiles arebuilt incomplete on the perimeter of the grid.The notation for the Pegasus topology is simplified to P(m), which de-scribes an m×m grid of tiles, with the number of qubits per “shore” fixedto 4; i.e., 12 per tile. At the time of writing, D-Wave’s Pegasus devicesare based on 16 × 16 graphs; i.e., the Advantage system4.1 and Advan-tage system6.3 are built on P(16) graphs.The Zephyr architecture, shown in Figure 2.4, was described in 2021, and252.3. Quantum Annealing ProcessorsFigure 2.4: Zephyr [89] topology.at the time of writing, is used in D-Wave’s most recent experimental pro-totype [89]. This topology closely resembles a higher qubit count Chimera(the basic tile size is expanded to 48 qubits) with added overlap betweentiles. As with the Pegasus topology, native K4 clique embeddings are pos-sible on this graph. The notation for the Zephyr graph is also simplified asZ(m), making an m×m grid of tiles, with fixed “shore” size fixed at 4. TheAdvantage2 prototype1.1 system uses a 4 × 4 grid; i.e., is built on a Z(4)graph.D-Wave’s online service supports devices spanning all three topologies [43].In this dissertation, our results in Chapter 3 were gathered on a device witha Chimera topology, and our results in Chapters 4 and 5 were gathered on262.4. QAP Programming Flowa device with a Pegasus topology. However, due to the manner in whichthe topologies are constructed, it is straightforward to translate our contri-butions in each chapter to a different topology; cf. Appendix A for moredetails. In general, we expect to see new topologies as quantum anneal-ers evolve, however, the fact that the qubits are connected using a limitedconnectivity graph is likely to persist. Therefore, the contributions in al-gorithms and evaluations described in this dissertation will remain relevantand important.2.4 QAP Programming FlowIn the same way that CPU and GPU compilers optimize, schedule, and al-locate instructions and memory resources, or the same way that hardwaredesign tools synthesize, map, place, and route logic elements, a quantum an-nealing processor must be accompanied by a computer-aided design (CAD)flow which maps a problem to the underlying architecture. Such a flow in-cludes (1) translating the problem into a Binary Quadratic Model (ProblemModelling), (2) mapping the problem onto the device’s qubit fabric (GraphEmbedding), (3) calculating the corresponding couplers and node biases(Parameter Setting), (4) selecting the annealing profile (Anneal Schedul-ing), and (5) resolving the qubit samples accumulated from the machineand translating these samples back to the solutions of the original prob-lem (Sample Resolution). Figure 2.5 shows the flow graphically, and thefollowing subsections describe each step in more detail.272.4. QAP Programming FlowFigure 2.5: The programming flow for QAPs.282.4. QAP Programming Flow2.4.1 Problem ModellingIn the first stage, the problem to be solved is converted into the energyfunction of a Hamiltonian suitable for optimization on the quantum an-nealer. This involves identifying variables in the problem, their interactions,and writing the problem using either an Ising Spin Graph (ISG or Isingmodel) or Quadratic Unconstrained Binary Optimization (QUBO) formula-tion. Correspondingly, Equations (2.9) and (2.10).E(s) =N∑i=1hisi +∑i<jJijsisj ; si ∈ {−1,+1}. (2.9)E(x) =N∑i=1hixi +∑i<jJijxixj ; xi ∈ {0, 1}. (2.10)In both quadratic models (ISG or QUBO), the quantum annealer willreturn samples that minimize the energy E(x) parameterized by the pro-grammable parameters h and J . Evidently, if a linear bias hi is negative, itsuggests that the corresponding variable xi should be +1 in the ISG (or 1for QUBO). Negative interactions Jij < 0 in the ISG, therefore, apply a biastowards the product xixj > 0, i.e., when both xi and xj have the same value(or a ferromagnetic interaction). Positive quadratic biases Jij > 0 suggestthat the two variables should be different. The transformation between ISGand QUBO is detailed in Section 2.4.3.Depending on the type of application, we distinguish between two prob-lem formulations. For optimization problems, an Ising or QUBO model canbe adjusted to include “penalty functions” to represent constraints, and the292.4. QAP Programming FlowQAP is used to find a low-energy configuration of all variables in the prob-lem. Used this way, quantum annealing is categorized as a metaheuristicbecause many optimization problems can efficiently be transformed into anIsing model [68, 107], and sampled to obtain low energy solutions. In thisformulation, the Ising or QUBO model is constructed such that the min-imum energy solution found by the quantum annealer represents the bestsolution of the original optimization problem.The second type of problem formulation is for sampling applications, inwhich the quantum annealer is used to obtain samples from a Boltzmanndistribution. The open-system dynamics of D-Wave QAPs has been, andcontinues to be thoroughly examined [6, 53, 113]; and has been shown ex-perimentally that there is a strong correlation between the native samples ofthe QAP (i.e., without minor-embedding), and a Boltzmann distribution, asdescribed by Equation (2.11) where βDW is a dimensionless scalar that en-capsulates all the sources of noise (e.g., physical temperature, quantizationnoise, etc.). More details on βDW are covered in Section 4.3.p(s)DW =e−βDWE(s)ZDW; ZDW =∑se−βDWE(s) (2.11)Because of this capability of QAPs to sample from a Boltzmann prob-ability mass function, a great body of work exists on using them to collectsamples for Boltzmann machines (BMs) [2, 18, 57, 58, 97, 102, 104, 172].BMs are probabilistic machine learning (ML) models, and their training al-gorithms (detailed in Chapter 4), use the approximation of the expectationvalue of each node to calculate the gradients of the trainable parameters.302.4. QAP Programming FlowFor sampling applications, it is still necessary to formulate the Boltzmannmachine as a collection of interacting variables, which can be fed to the QAPas in an optimization problem.Sampling formulations are also used for benchmarking against classicalsolutions [9, 50, 91, 93] because they offer more flexibility in the quality ofresults. No device has reached a level of fault-tolerance and decoherencetime that would allow running quantum algorithms or binary optimiza-tion at scales that clearly surpass the capabilities of classical computing.Therefore, NISQ devices, both gate and annealing model, are comparedagainst classical algorithms trying to replicate the sample distribution of arandomly-prepared quantum state.Other considerations in the problem formulation include (1) problempartitioning with hybrid classical-quantum methods to solve problems withlarger numbers of variables than what is available in the devices [14], (2)error correction methods through qubit redundancy [102, 145], and (3) em-ploying discrete quadratic models (DQM), among others. In this disserta-tion, we consider both optimization applications (Chapter 3) and samplingfor ML applications (Chapters 4 and 5).2.4.2 Graph EmbeddingThe logical problem, represented as a QUBO problem or Ising model, needsto be mapped onto the physical qubit topology of the QAP. In this section,we describe the graph embedding, or minor-embedding problem. Previouspublished algorithms are described in Section 2.5.Ideally, each variable in the problem formulation would be mapped to312.4. QAP Programming FlowFigure 2.6: Example demonstrating chains during embedding.a single qubit in the target QAP, and each interaction between variables inthe problem would be mapped to a physical coupler connecting the qubits.Such a straightforward mapping, however, is often not possible, due to thelimited connectivity in the QAP topology; as described in Section 2.3.1,the pattern of couplers between qubits on a QAP is sparse. The problemis further exacerbated by the fact that in QAPs, some qubits are typicallynon-functional and must be avoided.Therefore, it is often necessary to use multiple qubits to represent a sin-gle variable. When multiple connected qubits are used to represent a singlevariable, the set of these qubits is called a chain. Consider the simple exam-ple in Figure 2.6. The three connected squares on the left side of the figurerepresent the problem to be solved and the graph on the right represents thetarget QAP (only one tile is shown for clarity). In this problem, the threeuser variables (A, B, and C) are connected as a clique (K3), each variablehas an interaction with the other two. Mathematically, this means that inthe QUBO formulation, each term with two of these variables has a non-zerocoefficient. In this example, it is not possible to find a mapping in which322.4. QAP Programming Floweach variable is assigned exactly one qubit, due to the limited connectivityof the target graph. Instead, a valid solution is to create a chain, in thiscase using qubits 1 and 7 to implement variable C.Long chains are not desirable for at least four reasons; especially if thelengths of chains are imbalanced. First, using more than one qubit to rep-resent a variable limits the size of the problem that can be solved. Second,after annealing, when samples are obtained from the QAP, it is possiblethat qubits in the same chain have different values; in that case, these val-ues need to be resolved to a single value for the variable (this is describedfurther in 2.4.5). Third, couplers have limited resolution; this limits accu-racy, especially when the value that would normally be programmed for asingle qubit (or coupler between interacting qubits) is spread among multi-ple qubits (or couplers). Finally, during the anneal run, chains of differentlengths exhibit “freeze-out” (or vanishing of the quantum interactions) atdifferent times in the system evolution [3, 13, 134]. For all these reasons, animportant goal of an embedding algorithm is to reduce the number of extraqubits required to implement chains.More formally, the mapping of a problem graph G = {P,E}, with nodesP and edges E, onto a graph representing the QAP topology (the devicegraph) H = {Q,C}, with qubits Q and couplers C, can be formulated as aminor-embedding problem [31]. A graph G is a minor of H if G is isomorphicto a graph obtained from a subgraph of H by successively contracting edges.Finding an optimal embedding that reduces the number of extra qubits isNP-Hard [31], so heuristic methods are required for medium and large prob-lem sizes. Although a given device has a fixed H, the dimension, topology,332.4. QAP Programming Flowand connectivity of the target graph grows with new generations of quan-tum annealing machines and, due to manufacturing limitations, some qubitsin the QAP graph may not be functional. Therefore, the problem shouldconsider both G and H as inputs.After mapping, the effective energy Eeff function implemented by theQAP is shown in (2.12). This formulation shows the impact of qubits chains,which occur whenever two neighbouring nodes have been mapped to qubitsthat do not share a coupler, or when the degree of the node is higher thanthe degree of the qubit. In the resulting embedding, each variable is mappedto a chain of qubits Qi = {s(k)i |k ∈ [1, λi]} where s(k)i is the kth physicalqubit used by the variable i, and λi is the length of the chain.Eeff(s) =N∑iλi∑khiλis(k)i +∑i<jλi∑kλj∑lJijκijs(k)i s(l)j −JFMN∑i∑k<ls(k)i s(l)i (2.12)For each pair of nodes (i and j) in the problem graph, the numberof interactions κij (or connectivity), is the number of couplers shared be-tween qubit chains Qi and Qj ; also interpretable as the size of the cut-set{(k, l) ∈ Cij |k ∈ Qi, l ∈ Qj}. Linear biases hi are split by the chain length;and qubits within chains are connected using a “strong” ferromagnetic cou-pling JFM, also called chain strength. Quadratic biases Jij are split by thenumber of interactions λi.As described above, long and imbalanced chains are detrimental to theQAP performance. Samples from a QAP may return results with “bro-ken chains”, which are mismatched physical qubits for the same variable.342.4. QAP Programming FlowThe chain break method of choice, to determine the sample value of i froma broken chain, is the majority vote with random tiebreaker [2, 19, 146];si = sign(∑λik s(k)i). Having larger λi and κij may also increase the resolu-tion required for the parameters to represent the problem, which is undesir-able [34, 69].2.4.3 Parameter SettingIn the Parameter Setting stage, the values for several programmable param-eters are determined, and the QAP is configured using these parameters.This stage includes the following tasks: (a) translate QUBO representationto an Ising representation, if necessary, (b) perform gauge transformations,(c) determine the linear bias values h for all qubits and determine couplervalues J for all qubit-to-qubit interactions, including the interactions be-tween qubits within the same chain, and (d) scale parameters to a rangesupported by the device. Each of these will be described below. Althoughsome of these transformations are straightforward, they are important to re-view in order to appreciate the challenges encountered creating our QAMLframework in Chapter 4.As described above, when modelling a problem, it is possible to useeither a QUBO formulation, in which each variable can take on a value 0 or1, or an Ising formulation, in which each variable can take on the values -1or 1. Since the QAP natively solves an Ising problem, if the problem wasformulated as a QUBO problem, the first step is to convert this to an Isingrepresentation, using:352.4. QAP Programming Flowhi =bi2+∑jWij4; J =W4(2.13)s = 2x− 1; C =∑i hi2+∑i,jJ4(2.14)where s is the spin-value vector given binary vector x, and C is a constantthat only offsets the energy values, and can be ignored.Optionally, the second step is to perform gauge transformations [13, 136].In these transformations, the signs of selected variables are flipped to com-pensate for bias noise on the qubits. These parameters can be selectedrandomly or systematically [2]. If the sign of a qubit or chain in the embed-ded problem corresponds to a flipped variables , then it will be necessary toflip its value back during Sample Resolution (described in Section 2.4.5) tomatch the original problem formulation.The third step is to determine linear bias values h for all qubits andcoupler values J for all qubit-to-qubit interactions. These can be takendirectly from the original problem formulation. Special consideration isnecessary for couplers that connect qubits within the same chain; in this case,the J value in the embedded problem should be as large as possible to biassolutions to those in which all qubits in a chain have the same value. Thislarge value, JFM, is referred to as the chain strength. Simple chain-strengthsetting methods based on auto-scaling of the other parameters have been thede-facto approach from D-Wave. Recent developments include the conceptof “torque”, which introduce compensation methods, either systematic orheuristic [149]. In some cases, chains can cause additional interactions as362.4. QAP Programming FlowFigure 2.7: Example demonstrating coupler strengths after embedding.shown in the example of Figure 2.7. In this example, the original problem(left) consists of three variables. The problem has been embedded onto 7qubits: variable A is mapped to qubit 1, variable B is mapped to a chainconsisting of qubits 2, 3, 4, and 5, and variable C is mapped to a chainconsisting of qubits 6 and 7. As can be seen the interaction between 1 and 2is taken directly from the problem, and the interactions within each chain isset to JFM as described above. The edge between B and C, however, has beensplit across two interactions. In such cases, it is necessary to apportion thevalue of JBC across multiple couplers. In the current D-Wave software, thisapportion is done evenly across all interactions that are available betweenchains, however, other strategies are possible.The fourth step is to scale parameters to a range supported by the device.In optimization applications, and as a default operational characteristic ofD-Wave QAPs, the parameters of the problem can be automatically scaled(auto scale=True) when submitted. The scaling factor α to fit an arbitrary372.4. QAP Programming FlowIsing model onto the available range is the following:α = max[max(max(h)max(hrange), 0),max(min(h)min(hrange), 0),max(max(J)max(Jrange), 0),max(min(J)min(Jrange), 0)](2.15)As an example, the D-Wave “Advantage system4.1” QAP system offers alinear bias range hrange = [−4.0, 4.0], and a quadratic bias range Jrange =[−1.0, 1.0]. Ideally, JFM should have a relatively strong value compared toany Jij , which is why D-Wave devices also feature an “extended” Jrange =[−2.0, 1.0].This step also requires quantizing the parameter values due to the resolu-tion limits of the QAP. As a result of these discrete ranges, the programmedvalues are subject to quantization noise; the scale and range of those valuesare consequential in the quality of the sample distribution collected from thedevice.Quantization errors, and therefore, parameter scaling, will continue tobe a part of the QAP programming flow in the future; as well as withany quantum computing platform. This is due to the nature of quantumtechnologies, wherein, a field or voltage is used to apply biases that controlcurrent directions or placing a charge in the underlying quantum mechanicalsystem.In sampling applications, such as in BM training, this setting is typicallyturned off (auto scale=False) to provide control over the scale of the parameters,as will be shown in Section 4.4.382.4. QAP Programming Flow2.4.4 Anneal SchedulingBefore running the QAP, it is necessary to determine the parameters de-scribing the anneal schedule, which goes beyond setting the anneal time ta.Although default parameters are provided, as in Figure 2.1, D-Wave’s QAPsprovide the ability to over-ride this schedule and select an anneal profile, andper-qubit anneal offsets.The anneal profile defines the pausing points, pause duration, and di-rections of A(s) and B(s) over time. For example, it is possible in currentgeneration D-Wave machines to pause the anneal at values of s, effectivelyallowing for a thermalization of the system [113]; and/or perform reverseannealing, and quenching, the latter being an abrupt termination of theanneal in a short time [3, 13, 166].The timing details of each call to a quantum annealing device are deter-mined by the annealing time ta, the number of reads N , and time spent onoperational functions of the device.As an example, Figure 2.8 shows the timing details for 100 reads atta = 20µs, with 4 spin reversal transformations (400 anneal runs). Thisis a typical call to the sampling function. Effectively, this means that thedevice is programmed 4 times, with some parameters “reversed” to de-noisethe samples. The programming (∼ 27ms) and anneal (∼ 18ms) times aresimilar for all calls, while the overhead ranges from 1.5−3.5ms, which is anyother time spent on initialization. These 4 sampling calls amount to 170msof “access time”, which is the cumulative time used by D-Wave to bill itsusers, without counting the access overhead.392.4. QAP Programming FlowFigure 2.8: Timing diagram for each QPU call. Each call uses a spin reversaltransformation.Figure 2.9 represents the time breakdown during each call to the device.Interestingly, the time of the anneal (ta = 20µs) is relatively short comparedto the readout time. Additionally, a programmable “cooling” or delay timeper sample is needed to avoid having noise caused by the readout circuitryto interfere in the next sample. The sum of the 100 reads with readout anddelay times, amount to the sampling time in Figure 2.8.Figure 2.9: Timing diagram breakdown of the sampling time.The availability of quantum computing devices to this day is scarce, andresearchers rely on shared cloud-enabled devices. This means that a more402.4. QAP Programming Flowaccurate “wall-clock time” breakdown also includes the communication andqueuing time.2.4.5 Sample ResolutionThis final step is to interpret the values from the physical qubits after theannealing is complete, and use these values to determine the solution tothe original optimization problem. For most applications, the annealing isperformed many times, and each annealing run produces one sample; eachsample contains one spin value for each qubit. If the embedding containsmultiple qubits to represent a user variable, it is possible that differentqubits in a chain may have different values, and it is necessary to resolvethese values to obtain a value for the user variable. There are a number ofmethods, called chain break methods to perform this resolution. D-Wave,at the time of writing, provides several methods, including majority vote,weighted random, discard, and minimize energy [47]. The best method touse depends on the application.More advanced chain break methods or “unembedding” techniques, asfound in [133], bring in awareness of the problem to be solved. This has beenfound to result in better performance for specific graph theoretic optimiza-tion problems, by making the “unembedding” a part of the optimizationloop. A similar approach has been taken by D-Wave through the use ofpost-processing passes. An optimization post-processing pass, and a sam-pling post-processing pass are available to either perform local minimizationon partitions of the problem graph, or adjust the solutions on those samepartitions to achieve a target βeff of a Boltzmann distribution [41]. No post-412.5. Related work on Minor-Embedding for QAPsprocessing or hybrid optimization methods are used in this work in order toevaluate the “raw” performance of the QAP hardware.2.5 Related work on Minor-Embedding for QAPsBecause the focus of this thesis is on minor-embedding methods, this sectionpresents notable algorithms that have been developed with the goal of map-ping QUBO problems onto QAPs. These can be classified into two differentcategories: systematic and heuristic methods.2.5.1 SystematicThe design of the Chimera graph was made such that the minor-embeddingof a clique with homogeneous chains is known; such a graph is known as aminor-universal graph [35]. Over time, new methods have been developedto work around qubit faults and to adapt to new architectures [28, 95, 181].Aside from cliques, other problem graphs can make use of systematic ap-proaches for minor-embedding. For example, bicliques [2, 27, 89], and threedimensional lattices [74, 89] can be embedded in polynomial time. Moreover,given a device’s adjacency graph (accounting for missing qubits), it is pos-sible to build a minor-embedding cache, e.g., addressed by the dimensionsof the graph [48].In the presence of qubit faults, these methods may not guarantee findingthe most resource efficient mappings (i.e., fewer qubits) but, instead, aredesigned to be efficient in run-time, have balanced chain lengths, and toprovide (limited) adaptability to faults.422.5. Related work on Minor-Embedding for QAPsThe most illustrative example is the minor-embedding of a biclique ontothe Chimera graph, as depicted in Figure 2.10 for a K12,12 graph. A colouris assigned to each side of the biclique, and each chain is assigned the indexof a node. One side of the bipartite graph is mapped onto columns of qubits,and the other to rows. In order to extend these capabilities to Pegasus andZephyr graphs, the implementation of these algorithms in [48] transformsthe coordinates of the qubits to an equivalent Chimera family graph; e.g., aChimera C(3, 3, 8) contains a Zephyr Z(1) graph [89]. The minor-embeddingis found systematically on the Chimera graph, and converted into the cor-responding topology.Figure 2.10: Systematic K12,12 onto Chimera C(3, 3, 4).432.5. Related work on Minor-Embedding for QAPsFigures 2.11 and 2.5.1 are examples of the same K12,12 minor-embeddedonto Pegasus and Zephyr. More details on the graph transformations areshown in Appendix A.Figure 2.11: Systematic K12,12 onto Pegasus P(3).Despite their run-time efficiency, systematic methods have two weak-nesses: First, in the presence of qubit faults, these methods do not guaranteefinding the most resource efficient mappings (i.e., fewer qubits). Second, to442.5. Related work on Minor-Embedding for QAPsfind the minor-embedding of other topologies, for which there is no special-ized systematic method, the simplest approach is to assign each node to aclique minor-embedding chain and ignore the unused interactions, which isvery inefficient for sparse graphs.Figure 2.12: Systematic K12,12 onto Zephyr Z(2).The minor-embedding method for cliques introduces a bend in the chains452.5. Related work on Minor-Embedding for QAPsto realize the full connectivity [28]. Figure 2.5.1 depicts the systematic K12clique embedding onto a Chimera C(3, 3, 4) graph. Each colour represents adifferent chain.Figure 2.13: Systematic K12 onto Chimera C(3, 3, 4).As opposed to the biclique method, the location of these L-shaped chainscan be initialized at random, and/or rotated and mirrored around the qubitfabric. This introduces a randomness to the result, which is used in the pres-ence of faults. Pegasus and Zephyr graphs use the Chimera representation,as described for the biclique method.In the D-Wave CAD flow, this is the method used for large problems thatare known not to fit onto one device graph. Hybrid quantum-classical meth-ods [49], perform (1) partitioning, (2) minor-embedding of each partition,462.5. Related work on Minor-Embedding for QAPsand (3) classical methods to combine the sub-solutions into a solution of thewhole problem. This allows for a quick assignment of nodes to chains, butcompromises on the quality of the minor-embedding which may not requirefull connectivity. This may impact the sample quality. Other methods havebeen proposed to maximize the size of each partition that can be minor-embedded [1, 14, 128]. However, to our knowledge, these are not part ofD-Wave’s default programming flow.2.5.2 HeuristicMost optimization problems do not have a characteristic topology with aknown efficient minor-embedding method. Moreover, both the problem andthe device graphs are input variables to the minor-embedding problem. Aspreviously mentioned, each new device may have disabled qubits throughoutthe qubit fabric, which often force the systematic methods to adapt andmake choices in the algorithm that may not be optimal [95]. For those twoscenarios (i.e., generic topologies and adaption to faults), it is necessary touse heuristics, optimizing for a minimum total number of qubits.Typically, these methods use a path-search heuristic, similar to that ofthe negotiated-congestion algorithm [120], which is an industry standard inCAD tools for digital design (e.g., ASIC and FPGA [115]). Negotiated-congestion is an iterative approach of mapping and remapping elements(i.e., QUBO nodes, or Ising spin sites) onto resources (one or more qubits),starting from a random assignment [31, 165] or from an initial placement [23–25, 142, 153, 163, 164, 182], gradually removing overlapping assignments.Unlike algorithms targeting ASICs and FPGAs, qubits in a QAP are used472.5. Related work on Minor-Embedding for QAPsfor both “logic” and “routing”.D-Wave’s minorminer:The method in [31] is the current D-Wave standard, hosted on the open-source repository called minorminer [48]. This is a high-performance C++implementation, which also includes methods for initial placement [142, 182].The minorminer algorithm is wrapped in a Python package and built forintegration with the rest of the D-Wave framework [47].At its core, the algorithm loops over every node, assigning the node toa random qubit if none of their neighbours have been mapped, or findingthe “minimal vertex model”, i.e., the lowest cost chain that has at leastone edge with each chain of the neighbouring nodes. The cost of a chain isdetermined by the distance and occupancy of each qubit at that iteration.One important feature of this (and any negotiated-congestion) approach,is that the choices during mapping are made using a weighted-random se-lection, which ensures the algorithm does not suffer from cyclic behaviour.The pseudocode in Algorithm 2.1 describes the main steps of a path-searchheuristic like minorminer. The implementation details and improvementsmade in minorminer can be found in the open-source repository [48] or itsfoundational paper [31].With every new architecture, the minorminer package has been testedon three metrics [27, 89]: Average chain lengthℓ(G,H) = 1tt∑i=11|G|∑c∈A(G,H)|c|, (2.16)482.5. Related work on Minor-Embedding for QAPsmaximum chain lengthL(G,H) = 1tt∑i=1maxc∈A(G,H)|c|, (2.17)and average run-time τ(G,H). In these equations, the problem graph G isminor-embedded t times with algorithmA onto the target graphH, resultingin chains c.Algorithm 2.1: Path-search heuristic example.Input: Source Graph (G), Target Graph (H)Output: Minor-Embedding E = {g : c ∀ g ∈ G} or {}1 Init E = {g : [ ] ∀ g ∈ G}2 Init N (g) = neighbours of g ∀ g ∈ G3 while L(G,H) or ℓ(G,H) is improving do/* ====== Randomly iterate over every node ====== */4 for g ∈ randomize(G) do/* ====== Update weights of local paths ====== */5 h = = multisource A∗(N (g), E[g],H)/* == Select root from qubits in local paths == */6 h∗ = choose with probability exp−cost(h)/* ===== Assign new chain to source node ===== */7 E[g] = {h∗} ∪ {paths from E to eachE[N (})]}8 if no overlap(E) then return E;9 else return {};Even though a significant improvement was possible between the Chimera492.5. Related work on Minor-Embedding for QAPsand Pegasus architectures (50-60% in chain length) due to the increase inqubit connectivity [27], the jump from Pegasus to Zephyr is only expected tohave a 2-10% improvement in run-time and chain length [89]. This highlightsthe importance of a co-design between new architectures without relying ona single generic global heuristic.Dense Placement:The work in [152] proposes an algorithm that: (1) densely places connectednodes, starting from a random node positioned at the centre of the qubitfabric, and (2) introduces the concept of “opening seams” in the graph everytime a new neighbour needs to be mapped, but all connections are exhausted.This method performs well for its target application of Quantum-dot Cellu-lar Automata (QCA). However, minorminer outperforms this approach inmost scenarios. QCA circuits were used to benchmark the contribution inChapter 3.Place & Route:Place & Route methods make use of “local” strategies, by fixing subsets ofthe problem graph, e.g., terms in constraint satisfaction problems (CSP),followed by a routing stage connecting those subgraphs [23–25, 163, 164].This is different from the “global” path-search heuristic used in minorminer,in which all nodes are ripped and rerouted in each iteration. This approachcan use optimally embedded subgraphs, but results in very long chains con-necting the subgraphs.502.6. SummarySimulated Annealing placement:One heuristic approach used Simulated Annealing instead of the path-searchheuristics [165]. The algorithm first assigns each node randomly to a chainthat spans a predefined set of qubits. Then, with a simulated annealingschedule (i.e. initially accepting more random moves and progressively low-ering the “temperature”) it performs three types of moves: swap chain as-signments, shifts along the chain axis (elongate), and shifts away from thechain axis (branch). It was demonstrated for very sparse graphs, so it ispossible that it has a particular area in which it is efficient, but just like theother algorithms, minorminer outperforms it in most scenarios.2.6 SummaryDevelopments in quantum computing are motivated by potential speedupsin many applications, including machine learning. QAPs are a specializedtype of quantum computing device, which are easier to scale compared toother quantum devices, regardless of the underlying technology.With the growing capabilities and architectural complexity of QAPs, it isimportant to develop the programming tools in tandem with the technology.As part of the programming flow for QAPs, it is required to map eachvariable in the problem formulation onto qubits; this task is also known asminor-embedding.This dissertation describes our contributions in context-aware minor-embedding algorithms, with the perspective that a QAP is only as good asthe software stack used to program it. Contextual information, or informa-512.6. Summarytion related to the problem graph is used to inform the minor-embeddingalgorithms, in order to improve resource utilization and performance of theQAPs.52Chapter 3Context-Awareness: LayoutInformationThis chapter presents and evaluates our context-aware minor-embedding al-gorithms that leverage the input graph locality as expressed in a 2D layout.Our key observation is that the input to many minor-embedding problemshas relative location information inherent in the problem description, yet thisinformation is not typically used by existing heuristics. Using this locationinformation to guide the embedding, we show that we can obtain better em-bedding results with respect to a layout-agnostic approach. Even if locationinformation is not available, we show that we can use a pre-processing stepto estimate relative location information, and use that information duringembedding. Our approach is applicable to any QUBO or Ising-formulatedproblem.This chapter is organized as follows. Section 3.1 motivates our approachby describing examples which can benefit from it. Our overall algorithms arepresented in Section 3.2, and the approach is evaluated in Section 3.3. Thechapter ends with a summary and discussion and generality of the approachin Section 3.4.533.1. Motivating Examples3.1 Motivating ExamplesFor many problems, nodes in the problem graph may have natural locationinformation that can be deduced by understanding how the graph is createdfrom the problem instance. In other cases, it can be artificially generatedusing graph drawing heuristics. In this section, we present examples toillustrate the types of problems that may be suitable for our technique.3.1.1 Antenna SelectionA simple example of an optimization problem that has an intuitive mappingto a QUBO, and has innate topological location information, is the antennaselection problem. Figure 3.1 depicts a toy example of five antennas withequal coverage (diameter of each circle). The antenna selection problemassigns a value 1 or 0, respectively, indicating whether we should build ornot build each antenna, such that the interference (overlap) is reduced. Morecomplex versions of this problem exist, e.g., using the amount of overlap oradding a constraint in the number of antennas to the optimization goal.Figure 3.1: The antenna interference problem with its QUBO formulation.543.1. Motivating ExamplesConverting this problem into a QUBO is done by assigning a negativebias to all nodes, with the goal of maximizing coverage (i.e., minimizingthe objective function), and minimizing interference (i.e., constrained bypositive weights between interfering antennas). This is shown in Figure 3.1.The graph on the right side of Figure 3.1 represents a QUBO problem,and contains sufficient information for an existing minor-embedding algo-rithm (such as the D-Wave minorminer algorithm described in Chapter 2)to find a valid embedding. However, we observe that in this example, the lo-cations of the potential antenna sites are known, but this information is notused by the existing embedding algorithm. Such information may providevaluable information to help find a good embedding. In our approach in thischapter, we use this additional Euclidian location information (in this case,location of the potential antenna sites) to guide the algorithm.3.1.2 Quantum-dot Cellular Automata (QCA)A second example (and the problem that motivated this work) is the effi-cient minor-embedding models of Quantum-dot Cellular Automata (QCA)circuits to simulate their behaviour using D-Wave’s QAPs. QCA [77] is afield-based computing technology based on the polarization of QCA cells,where the geometry of the design determines the polarity of each cell. EachQCA cell, disregarding the physical implementation, can be represented byfour quantum dots and two moving charges interacting due to Coulombicrepulsion. Therefore, a QCA cell can have state |0⟩ with polarization −1when charges are in the anti-diagonal[ ◦ •• ◦ ] , or state |1⟩ with polarization+1 when charges are in the diagonal[ • ◦◦ • ] dots. Interactions between cells553.1. Motivating Examplescauses each local configuration to propagate to neighbouring cells. QCA cir-cuits are typically designed using layout-level tools (e.g. [175]), which makesthem especially interesting for the layout-aware algorithm.FMAFM(a)(b)(c)(d)Figure 3.2: QCA components and circuits.Figure 3.2 shows an example QCA circuit and representation. Thisexample includes: (a) QCA wire and inverter showing ferromagnetic andanti-ferromagnetic coupling, where the “kink” energy Ei,jk depends on thelocations rin and charges qin at dot n of cell i, and the free space and relativepermitivities, ε0 and εr; (b) QCA majority voter; (c) QCA fault tolerantNOT gate, titled QCA NOTFT in Table 3.1; (d) Ising or QUBO modelgraph of the QCA NOTFT with a threshold in adjacency ra,b < 2.5, andwhere the driver cell is replaced by the Ei,dk biases.In QCA simulation, the problem being solved for each circuit is to find563.1. Motivating Examplesthe solution of the complete quantum mechanical formulation required tosimulate cell-to-cell interactions, as given by the two-state approximation inEquation (3.1).Hˆ = −N∑i=1γiσˆx(i)− 12∑i<jEi,jk σˆz(i)σˆz(j) +12∑dN∑i=1Ei,dk Pdσˆz(i) (3.1)The three terms in Equation (3.1) account for: the kinetic energy ofmoving charges in the cells, the energy due to the geometry of neighbouringcells, and the energy due to driver cells. Here, γi is the effective tunnellingenergy used to control the “activation” of cells, Pd is the polarization ofdriver cell d, and Ea,bk is the “kink” energy; or the energy required to changethe cell’s polarization as a function of its proximity to other cells. Whenparsing the QCA layout, Ea,bk becomes negligible for distances greater thanthe span of a few cells due to Ea,bk ∝ r−5a,b ; where ra,b is the distance betweena and b. These models of the adjacency between cells use a threshold forra,b < 2.5 to produce non-planar graphs.Favourably, there is a direct mapping from QCA cells to nodes in an Isingor QUBO model, and from the QCA tunnelling energy to the transverseenergy of the QAP [152]. After embedding once, the QCA model can besimulated for different test vectors by changing the biases associated to thedriver cells. This direct mapping, along with recent developments in QCAtechnology [77], are an opportunity for the use of a layout-aware embeddingapproach.573.2. Layout-Aware Minor-Embedding Methods3.1.3 Artificial Location InformationLayout-awareness for the minor-embedding heuristic is not limited to theexamples above, nor to problems with natural location information. Thisis because it is possible to artificially create a layout that also conveys thelocality information that is responsible for the benefits obtained by usingthis algorithm. For graphs with lower density than a clique, a non-optimalspring-layout [65] drawing algorithm may be able to create a mapping ofnodes to 2D coordinates that is useful for a layout-aware minor-embeddingmethod. For planar graphs, an optimal graph drawing algorithm with lineartime complexity [36] could also be used to improve run-time.3.2 Layout-Aware Minor-Embedding MethodsOur approach consists of two stages: global placement and detailed routing.During the first stage, each node p ∈ P is matched with a set of candidatequbits Qp ⊂ Q. For D-Wave’s 2000Q QAP, these candidates are assignedto the 8 qubits in tile j, k of the Chimera graph; or the respective buildingblocks for Pegasus and Zephyr. Then, a routing algorithm for each nodefinds a qubit or chain of qubits guided by the initial candidate assignment.We present two routing methods, both based on negotiated congestion. Thefirst method is the Disperse router, as detailed in Section 3.2.2, while thesecond method in Section 3.2.3 employs the routing approach describedin [31].583.2. Layout-Aware Minor-Embedding MethodsAlgorithm 3.1: Layout-aware minor-embedding.Input: S: Source Graph, T: Target Graph, (Optional) L: Source LocationOutput: E: Embedding/* ====== Artificial Layout ===== */1 if not L then2 L← spring layout(S)/* ====== Global Placement ===== */3 candidates← diffusion(S, T, L)/* ====== Detailed Routing ===== */4 E ← minorminer(S, T, initial mapping = candidates)3.2.1 Global PlacementThe global placement stage uses each node’s location in the problem layout(xp, yp) and the grid size of the target Chimera (N,M), to superimposea stretched out geometry (x′p, y′p) of the problem on top of the Chimeratiles grid. The qubits in tile (jp, kp) are assigned as candidates for node p;jp = ⌊x′p⌋ and kp = ⌊y′p⌋.Although a routing guided by this initial placement may result in avalid solution, stretching will lead to long chains connecting distant nodes.Usually, down-scaling the superimposed layout is enough to meet a targetconcentration (dj,k =Pj,kSj,k), given as the number of problem nodes mappedto a tile Pj,k, over that tile’s supply of functional qubits Sj,k; the latter isto account for qubit yield. A down-scaled candidate assignment for a graphlayout is shown in Figure 3.3a. The input problem graph is the Ising modelof the layout in the inset; see Section 3.1 for details. In that figure, eachcolour corresponds to qubits in the same tile occupied by one or more nodes;overlapping candidates are allowed.At this stage, the algorithm transforms the initial placement to meet593.2. Layout-Aware Minor-Embedding MethodsAlgorithm 3.2: Diffusion-based migration.Input: S: Source Graph, T: Target Graph, L: Source LocationOutput: C: Candidates/* ====== Stretch ===== */1 N,M = dimensions(T )2 for (xp, yp) ∈ L do3 (x′p, y′p)← stretch(xp, yp, N,M)/* ====== Migrate ===== */4 migrate = True5 tiling = {p : [] ∀ p ∈ S}6 (cx, cy) = (N/2,M/2)7 while migrate do8 for p, (xp, yp) ∈ S,L do9 (jp, kp)← (⌊xp⌋, ⌊yp⌋)10 tiling(jp, kp)← p11 distaccum ← 012 for tilej,k ∈ tiling do13 (gradj , gradk) = gradient(tiling, tilej,k)14 for p ∈ tilej,k do15 (x′p, y′p)← (x′p, y′p) + (gradj , gradk)16 distaccum ← distaccum + (x′p − cx)2 + (y′p − cy)217 migrate = condition(distaccum)18 C = assign candidates(L′)two objectives: (1) spread nodes out of overpopulated regions (diffusion) toensure that the demand for each tile Pj,k does not exceed the supply Sj,k;and (2) migrate nodes from sparsely populated regions into denser regions(compaction) in order to improve resource utilization. A diffusion-basedmethod is appealing because it is a heuristic where each step is O(|P|); |P|being the size of the input problem. Layout-aware algorithms, however, arenot constrained to the use of this method for layout transformations.603.2. Layout-Aware Minor-Embedding Methods(a) Global Placement with highlighted candidates for aQCA layout.ACDBE0:0 1:00:1 1:1 d1,1 = 0.125d0,0 = 0.125d0,1 = 0.0d1,0 = 0.375(b) Global Placement with final tileconcentrations dj,k.0:0 1:00:1 1:1WXYVAE(c) Detailed Routing with highlightedshortest path A to E.Figure 3.3: Layout-aware embedding flow.Diffusion-Based MigrationThe concept of diffusion, in the context of CAD tools (e.g., VLSI and FPGAplacement [10, 108, 151]), is borrowed from the process in molecular dynam-613.2. Layout-Aware Minor-Embedding Methodsics in which molecules move from regions with high concentration to regionswith low concentration. Each molecule/node moves over time (∂dx,y∂t ) pro-portionally to the local curvature of the concentration gradient, and thediffusivity of the medium D. In Equation (3.2) D is defined as the over-all density of the embedding multiplied by an expected occupancy α, orthe number of qubits expected to be used per problem node; for practicalpurposes α = 3. The choice of D causes higher migration for low globaldensities, and lower migration when there is limited qubit availability.∂dx,y∂t= D∇2dx,y; D = 1− α|P ||Q| ; α = 3 (3.2)Diffusion can be achieved by applying a velocity field which, in thespace discretized by the Chimera tiles, translates to the equations in (3.3),dependent on the concentration in each tile and its neighbours, at discretizedtime step n; where t = n∆t and a choice of ∆t = 0.2.vXj,k(n) = −dj+,k(n)− dj−,k(n)2dj,k(n); vYj,k(n) = −dj,k+(n)− dj,k−(n)2dj,k(n)(3.3)Compaction is achieved by forcing the migration of nodes to the cen-tre of the tile grid using a modified velocity field v′j,k(n). To do this, inEquation (3.4), one of the concentration terms is replaced with a high con-centration using a node limit PLIM = 6 over the Maximum supply SMAX = 8,while the other term is replaced with the concentration at the “attractor”tiles; or the concentrations at the neighbouring tiles of (j, k) that are hor-izontally (dh), vertically (dv), and oblique (do) towards the centre of the623.2. Layout-Aware Minor-Embedding Methodsgrid.v′Xj,k(n) = −PLIMSMAX− (dh(n) + do2 (n))2dj,k(n)v′Yj,k(n) = −PLIMSMAX− (dv(n) + do2 (n))2dj,k(n)(3.4)This gradient will have the direction relative to the “attractor” tiles.Equation (3.5) uses the x and y components of the distance from the centreof the grid lX,Yp , in order to translate the gradient into an absolute valueand assign it to a specific node. Each node in a tile moves differently.vXp (n) = lXp (n)v′Xj,k(n); vYp (n) = lYp (n)v′Yj,k(n)lXp (n) =2xp(n)N− 1; lYp (n) =2yp(n)M− 1(3.5)Lastly, Equation (3.6) incorporates the velocity and diffusivity to calcu-late each node’s placement at the next time step. The algorithm iteratesuntil the dispersion, or average distance of the cells from the centre of thetile array, increases or has a cumulative variance lower than a predefinedthreshold.xp(n+ 1) = xp(n) +DvXp (n)∆t yp(n+ 1) = yp(n) +DvYp (n)∆t (3.6)As a result, the set of candidates Qp is given by the qubits in tile (jp =⌊xp⌋, kp = ⌊yp⌋) at the final iteration. Qp can be expanded to neighbouringtiles or reduced to specific qubits in each tile. As an example, Figure 3.3bshows a global placement for a graph with nodes P = {A,B,C,D,E}. In633.2. Layout-Aware Minor-Embedding Methodsit, the candidate qubits for node A are all the functional qubits in tile (0, 0),while the candidate qubits for E are all the functional qubits in tile (1, 1).3.2.2 Disperse RouterThe Disperse router starts by creating a Routing graph F in which the nodesP from the problem graph (G = {P,E}) are connected to the Chimera graph(H = {Q,C}), by adding edges from each node p ∈ P to the candidatequbitsQp. Figure 3.3c shows a subgraph of a Routing Graph F with problemnodes A and E connected to their corresponding candidates. The adjacencyof G is used to formulate a series of minimal Steiner tree problems. The goalis to iteratively solve for the minimal Steiner tree between p and the unroutedneighbouring nodes N (p) in G, through the qubit nodes in F . Using thenegotiated congestion routing algorithm described below, Figure 3.3c showsa shortest path from nodes A to E through graph F which passes throughfour qubits (V , W , X, and Y ).This work uses the negotiated-congestion scheme, which is widely usedfor FPGA routing [115], in which overlap of resources is initially allowed butthe costs of using each qubit is recalculated until a legal solution is found.A solution is legal when the occupancy of the qubits do not have conflicts.The cost of using one qubit cq = bqsqhq is defined such that it depends ona base cost bq, a present-sharing cost sq, and a historical-sharing cost hq.The base cost bq, given in Equation (3.7), is calculated using the degree ∆qof a node in relation to the maximum degree ∆MAX, and the scope cost ςq,which favours qubits inside the same tile over those in neighbouring tiles.643.2. Layout-Aware Minor-Embedding Methodsbq = 1 +(1− ∆q∆MAX)+ ςq; ςq =0 if intra0.2 if inter(3.7)sq(n) = 1 + δsnkq(n); hq(n) = hq(n− 1) + δhkq(n); hq(0) = 1 (3.8)The congestion costs sq and hq, defined in Equation (3.8), depend on therouter iteration n, the respective cost steps δp and δh, and the present qubitoccupancy kq(n). This also ensures that no paths between source and sinkpass through only one qubit. For each path, the qubit closest to the root isassigned to the root node, and the qubit closest to the sink is occupied bythe sink node. In Figure 3.3c, qubit V is assigned to node A, and qubit Y isassigned to node E. Qubits in between the source and sink (W , X, and Yin Figure 3.3c) can be assigned to either the source or sink. Initially thesenodes are labelled as unassigned. During routing, if a path to a different sinknode is found through an unassigned node, that node is assigned to the rootnode of that path. Once all connections have been routed, assignments aremade for all remaining unassigned nodes by solving a linear programmingproblem to minimize the maximum chain length.3.2.3 Combined ApproachThe Combined approach creates a global placement as in Section 3.2.1, fol-lowed by the algorithm in [31] with each model initialized with the candidatequbits. In comparison with the Disperse router, the heuristic in [31] ripsup conflicting or large sized chains and performs a tree search starting from653.3. Evaluationthe remaining neighbouring nodes. Negotiated congestion is also used tocalculate the cost of each unused vertex. Unlike the disperse router, thisapproach allows chains to move away from their candidate tiles and movetoward more congested areas. As seen in Figure 3.4, the Combined approachyielded better results in terms of average chain length, and comparable re-sults for maximum chain length, when compared both to the layout-agnosticalgorithm [31], and the Disperse router. The Disperse method tends to betoo restrictive, and is outperformed by the Combined method for bench-marks with more complexity than the grid shown in Figure 3.4. For thefollowing sections, this document will focus on comparing D-Wave’s layout-agnostic [31] heuristic with the layout-aware Combined flow.3.3 EvaluationIn this section, we evaluate our techniques using the set of benchmark prob-lems outlined in Table 3.1. These benchmark problems include: differentsize 2D grids and Rook’s graphs, models of Quantum-dot Cellular Automata(QCA) Networks (as explained in Section 3.1), and LANL1 which is a prob-lem known to be hard to embed using D-Wave’s default algorithm [131] (aswitnessed in the valid embedding count in Table 3.1). Unlike the otherbenchmarks, LANL1 does not have an intrinsic layout. To address this, aspring layout is generated every time it is embedded, and the runtime in-curred in that is included in the evaluation. This problem was included inthe benchmark set to demonstrate the applicability of layout-awareness toany type of Ising model.663.3. Evaluation(a) Layout-Agnostic[31]: Total: 648. Max Chain: 7. Avg Chain±Stdev: 2.53±1.34(b) Layout-Aware Disperse:Total: 553. Max Chain: 4.Avg Chain±Stdev: 2.16±0.76(c) Layout-Aware Combined:Total: 529. Max Chain: 4.Avg Chain±Stdev:2.07±0.86Figure 3.4: Comparison of embedding methods.673.3.EvaluationTable 3.1: Benchmark characteristics and summary of embedding results.BenchmarkAgnostic[31] Combinedτ(s)λi κi ✓ τ(s) λi κi ✓Name |P | |E| D β Max Avg σ Max Max Avg σ MaxQCA MAJ5B 13 41 0.53 3.15 0.2 4.7 2.9 1 2.4 100 0.3 4.6 2.9 1 2.4 100QCA NOTFT 13 49 0.54 3.5 0.3 5 3.2 1 2.5 100 0.3 4.9 3.1 0.9 2.5 100GRID2D 4X4∗ 16 24 0.2 1.5 0.1 3 1.6 0.7 1.5 100 0.2 3.1 1.7 0.7 1.4 100ROOKS 4X4 16 48 0.4 3 0.3 6.1 3.9 1.1 3.5 100 0.4 5.8 3.8 1 3.1 100QCA MAJ5A 19 88 0.51 4.63 0.6 7.1 4.5 1.5 3.4 100 0.5 7 4.4 1.6 3.4 100QCA SRFF 24 80 0.29 3.33 0.5 5.8 3.3 1.2 3 100 0.5 5.9 3.4 1.3 3 100GRID2D 5X5∗ 25 40 0.13 1.6 0.3 4 1.9 0.9 1.8 100 0.4 3.5 1.8 0.8 1.8 100QCA COPLANX 25 58 0.19 2.32 0.5 4.7 2.4 1.1 2.3 99 0.6 4.8 2.5 1.1 2.4 100QCA MUX 25 87 0.29 3.48 0.5 6.1 3.4 1.5 3.1 100 0.6 6.1 3.4 1.5 3.2 100ROOKS 5X5 25 100 0.33 4 0.9 9.4 5.9 1.7 4.4 100 1 9.3 5.8 1.6 4.3 100QCA SOSC 33 112 0.21 3.39 1 6.5 3.5 1.3 3.4 100 0.9 6.3 3.5 1.3 3.4 100QCA XOR 77 256 0.09 3.32 2 11.4 4.1 2.2 4.4 98 1.6 6.9 3.6 1.4 4.1 100QCA FULLADD 101 305 0.06 3.02 2.9 12.5 3.6 2.1 4 90 1.6 6.8 3.3 1.4 3.9 100QCA SERADD 128 391 0.05 3.05 3.7 14.4 3.8 2.3 4.2 91 1.9 7 3.4 1.4 4.2 100QCA LOOPMEM 129 412 0.05 3.19 4.3 14.5 4 2.4 4.2 86 1.9 7.7 3.6 1.5 4.3 100QCA 4BMUX 210 719 0.03 3.42 11.8 20.1 4.1 2.6 5.1 48 4.5 22.3 4.2 2.9 5.2 93GRID2D 16X16∗ 256 480 0.01 1.88 3.9 14 3 2.1 3.1 95 2.3 4.3 2.3 0.9 2.4 100LANL1§ 269 490 0.01 1.82 5.4 27.7 3.4 3.8 3.6 33 3.4 17.9 3.1 2.9 3.7 100QCA 4BACCUM 290 883 0.02 3.04 12.5 17.6 3.5 2.2 4.8 23 6.3 16.8 3.8 2.4 5.3 99(*) Grid graphs are planar.(§) Run-time τ(s) spent generating an artificial spring-layout is included.683.3. Evaluation3.3.1 Embedding ResultsThe evaluation of the Agnostic and Combined methods is collected in Ta-ble 3.1. Each benchmark problem is characterized by graph size |P |, numberof edges |E|, graph density D = 2|E||P |(|P |−1) (“cliqueness”), and beta index(or connectivity) β = |E||P | . Results are obtained from averaging 100 runsof a layout-agnostic and layout-aware algorithm for embedding time in sec-onds τ ; maximum, average, and standard deviation (σ) of chain lengths λi;maximum connectivity κi; and valid embeddings (✓).From those results, it can be seen that, in small problems with sizes|P | < 50, there is no clear advantage for either method, including similarembedding times. However, with increasing problem complexity, it is seenthat the likelihood of finding a valid embedding increases for the Combinedmethod, compared to the Agnostic method. In particular, for the benchmarkQCA 4BACCUM, for the Combined method, 99 of the 100 trials resulted ina valid embedding, while for the Agnostic method, only 23 trials resulted in avalid embedding. The table also shows that for higher complexity problems,the time spent on the Combined approach is shorter than for Agnostic.On average, for all benchmarks, the Agnostic algorithm spends 26msper node, while the Combined method spends 20ms (a 19% improvement).In the quality of chains, for all benchmarks, Agnostic uses an average of3.50 qubits per node, while Combined uses 3.35 qubits per node (a 3.6%improvement). Maximum chains are also consistently reduced, by an averageof 16%. These results are caused by the reduction of congestion providedby layout-awareness.693.3. EvaluationQCA_XORQCA_FULLADQCA_SERADDQCA_LOOPMEMQCA_4BMUXGRID2D_16X16LANL1QCA_4BACCUM12345Avg Chainagnostic avg=3.67combined avg=3.41(a) Avg ChainQCA_XORQCA_FULLADQCA_SERADDQCA_LOOPMEMQCA_4BMUXGRID2D_16X16LANL1QCA_4BACCUM01020304050Max Chainagnostic avg=15.02combined avg=11.19(b) Max ChainFigure 3.5: Comparison of chain metrics.703.3. EvaluationFigures 3.5a and 3.5b contain more detailed results for average and max-imum chain length, from 100 embeddings of benchmarks with sizes |P | > 50.Each box shows the quartiles, a horizontal line at the median, a marker(▲) at the mean, and whiskers extending until the lowest and highest da-tum within 1.5 of the interquartile range; outliers are plotted as individualpoints.Overall, the average chain length is improved by 7%, and maximum chainlength reduced by 25%.On the other hand, in this set of results, embeddingsfor two out of the nineteen problems (QCA 4BACCUM and QCA 4BMUX )tend to have slightly longer chain lengths when using layout-awareness.These negative results in the two benchmarks (longer chains) are also asso-ciated to the reduction of congestion in the initial stages of the embeddingheuristic, which allow the algorithm to yield more valid embeddings faster,but in doing so, will also yield un-optimized embeddings “prematurely”.For the set of larger benchmarks, the run-time improvement per-node in-creases to 48%, which suggests that, if available, more time could be spenton further optimizing chain length.Lastly, in these results, a higher number of interactions κ suggests higherdensity in the resulting embedding; more connected nodes are mapped closerto each other. This is a desirable feature, in order to allow more choice inthe assignment of coupler weights.3.3.2 Sampling ResultsD-Wave sampling experiments are performed for the problems in the bench-mark set with size |P | > 50. The ten best embeddings from each algorithm713.3. Evaluation3.3 3.4 3.5 3.6Avg Chain−3.13−3.12−3.11−3.10−3.09−3.08−3.07−3.06−3.05Energyagnosticcombined6 7 8 9Max Chain−3.13−3.12−3.11−3.10−3.09−3.08−3.07−3.06−3.05Energyagnosticcombined(a) QCA XOR3.05 3.10 3.15 3.20 3.25Avg Chain−3.16−3.14−3.12−3.10−3.08Energyagnosticcombined6 8 10 12Max Chain−3.16−3.14−3.12−3.10−3.08Energyagnosticcombined(b) QCA FULLADDFigure 3.6: D-Wave energy statistics.723.4. Conclusions and Discussionwere run on a D-Wave processor. For each embedding, we collected 10000samples. The results are summarized in Figures 3.6 to 3.9. The x positionfor each dot is a chain metric, while y marks both the median (labelledmarker) and minimum energies (▼). A black dotted line marks the lowestenergy sampled for that benchmark. The averages over all ten embeddings,in both axes, are marked by dotted lines in the corresponding colours foreach method.The generation of better embeddings has a direct positive impact on thesampling of lower energy results, and the use of layout-awareness can leadto a minimization of the maximum and average chain lengths. However, inagreement with the results in Table 3.1, embeddings for bothQCA 4BACCUMand QCA 4BMUX do not seem to benefit from layout-awareness. This is anopportunity for the exploration of post-embedding optimization methods asan interesting area for future work, given that the embeddings found fasterusing layout-awareness are less congested.3.4 Conclusions and DiscussionThis chapter described layout-awareness for minor-embedding, a fundamen-tally different approach from existing methods. It leverages layout informa-tion that is part of the problem formulation, or artificially created from thegraph adjacency with graph drawing algorithms.Layout-aware minor-embedding methods can find mappings faster andwith higher success rate compared to the existing heuristics, while also be-ing able to yield shorter or equal qubit chain embeddings for a diverse set733.4. Conclusions and Discussionof benchmarking graphs. In cases where the layout-aware method has asignificant impact on the quality of the chains (e.g. GRID 2D 16X16 andLANL1 ), there is also evidence of the subsequent impact on quality of sam-ples that can be obtained from a QAP. These four factors: run-time, successrate, embedding quality, and the resulting sampling performance, are clearmotivators to continue working on improvements to the minor-embeddingheuristics.Implementations of the algorithms, benchmarks, and metrics describedhere have been made available online as part of an open-source Pythonpackage [138], and collaboratively integrated into the official D-Wave sys-tems minor-embedding Python package [48]. Therefore, the community ofresearchers in CAD for quantum annealing can contribute to these and othermethods.More generally, context-awareness for minor-embedding, the idea of us-ing additional information from the problem formulation in the process ofmapping it onto qubits, is not limited to location information. Chapter 4presents the field of quantum-assisted machine learning, and Chapter 5 usesQAML as an example for the use of contextual information available in thoseapplications.743.4. Conclusions and Discussion3.2 3.4 3.6 3.8 4.0 4.2Avg Chain−2.18−2.16−2.14−2.12−2.10Energyagnosticcombined6 8 10 12 14 16Max Chain−2.18−2.16−2.14−2.12−2.10Energyagnosticcombined(a) QCA SERADD3.30 3.35 3.40 3.45 3.50 3.55Avg Chain−1.18−1.16−1.14−1.12−1.10Energyagnosticcombined7.5 10.0 12.5 15.0 17.5Max Chain−1.18−1.16−1.14−1.12−1.10Energyagnosticcombined(b) QCA LOOPMEMFigure 3.7: (continued) D-Wave energy statistics.753.4. Conclusions and Discussion3.5 3.6 3.7 3.8 3.9 4.0Avg Chain−4.24−4.22−4.20−4.18−4.16−4.14−4.12Energyagnosticcombined10 20 30Max Chain−4.24−4.22−4.20−4.18−4.16−4.14−4.12Energyagnosticcombined(a) QCA 4BMUX2.8 2.9 3.0 3.1Avg Chain−368−366−364−362−360−358Energyagnosticcombined12.5 15.0 17.5 20.0 22.5 25.0Max Chain−368−366−364−362−360−358Energyagnosticcombined(b) LANL1Figure 3.8: (continued) D-Wave energy statistics.763.4. Conclusions and Discussion2.0 2.5 3.0 3.5Avg Chain−154−153−152−151−150−149Energyagnosticcombined5 10 15 20Max Chain−154−153−152−151−150−149Energyagnosticcombined(a) GRID 2D 16X163.2 3.4 3.6Avg Chain−2.350−2.325−2.300−2.275−2.250−2.225−2.200Energyagnosticcombined10 15 20 25 30Max Chain−2.350−2.325−2.300−2.275−2.250−2.225−2.200Energyagnosticcombined(b) QCA 4BACCUMFigure 3.9: (continued) D-Wave energy statistics.77Chapter 4Quantum-Assisted MachineLearningThe embedding methods described in Chapter 3 make use of location infor-mation to guide the embedding of a problem onto a QAP fabric. Layoutinformation is not the only type of contextual information that can be usedto guide the embedding methods. In this chapter, we focus on a specificapplication domain, Quantum Assisted Machine Learning (QAML) trainingfor Boltzmann Machines (BM), which has rich contextual information thatcan be used during embedding. Unlike the optimization problems consid-ered in Chapter 3, QAML applications employ a sampling-based approach,in which all samples are used instead of the minimum energy sample. Thisprovides a good match between QAML applications and the capabilities ofa QAP. Although our primary focus on the relationship between embeddingand the application, QAML architectures and methods are interesting intheir own right, and have been the subject of a considerable amount of re-search [2, 18, 52, 57, 58, 82, 90, 97, 102–105, 117, 123, 156, 160, 161, 172, 174].As will be shown, there are several contextual structural properties ofthe graphs needed for QAML that can be integrated into embedding meth-78Chapter 4. Quantum-Assisted Machine Learningods. First, nodes (variables) are explicitly divided into visible or hidden(latent) nodes. An embedding algorithm can use this distinction to opti-mize the implementation. Second, the graphs needed to compute gradientsare typically organized in a layered fashion which is the conventional designof deep neural networks. Third, nodes with the same connectivity can beinterchanged; the enumeration of nodes is arbitrary as long as inputs in thedataset are “clamped” to the appropriate visible nodes. Fourth, machinelearning graphs can be modified (often known as “pruning”) without losingthe overall functionality. This raises the possibility of modifying the graphduring embedding to reduce chains. Although pruning nodes (or edges)typically reduces performance, if doing so can reduce chain length, the im-provement in the sample distribution (making it more ”Boltzmann-like”)may counterbalance this performance reduction.Our discussion of QAML is divided into two chapters: this chapter fo-cuses on the framework we built to explore QAML, and Chapter 5 presentsembedding methods and results.The organization of this chapter is as follows. The following section in-troduces QAML, beginning with the principles behind Boltzmann machines,and the methods used in classical BM training, which lay the foundation forquantum-assisted BM training with QAPs. Section 4.2 describes the soft-ware framework developed to achieve QAML training. To our knowledge, noother QAML software framework exists that implements the configurationsthat will be described below. In developing our framework, we encounteredseveral research challenges; these will be described in Sections 4.3 to 4.6.Finally, Section 4.7 concludes and provides some discussion related to the794.1. Boltzmann Machinesproposed framework.4.1 Boltzmann MachinesBoltzmann Machines (BMs) are probabilistic generative network models. Ina BM, each binary node obeys the probability function in Equation (4.1),which depends on the values of its neighbours, where the set of nodes x canbe made exclusively out of visible (v or input nodes), or visible and hidden(x = {v,h}) nodes, and is parameterized by the linear (a = {b, c}) (forvisible and hidden) and quadratic biases W .p(xi = 1) = sigm(ai +∑j∈N(i)wijxj). (4.1)Because of the distinction between visible and hidden nodes, there is alsoa distinction between edges inW that are: between visible and visible (vv),and between hidden and hidden (hh). The collection of trainable parameterscan also be referred to as Θ = {b, c,W }. Figure 4.1 is an example ofa BM(3,5), with three visible, and five hidden nodes; with correspondinglinear biases and example quadratic biases.804.1. Boltzmann MachinesFigure 4.1: Boltzmann Machine (a.k.a Fully-connected, complete or gen-eral).The probability function in Equation (4.1), when applied to the completeset of nodes, results in the joint set (visible and hidden) behaving accordingto a Boltzmann distribution:p(v,h) =e−E(v,h)Z; Z =∑xe−E(x) (4.2)E(v,h) = −m∑ibivi −m∑jcjhj −∑i<jwijxixj (4.3)This means that characterizing these models requires the challengingtask of calculating (or estimating) the joint probability p(v,h), as seen inthe probability mass function (4.2). This becomes intractable with the sizeof the problem due to the summation of terms in the partition function Z.A detailed derivation of these equations can be found in [63].Even though BMs attract significant interest for unsupervised learning814.1. Boltzmann Machinesand data reconstruction, or as building blocks for classification networks;adoption of these models remains experimental because of the prohibitivecost of accurate sampling. On the other hand, problems in the area ofphysical systems simulations could benefit from advances in the performanceof BMs [15, 167, 168], where there is evidence that additional connectivity inthe network can improve the testing accuracy and reconstruction error [104].4.1.1 Learning RulesTypically, in order to train a Boltzmann machine, one can target maximizingthe likelihood of sampling the dataset from the visible nodes v of the networkL(Θ|v), as seen in Equation (4.4) for one input vector. The use of logarithmsallow the linear separation in the right hand side, between the (first term)computation that accounts for sampling states with the input vector in thevisible nodes, also called positive phase; and the (second term) computationthat accounts for all possible configurations of the network, called negativephase.lnL(Θ|v) = ln 1Z∑he−E(v,h) =positive phase︷ ︸︸ ︷ln∑he−E(v,h)−negative phase︷ ︸︸ ︷ln∑v,he−E(v,h) (4.4)From this formulation, it can be seen that algorithms to train Boltzmannmachines face an immense challenge in the calculation of the negative-phaseterm, which is why approximation methods are commonplace in this areaof work. These approximations are possible because the computation ofthe gradient of the likelihood with respect to Θ, as seen in (4.5), is equal824.1. Boltzmann Machinesto the expectation value of the difference in energy, for both the positiveand negative phase; that is, with respect to the states with visible nodesclamped, for the former case, and with respect to all states for the latter.∂ lnL(Θ|v)∂Θ= −∑hp(h|v)∂E(v,h)∂Θ+∑v,hp(v,h)∂E(v,h)∂Θ(4.5)For example, with dataset D = {y(1), ...,y(D)}, the gradient for thelog-likelihood with respect to visible bias b is:1|D|D∑d=1∂ lnL(Θ|y(d))∂bi∝ ⟨vi⟩data − ⟨vi⟩model ; (4.6)with respect to hidden bias c is:1|D|D∑d=1∂ lnL(Θ|y(d))∂cj∝ ⟨hj⟩data − ⟨hj⟩model ; (4.7)and with respect to weights W :1|D|D∑d=1∂ lnL(Θ|y(d))∂wij∝ ⟨xixj⟩data − ⟨xixj⟩model . (4.8)Practical implementations of BMs calculate both terms by approximat-ing the expectation values from a collection of samples S, shown below forthe individual cases of visible and hidden nodes,⟨vi⟩model ≈1SS∑s=1v(s)i ; ⟨hi⟩model ≈1SS∑s=1h(s)i ; (4.9)and for the pairwise visible-hidden interactions in the network,834.1. Boltzmann Machines⟨xixj⟩model ≈1SS∑s=1x(s)i x(s)j . (4.10)Having estimated the gradients at each node, the model is iterativelytuned using Stochastic Gradient Descent (SGD). As in any machine learn-ing training heuristic, more complex optimization algorithms can be imple-mented. Equation (4.11) is an example implementation, showing only theupdate rule for the quadratic terms.∆wij(t+ 1) =η∆wij(t) + ϵ(1SS∑s=1[v(s)i h(s)j − vˆ(s)i hˆ(s)j])− λwij(t) (4.11)where ϵ is the learning rate, with a momentum term η, and a weight-decayterm λ.4.1.2 Restricted Boltzmann Machine (RBM)Collecting those samples typically relies on Markov Chain Monte Carlo(MCMC) methods, which are subject to very slow mixing. For this rea-son, to be able to train a Boltzmann machine classically, the problem canbe reduced by restricting the connectivity of the network only to edges be-tween visible and hidden nodes. An RBM(m,n) has m visible nodes, andn hidden nodes, connected in a bipartite graph. Figure 4.2 represents anRBM(3,4), with linear and quadratic biases.844.1. Boltzmann MachinesFigure 4.2: Restricted Boltzmann Machine.This simplifies the chain sampling method because the two sets of nodesbecome conditionally independent; i.e., computing the probabilities of thehidden nodes only needs knowledge of the visible, and vice versa, as seen inEquations (4.12) and (4.13), respectively.p(hj = 1|v) = sigm(cj +m∑iwijvi) (4.12)p(vi = 1|h) = sigm(bi +n∑jwijhj) (4.13)This significantly simplifies the positive phase. However, the trainingalgorithm still requires the negative phase, which in RBMs is done usingk-step Gibbs-k sampling; a method based on repeatedly sampling (k-times)the chain of v and h nodes.854.1. Boltzmann Machinesvˆ(0)⇒ hˆ(0)⇒ vˆ(1)⇒ hˆ(1)⇒ . . . vˆ(k)⇒ hˆ(k) (4.14)where vˆ(0) is the input data. This allows the estimation of the modelexpectation values. For example:⟨vihj⟩model ≈〈vˆi(k)hˆj(k)〉S=1SS∑s=1vˆ(s)i (k)hˆ(s)j (k). (4.15)The use of Gibbs sampling paired with the maximum likelihood gradientcalculation is commonly referred to as Contrastive Divergence (CD), or CD-k. There are variations of this algorithm, not in the scope of this work,that change how those samples are collected [63, 76, 147]. However, justas in CD-k, these algorithms are ultimately minimizing a different function,“biased” by the sampling method [33].For this reason, methods that are able to sample more accurately from thenetwork’s Boltzmann distribution are of great interest. In addition, explo-ration of the capabilities of non-restricted topologies with classical methods iscomputationally prohibitive. Both of these goals are targeted with Quantum-assisted Machine Learning (QAML).4.1.3 Quantum-Assisted Boltzmann MachinesThe mechanisms that employ quantum annealing devices to train Boltz-mann machines belong to the category of quantum-assisted machine learn-ing (QAML), i.e., they use classical datasets, and offload demanding com-putation tasks in the training algorithm (and inference in some cases) toa quantum computing device. In that sense, QAML resembles classical864.1. Boltzmann MachinesML training using accelerators such as Graphics Processing Units (GPUs),Tensor Processing Units (TPUs), or FPGAs, among others. This is in con-trast with Quantum machine learning (QML), where the datasets consist ofquantum states which has the added complexity of “storing” those states.Conversely, there are QAML applications that are formulated as optimiza-tion problems [118]. In those cases, the QAP can be formulated in the sameway as in any other QUBO, and the contributions of Chapter 3 are morerelevant to the type of minor-embedding that is required.The goal in QAML for Boltzmann machines is to replace the slow-mixingMonte-Carlo methods used to sample from the model’s distribution, withcalls to a quantum computing device. This is possible because of the be-haviour described in Equations (2.11) and (4.16), i.e. the expectation valuesused to calculate the gradients for all nodes and pairs of nodes are calcu-lated from a set of S samples, where vsi is the s-th sample (+1 or −1) of theBoltzmann machine.〈vˆihˆj〉model∼〈vˆihˆj〉S=1SS∑s=1vˆsi hˆsj . (4.16)Quantum-assisted training of BMs is different from training quantumBoltzmann machines (QBMs). The latter is a model that is purely theoret-ical at the time of writing, due to limitations in the annealing schedule ofcommercial QAPs [7]; it requires the samples to be obtained from the quan-tum distribution at a specific point in the anneal, instead of the equilibriumBoltzmann distribution obtained at the end. On the other hand, the trainingmechanisms are similar, therefore, any advances made in quantum-assisted874.2. QAML Software Frameworkmachine learning, would directly translate to QBMs and vice versa.4.2 QAML Software FrameworkThis section presents the QAML software framework that was developed forthe experiments in this thesis. This type of implementation is necessary todemonstrate the principles of quantum-assisted BM training, and to evaluatethe effects of minor-embedding and pruning on the performance of quantum-assisted Boltzmann machine training.The development of a framework required significant engineering effort.Even though multiple publications have shown proof-of-concept experimentswith quantum-assisted training of Boltzmann machines [2, 18, 57, 97, 102,104, 156, 172], the frameworks used in these previous works are either notavilable, or not suitable for the types of experiments we wish to conduct. Thedevelopment of a new framework was motivated both by our own research,but also the desire to create a flexible, accessible, and open-source frameworkthat can be used by other researchers (such as [175] for QCA circuits and [22]for FPGAs). The development of the framework also unearthed researchproblems related to scaling, which we describe later in this chapter.4.2.1 Framework ComponentsFigure 4.5 is a high level diagram of the components implemented and in-tegrated as part of this work. The QAML framework has similarities withits classical machine learning counterparts, especially those that focus onBoltzmann Machines [15, 116]. This allows the development of cross com-884.2. QAML Software Frameworkpatibility by coding the framework as a Python package on top of the widelyused PyTorch code base [132].Each component of the framework will be described below, and Sec-tion 4.2.2 will demonstrate the flexibility of the framework by showing howthese components can be used to investigate four different QAML configu-rations.Datasets: In the experimental ML setup, it is important to have a baselineof datasets that allow the evaluation of the machine learning principles beingdeveloped under the QAML framework. Datasets can either be constructedusing actual data, or synthetically generated. As an example of the latter,we have implemented the Bars-And-Stripes dataset as seen in Figure 4.3.This is a dataset that has been used in different QAML setups [55, 102, 156]to provide an intuitive way to measure performance [16]. In this dataset,each frame contains either vertical bars or horizontal stripes, and a two bitlabel indicating whether the frame contains bars or stripes. In Figure 4.3,the label is encoded as in one-hot format using the upper-right pixel and thepixel below the upper-right pixel. More details are given in Subsection 4.6.1where it is used to evaluate a classification model, and Section 5.2 where itis used to evaluate a model’s ability to sample from the dataset.894.2. QAML Software FrameworkFigure 4.3: Subset of the 8x8 Bars-And-Stripes (BAS) dataset with labels.904.2. QAML Software FrameworkFigure 4.4: Subset of the binarized OptDigits dataset with labels.A second input dataset we use in this thesis is the OptDigits datasetwhich has been used in other QAML research [18, 98] and is similar to aCoarse Grained MNIST (CG-MNIST) [2]. When formulating a Boltzmannmachine as a standalone classification model, a label can be embedded ontothe image, as shown in Figure 4.4. In this case, the label consists of the right-most column, and uses a one-hot encoding scheme to indicate the numberrepresented by the image.These two input datasets are small, compared to those used for classicalML training; this reflects the current state-of-the-art in QAML hardware.Larger datasets can be created as the capacity of these systems increases orby introducing classical convolution layers. However, for the purpose of this914.2. QAML Software Frameworkwork to evaluate the “raw” behaviour of the QAP devices, small datasetsthat fit the qubit fabric are preferred.Models: The QAML framework supports the general BM, as well as ar-bitrary subgraphs, such as the bipartite RBM seen in Section 4.1.2. In themost general case, general Boltzmann machines span a clique (also known asa complete or fully-connected) graph with size (V,H), as portrayed in Fig-ure 4.1. In order to train any BM that is not an RBM, the QAML requiresthe ability to train the intra-layer weights. This feature does not typicallyexist in classical machine learning frameworks [15, 116].Section 4.2.2 highlights how this flexibility can be used to describe avariety of configurations. Moreover, it is also possible to integrate thesemodels into more complex systems, such as different varieties of Deep Boltz-mann Machines (DBMs) [2, 156], or Quantum Variational AutoEncoders(QVAEs) [90, 172]. We do not experiment with these in this thesis, how-ever, the ability to describe such complex model enables future work in thisarea.Boltzmann machines can be formulated as either binary or spin-valuemodels, while, the native formulation in D-Wave’s QAP devices is an Isingspin model. Even though the transformation of a dataset between the twovariable types is trivial, the use of binary data is preferred to preserve com-patibility with classical learning models.Samplers: As described in Section 4.1.1, training for BMs requires nega-tive (-) and positive (+) phase samplers. In our framework, these samplers924.2. QAML Software Frameworkcan be configured to use either classical algorithms or employ the quantumannealer (in our flow, this is the only place in which quantum annealingcan be used). Several classical sampling algorithms have been provided inthe flow: Gibbs, persistent Gibbs, simulated annealing (SA), random sam-pling, and an exact solver. If a quantum sampler is used, the topology ofthe model is minor-embedded onto the qubit fabric at this stage. Therefore,the size of the largest model to be trained (without relying on partitioningmethods [14, 128]) is limited to the embeddable size of the model.During training, the positive-phase and negative-phase samplers are han-dled slightly differently. The positive-phase sampler receives a batch of datapoints as inputs (v0) and returns samples from the hidden nodes (h0), i.e.,the conditional probability. The negative-phase sampler does not clamp in-put nodes, but instead determines samples from all nodes (vk and hk), i.e.,the joint probability. As in Monte-Carlo sampling methods, increasing thenumber of samples S, increases the quality of the sampleset.An important consideration regarding the samplers is that they needto collect the probability that a given node is a +1. The manner in whichthis is done depends on the sampler used. When using a Gibbs samplerfor an RBM, this is relatively straightforward because the Gibbs samplingalgorithm already calculates the probability of each node. When using SA orQAP as a sampler (for a BM or RBM), it is possible to run multiple instancesof the algorithm to collect samples from each input, and from those samples,estimate the probability that a given node is a +1 by calculating the averagevalue for that node over all samples.934.2. QAML Software FrameworkAutomatic Differentiation: Similar to classical ML training, the auto-matic differentiation (also referred to as autograd) methods in the frameworkare designed to take the outputs of the model, and a reference (in this casethe input data) and compute a loss and gradient. The gradient is then prop-agated back to each parameter as described in Section 4.1.1. The processis then repeated for the next batch until the convergence criteria has beenachieved.Metrics: For BMs, it is important to distinguish between the reported lossand the objective function of the optimizer. As seen above in Equation (4.5)the gradients are calculated to maximize the likelihood of sampling from theinput dataset, however, reporting the likelihood would require computingthe probability of all states which becomes intractable.Because of the disparity between the gradient objective function and thereported loss, it is important to consider various metrics when training BMs.BM training research often reports the Mean Absolute Error (MAE)between the samples and the input batch. This is shown in Equation (4.17),where n is the number of samples and inputs in a batch.MAE =∑ni=0 |v(d) − v(s)|n(4.17)For classification tasks, accuracy is a suitable metric, however, for syn-thetic datasets, for which we can characterize the domain of the input set,the following may be more appropriate:• Precision: The capacity of the model to retrieve images that belong944.2. QAML Software Frameworkto the dataset. p =< #sampled patterns > / < #total samples >• Recall : The capacity of the model to retrieve a representative distribu-tion of the dataset. r =< #unique patterns > / < #total patterns >• Score: A single figure of merit to represent both p and r. score = 2prp+rFor RBMs, or small models with more complex topologies, the Kullback-Leibler Divergence (DKL) can be computed between the probabilities ofeach each energy level Ei in the dataset (Pdata), and the probabilities ofsampling Ei from the QAP Psamples. Wherein, DKL(Pdata ∥ Psamples) isalways non-negative and only 0 when Pdata = Psamples. The probabilitiescan be computed by getting the energy of each configuration, aggregatingthe same energy levels and dividing that count by the number of samples.Calculating the energies is an expensive computation in non-restricted BMs.For probabilities equal to 0, the DKL can use a very small smoothing value;e.g., 1e− 6.DKL(P ||Q) =∑x∈Xp(x) logp(x)q(x)(4.18)The QAML framework is able to report all these quantities, as well as othermetrics that can characterize the model without the need of training. Forexample, the distance to an exact Boltzmann distribution can be used insmall models when those probabilities can be computed in tractable time,such as the models in Chapter 4.954.2. QAML Software Framework4.2.2 Framework ConfigurationsAn important goal in creating the framework was to make it as flexibleas possible. The combination of the models and samplers described in theprevious section allows the framework to be used to evaluate several differentconfigurations:Classic RBM: This is the most common implementation of RBM train-ing, and can be found in other specialized software frameworks [116]. Thetopology of the RBM allows for efficient sampling for the positive phase bysimply propagating forward from visible to hidden nodes. Even though col-lecting samples using Gibbs sampling is trivial, there are limitations to thisapproach, as mentioned in Section 4.1.2.Quantum-assisted RBM: A QARBM uses the same positive-phase asa classic RBM, but replaces the negative-phase sampler with a call to thequantum sampler per batch. For QAPs, a minor-embedding of the bipartitegraph is needed once at the beginning of training. The QAML methods willtry to minor-embed multiple replicas of the bipartite graph to increase thenumber of samples obtained.964.2.QAMLSoftwareFrameworkFigure 4.5: QAML framework. Both RBM and BM components are shown. The positive and negative phasesamplers are either a QAP or classical. The grey block uses unmodified PyTorch classes and methods. (*)Datasets are binarized and not limited to those used in this work.974.3. Temperature EstimationClassic BM: This is only practically useful for small sizes because sam-pling from both the positive and negative phase becomes impractical as thesize of the model increases. For small models, however, a QAML “solver” canprovide exact probabilities useful for characterization. This also applies forany BM topology that is not a complete graph, but which has higher connec-tivity than bipartite, e.g., Limited Boltzmann Machines (LBM) [52, 58, 104].Quantum-assisted BM: In this configuration, both the positive and neg-ative phases use a quantum sampler. Such a configuration is still consideredquantum-assisted because the dataset and parameters of the model remainclassical. The positive sampler requires an embedding of the sub-graphspanning the hidden nodes. The QAML methods will try to minor-embedmultiple replicas of the hidden-node graph; the number of embedded replicasdetermines the batch size. The negative-phase sampler requires an embed-ding of the complete graph. Both samplers are called once per batch, unlessthe number of hidden-node graph replicas is too low.4.3 Temperature EstimationAn important consideration when using a quantum annealer for this appli-cation is the estimation of the inverse temperature of the distribution. Theinverse temperature, βDW in Equation (4.19), encapsulates all sources ofnoise, including the physical temperature, quantization noise, and transi-tion probability (as mentioned in Section 2.3). However, this is an instance-dependent value. For different values of {h,J}, the inverse-temperature will984.3. Temperature Estimationbe different, due to the differences in the energy gaps between Ising models.p(v, h)DW =e−βDWE(v,h)ZDW; ZDW =∑v,he−βDWE(v,h) (4.19)It is therefore required that a training algorithm for QARBMs, wherea classical sampler (e.g., Gibbs) is expected to sample from the distribu-tion, incorporates an estimate of distribution temperature into the trainingalgorithm. For this reason, several authors have proposed or implementedmethods to estimate this inverse temperature value, known as βeff, or effec-tive inverse temperature [17, 113, 150, 176].4.3.1 Physical Temperature ApproximationIt has been proposed that the inverse temperature of the distribution can beclosely approximated from the physical properties of the device [113], suchthat:βDW ∼ βeff = β¯B(s∗)/Jmax; β¯ = hkBTDW, (4.20)where B(s∗) is the value of B(s) (as seen in Figure 2.1) at a point s∗, whichis called the “optimal pausing point” or a point in the anneal just beforethe freeze-out point where the quantum tunnelling effects are reduced; andJmax is the maximum range of the D-Wave quadratic biases. The operatingtemperature of the annealer TDW is used to compute β¯, with Boltzmannconstant kB, and Planck’s constant h.994.3. Temperature EstimationAs an example, the estimate for the Advantage system4.1 used in theexperiments for this and the following chapter, is the following:Jmax = 1.0; B(s∗) = 0.8; TDW = 15.4± 0.1mK =⇒ βDW ∼ 2.5.However, this approximation may not be sufficient, because the value ofs∗ can only be obtained empirically, requiring the execution of a significantnumber of experiments to calculate s∗. Furthermore, the value changes de-pending on the location and scale of the minimum energy gap (it is instancedependent).4.3.2 Exact ComputationAnother method is to find the exact inverse temperature. In this approach,the user interested in characterizing a specific machine would create a prob-lem formulation with known exact probabilities. This is possible (a) in smallenough problems were diagonalization of the problem Hamiltonian is feasi-ble within reasonable wall clock times; or (b) with the creation of syntheticproblems, which have a lower time complexity to calculate all degenerateenergy states [12, 112].This method guarantees a close approximation to the device inverse tem-perature value of that specific problem instance. However, as mentioned, thisinverse temperature value will vary when the problem instance (i.e., h andJ) changes. Therefore, this method is not fit for training BMs or othervariational methods. Recalculating βDW with this method at each iterationwould become impractical.1004.4. Negative-Phase Temperature Scaling4.3.3 Adaptive HyperparameterThe most recent approach proposes to dynamically estimate the inverse tem-perature of the QAP sample distribution through adaptive training [176].With this method, one can make an educated initial guess of the value of βeff(with physical approximation), and then incorporate it as a trainable vari-able within the gradient calculation. The chosen βeff is then updated withits own configuration of stochastic gradient descent, by using the followinggradient:∆βeff = [⟨E⟩D − ⟨E⟩S ] . (4.21)Unless otherwise mentioned, all training experiments in this thesis use asimple estimation of βeff = 2.5, to be able to isolate the performance impactfrom the minor-embedding changes proposed in this thesis. Incorporatingthe gradient in (4.21) had a negligible effect on performance compared to afixed value. On the other hand, work on βeff estimation is orthogonal to thegoals of this thesis but is included into the QAML framework for future use.4.4 Negative-Phase Temperature ScalingThe most common approach to incorporate βeff into the QARBM training isto perform negative-phase temperature scaling. That is, during the negative-phase, the parameters of the Boltzmann machines are copied and modifiedsuch that the overall energy of the model is down-scaled by the estimatedβeff, as seen in Equation (4.22).1014.4. Negative-Phase Temperature ScalingΘDW = { bβeff,cβeff,Wβeff} (4.22)Based on the assumption that βeff is equivalent to βDW, those scaling factorscan cancel each other out, as seen in Equation (4.23). Therefore, the forwardsampling in the positive phase (i.e., samples using Equation (4.12)), cansample from the same distribution as the samples collected from the QAPin the negative phase.p(v,h)DW =e−βDWE(v,h)βeffZDW; ZDW =∑v,he−βDWE(v,h)βeff (4.23)βeff ∼ βDW =⇒ p(v,h)DW ≡ p(v,h) (4.24)The pseudocode in Algorithm 4.1 shows the steps to train an RBM usingsamples from a QAP. Compared to a classical approach, the only differenceis in the negative phase. The QAP method in Line 8 refers to a call to theD-Wave API which includes converting the parameters to the Ising model(as seen in Equation (2.13)).4.4.1 Limitations of Negative-Phase Temperature ScalingThe are limitations in the use use of negative-phase temperature scaling:Inability to Scale: If one would like to have the new parameters ΘDWscaled to the available bias range, doing so would counteract the effect of1024.4. Negative-Phase Temperature ScalingAlgorithm 4.1: Gradients using negative-phase β scaling.Input: RBM(Θ), training batch D, estimated βeffOutput: Approximation of gradient ∆Θ1 Init: ∆wij = ∆bi = ∆cj = 0 for i = 1, . . . , n; j = 1, . . . ,m2 for v ∈D do/* ====== Positive Phase ===== */3 v(0) ← v4 for j = 1, ...,m do5 h(0)j ∼ p(hj = 1|v(0),Θ)6 ⟨vh⟩D ← ⟨v(0)h(0)⟩; ⟨v⟩D ← ⟨v(0)⟩; ⟨h⟩D ← ⟨h(0)⟩/* ====== Negative Phase ====== */7 ΘDW ← {b/βeff, c/βeff,W /βeff}8 vˆ, hˆ← QAP (ΘDW )/* ====== Learning Rules ====== */9 for i = 1, . . . , n; j = 1, . . . ,m do10 ∆wij ← ∆wij +〈vihj〉D−〈vˆihˆj〉S11 for i = 1, . . . , n do12 ∆bi ← ∆bi +〈vi〉D−〈vˆi〉S13 for j = 1, . . . ,m do14 ∆cj ← ∆cj +〈hj〉D−〈hˆj〉Susing the βeff; undoing the actions taken to approximate the sample distri-butions.Quantization Error: Because of the inability to scale, it is challengingto avoid having quantization noise on the bias values, unless the weights aretuned to occupy the full bias range of the device.Parameter Overflow: This also brings forward a practical issue specificto the variational nature of this application. If the weights of the models aretuned such that they utilize the entire available range in the QAP device,then the set of gradients added to the models will most likely push the values1034.5. Evaluation: Range Scalingout of range. This has been seen in previous work, where authors trainedmodels until this overflow occurred [18, 155].4.5 Evaluation: Range ScalingDuring the construction of our QAML software framework, the limitationsdescribed above became evident. This section quantifies the effects on thequality of samples that are caused by scaling the model parameters, i.e.quantization noise. The QAML framework is used in the creation, sub-mission, and evaluation of the samples from a set of randomly initializedRBMs.The definition of quality for the samples collected, in the context oftraining Boltzmann machines, can be given by the distance between theprobabilities computed from the samples collected from the device, and theexact probability distribution at a certain β. Another way of describing thisis a measure of how “Boltzmann” is the distribution and, by extension, howto find the closest β =⇒ βeff. Equation (4.25) describes this metric, whereEi is an energy level i in the discrete set of levels for each model, P (Ei|β)is calculated from the exact diagonalization of the model at a given β, andQ(Ei) is calculated from the samples of the QAP.d(β) =12∑Ei∣∣Q(Ei)− P (Ei|β)∣∣; βeff = argminβd(β) (4.25)The values of β used in these experiments range between 2 and 9, with1044.5. Evaluation: Range Scalingincrements of 0.125. A more detailed study of the approximate value of βeffrequires a significant amount of QAP time which has been done in relatedwork [17, 150]; this work focuses on the effects of quantization instead.In order to do this evaluation, we use an RBM topology with eightvisible nodes and eight hidden nodes. This facilitates the calculation ofthe exact probabilities P (Ei|β); solving for the exact probabilities of largermodels would require exponentially more compute time (due to the Z termin Equation (4.2)). Multiple copies of the RBM were created, each oneinitialized with a uniform distribution of weights within a specific range, i.e.,a model with biases within [−0.1, 0.1] would have more quantization noisethan one with the range [−4.0, 4.0]. Each RBM is sampled 50, 000 times(five QAP calls with 10, 000 samples) with the setup specified in Table 4.1.Figures 4.6 and 4.7 present the effect of scaling an RBM(8,8) model tothe QAP device range. First, for the case without range-scaling, for eachbias range, Figure 4.6a shows the spread of closest estimated values of βeff,while Figure 4.6b shows the spread of minimum distances at which thosevalues were found. Each box plot shows the mean (▲), median line, lower-to-upper quartile boxes, whiskers to last value within one interquartile rangeafter the quartile, and the outliers (◦).As shown in the diagrams, networks initialized between [−0.1, 0.1], andsampled without range-scaling, are closest to a Boltzmann distribution at aninverse temperature βeff ∼ 7.0, with a distance deff(β) ∼ 0.7, and networksinitialized between [−4.0, 4.0] are closest to a Boltzmann distribution atan inverse temperature βeff ∼ 3.0, with a distance deff(β) ∼ 0.1. Theseexperiments confirm that quantization noise, introduced by under-utilizing1054.5. Evaluation: Range Scaling[-0.1,0.1] [-0.5,0.5] [-1.0,1.0] [-2.0,2.0] [-4.0,4.0]Uniform Weight Range2345678910βeff(a) Closest estimated βeff without range-scaling[-0.1,0.1] [-0.5,0.5] [-1.0,1.0] [-2.0,2.0] [-4.0,4.0]Uniform Weight Range0.00.20.40.60.81.0d(βeff)(b) Distance from Boltzmann at βeffwithout range-scalingFigure 4.6: Boltzmann distance without range-scaling.1064.5. Evaluation: Range Scalingthe device range, not only increases the temperature of the distribution but,more importantly, makes the distribution less “Boltzmann”. This meansthat, even with an accurate βeff estimation, using negative-phase scalingreduces the quality of the sample distribution.When using range-scaling, the distances remain similar between weightranges, suggesting that the values of βeff more closely approximate the Boltz-mann distribution. However, the variation in βeff increases which can beinterpreted as a better representation of the instance-dependent nature ofthe βDW term. This is a more desirable scenario since the magnitude of βeffdoesn’t affect the sample quality as long as it can be approximated.To aid repeatability of these experiments, Table 4.1 discloses the config-uration of the QAP used in the API call to collect the results in this section,as well as Section 4.6.1.Table 4.1: QAP configuration sheet.Property ValueSolver Name Advantage system4.1Annealing Time 20µsSpin Reversal Transforms 4Chain Strength (JFM) 1.6Chain Break Method Majority VoteAuto scale FalseQubit Temperature (TDW) 15.4± 0.1mK1074.5. Evaluation: Range Scaling[-0.1,0.1] [-0.5,0.5] [-1.0,1.0] [-2.0,2.0] [-4.0,4.0]Uniform Weight Range2345678910βeff(a) Closest estimated βeff with range-scaling[-0.1,0.1] [-0.5,0.5] [-1.0,1.0] [-2.0,2.0] [-4.0,4.0]Uniform Weight Range0.00.20.40.60.81.0d(βeff)(b) Distance from Boltzmann at βeff with range-scalingFigure 4.7: Boltzmann distance with range-scaling.1084.6. Contribution: Positive-Phase Temperature Scaling4.6 Contribution: Positive-Phase TemperatureScalingPositive-phase temperature scaling addresses these limitations. As discussedin Section 2.4.3, in order to obtain the best quality samples from a QAP,it is important to use the entire range of bias values provided. This is notpossible using the auto-scale setting on D-Wave’s cloud service, but only bymanually scaling the parameters before submitting them with auto scale=False,and preserving the α value. The parameters submitted to the QAP are,therefore,Θα = {αb, αc, αW }. (4.26)This is counter-intuitive because, as mentioned before, using the scalingfactor α is modifying the temperature of the sample distribution that iscollected from the QAP device. The formulation of the probability functionin this case is as follows,p(v,h)α =e−αβDWE(v,h)Zα; Zα =∑v,he−αβDWE(v,h). (4.27)This means that there is still a need to incorporate temperature esti-mation into the algorithm. Therefore, instead of modifying the parameterssubmitted to the QAP, positive-phase temperature scaling is a modificationof the training algorithm to compensate for the temperature change in thedistribution from both α and βDW. The changes can be seen in the pseu-1094.6. Contribution: Positive-Phase Temperature Scalingdocode in Algorithm 4.2.The first change is to perform the negative phase of the training algo-rithm before the positive phase, in order to calculate and store the scalingfactor α at this iteration, to then be used in the positive phase.Algorithm 4.2: Gradients using positive-phase β scaling.Input: RBM(Θ), training batch D, estimated βeffOutput: Approximation of gradient ∆Θ1 Init ∆wij = ∆bi = ∆cj = 0 for i = 1, . . . , n; j = 1, . . . ,m2 for v ∈D do/* ====== Negative Phase ======= */3 Θα, α← Scale(Θ)4 vˆ, hˆ← QAP (Θα)/* ====== Positive Phase ======= */5 v(0) ← v6 for j = 1, ...,m do7 h(0)j ∼ p(hj = 1|v(0),Θα)8 ⟨vh⟩D ← ⟨v(0)h(0)⟩; ⟨v⟩D ← ⟨v(0)⟩; ⟨h⟩D ← ⟨h(0)⟩/* ====== Learning Rules ===== */9 . . .Second, in order to compute the positive-phase expectation values, weperform the sampling of the hidden nodes, similarly to Equation (4.12), butwith the modification that the parameters Θ are scaled by both the scalingfactor α in this iteration, and the estimated inverse temperature βeff.Θ′ = {αβeffb, αβeffc, αβeffW } (4.28)This is possible because the probabilities associated to the hidden nodesin the positive phase can be calculated exactly in an RBM, regardless of thetemperature of the model. The samples collected from the QAP will be ofthe best quality in regard to quantization noise.1104.6. Contribution: Positive-Phase Temperature Scalingp(h′j = 1|v) = sigm(αβeffcj + αβeffm∑iwijvi) (4.29)Because this method scales the parameters of the model every time it issubmitted to the QAP, this approach guarantees that the values will neverbe out of range; i.e., α can also take values less than 1. This behaviour iscrucial for real-world implementations of RBM training, or any variationalmethod.The implementation of positive-phase temperature scaling does not resultin expensive computations that would not be required in a training algorithmusing negative-phase temperature scaling. This makes this work equivalentin terms of run-time to previous work using negative-phase temperaturescaling.4.6.1 Evaluation: Positive-phase Temperature ScalingTo further demonstrate the QAML framework and to evaluate the use ofpositive-phase β, this section shows the full training flow of an RBM(64,64).This experiment is set up using the Bars And Stripes (BAS) dataset de-scribed in Table 4.2, and the model in Table 4.3.1114.6. Contribution: Positive-Phase Temperature ScalingTable 4.2: Dataset datasheet.Property ValueName Bars And StripesLearning Task ClassificationData Size 8x8Number of data vectors 510Sampler RandomTraining Set 400Testing Set 110Batch Size 400Throughout training, the testing accuracy was recorded by identifyingthe label that is generated after one forward-backward pass, when the valuesof the image are clamped to the visible nodes, except for the label bitswhich are set to 0.5. The choice of hyperparameters was tuned to obtainproof-of-concept results, and are not a representation of the capabilities ofquantum-assisted training against other training heuristics. Each call to theQAP collected S = 400 samples, i.e., the same size as the mini-batch.Table 4.3: Training datasheetProperty ValueVisible Nodes 64Hidden Nodes 64Optimization function SGDLearning Rate (ϵ) 0.1Weight Decay (λ) 1e-4Momentum (η) 0.5Figures 4.8 and 4.9 display the results of training with negative-phasescaling. Figures 4.10 and 4.11 display the results of training with positive-phase scaling. Each of the plots shows the testing accuracy throughout1124.6. Contribution: Positive-Phase Temperature Scalingtraining for 200 epochs, at an estimated βeff = [1.0, 2.0, 3.0, 4.0]. Bold linesshow the mean of five runs, initialized with different seeds at a uniform dis-tribution of weights within negative and positive of the value in the legend,i.e., W0.1 =⇒ [−0.1, 0.1], and so on. The shaded regions are the confidenceinterval in terms of standard deviation.Two special cases are highlighted in Figure 4.8: (†) when the modelswent out of range with the first gradient, and (‡) when the models went outof range before the 200 epochs; average is shown over the remaining runs.From Figure 4.8a it can be observed that training a model that startsat the maximum range available, and without down-scaling (i.e., βeff =1.0) results in an immediate overflow. This is also an issue later on inthe training, even when down-scaled, seen in Figure 4.8b. On top of that,quantization noise is evidently the problem for the smallest initial values(W0.1 and W0.5), or also visible in the decreasing performance of the W1.0lines as the value of βeff increases.4.6.2 Conclusions: Temperature ScalingPrevious work has tried to address the problem of overflow in two ways: (1)with the selection of model weights, and (2) with the use of weight-decay(λ), tuned such that it penalizes the higher value weights [100]. However,this does not guarantee staying within range, and requires extensive exper-imentation to adjust these values. This would introduce a major obstaclecompared to purely classical machine learning.Conversely, as shown in Figures 4.10 and 4.11, using positive-phase scal-ing allows training RBMs without having to go through an exhaustive tuning1134.6. Contribution: Positive-Phase Temperature Scaling(a) Training at βeff = 1.0(b) Training at βeff = 2.0Figure 4.8: Accuracy tests with negative-phase β scaling.1144.6. Contribution: Positive-Phase Temperature Scaling(a) Training at βeff = 3.0(b) Training at βeff = 4.0Figure 4.9: (Continued) Accuracy tests with negative-phase β scaling.1154.6. Contribution: Positive-Phase Temperature Scaling(a) Training at βeff=1.0(b) Training at βeff=2.0Figure 4.10: Accuracy tests with positive-phase β scaling.1164.6. Contribution: Positive-Phase Temperature Scaling(a) Training at βeff=3.0(b) Training at βeff=4.0Figure 4.11: (Continued) Accuracy tests with positive-phase β scaling.1174.7. Discussion: QAML Frameworkstep [18]. This can be seen in the successful convergence of all the modelsevaluated, as well as the similarity in the final testing accuracy within exper-iments using the same βeff value. This more closely resembles the experienceof training RBMs using purely classical algorithms.4.7 Discussion: QAML FrameworkQuantum-assisted training of both RBMs and general BMs is a new fieldof research in both the gate [185] and annealing models of quantum com-putation. QARBMs have been used in numerous studies cited throughoutthis chapter and Chapter 4, including potential demonstrations of speed-up [117, 172].While the gate model approach requires encoding a probability distribu-tion into a parameterized quantum circuit, quantum annealers can be seenas application-specific Boltzmann samplers. As quantum annealing devicesevolve, more qubits with lower noise may become available. In order to al-low proper evaluation and eventual adoption of these quantum computingdevices, the programming tools need to be developed in tandem with thehardware.This chapter presented the QAML framework we developed. We in-corporated new methods for the automatic gradient computation of graphswith intra-layer parameters, and the unique ability of altering the minor-embedding method while simultaneously modifying the topology of the mod-els. During the development of this implementation, we identified a commonobstacle in previous implementations: the limitations caused by negative-1184.7. Discussion: QAML Frameworkphase temperature scaling. We implemented and demonstrated a significantchange in the reliability of results obtained when using our training algo-rithm with positive-phase temperature scaling.An important outcome of the temperature scaling approach is that it al-lows studying the effect of changes in the model, dataset, and QAP, ensuringthat the variation seen in training accuracy is due to those changes, and notdue to changes in the utilization of the bias range. This is reflected by thedifferences in performance from 4.10a to 4.11b which can be attributed tothe change in βeff.The premise and contributions of this work are not meant to providean evaluation of performance between quantum and classical ML methods.However, it does make significant progress in developing the system andmethods that will eventually allow QAPs to be used to their potential. Fur-ther comparisons of the performance of quantum annealing devices againstclassical sampling methods can benefit from using the QAML framework,and positive-phase β scaling to accurately characterize their results.119Chapter 5Context-Awareness:Structure Information inQAMLSampling-based training of QAML models is a unique application of theQAP CAD flow. As presented in the previous chapter, there are importantpractical considerations when using QAPs to train Boltzmann machines.Two examples discussed in that chapter are (1) scaling the parameter β inthe parameter-setting stage and (2) calculating the expectation values ofeach node, instead of reducing to the lowest energy sample.In this chapter the focus is on the graph-embedding stage. Contextualinformation from the application becomes available during the conversionof the Boltzmann machine parameters onto the equivalent Ising graph. Werefer to this as structure-awareness. The term structure-awareness encapsu-lates the identification of structural properties of the graph formulations inQAML models, and their integration into the QAP CAD flow.For this work, we identified four structural properties that relate directlyto how the graph can be manipulated in the process of minor-embedding:120Chapter 5. Context-Awareness: Structure Information in QAMLVisible/Hidden nodes: In a BM, we can distinguish between visible orhidden nodes. Correct behaviour requires us to ensure that the number ofvisible nodes matches the size of the input, however, there is flexibility inthe number of hidden nodes. Also, during the positive-phase sampling, thevisible nodes are clamped and only the hidden nodes need to be sampled.Layered graphs: Conventionally, the field of ML uses layered networks.This is the basis of backpropagation in deep neural networks (DNNs), andthe CD-k training algorithm for RBMs (as described in Section 4.1.2). InQAML, this implies a distinction between minor-embedding methods forRBMs (Section 5.1) and general BMs (Section 5.2). Quantum-Assistedtraining of Restricted Boltzmann Machines (QARBM) allows for classicalinference, while the Quantum-Assisted training of general Boltzmann Ma-chines (QABM) uses the QAP during and after training, therefore requiringtwo minor-embeddings.Interchangeability: The assignment of nodes to chains can be inter-changed. This is also true for optimization problems, as long as the nodesbeing swapped have the same adjacency. This is prevalent in the densegraphs used in QAML. For example, in RBMs, nodes are interchangeablewithin the same type (i.e., visible or hidden). In general BMs, the enumer-ation of nodes is arbitrary as long as inputs in the dataset are “clamped” tothe appropriate nodes in the positive-phase.Malleability: Machine learning graphs can be modified, or pruned, with-out losing overall functionality. In the context of QAML, pruning a network121Chapter 5. Context-Awareness: Structure Information in QAMLcan be done to adapt the structure of a model subject to the availabilityand connectivity of the qubit fabric in a QAP. In classical ML, the idea ofpruning a network is typically motivated by a reduction in computation,with a small penalty on performance, measured in testing accuracy or us-ing other metrics. However, in QAML, pruning the model may result inimproving its minor-embedding, resulting in an improvement in the qualityof the sample distribution (making it more ”Boltzmann-like”). Therefore,counter-intuitively, pruning the model can counterbalance the fact that themodel is smaller. This is the subject of the experiments in Sections 5.1and 5.2.In general, the minor-embedding problem for bicliques (QARBM) andcliques (QABM) has been solved efficiently using systematic methods, asdescribed in Section 2.5.1. As an example, in the experiments in the pre-vious chapter, minor-embedding was done using the row/column bicliqueminor-embedding. For the specific networks in those experiments, it is pos-sible to efficiently find a balanced minor-embedding. In comparison, thelayout-aware methods in Chapter 3 would (1) not guarantee a balanced em-bedding, and (2) have the same results as a layout-agnostic method becausethe high density and symmetry of QAML graphs translates to trivial lay-outs (bipartite for bicliques, and rings for cliques). Therefore, path-searchheuristics will most likely find worse mappings and have longer run-time.Instead, the objective of this chapter is to propose and evaluate modifica-tions in the QAML CAD flow that simultaneously modify the model and itsminor-embedding, informed by the structural properties listed above.1225.1. Structure-Aware Minor-Embedding for RBMsFirst, Section 5.1 covers the implementation of structure-aware minor-embedding for QARBMs. Second, Section 5.2 explores the implementationof structure-aware minor-embedding for general QABMs. QABM implemen-tations open the opportunity of training a BM with an arbitrary topology,as long as there exists a minor-embedding onto the QAP device.5.1 Structure-Aware Minor-Embedding forRBMsThe minor-embedding of bicliques, as shown in Section 2.5.1, has been usedin much previous QARBM research [2, 18, 56, 57, 82, 90, 97, 102, 117,123, 156, 160, 161, 172, 174]. This is also the method used to obtain theresults presented in the previous chapter. However, if a straightforward rowand column minor-embedding cannot be found due to missing qubits and/orcouplers in the fabric, then these methods fall back to path-search heuristics.This section presents experimental demonstrations and analysis of theimpact of the minor-embedding quality on the performance of training al-gorithms for QARBMs. Motivated by the results of that evaluation, wedescribe modifications to the minor-embedding methods by applying knowl-edge of the structural properties of QAML models. Then, we demonstratethe trade-offs when “pruning” a QAML model, and how these trade-offsdiffer from what motivates the use of “pruning” methods in classical MLtheory.All the experiments presented below are made possible by the QAMLframework introduced in Chapter 4 and shown in Figure 4.5. The methods1235.1. Structure-Aware Minor-Embedding for RBMsfor model “pruning” in QAML that are presented below, make part of themodel embedding step of the programming flow, because they start from alarger model, but are informed by the QAP graph to determine which edgesand nodes to preserve before training.5.1.1 Heuristic vs SystematicTo further understand and motivate the incorporation of context-awarenessinto minor-embedding algorithms, this section compares the training perfor-mance of QARBM models mapped with heuristic and systematic methods.Intuitively, the embedding result from these two methods will differ in qual-ity (i.e., maximum chain length, average chain length, and homogeneity).However, the effect that this difference has on the QAP sample distributionand, as a result, on the capabilities of the training algorithm that uses thosesamples, has not been studied in previous work.Figure 5.1 shows a histogram of the chain length metric for three heuristicminor-embeddings of an RBM(64,64) onto the Advantage system4.1 devicewith different seeds. At the size of the D-Wave QAP chosen for these experi-ments, this method can result in very low quality embeddings, i.e., with verylong chains. In comparison, the Systematic embeddings of the RBM(64,64)have homogeneous chains of length 6. This size of model was chosen in orderto find a systematic mapping without “disjoint chains” to use as a reference.5.1.2 Evaluation: Heuristic vs SystematicThe RBM is trained on a simplified version of the 8x8 OptDigits dataset:binarized data with 8 classes. This is a similar setup to that in [18] and1245.1. Structure-Aware Minor-Embedding for RBMsFigure 5.1: Quality of heuristic embeddings.described in Section 4.2.1. This configuration demonstrates the classificationtask, where an 8 one-hot encoding of the label is included as part of theimage (i.e., Classes 4 and 9 are removed). Figure 4.4 shows a random subsetof the binarized OptDigits dataset. For each of these experiments, threemodels are initialized randomly and trained for 75 epochs on the trainingset (3054 images). A batch size of 1024 data points is used, which is alsothe number of samples collected from the QAP per batch. For repeatability,other characteristics and parameters of the dataset and training algorithmare given in Tables 5.1 and 5.2. The QAP configuration is the same as inTable 4.1, with an effective inverse-temperature βeff = 2.5.The choice of hyperparameters (Table 5.2) was made such that the train-ing results are consistent between all iterations and between all models.More complex training methods were not used to be able to isolate the ef-1255.1. Structure-Aware Minor-Embedding for RBMsfect of minor-embedding from the effect of the choice of hyperparameters.Small changes in learning rate (ϵ), weight-decay (λ) and momentum (η) canmake significant changes to the testing accuracy results, in the same waythat it would for classical ML training. Exploration of the hyperparameterspace in QAML training algorithms is at an early stage.Table 5.1: Dataset datasheet.Property ValueName OptDigitsLearning Task ClassificationData Size 8x8Sampler RandomTraining Set 3054Testing Set 1436Batch Size 1024Table 5.2: Training datasheet.Property ValueVisible Nodes 64Hidden Nodes 64Optimization function SGDLearning Rate (ϵ) 0.1Weight Decay (λ) 1e-4Momentum (η) 0.1Throughout training, at every epoch, the testing accuracy is measured onthe remaining 1436 images by clamping only the visible nodes with the image(no label), running a forward and backward pass of the RBM, and comparingthe probabilities obtained on the label nodes to the true label. These evalu-ations also include the mean absolute error (MAE) and the Kullback-Leibler1265.1. Structure-Aware Minor-Embedding for RBMsDivergence (DKL) between the training dataset and the samples collectedduring the negative phase at each epoch. Details on these metrics are pro-vided in Section 4.2.1. In classification applications, the testing accuracyalso quantifies the capability of the system (model and training method) togeneralize beyond the training dataset.Figure 5.2 presents the results for the three metrics; a bold line is theaverage and the shaded region is the standard deviation. As expected, thedifference in the embedding quality reflects directly on the performance ofthe training algorithm, with a slight lead in the average final testing ac-curacy, MAE and DKL. However, this evaluation also shows that, for allthree metrics, the Systematic embedding exhibits more variation. This hasa counterintuitive connection to the quality of the embedding, which havethe same quality for all Systematic embeddings, and high variation for theHeuristic ones. One possibility for this behaviour is that the long chainsin the heuristic-embedded models behave erratically and, therefore, do notcontribute to the overall performance. In those cases, the model is effec-tively biased towards a reduced space in which to optimize the parametersof the model. This is reminiscent of the “lottery ticket hypothesis” [64],which states that a larger model has more subnetworks that can be trainedtowards the optimization goal. In our experiments, more subnetworks aremade available from a larger number of reliable qubit chains.5.1.3 Adaption Methods for RBMsWith that in mind, instead of working with models with low quality chains,the training algorithm can benefit from “pruning” methods before training.1275.1. Structure-Aware Minor-Embedding for RBMs(a) Testing Accuracy. Higher is better.(b) MAE(vdata, vsamples). Lower is better.(c) DKL(Pdata ∥ Psamples). Lower is better.Figure 5.2: Comparison between systematic and heuristic.1285.1. Structure-Aware Minor-Embedding for RBMsThis section focuses on bringing context-awareness to the systematic bicliqueminor-embedding methods, by modifying the assignment of nodes to chains,informed by the adjacency of the device graph.Figure 5.3 shows an RBM(6,6) with a faultless minor-embedding and twocases of faults in the device that would cause a mismatch of the systematicminor-embedding. For each image, the corresponding RBM(6,6) graph isshown on the left side. The green nodes on the left are visible nodes, and theblue nodes on the right are hidden nodes. A toy version of the qubit fabricis on the right. This toy version can be characterized as a Chimera C(3, 3, 2)graph.6 This toy version helps with visualization, but is not representativeof any hardware implementation. In practice [48], minor-embedding for thePegasus and Zephyr topologies, as seen in Chapter 2 and Appendix A, canbe found on a corresponding Chimera graph and then transformed into theoriginal device topology. Therefore, studying the minor-embedding methodson Chimera informs the outcomes for the other topologies.For reference, Figure 5.3a is the optimal minor-embedding onto the tar-get graph. All chains have minimal length and satisfy the adjacency of theRBM(6,6). Figure 5.3b shows the case where a qubit on the perimeter ofthe target graph and a single coupler are defective; these defective qubit andcoupler are highlighted using red and dotted lines. As a result of the missingqubit and couplers, the RBM(6,6) is effectively pruned, meaning that theweights on those edges are “masked”, assigned a value of 0 and removedfrom the gradient calculation. This is symbolized by the red dotted edgeson the corresponding graph.6D-Wave’s Chimera devices use tile size t = 4 or C(m,n, 4)1295.1. Structure-Aware Minor-Embedding for RBMs(a) Systematic Minor-Embedding (Biclique)(b) Systematic Minor-Embedding with Trivial Prune(c) Systematic Minor-Embedfing with Disjoint ChainFigure 5.3: Systematic minor-embedding with faults.1305.1. Structure-Aware Minor-Embedding for RBMsOn the other hand, the qubit graph on Figure 5.3c is missing one qubitthat creates a disjoint chain, or an assignment of a model node to discon-nected qubits. In the model, this discontinuity in the chain is representedby a split in the corresponding node, with edges only on the remaining cou-plers. The red dotted edges in the graph are pruned, while the “disjointchain” creates two conditionally-independent nodes.Prefaced by the examples described above, we present four simple adap-tion methods that transform the model graph to deal with the presence ofthose discontinuities. As inputs, these methods take in the graphs of theQAP device and the RBM, and they return a mask (compatible with thePyTorch pruning methods) and the embedding that maps the RBM nodesto qubits. Figure 5.4 is a high level visualization of the process. A templategraph, i.e., a graph with the same dimensions as the device graph but with100% yield, is created and put through the systematic biclique embeddingalgorithm. The resulting embedding is then “adapted” to the faults in theactual device graph.Template Graph100% yieldSolver Graphfrom DWave APIBiclique Embedding(V,H)PruningMethodRBM(V,H)PrunedEmbeddingPyTorch MaskFigure 5.4: Adaption of a systematic biclique embedding of the graph modelto the locations of “gaps” in the target graph.1315.1. Structure-Aware Minor-Embedding for RBMsAdaption with disjoint chains (Adachi): One approach from previouswork [2, 56, 82] is to prune the edges corresponding to missing couplers, andtreat the “disjoint chains” as a single node. After collecting the samples fromthe QAP, the values from the “disjoint chains” are resolved using the samechain-break method as any other chain, as if they were connected. Theseimplementations have been shown to have negligible effects when only asmall number of qubits are missing, suggesting that the training algorithmcan train around these faults. Figure 5.5a is a representation of the adaptionmade to the RBM graph, when the same faults in Figure 5.3c are in the qubitgraph.Adaption with subchain pruning (Adaptive): As seen in Figure 5.3c,“disjoint chains” can create multiple portions or “subchains” along its axis.For the example graph, the missing qubits creates two subchains. Giventhe device graph and the biclique embedding, this method prunes away thesmall portions of all ‘disjoint chains”, and keeps the longest subchain, and itsconnections. If multiple portions of the same chain are equally long, one ischosen randomly. We then ensure that the choice of subchain preserves thevalidity of the model. Instances where the label nodes are not connected toany hidden node (in classification applications), or prunings resulting in dis-connected graphs would be considered unsuitable for training. Figure 5.5brepresents the resulting RBM graph from the faults in Figure 5.3c.1325.1. Structure-Aware Minor-Embedding for RBMs(a) Adachi‡ (b) Adaptive(c) Priority (d) RepurposeFigure 5.5: Representation of the adaptions made to the RBM graph. (‡)Proposed by [2].Adaption with node priority (Priority): The previous method canbe modified by rearranging the node-to-chain assignments. In an RBMmodel all visible nodes are indistinguishable, which allows any mappingfrom dataset to visible nodes. This additional structural information is usedto select which higher priority visible nodes can be swapped onto moreconnected qubit chains. A node-priority list is taken as a parameter of the1335.1. Structure-Aware Minor-Embedding for RBMspruning method, and a chain-priority list is made by sorting the chainsfrom most interactions (highest priority) to least interactions (low priority).This is particularly straightforward when an RBM is used in a classificationapplication. These networks have visible nodes that represent a one-hotencoding of the labels in the dataset, these are assigned the highest priority,and every other node is lower priority.Adaption with node repurposing (Repurpose): In order to recoverqubits lost in the basic Adaptive method, one further step is to re-purposethe lower connectivity subchains. First, assignments from visible nodes torows (or columns) of qubits can be swapped with the assignments of hiddennodes to columns (or rows), but only if there are as many hidden subchainsas there are visible nodes. Second, new hidden nodes can be created if thereare suitable subchains available. For example, in Figure 5.3c, the fracture isin a visible chain. In that case the embedding is chosen to be mirrored (i.e.,hidden and visible nodes are swapped) to make use of the additional sub-chain as a hidden node. Figure 5.5d shows the new RBM(6,7) graph withvisible and hidden nodes flipped, and one extra partially-connected hiddennode.5.1.4 Evaluation: RBM Training with PruningThis section presents the evaluation of RBMs when the models are pruned,and trained on the OptDigits dataset, as described in Tables 5.1 and 5.2.First, we describe the models that resulted from applying the adaption1345.1. Structure-Aware Minor-Embedding for RBMsmethods described above, when using the adjacency graph of the Advan-tage system4.1 D-Wave device to sample from the RBM(64,64). Second, asa baseline, we evaluate the changes in testing accuracy when we train thosepruned models classically using Gibbs-1 sampling. Lastly, we train all themodels on the Advantage system4.1 D-Wave QAP.At the size of RBM that was chosen for these experiments it is possibleto find a region of the D-Wave device such that an embedding can be foundwithout qubit imperfections. We call that the Biclique embedding and use itas a reference for performance in our experiments. Table 5.3 shows the chainmetrics of the Biclique and pruned embeddings found with the adaptionmethods. As opposed to the previous results from the heuristic method, theresults here have small variation, and are meant to demonstrate the effectof small changes to the minor-embedding that simultaneously change themodel. Due to the imperfections in an area of the device chosen for theseembeddings, the Adachi method created two pairs of “disjoint chains” (†),one pair (2 qubits and 3 qubits) for a visible node, and one pair (4 qubits and1 qubit) for a hidden node. The Priority method uses the same topologyas Adaptive, but swapped one label node into a more connected chain. TheRepurpose method (‡) created one additional hidden node from a disjointchain, resulting in an RBM(64,65).Gibbs-1 Training: The baseline evaluation consists of the classical train-ing, on the OptDigits dataset, of three models: the Biclique, and two levelsof pruning (i.e., with 24 and 52 edges pruned). The negative phase uses aGibbs-1 sampler with βeff = 1, and all other configurations of the training1355.1. Structure-Aware Minor-Embedding for RBMsTable 5.3: Quality of systematic embeddings.Method EdgesChain lengthpruned 6 5 4 3 2 1Biclique 0 128 0 0 0 0 0Adachi 24 126 2† 0 0 0 0Adaptive 52 126 0 1 1 0 0Priority 52 126 0 1 1 0 0Repurpose‡ 40 126 0 1 1 0 1algorithm are the same as those in Section 5.1.1. Figure 5.6 is the testingaccuracy for 75 epochs.Figure 5.6: Classical RBM testing accuracy with adaptions.These results are representative of experience with pruning using classicaltechniques. A smaller model, made of fewer trainable subnetworks, mayconverge slower towards the optimization goal, and is more likely to havelower accuracy.1365.1. Structure-Aware Minor-Embedding for RBMsQuantum-Assisted Training: The quantum-assisted evaluation consistsof the same training setup, on the five models discussed above: the Biclique,and four methods of structure-aware minor-embedding, resulting in differentlevels of pruning. All samples are collected from the Advantage system4.1,with the same configuration listed in Table 4.1. Figure 5.7 shows the testingaccuracy results throughout training.As the results show, even though there exists a Biclique embedding of theRBM network onto the device graph, better performance can be obtainedin two instances: when some edges (24) are pruned and disjoint chainsare preserved (i.e., Adachi), and when more edges are pruned, but withan additional hidden node (i.e., Repurpose). Those two adaption methodsshare the idea of repurposing, either by creating higher connectivity in RBMnodes through disjoint chains (i.e., Adachi), or by creating a wider hiddenlayer by assigning disjoint chains to multiple RBM nodes (i.e. Repurpose).Pruning of additional nodes (52 in total) (i.e., Adaptive and Priority)resulted in similar or lower testing accuracy at the end of the 75 epochscompared to the Biclique embedding. However, more variation is seen inthe training curves of the pruned models, resembling the classical trainingbehaviour seen in Figure 5.6.1375.1. Structure-Aware Minor-Embedding for RBMsFigure 5.7: QARBM testing accuracy with adaptions.These results highlight the difference in trade-offs that should be con-sidered when training RBM models with quantum annealers. Despite thereduction in the number of trainable parameters, choices made during theminor-embedding stage with awareness of the structural properties of themodel make it possible to train with better results than using a Bicliqueversion.The improvement in testing-accuracy when using the Adachi methoddemonstrates the resilience of the training algorithm to faults in the qubitfabric. If a suitable minor-embedding exists (i.e., no disconnected graphs),then the Adachi is sufficient. This observation is complementary to thefindings of this work, which suggest that a more informed (structure-aware)1385.1. Structure-Aware Minor-Embedding for RBMsapproach with smaller models, may provide better results than a naive Bi-clique minor-embedding.5.1.5 Related WorkTwo other approaches have been considered in related work, that createminor-embeddings of RBMs beyond the biclique method:Maximal biclique embedding (Koshka): In [99], the goal is to con-struct a maximum “embeddable” RBM model on a fixed fabric. The row/-column approach is modified such that a new RBM node is created whenevera chain is found to be broken. This method is useful for the characterizationof a device, and demonstration of the training capabilities in QAML sys-tems. This approach would not be efficient in a real-world scenario, wherethe visible nodes are required to match an input size, and the remainingqubit resources could be used for hidden nodes.Unit Dropout (Salmenpera¨): The classical ML precedent of Dropoutis a widely adopted method of neural network pruning [126], which wasdeveloped to avoid over-fitting of the models under training. In [156], theauthors describe an initial implementation inspired by Dropout for quantum-assisted RBMs, along with other modifications to the CAD flow, referredto as “software techniques”. However, the Dropout method described inthat work is not informed by the qubit fabric, and focuses on pre-trainingrandomly pruned models (“thin” models).1395.1. Structure-Aware Minor-Embedding for RBMs5.1.6 DiscussionQuantum-assisted training of RBMmodels with quantum annealers has beendemonstrated in this section. This type of analysis is still in its early stagesof evaluation against classical methods. As quantum computing technologyevolves, simultaneous efforts in the development and improvement of theprogramming CAD flow are necessary to accurately evaluate the speed-uppotential of these new technologies.Using the QAML framework described in Chapter 4, this section showed(1) the importance of the minor-embedding quality in the use of QAPsas RBM samplers, (2) methods to adapt the RBM topology and minor-embedding to the faults in the qubit fabric of real-world QAPs (what we referto as structure-aware minor-embedding), (3) the changes in testing-accuracycaused by the simultaneous changes in topology and minor-embedding.Context-awareness of the QAML structural properties found in RBMmodels presents an opportunity to obtain better sampling performance froma QAP. This is an important observation that motivates the use of smallermodels, properly adapted to the qubit fabric, instead of the development ofnew methods to find the minor-embedding of cliques onto the device qubitgraph.We believe that the use of “disjoint chains” with the Adachi methodrequires further research. As seen in Figure 5.5, the portions of chainscreated in that method are conditionally independent from each other, andthe value is reconstructed from a simple majority vote over the full lengthof the chain. Other sample resolution methods may be preferable.1405.2. Structure-Aware Minor-Embedding for General BMs5.2 Structure-Aware Minor-Embedding forGeneral BMsClassical machine learning relies on the efficient computation of gradientsthat is available on layered networks. For these networks, the capacityto “learn” and generalize grows with the number of trainable parameters(weights, or linear and quadratic biases), which is a function of the number oflayers (in deep learning models) and/or of the “width” (number of nodes) ineach layer. An alternative approach is to use a graph with intra-layer edges,increasing the connectivity compared to a biclique (layered) graph. Thismay provide better ability to sample from a target distribution, sometimesreferred to as having “more representational power” [104].As shown in Section 4.1, the theory behind the training algorithms forBoltzmann machines is not limited to the RBM model. RBMs are a sub-class of the general BM model, designed such that an efficient (approximate)sampling method can be used in both training phases (positive and nega-tive), as well as during the inference stage in deployment. Quantum-assistedtraining, on the other hand, has been demonstrated for more complex net-works, by using the QAP as a sampler in both training phases and infer-ence [18, 52, 97, 103, 104, 160]. These examples include models such as thefully-visible clique, Limited Boltzmann Machines (LBMs), and the generalBM, i.e., with fully-connected visible and hidden nodes.In practice, in order for the QAML framework to support training generalBMs, it requires the calculation of the expectation values for the visible-hidden product, as seen in Equation 4.16, as well as the expectation values1415.2. Structure-Aware Minor-Embedding for General BMsfor visible-visible and hidden-hidden interactions:⟨vˆivˆj⟩model ≈1SS∑s=1vˆ(s)i vˆ(s)j (5.1)〈hˆihˆj〉model≈ 1SS∑s=1hˆ(s)i hˆ(s)j , (5.2)which are used to compute the gradients of the intra-layer weights:1|D|D∑d=1∂ lnL(Θ|y(d))∂vvij∝ ⟨vivj⟩data − ⟨vivj⟩model (5.3)1|D|D∑d=1∂ lnL(Θ|y(d))∂hhij∝ ⟨hihj⟩data − ⟨hihj⟩model . (5.4)Like RBMs, BMs can be embedded onto a target graph in two ways: (1)heuristic techniques (e.g., minorminer or the method described in Chapter 3of this thesis), or (2) systematic clique embedding methods, which can usethe adaption methods from Section 5.1.3 to account for missing couplers andqubits.The first method may provide the best use of qubits for sparse prob-lem graphs, however, the embeddings may suffer from large and unequalchain lengths. In addition, the embedding times for graphs that are notsparse may be significant, making it less desirable for the application in thischapter. Using a systematic embedding of a clique can be fast (especiallyif cliques of various sizes can be pre-computed and cached) and such em-beddings may have equal chain lengths which improve the quality of the1425.2. Structure-Aware Minor-Embedding for General BMssample distributions. In the experiments in this section, we use the cliqueembedding approach, but provide a comparison to the heuristic approach inSection 5.2.4.Removing the restriction that the problem graph needs to be an RBM,leads to a huge potential design space. Any graph topology can be used,only limited by the ability to find its minor-embedding. In turn, becauseany graph topology can be mapped onto a clique, the lower-bound limit isthe number of nodes in the largest clique minor-embedding on the device.Bigger graphs with generic topologies may also be used, but will incur inexpensive minor-embedding run-time.This exposes a continuum of potential network architectures, rangingfrom sparse networks to extremely highly connected networks (and at anextreme, cliques). A thorough exploration of the “graph continuum” is en-abled by the QAML framework, but a complete study of potential topologiesis beyond the scope of this work. Being able to determine the best graphtopology is a challenge specific to each dataset and use case, and is part ofthe application-design stage.Instead, this work is focused on modifications to introduce structure-awareness into the minor-embedding of general BMs, including the evalu-ation of weight “pruning”. The latter is done with the intuition that as aQAML model is pruned, the resulting qubit chains resulting from the minor-embedding methods, can provide better quality samples, at the expense ofa smaller model. This is, as its the case for QARBMs, contrary to thetrade-offs from “pruning” classical models.As briefly described in Section 4.2, there are some practical consider-1435.2. Structure-Aware Minor-Embedding for General BMsations necessary for training QABMs that are not part of the QARBMalgorithms. The next sections in this chapter describe those differences indetail. Then, following the same evaluation strategy as QARBMs, we firstcompare the heuristic and systematic embedding approaches and demon-strate the importance of the chain metrics, with a new perspective on themultiple instances minor-embedded onto the QAP. We follow this with acomparison between different levels of edge pruning.5.2.1 QABM negative-phase samplingThe computation of the expectation values in the negative phase of traininga general BM is mostly the same as that of an RBM. The parameters ofthe model are properly submitted to the QAP (i.e., converted to Ising andscaled), and the samples are averaged over the number of reads. The onlymodification in this flow is that the use of an effective inverse temperature(βeff) can be avoided, because both probability distributions are scaled by(βDW), and both parameters use the automatic scaling. In our experiments,the difference in the scaling factor between the negative (α−) and positive-phase (α+) is negligible. However,it is possible that future work with largermodels will require a similar strategy to the one described in Section 4.6.5.2.2 QABM positive-phase samplingIn order to collect the samples necessary for the positive-phase of training,“clamping” of the input nodes is necessary. In RBMs, this is done by per-forming the classical computation of the forward pass from visible to hiddennodes, using Equation 4.1. When the BM has hidden-hidden connectivity,1445.2. Structure-Aware Minor-Embedding for General BMsafter clamping the visible nodes, there exists a conditional probability be-tween hidden nodes, which forms the hidden nodes subgraph. The hiddennodes subgraph is constructed by adding the contribution of each visiblenode (vi) to the linear biases of all neighbouring hidden nodes (cj). Thelinear biases of the visible nodes (ai) are ignored. The contributions arethe product of the “clamped” value and the quadratic bias on the corre-sponding visible-hidden edge (viwij). Figure 5.8a shows the original graphused in the negative phase, and Figure 5.8b shows the new parameters ofthe model during the positive-phase. This is a standard approach used inQABM sampling, and described in [160].(a) Negative-phase graph (b) Positive-phase hidden node subgraphFigure 5.8: Creating the hidden node subgraph.For the purpose of this work, as it relates to minor-embedding, thismeans that two mappings, from BM nodes to qubits, must be made duringthe graph embedding step. The most simple approach for the positive phaseis to reuse the minor-embedding of the original graph (in this example aclique embedding of size V + H), and only map the hidden nodes onto1455.2. Structure-Aware Minor-Embedding for General BMsit. This is sufficient for small demonstrations of the training algorithms inQAML. However, structure-awareness of the types of graphs that are usedin this application allow for a more efficient use of the qubit fabric.5.2.3 Batched Quantum SamplingGenerally, during training, the algorithm loops through the training datasetin batches, or subsets of the dataset collection. The size of each batch, inclassical ML, is chosen by the user such that it maximizes the efficiency ofresource utilization for the underlying computing systems (e.g., CPU, GPU,TPU). These systems are designed to efficiently compute matrix operationson multiple input vectors, but have architecture-specific vector size limits.A similar optimization can be achieved in the use of QAPs for Boltz-mann sampling. In the negative phase, multiple copies of the clique maybe minor-embedded onto the device. Samples are collected from all copies,and averaged altogether. This is referred to as Parallel Quantum Anneal-ing [135, 156], and is equivalent to obtaining a larger number of reads withgauge transformations. Sampling from multiple devices simultaneously ispossible, but we assume that QAP availability is, and will remain scarce.Typically, in the positive phase, the approach to obtain these samplesis to call the quantum annealer for each input set, in the form of a hiddennode subgraph. However, this approach requires waiting for the samples ofeach input in the dataset to be returned, even if parallel quantum annealingis used. Instead, we use Batched Quantum Sampling, a method developedspecifically for this research in which multiple copies of the hidden node sub-graph are embedded onto the quantum annealing device, and each instance1465.2. Structure-Aware Minor-Embedding for General BMsis assigned an input vector.The first modification to the training flow is that the minor-embeddingstep for the positive-phase (the hidden node subgraph) is computed beforeselecting the training batch size. This is because a new minor-embeddingmethod is put in place to “harvest” as many cliques as possible from thetarget device. This is done by repeatedly calling the embedding method,with the qubits from previous embeddings removed from the QAP graph.This results in a set of clique minor-embeddings of the size of the hiddennode subgraph. The number of clique embeddings is the size of the trainingbatch. Effectively, each instance is a different problem, which is differentfrom the parallel quantum annealing approach.Figure 5.9 is an example of the positive-phase batched embedding for ahidden node subgraph of size H = 16. In this case the “harvesting” loop,using the systematic method, is able to find 84 instances. This means thatthe training algorithm is able to run with a batch size of 84 inputs.Figure 5.10 is an example of the negative-phase parallel embedding ofa 52 node complete graph (i.e., 36 visible + 16 hidden). The number ofinstances in the negative-phase is less significant, but it can provide noisemitigation due to the redundancy on each node; i.e., when averaged overall samples and all instances, the noise associated to physical qubits canbe reduced [136], or simply provide more samples per anneal run. In thiscase the “harvesting” loop, using the systematic method is able to find 10instances.Even though the systematic method can reliably find clique embeddings1475.2. Structure-Aware Minor-Embedding for General BMsFigure 5.9: Batch embedding of 84 instances of the 16 hidden nodes in thepositive-phase.1485.2. Structure-Aware Minor-Embedding for General BMsFigure 5.10: Batch Embedding of 10 instances with 52 nodes (i.e., 36 visible+ 16 hidden) in the negative-phase.1495.2. Structure-Aware Minor-Embedding for General BMswith homogeneous chains, the “harvesting” loop is not optimal7 due to therandomness in the selection of the starting chains, as described in Sec-tion 2.5.1. For the purpose of this work, the emphasis is in obtaining a“good” number of instances fast.Batched quantum sampling is essential for the proper evaluation of QABMalgorithms, because there is a significant run-time penalty in running indi-vidual hidden node subgraphs. Future work on the quality of the clique“harvesting” method could provide run-time improvements to the resultspresented here. However, given that the graphs we tested are cliques, theimpact on performance is more suitably evaluated by “pruning” the models,as is shown later in this chapter.5.2.4 Heuristic vs SystematicFor reasons outlined earlier, most of our experiments in this section usethe clique embedding approach. However, analogous to the experiments inSection 5.1.1, we evaluate the minor-embedding of QABMs using the sys-tematic clique embedding approach, compared to the heuristic method; i.e.,minorminer. In this scenario, however, both methods are used to “harvest”clique embeddings. We would expect that the heuristic approach gives em-beddings with imbalanced and potentially large chain-lengths. So we usethese characteristics to measure the impact of chain-length on the perfor-mance of the training algorithms.Figures 5.11 and 5.12 give one example of the chain length statistics from7The optimal “harvesting” method would find the maximum number of clique embed-dings of a given size in a QAP graph.1505.2. Structure-Aware Minor-Embedding for General BMs(a) Positive phase (52 nodes) with 93 instances(b) Negative phase with 9 instancesFigure 5.11: Heuristic minor-embedding quality.1515.2. Structure-Aware Minor-Embedding for General BMs(a) Positive phase (16 nodes) with 84 instances(b) Negative phase with 10 instancesFigure 5.12: Systematic minor-embedding quality.1525.2. Structure-Aware Minor-Embedding for General BMsthe heuristic and systematic methods, respectively. Each figure representsone phase embedding; i.e., positive (16 nodes) or negative (52 nodes). The Yaxis is the number of chains per instance in each embedding. Each box plotshows the mean (▲), median line, lower to upper quartile boxes, whiskers tolast value within one interquartile range after the quartile, and the outliers(◦).The results in Figure 5.11a show the statistics for the positive-phase (16nodes) batched embedding of 93 instances using the heuristic method. Eventhough many of the instances have a high number of 2-qubit and 3-qubitchains, the long tail of longer chains is evidence of how imbalanced and longsome chains are. The heuristic method may have the capacity of findingmore instances than the systematic method in the unused resources of thegraph (84 instances with the systematic method). However, more embed-dings is not necessarily an improvement if those chain lengths are imbalancedand relatively long. Similar results are seen for the bigger negative-phasegraph; i.e., 52 nodes.In comparison, the statistics of the chain lengths found using using thesystematic method for each phase are shown in Figure 5.12. Clearly, theresults are more balanced, and chain lengths are shorter. The systematicmethod used for these experiments may be improved upon to find more in-stances but that is beyond the scope of this work. More instances wouldimply a larger batch size, mostly affecting run-time; the quality of the sam-ples would not change significantly.To better understand the impact of these chain length distributions,we considered the general BM with 36 visible nodes and 16 hidden nodes,1535.2. Structure-Aware Minor-Embedding for General BMstrained on the BAS(4,4) dataset. The model is embedded onto, and sampledfrom the publicly available D-Wave Advantage System4.1 QAP. Each callto the QAP device consists of 400 reads, or 100 reads with 4 spin reversaltransformations.Due to the connectivity of the clique graphs, the size of the dataset issmaller than the one used in QARBM. Therefore, instead of measuring test-ing accuracy against a very small testing set, we train on a subset of thedataset, and quantify training performance against the complete datasetusing the scoring methods available for the synthetic BAS dataset, as de-scribed in 4.2.1. These metrics are (1) precision, or the ability of the modelto provide samples from the input dataset, (2) recall, or the ability of themodel to provide a representative distribution of the dataset, and (3) overallscore, which is a combination of (1) and (2).As a baseline, we also train the models using simulated annealing sam-pler. SA is only used here as an alternative solver, given that an exactsolver, like the one used in Section 4.5 becomes impractical, and no efficientapproximation (like Gibbs-1 sampling for RBMs) exists. Moreover, the SAsampler is intended as a point of reference and not as a demonstration ofperformance. SA is understood to only work in the presence of high degen-eracy of the energy barriers [88], when many paths are available betweenlow-energy configurations. High energy barriers result in biased samples.Figures 5.13 to 5.15 show the evaluation of these methods. Quantum-assisted training with each embedding method (i.e., with heuristic and sys-tematic) and simulated annealing (SA) are used on three randomly initial-ized BMs; the random seed used for the BM weights is also used for the1545.2. Structure-Aware Minor-Embedding for General BMsFigure 5.13: Heuristic vs systematic minor-embedding, and simulated an-nealing precision.embedding heuristics. Figure 5.13 shows the sampling precision throughouttraining. As the graph shows, consistently, using SA to train BMs classicallyresults in high precision sampling when compared to both quantum-assistedsolutions.On the other hand, Figure 5.14 conveys a different characterization of thesamples from the three systems. When comparing the recall, both quantum-assisted versions outperform the classical solution. At this size of the modelit may be possible to tune an SA sampler to provide a better characterizationof the Boltzmann distribution, but we highlight this implementation to show1555.2. Structure-Aware Minor-Embedding for General BMsFigure 5.14: Heuristic vs systematic minor-embedding, and simulated an-nealing recall.the “symptom” of a biased sampler in training.Between the heuristic and systematic methods, even though the precisionmetric is similar, there is a large difference in recall and, as a consequence, onthe final score metric. The low quality of the chains in the heuristic minor-embedding (longer and with more variation) results in poor quality samples(lower fidelity to the Boltzmann distribution). As a result, the samplescollected from the heuristic embeddings has lower recall, which means worsegeneralization.1565.2. Structure-Aware Minor-Embedding for General BMsFigure 5.15: Heuristic vs systematic minor-embedding, and simulated an-nealing score.5.2.5 Pruning ratiosWe next investigate the impact of pruning to demonstrate the potentialof networks with connectivity less than a full clique. We used a systematicminor-embedding and varied the amount of pruning. Similar to the adaptiveminor-embedding methods demonstrated for RBMs in the previous section,“pruning” for BMs is possible due to the malleability of the QAML models;the training algorithm “works around” the edge deletion and is able to trainmodels by ignoring the gradients between disconnected nodes.1575.2. Structure-Aware Minor-Embedding for General BMsThe use of the adaption methods from Section 5.1 becomes more complexbecause of the positive-phase sampling and the use of batched quantumsampling. If a minor-embedding is adapted to the existing edges in a regionof the QAP, there is no guarantee that more than one instance of thatsame graph can be found in other regions of the QAP graph. While wecould eliminate the use of batched quantum sampling, we feel this methodis essential for good performance of the training algorithm.Instead, the analysis of the effects of pruning on the complete BM mod-els resembles more its classical counterpart. That is, starting from themaximum connectivity, in this case the clique (or fully-connected) graph,and selecting a percentage of edges to prune away. For these experimentswe chose two pruning levels 80% (0.8) and 70% (0.7) of the visible-hiddenedges. Which results in changes in the minor-embedding of the instances inthe negative-phase.The impact of different pruning ratios is evaluated on the same BMwith 36 visible nodes and 16 hidden nodes used above, and trained on theBAS(4,4) dataset. The K52 graph has 1326 edges, 576 of which are betweenthe visible and hidden nodes. The model is embedded onto, and sampledfrom the publicly available D-Wave Advantage System4.1 QAP. Both thepositive and negative phases are sampled using multiple instances as seenin the embeddings from Figures 5.10 and 5.9.The evaluation of changes in performance in relation to the pruningratio is similar to the one presented above. The experiments include threerandomly initialized instances of each BM: one complete BM and two withdifferent percentages of edges removed. These are trained with both the1585.2. Structure-Aware Minor-Embedding for General BMsquantum-assisted and the simulated annealing samplers. The SA sampler isused to demonstrate that pruning does in fact affect performance as expectedin classical training.Figure 5.16: Simulated vs quantum annealing precision with pruning.As the results show, the training performance between classical andquantum-assisted has the same trend as the previous experiment. SA sam-plers are biased towards individual solutions, i.e., have high precision, asseen in Figure 5.16. Meanwhile, training with QA samplers has a lower pre-cision, but significantly better recall ; samples from the dataset are encodedinto different low energy states.1595.2. Structure-Aware Minor-Embedding for General BMsFigure 5.17: Simulated vs quantum annealing recall with pruning.For the SA-trained models, as the model is pruned, precision and, to alesser extent, recall are reduced. This is in agreement with results in classicalmachine learning. For the objectives of this work, the comparison betweenthe different levels of pruning of the quantum-assisted trained models, alsoreveals changes in performance, however, the trade-off in pruning for QABMis different from classical.First, in Figure 5.16 there is a small but noticeable separation betweenthe pruned models (QA 0.8 and QA 0.7), and the complete model (QA).Figure 5.17, presents a different, counter-intuitive result if only the size of the1605.2. Structure-Aware Minor-Embedding for General BMsFigure 5.18: Simulated vs quantum annealing score with pruning.model is considered. As edges are pruned the recall improves in convergencespeed and final result.5.2.6 Related WorkPrevious publications have addressed the idea of the “graph continuum”in different ways [52, 103–105, 123, 174]. However, the batched quantumsampling and the idea of pruning for quantum-assisted Boltzmann machinesto evaluate its effect on the minor-embedding cost are novel.1615.2. Structure-Aware Minor-Embedding for General BMsNative graph For example, researchers have suggested that the nativegraph of the D-Wave devices can be the graph of the Boltzmann machine [123,174]. At the time of that publication, the Chimera graph was used to demon-strate those principles, but that approach can easily be translated onto newertopologies/architectures. Even though this approach guarantees the highestquality samples from each node, the limited connectivity of the QAP graphsmay not be suitable as a network topology. Future work on this avenue isimportant, and could include the design of new QAP architectures specificto BM training.Limited Boltzmann Machine (LBM) In a series of publications [103–105], Liu et al. have explored the use of Limited Boltzmann Machines(LBMs), i.e., RBMs with some edges between hidden nodes. The connectiv-ity between hidden nodes is not complete, but depends on the topology of thetarget device (e.g., Chimera, Pegasus, Zephyr). LBMs were proposed earlier,but only theoretically and without alterations to the minor-embedding [52].LBMs provide more trainable parameters, which may lead to better per-formance [104]. The quantum-assisted training mechanism for LBMs sharesmore similarities with other complex BMs than with RBMs. i.e., both thepositive and negative phase collect samples from the hidden node subgraphwith the QAP, with an additional backward pass to sample from the visiblenodes in the negative phase. The last step takes advantage of the sameconditional independence used in the classical Gibbs sampling.The work in [105] effectively modifies the minor-embedding of LBMs ontoqubits through dynamic topology reconfiguration. This approach preserves1625.2. Structure-Aware Minor-Embedding for General BMsthe structure of the embedding, while the mapping of nodes to chains ismodified throughout training. These swaps are made to stimulate entropyon each node. However, performing this dynamic entropy-based remappingat every epoch may incur a significant impact in run-time.In comparison, the work described in this section is aimed at highercomplexity graphs, i.e., also including visible-visible edges, and starting fromthe fully-connected BM. The goal is to demonstrate modifications in theminor-embedding methods at the highest complexity, and to make use ofthe QAP devices in tasks that are not feasible with classical computing.5.2.7 DiscussionThe potential of QAML becomes more evident when working with topologiesthat are more complex than the traditional bipartite (layered) networks.Layered networks have been the foundation of classical machine learningsince the invention of backpropagation. However, choosing those topologiesis a reflection of the limitations of classical auto-differentiation algorithms,and not a design choice. The topology of the graph is not a fundamentallimitation for QABM training.However, because of the limited connectivity between qubits in QAPs,the complexity of a graph makes the minor-embedding less efficient as itapproaches maximum occupancy of the qubits. i.e., longer chains and morechain interactions. This work outlined the steps to efficiently minor-embedmultiple copies of QABM models onto a QAP, to sample from multipleinputs in the positive phase and collect multiple samples in the negativephase. Moreover, the malleability of QABM models is a structural property1635.3. Discussion: Structure-awareness in QAML minor-embeddingthat can be used to prune the models.Using a traditional random pruning method similar to those in classicalML, different QABM models resulted in a change in performance. As ev-idenced in the previous section and Chapter 3, changes in the model, andtherefore changes in the minor-embedding may result in better quality sam-ples. Therefore, pruning for QAML models offers different trade-offs fromits classical ML counterparts (e.g., Dropout [126]).Whereas classical ML pruning is motivated by power optimization, pre-training [126], or to reduce over-fitting. Pruning of QABMs is used here asa means to study the behaviour of the training algorithms under simulta-neous changes of the model and its minor-embedding. Both of the findingsfrom this section, (1) batched sampling and (2) the impact of pruning, arethe result of a context-aware approach at the minor-embedding step of theQAP CAD flow. The structural properties of the QAML application fieldallow for modifications that make significant progress in (1) enabling effi-cient run-times of the training algorithms with QAPs, and (2) provide anunderstanding of the trade-offs involved in designing BM network topologiesfor QABM applications.5.3 Discussion: Structure-awareness in QAMLminor-embeddingThis chapter covered two major areas of research in the QAML field. Quantum-assisted training of both RBMs and general BMs has been demonstrated innumerous proof-of-concept implementations, but is not yet ready for practi-1645.3. Discussion: Structure-awareness in QAML minor-embeddingcal use in real-world applications. We believe that further understanding ofthe training mechanisms and the further development of the software stack,or CAD flow, are essential.Furthermore, RBMs and general BMs should both be considered goingforward. While it is true that general BMs may offer more representationalpower only achievable through specialized sampling devices, the ability toperform inference classically on RBMs suggests that those models are closerto practical demonstrations of advantage in the near future [117, 172].With that in mind, we evaluated the training behaviour of RBMs andgeneral BMs under changes in the minor-embedding quality, to assert theimportance of that programming step for QAPs. Then, for both mod-els, we described the idea of incorporating structure-aware modifications inthe minor-embedding methods, and provided examples that simultaneouslyprune the topology of the models.The evaluation of those modifications demonstrated that there are trade-offs in the quality of results (testing accuracy or sampling score) that differfrom the experience of pruning for classical ML; in classical ML, pruninga model is motivated by the use of fewer resources while tolerating a de-crease in performance. Instead, a pruned QAML model may result in betterutilization of the qubit resources which translates into better training per-formance. We believe this is a result of better fidelity in the sampling of theBoltzmann distribution.Structure-awareness in the minor-embedding of QAML models shouldalways be considered in the implementation of QARBM and QABM trainingwith quantum annealers. That is, the choice of the topology of the network1655.3. Discussion: Structure-awareness in QAML minor-embeddingneeds to consider the impact of both the number and connectivity of thenodes, as well as the quality of the chains onto which they are mapped.Currently, demonstrations of RBMs and BMs target full connectivity of thenetworks (complete-bipartite or complete), however, an interesting approachwould be to co-design networks and their minor-embedding, by integratingawareness of the application.166Chapter 6ConclusionsQuantum computing is a new computing paradigm. Like other paradigms,it requires a computer-aided design flow that provides potential solutionsto user-designed problems. For most technologies of QC, one major stepin this flow is the process of mapping logical qubits onto the physical qubitgraph; also called transpilation [170]. For quantum annealing devices, whichis a specialized model of quantum computing intended as an optimizationmetaheuristic, this mapping is a minor-embedding of the problem graphonto the target graph. The quality of these mapping algorithms have ameasurable impact in the quality of the samples obtained.This work identified two types of contextual information that can aid themethods used to obtain those minor-embeddings: (1) layout (or location)information available in the problem, or created from the adjacency of thegraph, and (2) structural properties specific to the use of quantum annealersin the training loop of QAML models. Additionally, in order to be able toexplore the latter (structure-awareness), we developed a QAML frameworkto perform classical and quantum-assisted training of various configurationsof restricted and general Boltzmann Machines.1676.1. Layout-Awareness6.1 Layout-AwarenessLayout-awareness, when applied to the minor-embedding of optimizationproblems can provide a significant gain in the success ratio of path-searchheuristics. Without layout-awareness, the heuristic methods start from arandom assignment of nodes to qubits. Instead, using the 2D location infor-mation, projected onto the qubit fabric, layout-awareness reduces the searchspace and makes it easier to resolve routing conflicts.In our experiments, the time spent on mapping per-node was 19% faster,with better chain metrics (16% lower maximum and 3.6% lower averagechain length), and sustained success rate ≥ 93%. In comparison, the layout-agnostic approach resulted in a success rate of 23% for our biggest bench-mark. The success rate is a significant indication of performance for tworeasons, (1) solving congestion earlier in the algorithm means that the usercan allocate more time on optimizing the results, instead of spending it onfinding one valid solution, and (2) minor-embedding heuristics are usuallyexecuted multiple times and only the “best” solution is chosen, having ahigher success rate means that the user can select from a broader set ofmappings using their own quality criteria.6.2 QAML FrameworkThroughout the development of the QAML framework we identified a weak-ness in the standard training algorithms of QARBMs. We developed anddemonstrated the use of positive-phase temperature scaling, a new way toincorporate an estimate of the temperature of the distribution provided by1686.3. Structure-AwarenessQAPs.Through a set of experiments we concluded that the use of positive-phase temperature scaling is essential when training QARBMs with QAPs.Variations in performance (e.g., testing accuracy or distance to a Boltzmanndistribution), caused by an increase in quantization error in the standardpractice of negative-phase temperature scaling, have prohibitive effects inthe training algorithm. Models with negative-phase temperature scalingresult in low testing accuracy, including models that do not converge (i.e.,∼ 50% testing accuracy after 200 epochs), or overflow of the bias rangesduring the training iterations. Our method allowed 100% of the models weconfigured to properly converge towards a ∼ 95% testing accuracy with allother training hyperparameters set equally between experiments.6.3 Structure-AwarenessWe evaluated the impact of minor-embedding quality on the quantum-assisted training behaviour of both RBMs and general BMs. For both ofthose configurations we compared the minorminer heuristic and the corre-sponding systematic methods for bicliques and cliques. As expected, withthe same size of model, the quality of the minor-embedding result has aproportional impact on the performance of the training algorithms; i.e., inthe testing accuracy in a classification task, and the scoring metrics of asynthetic benchmark.Our investigation into context-awareness for QAML training algorithmsidentified four structural properties in the models, that can be incorporated1696.3. Structure-Awarenessinto the qubit mapping algorithms:a) Nodes are distinguished between visible and hidden, which have dif-ferent requirements when mapped onto qubits. For example, BatchedQuantum Sampling can be used for the hidden nodes subgraph.b) QAML modes can use layered graphs for efficient classical inference.Bicliques have an efficient systematic minor-embedding.c) The assignment of nodes to chains can be interchanged as long as theyhave the same adjacency. Therefore, visible nodes assigned to labelscan have priority in the minor-embedding.d) Edges from machine learning graphs can be removed, without losingoverall functionality. This “pruning” of the graph can be done to adaptthe topology of the graph to faults in the qubit fabric, or as a strat-egy to find “thinner” models, which, due to their minor-embedding,provide better performance under training.With that in mind, we developed structure-aware modifications to theminor-embedding methods for QARBMs and BMs. In RBMs, consideringthat only the negative-phase is sampled from from the QAPs, we devisedadaption methods that take into account the faults in the qubit fabric, andsimultaneously modify the topology of the graph. In general BMs, we in-troduced the batched quantum sampling, and the capability of the QAMLframework to randomly prune away edges of the network. In our experi-ments, we evaluated all these contributions using our QAML, and reportedthe training behaviour.1706.3. Structure-AwarenessSeveral takeaways can be derived from those experiments:Malleability: The use of adaption methods to tolerate faults in the qubitfabric are a strong demonstration of the malleability of the QAML models,“pruning” methods informed by the qubit topology can allow better uti-lization of a QAP device, compared to methods that only target a perfectminor-embedding.Clique “harvesting”: Despite the existence of heuristic methods able to“harvest” large numbers of instances in a minor-embedding loop, we showedthat it is preferable to focus on systematic minor-embedding methods thathave short and homogeneous chain lengths.Pruning trade-offs: Opposite to the intuition of pruning for classical MLapplications, we showed that pruning of QAML models is motivated by dif-ferent trade-offs. Instead of using a pruning method as a means to use fewerresources, at the expense of lower performance, pruning for QAML shouldbe an architecture and minor-embedding perspective. In QAML, it may bepreferable to have a smaller model, to improve performance, if that modelcan provide higher quality samples.Further development of specific algorithms targeting location or structuralinformation are important in this area of research. Other applications,topologies, and hybrid strategies are available in quantum computing, whichmay benefit from the use of contextual information during the mapping stageof nodes onto qubits. Furthermore, context-awareness in other stages of the1716.4. Applicabilityprogramming flow (e.g., parameter setting, anneal scheduling, and sampleresolution) may have significant impact in the run-time and sample fidelityfrom QAPs.6.4 ApplicabilityEven though the work presented here has been developed to target QAPsand the qubit fabrics of commercial D-Wave devices, the ideas and contribu-tions are not limited to those specific architectures. The programming flowof gate-model or circuit-model quantum computers is a potential target ofthe methods described throughout this dissertation.The most common implementations of the gate-model quantum com-puting model are also based on superconducting qubits [61]. As such, thesedevices are built with a physically limited connectivity which requires amapping of logical qubits onto physical qubits. Fundamentally, the map-ping problem differs in the way that a qubit connectivity is “extended”. i.e.,while QAP embeddings use a one-to-many mapping from logical to physicalqubits, gate-model qubits are mapped one-to-one, followed by the insertionof a series of 2-qubit SWAP gates into the quantum circuit to change eachqubit adjacency during execution.The ideas described in this work can generally be translated to have sim-ilar outcomes on the gate-model qubit mapping problem. Layout-awarenesscan be used to create a global placement of the logical qubits which min-imizes the insertion of SWAP gates, while knowledge of the structure ofML networks mapped onto quantum circuits can be used to manipulate the1726.5. Future Work: Short-termgraph topology such that fewer SWAP gates are needed, e.g., “pruning”.6.5 Future Work: Short-termThe experiments presented in this dissertation were designed to demonstratethe effects of adding context-awareness to the minor-embedding methods.Therefore, parameter choices were made to provide consistent and replicableresults, and only the most standard practices were used, such as spin rever-sal gauge transformations, parallel quantum annealing, fixed chain strength,majority vote sample resolution, physical temperature estimation, and stan-dard anneal schedules.At many steps throughout the work described here, there are potentialchanges to the CAD flow, or design-space parameter exploration that deservemore attention:Minor-embedding transformations: Evaluating transformations of theminor-embedding based on the geometrical properties of the target graphs;i.e. rotation, mirroring, and/or translation. This can be a method to miti-gate the effects of qubit noise, in addition to the spin reversal, and parallelquantum annealing.Apportioning of quadratic biases: Given a minor-embedding, the stan-dard method to apportion the quadratic biases between chains is to use allavailable chain interactions. A study on the effects of this method com-pared to single-point interactions or other approaches could be useful tounderstand the dynamics of chains.1736.5. Future Work: Short-termLayout-aware partitioning: Partitioning methods take in the adjacencyof a problem graph and return subgraphs that fit into a systematic cliqueminor-embedding on a target device. Exposing layout-awareness to the par-titioning stage of the QAP CAD flow could provide an improvement in theutilization of the qubit fabric.Anneal offsets: Given a minor-embedding, it is possible to modify theannealing schedule of select qubit chains according to their length. It hasbeen shown that doing so can mitigate the “freeze-out” effect; i.e., longerchains can be annealed slower [13]. This effect has not been studied forBoltzmann sampling.Chain expectation value: The use of the majority vote sample reso-lution method should be compared with other methods for the purpose ofBoltzmann sampling. For example, the chain break ratio (i.e., average of+1) qubits could be used to incorporate the chain behaviour into the expec-tation values.Adaptive positive-phase β scaling: A thorough evaluation of the useof adaptive β estimation with positive-phase temperature scaling for RBMtraining.QAML quantization: Similar to classical ML implementations, QAMLmodels can be quantized to lower precision, without affecting the overallbehaviour. A model can be optimized to work at a quantization level thatclosely matches the analog-to-digital resolution of the QAP device.1746.6. Future Work: Exploratory directionsQABM β scaling: The scaling difference between the positive and neg-ative sample distributions in QABMs is lower than in QARBMs. However,more experiments could determine if matching the temperature scaling fac-tors in QABM is beneficial.6.6 Future Work: Exploratory directionsQuantum computing devices are at an early stage of development. There-fore, several exploratory directions of work are available. These are long-term research projects that extend from the developments of this thesis:Clique “harvesting” methods: As mentioned in Section 5.2.3, one pos-sible optimization of the training run-time in QAML is to optimize theminor-embedding “harvesting” methods. A systematic method could beused to obtain and cache the maximum number of instances of differentsizes of cliques per device graph.Graph “continuum”: One of the directions that this thesis has enabledis the exploration of the Boltzmann machine “continuum”. i.e., an investiga-tion of different topologies, with their own minor-embedding methods, andcompared against all corner cases, such as, the native QAP graph, RBM,LBM, and fully-connected BM.Deep Learning: Integrating structure-aware minor-embedding for DeepBoltzmann Machines (DBM), Deep Belief Networks (DBN) and QuantumVariational Auto-Encoders (QVAE) models to allow real-world training datasets1756.6. Future Work: Exploratory directionsto be used.Application-specific architecture: Proposing and simulating a quan-tum annealing architecture that specializes in BM sampling. One approachmay be to focus on the connectivity of each qubit.Layout-awareness for quantum gates: Implementing layout-aware qubitmapping algorithms for the quantum gate model. This consists of optimizingthe initial qubit mapping, such that the number of SWAP gates introducedin the circuit is reduced.Structure-awareness in gate-model QAML: Implementing and eval-uating similar strategies to the ones outlined here, for the adaption andpruning of QAML circuit models. Removing edges from the model trans-lates into fewer gates, and a possible reduction of the depth of the param-eterized quantum circuit. We believe that similar trade-offs may be found,that improve the quality of the samples, at the cost of a smaller model.In the long term, qubit-mapping algorithms will be as critical to quantumcomputing as placement algorithms are to digital circuit design today. Opti-mal minor-embedding remains an open problem, but we demonstrated thatthe use of contextual information is one way of improving state-of-the-artheuristics and systematic methods for future practical uses of quantum an-nealers, and/or future quantum computing devices.176Bibliography[1] Alastair A. Abbott, Cristian S. Calude, Michael J. Dinneen, andRichard Hua. A hybrid quantum-classical paradigm to mitigate em-bedding costs in quantum annealing. International Journal of Quan-tum Information, 17(5), 3 2019.[2] Steven H. Adachi and Maxwell P. Henderson. Application of quan-tum annealing to training of deep neural networks. arXiv preprintarXiv:1510.00635, page 18, 10 2015.[3] Juan I. Adame, Peter L. McMahon, and Peter L. McMahon. In-homogeneous driving in quantum annealers can result in orders-of-magnitude improvements in performance. Quantum Science and Tech-nology, 5(3), 2020.[4] Dorit Aharonov, Wim Van Dam, Julia Kempe, Zeph Landau, SethLloyd, and Oded Regev. Adiabatic quantum computation is equivalentto standard quantum computation. In SIAM Journal on Computing,volume 37, pages 166–194, 2007.[5] Tameem Albash and Daniel A. Lidar. Adiabatic quantum computa-tion. Reviews of Modern Physics, 90(1), 2018.177BIBLIOGRAPHY[6] Mohammad H. Amin. Searching for quantum speedup in quasistaticquantum annealers. Physical Review A - Atomic, Molecular, and Op-tical Physics, 92(5), 2015.[7] Mohammad H. Amin, Evgeny Andriyash, Jason Rolfe, BohdanKulchytskyy, and Roger Melko. Quantum Boltzmann Machine. Phys-ical Review X, 8(2), 2018.[8] Maliheh Aramon, Gili Rosenberg, Elisabetta Valiante, ToshiyukiMiyazawa, Hirotaka Tamura, and Helmut G. Katzgraber. Physics-inspired optimization for quadratic unconstrained problems using adigital annealer. Frontiers in Physics, 7(APR), 2019.[9] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C.Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G.S.L.Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, BenChiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Ed-ward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, MarissaGiustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P.Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, TrentHuang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang,Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov,Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Land-huis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandra`,Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi,Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman,Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby,178BIBLIOGRAPHYAndre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel,Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger,Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, AmitVainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao,Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis.Quantum supremacy using a programmable superconducting proces-sor. Nature, 574(7779):505–510, 2019.[10] Ali Asghar and Husain Parvez. An improved diffusion based placementalgorithm for reducing interconnect demand in congested regions ofFPGAs. International Journal of Reconfigurable Computing, 2015:1–10, 2015.[11] K. Asnaashari and R. V. Krems. Quantum annealing with pairs of$ˆ2\sigma$ molecules as qubits. Physical Review A, 106(2), 2022.[12] Lev Barash, Jeffrey Marshall, Martin Weigel, and Itay Hen. Estimat-ing the density of states of frustrated spin systems. New Journal ofPhysics, 21(7), 8 2019.[13] Aaron Barbosa, Elijah Pelofske, Georg Hahn, and Hristo N. Djidjev.Optimizing embedding-related quantum annealing parameters for re-ducing hardware bias. In Communications in Computer and Informa-tion Science, volume 1362, pages 162–173, 2021.[14] Gideon Bass, Maxwell Henderson, Joshua Heath, and Joseph Dulny.Optimizing the optimizer: decomposition techniques for quantum an-nealing. Quantum Machine Intelligence, 3(1), 1 2021.179BIBLIOGRAPHY[15] Matthew J.S. Beach, Isaac de Vlugt, Anna Golubeva, Patrick Huem-beli, Bohdan Kulchytskyy, Xiuzhe Luo, Roger G. Melko, Ejaaz Merali,and Giacomo Torlai. QuCumber: Wavefunction reconstruction withneural networks. SciPost Physics, 7(1), 12 2019.[16] Marcello Benedetti, Delfina Garcia-Pintos, Oscar Perdomo, VicenteLeyton-Ortega, Yunseong Nam, and Alejandro Perdomo-Ortiz. Agenerative modeling approach for benchmarking and training shallowquantum circuits. npj Quantum Information, 5(1), 2019.[17] Marcello Benedetti, John Realpe-Go´mez, Rupak Biswas, and Alejan-dro Perdomo-Ortiz. Estimation of effective temperatures in quantumannealers for sampling applications: A case study with possible appli-cations in deep learning. Physical Review A, 94(2), 10 2016.[18] Marcello Benedetti, John Realpe-Go´mez, Rupak Biswas, and Alejan-dro Perdomo-Ortiz. Quantum-assisted learning of hardware-embeddedprobabilistic graphical models. Physical Review X, 7(4), 9 2017.[19] Marcello Benedetti, John Realpe-Go´mez, and Alejandro Perdomo-Ortiz. Quantum-assisted Helmholtz machines: A quantum-classicaldeep learning framework for industrial datasets in near-term devices.Quantum Science and Technology, 3(3):34007, 8 2017.[20] Charles H. Bennett and Gilles Brassard. Quantum cryptography: Pub-lic key distribution and coin tossing. Theoretical Computer Science,560(P1):7–11, 2014.180BIBLIOGRAPHY[21] Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, Shah-nawaz Ahmed, Vishnu Ajith, M Sohaib Alam, Guillermo Alonso-Linaje, B AkashNarayanan, Ali Asadi, Juan Miguel Arrazola, UtkarshAzad, Sam Banning, Carsten Blank, Thomas R Bromley, Benjamin ACordier, Jack Ceroni, Alain Delgado, Olivia Di Matteo, AmintorDusko, Tanya Garg, Diego Guala, Anthony Hayes, Ryan Hill, AroosaIjaz, Theodor Isacsson, David Ittah, Soran Jahangiri, Prateek Jain,Edward Jiang, Ankit Khandelwal, Korbinian Kottmann, Robert ALang, Christina Lee, Thomas Loke, Angus Lowe, Keri McKiernan, Jo-hannes Jakob Meyer, J A Montan˜ez-Barrera, Romain Moyard, ZeyueNiu, Lee James O’Riordan, Steven Oud, Ashish Panigrahi, Chae-YeunPark, Daniel Polatajko, Nicola´s Quesada, Chase Roberts, Nahum Sa´,Isidor Schoch, Borun Shi, Shuli Shu, Sukin Sim, Arshpreet Singh, In-grid Strandberg, Jay Soni, Antal Sza´va, Slimane Thabet, Rodrigo AVargas-Herna´ndez, Trevor Vincent, Nicola Vitucci, Maurice Weber,David Wierichs, Roeland Wiersema, Moritz Willmann, Vincent Wong,Shaoming Zhang, and Nathan Killoran. PennyLane: Automatic dif-ferentiation of hybrid quantum-classical computations. ArXiv, 2018.[22] Vaughn Betz and Jonathan Rose. VPR: A new packing, placementand routing tool for FPGA research. In Lecture Notes in ComputerScience (including subseries Lecture Notes in Artificial Intelligenceand Lecture Notes in Bioinformatics), volume 1304, pages 213–222,1997.[23] Zhengbing Bian, Fabian Chudak, Robert Israel, Brad Lackey,181BIBLIOGRAPHYWilliam G. Macready, and Aidan Roy. Discrete optimization usingquantum annealing on sparse Ising models. Frontiers in Physics, 2:56,9 2014.[24] Zhengbing Bian, Fabian Chudak, Robert Israel, Brad Lackey,William G. Macready, and Aidan Roy. Mapping constrained opti-mization problems to quantum annealing with application to faultdiagnosis. Frontiers in ICT, 3:14, 2016.[25] Zhengbing Bian, Fabian Chudak, William G. Macready, Lane Clark,and Frank Gaitan. Experimental determination of Ramsey numbers.Physical Review Letters, 111(13), 1 2013.[26] Amy Blumenthal. USC to lead IARPA quantum computingproject. https://viterbischool.usc.edu/news/2017/06/usc-lead-iarpa-quantum-computing-project/, 2017.[27] Kelly Boothby, Paul Bunyk, Jack Raymond, and Aidan Roy. Next-generation topology of D-Wave quantum processors. ArXiv, 2020.[28] Tomas Boothby, Andrew D. King, and Aidan Roy. Fast clique minorgeneration in Chimera qubit connectivity graphs. Quantum Informa-tion Processing, 15(1):495–508, 7 2016.[29] Edward Boyda, Saikat Basu, Sangram Ganguly, Andrew Michaelis,Supratik Mukhopadhyay, and Ramakrishna R. Nemani. Deploying aquantum annealing processor to detect tree cover in aerial imagery ofCalifornia. Public Library of Science (PLoS) ONE, 12(2):e0172505, 22017.182BIBLIOGRAPHY[30] P. I. Bunyk, Emile M. Hoskinson, Mark W. Johnson, Elena Tolka-cheva, Fabio Altomare, Andrew J. Berkley, Richard Harris, Jeremy P.Hilton, Trevor Lanting, Anthony J. Przybysz, and Jed Whittaker. Ar-chitectural Considerations in the Design of a Superconducting Quan-tum Annealing Processor. IEEE Transactions on Applied Supercon-ductivity, 24(4):1–10, 8 2014.[31] Jun Cai, William G. Macready, and Aidan Roy. A practical heuristicfor finding graph minors, 6 2014.[32] V. Canivell, P. Forn-Dı´az, A. Garcia-Saez, and R. Sagastizabal.Startup Qilimanjaro—towards a European full-stack coherent quan-tum annealer platform. EPJ Quantum Technology, 8(1):6, 12 2021.[33] Miguel A Carreira-Perpinan and Geoffrey E. Hinton. On contrastivedivergence learning. In AISTATS 2005 - Proceedings of the 10th In-ternational Workshop on Artificial Intelligence and Statistics, pages33–40, 2005.[34] Vicky Choi. Minor-embedding in Adiabatic Quantum Computation:I. The Parameter Setting Problem. Quantum Information Processing,7(5):193–209, 10 2008.[35] Vicky Choi. Minor-embedding in Adiabatic Quantum Computation:II. Minor-universal Graph Design. Quantum Information Processing,10(3):343–353, 6 2011.[36] M. Chrobak and T. H. Payne. A linear-time algorithm for drawing a183BIBLIOGRAPHYplanar graph on a grid. Information Processing Letters, 54(4):241–246,1995.[37] Cirq Developers. Cirq. https://doi.org/10.5281/zenodo.8161252, 2023.[38] E. J. Crosson and D. A. Lidar. Prospects for quantum enhancementwith diabatic quantum annealing. Nature Reviews Physics, 3(7):466–489, 2021.[39] D-Wave Systems. Ocean Software Development Kit.https://github.com/dwavesystems/dwave-ocean-sdk, 2023.[40] D-Wave Systems Inc. D-Wave Ocean Software, Available:https://ocean.dwavesys.com/. https://ocean.dwavesys.com/, 2021.[41] D-Wave Systems Inc. Postprocessing Methods.https://docs.dwavesys.com/docs/latest/doc post-processing.html,2021.[42] D-Wave Systems Inc. Source repository for dimod,Available: https://github.com/dwavesystems/dimod.https://github.com/dwavesystems/dimod, 2021.[43] D-Wave Systems Inc. D-Wave Leap.https://cloud.dwavesys.com/leap/, 2023.[44] D-Wave Systems Inc. Featured Applications.https://www.dwavesys.com/learn/featured-applications/, 2023.184BIBLIOGRAPHY[45] D-Wave Systems Inc. QPU-Specific Characteristics.https://docs.dwavesys.com/docs/latest/doc physical properties.html,3 2023.[46] D-Wave Systems Inc. Source repository for D-Wave NetworkX,Available: https://github.com/dwavesystems/dwave networkx.https://github.com/dwavesystems/dwave networkx, 2023.[47] D-Wave Systems Inc. Source repository for D-Wave System.https://github.com/dwavesystems/dwave-system/, 2023.[48] D-Wave Systems Inc. Source Repository for minorminer,Available: https://github.com/dwavesystems/minorminer.https://github.com/dwavesystems/minorminer, 2023.[49] D-Wave Systems Inc. Using Leap’s Hybrid Solvers.https://docs.dwavesys.com/docs/latest/doc leap hybrid.html, 2023.[50] Andrew J. Daley, Immanuel Bloch, Christian Kokail, Stuart Flanni-gan, Natalie Pearson, Matthias Troyer, and Peter Zoller. Practicalquantum advantage in quantum simulation. Nature, 607(7920):667–676, 2022.[51] Samudra Dasgupta and Arnab Banerjee. Quantum annealing algo-rithm for expected shortfall based dynamic asset allocation. ArXiv,2019.[52] M Denil and N De Freitas. Toward the implementation of a quantum185BIBLIOGRAPHYRBM. NIPS 2011 Deep Learning and Unsupervised Feature LearningWorkshop, 1(2):1–9, 2011.[53] N G Dickson, M W Johnson, M H Amin, R Harris, F Altomare, a JBerkley, P Bunyk, J Cai, E M Chapple, P Chavez, F Cioata, T Cirip,P Debuen, M Drew-Brook, C Enderud, S Gildert, F Hamze, J PHilton, E Hoskinson, K Karimi, E. Ladizinsky, N Ladizinsky, T Lant-ing, T Mahon, R Neufeld, T Oh, I Perminov, C Petroff, A Przybysz,C Rich, P Spear, A Tcaciuc, M C Thom, E Tolkacheva, S Uchaikin,J Wang, a B Wilson, Z Merali, and G Rose. Thermally assistedquantum annealing of a 16-qubit problem. Nature Communications,4(May):1903, 7 2013.[54] Vinayak Dixit and Chence Niu. Quantum computing for transportnetwork design problems. SSRN Electronic Journal, 2022.[55] Vivek Dixit, Raja Selvarajan, Muhammad A. Alam, Travis S. Humble,and Sabre Kais. Training restricted Boltzmann machines with a D-Wave quantum annealer. Frontiers in Physics, 9, 5 2021.[56] Vivek Dixit, Raja Selvarajan, Tamer Aldwairi, Yaroslav Koshka,Mark A. Novotny, Travis S. Humble, Muhammad A. Alam, and SabreKais. Training a quantum annealing based restricted Boltzmann ma-chine on cybersecurity data. IEEE Transactions on Emerging Topicsin Computational Intelligence, 6(3):417–428, 11 2022.[57] John E. Dorband. A Boltzmann machine implementation for the D-Wave. In Proceedings of the 12th International Conference on Infor-186BIBLIOGRAPHYmation Technology: New Generations, ITNG 2015, pages 703–707, 62015.[58] Vincent Dumoulin, Ian J. Goodfellow, Aaron Courville, and YoshuaBengio. On the challenges of physical implementations of RBMs. InProceedings of the National Conference on Artificial Intelligence, vol-ume 2, pages 1199–1205, 12 2014.[59] S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein,G. Semeghini, A. Omran, J. G. Liu, R. Samajdar, X. Z. Luo, B. Nash,X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi,H. Pichler, S. T. Wang, M. Greiner, V. Vuletic´, and M. D. Lukin.Quantum optimization of maximum independent set using Rydbergatom arrays. Science, 376(6598):1209–1215, 2022.[60] European Commission. Quantum Technologies Flagship.https://digital-strategy.ec.europa.eu/en/policies/quantum-technologies-flagship, 2023.[61] Olivier Ezratty. Perspective on superconducting qubit quantum com-puting. European Physical Journal A, 59(5), 2023.[62] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantumapproximate optimization algorithm. ArXiv, 2014.[63] Asja Fischer and Christian Igel. Training restricted Boltzmann ma-chines: An introduction. Pattern Recognition, 47(1):25–39, 1 2014.[64] Jonathan Frankle and Michael Carbin. The lottery ticket hypothe-187BIBLIOGRAPHYsis: Finding sparse, trainable neural networks. In 7th InternationalConference on Learning Representations, ICLR 2019, 2019.[65] Thomas M.J. Fruchterman and Edward M. Reingold. Graph draw-ing by force-directed placement. Software: Practice and Experience,21(11):1129–1164, 1991.[66] Jay M. Gambetta, Jerry M. Chow, and Matthias Steffen. Buildinglogical qubits in a superconducting quantum computing system. npjQuantum Information, 3(1), 2017.[67] A. I. Gircha, A. S. Boev, K. Avchaciov, P. O. Fedichev, and A. K.Fedorov. Training a discrete variational autoencoder for generativechemistry and drug design on a quantum annealer. ArXiv, 8 2021.[68] Fred Glover, Gary Kochenberger, Rick Hennig, and Yu Du. Quantumbridge analytics I: a tutorial on formulating and using QUBO models.Annals of Operations Research, 314(1):141–183, 2022.[69] Zoe Gonzalez Izquierdo, Shon Grabbe, Stuart Hadfield, Jeffrey Mar-shall, Zhihui Wang, and Eleanor Rieffel. Ferromagnetically shiftingthe power of pausing. Physical Review Applied, 15(4), 6 2021.[70] Hayato Goto, Kosuke Tatsumura, and Alexander R. Dixon. Combina-torial optimization by simulating adiabatic bifurcations in nonlinearHamiltonian systems. Science Advances, 5(4), 2019.[71] GOV.UK. National Quantum Strategy.188BIBLIOGRAPHYhttps://www.gov.uk/government/publications/national-quantum-strategy, 2023.[72] Lov K. Grover. A fast quantum mechanical algorithm for databasesearch. In Proceedings of the Annual ACM Symposium on Theory ofComputing, volume Part F1294, pages 212–219, 1996.[73] R Harris, M. W. Johnson, T. Lanting, A. J. Berkley, J. Johans-son, P. Bunyk, E. Tolkacheva, E. Ladizinsky, N. Ladizinsky, T. Oh,F. Cioata, I. Perminov, P. Spear, C. Enderud, C. Rich, S. Uchaikin,M. C. Thom, E. M. Chapple, J. Wang, B. Wilson, M. H.S. Amin,N. Dickson, K. Karimi, B. MacReady, C. J.S. Truncik, and G. Rose.Experimental investigation of an eight-qubit unit cell in a supercon-ducting optimization processor. Physical Review B - Condensed Mat-ter and Materials Physics, 82(2):24511, 7 2010.[74] R Harris, Y Sato, A J Berkley, M Reis, F Altomare, M H Amin,K Boothby, P Bunyk, C Deng, C Enderud, S Huang, E Hoskinson,MW Johnson, E Ladizinsky, N Ladizinsky, T Lanting, R Li, T Medina,R Molavi, R Neufeld, T Oh, I Pavlov, I Perminov, G Poulin-Lamarre,C Rich, A Smirnov, L Swenson, N Tsai, M Volkmann, J Whittaker,and J Yao. Phase transitions in a programmable quantum spin glasssimulator. Science (New York, N.Y.), 361(6398):162–165, 7 2018.[75] Dylan Herman, Cody Googin, Xiaoyuan Liu, Alexey Galda, Ilya Safro,Yue Sun, Marco Pistoia, and Yuri Alexeev. A survey of quantumcomputing for finance. ArXiv, 1 2022.189BIBLIOGRAPHY[76] Geoffrey E. Hinton. A practical guide to training restricted boltzmannmachines. Lecture Notes in Computer Science (including subseriesLecture Notes in Artificial Intelligence and Lecture Notes in Bioinfor-matics), 7700 LECTU:599–619, 2012.[77] Taleana Huff, Hatem Labidi, Mohammad Rashidi, Lucian Livadaru,Thomas Dienel, Roshan Achal, Wyatt Vine, Jason Pitters, andRobert A. Wolkow. Binary atomic silicon logic. Nature Electronics,1(12):636–643, 6 2018.[78] Eric Hyyppa¨, Suman Kundu, Chun Fai Chan, Andra´s Gunyho´, JuhoHotari, David Janzso, Kristinn Juliusson, Olavi Kiuru, Janne Koti-lahti, Alessandro Landra, Wei Liu, Fabian Marxer, Akseli Ma¨kinen,Jean Luc Orgiazzi, Mario Palma, Mykhailo Savytskyi, FrancescaTosto, Jani Tuorila, Vasilii Vadimov, Tianyi Li, Caspar Ockeloen-Korppi, Johannes Heinsoo, Kuan Yen Tan, Juha Hassel, and MikkoMo¨tto¨nen. Unimon qubit. Nature Communications, 13(1), 2022.[79] Kazuki Ikeda, Yuma Nakamura, and Travis S. Humble. Applicationof quantum annealing to nurse scheduling problem. Scientific Reports,9(1), 2019.[80] Daisuke Inoue, Akihisa Okada, Tadayoshi Matsumori, Kazuyuki Ai-hara, and Hiroaki Yoshida. Traffic signal optimization on a squarelattice with quantum annealing. Scientific Reports, 11(1), 2021.[81] ISED Canada. Overview of Canada’s National Quantum Strategy.https://ised-isde.canada.ca/site/national-quantum-strategy/en, 2023.190BIBLIOGRAPHY[82] Joshua Job and Steve Adachi. Systematic comparison of deep beliefnetwork training using quantum annealing vs. classical techniques, 82020.[83] M. W. Johnson, M. H.S. Amin, S. Gildert, T. Lanting, F. Hamze,N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk,E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi, E. Ladizinsky,N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolka-cheva, C. J.S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose.Quantum annealing with manufactured spins. Nature, 473(7346):194–198, 2011.[84] M. W. Johnson, P. Bunyk, F. Maibaum, E. Tolkacheva, A. J. Berkley,E. M. Chapple, R. Harris, J. Johansson, T. Lanting, I. Perminov,E. Ladizinsky, T. Oh, and G. Rose. A scalable control system fora superconducting adiabatic quantum optimization processor. Super-conductor Science and Technology, 23(6), 7 2010.[85] Ju¨lich Supercomputing Centre (JSC). JUNIQ Facil-ity. https://www.fz-juelich.de/en/ias/jsc/systems/quantum-computing/juniq-facility, 2023.[86] Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing inthe transverse Ising model. Phys. Rev. E, 58(5):5355–5363, 11 1998.[87] Peter J Karalekas, Nikolas A Tezak, Eric C Peterson, Colm A Ryan,Marcus P da Silva, and Robert S Smith. A quantum-classical cloud191BIBLIOGRAPHYplatform optimized for variational hybrid algorithms. Quantum Sci-ence and Technology, 5(2):24003, 4 2020.[88] Hillol Kargupta and Philip Chan. Graphical models: Foundations ofneural computation. Pattern Analysis and Applications, 5(4):401–402,2002.[89] Jack Raymond Kelly Boothby, Andrew D. King. Zephyr topology ofD-Wave quantum processors. Technical report, D-Wave Systems Inc.,2021.[90] Amir Khoshaman, Walter Vinci, Brandon Denis, Evgeny Andriyash,Hossein Sadeghi, and Mohammad H. Amin. Quantum variational au-toencoder. Quantum Science and Technology, 4(1):014001, 2 2018.[91] Youngseok Kim, Andrew Eddins, Sajant Anand, Ken Xuan Wei,Ewout van den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu,Michael Zaletel, Kristan Temme, and Abhinav Kandala. Evidencefor the utility of quantum computing before fault tolerance. Nature,618(7965):500–505, 2023.[92] Andrew D. King, Juan Carrasquilla, Jack Raymond, Isil Ozfidan,Evgeny Andriyash, Andrew Berkley, Mauricio Reis, Trevor Lanting,Richard Harris, Fabio Altomare, Kelly Boothby, Paul I. Bunyk, ColinEnderud, Alexandre Fre´chette, Emile Hoskinson, Nicolas Ladizinsky,Travis Oh, Gabriel Poulin-Lamarre, Christopher Rich, Yuki Sato,Anatoly Yu Smirnov, Loren J. Swenson, Mark H. Volkmann, JedWhittaker, Jason Yao, Eric Ladizinsky, Mark W. Johnson, Jeremy192BIBLIOGRAPHYHilton, and Mohammad H. Amin. Observation of topological phenom-ena in a programmable lattice of 1,800 qubits. Nature, 560(7719):456–460, 2018.[93] Andrew D. King, Jack Raymond, Trevor Lanting, Richard Harris,Alex Zucca, Fabio Altomare, Andrew J. Berkley, Kelly Boothby, SaraEjtemaee, Colin Enderud, Emile Hoskinson, Shuiyuan Huang, EricLadizinsky, Allison J.R. MacDonald, Gaelen Marsden, Reza Molavi,Travis Oh, Gabriel Poulin-Lamarre, Mauricio Reis, Chris Rich, YukiSato, Nicholas Tsai, Mark Volkmann, Jed D. Whittaker, Jason Yao,Anders W. Sandvik, and Mohammad H. Amin. Quantum criti-cal dynamics in a 5,000-qubit programmable spin glass. Nature,617(7959):61–66, 2023.[94] Koki Kitai, Jiang Guo, Shenghong Ju, Shu Tanaka, Koji Tsuda, Ju-nichiro Shiomi, and Ryo Tamura. Expanding the horizon of automatedmetamaterials discovery via quantum annealing. ArXiv, 2 2019.[95] Christine Klymko, Blair D. Sullivan, and Travis S. Humble. Adiabaticquantum programming: Minor embedding with hard faults. QuantumInformation Processing, 13(3):709–729, 3 2014.[96] Mario S. Ko¨nz, Guglielmo Mazzola, Andrew J. Ochoa, Helmut G.Katzgraber, and Matthias Troyer. Uncertain fate of fair sampling inquantum annealing. Physical Review A, 100(3), 6 2019.[97] Dmytro Korenkevych, Yanbo Xue, Zhengbing Bian, Fabian Chudak,William G. Macready, Jason Rolfe, and Evgeny Andriyash. Bench-193BIBLIOGRAPHYmarking quantum hardware for training of fully visible Boltzmannmachines. arXiv preprint arXiv:1611.04528, 11 2016.[98] Yaroslav Koshka and M. A. Novotny. Toward sampling from undi-rected probabilistic graphical models using a D-Wave quantum an-nealer. Quantum Information Processing, 19(10), 5 2020.[99] Yaroslav Koshka and Mark A. Novotny. Comparison of use of a 2000qubit D-Wave quantum annealer and MCMC for sampling, image re-construction, and classification. IEEE Transactions on Emerging Top-ics in Computational Intelligence, 5(1):119–129, 2 2021.[100] Yaroslav Koshka, Dilina Perera, Spencer Hall, and M. A. Novotny.Determination of the lowest-energy states for the model distributionof trained restricted Boltzmann machines using a 1000 qubit D-Wave2X quantum computer. Neural Computation, 29(7):1815–1837, 7 2017.[101] Lev Davidovich Landau. A THEORY OF ENERGY TRANSFER. II.In Collected Papers of L.D. Landau, pages 63–66. Pergamon Press,1965.[102] Richard Y. Li, Tameem Albash, and Daniel A. Lidar. Limitations oferror corrected quantum annealing in improving the performance ofBoltzmann machines. Quantum Science and Technology, 5(4):045010,10 2020.[103] Jeremy Liu, Ankith Mohan, Rajiv K. Kalia, Aiichiro Nakano, Ken ichiNomura, Priya Vashishta, and Ke Thia Yao. Boltzmann machine mod-194BIBLIOGRAPHYeling of layered MoS2 synthesis on a quantum annealer. ComputationalMaterials Science, 173:109429, 2 2020.[104] Jeremy Liu, Federico M. Spedalieri, Ke Thia Yao, Thomas E. Potok,Catherine Schuman, Steven Young, Robert Patton, Garrett S. Rose,and Gangotree Chamka. Adiabatic quantum computation applied todeep learning networks. Entropy, 20(5), 2018.[105] Jeremy Liu, Ke Thia Yao, and Federico Spedalieri. Dynamic topologyreconfiguration of boltzmann machines on quantum annealers. En-tropy, 22(11):1–20, 2020.[106] William P. Livingston, Machiel S. Blok, Emmanuel Flurin, JustinDressel, Andrew N. Jordan, and Irfan Siddiqi. Experimental demon-stration of continuous quantum error correction. Nature Communica-tions, 13(1), 2022.[107] Andrew Lucas. Ising formulations of many NP problems. Frontiers inPhysics, 2:5, 2014.[108] Tao Luo and David Z. Pan. DPlace2.0: A stable and efficient ana-lytical placement based on diffusion. In Proceedings of the Asia andSouth Pacific Design Automation Conference, ASP-DAC, pages 346–351, 2008.[109] Lars S. Madsen, Fabian Laudenbach, Mohsen Falamarzi Askarani,Fabien Rortais, Trevor Vincent, Jacob F.F. Bulmer, Filippo M. Mi-atto, Leonhard Neuhaus, Lukas G. Helt, Matthew J. Collins, Adri-ana E. Lita, Thomas Gerrits, Sae Woo Nam, Varun D. Vaidya, Matteo195BIBLIOGRAPHYMenotti, Ish Dhand, Zachary Vernon, Nicola´s Quesada, and JonathanLavoie. Quantum computational advantage with a programmable pho-tonic processor. Nature, 606(7912):75–81, 2022.[110] Mateusz T. Ma¸dzik, Serwan Asaad, Akram Youssry, BenjaminJoecker, Kenneth M. Rudinger, Erik Nielsen, Kevin C. Young, Timo-thy J. Proctor, Andrew D. Baczewski, Arne Laucht, Vivien Schmitt,Fay E. Hudson, Kohei M. Itoh, Alexander M. Jakob, Brett C. John-son, David N. Jamieson, Andrew S. Dzurak, Christopher Ferrie, RobinBlume-Kohout, and Andrea Morello. Precision tomography of a three-qubit donor quantum processor in silicon. Nature, 601(7893):348–353,2022.[111] Salvatore Mandra`, Zheng Zhu, and Helmut G. Katzgraber. Exponen-tially biased ground-state sampling of quantum annealing machineswith transverse-field driving Hamiltonians. Physical Review Letters,118(7):070502, 2 2017.[112] Jeffrey Marshall, Eleanor G. Rieffel, and Itay Hen. Thermalization,freeze-out, and noise: Deciphering experimental quantum annealers.Physical Review Applied, 8(6):064025, 12 2017.[113] Jeffrey Marshall, Davide Venturelli, Itay Hen, and Eleanor G. Rief-fel. Power of pausing: Advancing understanding of thermalization inexperimental quantum annealers. Physical Review Applied, 11(4), 102019.[114] Peter L McMahon, Alireza Marandi, Yoshitaka Haribara, Ryan196BIBLIOGRAPHYHamerly, Carsten Langrock, Shuhei Tamate, Takahiro Inagaki, Hi-roki Takesue, Shoko Utsunomiya, Kazuyuki Aihara, Robert L Byer,M M Fejer, Hideo Mabuchi, and Yoshihisa Yamamoto. A fully pro-grammable 100-spin coherent Ising machine with all-to-all connec-tions. Science, 354(6312):614–617, 11 2016.[115] Larry McMurchie and Carl Ebeling. PathFinder: A negotiation-basedperformance-driven router for FPGAs. In Proceedings of the 1995ACM Third International Symposium on Field-programmable GateArrays, FPGA ’95, pages 111–117, New York, NY, USA, 1995. ACM.[116] Jan Melchior. PyDeep. Available:https://github.com/MelJan/PyDeep.git, 2017.[117] Lorenzo Moro and Enrico Prati. Anomaly detection speed-up by quan-tum restricted Boltzmann machines. Communications Physics, 6(1),2023.[118] Alex Mott, Joshua Job, Jean Roch Vlimant, Daniel Lidar, and MariaSpiropulu. Solving a Higgs optimization problem with quantum an-nealing for machine learning. Nature, 550(7676):375–379, 2017.[119] Samuel Mugel, Carlos Kuchkovsky, Escola´stico Sa´nchez, SamuelFerna´ndez-Lorenzo, Jorge Luis-Hita, Enrique Lizaso, and Roma´nOru´s. Dynamic portfolio optimization with real datasets using quan-tum processors and quantum-inspired tensor networks. Physical Re-view Research, 4(1), 2022.197BIBLIOGRAPHY[120] Ravi Nair. A simple yet effective technique for global wiring. IEEETransactions on Computer-Aided Design of Integrated Circuits andSystems, 6(2):165–172, 1987.[121] NASA. NASA Quantum Artificial Intelligence Laboratory (QuAIL).https://www.nasa.gov/intelligent-systems-division/discovery-and-systems-health/nasa-quail/, 2023.[122] NEC Corporation. NEC develops the world’sfirst unit cell facilitating scaling up to a fully-connected quantum annealing architecture. Available:https://www.nec.com/en/press/202203/global 20220317 01.html,2022.[123] Jon Nelson, Marc Vuffray, Andrey Y. Lokhov, Tameem Albash, andCarleton Coffrin. High-quality thermal Gibbs sampling with quantumannealing hardware. ArXiv, 9 2021.[124] Hartmut Neven, Vasil S. Denchev, Geordie Rose, and William G.Macready. Training a large scale classifier with the quantum adia-batic algorithm. ArXiv, 12 2009.[125] Hartmut Neven, Vasil S Denchev, Geordie Rose, and William G.MacReady. QBoost: Large scale classifier training with adiabaticquantum optimization. In Journal of Machine Learning Research, vol-ume 25, pages 333–348, 2012.[126] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever,and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural198BIBLIOGRAPHYnetworks from overfitting. Journal of Machine Learning Research,2014.[127] Sergey Novikov, Robert Hinkey, Steven Disseler, James I. Basham,Tameem Albash, Andrew Risinger, David Ferguson, Daniel A. Lidar,and Kenneth M. Zick. Exploring more-coherent quantum annealing. In2018 IEEE International Conference on Rebooting Computing, ICRC2018, 9 2019.[128] Shuntaro Okada, Masayuki Ohzeki, Masayoshi Terabe, and ShinichiroTaguchi. Improving solutions by embedding larger subproblems in aD-Wave quantum annealer. Scientific Reports, 9(1):2098, 12 2019.[129] I. Ozfidan, C. Deng, A. Y. Smirnov, T. Lanting, R. Harris, L. Swen-son, J. Whittaker, F. Altomare, M. Babcock, C. Baron, A. J. Berkley,K. Boothby, H. Christiani, P. Bunyk, C. Enderud, B. Evert, M. Hager,A. Hajda, J. Hilton, S. Huang, E. Hoskinson, M. W. Johnson,K. Jooya, E. Ladizinsky, N. Ladizinsky, R. Li, A. MacDonald, D. Mars-den, G. Marsden, T. Medina, R. Molavi, R. Neufeld, M. Nissen,M. Norouzpour, T. Oh, I. Pavlov, I. Perminov, G. Poulin-Lamarre,M. Reis, T. Prescott, C. Rich, Y. Sato, G. Sterling, N. Tsai, M. Volk-mann, W. Wilkinson, J. Yao, and M. H. Amin. Demonstration ofa nonstoquastic Hamiltonian in coupled superconducting flux qubits.Physical Review Applied, 13(3), 3 2020.[130] Scott Pakin. Performing fully parallel constraint logic programmingon a quantum annealer, 3 2018.199BIBLIOGRAPHY[131] Scott Pakin. Personal Communication via email, 2018.[132] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, JamesBradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, NataliaGimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, EdwardYang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chil-amkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chin-tala. PyTorch: An imperative style, high-performance deep learning li-brary. In HWallach, H Larochelle, A Beygelzimer, F d\textquotesingleAlche´-Buc, E Fox, and R Garnett, editors, Advances in Neural Infor-mation Processing Systems, volume 32. Curran Associates, Inc., 2019.[133] Elijah Pelofske, Georg Hahn, and Hristo Djidjev. Advanced unem-bedding techniques for quantum annealers. In Proceedings of the 2020International Conference on Rebooting Computing, ICRC 2020, pages34–41, 9 2020.[134] Elijah Pelofske, Georg Hahn, and Hristo Djidjev. Inferring the dy-namics of ground-state evolution of quantum annealers. ArXiv, 2020.[135] Elijah Pelofske, Georg Hahn, and Hristo N. Djidjev. Parallel quantumannealing. Scientific Reports, 12(1), 2022.[136] Alejandro Perdomo-Ortiz, Joseph Fluegemann, Rupak Biswas, andVadim N. Smelyanskiy. A performance estimator for quantum anneal-ers: Gauge selection and parameter setting. ArXiv, 3 2015.[137] Cameron Perot. Quantum boltzmann machines: Applications in quan-titative finance. ArXiv, 2023.200BIBLIOGRAPHY[138] Jose P. Pinilla. Source Repository for embera,Available: https://github.com/joseppinilla/embera.https://github.com/joseppinilla/embera, 2021.[139] Jose P. Pinilla. joseppinilla/qaml: v0.0.1.https://doi.org/10.5281/zenodo.6612474#.YppzVYZBpss.mendeley,2023.[140] Jose P. Pinilla and Steven J. E. Wilton. Layout-aware embedding ofQCA networks onto a quantum annealer. Poster presented at DesignAutomation Conference (DAC55), 2018.[141] Jose P. Pinilla and Steven J. E. Wilton. Structure-aware minor-embedding for machine learning in quantum annealing processors. InQuantum Computing, pages 89–99. Springer Verlag, 1st ed. edition,2024.[142] Jose P. Pinilla and Steven J.E. Wilton. Layout-aware embedding forquantum annealing processors. In Lecture Notes in Computer Science(including subseries Lecture Notes in Artificial Intelligence and LectureNotes in Bioinformatics), volume 11501 LNCS, pages 121–139, 2019.[143] Jose P. Pinilla and Steven J.E. Wilton. Positive-phase temperaturescaling for quantum-assisted Boltzmann machine training. In Inter-national Conference for High Performance Computing, Networking,Storage and Analysis, SC, volume 2022-Novem. IEEE Computer So-ciety, 11 2022.201BIBLIOGRAPHY[144] John Preskill. Quantum computing in the NISQ era and beyond.Quantum, 2:79, 8 2018.[145] Kristen L. Pudenz, Tameem Albash, and Daniel A. Lidar. Error-corrected quantum annealing with hundreds of qubits. Nature Com-munications, 5(1):1–10, 2 2014.[146] Kristen L. Pudenz, Tameem Albash, and Daniel A. Lidar. Quantumannealing correction for random Ising problems. Physical Review A -Atomic, Molecular, and Optical Physics, 91(4), 2015.[147] Yixuan Qiu, Lingsong Zhang, and Xiao Wang. Unbiased constrastivedivergence algorithms for training energy-based latent variable models.In 8th International Conference on Learning Representations, ICLR2020, 2020.[148] Robert Raussendorf, Daniel E. Browne, and Hans J. Briegel.Measurement-based quantum computation on cluster states. PhysicalReview A - Atomic, Molecular, and Optical Physics, 68(2):32, 2003.[149] Jack Raymond, Ndiame Ndiame´ Ndiaye, Gautam Rayaprolu, and An-drew D. King. Improving performance of logical qubits by parametertuning and topology compensation. In Proceedings of the IEEE Inter-national Conference on Quantum Computing and Engineering, QCE2020, pages 295–305, 6 2020.[150] Jack Raymond, Sheir Yarkoni, and Evgeny Andriyash. Global warm-ing: Temperature estimation in annealers. Frontiers in ICT, 3(NOV),6 2016.202BIBLIOGRAPHY[151] Haoxing Ren, David Z. Pan, Charles J. Alpert, and Paul Villarrubia.Diffusion-based placement migration. Proceedings of the 42nd annualconference on Design automation - DAC ’05, page 515, 2005.[152] Jacob Retallick, Michael Babcock, Miguel Aroca-Ouellette, Shane Mc-Namara, Steve Wilton, Aidan Roy, Mark Johnson, and Konrad Walus.Embedding of quantum-dot cellular automata circuits onto a quantumannealing processor. In 2014 Conference on Optoelectronic and Mi-croelectronic Materials and Devices, COMMAD 2014, pages 200–203,12 2014.[153] Eleanor G. Rieffel, Davide Venturelli, Bryan O’Gorman, Minh B. Do,Elicia M. Prystay, and Vadim N. Smelyanskiy. A case study in pro-gramming a quantum annealer for hard operational planning prob-lems. Quantum Information Processing, 14(1):1–36, 1 2014.[154] Chad Rigetti, Jay M Gambetta, Stefano Poletto, B. L.T. Plourde,Jerry M Chow, A. D. Co´rcoles, John A. Smolin, Seth T Merkel, J RRozen, George A Keefe, Mary B Rothwell, Mark B Ketchen, andM Steffen. Superconducting qubit in a waveguide cavity with a coher-ence time approaching 0.1 ms. Physical Review B - Condensed Matterand Materials Physics, 86(10):1–4, 2012.[155] Lorenzo Rocutto, Claudio Destri, and Enrico Prati. Quantum seman-tic learning by reverse annealing of an adiabatic quantum computer.Advanced Quantum Technologies, 4(2), 3 2021.[156] Ilmo Salmenpera¨ and Jukka K. Nurminen. Software techniques for203BIBLIOGRAPHYtraining restricted Boltzmann machines on size-constrained quantumannealing hardware. Frontiers in Computer Science, 5, 2023.[157] Peter W. Shor. Polynomial-time algorithms for prime factorizationand discrete logarithms on a quantum computer. SIAM Journal onComputing, 26(5):1484–1509, 1997.[158] Georg Sigl, Konrad Doll, and Frank M. Johannes. Analytical place-ment: A linear or a quadratic objective function? In Proceedings -Design Automation Conference, pages 427–432, 1991.[159] Jennifer Sleeman, John Dorband, and Milton Halem. A hybrid quan-tum enabled RBM advantage: convolutional autoencoders for quan-tum image compression and generative learning, 1 2020.[160] Siddhartha Srivastava and Veera Sundararaghavan. Machine learningin quantum computers via general Boltzmann machines: Generativeand discriminative training through annealing. ArXiv, 2 2020.[161] Jonas Stein, Danie¨lle Schuman, Magdalena Benkard, Thomas Holger,Wanja Sajko, Michael Ko¨lle, Jonas Nu¨ßlein, Leo Su¨nkel, Olivier Sa-lomon, and Claudia Linnhoff-Popien. Exploring unsupervised anomalydetection with quantum Boltzmann machines in fraud detection.ArXiv, 2023.[162] Tobias Stollenwerk, Elisabeth Lobe, and Martin Jung. Flight gateassignment with a quantum annealer. In Lecture Notes in ComputerScience (including subseries Lecture Notes in Artificial Intelligence204BIBLIOGRAPHYand Lecture Notes in Bioinformatics), volume 11413 LNCS, pages 99–110, 2019.[163] Juexiao Su and Lei He. Fast embedding of constrained satisfac-tion problem to quantum annealer with minimizing chain length. In2017 54th ACM/EDAC/IEEE Design Automation Conference (DAC),pages 1–6, New York, New York, USA, 6 2017. ACM Press.[164] Juexiao Su, Tianheng Tu, and Lei He. A quantum annealing approachfor boolean satisfiability problem. In Proceedings of the 53rd AnnualDesign Automation Conference on - DAC ’16, pages 1–6, New York,New York, USA, 2016. ACM Press.[165] Yuya Sugie, Yuki Yoshida, Normann Mertig, Takashi Takemoto, Hi-roshi Teramoto, Atsuyoshi Nakamura, Ichigaku Takigawa, Shin IchiMinato, Masanao Yamaoka, and Tamiki Komatsuzaki. Graph minorsfrom simulated annealing for annealing machines with sparse connec-tivity. In Lecture Notes in Computer Science, volume 11324 LNCS,pages 111–123. Springer, Cham, 12 2018.[166] Yuki Susa, Yu Yamashiro, Masayuki Yamamoto, and Hidetoshi Nishi-mori. Exponential speedup of quantum annealing by inhomogeneousdriving of the transverse field. Journal of the Physical Society of Japan,87(2), 2018.[167] E. S. Tiunov, V. V. Tiunova (Vyborova), A. E. Ulanov, A. I. Lvovsky,and A. K. Fedorov. Experimental quantum homodyne tomographyvia machine learning. Optica, 7(5):448, 2020.205BIBLIOGRAPHY[168] Giacomo Torlai and Roger G. Melko. Learning thermodynamics withBoltzmann machines. Physical Review B, 94(16), 2016.[169] USA.GOV. National Quantum Initiative. www.quantum.gov, 2023.[170] Jessica Vandebon, Jose Coutinho, and Wayne Luk. Meta-programming design-flow patterns for automating reusable optimi-sations. In ACM International Conference Proceeding Series, pages42–50, 2022.[171] Davide Venturelli and Alexei Kondratyev. Reverse quantum anneal-ing approach to portfolio optimization problems. Quantum MachineIntelligence, 1(1-2):17–30, 2019.[172] Walter Vinci, Lorenzo Buffoni, Hossein Sadeghi, Amir Khoshaman,Evgeny Andriyash, Mohammad H. Amin, Walter Winci, Lorenzo Buf-foni, Hossein Sadeghi, Amir Khoshaman, Evgeny Andriyash, and Mo-hammad H. Amin. A path towards quantum advantage in trainingdeep generative models with quantum annealers. Machine Learning:Science and Technology, 1(4), 12 2019.[173] Walter Vinci and Daniel A. Lidar. Non-stoquastic Hamiltonians inquantum annealing via geometric phases. npj Quantum Information,3(1), 2017.[174] Marc Vuffray, Carleton Coffrin, Yaroslav A. Kharkov, and Andrey Y.Lokhov. Programmable quantum annealers as noisy Gibbs samplers.ArXiv, 12 2020.206BIBLIOGRAPHY[175] Konrad Walus, Timothy J. Dysart, Graham A. Jullien, and R. AriefBudiman. QCADesigner: A rapid design and simulation tool forquantum-dot cellular automata. IEEE Transactions on Nanotechnol-ogy, 3(1):26–31, 3 2004.[176] Guanglei Xu and William S. Oates. Adaptive hyperparameter updat-ing for training restricted Boltzmann machines on quantum annealers.Scientific Reports, 11(1), 2021.[177] Masanao Yamaoka, Chihiro Yoshimura, Masato Hayashi, TakuyaOkuyama, Hidetaka Aoki, and Hiroyuki Mizuno. A 20k-spin Ising chipto solve combinatorial optimization problems with CMOS annealing.IEEE Journal of Solid-State Circuits, 51(1):303–309, 1 2016.[178] Bin Yan and Nikolai A. Sinitsyn. Analytical solution for nonadia-batic quantum annealing to arbitrary Ising spin Hamiltonian. NatureCommunications, 13(1), 2022.[179] Sheir Yarkoni, Elena Raponi, Thomas Ba¨ck, and Sebastian Schmitt.Quantum annealing for industry applications: introduction and re-view. Reports on Progress in Physics, 85(10), 12 2022.[180] Sizhuo Yu and Tahar Nabil. Applying the Hubbard-Stratonovichtransformation to solve scheduling problems under inequality con-straints with quantum annealing. Frontiers in Physics, 9, 2021.[181] Arman Zaribafiyan, Dominic J.J. Marchand, and Seyed SaeedChangiz Rezaei. Systematic and deterministic graph minor embedding207for Cartesian products of graphs. Quantum Information Processing,16(5):136, 4 2017.[182] Stefanie Zbinden, Andreas Ba¨rtschi, Hristo Djidjev, and Stephan Ei-denbenz. Embedding algorithms for quantum annealers with chimeraand pegasus connection topologies. In Lecture Notes in Computer Sci-ence (including subseries Lecture Notes in Artificial Intelligence andLecture Notes in Bioinformatics), volume 12151 LNCS, pages 187–206.Springer, 6 2020.[183] Clarence Zener. Non-adiabatic crossing of energy levels. Proceedingsof the Royal Society of London A: Mathematical, Physical and Engi-neering Sciences, 137(833):696–702, 1932.[184] Yu Zou and Mingjie Lin. Massively simulating adiabatic bifurcationswith FPGA to solve combinatorial optimization. In FPGA 2020 -2020 ACM/SIGDA International Symposium on Field-ProgrammableGate Arrays, pages 65–75, 2020.[185] Christa Zoufal, Aure´lien Lucchi, and Stefan Woerner. Variationalquantum Boltzmann machines. Quantum Machine Intelligence, 3(1),2021.208Appendix AThe Chimera FamilyThe Chimera graph notation C(m,n, t) refers to an m×n grid of tiles. Eachtile is aKt,t biclique with t qubits on each “shore”. One “shore” is connectedhorizontally to the next tile, and the other vertically.Figure A.1: The Chimera graph C(3, 3, 4).The contributions and evaluations made in this thesis refer to three dif-ferent architectures of the D-Wave QAP devices; i.e., Chimera, Pegasus, andZephyr. Both Pegasus and Zephyr graphs have an equivalent Chimera-typeof graph, which allows the minor-embedding methods targeting older devicesto be relevant today.209Appendix A. The Chimera FamilyThe Pegasus graph in Figure A.2 P(2) can be minor-embedded onto aChimera-type graph C(12, 12, 2).Figure A.2: The Pegasus graph P(2). Each node has a unique colour.Figure A.3: The Chimera C(12, 12, 2) equivalent of the Pegasus graph P(2).Each chain/colour corresponds to a unique Pegasus node. Grey nodes haveno assignment.210Appendix A. The Chimera FamilyThe Zephyr graph in Figure A.4 Z(1) can be minor-embedded onto aChimera-type graph C(3, 3, 8).Figure A.4: The Zephyr graph Z(1).Figure A.5: The Chimera C(3, 3, 8) equivalent of the Zephyr graph Z(1).Each chain/colour corresponds to a unique Zephyr node. Grey nodes haveno assignment.211
Thesis/Dissertation
eng
Electrical and Computer Engineering
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Wilton, Steve
Context-aware minor-embedding for quantum annealing processors
Text