Q-Match: Iterative Shape Matching via Quantum Annealing
- URL: http://arxiv.org/abs/2105.02878v1
- Date: Thu, 6 May 2021 17:59:38 GMT
- Title: Q-Match: Iterative Shape Matching via Quantum Annealing
- Authors: Marcel Seelbach Benkner and Zorah L\"ahner and Vladislav Golyanik and
Christof Wunderlich and Christian Theobalt and Michael Moeller
- Abstract summary: Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP)
This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm.
Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
- Score: 64.74942589569596
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Finding shape correspondences can be formulated as an NP-hard quadratic
assignment problem (QAP) that becomes infeasible for shapes with high sampling
density. A promising research direction is to tackle such quadratic
optimization problems over binary variables with quantum annealing, which, in
theory, allows to find globally optimal solutions relying on a new
computational paradigm. Unfortunately, enforcing the linear equality
constraints in QAPs via a penalty significantly limits the success probability
of such methods on currently available quantum hardware. To address this
limitation, this paper proposes Q-Match, i.e., a new iterative quantum method
for QAPs inspired by the alpha-expansion algorithm, which allows solving
problems of an order of magnitude larger than current quantum methods. It works
by implicitly enforcing the QAP constraints by updating the current estimates
in a cyclic fashion. Further, Q-Match can be applied for shape matching
problems iteratively, on a subset of well-chosen correspondences, allowing us
to scale to real-world problems. Using the latest quantum annealer, the D-Wave
Advantage, we evaluate the proposed method on a subset of QAPLIB as well as on
isometric shape matching problems from the FAUST dataset.
Related papers
- A quantum annealing approach to the minimum distance problem of quantum codes [0.0]
We introduce an approach to compute the minimum distance of quantum stabilizer codes by reformulating the problem as a Quadratic Unconstrained Binary Optimization problem.
We demonstrate practical viability of our method by comparing the performance of purely classical algorithms with the D-Wave Advantage 4.1 quantum annealer.
arXiv Detail & Related papers (2024-04-26T21:29:42Z) - Two quantum algorithms for solving the one-dimensional
advection-diffusion equation [0.0]
Two quantum algorithms are presented for the numerical solution of a linear one-dimensional advection-diffusion equation with periodic boundary conditions.
Their accuracy and performance with increasing qubit number are compared point-by-point with each other.
arXiv Detail & Related papers (2023-12-30T21:23:15Z) - Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
AQCs allow to implement problems of research interest, which has sparked the development of quantum representations for computer vision tasks.
In this work, we explore the potential of using this information for probabilistic balanced k-means clustering.
Instead of discarding non-optimal solutions, we propose to use them to compute calibrated posterior probabilities with little additional compute cost.
This allows us to identify ambiguous solutions and data points, which we demonstrate on a D-Wave AQC on synthetic tasks and real visual data.
arXiv Detail & Related papers (2023-10-18T17:59:45Z) - A Quantum Approach for Stochastic Constrained Binary Optimization [2.6803492658436032]
Quantum-based algorithms have been shown to generate high-quality solutions to hard problems.
This work puts forth quantum vectors to cope with binary quadratically constrained programs.
The method builds upon dual decomposition and entails solving a sequence of judiciously modified standard VQE tasks.
arXiv Detail & Related papers (2023-01-04T04:24:26Z) - 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) - 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) - VQE Method: A Short Survey and Recent Developments [5.9640499950316945]
The variational quantum eigensolver (VQE) is a method that uses a hybrid quantum-classical computational approach to find eigenvalues and eigenvalues of a Hamiltonian.
VQE has been successfully applied to solve the electronic Schr"odinger equation for a variety of small molecules.
Modern quantum computers are not capable of executing deep quantum circuits produced by using currently available ansatze.
arXiv Detail & Related papers (2021-03-15T16:25:36Z) - Larger Sparse Quadratic Assignment Problem Optimization Using Quantum
Annealing and a Bit-Flip Heuristic Algorithm [0.4125187280299248]
Linear constraints reduce the size of problems that can be represented in quantum annealers.
We propose a method for solving a sparse QAP by applying a post-processing bit-flip algorithm to solutions obtained by the Ohzeki method.
We successfully solved a QAP of size 19 with high accuracy for the first time using D-Wave Advantage.
arXiv Detail & Related papers (2020-12-18T09:48:28Z)
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.