Quantum ant colony optimization (QACO) has drew much attention since it combines the advantages of quantum computing and ant colony optimization (ACO) algorithm overcoming some limitations of the traditional ACO algorithm. However,due to the hardware resource limitations of currently available quantum computers, the practical application of the QACO is still not realized. In this paper, we developed a quantum-classical hybrid algorithm by combining the clustering algorithm with QACO algorithm.This extended QACO can handle large-scale optimization problems with currently available quantum computing resource. We have tested the effectiveness and performance of the extended QACO algorithm with the Travelling Salesman Problem (TSP) as benchmarks, and found the algorithm achieves better performance under multiple diverse datasets. In addition, we investigated the noise impact on the extended QACO and evaluated its operation possibility on current available noisy intermediate scale quantum(NISQ) devices. Our work shows that the combination of the clustering algorithm with QACO effectively improved its problem solving scale, which makes its practical application possible in current NISQ era of quantum computing.
Quantum ant colony optimization (QACO) has drew much attention since it combines the advantages of quantum computing and ant colony optimization (ACO) algorithm overcoming some limitations of the traditional ACO algorithm. However,due to the hardware resource limitations of currently available quantum computers, the practical application of the QACO is still not realized. In this paper, we developed a quantum-classical hybrid algorithm by combining the clustering algorithm with QACO algorithm.This extended QACO can handle large-scale optimization problems with currently available quantum computing resource. We have tested the effectiveness and performance of the extended QACO algorithm with the Travelling Salesman Problem (TSP) as benchmarks, and found the algorithm achieves better performance under multiple diverse datasets. In addition, we investigated the noise impact on the extended QACO and evaluated its operation possibility on current available noisy intermediate scale quantum(NISQ) devices. Our work shows that the combination of the clustering algorithm with QACO effectively improved its problem solving scale, which makes its practical application possible in current NISQ era of quantum computing.
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 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.
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 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.
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 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.