Spatial search on Johnson graphs by continuous-time quantum walk
Spatial search on Johnson graphs by continuous-time quantum walk
复制标题
通过连续时间量子行走对约翰逊图进行空间搜索
DOI：
10.1007/s11128-022-03417-9
复制
发表时间：
2022
影响因子：
2.5
通讯作者：
Renato Portugal
中科院分区：
文献类型：
--
作者：
Hajime Tanaka;Mohamed Sabri;Renato Portugal
图上的空间搜索是量子行走最重要的算法应用之一。证明基于量子行走的搜索比基于随机行走的搜索更有效是一个难题，人们已经通过多种方式解决了这个问题。通常，图对称性有助于计算算法的计算复杂性，而约翰逊图是关于对称性的一个有趣的类别，因为它们是正则的、哈密顿连通的、顶点和距离传递的。在这项工作中，我们表明，通过连续时间量子行走对约翰逊图进行空间搜索，对于每个固定直径渐进地达到格罗弗下界，成功概率为 1，其中 N 是顶点数。该证明在数学上是严格的，可用于其他图类。
Spatial search on graphs is one of the most important algorithmic applications of quantum walks. To show that a quantum-walk-based search is more efficient than a random-walk-based search is a difficult problem, which has been addressed in several ways. Usually, graph symmetries aid in the calculation of the algorithm’s computational complexity, and Johnson graphs are an interesting class regarding symmetries because they are regular, Hamilton-connected, vertex- and distance-transitive. In this work, we show that spatial search on Johnson graphs by continuous-time quantum walk achieves the Grover lower boundwith success probability 1 asymptotically for every fixed diameter, whereNis the number of vertices. The proof is mathematically rigorous and can be used for other graph classes.
登录
查看更多内容
平衡树上的连续时间量子搜索
影响因子：
2.9
作者：
Pascal Philipp;Luís Tarrataca;S. Boettcher
通讯作者：
S. Boettcher
约翰逊图上的量子行走搜索
DOI：
10.1088/1751-8113/49/19/195303
发表时间：
2016
期刊：
Journal of Physics A: Mathematical and Theoretical
影响因子：
--
作者：
T. G. Wong
通讯作者：
T. G. Wong
Bollobás 无标度网络上的连续时间量子行走空间搜索
影响因子：
2.9
作者：
Tomo Osada;B. Coutinho;Y. Omar;K. Sanaka;W. Munro;K. Nemoto
通讯作者：
K. Nemoto
影响因子：
1.8
作者：
Benedetti, Claudia;Rossi, Matteo A. C.;Paris, Matteo G. A.
通讯作者：
Paris, Matteo G. A.
动量空间中连续时间量子行走的量子搜索
DOI：
10.1088/1361-6455/ab63ad
发表时间：
2020
期刊：
Journal of Physics B: Atomic, Molecular and Optical Physics
影响因子：
--
作者：
Michele Delvecchio;C. Groiseau;F. Petiziol;G. Summy;S. Wimberger
通讯作者：
S. Wimberger