Quantum Permutation Synchronization

• URL: http://arxiv.org/abs/2101.07755v1
• Date: Tue, 19 Jan 2021 17:51:02 GMT
• Title: Quantum Permutation Synchronization
• Authors: Tolga Birdal, Vladislav Golyanik, Christian Theobalt, Leonidas Guibas
• Abstract summary: We present QuantumSync, the quantum algorithm for solving a quantum vision problem in the context of computer vision. We show how to insert permutation constraints into a QUBO problem and to solve the constrained QUBO problem on the current generation of the abatic quantum DWave computer.
• Score: 88.4588059792167
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm [0.0]
  This paper introduces in detail a non-variational quantum algorithm designed to solve a wide range of optimisation problems. The algorithm returns optimal and near-optimal solutions from repeated preparation and measurement of an amplified state.
  arXiv  Detail & Related papers  (2024-07-29T13:54:28Z)
• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  We call this protocol bias-field digitizeddiabatic quantum optimization (BF-DCQO) Our purely quantum approach eliminates the dependency on classical variational quantum algorithms. It achieves scaling improvements in ground state success probabilities, increasing by up to two orders of magnitude.
  arXiv  Detail & Related papers  (2024-05-22T18:11:42Z)
• A Universal Quantum Algorithm for Weighted Maximum Cut and Ising Problems [0.0]
  We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary problems. We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian. Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system.
  arXiv  Detail & Related papers  (2023-06-10T23:28:13Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Quantum-inspired optimization for wavelength assignment [51.55491037321065]
  We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
  arXiv  Detail & Related papers  (2022-11-01T07:52:47Z)
• Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
  We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
  arXiv  Detail & Related papers  (2022-03-23T18:00:03Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.