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:2210.05310 · Physical Review Research

Quantum walks on random lattices: Diffusion, localization, and the absence of parametric quantum speedup

Rostislav Duda, Moein N. Ivaki, Isac Sahlberg, Kim Pöyhönen, Teemu Ojanen

Published Jun 5, 2023• 13 citations
arXivHTMLPDF

Abstract

Discrete-time quantum walks, quantum generalizations of classical random walks, provide a framework for quantum information processing, quantum algorithms, and quantum simulation of condensed-matter systems. The key property of quantum walks, which lies at the heart of their quantum information applications, is the possibility for a parametric quantum speedup in propagation compared to classical random walks. In this work we study propagation of quantum walks on percolation-generated two-dimensional random lattices. In large-scale simulations of topological and trivial split-step walks, we identify distinct prediffusive and diffusive behaviors at different timescales. Importantly, we show that even arbitrarily weak concentrations of randomly removed lattice sites give rise to a complete breakdown of the superdiffusive quantum speedup, reducing the motion to ordinary diffusion. By increasing the randomness, quantum walks eventually stop spreading due to Anderson localization. Near the localization threshold, we find that the quantum walks become subdiffusive. The fragility of quantum speedup implies dramatic limitations for quantum information applications of quantum walks on random geometries and graphs.

DOI
10.1103/physrevresearch.5.023150

Related papers

Coined quantum walks on percolation graphs

Godfrey Leung, Paul Knott, Joe Bailey +1 more

Quantum walks, both discrete (coined) and continuous time, form the basis of several quantum algorithms and have been used to model processes such as transport in spin chains and quantum chemistry. The enhanced spreading and mixing properties of quantum walks compared with their classical counterparts have been well studied on regular structures and also shown to be sensitive to defects and imperfections in the lattice. As a simple example of a disordered system, we consider percolation lattices, in which edges or sites are randomly missing, interrupting the progress of the quantum walk. We use numerical simulation to study the properties of coined quantum walks on these percolation lattices in one and two dimensions. In one dimension (the line), we introduce a simple notion of quantum tunnelling and determine how this affects the properties of the quantum walk as it spreads. On two-dimensional percolation lattices, we show how the spreading rate varies from linear in the number of steps down to zero as the percolation probability decreases towards the critical point. This provides an example of fractional scaling in quantum-walk dynamics.

arXiv:1006.1283•New Journal of Physics•Dec 9, 2010•52 citations

Fractional scaling of quantum walks on percolation lattices

Viv M. Kendon, Godfrey Leung, Joe Bailey +1 more

Quantum walks can be used to model processes such as transport in spin chains and bio-molecules. The enhanced spreading and mixing properties of quantum walks compared with their classical counterparts have been well-studied on regular structures and also shown to be sensitive to defects and imperfections. Using numerical simulation, we study the spreading properties of quantum walks on percolation lattices for both bond and site percolation. The randomly missing edges or sites provide a controlled amount of disorder in the regular Cartesian lattice. In one dimension (the line) we introduce a simple model of quantum tunneling to allow the walk to proceed past the missing edges or sites. This allows the quantum walk to spread faster than a classical random walk for short times, but at longer times the disorder localises the quantum walk. In two dimensions, we observe fractional scaling of the spreading with the number of steps of the walk. For percolation above the 85% level, we obtain faster spreading than classical random walks on the full lattice.

Journal of Physics Conference Series•Mar 1, 2011•2 citations

Spreading and transport properties of quantum walks

İ. Yalçınkaya

Quantum computing aims to harness and exploit the quantum mechanical phenomena such as superposition, entanglement and contextuality in order to encode and process information. In this context, quantum walks, which has been suggested as the quantum counterpart of classical random walks, is an emerging topic in quantum computing that provides powerful techniques for developing new quantum algorithms, quantum simulation and quantum state transfer. This thesis intends to investigate the properties of quantum walks which may potentially promote further work in such techniques in quantum computation. We first propose a novel method for transferring arbitrary unknown qubit state between two points in space with quantum walk architecture. We determine the cases providing perfect state transfers over both finite and infinite lattices with different boundary conditions and we introduce recovery operators assisting the transfer process. Next, by modeling the incoherent and coherent transport with classical random walks and quantum walks, respectively, we calculate the transport efficiencies over an explosive percolation lattice. We show that the minimal correlation between discrete clusters leads to maximal localizations which originating from random scatterings. These localization effects, however, are rather small when compared to the supportive effect of the abrupt growth of the largest cluster on transport efficiency, which eventually allows us to obtain more efficient transports in case of minimal correlations. We support our results with further calculations on whether the eigenstates of the systems we study are localized or not. Lastly, we turn our attention to the spreading dynamics and the coin-position entanglement for two-dimensional quantum walks under an artificial magnetic fields by introducing Peierls phases to the system. In particular, we show that the spreading of the quantum walk is diffusive rather than ballistic when the ratio of the magnetic flux through unit cell - where the walk takes place - to the flux quantum is an irrational number. On the contrary, the walk recovers its original ballistic behavior when this ratio is chosen to be a rational number. Furthermore, we demonstrate that coin-position entanglement is nearly maximum under an artificial magnetic field, even for large number of steps.

