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:quant-ph/0108004 · Journal of Physics A Mathematical and General

Quantum walks in higher dimensions

Troy D. Mackay, Stephen D. Bartlett, Leigh T. Stephenson, Barry C. Sanders

Published Mar 15, 2002• 255 citations
arXivHTMLPDF

Abstract

We analyse the quantum walk in higher spatial dimensions and compare classical and quantum spreading as a function of time. Tensor products of Hadamard transformations and the discrete Fourier transform arise as natural extensions of the 'quantum coin toss' in the one-dimensional walk simulation, and other illustrative transformations are also investigated. We find that entanglement between the dimensions serves to reduce the rate of spread of the quantum walk. The classical limit is obtained by introducing a random phase variable.

DOI
10.1088/0305-4470/35/12/304

Related papers

Scaling limits of long-range quantum random walks

Rik Westdorp

In this thesis we introduce a variation on the quantum random walk to discuss shifts in an arbitrary range. The concept of Hadamard coin was therefore generalised to a higher order. By a Fourier transform method and a tensor product decomposition of the evolution matrix the long-range quantum random walk was found to converge in distribution to a random variable, different for every range. The limiting random variable consists of three parts: one part fast decaying with the range size, a non-convergent part and a convergent part. Lastly, an introduction was made into the topic of trapped quantum random walks. As a starting point, the survival probability of such a walk on a 3-cycle was calculated and found to scale as 2^(-n), as does the classical trapped random walk on this topology.

•Jan 1, 2018•0 citations

Faster transport with a directed quantum walk

Stephan Hoyer, DAVID A. MEYER

We give an example of faster transport with a quantum walk on an inherently directed graph, on the directed line with a variable number of self-loops at each vertex. These self-loops can be thought of as adding a number of small dimensions. This is a discrete time quantum walk using the Fourier transform coin, where the walk proceeds a distance $\ensuremath{\Theta}(1)$ in constant time compared to $\ensuremath{\Theta}(1/n)$ classically, independent of the number of these small dimensions. The analysis proceeds by reducing this walk to a walk with a two-dimensional coin.

arXiv:0901.1007•Physical Review A•Feb 18, 2009•32 citations

Quantum walks driven by many coins

Todd A. Brun, Hilary A. Carteret, Andris Ambainis

Quantum random walks have been much studied recently, largely due to their highly nonclassical behavior. In this paper, we study one possible route to classical behavior for the discrete quantum random walk on the line: the use of multiple quantum ``coins'' (or more generally, coins of higher dimension) in order to diminish the effects of interference between paths. We find solutions to this system in terms of the single-coin random walk, and compare the asymptotic limit of these solutions to numerical simulations. We find exact analytical expressions for the time dependence of the first two moments, and show that in the long-time limit the ``quantum-mechanical'' behavior of the one-coin walk persists, even if each coin is flipped only twice. We further show that this is generic for a very broad class of possible walks, and that this behavior disappears only in the limit of a new coin for every step of the walk.

arXiv:quant-ph/0210161•Physical Review A•May 30, 2003•186 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

Optimizing the spatial spread of a quantum walk

Gonzalo Martín-Vázquez, Javier Rodríguez-Laguna

We devise a protocol to build one-dimensional time-dependent quantum walks, maximizing the spatial spread throughout the procedure. We allow only one of the physical parameters of the coin-tossing operator to vary, i.e., the angle $\ensuremath{\theta}$, such that for $\ensuremath{\theta}=0$ we have the ${\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\ensuremath{\sigma}}}_{z}$, while for $\ensuremath{\theta}=\ensuremath{\pi}/4$ we obtain the Hadamard gate. The optimal $\ensuremath{\theta}$ sequences present nontrivial patterns, with mostly $\ensuremath{\theta}\ensuremath{\approx}0$ alternating with $\ensuremath{\theta}\ensuremath{\approx}\ensuremath{\pi}/4$ values after increasingly long periods. We provide an analysis of the entanglement properties, quasienergy spectrum, and survival probability, providing a full physical picture.

arXiv:2004.05657•Physical Review A•Aug 24, 2020•10 citations

One-dimensional lazy quantum walks and occupancy rate

Dan Li, Gettrick, Michael Mc, Weiwei Zhang +1 more

