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:1307.3384 · Journal of Computational and Theoretical Nanoscience

From Discrete Time Quantum Walk to Continuous Time Quantum Walk in Limit Distribution

Yutaka Shikano

Published Jun 20, 2013• 51 citations
arXivHTMLPDF

Abstract

The discrete time quantum walk defined as a quantum-mechanical analogue of the discrete time random walk have recently been attracted from various and interdisciplinary fields. In this review, the weak limit theorem, that is, the asymptotic behavior, of the one-dimensional discrete time quantum walk is analytically shown. From the limit distribution of the discrete time quantum walk, the discrete time quantum walk can be taken as the quantum dynamical simulator of some physical systems.

DOI
10.1166/jctn.2013.3097

Related papers

Continuous limit of discrete quantum walks

M N Dheeraj, Todd A. Brun

Quantum walks can be defined in two quite distinct ways: discrete-time and continuous-time quantum walks (DTQWs and CTQWs). For classical random walks, there is a natural sense in which continuous-time walks are a limit of discrete-time walks. Quantum mechanically, in the discrete-time case, an additional ``coin space'' must be appended for the walk to have nontrivial time evolution. Continuous-time quantum walks, however, have no such constraints. This means that there is no completely straightforward way to treat a CTQW as a limit of a DTQW, as can be done in the classical case. Various approaches to this problem have been taken in the past. We give a construction for walks on $d$-regular, $d$-colorable graphs when the coin flip operator is Hermitian: from a standard DTQW we construct a family of discrete-time walks with a well-defined continuous-time limit on a related graph. One can think of this limit as a ``coined'' continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at a spatial search by a DTQW over the two-dimensional (2D) torus (a grid with periodic boundary conditions) of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$, where it was shown that a coined DTQW can search in time $O(\sqrt{N}logN)$, but a standard CTQW takes $\mathrm{\ensuremath{\Omega}}(N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2D torus exhibits the $O(\sqrt{N}logN)$ scaling, like the coined walk it is derived from. We also look at the effects of graph symmetry on the limiting walk, and show that the properties are similar to those of the DTQW as shown in Krovi and Brun, Phys. Rev. A 75, 062332 (2007).

arXiv:1501.06950•Physical Review A•Jun 5, 2015•17 citations

Crossovers induced by discrete-time quantum walks

Kota Chisaki, Norio Konno, Etsuo Segawa +1 more

We consider crossovers with respect to the weak convergence theorems from a discrete-time quantum walk (DTQW). We show that a continuous-time quantum walk (CTQW) and discrete- and continuous-time random walks can be expressed as DTQWs in some limits. At first we generalize our previous study [Phys. Rev. A \textbf{81}, 062129 (2010)] on the DTQW with position measurements. We show that the position measurements per each step with probability $p \sim 1/n^\beta$ can be evaluated, where $n$ is the final time and $0<\beta<1$. We also give a corresponding continuous-time case. As a consequence, crossovers from the diffusive spreading (random walk) to the ballistic spreading (quantum walk) can be seen as the parameter $\beta$ shifts from 0 to 1 in both discrete- and continuous-time cases of the weak convergence theorems. Secondly, we introduce a new class of the DTQW, in which the absolute value of the diagonal parts of the quantum coin is proportional to a power of the inverse of the final time $n$. This is called a final-time-dependent DTQW (FTD-DTQW). The CTQW is obtained in a limit of the FTD-DTQW. We also obtain the weak convergence theorem for the FTD-DTQW which shows a variety of spreading properties. Finally, we consider the FTD-DTQW with periodic position measurements. This weak convergence theorem gives a phase diagram which maps sufficiently long-time behaviors of the discrete- and continuous-time quantum and random walks.

arXiv:1009.2131•Quantum Information and Computation•Sep 1, 2011•24 citations

Quantum walks: a comprehensive review

Salvador Elías Venegas-Andraca

Quantum walks, the quantum mechanical counterpart of classical random walks, is an advanced tool for building quantum algorithms that has been recently shown to constitute a universal model of quantum computation. Quantum walks is now a solid field of research of quantum computation full of exciting open problems for physicists, computer scientists and engineers. In this paper we review theoretical advances on the foundations of both discrete- and continuous-time quantum walks, together with the role that randomness plays in quantum walks, the connections between the mathematical models of coined discrete quantum walks and continuous quantum walks, the quantumness of quantum walks, a summary of papers published on discrete quantum walks and entangle-ment as well as a succinct review of experimental proposals and realizations of discrete-time quantum walks. Furthermore, we have reviewed several algorithms based on both discrete- and continuous-time quantum walks as well as a most important result: the computational universality of both continuous- and discrete-time quantum walks.

•Jan 1, 2012•436 citations

The discrete-time quantum walk as a stochastic process in quantum mechanics

Yutaka Shikano, Junsei Horikawa, Tatsuaki Wada

Quantum walks are powerful tools not only to construct the quantum speedup algorithms but also to describe specific models in physical processes. Furthermore, the discrete-time quantum walk (DTQW) has been experimentally realized in various setups. We show the limit distribution of the DTQW with the periodic position measurement under the time scale transformation and its connected to some physical-related models.

Physica Scripta•Nov 1, 2012•2 citations

Limit theorem for continuous-time quantum walk on the line

Norio Konno

Concerning a discrete-time quantum walk ${X}_{t}^{(d)}$ with a symmetric distribution on the line, whose evolution is described by the Hadamard transformation, it was proved by the author that the following weak limit theorem holds: ${X}_{t}^{(d)}∕t\ensuremath{\rightarrow}dx∕\ensuremath{\pi}(1\ensuremath{-}{x}^{2})\sqrt{1\ensuremath{-}2{x}^{2}}$ as $t\ensuremath{\rightarrow}\ensuremath{\infty}$. The present paper shows that a similar type of weak limit theorem is satisfied for a continuous-time quantum walk ${X}_{t}^{(c)}$ on the line as follows: ${X}_{t}^{(c)}∕t\ensuremath{\rightarrow}dx∕\ensuremath{\pi}\sqrt{1\ensuremath{-}{x}^{2}}$ as $t\ensuremath{\rightarrow}\ensuremath{\infty}$. These results for quantum walks form a striking contrast to the central limit theorem for symmetric discrete- and continuous-time classical random walks: ${Y}_{t}∕\sqrt{t}\ensuremath{\rightarrow}{e}^{\ensuremath{-}{x}^{2}∕2}dx∕\sqrt{2\ensuremath{\pi}}$ as $t\ensuremath{\rightarrow}\ensuremath{\infty}$. The work deals also with the issue of the relationship between discrete and continuous-time quantum walks. This topic, subject of a long debate in the previous literature, is treated within the formalism of matrix representation and the limit distributions are exhaustively compared in the two cases.

arXiv:quant-ph/0408140•Physical Review E•Aug 12, 2005•125 citations

Continuum Limits of the 1D Discrete Time Quantum Walk

Michael Manighalam, Mark Kon

The discrete time quantum walk (DTQW) is a universal quantum computational model. Significant relationships between discrete and corresponding continuous quantum systems have been studied since the work of Pauli and Feynman. This work continues the study of relationships between discrete quantum models and their ostensive continuum counterparts by developing a formal transition between discrete and continuous quantum systems through a formal framework for continuum limits of the DTQW. Under this framework, we prove two constructive theorems concerning which internal discrete transitions ("coins") admit nontrivial continuum limits. We additionally prove that the continuous space limit of the continuous time limit of the DTQW can only yield massless states which obey the Dirac equation. Finally, we demonstrate that the continuous time limit of the DTQW can be identified with the canonical continuous time quantum walk (CTQW) when the coin is allowed to transition through the continuous limit process.

arXiv:1909.07531•Sep 17, 2019•4 citations
The discrete time quantum walk defined as a quantum-mechanical analogue of the discrete time random walk have recently been attracted from various and interdisciplinary fields. In this review, the weak limit theorem, that is, the asymptotic behavior, of the one-dimensional discrete time quantum walk is analytically shown. From the limit distribution of the discrete time quantum walk, the discrete time quantum walk can be taken as the quantum dynamical simulator of some physical systems.
Quantum walks can be defined in two quite distinct ways: discrete-time and continuous-time quantum walks (DTQWs and CTQWs). For classical random walks, there is a natural sense in which continuous-time walks are a limit of discrete-time walks. Quantum mechanically, in the discrete-time case, an additional ``coin space'' must be appended for the walk to have nontrivial time evolution. Continuous-time quantum walks, however, have no such constraints. This means that there is no completely straightforward way to treat a CTQW as a limit of a DTQW, as can be done in the classical case. Various approaches to this problem have been taken in the past. We give a construction for walks on ddd-regular, ddd-colorable graphs when the coin flip operator is Hermitian: from a standard DTQW we construct a family of discrete-time walks with a well-defined continuous-time limit on a related graph. One can think of this limit as a ``coined'' continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at a spatial search by a DTQW over the two-dimensional (2D) torus (a grid with periodic boundary conditions) of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$, where it was shown that a coined DTQW can search in time O(NlogN)O(\sqrt{N}logN)O(N​logN), but a standard CTQW takes $\mathrm{\ensuremath{\Omega}}(N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2D torus exhibits the O(NlogN)O(\sqrt{N}logN)O(N​logN) scaling, like the coined walk it is derived from. We also look at the effects of graph symmetry on the limiting walk, and show that the properties are similar to those of the DTQW as shown in Krovi and Brun, Phys. Rev. A 75, 062332 (2007).
We consider crossovers with respect to the weak convergence theorems from a discrete-time quantum walk (DTQW). We show that a continuous-time quantum walk (CTQW) and discrete- and continuous-time random walks can be expressed as DTQWs in some limits. At first we generalize our previous study [Phys. Rev. A \textbf{81}, 062129 (2010)] on the DTQW with position measurements. We show that the position measurements per each step with probability p∼1/nβp \sim 1/n^\betap∼1/nβ can be evaluated, where nnn is the final time and 0<β<10<\beta<10<β<1. We also give a corresponding continuous-time case. As a consequence, crossovers from the diffusive spreading (random walk) to the ballistic spreading (quantum walk) can be seen as the parameter β\betaβ shifts from 0 to 1 in both discrete- and continuous-time cases of the weak convergence theorems. Secondly, we introduce a new class of the DTQW, in which the absolute value of the diagonal parts of the quantum coin is proportional to a power of the inverse of the final time nnn. This is called a final-time-dependent DTQW (FTD-DTQW). The CTQW is obtained in a limit of the FTD-DTQW. We also obtain the weak convergence theorem for the FTD-DTQW which shows a variety of spreading properties. Finally, we consider the FTD-DTQW with periodic position measurements. This weak convergence theorem gives a phase diagram which maps sufficiently long-time behaviors of the discrete- and continuous-time quantum and random walks.
Quantum walks, the quantum mechanical counterpart of classical random walks, is an advanced tool for building quantum algorithms that has been recently shown to constitute a universal model of quantum computation. Quantum walks is now a solid field of research of quantum computation full of exciting open problems for physicists, computer scientists and engineers. In this paper we review theoretical advances on the foundations of both discrete- and continuous-time quantum walks, together with the role that randomness plays in quantum walks, the connections between the mathematical models of coined discrete quantum walks and continuous quantum walks, the quantumness of quantum walks, a summary of papers published on discrete quantum walks and entangle-ment as well as a succinct review of experimental proposals and realizations of discrete-time quantum walks. Furthermore, we have reviewed several algorithms based on both discrete- and continuous-time quantum walks as well as a most important result: the computational universality of both continuous- and discrete-time quantum walks.
Concerning a discrete-time quantum walk Xt(d){X}_{t}^{(d)}Xt(d)​ with a symmetric distribution on the line, whose evolution is described by the Hadamard transformation, it was proved by the author that the following weak limit theorem holds: ${X}_{t}^{(d)}∕t\ensuremath{\rightarrow}dx∕\ensuremath{\pi}(1\ensuremath{-}{x}^{2})\sqrt{1\ensuremath{-}2{x}^{2}}$ as $t\ensuremath{\rightarrow}\ensuremath{\infty}$. The present paper shows that a similar type of weak limit theorem is satisfied for a continuous-time quantum walk Xt(c){X}_{t}^{(c)}Xt(c)​ on the line as follows: ${X}_{t}^{(c)}∕t\ensuremath{\rightarrow}dx∕\ensuremath{\pi}\sqrt{1\ensuremath{-}{x}^{2}}$ as $t\ensuremath{\rightarrow}\ensuremath{\infty}$. These results for quantum walks form a striking contrast to the central limit theorem for symmetric discrete- and continuous-time classical random walks: ${Y}_{t}∕\sqrt{t}\ensuremath{\rightarrow}{e}^{\ensuremath{-}{x}^{2}∕2}dx∕\sqrt{2\ensuremath{\pi}}$ as $t\ensuremath{\rightarrow}\ensuremath{\infty}$. The work deals also with the issue of the relationship between discrete and continuous-time quantum walks. This topic, subject of a long debate in the previous literature, is treated within the formalism of matrix representation and the limit distributions are exhaustively compared in the two cases.
The discrete time quantum walk (DTQW) is a universal quantum computational model. Significant relationships between discrete and corresponding continuous quantum systems have been studied since the work of Pauli and Feynman. This work continues the study of relationships between discrete quantum models and their ostensive continuum counterparts by developing a formal transition between discrete and continuous quantum systems through a formal framework for continuum limits of the DTQW. Under this framework, we prove two constructive theorems concerning which internal discrete transitions ("coins") admit nontrivial continuum limits. We additionally prove that the continuous space limit of the continuous time limit of the DTQW can only yield massless states which obey the Dirac equation. Finally, we demonstrate that the continuous time limit of the DTQW can be identified with the canonical continuous time quantum walk (CTQW) when the coin is allowed to transition through the continuous limit process.