We group all known quadratizations of cubic and quartic terms in binary optimization problems into six and seven unique graphs respectively. We then perform a minor embedding of these graphs onto the well-known Chimera graph, and the brand new Pegasus graph. We conclude with recommendations for which gadgets are best to use when aiming to reduce the total number of qubits required to embed a problem.
We group all known quadratizations of cubic and quartic terms in binary optimization problems into six and seven unique graphs respectively. We then perform a minor embedding of these graphs onto the well-known Chimera graph, and the brand new Pegasus graph. We conclude with recommendations for which gadgets are best to use when aiming to reduce the total number of qubits required to embed a problem.
We propose two new algorithms – Spring-Based MinorMiner (SPMM) and Clique-Based MinorMiner (CLMM) – which take as input the connectivity graph of a Quadratic Unconstrained Binary Optimization (QUBO) problem and produce as output an embedding of the input graph on a host graph that models the topology of a quantum computing device. As host graphs, we take the Chimera graph and the Pegasus graph, which are the topology graphs of D-Wave’s 2000 qubit (first introduced in 2017) and 5000 qubit (expected 2020) quantum annealer devices, respectively. We evaluate our algorithms on a large set of random graph QUBO inputs (Erdős-Renyi Gn,p, Barabasi-Albert and d-regular graphs) on both host topologies against other embedding algorithms. For the Pegasus topology, we find that CLMM outperforms all other algorithms at edge densities larger than 0.08, while SPMM wins at edge densities smaller than 0.08 for Erdős-Renyi graphs, with very similar transition densities for the other graph classes. Surprisingly, the standard D-Wave MinorMiner embedding algorithm – while also getting slightly outperformed by SPMM for sparse and very dense graphs on Chimera – does not manage to extend its overall good performance on Chimera to Pegasus as it fails to embed even medium-density graphs on 175–180 nodes which are known to have clique embeddings on Pegasus.
Abstract In order to solve real-world combinatorial optimization problems with a D-Wave quantum annealer, it is necessary to embed the problem at hand into the D-Wave hardware graph, namely Chimera or Pegasus. Most hard real-world problems exhibit a strong connectivity. For the worst-case scenario of a complete graph, there exists an efficient solution for the embedding into the ideal Chimera graph. However, since real machines almost always have broken qubits, it is necessary to find an embedding into the broken hardware graph. We present a new approach to the problem of embedding complete graphs into broken Chimera graphs. This problem can be formulated as an optimization problem, more precisely as a matching problem with additional linear constraints. Although being NP-hard in general, it is fixed-parameter tractable in the number of inaccessible vertices in the Chimera graph. We tested our exact approach on various instances of broken hardware graphs, both related to real hardware and randomly generated. For fixed runtime, we were able to embed larger complete graphs compared to previous, heuristic approaches. As an extension, we developed a fast heuristic algorithm which enables us to solve even larger instances. We compared the performance of our heuristic and exact approaches.
The embedding is an essential step when calculating on the D-Wave machine. In this work, we show the hardness of the embedding problem for all types of currently existing hardware, represented by the Chimera and the derived Pegasus and Zephyr graphs, containing unavailable qubits. We construct certain broken Chimera graphs, where it is hard to find a Hamiltonian cycle. As the Hamiltonian cycle problem is a special case of the embedding problem, this proves the general complexity result for the Chimera graphs. By exploiting the subgraph relation between the Chimera and the derived graphs, the proof is then further extended to the Pegasus graphs and to the Zephyr graphs.
Minor embedding is a required compilation step for quantum annealing, mapping logical problem graphs onto sparse hardware topologies. Despite its central role in determining solution quality, no standardized benchmark exists for comparing embedding algorithms: prior studies use incompatible graph libraries, inconsistent metrics, and non-reproducible experimental setups, making cross-algorithm comparisons unreliable. We present Ember (Embedding Minor Benchmark for Evaluative Reproducibility), an open-source benchmarking framework addressing this gap. Ember provides a standardized algorithm interface with seeded, reproducible execution infrastructure; a diverse graph library of 24,016 instances spanning structured, random, and physics-motivated problem types not previously used in embedding benchmarks; and a unified analysis pipeline supporting all three current D-Wave hardware topologies (Chimera, Pegasus, Zephyr). We evaluate five algorithms across the full library on Chimera and find that no algorithm dominates universally: rankings vary systematically with graph structure, and the best algorithm depends on the family being embedded. We also examine the effects of hardware topology (including Pegasus and Zephyr), qubit error rates, and evaluate a reinforcement-learning approach (CHARME) within a narrower test set. Ember is available at https://github.com/zachmacsmith/ember and is installable via pip install ember-qc.
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 into 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). One of the formulations presented is exact and thus can be used to certify the absence of a minor embedding using that template. On an extensive test set consisting of random graphs from five different classes of varying size and sparsity, we can embed more graphs than a state-of-the-art OCT-based approach, our approach scales better with the hardware size, and the runtime is generally orders of magnitude smaller. Summary of Contribution: Our work combines classical and quantum computing for operations research by showing that integer linear programming can be successfully used as a preprocessing step for adiabatic quantum optimization. We use it to determine how a quadratic unconstrained binary optimization problem can be solved by a quantum annealer in which the qubits are coupled as in a Chimera graph, such as in the quantum annealers currently produced by D-Wave Systems. The paper also provides a timely introduction to adiabatic quantum computing and related work on minor embeddings.
Pegasus is a graph which offers substantially increased connectivity between the qubits of quantum annealing hardware compared to the graph Chimera. It is the first fundamental change in the connectivity graph of quantum annealers built by D-Wave since Chimera was introduced in 2009 and then used in 2011 for D-Wave's first commercial quantum annealer. In this article we describe an algorithm which defines the connectivity of Pegasus and we provide what we believe to be the best way to graphically visualize Pegasus in order to see which qubits couple to each other. As supplemental material, we provide a wide variety of different visualizations of Pegasus which expose different properties of the graph in different ways. We provide an open source code for generating the many depictions of Pegasus that we show.