求根问题的量子计算算法

• 全文链接
• 请求原文

作   者：

孙国栋;  苏盛辉;  徐茂智; 

作者机构：

北京工业大学计算机学院;  北京大学数学科学学院; 

关键词：

量子算法;  求根问题;  Shor算法;  Grover算法; 

期刊名称：

北京工业大学学报

基金项目：

i s s n：

0254-0037

年卷期：

2015 年 03 期

页   码：

366-371

摘   要：

求根问题是计算数论中的一个困难性问题,为了提高求根问题的求解效率和扩大量子计算的应用范围,对求根问题进行了量子算法的分析.在两大量子算法Shor算法和Grover算法的基础上,提出了2种解决求根问题的量子算法RF-Shor算法和RF-Grover算法.经分析,RF-Shor算法需要多项式规模的量子门资源,能以接近1的概率求出求根问题的所有解.在没有使用任何可提高搜索效率的经典策略的情况下,RF-Grover算法能在O(M/k)步内以至少1/2的概率求出求根问题k个解中的一个解.