Hybrid Quantum Computing -- Tabu Search Algorithm for Partitioning Problems: preliminary study on the Traveling Salesman Problem

• URL: http://arxiv.org/abs/2012.04984v2
• Date: Mon, 12 Apr 2021 13:59:57 GMT
• Title: Hybrid Quantum Computing -- Tabu Search Algorithm for Partitioning Problems: preliminary study on the Traveling Salesman Problem
• Authors: Eneko Osaba, Esther Villar-Rodriguez, Izaskun Oregi and Aitor Moreno-Fernandez-de-Leceta
• Abstract summary: We introduce a novel solving scheme coined as hybrid Quantum Computing - Tabu Search Algorithm. Main pillars of operation of the proposed method are a greater control over the access to quantum resources, and a considerable reduction of non-profitable accesses.
• Score: 0.8434687648198277
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum Computing is considered as the next frontier in computing, and it is attracting a lot of attention from the current scientific community. This kind of computation provides to researchers with a revolutionary paradigm for addressing complex optimization problems, offering a significant speed advantage and an efficient search ability. Anyway, Quantum Computing is still in an incipient stage of development. For this reason, present architectures show certain limitations, which have motivated the carrying out of this paper. In this paper, we introduce a novel solving scheme coined as hybrid Quantum Computing - Tabu Search Algorithm. Main pillars of operation of the proposed method are a greater control over the access to quantum resources, and a considerable reduction of non-profitable accesses. To assess the quality of our method, we have used 7 different Traveling Salesman Problem instances as benchmarking set. The obtained outcomes support the preliminary conclusion that our algorithm is an approach which offers promising results for solving partitioning problems while it drastically reduces the access to quantum computing resources. We also contribute to the field of Transfer Optimization by developing an evolutionary multiform multitasking algorithm as initialization method.

Related papers

• Variational Quantum Algorithms for Combinatorial Optimization [0.571097144710995]
  Variational Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to Approximate optimization. We implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes.
  arXiv  Detail & Related papers  (2024-07-08T22:02:39Z)
• 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)
• 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)
• An introduction to variational quantum algorithms for combinatorial optimization problems [0.0]
  This tutorial provides a mathematical description of the class of Variational Quantum Algorithms. We introduce precisely the key aspects of these hybrid algorithms on the quantum side and the classical side. We devote a particular attention to QAOA, detailing the quantum circuits involved in that algorithm, as well as the properties satisfied by its possible guiding functions.
  arXiv  Detail & Related papers  (2022-12-22T14:27:52Z)
• Efficient algorithms for quantum information bottleneck [64.67104066707309]
  We propose a new and general algorithm for the quantum generalisation of information bottleneck. Our algorithm excels in the speed and the definiteness of convergence compared with prior results. Notably, we discover that a quantum system can achieve strictly better performance than a classical system of the same size regarding quantum information bottleneck.
  arXiv  Detail & Related papers  (2022-08-22T14:20:05Z)
• Implementable Hybrid Quantum Ant Colony Optimization Algorithm [0.0]
  We propose a new hybrid quantum algorithm to produce approximate solutions for NP-hard problems. We develop an improved algorithm that can be truly implemented on near-term quantum computers. The benchmarks made by simulating the noiseless quantum circuit and the experiments made on IBM quantum computers show the validity of the algorithm.
  arXiv  Detail & Related papers  (2021-07-08T13:50:51Z)
• Focusing on the Hybrid Quantum Computing -- Tabu Search Algorithm: new results on the Asymmetric Salesman Problem [1.672938048065882]
  This paper extends the results and findings of the recently proposed hybrid Quantum Computing - Tabu Search Algorithm for partitioning problems. As an additional contribution, this work supposes the first solver of the Asymmetric Traveling Salesman Problem using a Quantum Computing based method.
  arXiv  Detail & Related papers  (2021-02-11T10:08:44Z)
• 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)
• An Application of Quantum Annealing Computing to Seismic Inversion [55.41644538483948]
  We apply a quantum algorithm to a D-Wave quantum annealer to solve a small scale seismic inversions problem. The accuracy achieved by the quantum computer is at least as good as that of the classical computer.
  arXiv  Detail & Related papers  (2020-05-06T14:18:44Z)
• 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.