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:1501.06950 · Physical Review A

Continuous limit of discrete quantum walks

M N Dheeraj, Todd A. Brun

Published Jun 5, 2015• 17 citations
arXivHTMLPDF

Abstract

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).

DOI
10.1103/physreva.91.062304

Related papers

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

General methods and properties for evaluation of continuum limits of discrete time quantum walks in one and two dimensions

Michael Manighalam

Models of quantum walks which admit continuous time and continuous spacetime limits have recently led to quantum simulation schemes for simulating fermions in relativistic and non relativistic regimes (Di Molfetta and Arrighi, 2020). This work continues the study of relationships between discrete time quantum walks (DTQW) and their ostensive continuum counterparts by developing a more general framework than was done in (Di Molfetta and Arrighi, 2020) to evaluate the continuous time limit of these discrete quantum systems. Under this framework, we prove two constructive theorems concerning which internal discrete transitions ("coins") admit nontrivial continuum limits in 1D+1. 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. We also demonstrate that for general coins 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 continuum limit process. Finally, we introduce the Plastic Quantum Walk, or a quantum walk which admits both continuous time and continuous spacetime limits and, as a novel result, we use our 1D+1 results to obtain necessary and sufficient conditions concerning which DTQWs admit plasticity in 2D+1, showing the resulting Hamiltonians. We consider coin operators as general 4 parameter unitary matrices, with parameters which are functions of the lattice step size 𝜖. This dependence on 𝜖 encapsulates all functions of 𝜖 for which a Taylor series expansion in 𝜖 is well defined, making our results very general.

•Jan 1, 2021•0 citations

General methods and properties to evaluate continuum limits of the 1D discrete time quantum walk

Michael Manighalam, Mark Kon

Abstract Models of quantum walks which admit continuous time and continuous spacetime limits have recently led to quantum simulation schemes for simulating fermions in relativistic and nonrelativistic regimes (Molfetta GD, Arrighi P. A quantum walk with both a continuous-time and a continuous-spacetime limit, 2019). This work continues the study of relationships between discrete time quantum walks (DTQW) and their ostensive continuum counterparts by developing a more general framework than was done in Molfetta and Arrighi (A quantum walk with both a continuous-time and a continuous-spacetime limit, 2019) to evaluate the continuous time limit of these discrete quantum systems. 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 for general coins the continuous time limit of the DTQW can be identified with the canonical continuous time quantum walk when the coin is allowed to transition through the continuous limit process.

Quantum Information Processing•Oct 1, 2020•4 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

Generic quantum walk using a coin-embedded shift operator

C. M. Chandrashekar

The study of quantum walk processes has been widely divided into two standard variants, the discrete-time quantum walk (DTQW) and the continuous-time quantum walk (CTQW). The connection between the two variants has been established by considering the limiting value of the coin operation parameter in the DTQW, and the coin degree of freedom was shown to be unnecessary [F. W. Strauch, Phys. Rev. A 74, 030301(R) (2006)]. But the coin degree of freedom is an additional resource which can be exploited to control the dynamics of the QW process. In this paper we present a generic quantum walk model using a quantum coin-embedded unitary shift operation ${U}_{C}$. The standard version of the DTQW and the CTQW can be conveniently retrieved from this generic model, retaining the features of the coin degree of freedom in both variants.

arXiv:0810.1556•Physical Review A•Nov 5, 2008•10 citations

Connection Between Continuous and Discrete Time Quantum Walks on d-Dimensional Lattices; Extensions to General Graphs

I obtain the dynamics of the continuous time quantum walk on a d-dimensional lattice, with periodic boundary conditions, as an appropriate limit of the dynamics of the discrete time quantum walk on the same lattice. This extends the main result of [8] which proved this limit for the case of the quantum walk on the infinite line and the quantum cellular automaton proposed in [1]. By highlighting the main features of the limiting procedure, I then extend it to general graphs. For a given discrete time quantum walk on a general graph, I single out the type of continuous dynamics (Hamiltonians) that can be obtained as a limit of the discrete time dynamics. 1 Generalities on quantum walks; continuous and discrete time Consider a graph G: = {V, E} with a set of vertices V of cardinality N and a set of edges E. We assume G to be undirected and without self-loops. In the interval of time ∆t a certain fraction γ∆t of a quantity pj leaves the location of the j-th vertex to move to a neighboring vertex k. The quantity pj, j = 1,..., N, at time t + ∆t is given by 1 pj(t + ∆t) = pj(t) − deg (j)γ∆tpj(t) + ∑ (k,j)∈E γ∆tpk(t). (1) Define ⃗p the N−vector whose components are the pj’s quantities, and L the Laplacian matrix defined by Ljj = − deg (j), Ljk = 1 if (j, k) ∈ E and Ljk = 0 otherwise. L is

