Implementable Hybrid Quantum Ant Colony Optimization Algorithm
- URL: http://arxiv.org/abs/2107.03845v2
- Date: Fri, 26 Nov 2021 10:52:28 GMT
- Title: Implementable Hybrid Quantum Ant Colony Optimization Algorithm
- Authors: Mikel Garcia de Andoin and Javier Echanobe
- Abstract summary: 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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We propose a new hybrid quantum algorithm based on the classical Ant Colony
Optimization algorithm to produce approximate solutions for NP-hard problems,
in particular optimization problems. First, we discuss some previously proposed
Quantum Ant Colony Optimization algorithms, and based on them, we develop an
improved algorithm that can be truly implemented on near-term quantum
computers. Our iterative algorithm codifies only the information about the
pheromones and the exploration parameter in the quantum state, while
subrogating the calculation of the numerical result to a classical computer. A
new guided exploration strategy is used in order to take advantage of the
quantum computation power and generate new possible solutions as a
superposition of states. This approach is specially useful to solve constrained
optimization problems, where we can implement efficiently the exploration of
new paths without having to check the correspondence of a path to a solution
before the measurement of the state. As an example of a NP-hard problem, we
choose to solve the Quadratic Assignment Problem. The benchmarks made by
simulating the noiseless quantum circuit and the experiments made on IBM
quantum computers show the validity of the algorithm.
Related papers
- Solving the Independent Domination Problem by Quantum Approximate Optimization Algorithm [0.5919433278490629]
Independent Domination Problem (IDP) has practical implications in various real-world scenarios.
Existing classical algorithms for IDP are plagued by high computational complexity.
This paper introduces a Quantum Approximate Optimization (QAOA)-based approach to address the IDP.
arXiv Detail & Related papers (2024-10-22T17:49:00Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - 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) - Iterative Quantum Algorithms for Maximum Independent Set: A Tale of
Low-Depth Quantum Algorithms [0.0]
We study a new class of hybrid approaches to quantum optimization, termed Iterative Maximum Quantum Algorithms.
We show that for QAOA with depth $p=1$, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS.
arXiv Detail & Related papers (2023-09-22T18:00:03Z) - A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems.
This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios.
We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
arXiv Detail & Related papers (2023-06-15T15:28:12Z) - 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) - NP-hard but no longer hard to solve? Using quantum computing to tackle
optimization problems [1.1470070927586016]
We discuss the field of quantum optimization where we solve optimisation problems using quantum computers.
We demonstrate this through a proper use case and discuss the current quality of quantum computers.
We conclude with discussion on some recent quantum optimization breakthroughs and the current status and future directions.
arXiv Detail & Related papers (2022-12-21T12:56:37Z) - Efficient Use of Quantum Linear System Algorithms in Interior Point
Methods for Linear Optimization [0.0]
We develop an Inexact Infeasible Quantum Interior Point Method to solve linear optimization problems.
We also discuss how can we get an exact solution by Iterative Refinement without excessive time of quantum solvers.
arXiv Detail & Related papers (2022-05-02T21:30:56Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory.
We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
arXiv Detail & Related papers (2021-11-30T12:21:41Z) - 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)
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.