For classical random walks on networks, the flux-fluctuation relation is an important characteristic that relates the mean flux and strength of fluctuations on the nodes. It was extensively studied before, although equivalent relations for quantum walks on networks remain unknown. In this work, a quantum version of the flux-fluctuation relation is obtained. It is valid for quantum walks on an arbitrary network, subject to the condition that the spectrum of the unitary walk operator is nondegenerate. Remarkably, for phase coherent quantum walks, the quantum flux-fluctuation relation is qualitatively similar to its classical counterpart, and quantum effects are insignificant. We numerically simulate quantum walks on periodic lattices and scale-free and Erdős-Rényi networks, and the results are consistent with the analytical quantum flux-fluctuation relation. We discuss the implications for the quantum walk dynamics if the spectrum of the unitary walk operator violate the nondegeneracy condition.
For classical random walks on networks, the flux-fluctuation relation is an important characteristic that relates the mean flux and strength of fluctuations on the nodes. It was extensively studied before, although equivalent relations for quantum walks on networks remain unknown. In this work, a quantum version of the flux-fluctuation relation is obtained. It is valid for quantum walks on an arbitrary network, subject to the condition that the spectrum of the unitary walk operator is nondegenerate. Remarkably, for phase coherent quantum walks, the quantum flux-fluctuation relation is qualitatively similar to its classical counterpart, and quantum effects are insignificant. We numerically simulate quantum walks on periodic lattices and scale-free and Erdős-Rényi networks, and the results are consistent with the analytical quantum flux-fluctuation relation. We discuss the implications for the quantum walk dynamics if the spectrum of the unitary walk operator violate the nondegeneracy condition.
Due to the unitary evolution, quantum walks display different dynamical features from that of classical random walks. In contrast to this expectation, in this work, we show that extreme events can arise in unitary dynamics and its properties are qualitatively similar to that of random walks. We consider quantum walks on a ring lattice and a scale-free graph. Firstly, we obtain quantum version of flux-fluctuation relation and use this to define to extreme events on vertices of a graph as exceedences above the mean flux. The occurrence probability for extreme events on scale-free graphs displays a power-law with the degree of vertices, in qualitative agreement with corresponding classical random walk result. For both classical and quantum walks, the extreme event probability is larger for small degree nodes compared to hubs on the graph. Further, it is shown that extreme event probability scales with threshold used to define extreme events.
Based on studies of four specific networks, we conjecture a general relation between the walk dimensions dw of discrete-time random walks and quantum walks with the (self-inverse) Grover coin. In each case, we find that dw of the quantum walk takes on exactly half the value found for the classical random walk on the same geometry. Since walks on homogeneous lattices satisfy this relation trivially, our results for heterogeneous networks suggest that such a relation holds irrespective of whether translational invariance is maintained or not. To develop our results, we extend the renormalization-group analysis (RG) of the stochastic master equation to one with a unitary propagator. As in the classical case, the solution $\ensuremath{\rho}(x,t)$ in space and time of this quantum-walk equation exhibits a scaling collapse for a variable xdw/t in the weak limit, which defines dw and illuminates fundamental aspects of the walk dynamics, e.g., its mean-square displacement. We confirm the collapse for $\ensuremath{\rho}(x,t)$ in each case with extensive numerical simulation. The exact values for dw themselves demonstrate that RG is a powerful complementary approach to study the asymptotics of quantum walks that weak-limit theorems have not been able to access, such as for systems lacking translational symmetries beyond simple trees.
Extreme events are the ones for which the magnitude of the event is much larger than its typical values. They have been extensively investigated on classical dynamical and stochastic processes on networks. In this work, in analogy with well-studied extreme events of random walks, the extreme events of quantum walks on regular lattices, a scale-free network, and Erdős-Rényi network are studied. Due to unitary quantum evolution, the quantum walk dynamics usually differs from that of the classical random walks, and hence we expect extreme event properties to be different in classical and quantum settings. In contrast to this expectation, we report that extreme events of phase coherent quantum walks are qualitatively similar to that of classical random walks. We show that this counterintuitive behavior originates from the dominance of nodal fluctuations over internode correlations in disordered network structures. In particular, the occurrence probability for extreme events on scale-free and Erdős-Rényi networks displays a decaying power law with the degree of nodes. That is, the extreme event probability is larger for small degree nodes compared to the hubs on the network, in qualitative agreement with corresponding classical random walk results. Further, it is shown that extreme event probability scales with the threshold used to define extreme events.
Quantum walks on graphs are ubiquitous in quantum computing finding a myriad of applications. Likewise, random walks on graphs are a fundamental building block for a large number of algorithms with diverse applications. While the relationship between quantum and random walks has been recently discussed in specific scenarios, this work establishes a formal equivalence between the two processes on arbitrary finite graphs and general conditions for shift and coin operators. It requires empowering random walks with time heterogeneity, where the transition probability of the walker is non-uniform and time dependent. The equivalence is obtained by equating the probability of measuring the quantum walk on a given node of the graph and the probability that the random walk is at that same node, for all nodes and time steps. The first result establishes procedure for a stochastic matrix sequence to induce a random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. The second result establishes a similar procedure in the opposite direction. Given any random walk, a time-dependent quantum walk with the exact same vertex probability distribution is constructed. Interestingly, the matrices constructed by the first procedure allows for a different simulation approach for quantum walks where node samples respect neighbor locality and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial-time) sampling of quantum graph trajectories. Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case.
Some interesting findings can be achieved by modeling and visualizing networks which can include complex networks and large scale networks to name a few. These networks have been analyzed with the help of classical stochastic walks before. So, here in our proposed work, we provide the quantum version of the walk which basically involves making use of properties found in quantum computing. These properties can include such as quantum interference, no-cloning theorem, and restriction on intermediate measurement. In this proposed work, we present quantum circuit designs for discrete time random walk algorithms that operate on various networks.To demonstrate our ideas we have considered two different types of networks, the star network and an extended version of the star network.Though there exist a few research works related to quantum approach for random walk on networks, to the best of our knowledge, the ideas and approach we present here are unique. These ideas which we have discussed can be extended to more complex networks and systems as well. As an application of quantum walk we have shown, how results got after performing quantum walk can be used to identify critical nodes in such networks. Therefore, we have also provided some analysis of complex networks. Identification of critical nodes is important for robustness and survivability of the network.
Random walks are fundamental models of stochastic processes with applications in various fields, including physics, biology, and computer science. We study classical and quantum random walks under the influence of stochastic resetting on arbitrary networks. Based on the mathematical formalism of quantum stochastic walks, we provide a framework of classical and quantum walks whose evolution is determined by graph Laplacians. We study the influence of quantum effects on the stationary and long-time average probability distribution by interpolating between the classical and quantum regime. We compare our analytical results on stationary and long-time average probability distributions with numerical simulations on different networks, revealing differences in the way resets affect the sampling properties of classical and quantum walks.