2015/01/27 by Dheeraj M N, Todd A. Brun
Physics and Astronomy · #quant-ph
paper · pdf · doi:10.1103/physreva.91.062304
published as Phys. Rev. A 91, 062304 (2015) · 7 pages, RevTeX format
arxiv created 2015/01/27 · arxiv updated 2015/06/10
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 √(N)×√(N), where it was shown \nociteAAmbainis08 that a coined DTQW can search in time O(√(N)logN), but a standard CTQW \nociteChilds2004 takes Ω(N) time to search for a marked element. The continuous limit of the DTQW search over the 2-D torus exhibits the 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 \citeHariKrovi2007.