Arc search in graphs via Szegedy walks
Sho Kubota, Kiyoto Yoshino · 2026
Read Arc search in graphs via Szegedy walks by Sho Kubota, Kiyoto Yoshino (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-19134.txt.
Introduction
Kubota and Yoshino study arc search using the Szegedy walk, which finds a quantum particle by position and internal state. Graph symmetry appears in the time evolution matrix, giving a sufficient condition for success probability independent of the marked arc. Arc-transitive graphs have success probabilities independent of the marked arc. Path and cycle graphs defeat the search, while complete bipartite graphs succeed. The results ground future arc and edge searches and suggest new edge-signed graph eigenvalue problems.
Catalog record
| CREATOR | Sho Kubota, Kiyoto Yoshino |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50227 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.19134
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Arc search in graphs via Szegedy walks Sho Kubota, Kiyoto Yoshino Abstract 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 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. Keywords: quantum search, signed graph, automorphism MSC 2020 subject classifications: 05C50; 81Q99 1 Introduction Quantum search has been widely studied as one of the representative applications of quantum computing and is known to provide dramatic speedups over classical search algorithms. In particular, Grover’s algorithm [ 7 ] demonstrated that a marked item can be found in a database in O(\sqrt{N}) steps (more precisely, \Theta(\sqrt{N}) steps), which has attracted significant attention. Subsequently, it has been shown that Grover’s algorithm can be generalized to efficiently search for multiple marked items [ 3 ] . These developments have established quantum search as a versatile tool for a variety of algorithms. This is discussed, for example, in the textbook by Nielsen and Chuang [ 12 ] . In parallel with this trend, search algorithms based on quantum walks began to be studied, such as [ 16 , 17 ] . Furthermore, subsequent studies have established new frameworks for acceleration that exploit graph structures, including applications to element distinctness [ 2 ] and triangle detection [ 11 ] . This paper formulates the search problem from a perspective different from conventional quantum search. The framework for defining quantum walks on finite-dimensional vector spaces indexed by symmetric arc sets has been extensively studied, but most existing search algorithms mark vertices in a graph as the search targets [ 4 , 9 ] . Search algorithms for finding edges in graphs have also been discussed recently in [ 14 , 18 ] . In contrast, this study considers the setting in which an arc is marked as the search target. In this framework, the search can be interpreted as not only identifying the vertex where the walker is found but also simultaneously detecting internal degrees of freedom, such as the direction of motion or the spin state. First, we study the relationship between search behavior in discovering a marked arc and symmetry of graphs. We refer to the probability of finding a marked item, whether a vertex or an arc, as the success probability . In the case of vertex search on vertex-transitive graphs, it is widely understood that the probability of finding a marked vertex is independent of which vertex is marked. Similarly, in arc search on arc-transitive graphs, the success probability is likewise expected to be independent of the choice of marked arc. However, this fact is not necessarily obvious and requires a rigorous mathematical justification. One of our main results is to clarify conditions for symmetry of graphs that guarantee equal probabilities of discovering marked arcs. In particular, we prove that if a graph is arc-transitive, the success probability is independent of the choice of the marked arc. See Corollary 3.5 for details. Next, we analyze the search behavior and computational complexity on path graphs, cycle graphs, and complete bipartite graphs. We show that our search algorithm is not effective for path or cycle graphs, whereas it performs well on complete bipartite graphs K_{n,n} . More specifically, the success probabilities on the path graphs P_{n} and the cycle graphs C_{n} are \frac{1}{2n-2} and \frac{1}{2n} , respectively, and are independent of the measurement time. On the other hand, for the success probability p^{*} at an appropriately chosen measurement time in complete bipartite graphs K_{n,n} , it is shown that p^{*}\geq\frac{1}{2}-\Theta\left(\frac{1}{\sqrt{n}}\right) holds and the corresponding measurement time is \Theta(n) . Since K_{n,n} has 2n^{2} arcs, this yields a quadratic speedup for this graph. 2 Preliminaries See [ 6 ] for basic terminology related to graphs. Let \Gamma=(V,E) be a graph with the vertex set V and the edge set E . Throughout this paper, we assume that graphs are simple and finite, i.e., |V|<\infty and E\subset\{\{x,y\}\subset V\mid x\neq y\} . Define \mathcal{A}=\mathcal{A}(\Gamma)=\{(x,y),(y,x)\mid\{x,y\}\in E\} , which is the set of the symmetric arcs of \Gamma . The origin x and terminus y of a=(x,y)\in\mathcal{A} are denoted by o(a) and t(a) , respectively. We write the inverse arc of a as a^{-1} . Before defining the time evolution matrix used in the search, we introduce several matrices related to Grover walks. Note that Grover walks are also referred to as arc-reversal walks or arc-reversal Grover walks, and they are known as a special case of bipartite walks [ 5 ] . Let \Gamma=(V,E) be a graph, and set \mathcal{A}=\mathcal{A}(\Gamma) . The boundary matrix d=d(\Gamma)\in\mathbb{C}^{V\times\mathcal{A}} is defined by d_{x,a}=\frac{1}{\sqrt{\deg x}}\delta_{x,t(a)} , where \delta_{a,b} is the Kronecker delta. By directly calculating the entries based on the definition of matrix multiplication, it follows that dd^{*}=I, where I is the identity matrix. The shift matrix S=S(\Gamma)\in\mathbb{C}^{\mathcal{A}\times\mathcal{A}} is defined by S_{a,b}=\delta_{a,b^{-1}} . Clearly, S^{2}=I . The time evolution matrix U=U(\Gamma)\in\mathbb{C}^{\mathcal{A}\times\mathcal{A}} for the Grover walk is defined by U:=S(2d^{*}d-I), but we do not use U itself. Instead, we use a modified form of U , which is introduced in the next section, to perform the search. Furthermore, we describe relationships between symmetry of graphs and Grover walks. For the convenience of a broad readership, we begin by introducing automorphisms of graphs and their associated permutation matrices. Let \Gamma=(V,E) be a graph. A mapping g:V\to V is an automorphism of \Gamma if g is bijective, and \{x,y\}\in E if and only if \{g(x),g(y)\}\in E . We denote the set of all automorphisms of \Gamma by \Aut(\Gamma) . Let g be an automorphism of a graph \Gamma . Since g is bijective, it defines the permutation matrix M_{g}\in\mathbb{C}^{V\times V} given by (M_{g})_{x,y}=\delta_{x,g(y)} . Basic properties of permutation matrices are M_{g}^{\top}=M_{g}^{-1}=M_{g^{-1}}, (2.1) and M_{g}e_{x}=e_{g(x)} for x\in V . The action of automorphisms of a graph is naturally extended to the set of symmetric arcs. Let g be an automorphism of a graph \Gamma , and let \mathcal{A}=\mathcal{A}(\Gamma) be the symmetric arc set. Define \tilde{g}:\mathcal{A}\to\mathcal{A} by \tilde{g}(\left(x,y)\right)=(g(x),g(y)) . Clearly, \tilde{g} is a bijection. Thus, the permutation matrix N_{\tilde{g}}\in\mathbb{C}^{\mathcal{A}\times\mathcal{A}} is defined by (N_{\tilde{g}})_{a,b}=\delta_{a,\tilde{g}(b)} , and it holds that N_{\tilde{g}}^{\top}=N_{\tilde{g}}^{-1}=N_{\tilde{g}^{-1}} as in Equality ( 2.1 ). Moreover, we have N_{\tilde{g}}e_{a}=e_{\tilde{g}(a)} for a\in\mathcal{A} . The following statements describe relationships between permutation matrices induced by automorphisms and matrices associated with Grover walks. See [ 10 , Lemmas 3.1 and 3.2]