| 本文已被：浏览 4979次 下载 8196次 |
码上扫一扫！ |
|
|
| 量子搜索算法 |
|
孙吉贵1,2,3, 何雨果1
|
|
1.吉林大学,计算机科学与技术学院,吉林,长春,130012;2.吉林大学,符号计算与知识工程教育部重点实验室,吉林,长春,130012;3.复旦大学,智能信息处理开放实验室,上海,200433
|
|
| 摘要: |
| 结合Grover和Tad Hogg的算法框架,叙述了量子算法中非结构化和结构化的两类搜索算法的设计思想.在Grover算法中,结合复杂性、临界点、非单调性、完备性和鲁棒性分析总结了一些性质,分析了Grover算法的优缺点.在Tad Hogg算法中对独立于问题的映射和相位调整分别作了介绍.重点分析了一种相位调整策略,解释该策略有效的原因和适用的场合,讨论了影响算法效率的因素.在上述论述的基础上对量子搜索算法与传统搜索算法进行了比较和分析,总结了隐藏在不同量子搜索算法背后的深刻思想. |
| 关键词: 量子搜索算法 Grover迭代的几何表示 独立于问题的映射 相位调整 |
| DOI： |
| 分类号: |
| 基金项目:Supported by National Natural Science Foundation of China under Grant Nos.60073039, 60273080 (国家自然科学基金); the Science and Technology Development Program of Jilin Provience of China under Grant No.20020306 (吉林省科技发展计划); the Foundation of Innovation of Jilin University of China(吉林大学创新基金) |
|
| A Quantum Search Algorithm |
|
SUN Ji-Gui,HE Yu-Guo
|
| Abstract: |
| In this paper, an important idea of devising a quantum algorithm is introduced, based on the description and analysis of two classes of quantum search algorithms, i.e. the unstructured search algorithms and structured search algorithms. Some qualities of Grover’s search algorithm, which is the representation of the unstructured search algorithms are introduced and summarized, by analyzing its peculiar complexity, completeness, sensitivity to the errors in the mappings, and its advantages and disadvantages. On introducing structure-based search algorithm, the Tad Hogg’s series of search algorithms are referred to. They can be summarized into one universal algorithm framework, which can be separated into two parts, i.e., the problem-independent mapping and phase rotation matrix. This paper places emphasis on analyzing one of the phase adaptation strategies, and interprets how it works and what can make it more efficient. Some other factors affect the algorithm are also discussed more generally. Finally, based on the comparison and analysis of classical search algorithm and the quantum one, the thoughts behind various quantum search algorithms are illustrated. |
| Key words: quantum search algorithm geometric interpretation of Grover’s iterative procedure problem- independent mapping phase for nogoods |
