Quantum walk search on Johnson graphs
Quantum walk search on Johnson graphs
复制标题
约翰逊图上的量子行走搜索
DOI：
10.1088/1751-8113/49/19/195303
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
T. G. Wong
中科院分区：
文献类型：
--
作者：
T. G. Wong
约翰逊图J（n，k）由n个符号定义，其中顶点是符号的k元子集，如果顶点之间只有一个符号不同，则它们是相邻的。特别地，J（n，1）是完全图Kn，J（n，2）是强正则三角图Tn，已知这两者都支持通过连续时间量子行走的快速空间搜索。在本文中，我们证明了J（n，3），这是n-四面体图，也支持快速搜索。在这个过程中，我们表明，一个变化的基础是需要退化微扰理论，以准确地描述动力学。这种方法也可以应用于k固定的一般约翰逊图J（n，k）。
The Johnson graph J ( n , k ) is defined by n symbols, where vertices are k-element subsets of the symbols, and vertices are adjacent if they differ in exactly one symbol. In particular, J ( n , 1 ) is the complete graph Kn, and J ( n , 2 ) is the strongly regular triangular graph Tn, both of which are known to support fast spatial search by continuous-time quantum walk. In this paper, we prove that J ( n , 3 ) , which is the n-tetrahedral graph, also supports fast search. In the process, we show that a change of basis is needed for degenerate perturbation theory to accurately describe the dynamics. This method can also be applied to general Johnson graphs J ( n , k ) with fixed k.