Optimization Online


Template-based Minor Embedding for Adiabatic Quantum Optimization

Thiago Serra (thiago.serra***at***bucknell.edu)
Teng Huang (teng.huang***at***uconn.edu)
Arvind Raghunathan (raghunathan***at***merl.com)
David Bergman (david.bergman***at***uconn.edu)

Abstract: Quantum Annealing (QA) can be used to quickly obtain near-optimal solutions for Quadratic Unconstrained Binary Optimization (QUBO) problems. In QA hardware, each decision variable of a QUBO should be mapped to one or more adjacent qubits in such a way that pairs of variables defining a quadratic term in the objective function are mapped to some pair of adjacent qubits. However, qubits have limited connectivity in existing QA hardware. This has spurred work on preprocessing algorithms for embedding the graph representing problem variables with quadratic terms in the hardware graph representing qubits adjacencies, such as the Chimera graph in hardware produced by D-Wave Systems. In this paper, we use integer linear programming to search for an embedding of the problem graph into certain classes of minors of the Chimera graph, which we call template embeddings. One of these classes corresponds to complete bipartite graphs, for which we show the limitation of the existing approach based on minimum Odd Cycle Transversals (OCTs). Some of the formulations presented are exact, and thus can be used to certify the absence of a minor embedding. On an extensive test set consisting of random graphs from five different classes of varying size and sparsity, we can embed 38% more graphs than a state-of-the-art OCT-based approach.


Category 1: Integer Programming (0-1 Programming )

Category 2: Applications -- Science and Engineering (Other )


Download: [PDF]

Entry Submitted: 10/09/2019
Entry Accepted: 10/09/2019
Entry Last Modified: 01/25/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society