Quantum walks with memory - goldfish, elephants and wise old men
arXiv:1212.4540 · doi:10.1103/PhysRevA.87.052302
Abstract
Quantum walks have emerged as an interesting approach to quantum information processing, exhibiting many unique properties compared to the analogous classical random walk. Here we introduce a model for a discrete-time quantum walk with memory by endowing the walker with multiple recycled coins and using a physical memory function via a history dependent coin flip. By numerical simulation we observe several phenomena. First in one dimension, walkers with memory have persistent quantum ballistic speed up over classical walks just as found in previous studies of multi-coined walks with trivial memory function. However, measurement of the multi-coin state can dramatically shift the mean of the spatial distribution. Second, we consider spatial entanglement in a two-dimensional quantum walk with memory and find that memory destroys entanglement between the spatial dimensions, even when entangling coins are employed. Finally, we explore behaviour in the presence of spatial randomness and find that in contrast to single coined walks, multi-coined walks do not localise and in fact a memory function can speed up the walk relative to a fully decohered multi-coin walker with trivial memory. We explicitly show how to construct linear optics circuits implementing the walks, and discuss prospects for classical simulation.
References in corpus (37)
- Review article: Linear optical quantum computing
- Measurement-based quantum computation with cluster states
- Quantum random walks - an introductory overview
- A Quantum Random Walk Search Algorithm
- Universal computation by quantum walk
- Quantum walks of correlated particles
- Quantum walks: a comprehensive review
- Spatial search by quantum walk
- Photons Walking the Line: A quantum walk with adjustable coin operations
- Two-particle bosonic-fermionic quantum walk via 3D integrated photonics
- Realization of quantum walks with negligible decoherence in waveguide lattices
- Universal quantum computation using the discrete time quantum walk
- Universal computation by multi-particle quantum walk
- A 2D Quantum Walk Simulation of Two-Particle Dynamics
- Discrete single-photon quantum walks with tunable decoherence
- Decoherence and disorder in quantum walks: From ballistic spread to localization
- Elephants can always remember: Exact long-range memory effects in a non-Markovian random walk
- Decoherence in quantum walks - a review
- Quantum Walks driven by many coins
- The quantum to classical transition for random walks
- Faster quantum walk algorithm for the two dimensional spatial search
- Quantum random walks with decoherent coins
- Asymptotic evolution of quantum walks with random coin
- Simulating quantum statistics with entangled photons: a continuous transition from bosons to fermions
- Disordered Quantum Walks in one lattice dimension
- Multi-walker discrete time quantum walks on arbitrary graphs, their properties, and their photonic implementation
- Amnestically induced persistence in random walks
- Quantum random walks with history dependence
- Phase-Transition in Binary Sequences with Long-Range Correlations
- Coined quantum walks on percolation graphs
- Current fluctuations in stochastic systems with long-range memory
- Exact moments in a continuous time random walk with complete memory of its history
- Survival probability in a one-dimensional quantum walk on a trapped lattice
- Entanglement dynamics and quasi-periodicity in discrete quantum walks
- Survival Probabilities of History-Dependent Random Walks
- Quantization and Asymptotic Behaviour of Quantum Random Walk on Integers
- Variable survival exponents in history-dependent random walks: hard movable reflector
Cited by in corpus (23)
- Quantum key distribution with quantum walks
- Quantum walk approach to simulating parton showers
- Discrete-time quantum walk with feed-forward quantum coin
- The Elephant Quantum Walk
- Collider Events on a Quantum Computer
- Quantum and random walks as universal generators of probability distributions
- Generic Quantum Walks with Memory
- Fluctuations in interacting particle systems with memory
- Quantum adaptive agents with efficient long-term memories
- Quantum walks with memory on cycles
- Enhancing entanglement with the generalized elephant quantum walk from localized and delocalized states
- Maximal coin-position entanglement generation in a quantum walk for the third step and beyond regardless of the initial state
- Massless Dirac Equation from Fibonacci Discrete-Time Quantum Walk
- Negative correlations can play a positive role in disordered quantum walks
- Quantum walks in two dimensions: controlling directional spreading with entangling coins and tunable disordered step operator
- Persistent quantum walks: dynamic phases and diverging timescales
- History Dependent Quantum Random Walks as Quantum Lattice Gas Automata
- History Dependent Quantum Walk on the Cycle with an Unbalanced Coin
- Steered discrete-time quantum walks for engineering of quantum states
- Self-avoiding quantum walks
- Source Independent Quantum Walk Random Number Generation
- Neighborhood-History Quantum Walk
- One Dimensional Quantum Walks with Two-step Memory