•Jan 1, 2009•11 citations
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 N\ifmmode×\else\texttimes\fiN\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}N​\ifmmode×\else\texttimes\fiN​, 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 \ensuremathΩ(N)\mathrm{\ensuremath{\Omega}}(N)\ensuremathΩ(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).
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.
Models of quantum walks which admit continuous time and continuous spacetime limits have recently led to quantum simulation schemes for simulating fermions in relativistic and non relativistic regimes (Di Molfetta and Arrighi, 2020). This work continues the study of relationships between discrete time quantum walks (DTQW) and their ostensive continuum counterparts by developing a more general framework than was done in (Di Molfetta and Arrighi, 2020) to evaluate the continuous time limit of these discrete quantum systems. Under this framework, we prove two constructive theorems concerning which internal discrete transitions ("coins") admit nontrivial continuum limits in 1D+1. 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. We also demonstrate that for general coins 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 continuum limit process. Finally, we introduce the Plastic Quantum Walk, or a quantum walk which admits both continuous time and continuous spacetime limits and, as a novel result, we use our 1D+1 results to obtain necessary and sufficient conditions concerning which DTQWs admit plasticity in 2D+1, showing the resulting Hamiltonians. We consider coin operators as general 4 parameter unitary matrices, with parameters which are functions of the lattice step size 𝜖. This dependence on 𝜖 encapsulates all functions of 𝜖 for which a Taylor series expansion in 𝜖 is well defined, making our results very general.
Abstract Models of quantum walks which admit continuous time and continuous spacetime limits have recently led to quantum simulation schemes for simulating fermions in relativistic and nonrelativistic regimes (Molfetta GD, Arrighi P. A quantum walk with both a continuous-time and a continuous-spacetime limit, 2019). This work continues the study of relationships between discrete time quantum walks (DTQW) and their ostensive continuum counterparts by developing a more general framework than was done in Molfetta and Arrighi (A quantum walk with both a continuous-time and a continuous-spacetime limit, 2019) to evaluate the continuous time limit of these discrete quantum systems. 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 for general coins the continuous time limit of the DTQW can be identified with the canonical continuous time quantum walk when the coin is allowed to transition through the continuous limit process.
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.
The study of quantum walk processes has been widely divided into two standard variants, the discrete-time quantum walk (DTQW) and the continuous-time quantum walk (CTQW). The connection between the two variants has been established by considering the limiting value of the coin operation parameter in the DTQW, and the coin degree of freedom was shown to be unnecessary [F. W. Strauch, Phys. Rev. A 74, 030301(R) (2006)]. But the coin degree of freedom is an additional resource which can be exploited to control the dynamics of the QW process. In this paper we present a generic quantum walk model using a quantum coin-embedded unitary shift operation UC{U}_{C}UC​. The standard version of the DTQW and the CTQW can be conveniently retrieved from this generic model, retaining the features of the coin degree of freedom in both variants.
I obtain the dynamics of the continuous time quantum walk on a d-dimensional lattice, with periodic boundary conditions, as an appropriate limit of the dynamics of the discrete time quantum walk on the same lattice. This extends the main result of [8] which proved this limit for the case of the quantum walk on the infinite line and the quantum cellular automaton proposed in [1]. By highlighting the main features of the limiting procedure, I then extend it to general graphs. For a given discrete time quantum walk on a general graph, I single out the type of continuous dynamics (Hamiltonians) that can be obtained as a limit of the discrete time dynamics. 1 Generalities on quantum walks; continuous and discrete time Consider a graph G: = {V, E} with a set of vertices V of cardinality N and a set of edges E. We assume G to be undirected and without self-loops. In the interval of time ∆t a certain fraction γ∆t of a quantity pj leaves the location of the j-th vertex to move to a neighboring vertex k. The quantity pj, j = 1,..., N, at time t + ∆t is given by 1 pj(t + ∆t) = pj(t) − deg (j)γ∆tpj(t) + ∑ (k,j)∈E γ∆tpk(t). (1) Define ⃗p the N−vector whose components are the pj’s quantities, and L the Laplacian matrix defined by Ljj = − deg (j), Ljk = 1 if (j, k) ∈ E and Ljk = 0 otherwise. L is