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:1609.00756 · Journal of Physics A Mathematical and Theoretical

Renormalization of the unitary evolution equation for coined quantum walks

Stefan Boettcher, Shanshan Li, Renato Portugal

Published Jan 31, 2017• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1088/1751-8121/aa5bc1

Related papers

Analysis of coined quantum walks with renormalization

Stefan Boettcher, Shanshan Li

We introduce a framework to analyze quantum algorithms with the renormalization group (RG). To this end, we present a detailed analysis of the real-space RG for discrete-time quantum walks on fractal networks and show how deep insights into the analytic structure as well as generic results about the long-time behavior can be extracted. The RG flow for such a walk on a dual Sierpinski gasket and a Migdal-Kadanoff hierarchical network is obtained explicitly from elementary algebraic manipulations, after transforming the unitary evolution equation into Laplace space. Unlike for classical random walks, we find that the long-time asymptotics for the quantum walk requires consideration of a diverging number of Laplace poles, which we demonstrate exactly for the closed-form solution available for the walk on a one-dimensional loop. In particular, we calculate the probability of the walk to overlap with its starting position, which oscillates with a period that scales as ${N}^{{d}_{w}^{Q}/{d}_{f}}$ with system size $N$. While the largest Jacobian eigenvalue ${\ensuremath{\lambda}}_{1}$ of the RG flow merely reproduces the fractal dimension, ${d}_{f}={log}_{2}{\ensuremath{\lambda}}_{1}$, the asymptotic analysis shows that the second Jacobian eigenvalue ${\ensuremath{\lambda}}_{2}$ becomes essential to determine the dimension of the quantum walk via ${d}_{w}^{Q}={log}_{2}\sqrt{{\ensuremath{\lambda}}_{1}{\ensuremath{\lambda}}_{2}}$. We trace this fact to delicate cancellations caused by unitarity. We obtain identical relations for other networks, although the details of the RG analysis may exhibit surprisingly distinct features. Thus, our conclusions---which trivially reproduce those for regular lattices with translational invariance with ${d}_{f}=d$ and ${d}_{w}^{Q}=1$---appear to be quite general and likely apply to networks beyond those studied here.

arXiv:1704.04692•Physical Review A•Jan 12, 2018•18 citations

Relation between random walks and quantum walks

Stefan Boettcher, Stefan Falkner, Renato Portugal

Based on studies of four specific networks, we conjecture a general relation between the walk dimensions ${d}_{w}$ of discrete-time random walks and quantum walks with the (self-inverse) Grover coin. In each case, we find that ${d}_{w}$ of the quantum walk takes on exactly half the value found for the classical random walk on the same geometry. Since walks on homogeneous lattices satisfy this relation trivially, our results for heterogeneous networks suggest that such a relation holds irrespective of whether translational invariance is maintained or not. To develop our results, we extend the renormalization-group analysis (RG) of the stochastic master equation to one with a unitary propagator. As in the classical case, the solution $\ensuremath{\rho}(x,t)$ in space and time of this quantum-walk equation exhibits a scaling collapse for a variable ${x}^{{d}_{w}}/t$ in the weak limit, which defines ${d}_{w}$ and illuminates fundamental aspects of the walk dynamics, e.g., its mean-square displacement. We confirm the collapse for $\ensuremath{\rho}(x,t)$ in each case with extensive numerical simulation. The exact values for ${d}_{w}$ themselves demonstrate that RG is a powerful complementary approach to study the asymptotics of quantum walks that weak-limit theorems have not been able to access, such as for systems lacking translational symmetries beyond simple trees.

arXiv:1410.7034•Physical Review A•May 29, 2015•23 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

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

Renormalization of discrete-time quantum walks with a non-Grover coin

Stefan Boettcher, Joshua L. Pughe-Sanford

Abstract We present an in-depth analytic study of discrete-time quantum walks driven by a non-reflective coin. Specifically, we compare the properties of the widely-used Grover coin C G that is unitary and reflective ( C G 2 = I ) with those of a 3 × 3 ‘rotational’ coin C 60 that is unitary but non-reflective ( C 60 2 ≠ I ) and satisfies instead C 60 6 = I , which corresponds to a rotation by 60 ∘ . While such a modification apparently changes the real-space renormalization group (RG) treatment, we show that nonetheless this non-reflective quantum walk remains in the same universality class as the Grover walk. We first demonstrate the procedure with C 60 for a three-state quantum walk on a one-dimensional ( 1d ) line, where we can solve the RG-recursions in closed form in a process providing exact solutions for some difficult non-linear recursions. Then, we apply the procedure to a quantum walk on a dual Sierpinski gasket (DSG), for which we ultimately reproduce the same results found for C G

