物理学报2016，Vol.65Issue(8)：080302-1-080302-9,9.DOI:10.7498/aps.65.080302
基于散射量子行走的完全图上结构异常搜索算法∗
Search algorithm of structure anomalies in complete graph based on scattering quantum walk
摘要
Abstract
Quantum walks have been proven to be a useful framework in designing new quantum algorithms, of which the search algorithm is the most notable. Besides a general search for a special vertex, recent researches have shown that quantum walks can also be used to find structural anomalies. Suppose a vertex of complete graph KN is attached to a second graph G, then the kind of structure anomaly will break the symmetry of the complete graph. The search algorithm based on scattering quantum walk model is presented to speed up locating this kind of structure anomaly. The concepts of scattering quantum walk model and collapsed graphs are presented. The definition of the evolutionary operator, which is different from that of a general search, is given. Based on the specific definition of evolutionary operator and the obvious symmetry of complete graph, it is shown that the search space is confined to a low-dimensional collapsed space, and the initial state is chosen to lie in this subspace. To illustrate the evolutionary process of the search algorithm, an example is given in the case that G is a single vertex. Taking advantage of our earlier study on the evolutionary operator of coined quantum walks with Grover coin, calculations of the unitary operator in the collapsed space are greatly simplified. To quantify the evolutionary process of the algorithm, we use the matrix perturbation theory involving a perturbative approach to find the eigenvalues and eigenstates. It is the degenerate zeroth-order eigenvalue λ0 =1 that leads to the interesting parts of the Hilbert space. Most of the recent researches of searching the structure anomalies focus on star graph SN with an unspecified graph G attached to one of its external vertices, where the overall graph is divided into two parts by the central vertex. It is shown that quantum speedup will occur if and only if the eigenvalues associated with these two parts in the N → ∞ limit are the same. In this paper, we find that the collapsed graph of complete graphs can also be divided into two parts by a single collapsed vertex. As these two parts roughly correspond to the initial state and the desired state respectively, the techniques and results in star graphs can be generalized to the collapse graph on complete graph. What is more, under our definition of unitary evolution operator these two parts in the N →∞limit will always share the same eigenvalue, i.e. λ0=1, no matter what the structure of graph G is. Based on this, we prove that the search algorithm can find the target vertex in O(√N ) time steps with a success probability of 1−O(1/N ). That is to say, the quantum search algorithm gains a quadratic speedup over classical counterpart.关键词
散射量子行走/量子搜索/完全图Key words
scattering quantum walk/quantum search/complete graph引用本文复制引用
薛希玲,陈汉武,刘志昊,章彬彬..基于散射量子行走的完全图上结构异常搜索算法∗[J].物理学报,2016,65(8):080302-1-080302-9,9.基金项目
国家自然科学基金(批准号:61502101,61170321)、江苏省自然科学基金(批准号：BK20140651)和高等学校博士学科点专项科研基金(批准号:20110092110024)资助的课题.* Project supported by the National Natural Science Foundation of China (Grant Nos.61502101,61170321), the Natural Science Foundation of Jiangsu Province, China (Grant No. BK20140651), and the Research Fund for the Doctoral Program of Higher Education, China (Grant No.20110092110024) （批准号:61502101,61170321）
