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

Applied and Computational Engineering

Quantum Ant Colony Algorithm for Solving the Traveling Salesman Problem: A Theoretical and Practical Analysis

Yida Li

Published Nov 28, 2024• 1 citation
Publisher

Abstract

The quantum ant colony algorithm (QACO) is explored as a solution to the traveling salesman problem (TSP), targeting inefficiencies such as slow convergence and local optima entrapment found in traditional ant colony optimization (ACO) methods. By integrating quantum computing elements, specifically quantum rotation gates and qubits, into the ACO framework, QACO demonstrates enhanced efficiency and faster convergence. This paper delves into the foundational principles of quantum computing and their application to refine ACO, effectively solving the TSP. An in-depth analysis is provided, showcasing QACO's advantages over traditional ACO through empirical examples. These examples illustrate QACO's potential to improve path planning for applications within the rapidly growing e-commerce and logistics sectors. The integration of quantum mechanisms facilitates a more dynamic pheromone update process, which significantly reduces the likelihood of premature convergence and enhances solution quality in complex optimization scenarios. This advancement indicates a promising direction for future research in algorithmic optimization in both theoretical and practical applications.

DOI
10.54254/2755-2721/110/2024melb0121

Related papers

Integrating Grover’s Quantum Search with Ant Colony Optimization for Efficient TSP Solving

Doddi Sreenija Reddy, Sountharrajan S

The Traveling Salesman Problem (TSP) is a canonical example of an NP-hard combinatorial optimization problem that has extensive applications in the context of logistics and routing and network design, where classical methods cannot be used in practice due to the large scale of the instances. The approach includes extensive research on a hybrid quantum and classical optimisation model, termed Grover-ACO, that combines the Grover quantum amplitude amplification with the elitist selection stage of the Ant Colony Optimization (ACO). This study can be described as an algorithm that includes candidate pool formation, quantum oracle design, amplitude amplification, and pheromone update algorithms, and give a mathematical model of the hybrid algorithm. The evaluation of standard TSPLIB benchmark instances is conducted experimentally on a quantum circuit simulator, and performance is measured in terms of the best and average tour costs, as well as computational overhead. Findings indicate that GroverACO is consistently able to achieve better quality solutions and discourage premature convergence than classical ACO, especially on medium and large-scale problems, albeit at a higher computational budget due to quantum simulation.

•Mar 23, 2026•0 citations

A Novel Quantum Algorithm for Ant Colony Optimization

Qian Qiu, Mohan Wu, Qichun Sun +2 more

Quantum ant colony optimization (QACO) has drew much attention since it combines the advantages of quantum computing and ant colony optimization (ACO) algorithms and overcomes some limitations of the traditional ACO algorithm. However, due to the hardware resource limitations of currently available quantum computers, such as the limited number of qubits, lack of high-fidelity gating operation, and low noisy tolerance, the practical application of the QACO is quite challenging. In this paper, we introduce a hybrid quantum-classical algorithm by combining the clustering algorithm with QACO algorithm, so that this extended QACO can handle large-scale optimization problems, which makes the practical application of QACO based on available quantum computation resource possible. To verify the effectiveness and performance of the algorithm, we tested the developed QACO algorithm with the Travelling Salesman Problem (TSP) as benchmarks. The developed QACO algorithm shows better performance under multiple data set. In addition, the developed QACO algorithm also manifests the robustness to noise of calculation process, which is typically a major barrier for practical application of quantum computers. Our work shows that the combination of the clustering algorithm with QACO has effectively extended the application scenario of QACO in current NISQ era of quantum computing.

arXiv:2403.00367•Mar 1, 2024•8 citations

Integrating Grover’s Quantum Search with Ant Colony Optimization for Efficient TSP Solving

Doddi Sreenija Reddy, Sountharrajan S

