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.

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

References in corpus (18)

• Statistical mechanics of complex networks
• Temporal Networks
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Spatial search by quantum walk
• The fundamental advantages of temporal networks
• Causality-Driven Slow-Down and Speed-Up of Diffusion in Non-Markovian Temporal Networks
• Spatial search by quantum walk is optimal for almost all graphs
• Noise resistance of adiabatic quantum computation using random matrix theory
• Global Symmetry is Unnecessary for Fast Quantum Search
• Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
• Connectivity is a Poor Indicator of Fast Quantum Search
• Asymptotic dynamics of coined quantum walks on percolation graphs
• Coined quantum walks on percolation graphs
• Degree Distribution in Quantum Walks on Complex Networks
• Quantum search on graphene lattices
• Community Detection in Quantum Complex Networks
• Continuous Time Quantum Walks in finite Dimensions
• Time evolution of continuous-time quantum walks on dynamical percolation graphs

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