# Minor Embedding for Quantum Annealing with Reinforcement Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Quantum reinforcement learning, one of 15 directions in Deep reinforcement learning methods.
- Builds on 15 of its 54 references that are in the map.
- First posted on arXiv 21 Jul 2025.

## Placed in

- Deep reinforcement learning methods / [Quantum reinforcement learning](https://mlsanity.com/deeprl/quantum-reinforcement-learning/)

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [A Closer Look at Invalid Action Masking in Policy Gradient Algorithms](https://mlsanity.com/paper/2006.14171/) (2020)
- [Support vector machines on the D-Wave quantum annealer](https://mlsanity.com/paper/1906.06283/) (2019)
- [A practical heuristic for finding graph minors](https://mlsanity.com/paper/1406.2741/) (2014)
- [Nonnegative/binary matrix factorization with a D-Wave quantum annealer](https://mlsanity.com/paper/1704.01605/) (2017)
- [Feature Selection for Recommender Systems with Quantum Computing](https://mlsanity.com/paper/2110.05089/) (2021)
- [Towards Feature Selection for Ranking and Classification Exploiting Quantum Annealers](https://mlsanity.com/paper/2205.04346/) (2022)
- [Fast clique minor generation in Chimera qubit connectivity graphs](https://mlsanity.com/paper/1507.04774/) (2015)
- [Integer programming techniques for minor-embedding in quantum annealers](https://mlsanity.com/paper/1912.08314/) (2019)
- [CHARME: A chain-based reinforcement learning approach for the minor embedding problem](https://mlsanity.com/paper/2406.07124/) (2024)
- [Analyzing the Effectiveness of Quantum Annealing with Meta-Learning](https://mlsanity.com/paper/2408.00570/) (2024)
- [Adaptive Learning for Quantum Linear Regression](https://mlsanity.com/paper/2408.02833/) (2024)

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

- [Infeasibility Aware Large Language Models for Combinatorial Optimization](https://mlsanity.com/paper/2604.01455/) (2026)

## Abstract (arXiv)

Quantum Annealing (QA) is a quantum computing paradigm for solving combinatorial optimization problems formulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. An essential step in QA is minor embedding, which maps the problem graph onto the sparse topology of the quantum processor. This process is computationally expensive and scales poorly with increasing problem size and hardware complexity. Existing heuristics are often developed for specific problem graphs or hardware topologies and are difficult to generalize. Reinforcement Learning (RL) offers a promising alternative by treating minor embedding as a sequential decision-making problem, where an agent learns to construct minor embeddings by iteratively mapping the problem variables to the hardware qubits. We propose a RL-based approach to minor embedding using a Proximal Policy Optimization agent, testing its ability to embed both fully connected and randomly generated problem graphs on two hardware topologies, Chimera and Zephyr. The results show that our agent consistently produces valid minor embeddings, with reasonably efficient number of qubits, in particular on the more modern Zephyr topology. Our proposed approach is also able to scale to moderate problem sizes and adapts well to different graph structures, highlighting RL's potential as a flexible and general-purpose framework for minor embedding in QA.