User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse





Quantum Permutation Synchronization


Golyanik,  Vladislav
Computer Graphics, MPI for Informatics, Max Planck Society;


Theobalt,  Christian
Computer Graphics, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)

(Preprint), 6MB

Supplementary Material (public)
There is no public supplementary material available

Birdal, T., Golyanik, V., Theobalt, C., & Guibas, L. (2021). Quantum Permutation Synchronization. Retrieved from https://arxiv.org/abs/2101.07755.

Cite as: http://hdl.handle.net/21.11116/0000-0007-E895-B
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.