# Quantum Permutation Synchronization

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 111 references that are in the map.
- First posted on arXiv 19 Jan 2021.

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

- [Past, Present, and Future of Simultaneous Localization And Mapping: Towards the Robust-Perception Age](https://mlsanity.com/paper/1606.05830/) (2016)
- [SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group](https://mlsanity.com/paper/1612.07386/) (2016)
- [Learning multiview 3D point cloud registration](https://mlsanity.com/paper/2001.05119/) (2020)
- [CaSPR: Learning Canonical Spatiotemporal Point Cloud Representations](https://mlsanity.com/paper/2008.02792/) (2020)
- [Deep Bingham Networks: Dealing with Uncertainty and Ambiguity in Pose Estimation](https://mlsanity.com/paper/2012.11002/) (2020)
- [Multi-Image Matching via Fast Alternating Minimization](https://mlsanity.com/paper/1505.04845/) (2015)
- [Traffic flow optimization using a quantum annealer](https://mlsanity.com/paper/1708.01625/) (2017)
- [Learning Transformation Synchronization](https://mlsanity.com/paper/1901.09458/) (2019)
- [A practical heuristic for finding graph minors](https://mlsanity.com/paper/1406.2741/) (2014)
- [Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope](https://mlsanity.com/paper/1904.05814/) (2019)
- [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)
- [Bayesian Pose Graph Optimization via Bingham Distributions and Tempered Geodesic MCMC](https://mlsanity.com/paper/1805.12279/) (2018)
- [Synchronizing Probability Measures on Rotations via Optimal Transport](https://mlsanity.com/paper/2004.00663/) (2020)
- [Quantum-soft QUBO Suppression for Accurate Object Detection](https://mlsanity.com/paper/2007.13992/) (2020)
- [Global registration of multiple point clouds using semidefinite programming](https://mlsanity.com/paper/1306.5226/) (2013)
- [A Solution for Multi-Alignment by Transformation Synchronisation](https://mlsanity.com/paper/1410.8546/) (2014)
- [Synchronisation of Partial Multi-Matchings via Non-negative Factorisations](https://mlsanity.com/paper/1803.06320/) (2018)
- [Multi-Image Semantic Matching by Mining Consistent Features](https://mlsanity.com/paper/1711.07641/) (2017)
- [Bayesian Deep Learning on a Quantum Computer](https://mlsanity.com/paper/1806.11463/) (2018)
- [Generic Primitive Detection in Point Clouds Using Novel Minimal Quadric Fits](https://mlsanity.com/paper/1901.01255/) (2019)
- [Graph isomorphism and adiabatic quantum computing](https://mlsanity.com/paper/1304.5773/) (2013)
- [Distributed methods for synchronization of orthogonal matrices over graphs](https://mlsanity.com/paper/1701.07248/) (2017)
- [CAD Priors for Accurate and Flexible Instance Reconstruction](https://mlsanity.com/paper/1705.03111/) (2017)
- [A regression algorithm for accelerated lattice QCD that exploits sparse inference on the D-Wave quantum annealer](https://mlsanity.com/paper/1911.06267/) (2019)
- [Path-Invariant Map Networks](https://mlsanity.com/paper/1812.11647/) (2018)

## Built on by (most cited first, 30 of 32)

- [Multiway Non-rigid Point Cloud Registration via Learned Functional Map Synchronization](https://mlsanity.com/paper/2111.12878/) (2021)
- [Q-Match: Iterative Shape Matching via Quantum Annealing](https://mlsanity.com/paper/2105.02878/) (2021)
- [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)
- [Matching Point Sets with Quantum Circuit Learning](https://mlsanity.com/paper/2102.06697/) (2021)
- [Quantum Visual Feature Encoding Revisited](https://mlsanity.com/paper/2405.19725/) (2024)
- [Penalty Weights in QUBO Formulations: Permutation Problems](https://mlsanity.com/paper/2206.11040/) (2022)
- [Towards Quantum Graph Neural Networks: An Ego-Graph Learning Approach](https://mlsanity.com/paper/2201.05158/) (2022)
- [Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization](https://mlsanity.com/paper/2203.12633/) (2022)
- [Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation](https://mlsanity.com/paper/2110.00053/) (2021)
- [Quantum Visual Fields with Neural Amplitude Encoding](https://mlsanity.com/paper/2508.10900/) (2025)
- [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)
- [Pooling Image Datasets With Multiple Covariate Shift and Imbalance](https://mlsanity.com/paper/2403.02598/) (2024)
- [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)
- [QUBO Decision Tree: Annealing Machine Extends Decision Tree Splitting](https://mlsanity.com/paper/2303.09772/) (2023)
- [Quantum Annealing for Computer Vision Minimization Problems](https://mlsanity.com/paper/2312.12848/) (2023)
- [Is Quantum Optimization Ready? An Effort Towards Neural Network Compression using Adiabatic Quantum Computing](https://mlsanity.com/paper/2505.16332/) (2025)
- [Riemannian Functional Map Synchronization for Probabilistic Partial Correspondence in Shape Networks](https://mlsanity.com/paper/2111.14762/) (2021)
- [QSpeech: Low-Qubit Quantum Speech Application Toolkit](https://mlsanity.com/paper/2205.13221/) (2022)
- [Training Multilayer Perceptrons by Sampling with Quantum Annealers](https://mlsanity.com/paper/2303.12352/) (2023)
- [Non-Negative Spherical Relaxations for Universe-Free Multi-Matching and Clustering](https://mlsanity.com/paper/2310.13311/) (2023)
- [Outlier-Robust Multi-Model Fitting on Quantum Annealers](https://mlsanity.com/paper/2504.13836/) (2025)
- [COMPOSE: Hypergraph Cover Optimization for Multi-view 3D Human Pose Estimation](https://mlsanity.com/paper/2601.09698/) (2026)

## Abstract (arXiv)

We present QuantumSync, the first quantum algorithm for solving a synchronization problem in the context of computer vision. In particular, we focus on permutation synchronization which involves solving a non-convex optimization problem in discrete variables. We start by formulating synchronization into a quadratic unconstrained binary optimization problem (QUBO). While such formulation respects the binary nature of the problem, ensuring that the result is a set of permutations requires extra care. Hence, we: (I) show how to insert permutation constraints into a QUBO problem and (ii) solve the constrained QUBO problem on the current generation of the adiabatic quantum computers D-Wave. Thanks to the quantum annealing, we guarantee global optimality with high probability while sampling the energy landscape to yield confidence estimates. Our proof-of-concepts realization on the adiabatic D-Wave computer demonstrates that quantum machines offer a promising way to solve the prevalent yet difficult synchronization problems.