# Q-Match: Iterative Shape Matching via Quantum Annealing

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 75 references that are in the map.
- First posted on arXiv 6 May 2021.

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

- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [Deep Functional Maps: Structured Prediction for Dense Shape Correspondence](https://mlsanity.com/paper/1704.08686/) (2017)
- [Support vector machines on the D-Wave quantum annealer](https://mlsanity.com/paper/1906.06283/) (2019)
- [Quantum Permutation Synchronization](https://mlsanity.com/paper/2101.07755/) (2021)
- [A practical heuristic for finding graph minors](https://mlsanity.com/paper/1406.2741/) (2014)
- [Submodular Functions: from Discrete to Continous Domains](https://mlsanity.com/paper/1511.00394/) (2015)
- [Efficient Deformable Shape Correspondence via Kernel Matching](https://mlsanity.com/paper/1707.08991/) (2017)
- [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)
- [Quantum-soft QUBO Suppression for Accurate Object Detection](https://mlsanity.com/paper/2007.13992/) (2020)
- [Image classification using quantum inference on the D-Wave 2X](https://mlsanity.com/paper/1905.13215/) (2019)
- [Convex Relaxations for Permutation Problems](https://mlsanity.com/paper/1306.4805/) (2013)
- [Alternating Direction Graph Matching](https://mlsanity.com/paper/1611.07583/) (2016)
- [Performance of a Quantum Annealer for Ising Ground State Computations on Chimera Graphs](https://mlsanity.com/paper/1904.11965/) (2019)

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

- [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)
- [Denoising Functional Maps: Diffusion Models for Shape Correspondence](https://mlsanity.com/paper/2503.01845/) (2025)
- [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)
- [Q-Seg: Quantum Annealing-Based Unsupervised Image Segmentation](https://mlsanity.com/paper/2311.12912/) (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)
- [Quantum Visual Fields with Neural Amplitude Encoding](https://mlsanity.com/paper/2508.10900/) (2025)
- [Quantum Annealing for Single Image Super-Resolution](https://mlsanity.com/paper/2304.08924/) (2023)
- [Kissing to Find a Match: Efficient Low-Rank Permutation Representation](https://mlsanity.com/paper/2308.13252/) (2023)
- [3D-QAE: Fully Quantum Auto-Encoding of 3D Point Clouds](https://mlsanity.com/paper/2311.05604/) (2023)
- [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)
- [Fast Globally Optimal and Geometrically Consistent 3D Shape Matching](https://mlsanity.com/paper/2504.06385/) (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)
- [Quantum-Hybrid Stereo Matching With Nonlinear Regularization and Spatial Pyramids](https://mlsanity.com/paper/2312.16118/) (2023)
- [Training Multilayer Perceptrons by Sampling with Quantum Annealers](https://mlsanity.com/paper/2303.12352/) (2023)
- [Qsco: A Quantum Scoring Module for Open-set Supervised Anomaly Detection](https://mlsanity.com/paper/2405.16368/) (2024)
- [Outlier-Robust Multi-Model Fitting on Quantum Annealers](https://mlsanity.com/paper/2504.13836/) (2025)
- [Quantum Multiple Rotation Averaging](https://mlsanity.com/paper/2602.10115/) (2026)
- [HQC-NBV: A Hybrid Quantum-Classical View Planning Approach](https://mlsanity.com/paper/2505.05212/) (2025)
- [Quantum-Enhanced Similarity Measures for Polarimetric Materials Classification](https://mlsanity.com/paper/2606.07766/) (2026)
- [TokenMatch: 3D Mesh Correspondence Transformer with Curvature-Guided Tokenisation](https://mlsanity.com/paper/2609.04202/) (2026)

## Abstract (arXiv)

Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) that becomes infeasible for shapes with high sampling density. A promising research direction is to tackle such quadratic optimization problems over binary variables with quantum annealing, which allows for some problems a more efficient search in the solution space. Unfortunately, enforcing the linear equality constraints in QAPs via a penalty significantly limits the success probability of such methods on currently available quantum hardware. To address this limitation, this paper proposes Q-Match, i.e., a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm, which allows solving problems of an order of magnitude larger than current quantum methods. It implicitly enforces the QAP constraints by updating the current estimates in a cyclic fashion. Further, Q-Match can be applied iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems. Using the latest quantum annealer, the D-Wave Advantage, we evaluate the proposed method on a subset of QAPLIB as well as on isometric shape matching problems from the FAUST dataset.