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•7 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•33 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•46 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•23 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

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
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​) .
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.
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.