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

Spatial search algorithms on Hanoi networks

Franklin de Lima Marquezino, Renato Portugal, Stefan Boettcher

Published Jan 28, 2013• 10 citations
arXivHTMLPDF

Abstract

We use the abstract search algorithm and its extension due to Tulsi to analyze a spatial quantum search algorithm that finds a marked vertex in Hanoi networks of degree 4 faster than classical algorithms. We also analyze the effect of using non-Groverian coins that take advantage of the small-world structure of the Hanoi networks. We obtain the scaling of the total cost of the algorithm as a function of the number of vertices. We show that Tulsi's technique plays an important role to speed up the searching algorithm. We can improve the algorithm's efficiency by choosing a non-Groverian coin if we do not implement Tulsi's method. Our conclusions are based on numerical implementations.

DOI
10.1103/physreva.87.012329

Related papers

Quantum search algorithms on hierarchical networks

Franklin de Lima Marquezino, Renato Portugal, Stefan Boettcher

The “abstract search algorithm” is a well known quantum method to find a marked vertex in a graph. It has been applied with success to searching algorithms for the hypercube and the two-dimensional grid. In this work we provide an example for which that method fails to provide the best algorithm in terms of time complexity. We analyze search algorithms in degree-3 hierarchical networks using quantum walks driven by non-groverian coins. Our conclusions are based on numerical simulations, but the hierarchical structures of the graphs seems to allow analytical results.

arXiv:1205.0529•IEEE Information Theory Workshop (ITW)•Oct 1, 2011•7 citations

Quantum search on Hanoi network

Pulak Ranjan Giri, V. E. Korepin

Hanoi network (HN) has a one-dimensional periodic lattice as its main structure with additional long-range edges, which allow having efficient quantum walk algorithm that can find a target state on the network faster than the exhaustive classical search. In this paper, we use regular quantum walks and lackadaisical quantum walks, respectively, to search for a target state. From the curve fitting of the numerical results for HN of degrees three and four, we find that their running time for the regular quantum walks are followed by amplitude amplification scales as [Formula: see text] and [Formula: see text], respectively. For the search by lackadaisical quantum walks, the running time scales are as [Formula: see text] and [Formula: see text], respectively.

arXiv:1903.08020•International Journal of Quantum Information•Oct 1, 2019•5 citations

Spatial quantum search in a triangular network

Gonzalo Abal, R. Donangelo, Marcelo Forets +1 more

The spatial search problem consists of minimising the number of steps required to find a given site in a network, with the restriction that only an oracle query or a translation to a neighbouring site is allowed at each step. We propose a quantum algorithm for the spatial search problem on a triangular lattice with N sites and torus-like boundary conditions. The proposed algorithm is a special case of the general framework for abstract search proposed by Ambainis, Kempe and Rivosh (AKR) in Ambainis et al. (2005) and Tulsi in Tulsi (2008) applied to a triangular network. The AKR–Tulsi formalism was employed to show that the time complexity of the quantum search on the triangular lattice is $O(\sqrt{N \log N})$ .

arXiv:1009.1422•Mathematical Structures in Computer Science•Feb 9, 2012•20 citations

Deterministic spatial search using alternating quantum walks

S. Marsh, Jingbo B. Wang

This paper examines the performance of spatial search where the Grover diffusion operator is replaced by continuous-time quantum walks on a class of interdependent networks. We prove that, for a set of optimal quantum walk times and marked vertex phase shifts, a deterministic algorithm for structured spatial search is established that finds the marked vertex with 100% probability. This improves on the Childs and Goldstone spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability. Our method uses $\ensuremath{\lceil}\frac{\ensuremath{\pi}}{2\sqrt{2}}\sqrt{N}\ensuremath{\rceil}$ marked vertex phase shifts for an $N$-vertex graph, making it comparable to Grover's algorithm for an unstructured search. It is expected that this framework can be readily extended to deterministic spatial search on other families of graph structures.

