# Quantum Permutation Synchronization

^{*}both authors contributed equally

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

## Overview

**Context and Goals:** Many computer vision problems can be interpreted as synchromization problems over permutations. Synchronization simultaneously averages the pairwise local information into a global one. This procedure is a fundamental piece of most state-of-the-art multi-view reconstruction and multi-shape analysis pipelines. In this paper, our focus is permutation synchronization, where the edges of the graph are labeled by permutation matrices denoting the correspondences either between two 2D images or two 3D shapes. Specifically, we seek to find an absolute ordering for each point of each frame which sorts all the corresponding points into the same bin. Unfortunately, this problem by definition involves a combinatorial non-convex optimization, for which attaining the global minimum is intractable under standard formulations targeting classical von Neumann computers. Because on a classical computer we cannot speak of a global optimality guarantee of our discrete problem, we turn our attention to a new family of processors, i.e., quantum computers.

**Quantum computers** are computational machines which employ quantum effects of quantum superposition, entanglement and tunneling. The concept of quantum computers was proposed in the early '80s, and it has taken more than fifteen years until the first functional computers were demonstrated in laboratories. Nowadays, quantum computing hardware is mature so that real-world problems can benefit from it. In this paper, we focus on adiabatic quantum computers (AQC). The operational principle of AQC is grounded on the adiabatic theorem of quantum mechanics.

**Contributions:**

- Formulation of the classical synchronization in a form consumable by an AQC,

i.e., quadratic unconstrained binary optimization (QUBO) problem. - Introduction of permutations as linear constraints into the obtained QUBO problem.
- Numerical verification of our formulation in simulated experiments as well as on a real AQC

(for the first time on D-Wave Advantage system 1.1). - Extensive ablation studies giving insights into this new way of computing.

**Minor Embeddings:**

**Summary:** For small problem instances, QuantumSync achieves state-of-the-art accuracy in our experiments which is on par with classical best techniques (not considering exhaustive search). Experimenting on D-Wave Advantage system 1.1 (introduced in October 2020) allows us to minor-embed larger problems compared to the previous D-Wave AQC generation. The overall experimental QPU time in our experiments amounts to ≈15 minutes. All in all, we conclude that quantum computing hardware has reached the level that it can be applied to real-world computer vision and pattern recognition problems with high potential to improve upon the known classical methods.

## Downloads

## Citation

@inproceedings{QuantumSync2021, author = {{Birdal}, Tolga and {Golyanik}, Vladislav and {Theobalt}, Christian and {Guibas}, Leonidas}, title = {Quantum Permutation Synchronization}, booktitle = {Computer Vision and Pattern Recognition (CVPR)}, year = {2021} }

## Contact

For questions and clarifications please get in touch with:Vladislav Golyanik golyanik@mpi-inf.mpg.de