Quantum Permutation Synchronization
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Enhanced Quantum Synchronization via Quantum Machine Learning
We study the quantum synchronization between a pair of two-level systems inside two coupled cavities. By using a digital-analog decomposition of the master equation that rules the system dynamics, we show that this appro…
BIG-bench Machine LearningQuantum Machine LearningAdiabatic Quantum Graph Matching with Permutation Matrix Constraints
Matching problems on 3D shapes and images are challenging as they are frequently formulated as combinatorial quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. In this work, we a…
Graph MatchingvalidQ-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization
We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linearly-constrained, binary optimization problems on quantum annealers (QA). The computational premise of …
Graph MatchingFast, Accurate and Memory-Efficient Partial Permutation Synchronization
Previous partial permutation synchronization (PPS) algorithms, which are commonly used for multi-object matching, often involve computation-intensive and memory-demanding matrix operations. These operations become intrac…
Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods
Group synchronization asks to recover group elements from their pairwise measurements. It has found numerous applications across various scientific disciplines. In this work, we focus on orthogonal and permutation group …