Scaling hypothesis of a spatial search on fractal lattices using a quantum walk
- 10 February 2020
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 101 (2) , 022312
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 oracle calls, where the exponent is given by for and the inverse of the spectral dimension for . We also propose a scaling hypothesis for the effective number of 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.
Keywords
All Related Versions
Funding Information
- Japan Society for the Promotion of Science (JP18K03499, JP16K05504)
This publication has 30 references indexed in Scilit:
- Higher winding number in a nonunitary photonic quantum walkPhysical Review A, 2018
- Observation of topological edge states in parity–time-symmetric quantum walksNature Physics, 2017
- Spatial Search by Quantum Walk is Optimal for Almost all GraphsPhysical Review Letters, 2016
- A 2D Quantum Walk Simulation of Two-Particle DynamicsScience, 2012
- Realization of a Quantum Walk with One and Two Trapped IonsPhysical Review Letters, 2010
- Photons Walking the Line: A Quantum Walk with Adjustable Coin OperationsPhysical Review Letters, 2010
- Quantum Walk in Position Space with Single Optically Trapped AtomsScience, 2009
- Self-similarity of complex networksNature, 2005
- Quantum random-walk search algorithmPhysical Review A, 2003
- Quantum Mechanics Helps in Searching for a Needle in a HaystackPhysical Review Letters, 1997