arXiv:2104.03806•Physical Review A•Aug 24, 2021•15 citations

Complexity bounds on quantum search algorithms in finite-dimensional networks

Stefan Boettcher, Shanshan Li, Tharso D. Fernandes +1 more

We establish a lower bound concerning the computational complexity of Grover's algorithms on fractal networks. This bound provides general predictions for the quantum advantage gained for searching unstructured lists. It yields a fundamental criterion, derived from quantum transport properties, for the improvement a quantum search algorithm achieves over the corresponding classical search in a network based solely on its spectral dimension, ${d}_{s}$. Our analysis employs recent advances in the interpretation of the venerable real-space renormalization group (RG) as applied to quantum walks. It clarifies the competition between Grover's abstract algorithm, i.e., a rotation in Hilbert space, and quantum transport in an actual geometry. The latter is characterized in terms of the quantum walk dimension ${d}_{w}^{Q}$ and the spatial (fractal) dimension ${d}_{f}$ that is summarized simply by the spectral dimension of the network. The analysis simultaneously determines the optimal time for a quantum measurement and the probability for successfully pinpointing a marked element in the network. The RG further encompasses an optimization scheme devised by Tulsi that allows us to tune this probability to certainty, leaving quantum transport as the only limiting process. It considers entire families of problems to be studied, thereby establishing large universality classes for quantum search, which we verify with extensive simulations. The methods we develop could point the way towards systematic studies of universality classes in computational complexity to enable modification and control of search behavior.

arXiv:1708.05339•Physical Review A•Jul 17, 2018•7 citations

Spatial search on Johnson graphs by discrete-time quantum walk

Hajime Tanaka, Mohamed Sabri, Renato Portugal

Abstract The spatial search problem aims to find a marked vertex of a finite graph using a dynamic with two constraints: (1) the walker has no compass and (2) the walker can check whether a vertex is marked only after reaching it. This problem is a generalization of unsorted database search and has many applications to algorithms. Classical algorithms that solve the spatial search problem are based on random walks and the computational complexity is determined by the hitting time. On the other hand, quantum algorithms are based on quantum walks and the computational complexity is determined not only by the number of steps to reach a marked vertex, but also by the success probability, since we need to perform a measurement at the end of the algorithm to determine the walker’s position. In this work, we address the spatial search problem on Johnson graphs using the coined quantum walk model. Since Johnson graphs are vertex- and distance-transitive, we have found an invariant subspace of the Hilbert space, which aids in the calculation of the computational complexity. We have shown that, for every fixed diameter, the asymptotic success probability is 1/2 after taking π N / ( 2 2 ) steps, where N is the number of vertices of the Johnson graph.

