Scaling Hypothesis of Spatial Search on Fractal Lattice Using Quantum Walk

Abstract

We investigate a quantum spatial search problem on fractal lattices, such as Sierpinski carpets and Menger sponges. In earlier numerical studies of the Sierpinski gasket, the Sierpinski tetrahedron, and the Sierpinski carpet, conjectures have been proposed for the scaling of a quantum spatial search problem finding a specific target, which is given in terms of the characteristic quantities of a fractal geometry. We find that our simulation results for extended Sierpinski carpets and Menger sponges support the conjecture for the $optimal$ number of the oracle calls, where the exponent is given by $1/2$ for $d_{\mathrm{s}}>2$ and the inverse of the spectral dimension $d_{\mathrm{s}}$ for $d_{\mathrm{s}}<2$. We also propose a scaling hypothesis for the $effective$ number of the oracle calls defined by the ratio of the $optimal$ number of oracle calls to a square root of the maximum finding probability. The form of the scaling hypothesis for extended Sierpinski carpets is very similar but slightly different from the earlier conjecture for the Sierpinski gasket, the Sierpinski tetrahedron, and the conventional Sierpinski carpet.

arXiv comment7 pages, 7 figures

References in corpus (24)

• Quantum Mechanics helps in searching for a needle in a haystack
• Self-similarity of complex networks
• A quantum gas microscope - detecting single atoms in a Hubbard regime optical lattice
• A Quantum Random Walk Search Algorithm
• Spatial search by quantum walk
• Single-Spin Addressing in an Atomic Mott Insulator
• Quantum Walk in Position Space with Single Optically Trapped Atoms
• Photons Walking the Line: A quantum walk with adjustable coin operations
• Realization of a quantum walk with one and two trapped ions
• A 2D Quantum Walk Simulation of Two-Particle Dynamics
• Design and characterization of electronic fractals
• Faster quantum walk algorithm for the two dimensional spatial search
• Spatial search by quantum walk is optimal for almost all graphs
• Spatial search and the Dirac equation
• Quantum walk approach to search on fractal structures
• Higher winding number in a non-unitary photonic quantum walk
• From Schrödinger's Equation to the Quantum Search Algorithm
• Search on a Hypercubic Lattice using a Quantum Random Walk: I. d>2
• Search on a Fractal Lattice using a Quantum Random Walk
• Quantum walks and quantum search on graphene lattices
• Search on a Hypercubic Lattice through a Quantum Random Walk: II. d=2
• Analysis of Coined Quantum Walks with Renormalization
• Complexity Bounds on Quantum Search Algorithms in finite-dimensional Networks
• Spatial Search on Sierpinski Carpet Using Quantum Walk

Cited by in corpus (6)

• Complex Quantum Networks: a Topical Review
• Ion Trap Long-Range XY Model for Quantum State Transfer and Optimal Spatial Search
• Optimal spatial searches with long-range tunneling
• Quantum walks with spatiotemporal fractal disorder
• Universal scaling hypothesis of quantum spatial search in complex networks
• Optimal quantum spatial search with one-dimensional long-range interactions