•Aug 1, 2016•0 citations

Localization, delocalization, and topological phase transitions in the one-dimensional split-step quantum walk

Tibor Rakovszky, János K. Asbóth

Quantum walks are promising for information processing tasks because in regular graphs they spread quadratically more rapidly than random walks. Static disorder, however, can turn the tables: unlike random walks, quantum walks can suffer Anderson localization, with their wave function staying within a finite region even in the infinite time limit, with a probability exponentially close to 1. It is thus important to understand when a quantum walk will be Anderson localized and when we can expect it to spread to infinity even in the presence of disorder. In this work we analyze the response of a one-dimensional quantum walk---the split-step walk---to different forms of static disorder. We find that introducing static, symmetry-preserving disorder in the parameters of the walk leads to Anderson localization. In the completely disordered limit, however, a delocalization transition occurs, and the walk spreads subdiffusively to infinity. Using an efficient numerical algorithm, we calculate the bulk topological invariants of the disordered walk and find that the disorder-induced Anderson localization and delocalization transitions are governed by the topological phases of the quantum walk.

arXiv:1505.04513•Physical Review A•Nov 10, 2015•63 citations

Quantum walks on trees with disorder: Decay, diffusion, and localization

Steven R. Jackson, T. J. Khoo, Frederick W. Strauch

Quantum walks have been shown to have impressive transport properties compared to classical random walks. However, imperfections in the quantum-walk algorithm can destroy any quantum-mechanical speedup due to Anderson localization. We numerically study the effect of static disorder on a quantum walk on the glued trees graph. For small disorder, we find that the dominant effect is a type of quantum decay, and not quantum localization. For intermediate disorder, there is a crossover to diffusive transport, while a localization transition is observed at large disorder, in agreement with Anderson localization on the Cayley tree.

arXiv:1206.3178•Physical Review A•Aug 27, 2012•28 citations

Quantum walks on a random environment

Y. Yin, D. E. Katsanos, S. N. Evangelou

Quantum walks are considered in a one-dimensional random medium characterized by static or dynamic disorder. Quantum interference for static disorder can lead to Anderson localization which completely hinders the quantum walk and it is contrasted with the decoherence effect of dynamic disorder having strength $W$, where a quantum to classical crossover at time ${t}_{c}\ensuremath{\propto}{W}^{\ensuremath{-}2}$ transforms the quantum walk into an ordinary random walk with diffusive spreading. We demonstrate these localization and decoherence phenomena in quantum carpets of the observed time evolution, we relate our results to previously studied models of decoherence for quantum walks, and examine in detail a dimer lattice which corresponds to a single qubit subject to randomness.

