mlsanityData to 7 Oct 2026

Quantum Permutation Synchronization

arXiv 2101.07755 ↗First posted 19 Jan 2021quant-ph cs.CV cs.ETcited by 32

Not on the map. Why?

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.

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

Builds on

26 of 111 references.

References · 26

  1. 2016Past, Present, and Future of Simultaneous Localization And Mapping: Towards the Robust-Perception Agecited by 405
  2. 2016SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Groupcited by 80
  3. 2020Learning multiview 3D point cloud registrationcited by 78
  4. 2020CaSPR: Learning Canonical Spatiotemporal Point Cloud Representationscited by 51
  5. 2020Deep Bingham Networks: Dealing with Uncertainty and Ambiguity in Pose Estimationcited by 43
  6. 2015Multi-Image Matching via Fast Alternating Minimizationcited by 33
  7. 2017Traffic flow optimization using a quantum annealercited by 29
  8. 2019Learning Transformation Synchronizationcited by 29
  9. 2014A practical heuristic for finding graph minorscited by 26
  10. 2019Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytopecited by 26
  11. 2017Nonnegative/binary matrix factorization with a D-Wave quantum annealercited by 23
  12. 2019A Quantum Computational Approach to Correspondence Problems on Point Setscited by 23
14 more
  1. 2018Bayesian Pose Graph Optimization via Bingham Distributions and Tempered Geodesic MCMCcited by 19
  2. 2020Synchronizing Probability Measures on Rotations via Optimal Transportcited by 19
  3. 2020Quantum-soft QUBO Suppression for Accurate Object Detectioncited by 19
  4. 2013Global registration of multiple point clouds using semidefinite programmingcited by 17
  5. 2014A Solution for Multi-Alignment by Transformation Synchronisationcited by 15
  6. 2018Synchronisation of Partial Multi-Matchings via Non-negative Factorisationscited by 15
  7. 2017Multi-Image Semantic Matching by Mining Consistent Featurescited by 13
  8. 2018Bayesian Deep Learning on a Quantum Computercited by 12
  9. 2019Generic Primitive Detection in Point Clouds Using Novel Minimal Quadric Fitscited by 9
  10. 2013Graph isomorphism and adiabatic quantum computingcited by 7
  11. 2017Distributed methods for synchronization of orthogonal matrices over graphscited by 7
  12. 2017CAD Priors for Accurate and Flexible Instance Reconstructioncited by 6
  13. 2019A regression algorithm for accelerated lattice QCD that exploits sparse inference on the D-Wave quantum annealercited by 6
  14. 2018Path-Invariant Map Networkscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 8; 2023: 10; 2024: 3; 2025: 4; 2026: 2.

32 papers.

Sort:

  1. 2021Multiway Non-rigid Point Cloud Registration via Learned Functional Map Synchronizationcited by 30
  2. 2021Q-Match: Iterative Shape Matching via Quantum Annealingcited by 27
  3. 2022Adiabatic Quantum Computing for Multi Object Trackingcited by 22
  4. 2022A Hybrid Quantum-Classical Algorithm for Robust Fittingcited by 16
  5. 2022Quantum Motion Segmentationcited by 16
  6. 2023Quantum Multi-Model Fittingcited by 12
  7. 2023CCuantuMM: Cycle-Consistent Quantum-Hybrid Matching of Multiple Shapescited by 11
  8. 2021Matching Point Sets with Quantum Circuit Learningcited by 10
  9. 2024Quantum Visual Feature Encoding Revisitedcited by 10
  10. 2022Penalty Weights in QUBO Formulations: Permutation Problemscited by 9
  11. 2022Towards Quantum Graph Neural Networks: An Ego-Graph Learning Approachcited by 8
  12. 2022Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimizationcited by 8
20 more
  1. 2021Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisationcited by 6
  2. 2025Quantum Visual Fields with Neural Amplitude Encodingcited by 6
  3. 20233D-QAE: Fully Quantum Auto-Encoding of 3D Point Cloudscited by 5
  4. 2024Robust Fitting on a Gate Quantum Computercited by 5
  5. 2025Quantum-enhanced Computer Vision: Going Beyond Classical Algorithmscited by 5
  6. 2022QuAnt: Quantum Annealing with Learnt Couplingscited by 3
  7. 2023Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computingcited by 3
  8. 2023Projected Stochastic Gradient Descent with Quantum Annealed Binary Gradientscited by 3
  9. 2024Pooling Image Datasets With Multiple Covariate Shift and Imbalancecited by 3
  10. 2023Quantum Annealing for Computer Vision Minimization Problemscited by 2
  11. 2025Is Quantum Optimization Ready? An Effort Towards Neural Network Compression using Adiabatic Quantum Computingcited by 2
  12. 2021Riemannian Functional Map Synchronization for Probabilistic Partial Correspondence in Shape Networkscited by 1
  13. 2022QSpeech: Low-Qubit Quantum Speech Application Toolkitcited by 1
  14. 2023QUBO Decision Tree: Annealing Machine Extends Decision Tree Splittingcited by 1
  15. 2023Training Multilayer Perceptrons by Sampling with Quantum Annealerscited by 1
  16. 2023Non-Negative Spherical Relaxations for Universe-Free Multi-Matching and Clusteringcited by 1
  17. 2025Outlier-Robust Multi-Model Fitting on Quantum Annealerscited by 1
  18. 2026COMPOSE: Hypergraph Cover Optimization for Multi-view 3D Human Pose Estimationcited by 1
  19. 2026Quantum Multiple Rotation Averagingcited by 1
  20. 2023QUBO-inspired Molecular Fingerprint for Chemical Property Predictioncited by 0