Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1804.06549 · Journal of the Physical Society of Japan

Spatial Search on Sierpinski Carpet Using Quantum Walk

Shu Tamegai, Shohei Watabe, Tetsuro Nikuni

Published Jul 23, 2018• 6 citations
arXivHTMLPDF

Abstract

We investigate a quantum spatial search problem on a fractal lattice. A recent study for the Sierpinski gasket and tetrahedron made a conjecture that the dynamics of the search on a fractal lattice is determined by spectral dimension. We tackle this problem for the Sierpinski carpet, and our simulation result supports the conjecture. We also propose a scaling hypothesis of oracle calls for the quantum amplitude amplification.

DOI
10.7566/jpsj.87.085003

Related papers

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

Rei Sato, Tetsuro Nikuni, Shohei Watabe

A quantum spatial search problem on fractal lattices, such as Sierpinski carpets and Menger sponges, is studied numerically. The results confirmed various conjectures on the relationship between the number of oracle calls needed for a search with respect to the number of sites and spatial dimensions.

arXiv:1908.11827•Physical Review A•Feb 10, 2020•9 citations

Search on a fractal lattice using a quantum random walk

Apoorva D. Patel, K. S. Raghunathan

The spatial search problem on regular lattice structures in integer number of dimensions $d\ensuremath{\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 noninteger 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.

arXiv:1203.3950•Physical Review A•Jul 27, 2012•31 citations

Quantum critical behavior of the quantum Ising model on fractal lattices

Hangmo Yi

I study the properties of the quantum critical point of the transverse-field quantum Ising model on various fractal lattices such as the Sierpiński carpet, Sierpiński gasket, and Sierpiński tetrahedron. Using a continuous-time quantum Monte Carlo simulation method and finite-size scaling analysis, I identify the quantum critical point and investigate its scaling properties. Among others, I calculate the dynamic critical exponent and find that it is greater than one for all three structures. The fact that it deviates from one is a direct consequence of the fractal structures not being integer-dimensional regular lattices. Other critical exponents are also calculated. The exponents are different from those of the classical critical point and satisfy the quantum scaling relation, thus confirming that I have indeed found the quantum critical point. I find that the Sierpiński tetrahedron, of which the dimension is exactly 2, belongs to a different universality class than that of the two-dimensional square lattice. I conclude that the critical exponents depend on more details of the structure than just the dimension and the symmetry.

arXiv:1408.5595•Physical Review E•Jan 9, 2015•9 citations

Renormalization group for a continuous-time quantum search in finite dimensions

Shanshan Li, Stefan Boettcher

We consider the quantum search problem with a continuous-time quantum walk for networks characterized by a finite spectral dimension ${d}_{s}$ of the network Laplacian. For general networks of fractal (integer or noninteger) dimension ${d}_{f}$, for which in general ${d}_{f}\ensuremath{\ne}{d}_{s}$, it suggests that it is ${d}_{s}$ that determines the computational complexity of the quantum search. Our results continue those of A. M. Childs and J. Goldstone [Phys. Rev. A 70, 022314 (2004)] for lattices of integer dimension, where $d={d}_{f}={d}_{s}$. Thus, we find for general fractals that the Grover limit of quantum search can be obtained whenever ${d}_{s}>4$. This complements the recent discussion of mean-field (i.e., ${d}_{s}\ensuremath{\rightarrow}\ensuremath{\infty}$) networks by S. Chakraborty et al. [Phys. Rev. Lett. 116, 100501 (2016)] showing that for all those networks, spatial search by quantum walk is optimal.

arXiv:1607.05317•Physical Review A•Mar 2, 2017•21 citations

Improving quantum spatial search in two dimensions

Abhijith Jayakumar, Apoorva D. Patel

The question of whether quantum spatial search in two dimensions can be made optimal has long been an open problem. We report progress towards its resolution by showing that the oracle complexity for target location can be made optimal, by increasing the number of calls to the walk operator that incorporates the graph structure by a logarithmic factor. Our algorithm does not require amplitude amplification. An important ingredient of our algorithm is the implementation of multi-step quantum walks by graph powering, using a coin space of walk-length dependent dimension, which may be of independent interest. Finally, we demonstrate how to implement quantum walks arising from powers of symmetric Markov chains using our methods.

Quantum Information and Computation•Jun 1, 2019•0 citations

Quantum walker trapped by self-similarity of the Sierpiński carpet

Tomasz Sowiński

We study the dynamics of a single quantum particle on a finite-size square lattice with a fractal structure resembling the Sierpiński carpet, and compare it to the dynamics on a uniform lattice of the same size. For a particle initially localized at a corner of the lattice, we monitor the probability of finding it near the initial and opposite corners using zone-integrated probabilities, allowing a consistent comparison across fractal orders. While on the uniform lattice the particle reaches the opposite corner ballistically, in a time proportional to the lattice size, on the Sierpiński lattice it becomes increasingly confined to the vicinity of its initial position. We show that this trapping builds up self-similarly across the whole hierarchy of corner zones of the lattice.

quant-pharXiv:2608.04844•Aug 6, 2026•0 citations
We investigate a quantum spatial search problem on a fractal lattice. A recent study for the Sierpinski gasket and tetrahedron made a conjecture that the dynamics of the search on a fractal lattice is determined by spectral dimension. We tackle this problem for the Sierpinski carpet, and our simulation result supports the conjecture. We also propose a scaling hypothesis of oracle calls for the quantum amplitude amplification.
The spatial search problem on regular lattice structures in integer number of dimensions $d\ensuremath{\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 noninteger 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.
I study the properties of the quantum critical point of the transverse-field quantum Ising model on various fractal lattices such as the Sierpiński carpet, Sierpiński gasket, and Sierpiński tetrahedron. Using a continuous-time quantum Monte Carlo simulation method and finite-size scaling analysis, I identify the quantum critical point and investigate its scaling properties. Among others, I calculate the dynamic critical exponent and find that it is greater than one for all three structures. The fact that it deviates from one is a direct consequence of the fractal structures not being integer-dimensional regular lattices. Other critical exponents are also calculated. The exponents are different from those of the classical critical point and satisfy the quantum scaling relation, thus confirming that I have indeed found the quantum critical point. I find that the Sierpiński tetrahedron, of which the dimension is exactly 2, belongs to a different universality class than that of the two-dimensional square lattice. I conclude that the critical exponents depend on more details of the structure than just the dimension and the symmetry.
We consider the quantum search problem with a continuous-time quantum walk for networks characterized by a finite spectral dimension ds{d}_{s}ds​ of the network Laplacian. For general networks of fractal (integer or noninteger) dimension df{d}_{f}df​, for which in general ${d}_{f}\ensuremath{\ne}{d}_{s}$, it suggests that it is ds{d}_{s}ds​ that determines the computational complexity of the quantum search. Our results continue those of A. M. Childs and J. Goldstone [Phys. Rev. A 70, 022314 (2004)] for lattices of integer dimension, where d=df=dsd={d}_{f}={d}_{s}d=df​=ds​. Thus, we find for general fractals that the Grover limit of quantum search can be obtained whenever ds>4{d}_{s}>4ds​>4. This complements the recent discussion of mean-field (i.e., ${d}_{s}\ensuremath{\rightarrow}\ensuremath{\infty}$) networks by S. Chakraborty et al. [Phys. Rev. Lett. 116, 100501 (2016)] showing that for all those networks, spatial search by quantum walk is optimal.
The question of whether quantum spatial search in two dimensions can be made optimal has long been an open problem. We report progress towards its resolution by showing that the oracle complexity for target location can be made optimal, by increasing the number of calls to the walk operator that incorporates the graph structure by a logarithmic factor. Our algorithm does not require amplitude amplification. An important ingredient of our algorithm is the implementation of multi-step quantum walks by graph powering, using a coin space of walk-length dependent dimension, which may be of independent interest. Finally, we demonstrate how to implement quantum walks arising from powers of symmetric Markov chains using our methods.
We study the dynamics of a single quantum particle on a finite-size square lattice with a fractal structure resembling the Sierpiński carpet, and compare it to the dynamics on a uniform lattice of the same size. For a particle initially localized at a corner of the lattice, we monitor the probability of finding it near the initial and opposite corners using zone-integrated probabilities, allowing a consistent comparison across fractal orders. While on the uniform lattice the particle reaches the opposite corner ballistically, in a time proportional to the lattice size, on the Sierpiński lattice it becomes increasingly confined to the vicinity of its initial position. We show that this trapping builds up self-similarly across the whole hierarchy of corner zones of the lattice.