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

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

Shanshan Li, Stefan Boettcher

Published Mar 2, 2017• 21 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.95.032301

Related papers

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

Quantum Search on Networks

Stefan Boettcher

Abstract We find a lower bound on the computational complexity of Grover’s quantum search algorithms in low-dimensional networks using the renormalization group (RG). It highlights the competition between Grover’s abstract algorithm, i.e., a rotation in Hilbert space, and quantum transport in an actual geometry. It can be characterized in terms of the quantum walk dimension <?CDATA ${d}_{w}^{Q}$?> d w Q and the spatial (fractal) dimension df or, alternatively, the spectral dimension of the network, ds , even when translational invariance is broken.

Journal of Physics Conference Series•Jun 1, 2019•0 citations

Spatial search by continuous-time quantum walks on renormalized Internet networks

Joonas Malmi, Matteo A. C. Rossi, Guillermo García-Pérez +1 more

We study spatial search with continuous-time quantum walks on real-world complex networks. We use smaller replicas of the Internet network obtained with a recent geometric renormalization method introduced by Garc\'{\i}a-P\'erez et al., Nat. Phys. 14, 583 (2018). This allows us to infer for the first time the behavior of a quantum spatial search algorithm on a real-world complex network. By simulating numerically the dynamics and optimizing the coupling parameter, we study the optimality of the algorithm and its scaling with the size of the network, showing that on average it is considerably better than the classical scaling $\mathcal{O}(N)$, but it does not reach the ideal quadratic speedup $\mathcal{O}(\sqrt{N})$ that can be achieved, e.g. in complete graphs. However, the performance of the search algorithm strongly depends on the degree of the nodes and, in fact, the scaling is found to be very close to optimal when we consider the nodes below the $99\mathrm{th}$ percentile ordered according to the degree.

arXiv:2205.02137•Physical Review Research•Dec 13, 2022•8 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

Optimality of spatial search via continuous-time quantum walks

Shantanav Chakraborty, Leonardo Novo, Jérémie Roland

One of the most important algorithmic applications of quantum walks is to solve spatial search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], finds a marked node on a graph of $n$ nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in $O(\sqrt{n})$ time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum search for certain graphs required an instance-specific analysis. In fact, the demonstration of the necessary and sufficient conditions that a graph must fulfill for quantum search to be optimal has been a long-standing open problem. In this work we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than ${n}^{\ensuremath{-}1/2}$. This allows us to derive necessary and sufficient conditions for optimal quantum search in this regime, as well as provide examples of graphs where quantum search is suboptimal. In addition, by extending this analysis, we are also able to show the optimality of quantum search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results.

arXiv:2004.12686•Physical Review A•Sep 14, 2020•37 citations

Renormalization of the unitary evolution equation for coined quantum walks

Stefan Boettcher, Shanshan Li, Renato Portugal

Abstract We consider discrete-time evolution equations in which the stochastic operator of a classical random walk is replaced by a unitary operator. Such a problem has gained much attention as a framework for coined quantum walks that are essential for attaining the Grover limit for quantum search algorithms in physically realizable, low-dimensional geometries. In particular, we analyze the exact real-space renormalization group (RG) procedure recently introduced to study the scaling of quantum walks on fractal networks. While this procedure, when implemented numerically, was able to provide some deep insights into the relation between classical and quantum walks, its analytic basis has remained obscure. Our discussion here is laying the groundwork for a rigorous implementation of the RG for this important class of transport and algorithmic problems, although some instances remain unresolved. Specifically, we find that the RG fixed-point analysis of the classical walk, which typically focuses on the dominant Jacobian eigenvalue λ 1 , with walk dimension d w R W = log 2 ⁡ λ 1 , needs to be extended to include the subdominant eigenvalue λ 2 , such that the dimension of the quantum walk obtains d w Q W = log 2 ⁡ λ 1 λ 2 . With that extension, we obtain analytically previously conjectured results for d w Q W of Grover walks on all but one of the fractal networks that have been considered.

arXiv:1609.00756•Journal of Physics A Mathematical and Theoretical•Jan 31, 2017•5 citations
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 df\ensuremath≠ds{d}_{f}\ensuremath{\ne}{d}_{s}df​\ensuremath=ds​, 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., ds\ensuremath→\ensuremath∞{d}_{s}\ensuremath{\rightarrow}\ensuremath{\infty}ds​\ensuremath→\ensuremath∞) 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 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 We find a lower bound on the computational complexity of Grover’s quantum search algorithms in low-dimensional networks using the renormalization group (RG). It highlights the competition between Grover’s abstract algorithm, i.e., a rotation in Hilbert space, and quantum transport in an actual geometry. It can be characterized in terms of the quantum walk dimension <?CDATA dwQ{d}_{w}^{Q}dwQ​?> d w Q and the spatial (fractal) dimension df or, alternatively, the spectral dimension of the network, ds , even when translational invariance is broken.
We study spatial search with continuous-time quantum walks on real-world complex networks. We use smaller replicas of the Internet network obtained with a recent geometric renormalization method introduced by Garc\'{\i}a-P\'erez et al., Nat. Phys. 14, 583 (2018). This allows us to infer for the first time the behavior of a quantum spatial search algorithm on a real-world complex network. By simulating numerically the dynamics and optimizing the coupling parameter, we study the optimality of the algorithm and its scaling with the size of the network, showing that on average it is considerably better than the classical scaling O(N)\mathcal{O}(N)O(N), but it does not reach the ideal quadratic speedup O(N)\mathcal{O}(\sqrt{N})O(N​) that can be achieved, e.g. in complete graphs. However, the performance of the search algorithm strongly depends on the degree of the nodes and, in fact, the scaling is found to be very close to optimal when we consider the nodes below the 99th99\mathrm{th}99th percentile ordered according to the degree.
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.
One of the most important algorithmic applications of quantum walks is to solve spatial search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], finds a marked node on a graph of nnn nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in O(n)O(\sqrt{n})O(n​) time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum search for certain graphs required an instance-specific analysis. In fact, the demonstration of the necessary and sufficient conditions that a graph must fulfill for quantum search to be optimal has been a long-standing open problem. In this work we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than ${n}^{\ensuremath{-}1/2}$. This allows us to derive necessary and sufficient conditions for optimal quantum search in this regime, as well as provide examples of graphs where quantum search is suboptimal. In addition, by extending this analysis, we are also able to show the optimality of quantum search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results.
Abstract We consider discrete-time evolution equations in which the stochastic operator of a classical random walk is replaced by a unitary operator. Such a problem has gained much attention as a framework for coined quantum walks that are essential for attaining the Grover limit for quantum search algorithms in physically realizable, low-dimensional geometries. In particular, we analyze the exact real-space renormalization group (RG) procedure recently introduced to study the scaling of quantum walks on fractal networks. While this procedure, when implemented numerically, was able to provide some deep insights into the relation between classical and quantum walks, its analytic basis has remained obscure. Our discussion here is laying the groundwork for a rigorous implementation of the RG for this important class of transport and algorithmic problems, although some instances remain unresolved. Specifically, we find that the RG fixed-point analysis of the classical walk, which typically focuses on the dominant Jacobian eigenvalue λ 1 , with walk dimension d w R W = log 2 ⁡ λ 1 , needs to be extended to include the subdominant eigenvalue λ 2 , such that the dimension of the quantum walk obtains d w Q W = log 2 ⁡ λ 1 λ 2 . With that extension, we obtain analytically previously conjectured results for d w Q W of Grover walks on all but one of the fractal networks that have been considered.