arXiv:0708.1137•Physical Review A•Feb 5, 2008•119 citations
Discrete-time quantum walks, quantum generalizations of classical random walks, provide a framework for quantum information processing, quantum algorithms, and quantum simulation of condensed-matter systems. The key property of quantum walks, which lies at the heart of their quantum information applications, is the possibility for a parametric quantum speedup in propagation compared to classical random walks. In this work we study propagation of quantum walks on percolation-generated two-dimensional random lattices. In large-scale simulations of topological and trivial split-step walks, we identify distinct prediffusive and diffusive behaviors at different timescales. Importantly, we show that even arbitrarily weak concentrations of randomly removed lattice sites give rise to a complete breakdown of the superdiffusive quantum speedup, reducing the motion to ordinary diffusion. By increasing the randomness, quantum walks eventually stop spreading due to Anderson localization. Near the localization threshold, we find that the quantum walks become subdiffusive. The fragility of quantum speedup implies dramatic limitations for quantum information applications of quantum walks on random geometries and graphs.
Quantum walks, both discrete (coined) and continuous time, form the basis of several quantum algorithms and have been used to model processes such as transport in spin chains and quantum chemistry. The enhanced spreading and mixing properties of quantum walks compared with their classical counterparts have been well studied on regular structures and also shown to be sensitive to defects and imperfections in the lattice. As a simple example of a disordered system, we consider percolation lattices, in which edges or sites are randomly missing, interrupting the progress of the quantum walk. We use numerical simulation to study the properties of coined quantum walks on these percolation lattices in one and two dimensions. In one dimension (the line), we introduce a simple notion of quantum tunnelling and determine how this affects the properties of the quantum walk as it spreads. On two-dimensional percolation lattices, we show how the spreading rate varies from linear in the number of steps down to zero as the percolation probability decreases towards the critical point. This provides an example of fractional scaling in quantum-walk dynamics.
Quantum walks can be used to model processes such as transport in spin chains and bio-molecules. The enhanced spreading and mixing properties of quantum walks compared with their classical counterparts have been well-studied on regular structures and also shown to be sensitive to defects and imperfections. Using numerical simulation, we study the spreading properties of quantum walks on percolation lattices for both bond and site percolation. The randomly missing edges or sites provide a controlled amount of disorder in the regular Cartesian lattice. In one dimension (the line) we introduce a simple model of quantum tunneling to allow the walk to proceed past the missing edges or sites. This allows the quantum walk to spread faster than a classical random walk for short times, but at longer times the disorder localises the quantum walk. In two dimensions, we observe fractional scaling of the spreading with the number of steps of the walk. For percolation above the 85% level, we obtain faster spreading than classical random walks on the full lattice.
Quantum computing aims to harness and exploit the quantum mechanical phenomena such as superposition, entanglement and contextuality in order to encode and process information. In this context, quantum walks, which has been suggested as the quantum counterpart of classical random walks, is an emerging topic in quantum computing that provides powerful techniques for developing new quantum algorithms, quantum simulation and quantum state transfer. This thesis intends to investigate the properties of quantum walks which may potentially promote further work in such techniques in quantum computation. We first propose a novel method for transferring arbitrary unknown qubit state between two points in space with quantum walk architecture. We determine the cases providing perfect state transfers over both finite and infinite lattices with different boundary conditions and we introduce recovery operators assisting the transfer process. Next, by modeling the incoherent and coherent transport with classical random walks and quantum walks, respectively, we calculate the transport efficiencies over an explosive percolation lattice. We show that the minimal correlation between discrete clusters leads to maximal localizations which originating from random scatterings. These localization effects, however, are rather small when compared to the supportive effect of the abrupt growth of the largest cluster on transport efficiency, which eventually allows us to obtain more efficient transports in case of minimal correlations. We support our results with further calculations on whether the eigenstates of the systems we study are localized or not. Lastly, we turn our attention to the spreading dynamics and the coin-position entanglement for two-dimensional quantum walks under an artificial magnetic fields by introducing Peierls phases to the system. In particular, we show that the spreading of the quantum walk is diffusive rather than ballistic when the ratio of the magnetic flux through unit cell - where the walk takes place - to the flux quantum is an irrational number. On the contrary, the walk recovers its original ballistic behavior when this ratio is chosen to be a rational number. Furthermore, we demonstrate that coin-position entanglement is nearly maximum under an artificial magnetic field, even for large number of steps.
Quantum walks are promising for information processing tasks because in regular graphs they spread quadratically more rapidly than random walks. Static disorder, however, can turn the tables: unlike random walks, quantum walks can suffer Anderson localization, with their wave function staying within a finite region even in the infinite time limit, with a probability exponentially close to 1. It is thus important to understand when a quantum walk will be Anderson localized and when we can expect it to spread to infinity even in the presence of disorder. In this work we analyze the response of a one-dimensional quantum walk---the split-step walk---to different forms of static disorder. We find that introducing static, symmetry-preserving disorder in the parameters of the walk leads to Anderson localization. In the completely disordered limit, however, a delocalization transition occurs, and the walk spreads subdiffusively to infinity. Using an efficient numerical algorithm, we calculate the bulk topological invariants of the disordered walk and find that the disorder-induced Anderson localization and delocalization transitions are governed by the topological phases of the quantum walk.
Quantum walks have been shown to have impressive transport properties compared to classical random walks. However, imperfections in the quantum-walk algorithm can destroy any quantum-mechanical speedup due to Anderson localization. We numerically study the effect of static disorder on a quantum walk on the glued trees graph. For small disorder, we find that the dominant effect is a type of quantum decay, and not quantum localization. For intermediate disorder, there is a crossover to diffusive transport, while a localization transition is observed at large disorder, in agreement with Anderson localization on the Cayley tree.
Quantum walks are considered in a one-dimensional random medium characterized by static or dynamic disorder. Quantum interference for static disorder can lead to Anderson localization which completely hinders the quantum walk and it is contrasted with the decoherence effect of dynamic disorder having strength WWW, where a quantum to classical crossover at time ${t}_{c}\ensuremath{\propto}{W}^{\ensuremath{-}2}$ transforms the quantum walk into an ordinary random walk with diffusive spreading. We demonstrate these localization and decoherence phenomena in quantum carpets of the observed time evolution, we relate our results to previously studied models of decoherence for quantum walks, and examine in detail a dimer lattice which corresponds to a single qubit subject to randomness.