Continuous-time quantum walk spatial search on the Bollobás scale-free network

Abstract

The scale-free property emerges in various real-world networks and is an essential property which characterizes the dynamics or features of such networks. In this work we investigate the effect of this scale-free property on a quantum information processing task of finding a marked node in the network, known as the quantum spatial search. We analyze the quantum spatial search algorithm using continuous-time quantum walk on the Bollobás network, and evaluate the time $T$ to localize the quantum walker on the marked node starting from an unbiased initial state. Our main finding is that $T$ is determined by the global structure around the marked node, while some local information of the marked node such as degree does not identify $T$. We discuss this by examining the correlation between $T$ and some centrality measures of the network, and show that the closeness centrality of the marked node is highly correlated with $T$. We also characterize the distribution of $T$ by marking different nodes in the network, which displays a multi-mode lognormal distribution. Especially on the Bollobás network, $T$ is magnitude of orders shorter depending whether the marked node is adjacent to the largest degree hub node or not. However, as $T$ depends on the property of the marked node, one requires some amount of prior knowledge about such property of the marked node in order to identify the optimal time to measure the quantum walker and achieve fast search. These results indicate that the existence of the hub node in the scale-free network is playing a crucial role on the quantum spatial search.

arXiv comment10 pages, 6 figures

References in corpus (32)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Epidemic processes in complex networks
• The spread of epidemic disease on networks
• Critical phenomena in complex networks
• Hierarchical Organization in Complex Networks
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Hyperbolic Geometry of Complex Networks
• Dynamics of Rumor Spreading in Complex Networks
• Many-body localization in a quantum simulator with programmable random disorder
• Biological network comparison using graphlet degree distribution
• Spatial search by quantum walk
• Origins of fractality in the growth of complex networks
• Operating Quantum States in Single Magnetic Molecules: Implementation of Grover's Quantum Algorithm
• Spectra and eigenvectors of scale-free networks
• Spatial search by quantum walk is optimal for almost all graphs
• Complex Networks from Classical to Quantum
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Enhancing quantum transport in a photonic network using controllable decoherence
• Interdisciplinary and physics challenges of Network Theory
• Quantum walk approach to search on fractal structures
• Global Symmetry is Unnecessary for Fast Quantum Search
• Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
• Quantum walk-based search and centrality
• Molecular quantum spin network controlled by a single qubit
• Perfect state transfer by means of discrete-time quantum walk search algorithms on highly symmetric graphs
• Spatial search by continuous-time quantum walks on crystal lattices
• Quantum search on graphene lattices
• Community Detection in Quantum Complex Networks
• Continuous-Time Quantum Search on Balanced Trees
• Vertices cannot be hidden from quantum spatial search for almost all random graphs
• Ergodic-localized junctions in periodically-driven systems

Cited by in corpus (11)

• Quadratic speedup for spatial search by continuous-time quantum walk
• Quantum spatial search in two-dimensional waveguide arrays
• Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk
• Ion Trap Long-Range XY Model for Quantum State Transfer and Optimal Spatial Search
• Quantum walk based state transfer algorithms on the complete M-partite graph
• Spatial search by continuous-time quantum walks on renormalized Internet networks
• Quantum search in many-body interacting system with long-range interaction
• Optimal quantum spatial search with one-dimensional long-range interactions
• Universal scaling hypothesis of quantum spatial search in complex networks
• Implementation of Continuous-Time Quantum Walks on Quantum Computers
• Application of graph theory in quantum computer science