Adiabatic Quantum Graph Matching with Permutation Matrix Constraints
- URL: http://arxiv.org/abs/2107.04032v1
- Date: Thu, 8 Jul 2021 17:59:55 GMT
- Title: Adiabatic Quantum Graph Matching with Permutation Matrix Constraints
- Authors: Marcel Seelbach Benkner and Vladislav Golyanik and Christian Theobalt
and Michael Moeller
- Abstract summary: 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.
- Score: 75.88678895180189
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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
address such problems with emerging quantum computing technology and propose
several reformulations of QAPs as unconstrained problems suitable for efficient
execution on quantum hardware. We investigate several ways to inject
permutation matrix constraints in a quadratic unconstrained binary optimization
problem which can be mapped to quantum hardware. We focus on obtaining a
sufficient spectral gap, which further increases the probability to measure
optimal solutions and valid permutation matrices in a single run. We perform
our experiments on the quantum computer D-Wave 2000Q (2^11 qubits, adiabatic).
Despite the observed discrepancy between simulated adiabatic quantum computing
and execution on real quantum hardware, our reformulation of permutation matrix
constraints increases the robustness of the numerical computations over other
penalty approaches in our experiments. The proposed algorithm has the potential
to scale to higher dimensions on future quantum computing architectures, which
opens up multiple new directions for solving matching problems in 3D computer
vision and graphics.
Related papers
- Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
Quantum computing sets the foundation for new ways of designing algorithms.
New challenges arise concerning which field quantum speedup can be achieved.
Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
arXiv Detail & Related papers (2024-02-26T09:32:07Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
The anticipated applications of quantum computers span across science and industry.
We present a survey of several potential application areas of quantum algorithms.
We outline the challenges and opportunities in each area in an "end-to-end" fashion.
arXiv Detail & Related papers (2023-10-04T17:53:55Z) - Trainable Variational Quantum-Multiblock ADMM Algorithm for Generation
Scheduling [0.0]
This paper proposes a two-loop quantum solution algorithm for generation scheduling by quantum computing, machine learning, and distributed optimization.
The aim is to facilitate noisy employing near-term quantum machines with a limited number of qubits to solve practical power system problems.
arXiv Detail & Related papers (2023-03-28T21:31:39Z) - 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) - Constrained Quantum Optimization for Extractive Summarization on a
Trapped-ion Quantum Computer [13.528362112761805]
We show the largest-to-date execution of a quantum optimization algorithm that preserves constraints on quantum hardware.
We execute XY-QAOA circuits that restrict the quantum evolution to the in-constraint subspace, using up to 20 qubits and a two-qubit gate depth of up to 159.
We discuss the respective trade-offs of the algorithms and implications for their execution on near-term quantum hardware.
arXiv Detail & Related papers (2022-06-13T16:21:04Z) - Multi-round QAOA and advanced mixers on a trapped-ion quantum computer [0.0]
Combinatorial optimization problems on graphs have broad applications in science and engineering.
The Quantum Approximate Optimization Algorithm (QAOA) is a method to solve these problems on a quantum computer by applying multiple rounds of variational circuits.
In this paper, we demonstrate on a trapped-ion quantum computer that QAOA results improve with the number of rounds for multiple problems on several arbitrary graphs.
arXiv Detail & Related papers (2022-01-28T18:57:14Z) - Multiple Query Optimization using a Hybrid Approach of Classical and
Quantum Computing [1.7077661158850292]
We tackle the multiple query optimization problem (MQO) which is an important NP-hard problem in the area of data-intensive problems.
We propose a novel hybrid classical-quantum algorithm to solve the MQO on a gate-based quantum computer.
Our algorithm shows a qubit efficiency of close to 99% which is almost a factor of 2 higher compared to the state of the art implementation.
arXiv Detail & Related papers (2021-07-22T08:12:49Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions.
Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
arXiv Detail & Related papers (2021-06-24T20:16:02Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
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.
arXiv Detail & Related papers (2021-05-06T17:59:38Z) - Quantum-Assisted Graph Clustering and Quadratic Unconstrained D-ary
Optimisation [1.4653008985229616]
This paper examines unsupervised graph clustering by quantum algorithms or, more precisely, quantum-assisted algorithms.
A qudit circuit to solve max-d cut through Quantum Approximate Optimization algorithm is constructed.
arXiv Detail & Related papers (2020-04-03T09:10:24Z)
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.