Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2107.03845 · Quantum Machine Intelligence

Implementable hybrid quantum ant colony optimization algorithm

Mikel Garcia de Andoin, Javier Echanobe

Published Jun 17, 2022• 11 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1007/s42484-022-00065-1

Related papers

Hybrid Quantum Ant Colony Algorithm for Traveling Salesman Problem

Jia Rui-y

Aiming at the Traveling Salesman Problem based on ant colony optimization which is easy to fall into local optimums and has a slow convergence rate,a hybrid quantum ant colony optimization algorithm is presented.In this algorithm,the pheromone on each path is encoded by a group of quantum bits,the quantum rotation gate and ant's tour are used to update the pheromone so as to accelerate its convergence speed.To avoid the search falling into local optimum,the new neighborhood exchange strategy is designed to improve solution efficiency.Some cases from the TSP library(TSPLIB)are used to experiment,the results show that the algorithm has rapider convergence speed and higher accuracy than the classical ant colony algorithm.

Computer Engineering and Applications Journal•Jan 1, 2013•0 citations

Algoritmos cuánticos y Quantum Ant Colony Optimization

Mikel Garcia de Andoin

[EN] I propose an improved algorithm that can be implemented on a real quantum computer with a new guided exploration strategy. The benchmarks made by simulating the quantum circuit shows that the time to solve a problem using QACO could outperform greatly other classical bio-inspired algorithms, in particular the one QACO is based on, the Ant Colony Optimization. Quantum computation is on the verge of becoming the new technology for solving time- and energy-consuming problems. To make use of the full potential of quantum computers one must implement algorithms that are significantly different from the ones used on digital computers. This work serves as an introduction to both quantum computing and algorithms. Starting from the basis of the quantum physics, I expose each of the steps needed to understand the mathematics beneath this topic. Using this basis, I develope one quantum algorithm from scratch. Based on a previously proposed Quantum Ant Colony Optimization (QACO) algorithm, I propose an improved algorithm that can be implemented on a real quantum computer with a new guided exploration strategy. The benchmarks made by simulating the quantum circuit shows that the time to solve a problem using QACO could outperform greatly other classical bio-inspired algorithms, in particular the one QACO is based on, the Ant Colony Optimization.

•Dec 15, 2020•0 citations

Hybrid Quantum Approximate Optimization Using Enhanced Ant Colony Optimization to Solve Large-Scale Combinatorial Optimization Problems

Bishad Ghimire, Ausif Mahmood, Khaled M. Elleithy

Quantum computing is a promising technology that may provide breakthrough solutions to today’s difficult problems such as breaking encryption and solving large-scale combinatorial optimization problems. A class of algorithms referred to as Quantum Approximate Optimization Algorithm (QAOA) have been recently proposed. QAOA attempts to approximately solve hard problems using a protocol know as bang-bang. The technique is based on the unitary evolution using a Hamiltonian encoding of the objective function of the combinatorial optimization problem. QAOA has been explored in the context of several optimization problems such as Max-Cut problem, variational Eigenvalue problem etc. Recently, attempts have been made to create QAOA for the Traveling Salesman Problem (TSP). Due to small node size and limited solution capability of the currently available Quantum computers and/or simulators, we develop a hybrid approach where subgraphs of a TSP tour are executed on a Quantum computer and the results from the quantum optimization are combined in further optimization of the whole tour. Since the local optimization of a subgraph is prone to getting stuck in a local minima, we overcome this problem by using a parallel Ant Colony Optimization Algorithm with periodic pheromone exchange between colonies. Our results are encouraging and yield optimum results for benchmarks with less than 50 nodes, and usually within 1% of the optimal solution for benchmarks with around 200 nodes.

International Conference on Soft Computing & Machine Intelligence (ISCMI)•Nov 26, 2021•6 citations

Hybrid Parallel Ant Colony Optimization for Application to Quantum Computing to Solve Large-Scale Combinatorial Optimization Problems

Bishad Ghimire, Ausif Mahmood, Khaled M. Elleithy

Quantum computing is a promising technology that may provide breakthrough solutions to today’s difficult problems such as breaking encryption and solving large-scale combinatorial optimization problems. An algorithm referred to as Quantum Approximate Optimization Algorithm (QAOA) has been recently proposed to approximately solve hard problems using a protocol know as bang–bang. The technique is based on unitary evolution using a Hamiltonian encoding of the objective function of the combinatorial optimization problem. The QAOA was explored in the context of several optimization problems such as the Max-Cut problem and the Traveling Salesman Problem (TSP). Due to the relatively small node-size solution capability of the available quantum computers and simulators, we developed a hybrid approach where sub-graphs of a TSP tour can be executed on a quantum computer, and the results from the quantum optimization are combined for a further optimization of the whole tour. Since the local optimization of a sub-graph is prone to becoming trapped in a local minimum, we overcame this problem by using a parallel Ant Colony Optimization (ACO) algorithm with periodic pheromone exchange between colonies. Our method exceeds existing approaches which have attempted partitioning a graph for small problems (less than 48 nodes) with sub-optimal results. We obtained optimum results for benchmarks with less than 150 nodes and results usually within 1% of the known optimal solution for benchmarks with around 2000 nodes.

