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:1908.11827 · Physical Review A

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

Rei Sato, Tetsuro Nikuni, Shohei Watabe

Published Feb 10, 2020• 9 citations
arXivHTMLPDF

Abstract

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.
DOI
10.1103/physreva.101.022312

Related papers

Spatial Search on Sierpinski Carpet Using Quantum Walk

Shu Tamegai, Shohei Watabe, Tetsuro Nikuni

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.

arXiv:1804.06549•Journal of the Physical Society of Japan•Jul 23, 2018•6 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

Spatial search on a honeycomb network

Gonzalo Abal, R. DONANGELO, Franklin de Lima Marquezino +1 more

The spatial search problem consists of minimising the number of steps required to find a given site in a network under the restriction that only oracle queries or translations to neighbouring sites are allowed. We propose a quantum algorithm for the spatial search problem on a honeycomb lattice withNsites and torus-like boundary conditions. The search algorithm is based on a modified quantum walk on an hexagonal lattice and the general framework proposed by Ambainis, Kempe and Rivosh (Ambainiset al. 2005) is employed to show that the time complexity of this quantum search algorithm is $O(\sqrt{N \log N})$ .

arXiv:1001.1139•Mathematical Structures in Computer Science•Nov 8, 2010•44 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

Spatial search via non-linear quantum walk

Mahdi Ebrahimi Kahou

One approach to the development of quantum search algorithms is the quantum walk. A spatial search can be effected by the continuous-time evolution of a single quantum particle on a lattice or graph containing a marked site. In most conceivable physical applications, however, one would rather expect to have multiple interacting particles. In bosonic systems at zero temperature, the dynamics would be well-described by a discrete non-linear Schrodinger equation. In this thesis we investigate the role of non-linearity in determining the efficiency of the spatial search algorithm within the quantum walk model, for the complete graph. Our analytical results indicate that the search time for this non-linear quantum search scales with size of the database N like square root of N, equivalent to linear spatial search time. The analytical results will be compared with numerical calculations of multiple interacting quantum walkers.

•Jan 1, 2013•1 citation

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
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.
The spatial search problem consists of minimising the number of steps required to find a given site in a network under the restriction that only oracle queries or translations to neighbouring sites are allowed. We propose a quantum algorithm for the spatial search problem on a honeycomb lattice withNsites and torus-like boundary conditions. The search algorithm is based on a modified quantum walk on an hexagonal lattice and the general framework proposed by Ambainis, Kempe and Rivosh (Ambainiset al. 2005) is employed to show that the time complexity of this quantum search algorithm is O(Nlog⁡N)O(\sqrt{N \log N})O(NlogN​) .
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.
One approach to the development of quantum search algorithms is the quantum walk. A spatial search can be effected by the continuous-time evolution of a single quantum particle on a lattice or graph containing a marked site. In most conceivable physical applications, however, one would rather expect to have multiple interacting particles. In bosonic systems at zero temperature, the dynamics would be well-described by a discrete non-linear Schrodinger equation. In this thesis we investigate the role of non-linearity in determining the efficiency of the spatial search algorithm within the quantum walk model, for the complete graph. Our analytical results indicate that the search time for this non-linear quantum search scales with size of the database N like square root of N, equivalent to linear spatial search time. The analytical results will be compared with numerical calculations of multiple interacting quantum walkers.
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.