  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 $\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.