Applied Sciences•Oct 29, 2023•9 citations

Quantum-inspired ant algorithm for knapsack problems

Wang Hong-gang, Honggang, ± Ma +5 more

The knapsack problem is a well-known combinatorial optimization problem which has been proved to be NP-hard. This paper proposes a new algorithm called quantum-inspired ant algorithm (QAA) to solve the knapsack problem. QAA takes the advantage of the principles in quantum computing, such as qubit, quantum gate, and quantum superposition of states, to get more probabilistic-based status with small colonies. By updating the pheromone in the ant algorithm and rotating the quantum gate, the algorithm can finally reach the optimal solution. The detailed steps to use QAA are presented, and by solving series of test cases of classical knapsack problems, the effectiveness and generality of the new algorithm are validated.

Journal of Systems Engineering and Electronics•Jan 1, 2009•6 citations

A Novel Hybrid Quantum Architecture for Path Planning in Quantum-Enabled Autonomous Mobile Robots

Mayukh Sarkar, Jitesh Pradhan, Anil Kumar Singh +1 more

Autonomous mobile robots are being used increasingly as consumer devices around the globe, such as for fetching items and cleaning purposes, to name a few, in households and industries. Such robots are being employed to traverse a set of target locations and provide the necessary services. In a 2-dimensional environment, these robots are required to traverse following a Hamiltonian path to reduce energy consumption and time requirements. This problem can be formulated as a Travelling Salesman Problem (TSP), an NP-hard problem. Moreover, upon urgent requirements, these robots must traverse in real-time, demanding speedy path planning from the TSP instance. Among the well-known optimization techniques for solving the TSP problem, Ant Colony Optimization has a good stronghold in providing good approximate solutions. Moreover, ACO not only provides near-optimal solutions for TSP instances but can also output optimal or near-optimal solutions for many other demanding hard optimization problems. However, most of the implementations of Ant Colony Optimization on quantum or hybrid quantum architecture proposed in the literature require conversion of classical data to qubits before being fed to the algorithm, and cannot be automated. But quantum-enabled mobile robots require automated path formation after receiving the commands from the environment. The novelties of the proposed work are many-fold. Firstly, the proposed work allows ACO to be applied as its classical counterparts, allowing automation in path formation in quantum-enabled mobile robots. Secondly, this allows a new way of incorporating quantum processing unit in the research of quantum-enabled mobile robots. Researchers around the globe have been trying to incorporate quantum computing in autonomous mobile robots, and true to the best of authors’ knowledge, no work in path planning for multiple targets in quantum-enabled mobile robots have been found in literature. Thirdly, quantum processing unit has been applied at exactly that point where it will be most useful, as in NISQ era quantum computer is not reliable for arithmetic processing. Simulation results of the proposed Hybrid Quantum Ant Colony Optimization algorithm on several TSP instances have shown promising results with average error percentage from optimumresults of only 6.985%. Hence, it is expected that the proposed work to be important in future research of fusing the two rising domains of quantum computing and autonomous mobile robots.

