Quantum Walk Based Search Algorithms
Quantum Walk Based Search Algorithms
复制标题
DOI：
10.1007/978-3-540-79228-4_3
复制
发表时间：
2008-04
期刊：
影响因子：
--
通讯作者：
M. Santha
中科院分区：
文献类型：
--
作者：
M. Santha
在这篇综述论文中，我们给出了一个直观的处理离散时间量化的经典马尔可夫链。Grover搜索和Ambainis，Szegedy和Magniez等人的基于量子行走的搜索算法将被描述为经典搜索过程的量子模拟。我们提出了一个相当详细的描述有点简化版本的MNRS算法。最后，在查询复杂性模型中，我们展示了量子行走如何应用于以下搜索问题：元素清晰度，矩阵乘积验证，限制范围关联性，三角形和组交换性。
In this survey paper we give an intuitive treatment of the discrete time quantization of classical Markov chains. Grover search and the quantum walk based search algorithms of Ambainis, Szegedy and Magniez et al. will be stated as quantum analogues of classical search procedures. We present a rather detailed description of a somewhat simplified version of the MNRS algorithm. Finally, in the query complexity model, we show how quantum walks can be applied to the following search problems: Element Distinctness, Matrix Product Verification, Restricted Range Associativity, Triangle, and Group Commutativity.