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(1N). That is to say, the quantum search algorithm gains a quadratic speedup over classical counterpart.
Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs (SRGs) with parameters ( N , k , λ , μ ) achieves full quantum speedup. The problem is reconsidered in terms of scattering quantum walk, a type of discrete-time quantum walks. Here, the search space is confined to a low-dimensional subspace corresponding to the collapsed graph of SRGs. To quantify the algorithm's performance, we leverage the fundamental pairing theorem, a general theory developed by Cottrell for quantum search of structural anomalies in star graphs. The search algorithm on the SRGs with k scales as N satisfies the theorem, and results can be immediately obtained, while search on the SRGs with k scales as N does not satisfy the theorem, and matrix perturbation theory is used to provide an analysis. Both these cases can be solved in O ( N ) time steps with a success probability close to 1. The analytical conclusions are verified by simulation results on two SRGs. These examples show that the formalism on star graphs can be applied more generally.
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.
We present a rigorous perturbative analysis of the Szegedy quantum walk search algorithm on the complete graph with marked nodes, when a specific anomaly is present in the graph. This is motivated by the problem of monitoring the integrity of dense trusted communication networks with a quantum-assisted procedure. The topology of these networks is modeled as a complete graph, and the anomaly of interest is the disappearance of a single communication link which represents the minimal and spectrally hardest structural defect to detect. Building on the graph-completeness testing algorithm framework, we quantify how the removal of a single unmarked-unmarked edge propagates through the relevant spectral quantities of the Szegedy quantum walk. Denoting by n the total number of nodes of the graph and by m the number of marked nodes, we prove that the perturbation to the transition matrix has spectral norm Θ(1/n), and that the gap eigenvalue undergoes a strictly negative first-order shift for every n and every number of marked nodes m, providing a formal proof of a conjecture from our completeness testing algorithm work; in the regime m=Θ(n) relevant for the search algorithm, this shift has magnitude Θ(1/n2). The corresponding eigenphase shift satisfies Δθ⋆=Θ(1/n2) in the same regime. We establish that the rotation angle of the effective subspace under this perturbation is O(1/n) for m=Θ(n). Finally, we bound the change in success probability to O(1/n) in this same regime of marked nodes, and show that this bound is dominated by the geometric misalignment of the effective subspace rather than by the spectral shift of the eigenphase. These results provide both the theoretical foundations and the fundamental scaling limits of quantum walk-based topology integrity monitoring under minimal structural perturbations.
This paper explores the application of quantum walk algorithms to graph traversal and search problems. Classical algorithms often struggle with the computational complexity of traversing and searching large graphs, leading to significant time and resource limitations. Quantum walks, utilizing superposition and interference, offer a potential pathway to achieve exponential speedups. This work details the theoretical framework for applying quantum walks to graph problems, specifically focusing on traversal and search tasks. We present a generalized approach for mapping graph structures onto quantum walk systems and discuss the key mathematical formulations involved. The core of our investigation revolves around the construction of quantum walk operators that mimic the movement and interaction rules inherent in graph traversal. We analyze the evolution of the quantum walk state and derive expressions for the probability of reaching a specific node in the graph. Furthermore, we examine the impact of graph topology on the performance of the quantum walk, highlighting the potential for tailored algorithms to exploit specific graph structures. The results demonstrate the theoretical feasibility of quantum walk algorithms for significantly accelerating graph traversal and search operations, contributing to advancements in areas such as network analysis, database management, and artificial intelligence.
We develop a general theory for a quantum-walk search on a star graph. A star graph has N edges each of which is attached to a central vertex. A graph G is attached to one of these edges, and we would like to find out to which edge it is attached. This is done by means of a quantum walk, a quantum version of a random walk. This walk contains O(sqrt[N]) steps, which represents a speedup over a classical search, which would require O(N) steps. The overall graph, star plus G, is divided into two parts, and we find that for a quantum speedup to occur, the eigenvalues associated with these two parts in the N→∞ limit must be the same. Our theory tells us how the initial state of the walk should be chosen, and how many steps the walk must make in order to find G.