【摘要】：采用量子計(jì)算思維探索新的圖結(jié)構(gòu)搜索方法,提出了一種基于散射量子行走的完全圖上結(jié)構(gòu)異常的搜索算法.在N個頂點(diǎn)的完全圖上外接一個懸掛點(diǎn),既破壞了完全圖的對稱性,也預(yù)示著圖的拓?fù)浣Y(jié)構(gòu)將發(fā)生變化.首先給出完全圖上散射量子行走酉算子U的解析刻畫,將行走的Hilbert空間投影到低維不變子空間S,并給出酉算子U在空間S中的作用US的形式;然后將完全圖中所有狀態(tài)的均勻疊加態(tài)選擇為行走的初態(tài),借用微擾理論求出酉算子US的本征值和特征向量,通過數(shù)學(xué)解析計(jì)算出行走的終態(tài)(懸掛點(diǎn));最后分析算法的時間復(fù)雜度和成功概率.算法分析及Matlab仿真結(jié)果表明,利用散射量子行走可以在O(N~(1/2))步內(nèi)以接近于1的概率找到異常位置,而經(jīng)典算法中使用鄰接矩陣查找該異常點(diǎn)的時間復(fù)雜度為O(N),因此相對特定問題和特定的經(jīng)典算法,使用散射量子行走搜索算法可以實(shí)現(xiàn)二次加速.
[Abstract]:In this paper, a new method of graph structure search is explored by quantum computing thinking, and an algorithm for searching structural anomalies on complete graph based on scattered quantum walk is proposed. A suspension point is attached to the complete graph of N vertices, which not only destroys the symmetry of the complete graph, but also indicates that the topological structure of the graph will change. Firstly, the analytic characterization of the scattered quantum walking unitary operator U on a complete graph is given. The traveling Hilbert space is projected to the low dimensional invariant subspace S, and the form of US of the unitary operator U acting in the space S is given. Then, the uniform superposition states of all states in the complete graph are selected as the initial states of the walk, the eigenvalues and eigenvectors of the unitary operator US are obtained by using perturbation theory, and the final states (suspending points) of the walk are calculated by mathematical analysis. Finally, the time complexity and success probability of the algorithm are analyzed. The algorithm analysis and Matlab simulation results show that the anomalous position can be found in O (N ~ (1 / 2) step with the probability of approaching 1 by using scattering quantum walk. The time complexity of using the adjacency matrix to find the outlier in the classical algorithm is O (N),. Therefore, compared with the specific problem and the specific classical algorithm, the scattering quantum walk search algorithm can be used to achieve secondary acceleration.
【作者單位】： 東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院;東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室;南京森林公安學(xué)院信息技術(shù)系;南京郵電大學(xué)通信與信息工程學(xué)院;
【分類號】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王光輝;周珊;;完全圖中的正常染色的路和圈(英文)[J];運(yùn)籌學(xué)學(xué)報;2011年03期

2 王殿軍;完全圖圈分解的一種新方法[J];高校應(yīng)用數(shù)學(xué)學(xué)報A輯(中文版);1993年04期

3 鄧覲超,佟玉鳳;有關(guān)完全圖的算法及實(shí)現(xiàn)技術(shù)[J];煙臺大學(xué)學(xué)報(自然科學(xué)與工程版);1997年03期

4 張文軍;;完全圖的最小6-圈覆蓋和8-圈覆蓋[J];山東理工大學(xué)學(xué)報(自然科學(xué)版);2008年04期

5 O賜蜢，

本文編號：2329223