Search on a Fractal Lattice using a Quantum Random Walk

Abstract

The spatial search problem on regular lattice structures in integer number of dimensions $d\ge 2$ has been studied extensively, using both coined and coinless quantum walks. The relativistic Dirac operator has been a crucial ingredient in these studies. Here we investigate the spatial search problem on fractals of non-integer dimensions. Although the Dirac operator cannot be defined on a fractal, we construct the quantum walk on a fractal using the flip-flop operator that incorporates a Klein-Gordon mode. We find that the scaling behavior of the spatial search is determined by the spectral (and not the fractal) dimension. Our numerical results have been obtained on the well-known Sierpinski gaskets in two and three dimensions.

Revtex4, 9 pages, 11 figures (v2) Added: Relation of flip-flop walk to Klein-Gordon equation, Effect of non-translational invariance of fractals on spatial search

References in corpus (2)

• Faster quantum walk algorithm for the two dimensional spatial search
• Search on a Hypercubic Lattice through a Quantum Random Walk: II. d=2

Cited by in corpus (20)

• Propagation and spectral properties of quantum walks in electric fields
• Bulk-edge correspondence of one-dimensional quantum walks
• Transport properties of continuous-time quantum walks on Sierpinski fractals
• Complex Quantum Networks: a Topical Review
• Quantum walks and quantum search on graphene lattices
• Revivals in Quantum Walks with quasi-periodically time-dependent coin
• Spatial Search Algorithms on Hanoi Networks
• Scaling Hypothesis of Spatial Search on Fractal Lattice Using Quantum Walk
• Non-Markovian quantum interference in multilevel quantum systems: Exact master equation approach
• Spatial Search on Graphs with Multiple Targets using Flip-flop Quantum Walk
• Quantum Walks on Sierpinski Gaskets
• Complexity Bounds on Quantum Search Algorithms in finite-dimensional Networks
• Spatial Search on Sierpinski Carpet Using Quantum Walk
• Optimizing the walk coin in the quantum random walk search algorithm through machine learning
• Quantum search on Hanoi network
• Optimal spatial searches with long-range tunneling
• Quantum walks with spatiotemporal fractal disorder
• Quantum Ultra-Walks: Walks on a Line with Hierarchical Spatial Heterogeneity
• The localization of quantum random walks on sierpinski gaskets
• Universal scaling hypothesis of quantum spatial search in complex networks