# Integer programming techniques for minor-embedding in quantum annealers

arXiv: https://arxiv.org/abs/1912.08314 · HTML: https://mlsanity.com/paper/1912.08314/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Dec 2019.

## Built on by (most cited first, 5 of 5)

- [CHARME: A chain-based reinforcement learning approach for the minor embedding problem](https://mlsanity.com/paper/2406.07124/) (2024)
- [Minor Embedding for Quantum Annealing with Reinforcement Learning](https://mlsanity.com/paper/2507.16004/) (2025)
- [Addressing the Minor-Embedding Problem in Quantum Annealing and Evaluating State-of-the-Art Algorithm Performance](https://mlsanity.com/paper/2504.13376/) (2025)
- [Infeasibility Aware Large Language Models for Combinatorial Optimization](https://mlsanity.com/paper/2604.01455/) (2026)
- [Enhanced Reinforcement Learning-based Process Synthesis via Quantum Computing](https://mlsanity.com/paper/2605.21213/) (2026)

## Abstract (arXiv)

A major limitation of current generations of quantum annealers is the sparse connectivity of manufactured qubits in the hardware graph. This technological limitation generated considerable interest, motivating efforts to design efficient and adroit minor-embedding procedures that bypass sparsity constraints. In this paper, starting from a previous equational formulation by Dridi et al. (arXiv:1810.01440), we propose integer programming (IP) techniques for solving the minor-embedding problem. The first approach involves a direct translation from the previous equational formulation to IP, while the second decomposes the problem into an assignment master problem and fiber condition checking subproblems. The proposed methods are able to detect instance infeasibility and provide bounds on solution quality, capabilities not offered by currently employed heuristic methods. We demonstrate the efficacy of our methods with an extensive computational assessment involving three different families of random graphs of varying sizes and densities. The direct translation as a monolithic IP model can be solved with existing commercial solvers yielding valid minor-embeddings, however, is outperformed overall by the decomposition approach. Our results demonstrate the promise of our methods for the studied benchmarks, highlighting the advantages of using IP technology for minor-embedding problems.