The Traveling Salesman Problem (TSP) is a canonical example of an NP-hard combinatorial optimization problem that has extensive applications in the context of logistics and routing and network design, where classical methods cannot be used in practice due to the large scale of the instances. The approach includes extensive research on a hybrid quantum and classical optimisation model, termed Grover-ACO, that combines the Grover quantum amplitude amplification with the elitist selection stage of the Ant Colony Optimization (ACO). This study can be described as an algorithm that includes candidate pool formation, quantum oracle design, amplitude amplification, and pheromone update algorithms, and give a mathematical model of the hybrid algorithm. The evaluation of standard TSPLIB benchmark instances is conducted experimentally on a quantum circuit simulator, and performance is measured in terms of the best and average tour costs, as well as computational overhead. Findings indicate that GroverACO is consistently able to achieve better quality solutions and discourage premature convergence than classical ACO, especially on medium and large-scale problems, albeit at a higher computational budget due to quantum simulation.

EPJ Web of Conferences•Jan 1, 2026•0 citations

Research and Application on Ant Colony Optimization Based on Quantum Computing

Wang Xiao-mi

Aiming at the disadvantage of optimization problems based on traditional ant colony optimization (ACO)which easily falls into local optimums and has worse performance in convergence,the paper unifies the quantum evolutionary algorithm (QEA) and the ant colony algorithm,in this algorithm,pheromone is represented by quantum bits and updated by a new quantum rotation gate adjustment srrategy.And this paper applies separately this algorithm and the traditional ACO to traveling salesman problem(TSP),The simulation results show that the algorithm of this paper has excellent global optimization properties and quicker convergence than the traditional ACO.

Information Technology and Informatization•Jan 1, 2009•0 citations

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

A novel quantum algorithm for ant colony optimisation

Mrityunjay Ghosh, Nivedita Dey, Debdeep Mitra +1 more

Abstract Ant colony optimisation (ACO) is a commonly used meta‐heuristic to solve complex combinatorial optimisation problems like the travelling salesman problem (TSP), vehicle routing problem (VRP) etc. However, classical ACO algorithms provide better optimal solutions but do not reduce computation time overhead to a significant extent. Algorithmic speed‐up can be achieved by using parallelism offered by quantum computing. Existing quantum algorithms to solve ACO are either quantum‐inspired classical algorithms or hybrid quantum‐classical algorithms. Since all these algorithms need the intervention of classical computing, leveraging the true potential of quantum computing on real quantum hardware remains a challenge. This study's main contribution is to propose a fully quantum algorithm to solve ACO, enhancing the quantum information processing toolbox in the fault‐tolerant quantum computing (FTQC) era. We have solved the single source single destination (SSSD) shortest‐path problem using our proposed adaptive quantum circuit for representing the dynamic pheromone‐updating strategy in real IBMQ devices. Our quantum ACO technique can be further used as a quantum ORACLE to solve complex optimisation problems in a fully quantum setup with significant speed up upon the availability of more qubits.