In this paper, we discuss the properties of lazy quantum walks. Our analysis shows that the lazy quantum walks have O(t(n)) order of the n-th moment of the corresponding probability distribution, which is the same as that for normal quantum walks. The lazy quantum walk with a discrete Fourier transform (DFT) coin operator has a similar probability distribution concentrated interval to that of the normal Hadamard quantum walk. Most importantly, we introduce the concepts of occupancy number and occupancy rate to measure the extent to which the walk has a (relatively) high probability at every position in its range. We conclude that the lazy quantum walks have a higher occupancy rate than other walks such as normal quantum walks, classical walks, and lazy classical walks.

•Sep 20, 2018•16 citations
We analyse the quantum walk in higher spatial dimensions and compare classical and quantum spreading as a function of time. Tensor products of Hadamard transformations and the discrete Fourier transform arise as natural extensions of the 'quantum coin toss' in the one-dimensional walk simulation, and other illustrative transformations are also investigated. We find that entanglement between the dimensions serves to reduce the rate of spread of the quantum walk. The classical limit is obtained by introducing a random phase variable.
In this thesis we introduce a variation on the quantum random walk to discuss shifts in an arbitrary range. The concept of Hadamard coin was therefore generalised to a higher order. By a Fourier transform method and a tensor product decomposition of the evolution matrix the long-range quantum random walk was found to converge in distribution to a random variable, different for every range. The limiting random variable consists of three parts: one part fast decaying with the range size, a non-convergent part and a convergent part. Lastly, an introduction was made into the topic of trapped quantum random walks. As a starting point, the survival probability of such a walk on a 3-cycle was calculated and found to scale as 2^(-n), as does the classical trapped random walk on this topology.
We give an example of faster transport with a quantum walk on an inherently directed graph, on the directed line with a variable number of self-loops at each vertex. These self-loops can be thought of as adding a number of small dimensions. This is a discrete time quantum walk using the Fourier transform coin, where the walk proceeds a distance $\ensuremath{\Theta}(1)$ in constant time compared to $\ensuremath{\Theta}(1/n)$ classically, independent of the number of these small dimensions. The analysis proceeds by reducing this walk to a walk with a two-dimensional coin.
Quantum random walks have been much studied recently, largely due to their highly nonclassical behavior. In this paper, we study one possible route to classical behavior for the discrete quantum random walk on the line: the use of multiple quantum ``coins'' (or more generally, coins of higher dimension) in order to diminish the effects of interference between paths. We find solutions to this system in terms of the single-coin random walk, and compare the asymptotic limit of these solutions to numerical simulations. We find exact analytical expressions for the time dependence of the first two moments, and show that in the long-time limit the ``quantum-mechanical'' behavior of the one-coin walk persists, even if each coin is flipped only twice. We further show that this is generic for a very broad class of possible walks, and that this behavior disappears only in the limit of a new coin for every step of the walk.
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 devise a protocol to build one-dimensional time-dependent quantum walks, maximizing the spatial spread throughout the procedure. We allow only one of the physical parameters of the coin-tossing operator to vary, i.e., the angle $\ensuremath{\theta}$, such that for $\ensuremath{\theta}=0$ we have the ${\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{\ensuremath{\sigma}}}_{z}$, while for $\ensuremath{\theta}=\ensuremath{\pi}/4$ we obtain the Hadamard gate. The optimal $\ensuremath{\theta}$ sequences present nontrivial patterns, with mostly $\ensuremath{\theta}\ensuremath{\approx}0$ alternating with $\ensuremath{\theta}\ensuremath{\approx}\ensuremath{\pi}/4$ values after increasingly long periods. We provide an analysis of the entanglement properties, quasienergy spectrum, and survival probability, providing a full physical picture.
In this paper, we discuss the properties of lazy quantum walks. Our analysis shows that the lazy quantum walks have O(t(n)) order of the n-th moment of the corresponding probability distribution, which is the same as that for normal quantum walks. The lazy quantum walk with a discrete Fourier transform (DFT) coin operator has a similar probability distribution concentrated interval to that of the normal Hadamard quantum walk. Most importantly, we introduce the concepts of occupancy number and occupancy rate to measure the extent to which the walk has a (relatively) high probability at every position in its range. We conclude that the lazy quantum walks have a higher occupancy rate than other walks such as normal quantum walks, classical walks, and lazy classical walks.