This paper studies the search for a single arc in a graph using the Szegedy walk. Arc search can be interpreted as finding a quantum particle not only in its position but also with a specific internal state. The quantum walk employed in this study is essentially the model proposed by Segawa and Yoshie for the purpose of edge search. First, we investigate how the symmetry of a graph is reflected in its time evolution matrix, and provide a sufficient condition under which the success probability of the search is independent of the marked arc. In particular, we prove that if a graph is arc-transitive, the success probability is independent of the choice of the marked arc. Next, we analyze path and cycle graphs and show that the quantum search is ineffective for these graphs, whereas it performs well for complete bipartite graphs $K_{n,n}$. These results provide a theoretical foundation for studying arc and edge searches on various graphs, while also suggesting new problems concerning the eigenvalue analysis of edge-signed graphs in spectral graph theory.
This paper studies the search for a single arc in a graph using the Szegedy walk. Arc search can be interpreted as finding a quantum particle not only in its position but also with a specific internal state. The quantum walk employed in this study is essentially the model proposed by Segawa and Yoshie for the purpose of edge search. First, we investigate how the symmetry of a graph is reflected in its time evolution matrix, and provide a sufficient condition under which the success probability of the search is independent of the marked arc. In particular, we prove that if a graph is arc-transitive, the success probability is independent of the choice of the marked arc. Next, we analyze path and cycle graphs and show that the quantum search is ineffective for these graphs, whereas it performs well for complete bipartite graphs Kn,n. These results provide a theoretical foundation for studying arc and edge searches on various graphs, while also suggesting new problems concerning the eigenvalue analysis of edge-signed graphs in spectral graph theory.
The coined quantum walk is a discretization of the Dirac equation of relativistic quantum mechanics, and it is the basis of many quantum algorithms. We investigate how it searches the complete bipartite graph of N vertices for one of k marked vertices with different initial states. We prove an intriguing dependence on the number of marked and unmarked vertices in each partite set. For example, when the graph is irregular and the initial state is the typical uniform superposition over the vertices, then the success probability can vary greatly from one time step to the next, even alternating between 0 and 1, so the precise time at which measurement occurs is crucial. When the initial state is a uniform superposition over the edges, however, the success probability evolves smoothly. As another example, if the complete bipartite graph is regular, then the two initial states are equivalent. Then if two marked vertices are in the same partite set, the success probability reaches 1/2, but if they are in different partite sets, it instead reaches 1. This differs from the complete graph, which is the quantum walk formulation of Grover's algorithm, where the success probability with two marked vertices is 8/9. This reveals a contrast to the continuous-time quantum walk, whose evolution is governed by Schr\"odinger's equation, which asymptotically searches the regular complete bipartite graph with any arrangement of marked vertices in the same manner as the complete graph.
When searching for a marked vertex in a graph, Szegedy's usual search operator is defined by using the transition probability matrix of the random walk with absorbing barriers at the marked vertices. Instead of using this operator, we analyze searching with Szegedy's quantum walk by using reflections around the marked vertices, that is, the standard form of quantum query. We show we can boost the probability to 1 of finding a marked vertex in the complete graph. Numerical simulations suggests that the success probability can be improved for other graphs, like the two-dimensional grid. We also prove that, for a certain class of graphs, we can express Szegedy's search operator, obtained from the absorbing walk, using the standard query model.
Continuous-time quantum walks are typically effected by either the discrete Laplacian or the adjacency matrix. In this paper, we explore a third option: the signless Laplacian, which has applications in algebraic graph theory and may arise in layered antiferromagnetic materials. We explore spatial search on the complete bipartite graph, which is generally irregular and breaks the equivalence of the three quantum walks for regular graphs, and where the search oracle breaks the equivalence of the Laplacian and signless Laplacian quantum walks on bipartite graphs without the oracle. We prove that a uniform superposition over all the vertices of the graph partially evolves to the marked vertices in one partite set, with the choice of set depending on the jumping rate of the quantum walk. We boost this success probability to 1 by proving that a particular nonuniform initial state completely evolves to the marked vertices in one partite set, again depending on the jumping rate. For some parameter regimes, the signless Laplacian yields the fastest search algorithm of the three, suggesting that it could be a new tool for developing faster quantum algorithms.
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.
Searching via quantum walk is a topic that has been extensively studied. Most previous results provide approximate solutions, while in this paper we prove an algorithm that can find a marked vertex certainly. We adopt the coined discrete-time quantum walk (DTQW) model with adjusted operators and prove that, on complete bipartite graphs, when parameters are set properly, coined DTQW can deterministically find a marked vertex, i.e., the success probability is exactly 1. Before this paper there have been results of an alternating continuous-time quantum walk method that achieve deterministic spatial search, but this paper provides a deterministic quantum spatial search result via DTQW, while maintaining a quadratic speedup compared to classical algorithms. We also provide the quantum circuit implementation. Published by the American Physical Society 2024
n this paper, we consider the problem of searching a marked vertex in a graph based on quantum walks. A very large body of research exists on this issue, from both theoretical and experimental studies, yet the existing quantum walk-based search algorithms require knowing exactly how many marked vertices there are before starting the search process. In addition, even if the precise knowledge of the number of marked vertices is known, the success probability of these algorithms could shrink dramatically when the number of search steps is greater than the right one. For avoiding these defects, in this paper we present a new quantum walk-based search algorithm which need not know any prior information about the marked vertices, but still keeps a quadratic speedup over classical ones and ensures that the error is bounded by a tunable parameter ϵ. More specifically, for an N-vertex complete bipartite graph with marked vertices but without knowing the number of marked vertices, if the number of search steps h satisfies h≥ln(ϵ2)N, then the algorithm will output a marked vertex with probability at least $ 1-\epsilon$ for any given ϵ∈(0,1]. This feature leads to quantum search algorithms with stronger robustness and a wider scope of application.