Finding structural anomalies in graphs by means of quantum walks

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors	BUŽEK Vladimír FELDMAN Edgar HILLERY Mark LEE Hai-Woong REITZNER Daniel ZHENG Hongjun
Year of publication	2010
Type	Article in Periodical
Magazine / Source	Physical Review A
MU Faculty or unit	Faculty of Informatics
Citation
Web	http://arxiv.org/abs/1009.0482
Field	Informatics
Keywords	Quantum walks; graphs
Description	We explore the possibility of using quantum walks on graphs to find structural anomalies, such as extra edges or loops, on a graph. We focus our attention on star graphs, whose edges are like spokes coming out of a central hub. If there are N spokes, we show that a quantum walk can find an extra edge connecting two of the spokes or a spoke with a loop on it in O(sqrt(N)) steps. We initially find that if all of the spokes have loops except one, the walk will not find the spoke without a loop, but this can be fixed if we choose the phase with which the particle is reflected from the vertex without the loop. Consequently, quantum walks can, under some circumstances, be used to find structural anomalies in graphs.
Related projects:	Highly Parallel and Distributed Computing Systems