Scaling hypothesis of a spatial search on fractal lattices using a quantum walk

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 $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 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.

Figure 1

Menger sponges $\mathrm{MS}(3,1)$ at stages $S=1$ and 2, where the scaling factor is $s=3$.

Figure 2

Return probability of a classical random walker on fractal lattices: (a) Sierpinski carpets and (b) Menger sponges. (a) For Sierpinski carpets, we used a fixed boundary condition, and evaluated the spectral dimension $d_{\mathrm{s}}$ from data at stage $S=8$ for $\mathrm{SC}(4,2)$, at $S=7$ for $\mathrm{SC}(5,3)$, and at $S=6$ for $\mathrm{SC}(6,4)$. (b) For Menger sponges we employed a periodic boundary condition and evaluated the spectral dimension $d_{\mathrm{s}}$ from data at $S=5$ for $\mathrm{MS}(3,1)$ and at $S=4$ for $\mathrm{MS}(4,2),\mathrm{MS}(5,3)$, and $\mathrm{MS}(6,4)$.

Figure 3

Sierpinski carpet $\mathrm{SC}(3,1)$ at stages $S=1$ and 2. A red vertex pointed by an arrow at each stage represents a target site ${\mathbf{x}}_0$ for the spatial search.

Figure 4

Probability distribution of quantum spatial search on Sierpinski carpet $\mathrm{SC}(3,1)$ at the stage $S=3$. The probability becomes highest at the marked vertex when the time step reaches half the optimal number of the oracle calls, $Q/2\simeq 47$.

Figure 5

Spatial search on extended Sierpinski carpets. (a) Time dependence of the probability at a marked site, $P({\mathbf{x}}_0,t)$, at the stage $S=2$. (b) Site-number dependence of the optimal number of an oracle call $Q$ with a fitting $Q=O\left(N^{\beta }\right)$. The fitting is performed in data from $S=1$–5 for $\mathrm{SC}(4,2)$ and from $S=1$–4 for $\mathrm{SC}(5,3)$ and $\mathrm{SC}(6,4)$. (c) Site-number dependence of the mean value of the maximum probability at a marked vertex $P_{\max }$ with a fitting $P_{\max }=O\left(N^{-\alpha }\right)$. The fitting is performed in data from $S=3$–5 for $\mathrm{SC}(4,2)$ and $\mathrm{SC}(5,3)$, and from $S=2$–4 for $\mathrm{SC}(6,4)$. In this simulation, we employed the periodic boundary condition.

Figure 6

Spatial search on conventional and extended Menger sponges. (a) Time dependence of the probability at a marked site, $P({\mathbf{x}}_0,t)$, at stage $S=2$. (b) Site-number dependence of the optimal number of an oracle call $Q$ with a fitting $Q=O\left(N^{\beta }\right)$. The fitting is performed in data from $S=1$–5 for $\mathrm{MS}(3,1)$, from $S=1$–4 for $\mathrm{MS}(4,2)$, and from $S=1$–3 for $\mathrm{MS}(5,3)$ and $\mathrm{MS}(6,4)$. (c) Site-number dependence of the mean value of the maximum probability at a marked vertex $P_{\max }$, with a fitting $P_{\max }=O\left(N^{-\alpha }\right)$. The fitting is performed in data from $S=3$–5 for $\mathrm{MS}(3,1)$, from $S=2$–4 for $\mathrm{MS}(4,2)$, and from $S=2$–3 for $\mathrm{MS}(5,3)$ and $\mathrm{MS}(6,4)$. In this simulation we employed the periodic boundary condition.

Figure 7

Spectral dimension dependence of scaling exponents $\beta$, defined by $Q=O\left(N^{\beta }\right)$. This figure includes our numerical data obtained from Figs. 5 and 6 for the Sierpinski carpet (SC) and the Menger sponge (MS), respectively. It also includes the data of the Sierpinski carpet (SC), Sierpinski gasket (SG), and Sierpinski tetrahedron (ST) reported in Refs. [22, 27] for noninteger dimensions as well as the data of hypercubic lattices (Lattice) in Refs. [13, 14, 15, 16, 17] for integer dimensions. The exponent follows the relation $\beta =1/d_{\mathrm{s}}$ for $d_{\mathrm{s}}<2$ and saturates at $\beta =1/2$ for $d_{\mathrm{s}}>2$. For the spectral dimension close to the critical dimension $d_{\mathrm{s}}\simeq 2$, the exponent $\beta$ does not follow the relation $\beta =1/d_{\mathrm{s}}=1/2$, which may suggest the necessity of the logarithmic correction.