Pulsation of quantum walk between two arbitrary graphs with weakly connected bridge

Taisuke Hosaka, Etsuo Segawa · 2025

Read Pulsation of quantum walk between two arbitrary graphs with weakly connected bridge by Taisuke Hosaka, Etsuo Segawa (2025) 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-2511-12872.txt.

Introduction

Taisuke Hosaka and Etsuo Segawa study a quantum walker moving on two graphs joined by a single weak bridge. The walk is a Grover walk, a quantum version of a random walk used in search algorithms. A parameter sets the strength of the bridge: at zero the two graphs are fully separate. The authors show that for a weak bridge, a pulsation occurs, meaning the walker swings rhythmically between the two graphs.

They derive a formula for the chance of finding the walker on either side when the bridge is weak. Surprisingly, the rhythm depends only on how many edges each graph has, not on their detailed shapes. The swing period grows as the bridge weakens, and when both graphs have the same number of edges, the walker transfers almost completely each swing. The result gives quantum walk designers a simple rule for coupled networks.

Catalog record

CREATORTaisuke Hosaka, Etsuo Segawa
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-12872

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Pulsation of quantum walk between two arbitrary graphs with weakly connected bridge Taisuke Hosaka, Etsuo Segawa Abstract Abstract We consider the Grover walk on a finite graph composed of two arbitrary simple graphs connected by one edge, referred to as a bridge. The parameter \epsilon>0 assigned at the bridge represents the strength of connectivity: if \epsilon=0 , then the graph is completely separated. We show that for sufficiently small values of \epsilon , a phenomenon called pulsation occurs. The pulsation is characterized by the periodic transfer of the quantum walker between the two graphs. An asymptotic expression with respect to small \epsilon for the probability of finding the walker on either of the two graphs is derived. This expression reveals that the pulsation depends solely on the number of edges in each graph, regardless of their structure. In addition, we obtain that the quantum walker is transferred periodically between the two graphs, with a period of order O(\epsilon^{-1/2}) . Furthermore, when the number of edges of two graphs is equal, the quantum walker is almost completely transferred. 1 Introduction Quantum walks play key roles in the quantum computing like quantum algorithms [ 5 , 3 , 10 ] , quantum simulation [ 21 ] , and quantum cryptography [ 25 ] . Such effectiveness of application of quantum walks is based on distinctive properties compared to classical random walks, such as localization [ 15 , 14 , 17 ] , ballistic spreading [ 18 ] and periodicity [ 22 , 19 , 12 ] . One of the main topics in the study of quantum walks is quantum search algorithms [ 23 ] and perfect state transfer [ 8 ] . Spatial search algorithms based on quantum walks aim to locate the marked vertex with high probability, providing quadratic speed-up over classical search algorithms on some graphs [ 1 , 4 ] . Perfect state transfer refers to the phenomenon in which a quantum walker is transferred from one position to another with probability one [ 9 , 24 , 26 ] . Characterizing graphs that allow perfect state transfer remains an important research direction. Also, without being obsessed with perfectly transferring the quantum walker, some studies have shown that a sufficient amount of quantum walkers transfer to one position, such as the antipodal point or self-loop [ 20 ] . Both of these topics share a common goal: concentrating the quantum walker at a specific positions. Motivated by this, we investigate a related phenomenon called pulsation, where the quantum walker repeatedly transfers between two regions of the graph [ 13 ] . This behavior may be seen as a generalization of both spatial search algorithms and perfect state transfer. In this work, we aim to understand when pulsation occurs and to clarify the key factors that cause it. We hope that this pulsation can be added as one of the distinctive properties of quantum walks. Our study treats the Grover walk on the finite graph constructed by two graphs connected by an edge, referred to as a bridge . We put a weight parametrized by \epsilon>0 on a bridge, while all edges except a bridge are put weight 1 . The parameter \epsilon is considered as the strength of connectivity. If \epsilon=1 , standard Grover walk on the graphs is reproduced. While if \epsilon=0 , effectively the bridge disappears, and the graph is decomposed into the three disconnected parts: the two subgraphs and the bridge edge itself. This means that the smaller the value of \epsilon , the weaker the connectivity between two graphs in our model. Then, intuitively, if \epsilon is close to 0, it would be expected that the quantum walker would have difficulty transferring between the two graphs and would remain trapped on one side of the subgraphs. However, we observe a counterintuitive phenomenon: for sufficiently small \epsilon , the quantum walker goes back and forth between subgraphs via a weakly bridge , that is, the pulsation occurs in these settings. We obtain an asymptotic behavior of the finding probability of the quantum walker in either graph with respect to small \epsilon , presented in Theorem 4.1 (see Section 4). Theorem 4.1 implies that the behavior of the quantum walker determined solely by the number of edges in each graph and is independent of their structure. Theorem 4.2 gives the periodicity of the behavior of the quantum walk of order O(\epsilon^{-1/2}) . This work provides a new feature of quantum walks called pulsation and we hope that it contributes to a deeper understanding of quantum transport phenomena. This paper is organized as follows. In Section 2 , we proposed the settings of the graphs and our quantum walk model. Section 3 shows some numerical simulations. In Section 4 , we give our main results. In Section 5 , we address the proof of the main theorem. Section 6 summarizes our results and discusses future work. 2 Setting the model Let H_{j}=(V_{j},A_{j})\,(j=1,2) be a simple connected graph. Here, V_{j} and A_{j} are a set of vertices and symmetric arcs, respectively. The origin and terminal vertex of an arc a are indicated by o(a) and t(a) . The inverse arcs of an arc a are denoted by \bar{a} . Note that t(a)=o(\bar{a}) and o(a)=t(\bar{a}) hold. For a fixed vertex \xi_{j}\in V_{j} , we define \mathbb{e}_{*}=\{(\xi_{1},\xi_{2}),(\xi_{2},\xi_{1})\} . It is called the bridge between H_{1} and H_{2} . We set a graph G=(V,A) where V=V_{1}\cup V_{2},A=A_{1}\cup A_{2}\cup\mathbb{e_{*}} . Let \delta V=\{\xi_{1},\xi_{2}\}\subset V be the boundary vertex set. The weight function w:{A}\rightarrow[0,1] is defined by \displaystyle w(a)=\begin{cases}1&:a\notin\mathbb{e}_{*},\\ \epsilon&:a\in\mathbb{e}_{*}.\end{cases} (2.1) We set a function p_{\epsilon}:{A}\rightarrow[0,1] as p_{\epsilon}(a)=w(a)/m(o(a)) , where m(x)=\sum_{a:\,o(a)=x}w(a) . We should remark that p_{\epsilon}(a) is regarded as the probability of a random walker from a vertex o(a) to t(a) depending on the weight. Combining with a definition of p_{\epsilon} and Eq.( 2.1 ), it follows that \displaystyle p_{\epsilon}(a)=\begin{cases}1/\deg(o(a))&:o(a)\notin\delta V,\\ 1/(\deg(o(a))+\epsilon)&:o(a)\in\delta V,a\notin\mathbb{e}_{*},\\ \epsilon/(\deg(o(a))+\epsilon)&:a\in\mathbb{e}_{*}.\end{cases} The boundary matrix d_{\epsilon}:\mathbb{C}^{A}\rightarrow\mathbb{C}^{V} is defined by \displaystyle(d_{\epsilon})_{x,a}=\begin{cases}\sqrt{p_{\epsilon}(\bar{a})}&:t(a)=x,\\ 0&:otherwise.\end{cases} for any a\in A,x\in V . The shift matrix S:\mathbb{C}^{A}\rightarrow\mathbb{C}^{A} is defined by \displaystyle(S)_{b,a}=\delta_{a,\bar{b}}. Here, \delta_{x,y} is the Kronecker delta. The time evolution matrix U(\epsilon):\mathbb{C}^{A}\rightarrow\mathbb{C}^{A} is \displaystyle U(\epsilon)=S(2d_{\epsilon}^{*}d_{\epsilon}-I) Remark 2.1 . If \epsilon=0 , U(\epsilon) acts on each of the three divided graphs H_{1} , H_{2} and \{\mathbb{e}_{*}\} . While if \epsilon=1 , U(\epsilon) is regarded as Grover walks on G . This remark implies that the smaller \epsilon is, the weaker the connection of \mathbb{e}_{*} . In this paper, we focus on the case with sufficiently small \epsilon . Let us set the initial state \ket{\psi_{0}} as the uniform superposition on H_{1} , that is, \displaystyle\ket{\psi_{0}}=\frac{1}{\sqrt{|A_{1}|}}\sum_{a\in A_{1}}\ket{a}. (2.2) Let \mu_{t}(H_{j}) be the probability of the existence of a quantum walker on H_{j}\,(j=0,1,2) at time step t , denoted by \displaystyle\mu_{t}(H_{j})=\sum_{a\in A_{j}}\left|\bra{a}U(\epsilon)^{t}\ket{\psi_{0}}\right|^{2}. Here, we set H_{0}=(\delta V,\{\mathbb{e}_{*}\}) . We should remark that it follows that \displaystyle\mu_{t}(H_{0})=1-\mu_{t}(H_{1})-\mu_{t}(H_{2}). Thus, our main purpose is to estimate the asymptotic expression of \mu_{t}(H_{1}) and \mu_{t}(H_{2}) with respect to the parameter \epsilon\ll 1 , which is the strength of the connectivity between H_{1} and H_{2} . 3 Demonstration We are interested in what influences the behavior of \mu_{t}(H_{j})\;(j=1,2) , such as the structure of the graph and the number of vertices. Also, we want to

Read the complete text