Divide-and-conquer embedding for QUBO quantum annealing
- URL: http://arxiv.org/abs/2211.02184v2
- Date: Sat, 12 Nov 2022 17:10:03 GMT
- Title: Divide-and-conquer embedding for QUBO quantum annealing
- Authors: Minjae Jo, Michael Hanks, M. S. Kim
- Abstract summary: We show that a problem-focused approach to embedding can improve performance by orders of magnitude.
Our results show that a problem-focused approach to embedding can improve performance by orders of magnitude.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum annealing promises to be an effective heuristic for complex NP-hard
problems. However, clear demonstrations of quantum advantage are wanting,
primarily constrained by the difficulty of embedding the problem into the
quantum hardware. Community detection methods such as the Girvin--Newman
algorithm can provide a divide-and-conquer approach to large problems. Here, we
propose a problem-focused division for embedding, deliberately worsening
typical measures of embedding quality to improve the partial solutions we
obtain. We apply this approach first to the highly irregular graph of an
integer factorisation problem and, passing this initial test, move on to
consider more regular geometrically frustrated systems. Our results show that a
problem-focused approach to embedding can improve performance by orders of
magnitude.
Related papers
- Hybrid classical-quantum branch-and-bound algorithm for solving integer
linear problems [0.0]
Quantum annealers are suited to solve several logistic optimization problems expressed in the QUBO formulation.
The solutions proposed by the quantum annealers are generally not optimal, as thermal noise and other disturbing effects arise when the number of qubits involved in the calculation is too large.
We propose the use of the classical branch-and-bound algorithm, that divides the problem into sub-problems which are described by a lower number of qubits.
arXiv Detail & Related papers (2023-11-16T09:19:01Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods.
Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem.
As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
arXiv Detail & Related papers (2023-10-08T23:39:38Z) - 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) - Quantum Vision Clustering [10.360126989185261]
We present the first clustering formulation tailored for resolution using Adiabatic quantum computing.
The proposed approach demonstrates high competitiveness compared to state-of-the-art optimization-based methods.
This work showcases the solvability of the proposed clustering problem on current-generation real quantum computers for small examples.
arXiv Detail & Related papers (2023-09-18T16:15:16Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem.
The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
arXiv Detail & Related papers (2023-04-18T11:57:15Z) - 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) - 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) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation.
We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
arXiv Detail & Related papers (2021-08-18T09:26:17Z) - Quantum constraint learning for quantum approximate optimization
algorithm [0.0]
This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace.
One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz.
We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints.
arXiv Detail & Related papers (2021-05-14T11:31:14Z) - A Hybrid Quantum-Classical Heuristic to solve large-scale Integer Linear
Programs [0.4925222726301578]
We present a method that integrates any quantum algorithm capable of finding solutions to integer linear programs into the Branch-and-Price algorithm.
The role of the quantum algorithm is to find integer solutions to subproblems appearing in Branch-and-Price.
arXiv Detail & Related papers (2021-03-29T08:59:26Z) - Optimizing the Optimizer: Decomposition Techniques for Quantum Annealing [0.0]
Current generation quantum computers are too small to solve real-world problems.
In this work, we explore multiple heterogeneous approaches to solving benchmark problems.
Our results indicate that solver performance is highly dependent on the structure of the problem graph.
arXiv Detail & Related papers (2020-01-16T21:35:16Z)
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.