An improved quantum optimization algorithm for multicast routing problem

摘要

Delay-constraint minimum cost multicast tree problem is a classical combinatorial optimization problem. It has been proved to be a NP-complete problem. Many algorithms have been proposed to solve the problem. This paper proposed a tree-based quantum optimization algorithm for the multicast tree problem. In this algorithm, the probability amplitude of each side was stored in a quantum, and the quantum evolved by quantum gate, each quantum moved in the direction of better solution. The evolutionary process merged the trees rather than paths directly to accelerate the convergence and improved the quality of solutions. Simulation results showed that the algorithm in this paper performed well at searching and convergence speed.