Creating and sharing knowledge for telecommunications

Optimal Quantum Spatial Search on Random Temporal Networks

Chakraborty, S. ; Novo, L.N. ; Di Giorgio, S. ; Omar, Y.

Physical Review Letters Vol. 119, Nº NA, pp. 220503 - NA, November, 2017.

ISSN (print): 1079-7114
ISSN (online): 0031-9007

Scimago Journal Ranking: 3,62 (in 2017)

Digital Object Identifier: 10.1103/PhysRevLett.119.220503

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"os-R'enyi random graphs $G(n,p)$, where $p$ is the probability that any two given nodes are connected: after every time interval $ au$, 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 $ au$ 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 $ au$ 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.