求根问题的量子计算算法

• 作者: 孙国栋 徐茂智 苏盛辉
• 来源期刊: 北京工业大学学报
• 学科: 工学
• 关键词: 量子算法 求根问题 Shor算法 Grover算法
• 年，卷（期）: 2015,（3）
• 所属期刊栏目: 计算机与软件工程
• 页码范围: 366-371
• 页数: 6页
• 分类号: TP309
• 字数: 6401字
• 语种: 中文
• DOI: 10.11936/bjutxb2014040051

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐茂智	北京工业大学计算机学院	19	127	3.0	11.0
3	孙国栋	北京工业大学计算机学院	7	48	4.0	6.0
4	苏盛辉	北京工业大学计算机学院	8	21	3.0	3.0