Optimal quantum spatial search on random temporal networks

Abstract

To investigate the performance of quantum information tasks on networks whose topology changes in time, we study the spatial search algorithm by continuous time quantum walk to find a marked node on a random temporal network. We consider a network of $n$ nodes constituted by a time-ordered sequence of Erdös-Rényi random graphs $G(n,p)$, where $p$ is the probability that any two given nodes are connected: after every time interval $\tau$, a new graph $G(n,p)$ replaces the previous one. We prove analytically that for any given $p$, there is always a range of values of $\tau$ for which the running time of the algorithm is optimal, i.e.\ $\mathcal{O}(\sqrt{n})$, even when search on the individual static graphs constituting the temporal network is sub-optimal. On the other hand, there are regimes of $\tau$ where the algorithm is sub-optimal even when each of the underlying static graphs are sufficiently connected to perform optimal search on them. From this first study of quantum spatial search on a time-dependent network, it emerges that the non-trivial interplay between temporality and connectivity is key to the algorithmic performance. Moreover, our work can be extended to establish high-fidelity qubit transfer between any two nodes of the network. Overall, our findings show that one can exploit temporality to achieve optimal quantum information tasks on dynamical random networks.

Published version. Keywords: temporal networks, random graphs, quantum spatial search, quantum walks, quantum state transfer

References in corpus (6)

• Spatial search by quantum walk
• Noise resistance of adiabatic quantum computation using random matrix theory
• Connectivity is a Poor Indicator of Fast Quantum Search
• Asymptotic dynamics of coined quantum walks on percolation graphs
• Coined quantum walks on percolation graphs
• Continuous Time Quantum Walks in finite Dimensions

Cited by in corpus (27)

• Complex Networks from Classical to Quantum
• Quadratic speedup for spatial search by continuous-time quantum walk
• Review on Quantum Walk Computing: Theory, Implementation, and Application
• On the optimality of spatial search by continuous-time quantum walk
• Complex Quantum Networks: a Topical Review
• Quantum spatial search on graphs subject to dynamical noise
• How fast do quantum walks mix?
• Finding a marked node on any graph by continuous-time quantum walk
• Continuous-Time Quantum Walks on Dynamic Graphs
• Analog quantum algorithms for the mixing of Markov chains
• Feedback-assisted quantum search by continuous-time quantum walks
• Environment-assisted analog quantum search
• Vertices cannot be hidden from quantum spatial search for almost all random graphs
• Quantum walks on random lattices: Diffusion, localization and the absence of parametric quantum speed-up
• Ion Trap Long-Range XY Model for Quantum State Transfer and Optimal Spatial Search
• Scattering as a quantum metrology problem: a quantum walk approach
• Simplifying Continuous-Time Quantum Walks on Dynamic Graphs
• Quantum-walk search in motion
• Quantum search in many-body interacting system with long-range interaction
• Robust Diabatic Quantum Search by Landau-Zener-Stückelberg Oscillations
• Non-Markovianity is not a resource for quantum spatial search on a star graph subject to generalized percolation
• Optimal spatial searches with long-range tunneling
• Quantum transport in randomized quantum graphs
• Impact of the malicious input data modification on the efficiency of quantum spatial search
• Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks
• Application of graph theory in quantum computer science
• Optimal quantum spatial search with one-dimensional long-range interactions