Finding structural anomalies in graphs by means of quantum walks

Abstract

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.

References in corpus (6)

• Spatial search by quantum walk
• Quantum Walk in Position Space with Single Optically Trapped Atoms
• Realization of quantum walks with negligible decoherence in waveguide lattices
• Decoherence in quantum walks - a review
• Quantum walks on quotient graphs
• Quantum searches on highly symmetric graphs

Cited by in corpus (18)

• Quantum walks: a comprehensive review
• Perfect state transfer by means of discrete-time quantum walk search algorithms on highly symmetric graphs
• Quantum Walks
• Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
• Driven Quantum Walks
• Quantum walks as a probe of structural anomalies in graphs
• Finding structural anomalies in star graphs: A general approach
• Finding paths in tree graphs with a quantum walk
• Quantum walks on complex networks with connection instabilities and community structure
• Encoding graphs into quantum states: an axiomatic approach
• Framework for discrete-time quantum walks and a symmetric walk on a binary tree
• Finding paths with quantum walks or quantum walking through a maze
• Lively quantum walks on cycles
• Quantum walk based state transfer algorithms on the complete M-partite graph
• Finding Structural Anomalies in Star Graphs Using Quantum Walks: A General Approach
• Scattering Quantum Random Walks on Square Grids and Randomly Generated Mazes
• Experimental nonlocality-based network diagnostics of mutipartite entangled states
• Asymptotic reduced density matrix of discrete-time quantum walks