Abstract Quantum annealing has the potential to find low energy solutions of NP-hard problems that can be expressed as quadratic unconstrained binary optimization problems. However, the hardware of the quantum annealer manufactured by D-Wave Systems, which we consider in this work, is sparsely connected and moderately sized (on the order of thousands of qubits), thus necessitating a minor-embedding of a logical problem onto the physical qubit hardware. The combination of relatively small hardware sizes and the necessity of a minor-embedding can mean that solving large optimization problems is not possible on current quantum annealers. In this research, we show that a hybrid approach combining parallel quantum annealing with graph decomposition allows one to solve larger optimization problem accurately. We apply the approach to the Maximum Clique problem on graphs with up to 120 nodes and 6395 edges.
Quantum Annealing (QA) offers a promising framework for solving NP-hard optimization problems, but its effectiveness is constrained by the topology of the underlying quantum hardware. Solving an optimization problem
P via QA involves a hardware-aware circuit compilation which requires representing
P as a graph
GP and embedding it into the hardware connectivity graph
GQ that defines how qubits connect to each other in a QA-based quantum processing unit (QPU).
Minor Embedding (ME) is a possible operational form of this hardware-aware compilation. ME heuristically builds a map that associates each node of
GP -- the logical variables of
P -- to a chain of adjacent nodes in
GQ by means of one of its minors, so that the arcs of
GP are preserved as physical connections among qubits in
GQ.
The static topology of hardwired qubits can clearly lead to inefficient compilations because
GQ cannot be a clique, currently. We propose a methodology and a set of criteria to evaluate how the hardware topology
GQ can negatively affect the embedded problem, thus making the quantum optimization more sensible to noise.
We evaluate the result of ME across two QPU topologies: Zephyr graphs (used in current D-Wave systems) and Havel-Hakimi graphs, which allow controlled variation of the average node degree. This enables us to study how the ratio `number of nodes/number of incident arcs per node' affects ME success rates to map
GP into a minor of
GQ.
Our findings, obtained through ME executed on classical, i.e. non-quantum, architectures, suggest that Havel-Hakimi-based topologies, on average, require shorter qubit chains in the minor of
GP, exhibiting smoother scaling of the largest embeddable
GP as the QPU size increases. These characteristics indicate their potential as alternative designs for QA-based QPUs.
Quantum optimization by annealing constitutes a stochastic global search over QUBO-formulated combinatorial optimization problems. Its performance depends on pre-solving the Minor Embedding (ME) challenge—the
NP-hard problem of mapping logical graphs representing QUBOs onto the quantum hardware. Despite determining solution feasibility and quality, ME remains understudied as a standalone optimization challenge. Current understanding is largely limited to synthetic graphs on isolated topologies, leaving the generalizability of structural predictors across hardware generations unclear. We conduct the first cross-topology study analyzing the MINORMINER heuristic—the de facto industry standard—over ≈550 benchmark graph instances across D-Wave’s Chimera, Pegasus, and Zephyr architectures. Our analyses reveal a functional dissociation between embedding feasibility and cost: topological independence (via Maximum Independent Set ratio) predicts feasibility by identifying structural ‘slack’, while edge density—reflecting clique-like proximity—governs the resource ‘toll’ (chain length). Since ME is a purely graph-theoretic problem, agnostic to the combinatorial origin of the source graph, these structural predictors apply to any QUBO whose logical graph falls within the studied structural regime. This dissociation remains invariant across all architectures, establishing ME as a benchmark for Evolutionary Computation, where the local distribution of edges, rather than global density alone, determines algorithmic difficulty.
Abstract Quantum annealing (QA) is a novel type of analog computation that aims to use quantum mechanical fluctuations to search for optimal solutions of Ising problems. QA in the transverse Ising model, implemented on D-Wave quantum processing units, are available as cloud computing resources. In this study we report concise benchmarks across three generations of D-Wave quantum annealers, consisting of four different devices, for the NP-hard discrete combinatorial optimization problems unweighted maximum clique and unweighted maximum cut on random graphs. The Ising, or equivalently quadratic unconstrained binary optimization, formulation of these problems do not require auxiliary variables for order reduction, and their overall structure and weights are not highly variable, which makes these problems simple test cases to understand the sampling capability of current D-Wave quantum annealers. All-to-all minor embeddings of size 52, with relatively uniform chain lengths, are used for a direct comparison across the Chimera, Pegasus, and Zephyr device topologies. A grid-search over annealing times and the minor embedding chain strengths is performed in order to determine the level of reasonable performance for each device and problem type. Experiment metrics that are reported are approximation ratios for non-broken chain samples, chain break proportions, and time-to-solution for the maximum clique problem instances. How fairly the quantum annealers sample optimal maximum cliques, for instances which contain multiple maximum cliques, is quantified using entropy of the measured ground state distributions. The newest generation of quantum annealing hardware, which has a Zephyr hardware connectivity, performed the best overall with respect to approximation ratios and chain break frequencies.
Minor embedding is essential for mapping largescale combinatorial problems onto quantum annealers, particularly in quantum machine learning and optimization. This work presents an optimized, universal minor-embedding framework that efficiently accommodates complete bipartite graphs onto the hardware topology of quantum annealers. By leveraging the inherent topographical periodicity of the physical quantum adiabatic annealer processor, our method systematically reduces qubit chain lengths, resulting in enhanced stability, computational efficiency, and scalability of quantum annealing. We benchmark our embedding framework against Minorminer, the default heuristic embedding algorithm, for the Pegasus topology, demonstrating that our approach significantly improves embedding quality. Our empirical results show a 99.98% reduction in embedding time for a 120 x 120 complete bipartite graphs. Additionally, our method eliminates long qubit chains, which primarily cause decoherence and computational errors in quantum annealing. These findings advance the scalability of quantum embeddings, particularly for quantum generative models, anomaly detection, and large-scale optimization tasks. Our results establish a foundation for integrating efficient quantum-classical hybrid solutions, paving the way for practical applications in quantum-enhanced machine learning and optimization.
The D-Wave quantum annealers make it possible to obtain high quality solutions of NP-hard problems by mapping a problem in a QUBO (quadratic unconstrained binary optimization) or Ising form to the physical qubit connectivity structure on the D-Wave chip. However, the latter is restricted in that only a fraction of all pairwise couplers between physical qubits exists. Modeling the connectivity structure of a given problem instance thus necessitates the computation of a minor embedding of the variables in the problem specification onto the logical qubits, which consist of several physical qubits "chained" together to act as a logical one. After annealing, it is however not guaranteed that all chained qubits get the same value (-1 or +1 for an Ising model, and 0 or 1 for a QUBO), and several approaches exist to assign a final value to each logical qubit (a process called "unembedding"). In this work, we present tailored unembedding techniques for four important NP-hard problems: the Maximum Clique, Maximum Cut, Minimum Vertex Cover, and Graph Partitioning problems. Our techniques are simple and yet make use of structural properties of the problem being solved. Using Erdös-Rényi random graphs as inputs, we compare our unembedding techniques to three popular ones (majority vote, random weighting, and minimize energy). We demonstrate that our proposed algorithms outperform the currently available ones in that they yield solutions of better quality, while being computationally equally efficient.