Tabu-driven Quantum Neighborhood Samplers
- URL: http://arxiv.org/abs/2011.09508v2
- Date: Thu, 4 Mar 2021 08:55:41 GMT
- Title: Tabu-driven Quantum Neighborhood Samplers
- Authors: Charles Moussa, Hao Wang, Henri Calandra, Thomas B\"ack, Vedran Dunjko
- Abstract summary: Combinatorial optimization is an important application numerically targeted by quantum computing.
One option to achieve advantages with near-term devices is to use them in combination with classicals.
We show that QAOA provides a flexible tool for exploration Algorithm-exploitation in such hybrid settings.
- Score: 2.9934511331003555
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Combinatorial optimization is an important application targeted by quantum
computing. However, near-term hardware constraints make quantum algorithms
unlikely to be competitive when compared to high-performing classical
heuristics on large practical problems. One option to achieve advantages with
near-term devices is to use them in combination with classical heuristics. In
particular, we propose using quantum methods to sample from classically
intractable distributions -- which is the most probable approach to attain a
true provable quantum separation in the near-term -- which are used to solve
optimization problems faster. We numerically study this enhancement by an
adaptation of Tabu Search using the Quantum Approximate Optimization Algorithm
(QAOA) as a neighborhood sampler. We show that QAOA provides a flexible tool
for exploration-exploitation in such hybrid settings and can provide evidence
that it can help in solving problems faster by saving many tabu iterations and
achieving better solutions.
Related papers
- Randomized Benchmarking of Local Zeroth-Order Optimizers for Variational
Quantum Systems [65.268245109828]
We compare the performance of classicals across a series of partially-randomized tasks.
We focus on local zeroth-orders due to their generally favorable performance and query-efficiency on quantum systems.
arXiv Detail & Related papers (2023-10-14T02:13:26Z) - Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
We present an approach where the quantum computation is supplemented by a classical result.
Taking advantage of its anticipation also leads to a new type of quantum measurements, which we call anticipative.
In an anticipative quantum measurement the combination of the results from classical and quantum computations happens only in the end.
arXiv Detail & Related papers (2022-09-12T15:47:44Z) - Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem [0.8434687648198277]
The Bin Packing Problem (BPP) stands out as a paradigmatic optimization problem in logistics.
We have recently proposed a hybrid approach to the one dimensional BPP.
We compare the performance of our procedure with other classical approaches.
arXiv Detail & Related papers (2022-07-15T13:09:12Z) - Squeezing and quantum approximate optimization [0.6562256987706128]
Variational quantum algorithms offer fascinating prospects for the solution of optimization problems using digital quantum computers.
However, the achievable performance in such algorithms and the role of quantum correlations therein remain unclear.
We show numerically as well as on an IBM quantum chip how highly squeezed states are generated in a systematic procedure.
arXiv Detail & Related papers (2022-05-20T18:00:06Z) - 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) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
We propose a hybrid quantum-classical algorithm for robust fitting.
Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs.
We present results obtained using an actual quantum computer.
arXiv Detail & Related papers (2022-01-25T05:59:24Z) - 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) - 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) - Limitations of optimization algorithms on noisy quantum devices [0.0]
We present a transparent way of comparing classical algorithms to quantum ones running on near-term quantum devices.
Our approach is based on the combination of entropic inequalities that determine how fast the quantum state converges to the fixed point of the noise model.
arXiv Detail & Related papers (2020-09-11T17:07:26Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications.
Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem.
In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
arXiv Detail & Related papers (2020-03-11T13:52:41Z) - To quantum or not to quantum: towards algorithm selection in near-term
quantum optimization [0.0]
We study the problem of detecting problem instances of where QAOA is most likely to yield an advantage over a conventional algorithm.
We achieve cross-validated accuracy well over 96%, which would yield a substantial practical advantage.
arXiv Detail & Related papers (2020-01-22T20:42:02Z)
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.