arXiv:2010.07413•IET Quantum Communication•Nov 2, 2021•27 citations
The quantum ant colony algorithm (QACO) is explored as a solution to the traveling salesman problem (TSP), targeting inefficiencies such as slow convergence and local optima entrapment found in traditional ant colony optimization (ACO) methods. By integrating quantum computing elements, specifically quantum rotation gates and qubits, into the ACO framework, QACO demonstrates enhanced efficiency and faster convergence. This paper delves into the foundational principles of quantum computing and their application to refine ACO, effectively solving the TSP. An in-depth analysis is provided, showcasing QACO's advantages over traditional ACO through empirical examples. These examples illustrate QACO's potential to improve path planning for applications within the rapidly growing e-commerce and logistics sectors. The integration of quantum mechanisms facilitates a more dynamic pheromone update process, which significantly reduces the likelihood of premature convergence and enhances solution quality in complex optimization scenarios. This advancement indicates a promising direction for future research in algorithmic optimization in both theoretical and practical applications.
The Traveling Salesman Problem (TSP) is a canonical example of an NP-hard combinatorial optimization problem that has extensive applications in the context of logistics and routing and network design, where classical methods cannot be used in practice due to the large scale of the instances. The approach includes extensive research on a hybrid quantum and classical optimisation model, termed Grover-ACO, that combines the Grover quantum amplitude amplification with the elitist selection stage of the Ant Colony Optimization (ACO). This study can be described as an algorithm that includes candidate pool formation, quantum oracle design, amplitude amplification, and pheromone update algorithms, and give a mathematical model of the hybrid algorithm. The evaluation of standard TSPLIB benchmark instances is conducted experimentally on a quantum circuit simulator, and performance is measured in terms of the best and average tour costs, as well as computational overhead. Findings indicate that GroverACO is consistently able to achieve better quality solutions and discourage premature convergence than classical ACO, especially on medium and large-scale problems, albeit at a higher computational budget due to quantum simulation.
Quantum ant colony optimization (QACO) has drew much attention since it combines the advantages of quantum computing and ant colony optimization (ACO) algorithms and overcomes some limitations of the traditional ACO algorithm. However, due to the hardware resource limitations of currently available quantum computers, such as the limited number of qubits, lack of high-fidelity gating operation, and low noisy tolerance, the practical application of the QACO is quite challenging. In this paper, we introduce a hybrid quantum-classical algorithm by combining the clustering algorithm with QACO algorithm, so that this extended QACO can handle large-scale optimization problems, which makes the practical application of QACO based on available quantum computation resource possible. To verify the effectiveness and performance of the algorithm, we tested the developed QACO algorithm with the Travelling Salesman Problem (TSP) as benchmarks. The developed QACO algorithm shows better performance under multiple data set. In addition, the developed QACO algorithm also manifests the robustness to noise of calculation process, which is typically a major barrier for practical application of quantum computers. Our work shows that the combination of the clustering algorithm with QACO has effectively extended the application scenario of QACO in current NISQ era of quantum computing.
The Traveling Salesman Problem (TSP) is a canonical example of an NP-hard combinatorial optimization problem that has extensive applications in the context of logistics and routing and network design, where classical methods cannot be used in practice due to the large scale of the instances. The approach includes extensive research on a hybrid quantum and classical optimisation model, termed Grover-ACO, that combines the Grover quantum amplitude amplification with the elitist selection stage of the Ant Colony Optimization (ACO). This study can be described as an algorithm that includes candidate pool formation, quantum oracle design, amplitude amplification, and pheromone update algorithms, and give a mathematical model of the hybrid algorithm. The evaluation of standard TSPLIB benchmark instances is conducted experimentally on a quantum circuit simulator, and performance is measured in terms of the best and average tour costs, as well as computational overhead. Findings indicate that GroverACO is consistently able to achieve better quality solutions and discourage premature convergence than classical ACO, especially on medium and large-scale problems, albeit at a higher computational budget due to quantum simulation.
Aiming at the disadvantage of optimization problems based on traditional ant colony optimization (ACO)which easily falls into local optimums and has worse performance in convergence,the paper unifies the quantum evolutionary algorithm (QEA) and the ant colony algorithm,in this algorithm,pheromone is represented by quantum bits and updated by a new quantum rotation gate adjustment srrategy.And this paper applies separately this algorithm and the traditional ACO to traveling salesman problem(TSP),The simulation results show that the algorithm of this paper has excellent global optimization properties and quicker convergence than the traditional ACO.
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.
Abstract Ant colony optimisation (ACO) is a commonly used meta‐heuristic to solve complex combinatorial optimisation problems like the travelling salesman problem (TSP), vehicle routing problem (VRP) etc. However, classical ACO algorithms provide better optimal solutions but do not reduce computation time overhead to a significant extent. Algorithmic speed‐up can be achieved by using parallelism offered by quantum computing. Existing quantum algorithms to solve ACO are either quantum‐inspired classical algorithms or hybrid quantum‐classical algorithms. Since all these algorithms need the intervention of classical computing, leveraging the true potential of quantum computing on real quantum hardware remains a challenge. This study's main contribution is to propose a fully quantum algorithm to solve ACO, enhancing the quantum information processing toolbox in the fault‐tolerant quantum computing (FTQC) era. We have solved the single source single destination (SSSD) shortest‐path problem using our proposed adaptive quantum circuit for representing the dynamic pheromone‐updating strategy in real IBMQ devices. Our quantum ACO technique can be further used as a quantum ORACLE to solve complex optimisation problems in a fully quantum setup with significant speed up upon the availability of more qubits.