
Birdal, T., Golyanik, V., Theobalt, C., & Guibas, L. J. Quantum Permutation Synchronization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (2021) pp. 1312213133.
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 nonconvex 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 DWave. Thanks to the quantum annealing, we guarantee global optimality with high probability while sampling the energy landscape to yield confidence estimates. Our proofofconcepts realization on the adiabatic DWave computer demonstrates that quantum machines offer a promising way to solve the prevalent yet difficult synchronization problems.
Bibtex:
@inproceedings{birdal2021quantum,
title={Quantum Permutation Synchronization},
author={Birdal, Tolga and Golyanik, Vladislav and Theobalt, Christian and Guibas, Leonidas J},
booktitle={Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition},
pages={1312213133},
year={2021}
}

