Continuous Limit of Discrete Quantum Walks

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 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 {\it coined} continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at spatial search by a DTQW over the 2-D torus (a grid with periodic boundary conditions) of size $\sqrt{N}\times \sqrt{N}$, where it was shown \nocite{AAmbainis08} that a coined DTQW can search in time $O(\sqrt{N}\log N)$, but a standard CTQW \nocite{Childs2004} takes $\Omega (N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2-D torus exhibits the $O(\sqrt{N}\log N)$ 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 \cite{HariKrovi2007}.

arXiv comment7 pages, RevTeX format

References in corpus (14)

• Quantum random walks - an introductory overview
• Quantum Computation and Decision Trees
• A Quantum Random Walk Search Algorithm
• Spatial search by quantum walk
• From quantum cellular automata to quantum lattice gases
• An example of the difference between quantum and classical random walks
• On the relationship between continuous- and discrete-time quantum walk
• Connecting the discrete and continuous-time quantum walks
• Quantum walks with infinite hitting times
• Quantum walks on quotient graphs
• Quantum Random Walks do not need a Coin Toss
• Discrete-time quantum walks: continuous limit and symmetries
• Span-program-based quantum algorithm for evaluating formulas
• Connection Between Continuous and Discrete Time Quantum Walks on d-Dimensional Lattices; Extensions to General Graphs

Cited by in corpus (8)

• Staggered Quantum Walks on Graphs
• Quantum Search with Multiple Walk Steps per Oracle Query
• Discrete-time quantum walks as fermions of lattice gauge theory
• Massless Dirac Equation from Fibonacci Discrete-Time Quantum Walk
• Discretization of continuous-time quantum walks via the staggered model with Hamiltonians
• Exact simulation of coined quantum walks with the continuous-time model
• Continuous-time limit of topological quantum walks
• How to Teach a Quantum Computer a Probability Distribution