A Novel Quantum Algorithm for Ant Colony Optimization

Ant colony optimization is one of the potential solutions to tackle intractable NP-Hard discrete combinatorial optimization problems. The metaphor of ant colony can be thought of as the evolution of the best path from a given graph as a globally optimal solution, which is unaffected by earlier local convergence to achieve improved optimization efficiency. Earlier Quantum Ant Colony Optimization research work was primarily based on Quantum-inspired Evolutionary Algorithms, which deals with customizing and improving the quantum rotation gate through upgraded formation of the lookup table of rotation angle. Instead of relying on evolutionary algorithms, we have proposed a discrete-time quantum algorithm based on adaptive quantum circuit for pheromone updation. The algorithm encodes all possible paths in the exhaustive search space as input to the ORACLE. Iterative model of exploration and exploitation of all possible paths by quantum ants results in global optimal path convergence through probabilistic measurement of selected path. Our novel approach attempts to accelerate the search space exploitation in a significant manner to obtain the best optimal path as a solution through quantum arallelization achieving polynomial time speed-up over its classical counter part.