Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Quantum Permutation Synchronization


Golyanik,  Vladislav
Visual Computing and Artificial Intelligence, MPI for Informatics, Max Planck Society;


Theobalt,  Christian
Visual Computing and Artificial Intelligence, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
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: https://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.