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

摘要：

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

关键词：量子计算机、量子并行性、量子算法、量子搜索、最小生成树

所属期刊栏目：39

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：96-99