Addressing the Minor-Embedding Problem in Quantum Annealing and Evaluating State-of-the-Art Algorithm Performance
Preprint
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, an algorithm provided by D-Wave and widely recognized as the standard minor-embedding technique in the literature. 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 focus on the Minorminer technique, assessing its capacity to embed problems, the quality of the embeddings produced, and the robustness of the results. 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, as it has not consistently outperformed the worst-case scenario.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- On the emerging potential of quantum annealing hardware for combinatorial optimizationJournal of Heuristics, 2024
- Minor embedding in broken chimera and derived graphs is NP-completeTheoretical Computer Science, 2023
- Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problemsQuantum Information Processing, 2022
- A coherent quantum annealer with Rydberg atomsNature Communications, 2017
- Fast clique minor generation in Chimera qubit connectivity graphsQuantum Information Processing, 2015
- Quantum annealing with manufactured spinsNature, 2011
- Reducibility Among Combinatorial Problems2009
- Multistart Tabu Search Strategies for the Unconstrained Binary Quadratic Optimization ProblemAnnals of Operations Research, 2004
- Graph Minors .XIII. The Disjoint Paths ProblemJournal of Combinatorial Theory, Series B, 1995
- On the complexity of finding iso- and other morphisms for partial k-treesDiscrete Mathematics, 1992