论文部分内容阅读
量子信息科学是一门新兴的交叉学科,它在信息领域中有着独特的性能,在提高运算速度、确保信息安全、增大信息容量和提高检测精度等方面可突破现有经典信息系统的极限。特别是近年来,基于量子并行计算的量子算法有效地降低了一些经典难解算法的计算复杂度。本文研究了基于量子并行计算的Grover算法在多用户检测和网络路径优化中的应用。
在CDMA多用户检测问题中,Verdu已经证明最佳检测算法与二次函数的最优性相关,并且提出了基于信号估计的最大似然检测算法(MLSE)。这是一个搜索问题,其计算复杂度与用户数成指数关系,这在常规计算中是一个NP难解问题,有效降低最佳检测算法的计算复杂度,是当前多用户检测的一个研究热点。由于Grover算法可以以O(√N)的速度有效搜索长为N的未排序数据库搜索问题,结合多用户检测的最大似然检测算法,本文提出了一种基于量子并行计算特性和Grover算法的量子最佳检测方案,分析了该方案下最佳检测算法的计算复杂度。与经典最佳检测算法相比,量子最佳检测算法的复杂度下降为O(√2K),其中K为多用户通信系统的用户数,并且在误码率与用户数、误码率与用户间相关系数和误码率与信噪比等性能与经典最佳检测算法基本相同。
最短路径问题是网络路径优化的基本问题之一。目前,寻找连通网络的最小生成树的算法主要是Prim算法和Kruskal算法。然而面对庞大的网络体系,它们都存在运算复杂度过高、搜索效率低下的缺陷。本文利用Grover算法构造了六个节点的网络最小生成树,分析了基于Grover算法的最小生成树的计算复杂度,与经典算法相比计算复杂度明显降低。