arXiv:1709.06414•Journal of Statistical Mechanics Theory and Experiment•Mar 1, 2018•2 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
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.
We introduce a framework to analyze quantum algorithms with the renormalization group (RG). To this end, we present a detailed analysis of the real-space RG for discrete-time quantum walks on fractal networks and show how deep insights into the analytic structure as well as generic results about the long-time behavior can be extracted. The RG flow for such a walk on a dual Sierpinski gasket and a Migdal-Kadanoff hierarchical network is obtained explicitly from elementary algebraic manipulations, after transforming the unitary evolution equation into Laplace space. Unlike for classical random walks, we find that the long-time asymptotics for the quantum walk requires consideration of a diverging number of Laplace poles, which we demonstrate exactly for the closed-form solution available for the walk on a one-dimensional loop. In particular, we calculate the probability of the walk to overlap with its starting position, which oscillates with a period that scales as NdwQ/df{N}^{{d}_{w}^{Q}/{d}_{f}}NdwQ​/df​ with system size NNN. While the largest Jacobian eigenvalue ${\ensuremath{\lambda}}_{1}$ of the RG flow merely reproduces the fractal dimension, ${d}_{f}={log}_{2}{\ensuremath{\lambda}}_{1}$, the asymptotic analysis shows that the second Jacobian eigenvalue ${\ensuremath{\lambda}}_{2}$ becomes essential to determine the dimension of the quantum walk via ${d}_{w}^{Q}={log}_{2}\sqrt{{\ensuremath{\lambda}}_{1}{\ensuremath{\lambda}}_{2}}$. We trace this fact to delicate cancellations caused by unitarity. We obtain identical relations for other networks, although the details of the RG analysis may exhibit surprisingly distinct features. Thus, our conclusions---which trivially reproduce those for regular lattices with translational invariance with df=d{d}_{f}=ddf​=d and dwQ=1{d}_{w}^{Q}=1dwQ​=1---appear to be quite general and likely apply to networks beyond those studied here.
Based on studies of four specific networks, we conjecture a general relation between the walk dimensions dw{d}_{w}dw​ of discrete-time random walks and quantum walks with the (self-inverse) Grover coin. In each case, we find that dw{d}_{w}dw​ of the quantum walk takes on exactly half the value found for the classical random walk on the same geometry. Since walks on homogeneous lattices satisfy this relation trivially, our results for heterogeneous networks suggest that such a relation holds irrespective of whether translational invariance is maintained or not. To develop our results, we extend the renormalization-group analysis (RG) of the stochastic master equation to one with a unitary propagator. As in the classical case, the solution $\ensuremath{\rho}(x,t)$ in space and time of this quantum-walk equation exhibits a scaling collapse for a variable xdw/t{x}^{{d}_{w}}/txdw​/t in the weak limit, which defines dw{d}_{w}dw​ and illuminates fundamental aspects of the walk dynamics, e.g., its mean-square displacement. We confirm the collapse for $\ensuremath{\rho}(x,t)$ in each case with extensive numerical simulation. The exact values for dw{d}_{w}dw​ themselves demonstrate that RG is a powerful complementary approach to study the asymptotics of quantum walks that weak-limit theorems have not been able to access, such as for systems lacking translational symmetries beyond simple trees.
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.
Abstract We present an in-depth analytic study of discrete-time quantum walks driven by a non-reflective coin. Specifically, we compare the properties of the widely-used Grover coin C G that is unitary and reflective ( C G 2 = I ) with those of a 3 × 3 ‘rotational’ coin C 60 that is unitary but non-reflective ( C 60 2 ≠ I ) and satisfies instead C 60 6 = I , which corresponds to a rotation by 60 ∘ . While such a modification apparently changes the real-space renormalization group (RG) treatment, we show that nonetheless this non-reflective quantum walk remains in the same universality class as the Grover walk. We first demonstrate the procedure with C 60 for a three-state quantum walk on a one-dimensional ( 1d ) line, where we can solve the RG-recursions in closed form in a process providing exact solutions for some difficult non-linear recursions. Then, we apply the procedure to a quantum walk on a dual Sierpinski gasket (DSG), for which we ultimately reproduce the same results found for C G
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.