arXiv:2112.03744•Journal of Physics A Mathematical and Theoretical•May 12, 2022•9 citations
We use the abstract search algorithm and its extension due to Tulsi to analyze a spatial quantum search algorithm that finds a marked vertex in Hanoi networks of degree 4 faster than classical algorithms. We also analyze the effect of using non-Groverian coins that take advantage of the small-world structure of the Hanoi networks. We obtain the scaling of the total cost of the algorithm as a function of the number of vertices. We show that Tulsi's technique plays an important role to speed up the searching algorithm. We can improve the algorithm's efficiency by choosing a non-Groverian coin if we do not implement Tulsi's method. Our conclusions are based on numerical implementations.
The “abstract search algorithm” is a well known quantum method to find a marked vertex in a graph. It has been applied with success to searching algorithms for the hypercube and the two-dimensional grid. In this work we provide an example for which that method fails to provide the best algorithm in terms of time complexity. We analyze search algorithms in degree-3 hierarchical networks using quantum walks driven by non-groverian coins. Our conclusions are based on numerical simulations, but the hierarchical structures of the graphs seems to allow analytical results.
Hanoi network (HN) has a one-dimensional periodic lattice as its main structure with additional long-range edges, which allow having efficient quantum walk algorithm that can find a target state on the network faster than the exhaustive classical search. In this paper, we use regular quantum walks and lackadaisical quantum walks, respectively, to search for a target state. From the curve fitting of the numerical results for HN of degrees three and four, we find that their running time for the regular quantum walks are followed by amplitude amplification scales as [Formula: see text] and [Formula: see text], respectively. For the search by lackadaisical quantum walks, the running time scales are as [Formula: see text] and [Formula: see text], respectively.
The spatial search problem consists of minimising the number of steps required to find a given site in a network, with the restriction that only an oracle query or a translation to a neighbouring site is allowed at each step. We propose a quantum algorithm for the spatial search problem on a triangular lattice with N sites and torus-like boundary conditions. The proposed algorithm is a special case of the general framework for abstract search proposed by Ambainis, Kempe and Rivosh (AKR) in Ambainis et al. (2005) and Tulsi in Tulsi (2008) applied to a triangular network. The AKR–Tulsi formalism was employed to show that the time complexity of the quantum search on the triangular lattice is O(Nlog⁡N)O(\sqrt{N \log N})O(NlogN​) .
This paper examines the performance of spatial search where the Grover diffusion operator is replaced by continuous-time quantum walks on a class of interdependent networks. We prove that, for a set of optimal quantum walk times and marked vertex phase shifts, a deterministic algorithm for structured spatial search is established that finds the marked vertex with 100% probability. This improves on the Childs and Goldstone spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability. Our method uses $\ensuremath{\lceil}\frac{\ensuremath{\pi}}{2\sqrt{2}}\sqrt{N}\ensuremath{\rceil}$ marked vertex phase shifts for an NNN-vertex graph, making it comparable to Grover's algorithm for an unstructured search. It is expected that this framework can be readily extended to deterministic spatial search on other families of graph structures.
We establish a lower bound concerning the computational complexity of Grover's algorithms on fractal networks. This bound provides general predictions for the quantum advantage gained for searching unstructured lists. It yields a fundamental criterion, derived from quantum transport properties, for the improvement a quantum search algorithm achieves over the corresponding classical search in a network based solely on its spectral dimension, ds{d}_{s}ds​. Our analysis employs recent advances in the interpretation of the venerable real-space renormalization group (RG) as applied to quantum walks. It clarifies the competition between Grover's abstract algorithm, i.e., a rotation in Hilbert space, and quantum transport in an actual geometry. The latter is characterized in terms of the quantum walk dimension dwQ{d}_{w}^{Q}dwQ​ and the spatial (fractal) dimension df{d}_{f}df​ that is summarized simply by the spectral dimension of the network. The analysis simultaneously determines the optimal time for a quantum measurement and the probability for successfully pinpointing a marked element in the network. The RG further encompasses an optimization scheme devised by Tulsi that allows us to tune this probability to certainty, leaving quantum transport as the only limiting process. It considers entire families of problems to be studied, thereby establishing large universality classes for quantum search, which we verify with extensive simulations. The methods we develop could point the way towards systematic studies of universality classes in computational complexity to enable modification and control of search behavior.
Abstract The spatial search problem aims to find a marked vertex of a finite graph using a dynamic with two constraints: (1) the walker has no compass and (2) the walker can check whether a vertex is marked only after reaching it. This problem is a generalization of unsorted database search and has many applications to algorithms. Classical algorithms that solve the spatial search problem are based on random walks and the computational complexity is determined by the hitting time. On the other hand, quantum algorithms are based on quantum walks and the computational complexity is determined not only by the number of steps to reach a marked vertex, but also by the success probability, since we need to perform a measurement at the end of the algorithm to determine the walker’s position. In this work, we address the spatial search problem on Johnson graphs using the coined quantum walk model. Since Johnson graphs are vertex- and distance-transitive, we have found an invariant subspace of the Hilbert space, which aids in the calculation of the computational complexity. We have shown that, for every fixed diameter, the asymptotic success probability is 1/2 after taking π N / ( 2 2 ) steps, where N is the number of vertices of the Johnson graph.