English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  DetailsSummary

Released
Paper

Quantum Permutation Synchronization

MPS-Authors
/persons/resource/persons239654

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

/persons/resource/persons45610

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)

arXiv:2101.07755.pdf
(Preprint), 6MB

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

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
Abstract
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.