Optimal Quantum Spatial Search on Random Temporal Networks
- 28 November 2017
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 119 (22) , 220503
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 nodes constituted by a time-ordered sequence of Erdös-Rényi random graphs , where is the probability that any two given nodes are connected: After every time interval , a new graph replaces the previous one. We prove analytically that, for any given , there is always a range of values of for which the running time of the algorithm is optimal, i.e., , even when search on the individual static graphs constituting the temporal network is suboptimal. On the other hand, there are regimes of where the algorithm is suboptimal 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 nontrivial 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.
Keywords
All Related Versions
Funding Information
- Fundação para a Ciência e a Tecnologia (UID/EEA/50008/2013, SFRH/BD/52246/2013, SFRH/BD/52241/2013, PD/BD/114332/2016)
- Seventh Framework Programme (GA 323901)
- John Templeton Foundation (ID 60478)
- DP-PMI
This publication has 22 references indexed in Scilit:
- Degree Distribution in Quantum Walks on Complex NetworksPhysical Review X, 2013
- Time evolution of continuous-time quantum walks on dynamical percolation graphsJournal of Physics A: Mathematical and Theoretical, 2013
- Temporal networksPhysics Reports, 2012
- Coined quantum walks on percolation graphsNew Journal of Physics, 2010
- Community Structure in Time-Dependent, Multiscale, and Multiplex NetworksScience, 2010
- Wave Communication across Regular LatticesPhysical Review Letters, 2009
- Noise resistance of adiabatic quantum computation using random matrix theoryPhysical Review A, 2005
- Spatial search by quantum walkPhysical Review A, 2004
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- Analog analogue of a digital quantum computationPhysical Review A, 1998