Finding structural anomalies in complete graphs using scattering quantum walks
Xiling Xue, Hanwu Chen, Zhihao Liu · International Journal of Quantum Information · 2016
The search for structural anomalies in a complete graph, [Formula: see text], using scattering quantum walks (SQWs) is investigated in this study. A complete graph with a second graph, [Formula: see text], attached to one of its vertices is referred to as external structural anomaly. The structural change within a complete graph is called internal structural anomaly. First, an example with [Formula: see text] being a triangle is presented to illustrate the problem. Then, a general proof is provided to show that the vertex to which [Formula: see text] is attached can be found in [Formula: see text] time steps as long as the connectivity between [Formula: see text] and [Formula: see text] is far less than [Formula: see text]. Finally, two types of internal structural anomalies, namely, a complete graph with a missing edge and that with an extra loop, are considered. These two anomalies can be solved in a similar manner as external anomalies in [Formula: see text] time steps. These examples demonstrate that Cottrell’s formalism in star graphs can be applied more generally.