构造最小生成树的量子算法

图的最小生成树问题是网络优化中的一类基本问题。目前构造最小生成树的算法都是基于传统计算机的算法如Prim算法和Kruskal算法。该文提出了一个用于构造图的最小生成树的量子算法,它结合量子搜索的方法和经典Kruskal算法的思想,对于n个节点m条边的图,依次搜索出n-1条边使它们构成一棵最小生成树。这一算法的时间复杂性为O(nm√)。与经典Kruskal算法相比,在同等条件下,该文的算法有较快的加速。

A Quantum Algorithm for Constructing Minimum Spanning Tree

MST problem is a well-known network optimization problem.Efficient solutions based mainly on classical computers,such as Prim algorithm and Kruskal algorithm,are well-known.In this paper,a quantum algorithm for MST is proposed.It combines the method of quantum search with the idea of classical Kruskal algorithm.For an undirect graph with n vertices and m edges,the algorithm searches for n-1edges by turn to construct a MST,the complexity is O(n m√).Making a compare with classical Kruskal algorithm's complexity,its speedup is higher than classical one's on an equal footing.