IEEE Transactions on Consumer Electronics•Jul 4, 2024•18 citations
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.
Aiming at the Traveling Salesman Problem based on ant colony optimization which is easy to fall into local optimums and has a slow convergence rate,a hybrid quantum ant colony optimization algorithm is presented.In this algorithm,the pheromone on each path is encoded by a group of quantum bits,the quantum rotation gate and ant's tour are used to update the pheromone so as to accelerate its convergence speed.To avoid the search falling into local optimum,the new neighborhood exchange strategy is designed to improve solution efficiency.Some cases from the TSP library(TSPLIB)are used to experiment,the results show that the algorithm has rapider convergence speed and higher accuracy than the classical ant colony algorithm.
[EN] I propose an improved algorithm that can be implemented on a real quantum computer with a new guided exploration strategy. The benchmarks made by simulating the quantum circuit shows that the time to solve a problem using QACO could outperform greatly other classical bio-inspired algorithms, in particular the one QACO is based on, the Ant Colony Optimization. Quantum computation is on the verge of becoming the new technology for solving time- and energy-consuming problems. To make use of the full potential of quantum computers one must implement algorithms that are significantly different from the ones used on digital computers. This work serves as an introduction to both quantum computing and algorithms. Starting from the basis of the quantum physics, I expose each of the steps needed to understand the mathematics beneath this topic. Using this basis, I develope one quantum algorithm from scratch. Based on a previously proposed Quantum Ant Colony Optimization (QACO) algorithm, I propose an improved algorithm that can be implemented on a real quantum computer with a new guided exploration strategy. The benchmarks made by simulating the quantum circuit shows that the time to solve a problem using QACO could outperform greatly other classical bio-inspired algorithms, in particular the one QACO is based on, the Ant Colony Optimization.
Quantum computing is a promising technology that may provide breakthrough solutions to today’s difficult problems such as breaking encryption and solving large-scale combinatorial optimization problems. A class of algorithms referred to as Quantum Approximate Optimization Algorithm (QAOA) have been recently proposed. QAOA attempts to approximately solve hard problems using a protocol know as bang-bang. The technique is based on the unitary evolution using a Hamiltonian encoding of the objective function of the combinatorial optimization problem. QAOA has been explored in the context of several optimization problems such as Max-Cut problem, variational Eigenvalue problem etc. Recently, attempts have been made to create QAOA for the Traveling Salesman Problem (TSP). Due to small node size and limited solution capability of the currently available Quantum computers and/or simulators, we develop a hybrid approach where subgraphs of a TSP tour are executed on a Quantum computer and the results from the quantum optimization are combined in further optimization of the whole tour. Since the local optimization of a subgraph is prone to getting stuck in a local minima, we overcome this problem by using a parallel Ant Colony Optimization Algorithm with periodic pheromone exchange between colonies. Our results are encouraging and yield optimum results for benchmarks with less than 50 nodes, and usually within 1% of the optimal solution for benchmarks with around 200 nodes.
Quantum computing is a promising technology that may provide breakthrough solutions to today’s difficult problems such as breaking encryption and solving large-scale combinatorial optimization problems. An algorithm referred to as Quantum Approximate Optimization Algorithm (QAOA) has been recently proposed to approximately solve hard problems using a protocol know as bang–bang. The technique is based on unitary evolution using a Hamiltonian encoding of the objective function of the combinatorial optimization problem. The QAOA was explored in the context of several optimization problems such as the Max-Cut problem and the Traveling Salesman Problem (TSP). Due to the relatively small node-size solution capability of the available quantum computers and simulators, we developed a hybrid approach where sub-graphs of a TSP tour can be executed on a quantum computer, and the results from the quantum optimization are combined for a further optimization of the whole tour. Since the local optimization of a sub-graph is prone to becoming trapped in a local minimum, we overcame this problem by using a parallel Ant Colony Optimization (ACO) algorithm with periodic pheromone exchange between colonies. Our method exceeds existing approaches which have attempted partitioning a graph for small problems (less than 48 nodes) with sub-optimal results. We obtained optimum results for benchmarks with less than 150 nodes and results usually within 1% of the known optimal solution for benchmarks with around 2000 nodes.
The knapsack problem is a well-known combinatorial optimization problem which has been proved to be NP-hard. This paper proposes a new algorithm called quantum-inspired ant algorithm (QAA) to solve the knapsack problem. QAA takes the advantage of the principles in quantum computing, such as qubit, quantum gate, and quantum superposition of states, to get more probabilistic-based status with small colonies. By updating the pheromone in the ant algorithm and rotating the quantum gate, the algorithm can finally reach the optimal solution. The detailed steps to use QAA are presented, and by solving series of test cases of classical knapsack problems, the effectiveness and generality of the new algorithm are validated.
Autonomous mobile robots are being used increasingly as consumer devices around the globe, such as for fetching items and cleaning purposes, to name a few, in households and industries. Such robots are being employed to traverse a set of target locations and provide the necessary services. In a 2-dimensional environment, these robots are required to traverse following a Hamiltonian path to reduce energy consumption and time requirements. This problem can be formulated as a Travelling Salesman Problem (TSP), an NP-hard problem. Moreover, upon urgent requirements, these robots must traverse in real-time, demanding speedy path planning from the TSP instance. Among the well-known optimization techniques for solving the TSP problem, Ant Colony Optimization has a good stronghold in providing good approximate solutions. Moreover, ACO not only provides near-optimal solutions for TSP instances but can also output optimal or near-optimal solutions for many other demanding hard optimization problems. However, most of the implementations of Ant Colony Optimization on quantum or hybrid quantum architecture proposed in the literature require conversion of classical data to qubits before being fed to the algorithm, and cannot be automated. But quantum-enabled mobile robots require automated path formation after receiving the commands from the environment. The novelties of the proposed work are many-fold. Firstly, the proposed work allows ACO to be applied as its classical counterparts, allowing automation in path formation in quantum-enabled mobile robots. Secondly, this allows a new way of incorporating quantum processing unit in the research of quantum-enabled mobile robots. Researchers around the globe have been trying to incorporate quantum computing in autonomous mobile robots, and true to the best of authors’ knowledge, no work in path planning for multiple targets in quantum-enabled mobile robots have been found in literature. Thirdly, quantum processing unit has been applied at exactly that point where it will be most useful, as in NISQ era quantum computer is not reliable for arithmetic processing. Simulation results of the proposed Hybrid Quantum Ant Colony Optimization algorithm on several TSP instances have shown promising results with average error percentage from optimumresults of only 6.985%. Hence, it is expected that the proposed work to be important in future research of fusing the two rising domains of quantum computing and autonomous mobile robots.