# Adiabatic Quantum Graph Matching with Permutation Matrix Constraints

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 67 references that are in the map.
- First posted on arXiv 8 Jul 2021.

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

- [Quantum Variational Autoencoder](https://mlsanity.com/paper/1802.05779/) (2018)
- [Application of Quantum Annealing to Training of Deep Neural Networks](https://mlsanity.com/paper/1510.06356/) (2015)
- [Traffic flow optimization using a quantum annealer](https://mlsanity.com/paper/1708.01625/) (2017)
- [A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching](https://mlsanity.com/paper/1612.05476/) (2016)
- [Nonnegative/binary matrix factorization with a D-Wave quantum annealer](https://mlsanity.com/paper/1704.01605/) (2017)
- [A Quantum Computational Approach to Correspondence Problems on Point Sets](https://mlsanity.com/paper/1912.12296/) (2019)
- [DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems](https://mlsanity.com/paper/1711.10733/) (2017)
- [Image classification using quantum inference on the D-Wave 2X](https://mlsanity.com/paper/1905.13215/) (2019)
- [Quantum Robust Fitting](https://mlsanity.com/paper/2006.06986/) (2020)
- [Convex Relaxations for Permutation Problems](https://mlsanity.com/paper/1306.4805/) (2013)
- [A new look at reweighted message passing](https://mlsanity.com/paper/1309.5655/) (2013)
- [Graph isomorphism and adiabatic quantum computing](https://mlsanity.com/paper/1304.5773/) (2013)
- [A regression algorithm for accelerated lattice QCD that exploits sparse inference on the D-Wave quantum annealer](https://mlsanity.com/paper/1911.06267/) (2019)
- [Algorithm engineering for a quantum annealing platform](https://mlsanity.com/paper/1410.2628/) (2014)

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

- [Adiabatic Quantum Computing for Multi Object Tracking](https://mlsanity.com/paper/2202.08837/) (2022)
- [A Hybrid Quantum-Classical Algorithm for Robust Fitting](https://mlsanity.com/paper/2201.10110/) (2022)
- [Quantum Motion Segmentation](https://mlsanity.com/paper/2203.13185/) (2022)
- [Quantum Multi-Model Fitting](https://mlsanity.com/paper/2303.15444/) (2023)
- [CCuantuMM: Cycle-Consistent Quantum-Hybrid Matching of Multiple Shapes](https://mlsanity.com/paper/2303.16202/) (2023)
- [QClusformer: A Quantum Transformer-based Framework for Unsupervised Visual Clustering](https://mlsanity.com/paper/2405.19722/) (2024)
- [Quantum Visual Feature Encoding Revisited](https://mlsanity.com/paper/2405.19725/) (2024)
- [Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization](https://mlsanity.com/paper/2203.12633/) (2022)
- [Robust Fitting on a Gate Quantum Computer](https://mlsanity.com/paper/2409.02006/) (2024)
- [Quantum-enhanced Computer Vision: Going Beyond Classical Algorithms](https://mlsanity.com/paper/2510.07317/) (2025)
- [QuAnt: Quantum Annealing with Learnt Couplings](https://mlsanity.com/paper/2210.08114/) (2022)
- [Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing](https://mlsanity.com/paper/2310.12153/) (2023)
- [Projected Stochastic Gradient Descent with Quantum Annealed Binary Gradients](https://mlsanity.com/paper/2310.15128/) (2023)
- [Quantum Artificial Intelligence: A Brief Survey](https://mlsanity.com/paper/2408.10726/) (2024)
- [Quantum Annealing for Computer Vision Minimization Problems](https://mlsanity.com/paper/2312.12848/) (2023)
- [Quantum-Hybrid Stereo Matching With Nonlinear Regularization and Spatial Pyramids](https://mlsanity.com/paper/2312.16118/) (2023)
- [Convex Joint Graph Matching and Clustering via Semidefinite Relaxations](https://mlsanity.com/paper/2110.11335/) (2021)
- [Training Multilayer Perceptrons by Sampling with Quantum Annealers](https://mlsanity.com/paper/2303.12352/) (2023)
- [Outlier-Robust Multi-Model Fitting on Quantum Annealers](https://mlsanity.com/paper/2504.13836/) (2025)
- [HQC-NBV: A Hybrid Quantum-Classical View Planning Approach](https://mlsanity.com/paper/2505.05212/) (2025)

## Abstract (arXiv)

Matching problems on 3D shapes and images are challenging as they are frequently formulated as combinatorial quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. In this work, we address such problems with emerging quantum computing technology and propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. We investigate several ways to inject permutation matrix constraints in a quadratic unconstrained binary optimization problem which can be mapped to quantum hardware. We focus on obtaining a sufficient spectral gap, which further increases the probability to measure optimal solutions and valid permutation matrices in a single run. We perform our experiments on the quantum computer D-Wave 2000Q (2^11 qubits, adiabatic). Despite the observed discrepancy between simulated adiabatic quantum computing and execution on real quantum hardware, our reformulation of permutation matrix constraints increases the robustness of the numerical computations over other penalty approaches in our experiments. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures, which opens up multiple new directions for solving matching problems in 3D computer vision and graphics.