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

Search on a fractal lattice using a quantum random walk

Apoorva D. Patel, K. S. Raghunathan

Published Jul 27, 2012• 31 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.86.012332

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

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

QUANTUM RANDOM WALK ON FRACTALS

Kai Zhao

Quantum walks are the quantum mechanical analogue of classical random walks. Discrete-time quantum walks have been introduced and studied mostly on the line Z or higher dimensional space Z d but rarely defined on graphs with fractal dimensions because the coin operator depends on the position and the Fourier transform on the fractals is not defined. Inspired by its nature of classical walks, different quantum walks will be defined by choosing different shift and coin operators. When the coin operator is uniform, the results of classical walks will be obtained upon measurement at each step. Moreover, with measurement at each step, our results reveal more information about the classical random walks. In this dissertation, two graphs with fractal dimensions will be considered. The first one is Sierpinski gasket, a degree-4 regular graph with Hausdorff di- mension of df = ln 3/ ln 2. The second is the Cantor graph derived like Cantor set, with Hausdorff dimension of df = ln 2/ ln 3. The definitions and amplitude functions of the quantum walks will be introduced. The main part of this dissertation is to derive a recursive formula to compute the amplitude Green function. The exiting probability will be computed and compared with the classical results. When the generation of graphs goes to infinity, the recursion of the walks will be investigated and the convergence rates will be obtained and compared with the classical counterparts.

•Jan 1, 2018•0 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

Search on a Hypercubic Lattice using Quantum Random Walk

Apoorva Patel, Md. Aminoor Rahaman

We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized according to the staggered lattice fermion formalism. d=2 is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behavior. As a result, the construction used in our accompanying article [ A. Patel and M. A. Rahaman Phys. Rev. A 82 032330 (2010)] provides an O(√NlnN) algorithm, which is not optimal. The scaling behavior can be improved to O(√NlnN) by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi Phys. Rev. A 78 012310 (2008). We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.

•Jun 5, 2009•2 citations

Spatial search using flip-flop quantum walk

Abhijith Jayakumar, Apoorva D. Patel

We analyse the eigenvalue and eigenvector structure of the flip-flop quantum walk on regular graphs, explicitly demonstrating how it is quadratically faster than the classical random walk. Then we use it in a controlled spatial search algorithm with multiple target states, and determine the oracle complexity as a function of the spectral gap and the number of target states. The oracle complexity is optimal as a function of the graph size and the number of target states, when the spectral gap of the adjacency matrix is $\Theta(1)$. It is also optimal for spatial search on D>4 dimensional hypercubic lattices. Otherwise it matches the best result available in the literature, with a much simpler algorithm. Our results also yield bounds on the classical hitting time of random walks on regular graphs, which may be of independent interest.

Quantum Information and Computation•Dec 1, 2018•9 citations
The spatial search problem on regular lattice structures in integer number of dimensions d\ensuremath≥2d\ensuremath{\ge}2d\ensuremath≥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.
Quantum walks are the quantum mechanical analogue of classical random walks. Discrete-time quantum walks have been introduced and studied mostly on the line Z or higher dimensional space Z d but rarely defined on graphs with fractal dimensions because the coin operator depends on the position and the Fourier transform on the fractals is not defined. Inspired by its nature of classical walks, different quantum walks will be defined by choosing different shift and coin operators. When the coin operator is uniform, the results of classical walks will be obtained upon measurement at each step. Moreover, with measurement at each step, our results reveal more information about the classical random walks. In this dissertation, two graphs with fractal dimensions will be considered. The first one is Sierpinski gasket, a degree-4 regular graph with Hausdorff di- mension of df = ln 3/ ln 2. The second is the Cantor graph derived like Cantor set, with Hausdorff dimension of df = ln 2/ ln 3. The definitions and amplitude functions of the quantum walks will be introduced. The main part of this dissertation is to derive a recursive formula to compute the amplitude Green function. The exiting probability will be computed and compared with the classical results. When the generation of graphs goes to infinity, the recursion of the walks will be investigated and the convergence rates will be obtained and compared with the classical counterparts.
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.
We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized according to the staggered lattice fermion formalism. d=2 is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behavior. As a result, the construction used in our accompanying article [ A. Patel and M. A. Rahaman Phys. Rev. A 82 032330 (2010)] provides an O(√NlnN) algorithm, which is not optimal. The scaling behavior can be improved to O(√NlnN) by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi Phys. Rev. A 78 012310 (2008). We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.
We analyse the eigenvalue and eigenvector structure of the flip-flop quantum walk on regular graphs, explicitly demonstrating how it is quadratically faster than the classical random walk. Then we use it in a controlled spatial search algorithm with multiple target states, and determine the oracle complexity as a function of the spectral gap and the number of target states. The oracle complexity is optimal as a function of the graph size and the number of target states, when the spectral gap of the adjacency matrix is Θ(1)\Theta(1)Θ(1). It is also optimal for spatial search on D>4 dimensional hypercubic lattices. Otherwise it matches the best result available in the literature, with a much simpler algorithm. Our results also yield bounds on the classical hitting time of random walks on regular graphs, which may be of independent interest.