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/0310191 · Stochastic Models

Limit Theorems and Absorption Problems for One-Dimensional Correlated Random Walks

Norio Konno

Published Feb 12, 2009• 45 citations
arXivHTMLPDF

Abstract

There has recently been considerable interest in quantum walks in connection with quantum computing. The walk can be considered as a quantum version of the so-called correlated random walk. We clarify a strong structural similarity between both walks and study limit theorems and absorption problems for correlated random walks by our PQRS method, which was used in our analysis of quantum walks.

DOI
10.1080/15326340802640941

Related papers

Limit theorems and absorption problems for quantum radom walks in one dimension

Norio Konno

In this paper we consider limit theorems, symmetry of distribution, and absorption problems for two types of one-dimensional quantum random walks determined by $2 \times 2$ unitary matrices using our PQRS method. The one type was introduced by Gudder in 1988, and the other type was studied intensively by Ambainis et al. in 2001. The difference between both types of quantum random walks is also clarified.

arXiv:quant-ph/0210011•Quantum Information and Computation•Nov 1, 2002•35 citations

Connecting the discrete- and continuous-time quantum walks

Frederick W. Strauch

Recently, quantized versions of random walks have been explored as effective elements for quantum algorithms. In the simplest case of one dimension, the theory has remained divided into the discrete-time quantum walk and the continuous-time quantum walk. Though the properties of these two walks have shown similarities, it has remained an open problem to find the exact relation between the two. The precise connection of these two processes, both quantally and classically, is presented. Extension to higher dimensions is also discussed.

arXiv:quant-ph/0606050•Physical Review A•Sep 7, 2006•178 citations

Absorption phenomena in quantum walks

Parker Kuklinski

The quantum walk is a unitary analogue to the discrete random walk, and its properties have been increasingly studied since the turn of the millennium. In comparison with the classical random walk, the quantum walk exhibits linear spreading and initial condition dependent asymmetries. As noted early on in the conjecture and subsequent calculation of absorption probabilities in the one dimensional Hadamard walk, the interaction of the quantum walk with an absorbing boundary is fundamentally divergent from classical case. Here, we will survey absorption probabilities for a more general collection of one dimensional quantum walks and extend the method to consider d-dimensional walks in the presence of d-1 dimensional absorbing walls. However, these results are concerned only with local behavior at the boundary in the form of absorption probabilities. The main results of this thesis are concerned with the global behavior of finite quantum walks, which can be described by linear spreading in the short term, modal phenomena in the mid term, and stable distributions in the exceedingly long term. These theorems will be rigorously proved in the one-dimensional case and extrapolated to higher dimensional quantum walks. To this end we introduce QWSim, a new and robust computational engine for displaying finite two dimensional quantum walks.

•Jan 1, 2017•1 citation

AN ALGEBRAIC STRUCTURE FOR ONE-DIMENSIONAL QUANTUM WALKS AND A NEW PROOF OF THE WEAK LIMIT THEOREM

TATSUYA TATE

An algebraic structure for one-dimensional quantum walks is introduced. This structure characterizes, in some sense, one-dimensional quantum walks. A natural computation using this algebraic structure leads us to obtain an effective formula for the characteristic function of the transition probability. Then, the weak limit theorem for the transition probability of quantum walks is deduced by using simple properties of the Chebyshev polynomials.

arXiv:1210.0631•Infinite Dimensional Analysis Quantum Probability and Related Topics•Jun 1, 2013•2 citations

A random walk approach to quantum algorithms

Viv M. Kendon

The development of quantum algorithms based on quantum versions of random walks is placed in the context of the emerging field of quantum computing. Constructing a suitable quantum version of a random walk is not trivial; pure quantum dynamics is deterministic, so randomness only enters during the measurement phase, i.e. when converting the quantum information into classical information. The outcome of a quantum random walk is very different from the corresponding classical random walk owing to the interference between the different possible paths. The upshot is that quantum walkers find themselves further from their starting point than a classical walker on average, and this forms the basis of a quantum speed up, which can be exploited to solve problems faster. Surprisingly, the effect of making the walk slightly less than perfectly quantum can optimize the properties of the quantum walk for algorithmic applications. Looking to the future, even with a small quantum computer available, the development of quantum walk algorithms might proceed more rapidly than it has, especially for solving real problems.

