Framework for discrete-time quantum walks and a symmetric walk on a binary tree
arXiv:1107.4201 · doi:10.1103/PhysRevA.84.032311
Abstract
We formulate a framework for discrete-time quantum walks, motivated by classical random walks with memory. We present a specific representation of the classical walk with memory 2 on which this is based. The framework has no need for coin spaces, it imposes no constraints on the evolution operator other than unitarity, and is unifying of other approaches. As an example we construct a symmetric discrete-time quantum walk on the semi-infinite binary tree. The generating function of the amplitude at the root is computed in closed-form, as a function of time and the initial level n in the tree, and we find the asymptotic and a full numerical solution for the amplitude. It exhibits a sharp interference peak and a power law tail, as opposed to the exponentially decaying tail of a broadly peaked distribution of the classical symmetric random walk on a binary tree. The probability peak is orders of magnitude larger than it is for the classical walk (already at small n). The quantum walk shows a polynomial algorithmic speedup in n over the classical walk, which we conjecture to be of the order 2/3, based on strong trends in data.
arXiv comment13 pages, 8 pdf figures, revtex4-1. Published version (minor editorial changes throughout; "log" changed to "ln" in Appendix). This arXiv version contains some hyperlinks (to references) not available in the journal. 12 journal pages
References in corpus (37)
- Quantum random walks - an introductory overview
- Quantum Computation and Decision Trees
- Universal computation by quantum walk
- Quantum walks of correlated particles
- Environment-Assisted Quantum Transport
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- Photons Walking the Line: A quantum walk with adjustable coin operations
- Classical simulation of quantum many-body systems with a tree tensor network
- Exploring Topological Phases With Quantum Walks
- From quantum cellular automata to quantum lattice gases
- Realization of a quantum walk with one and two trapped ions
- Quantum walk of a trapped ion in phase space
- On the relationship between continuous- and discrete-time quantum walk
- Discrete single-photon quantum walks with tunable decoherence
- Decoherence and disorder in quantum walks: From ballistic spread to localization
- Continuous-Time Quantum Walks: Models for Coherent Transport on Complex Networks
- Experimental Implementation of Discrete Time Quantum Random Walk on an NMR Quantum Information Processor
- Controlling discrete quantum walks: coins and intitial states
- Quantum Walks driven by many coins
- Connecting the discrete and continuous-time quantum walks
- Quantum random walks with decoherent coins
- Optimizing the discrete time quantum walk using a SU(2) coin
- Recurrence and Pólya number of quantum walks
- Survival Probabilities in Coherent Exciton Transfer with Trapping
- Quantum walk on a line for a trapped ion
- Quantum walks based on an interferometric analogy
- Recurrence properties of unbiased coined quantum walks on infinite -dimensional lattices
- Quantum searches on highly symmetric graphs
- Quantum random walk on the line as a markovian process
- Quantum walks with random phase shifts
- Critical properties of homogeneous binary trees
- Scattering theory and discrete-time quantum walks
- The Random Walk in Generalized Quantum Theory
- Searching via walking: How to find a marked subgraph of a graph using quantum walks
- Finding structural anomalies in graphs by means of quantum walks
- Emergence of Randomness and Arrow of Time in Quantum Walks
- Grover-like search via Frenkel exciton trapping mechanism
Cited by in corpus (7)
- Quantum walks: a comprehensive review
- Spectral Transition for Random Quantum Walks on Trees
- Quantum walks induced by Dirichlet random walks on infinite trees
- Spectral Properties of Quantum Walks on Rooted Binary Trees
- Spectral and scattering properties of quantum walks on homogenous trees of odd degree
- Optimizing topology for quantum probing with discrete-time quantum walks
- Quantum state transfer and periodicity in discrete-time quantum walks under non--Markovian dephasing noise