Addressing the Minor-Embedding Problem in Quantum Annealing and Evaluating State-of-the-Art Algorithm Performance

Aitor Gómez-Tejedor, Eneko Osaba, Esther Villar-Rodriguez · 2025

Read Addressing the Minor-Embedding Problem in Quantum Annealing and Evaluating State-of-the-Art Algorithm Performance by Aitor Gómez-Tejedor, Eneko Osaba, Esther Villar-Rodriguez (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-13376.txt.

Introduction

Aitor Gómez-Tejedor, Eneko Osaba, and Esther Villar-Rodriguez wrote this computer science paper, published in 2025. It studies the unglamorous step that decides whether quantum annealers succeed: squeezing a problem's variables onto the machine's fixed wiring.

Annealers solve problems shaped like their hardware easily, but foreign shapes must be embedded, chaining several physical qubits per variable. The authors first measured how embedding quality drives results on D-Wave machines. Longer average chains clearly tracked worse solution errors. They then graded the standard embedding tool, Minorminer, on random graphs for quality, robustness, and speed. A deterministic clique embedder served as the worst-case yardstick. The verdict: the standard tool leaves significant room for improvement, and embedding deserves research attention equal to the hardware itself.

Catalog record

CREATORAitor Gómez-Tejedor, Eneko Osaba, Esther Villar-Rodriguez
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE83 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-13376

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Addressing the Minor-Embedding Problem in Quantum Annealing and Evaluating State-of-the-Art Algorithm Performance Aitor Gómez-Tejedor, Eneko Osaba, Esther Villar-Rodriguez Abstract This study addresses the minor-embedding problem, which involves mapping the variables of an Ising model onto a quantum annealing processor. The primary motivation stems from the observed performance disparity of quantum annealers when solving problems suited to the processor’s architecture versus those with non-hardware-native topologies. Our research has two main objectives: i) to analyze the impact of embedding quality on the performance of D-Wave Systems quantum annealers, and ii) to evaluate the quality of the embeddings generated by Minorminer, the standard minor-embedding technique in the quantum annealing literature, provided by D-Wave. Regarding the first objective, our experiments reveal a clear correlation between the average chain length of embeddings and the relative errors of the solutions sampled. This underscores the critical influence of embedding quality on quantum annealing performance. For the second objective, we evaluate Minorminer’s embedding capabilities, the quality and robustness of its embeddings, and its execution-time performance on Erdös-Rényi graphs . We also compare its performance with Clique Embedding, another algorithm developed by D-Wave, which is deterministic and designed to embed fully connected Ising models into quantum annealing processors, serving as a worst-case scenario. The results demonstrate that there is significant room for improvement for Minorminer, suggesting that more effective embedding strategies could lead to meaningful gains in quantum annealing performance. Journal: Future Generation Computer Systems \forestapplylibrarydefaults linguistics 1 Introduction Quantum computing (QC) is recognized as the next significant advancement in computing, with substantial potential across various fields, including combinatorial optimization. In this domain, QC can address problems in fundamentally different ways compared to classical methods, potentially offering significant advantages. Despite its promising potential, we are currently in the noisy intermediate scale quantum (NISQ) [ 40 ] era, which means that the technology is still in early development and faces hardware limitations. These limitations include the poor quality of qubits, which causes undesirable behavior, and a reduced number of qubits and couplers (connections between pairs of qubits) in the processors. In spite of these restrictions, extensive research is being conducted on the software and algorithmic aspects of the paradigm. Much of this research aims to address these constraints and maximize the potential of current NISQ-era quantum computers. Examples of research areas within this category include the design of hybrid methods that integrate classical and quantum processors [ 38 , 16 , 13 ] , as well as error correction and error mitigation techniques [ 28 , 10 ] . Among the various types of quantum computers, the gate-model and quantum annealing are the most prominent. This study focuses on the latter. Quantum annealing (QA) is grounded in the principles of adiabatic quantum computing, as initially proposed by Farhi et al. [ 15 ] . The adiabatic quantum computing paradigm starts by initializing a quantum system in an easy-to-prepare ground state. Then, the system’s time-dependent Hamiltonian is slowly evolved within the adiabatic theorem [ 33 ] regime until its final form is reached, where the state desired to be computed is encoded as the ground state. By evolving the system slowly enough, the adiabatic theorem states that there is a high probability that the final state of the system will be the desired ground state. Quantum annealing modifies this approach by relaxing the requirement for slow evolution, which is dependent on the problem and can be exponentially large. This relaxation allows for faster execution times, albeit with a reduced probability of achieving the ground state. There are different models for building quantum annealers, such as those based on Rydberg atoms [ 18 ] , trapped ions [ 41 ] or superconducting flux qubits [ 24 ] , with the latter being the most recognized to date. Additionally, several companies are working on this technology and building their own devices, such as NEC 1 1 1 https://parityqc.com/a-new-quantum-annealer-by-nec , Qilimanjaro 2 2 2 https://qilimanjaro.tech , and D-Wave Systems 3 3 3 https://www.dwavesys.com . In the literature, the reference quantum annealers are those developed by D-Wave Systems, which are specifically designed to solve Ising models by sampling low-energy states of a given Hamiltonian in which the Ising model is encoded [ 23 ] . Consequently, these annealers forfeit the computational universality inherent in general quantum annealing. However, the Ising model is mathematically equivalent to solving a quadratic unconstrained binary optimization (QUBO) model, and many combinatorial optimization problems can be formulated as QUBOs [ 19 ] , and therefore, as Ising models [ 30 ] . This study exhaustively analyzes the minor-embedding problem, a graph theoretical problem responsible for mapping the variables of the Ising model onto the quantum annealing processor. The motivation lies in the observed performance disparity of D-Wave’s processors when addressing hardware-native problems versus real-world optimization problems with generic topologies. Specifically, quantum annealers exhibit competitive performance with certain classical solvers when solving problems that are inherently suited to the processor’s architecture, thereby eliminating the need for minor-embedding, as shown in [ 46 ] and [ 3 ] . However, when applied to optimization tasks whose Ising model formulation has a non-hardware-native topology, the solution quality produced by quantum annealers is significantly inferior to that achieved by classical solvers [ 34 , 48 ] . This disparity highlights the importance of the minor-embedding problem in the context of quantum annealing. Furthermore, the mapping is not only critical but also highly complex to solve. The challenge arises from the limited connectivity of the processors, making the mapping of any Ising model non-trivial. In fact, the lower the hardware connectivity, the lower the likelihood that a problem can be trivially mapped onto the hardware. For instance, consider an Ising model where a variable interacts with 16 others, while the hardware qubits are only connected to 15 other qubits. This discrepancy hinders a direct one-to-one mapping of variables to qubits, necessitating the use of multiple qubits to represent a single variable. In this context, solving the minor-embedding problem while minimizing the number of qubits in the embedding is crucial. Using more qubits increases the solution space and, given the noise in the processors and its random nature, it also raises the error rate. However, finding an embedding for any Ising model into any processor while minimizing the number of qubits is an NP-Hard problem. Note that the minor-embedding problem in the context of quantum annealing will remain in that complexity class as long as QA processors do not possess all-to-all connectivity. This condition is likely to persist in the future because, due to the 2D nature of superconducting-based processors, it is extremely challenging to construct all-to-all hardware of non-small sizes [ 8 ] . Because of the complexity of the minor-embedding problem, heuristic methods have to be employed for its solving. In the literature, the standard algorithm to solve the minor-embedding problem is Minorminer . This method, proposed by Cai et al. in 2014 [ 9 ] , uses a greedy approach that iteratively constructs the embedding while minimizing at each step the total number qubits used to represent each variable. Minorminer is accessible in the D-Wave problem solving platform [ 23 ] as the standard to embed generic problems into the different available processors. Besides

Read the complete text