# Fast clique minor generation in Chimera qubit connectivity graphs

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2015.

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

- [A Hybrid Quantum-Classical Algorithm for Robust Fitting](https://mlsanity.com/paper/2201.10110/) (2022)
- [A Review of Machine Learning Classification Using Quantum Annealing for Real-world Applications](https://mlsanity.com/paper/2106.02964/) (2021)
- [Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness](https://mlsanity.com/paper/2305.00472/) (2023)
- [CHARME: A chain-based reinforcement learning approach for the minor embedding problem](https://mlsanity.com/paper/2406.07124/) (2024)
- [Hybrid adiabatic quantum computing for tomographic image reconstruction -- opportunities and limitations](https://mlsanity.com/paper/2212.01312/) (2022)
- [Minor Embedding for Quantum Annealing with Reinforcement Learning](https://mlsanity.com/paper/2507.16004/) (2025)
- [Skipper: Improving the Reach and Fidelity of Quantum Annealers by Skipping Long Chains](https://mlsanity.com/paper/2312.00264/) (2023)
- [Energy Scale Degradation in Sparse Quantum Solvers: A Barrier to Quantum Utility](https://mlsanity.com/paper/2503.08303/) (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)

## Abstract (arXiv)

The current generation of D-Wave quantum annealing processor is designed to minimize the energy of an Ising spin configuration whose pairwise interactions lie on the edges of a em Chimera graph mathcal CM,N,L. In order to solve an Ising spin problem with arbitrary pairwise interaction structure, the corresponding graph must be minor-embedded into a Chimera graph. We define a combinatorial class of em native clique minors in Chimera graphs with vertex images of uniform, near minimal size, and provide a polynomial-time algorithm that finds a maximum native clique minor in a given induced subgraph of a Chimera graph. These minors allow improvement over recent work and have immediate practical applications in the field of quantum annealing.