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.
翻译:我们提出量子合成法,这是在计算机视觉背景下解决同步问题的第一个量子算法。特别是,我们注重变异同步,这涉及解决离散变量中非电离量量优化问题。我们首先将同步制成一个无限制的二次优化问题(QUBO )。虽然这种配方尊重问题的二进制性质,但确保结果为一组变异需要格外小心。因此,我们:(一) 显示如何将变异限制插入QUBO问题,以及(二) 解决目前生成的半径量子计算机D-Wave的受限制的QUBO问题。由于量子反射,我们保证了全球最佳性,同时对能源环境进行取样以产生信心估计。我们在对diabatic D-Wave计算机上的认识证明,量子机器提供了解决普遍但困难的同步问题的有希望的方法。