# CHARME: A chain-based reinforcement learning approach for the minor embedding problem

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

## Key facts

- Cited by 3 papers in the map (data through 7 Oct 2026).
- Builds on 14 of its 40 references that are in the map.
- First posted on arXiv 11 Jun 2024.

## Builds on (most cited first, 14 of 14)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Convolutional Neural Networks for Graphs](https://mlsanity.com/paper/1605.05273/) (2016)
- [Deep Convolutional Networks on Graph-Structured Data](https://mlsanity.com/paper/1506.05163/) (2015)
- [Reinforcement learning for optimization of variational quantum circuit architectures](https://mlsanity.com/paper/2103.16089/) (2021)
- [Variational Quantum Reinforcement Learning via Evolutionary Optimization](https://mlsanity.com/paper/2109.00540/) (2021)
- [Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems](https://mlsanity.com/paper/1911.11071/) (2019)
- [A practical heuristic for finding graph minors](https://mlsanity.com/paper/1406.2741/) (2014)
- [Fast clique minor generation in Chimera qubit connectivity graphs](https://mlsanity.com/paper/1507.04774/) (2015)
- [Restricted Boltzmann Machines for galaxy morphology classification with a quantum annealer](https://mlsanity.com/paper/1911.06259/) (2019)
- [Integer programming techniques for minor-embedding in quantum annealers](https://mlsanity.com/paper/1912.08314/) (2019)
- [Optimizing Adiabatic Quantum Program Compilation using a Graph-Theoretic Framework](https://mlsanity.com/paper/1704.01996/) (2017)
- [Template-based Minor Embedding for Adiabatic Quantum Optimization](https://mlsanity.com/paper/1910.02179/) (2019)

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

- [Swift Hydra: Self-Reinforcing Generative Framework for Anomaly Detection with Multiple Mamba Models](https://mlsanity.com/paper/2503.06413/) (2025)
- [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)

## Abstract (arXiv)

Quantum annealing (QA) has great potential to solve combinatorial optimization problems efficiently. However, the effectiveness of QA algorithms is heavily based on the embedding of problem instances, represented as logical graphs, into the quantum processing unit (QPU) whose topology is in the form of a limited connectivity graph, known as the minor embedding problem. Because the minor embedding problem is an NP-hard problem~mboxciteGoodrich2018, existing methods for the minor embedding problem suffer from scalability issues when faced with larger problem sizes. In this paper, we propose a novel approach utilizing Reinforcement Learning (RL) techniques to address the minor embedding problem, named CHARME. CHARME includes three key components: a Graph Neural Network (GNN) architecture for policy modeling, a state transition algorithm that ensures solution validity, and an order exploration strategy for effective training. Through comprehensive experiments on synthetic and real-world instances, we demonstrate the efficiency of our proposed order exploration strategy as well as our proposed RL framework, CHARME. In particular, CHARME yields superior solutions in terms of qubit usage compared to fast embedding methods such as Minorminer and ATOM. Moreover, our method surpasses the OCT-based approach, known for its slower runtime but high-quality solutions, in several cases. In addition, our proposed exploration enhances the efficiency of the training of the CHARME framework by providing better solutions compared to the greedy strategy.