arXiv:quant-ph/0609035•Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences•Oct 18, 2006•112 citations

Two models of quantum random walk

Jozef Košík

Abstract We present an overview of two models of quantum random walk. In the first model, the discrete quantum random walk, we present the explicit solution for the recurring amplitude of the quantum random walk on a one-dimensional lattice. We also introduce a new method of solving the problem of random walk in the most general case and use it to derive the hitting amplitude for quantum random walk on the hypercube. The second is a special model based on a local interaction between neighboring spin-1/2 particles on a one-dimensional lattice. We present explicit results for the relevant quantities and obtain an upper bound on the speed of convergence to limiting probability distribution.

Open Physics•Dec 1, 2003•11 citations
There has recently been considerable interest in quantum walks in connection with quantum computing. The walk can be considered as a quantum version of the so-called correlated random walk. We clarify a strong structural similarity between both walks and study limit theorems and absorption problems for correlated random walks by our PQRS method, which was used in our analysis of quantum walks.
In this paper we consider limit theorems, symmetry of distribution, and absorption problems for two types of one-dimensional quantum random walks determined by 2×22 \times 22×2 unitary matrices using our PQRS method. The one type was introduced by Gudder in 1988, and the other type was studied intensively by Ambainis et al. in 2001. The difference between both types of quantum random walks is also clarified.
Recently, quantized versions of random walks have been explored as effective elements for quantum algorithms. In the simplest case of one dimension, the theory has remained divided into the discrete-time quantum walk and the continuous-time quantum walk. Though the properties of these two walks have shown similarities, it has remained an open problem to find the exact relation between the two. The precise connection of these two processes, both quantally and classically, is presented. Extension to higher dimensions is also discussed.
The quantum walk is a unitary analogue to the discrete random walk, and its properties have been increasingly studied since the turn of the millennium. In comparison with the classical random walk, the quantum walk exhibits linear spreading and initial condition dependent asymmetries. As noted early on in the conjecture and subsequent calculation of absorption probabilities in the one dimensional Hadamard walk, the interaction of the quantum walk with an absorbing boundary is fundamentally divergent from classical case. Here, we will survey absorption probabilities for a more general collection of one dimensional quantum walks and extend the method to consider d-dimensional walks in the presence of d-1 dimensional absorbing walls. However, these results are concerned only with local behavior at the boundary in the form of absorption probabilities. The main results of this thesis are concerned with the global behavior of finite quantum walks, which can be described by linear spreading in the short term, modal phenomena in the mid term, and stable distributions in the exceedingly long term. These theorems will be rigorously proved in the one-dimensional case and extrapolated to higher dimensional quantum walks. To this end we introduce QWSim, a new and robust computational engine for displaying finite two dimensional quantum walks.
The development of quantum algorithms based on quantum versions of random walks is placed in the context of the emerging field of quantum computing. Constructing a suitable quantum version of a random walk is not trivial; pure quantum dynamics is deterministic, so randomness only enters during the measurement phase, i.e. when converting the quantum information into classical information. The outcome of a quantum random walk is very different from the corresponding classical random walk owing to the interference between the different possible paths. The upshot is that quantum walkers find themselves further from their starting point than a classical walker on average, and this forms the basis of a quantum speed up, which can be exploited to solve problems faster. Surprisingly, the effect of making the walk slightly less than perfectly quantum can optimize the properties of the quantum walk for algorithmic applications. Looking to the future, even with a small quantum computer available, the development of quantum walk algorithms might proceed more rapidly than it has, especially for solving real problems.
Abstract We present an overview of two models of quantum random walk. In the first model, the discrete quantum random walk, we present the explicit solution for the recurring amplitude of the quantum random walk on a one-dimensional lattice. We also introduce a new method of solving the problem of random walk in the most general case and use it to derive the hitting amplitude for quantum random walk on the hypercube. The second is a special model based on a local interaction between neighboring spin-1/2 particles on a one-dimensional lattice. We present explicit results for the relevant quantities and obtain an upper bound on the speed of convergence to limiting probability distribution.