An example of the difference between quantum and classical random walks

Abstract

In this note, we discuss a general definition of quantum random walks on graphs and illustrate with a simple graph the possibility of very different behavior between a classical random walk and its quantum analogue. In this graph, propagation between a particular pair of nodes is exponentially faster in the quantum case.

4 pages, 4 EPS figures, REVTeX

References in corpus (2)

• Quantum Computation and Decision Trees
• On the absence of homogeneous scalar unitary cellular automata

Cited by in corpus (235)

• Quantum random walks - an introductory overview
• Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer
• Perfect state transfer in quantum spin networks
• A Quantum Random Walk Search Algorithm
• Quantum algorithms: an overview
• Quantum walks: a comprehensive review
• Exponential algorithmic speedup by quantum walk
• Environment-Assisted Quantum Transport
• Spatial search by quantum walk
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Perfect Transfer of Arbitrary States in Quantum Spin Networks
• On the relationship between continuous- and discrete-time quantum walk
• Role of quantum coherence in chromophoric energy transport
• Continuous-Time Quantum Walks: Models for Coherent Transport on Complex Networks
• Implementing the quantum random walk
• Experimental Implementation of Discrete Time Quantum Random Walk on an NMR Quantum Information Processor
• Experimental Two-dimensional Quantum Walk on a Photonic Chip
• Quantum Walks driven by many coins
• The quantum to classical transition for random walks
• Connecting the discrete and continuous-time quantum walks
• Open Quantum Random Walks
• Localization of Two-Dimensional Quantum Walks
• Quantum random walks with decoherent coins
• Two-particle quantum walks applied to the graph isomorphism problem
• Hitting time for quantum walks on the hypercube
• Complex Networks from Classical to Quantum
• Limit Theorem for Continuous-Time Quantum Walk on the Line
• Noisy intermediate-scale quantum computers
• Quantum Walks on a Random Environment
• Quantum stochastic walks: A generalization of classical random walks and quantum walks
• Localization and its consequences for quantum walk algorithms and quantum communication
• Experimental Quantum Fast Hitting on Hexagonal Graphs
• Fast Escape from Quantum Mazes in Integrated Photonics
• Coherent exciton transport in dendrimers and continuous-time quantum walks
• Quantum Networks on Cubelike Graphs
• Quantum transport on small-world networks: A continuous-time quantum walk approach
• Quantum walks with infinite hitting times
• Quantum walk approach to search on fractal structures
• Quantum walks: the first detected passage time problem
• Quantum walks on quotient graphs
• Recurrence properties of unbiased coined quantum walks on infinite $d$-dimensional lattices
• Measuring Topological Invariants in Disordered Discrete Time Quantum Walks
• Localization of Multi-State Quantum Walk in One Dimension
• One- and two-dimensional quantum walks in arrays of optical traps
• Quantum random walk on the line as a markovian process
• One dimensional quantum walk with unitary noise
• Quantum transport and localization in 1d and 2d tight-binding lattices
• Spacetime structures of continuous time quantum walks
• Decoherence in Quantum Walks on the Hypercube
• Quantum random walks with history dependence
• Hitting time for the continuous quantum walk
• Free Dirac evolution as a quantum random walk
• Universal quantum computation by discontinuous quantum walk
• Almost uniform sampling via quantum walks
• Universally Optimal Noisy Quantum Walks on Complex Networks
• Quantum Walks, Quantum Gates and Quantum Computers
• Analysis of Absorbing Times of Quantum Walks
• Review on Quantum Walk Computing: Theory, Implementation, and Application
• Quantum Walks
• Quantum walks on graphs representing the firing patterns of a quantum neural network
• A comprehensive review on developments of synthetic dimensions
• Quantum State Transfer in Spin-1 Chains
• Quantum Computing: An Overview Across the System Stack
• Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
• Slow transport by continuous time quantum walks
• Simulating Anderson localization via a quantum walk on a one-dimensional lattice of superconducting qubits
• Asymptotic entanglement in a two-dimensional quantum walk
• Perfect state transfer over distance-regular spin networks
• Perfect quantum state transfer with spinor bosons on weighted graphs
• Non-interacting multi-particle quantum random walks applied to the graph isomorphism problem for strongly regular graphs
• Asymmetries in symmetric quantum walks on two-dimensional networks
• The Power of Adiabatic Quantum Computation with No Sign Problem
• Investigation of continuous-time quantum walk by using Krylov subspace-Lanczos algorithm
• Decoherence and Quantum Walks: anomalous diffusion and ballistic tails
• Quantum Computing for Fusion Energy Science Applications
• Complex networks with complex weights
• A quantum-walk-inspired adiabatic algorithm for graph isomorphism
• Solving the Graph Isomorphism Problem with a Quantum Annealer
• H-theorem in quantum physics
• Continuous-time quantum walks on star graphs
• Continuous-Time Quantum Search on Balanced Trees
• Continuous-time quantum walks on one-dimension regular networks
• Absorption problems for quantum walks in one dimension
• Investigation of Continuous-Time Quantum Walk Via Modules of Bose-Mesner and Terwilliger Algebras
• Green's function approach for quantum graphs: an overview
• Dark states of quantum search cause imperfect detection
• Quantum correlations in continuos-time quantum walks of two indistinguishable particles
• Quantum Walks on Trees with Disorder: Decay, Diffusion, and Localization
• Quantum walks: the first detected transition time
• Generalized quantum-classical correspondence for random walks on graphs
• A graph with fractional revival
• Lattice quantum magnetometry
• Noisy quantum walks of two indistinguishable interacting particles
• Quantum walks on Cayley graphs
• Equivalence between discrete quantum walk models in arbitrary topologies
• Measurement induced quantum walks on an IBM Quantum Computer
• Thermodynamic formalism for dissipative quantum walks
• Non-Unitary Quantum Walks on Hyper-Cycles
• Asymptotic entanglement in 1D quantum walks with a time-dependent coined
• Quantum spatial search in two-dimensional waveguide arrays
• When is a Quantum Cellular Automaton (QCA) a Quantum Lattice Gas Automaton (QLGA)?
• Photonic quantum walks with four-dimensional coins
• Scattering model for quantum random walk on the hypercube
• QSWalk: a Mathematica package for quantum stochastic walks on arbitrary graphs
• Convergence of continuous-time quantum walks on the line
• Relation between Random Walks and Quantum Walks
• Quantum walk algorithm for element distinctness
• Finding paths in tree graphs with a quantum walk
• Limits on Efficient Computation in the Physical World
• Driving quantum systems with repeated conditional measurements
• Quantum central limit theorem for continuous-time quantum walks on odd graphs in quantum probability theory
• Decoherent quantum walks driven by a generic coin operation
• Extraordinary behaviors in two-dimensional decoherent alternative quantum walk
• Discrete spacetime, quantum walks and relativistic wave equations
• Efficient quantum circuits for continuous-time quantum walks on composite graphs
• The effect of quantum noise on algorithmic perfect quantum state transfer on NISQ processors
• Investigation of continuous-time quantum walk on root lattice $A_n$ and honeycomb lattice
• Localization in Quantum Walks on a Honeycomb Network
• Pseudo Memory Effects, Majorization and Entropy in Quantum Random Walks
• Quantum-classical dynamical distance and quantumness of quantum walks
• Unidirectional quantum walks: evolution and exit times
• Uncertainty and symmetry bounds for the quantum total detection probability
• The Road to Quantum Artificial Intelligence
• Link prediction with continuous-time classical and quantum walks
• Quantum-classical distance as a tool to design optimal chiral quantum walk
• Quantum walks on embedded hypercubes
• Continuous Limit of Discrete Quantum Walks
• Robust Quantum Walk Search Without Knowing the Number of Marked Vertices
• Perfect transference of a d-level quantum state over pseudo-distance-regular networks
• Feedback-assisted quantum search by continuous-time quantum walks
• Decoherence in quantum walks and quantum computers
• Transport efficiency of continuous-time quantum walks on graphs
• Properties of Open Quantum Walks on $\mathbb{Z}$
• Classical-like behavior in quantum walks with inhomogeneous, time-dependent coin operators
• Quantum Coarse-Graining, Symmetries and Reducibility of Dynamics
• Coherent chemical kinetics as quantum walks I: Reaction operators for radical pairs
• The Optimal Control Landscape for the Generation of Unitary Transformations with Constrained Dynamics
• A note on graphs resistant to quantum uniform mixing
• Continuous-time quantum walks on planar lattices and the role of the magnetic field
• On limiting distributions of quantum Markov chains
• Discrete-time quantum walks on one-dimensional lattices
• Quantum search with a continuous-time quantum walk in momentum space
• Implementation of a 3 x 3 directionally-unbiased linear optical multiport
• Towards Quantum Computing with Molecular Electronics
• Birth and death processes and quantum spin chains
• Quantum tunneling on graphs
• Transport and Entanglement Generation in the Bose-Hubbard Model
• Highly noise resistant multipartite quantum correlations
• Quantum field theory from a quantum cellular automaton in one spatial dimension and a no-go theorem in higher dimensions
• Grover-like search via Frenkel exciton trapping mechanism
• Diffusion on a heptagonal lattice
• Speed and entropy of an interacting continuous time quantum walk
• Evanescence in Coined Quantum Walks
• Mixing and Decoherence in Continuous-Time Quantum Walks on Cycles
• Quantum search with interacting Bose-Einstein condensates
• Nonreversal and nonrepeating quantum walks
• Noisy Quantum Cellular Automata for Quantum vs Classical Excitation Transfer
• General condition of quantum teleportation by one-dimensional quantum walks
• Parrondo's effect in continuous-time quantum walks
• Quantum Optical Random Walk: Quantization Rules and Quantum Simulation of Asymptotics
• Improved Upper Bounds for the Hitting Times of Quantum Walks
• Invariance in quantum walks with time-dependent coin operators
• Out-of-time-ordered correlators and quantum walks
• Inhibition of spreading in quantum random walks due to quenched Poisson-distributed disorder
• Tree Search and Quantum Computation
• Swift chiral quantum walks
• Continuous-time quantum walks in the presence of a quadratic perturbation
• Directionally-Unbiased Unitary Optical Devices in Discrete-Time Quantum Walks
• Continuous-Time Classical and Quantum Random Walk on Direct Product of Cayley Graphs
• Unveiling and exemplifying the unitary equivalence of discrete time quantum walk models
• Green function approach for scattering quantum walks
• Asymptotics of Quantum Random Walk Driven by Optical Cavity
• Average position in quantum walks with a U(2) coin
• Two component quantum walk in one-dimensional lattice with hopping imbalance
• Study of Quantum Walk over a Square Lattice
• Circuit Design for Clique Problem and Its Implementation on Quantum Computer
• Quantum walk with a general coin: Exact solution and asymptotic properties
• Mixing in Continuous Quantum Walks on Graphs
• Experimental Quantum Simulation of Dynamic Localization on Curved Photonic Lattices
• Coherent spatial control of wave packet dynamics on quantum lattices
• Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks
• Entanglement transfer via Chiral Quantum Walk on a Triangular Chain
• Quantum walk on a chimera graph
• Limit properties of global interaction stochastic quantum walks on directed graphs
• Driven Topological Systems in the Classical Limit
• Quantum random walk in periodic potential on a line
• Which-way interference within biomimetic unit-cells for efficient energy transfer
• Implementation of Continuous-Time Quantum Walk on Sparse Graph
• Quantum walk on a toral phase space
• Quantum transport senses community structure in networks
• Multimarked Spatial Search by Continuous-Time Quantum Walk
• Investigation of the time evolution of entanglement and trace distance in an atom-cavity system described with random walk and non-random walk states
• Quantum Walks on Graphs of the Ordered Hamming Scheme and Spin Networks
• Limit distribution with a combination of density functions for a 2-state quantum walk
• Multiparticle quantum walk: a dynamical probe of topological many-body excitations
• Scoring Anomalous Vertices Through Quantum Walks
• Photonic random walks with traps
• Enhancing quantum state transfer efficiency in binary-tree spin networks by partially collapsing measurements
• Hitting statistics from quantum jumps
• On the Efficiency of Quantum Algorithms for Hamiltonian Simulation
• Two-Particle Scattering on Non-Translation Invariant Line Lattices
• A Rubik's Cube inspired approach to Clifford synthesis
• Dephasing assisted transport on a biomimetic ring structure
• Quantum State Transfer through Noisy Quantum Cellular Automata
• Interference-induced localization in quantum random walk on clean cyclic graph
• Reductions in finite-dimensional quantum mechanics: from symmetries to operator algebras and beyond
• Krylov Spread Complexity of Quantum-Walks
• Influence of coin symmetry on infinite hitting times in quantum walks
• Disorder-free localisation in continuous-time quantum walks : Role of symmetries
• Wormhole Traversability via Quantum Random Walks
• Polarization-path-frequency entanglement using interferometry and frequency shifters
• Quantum vs Classical Birth and Death Processes; Exactly Solvable Examples
• Distributions of continuous-time quantum walks
• Randomized Algorithms and Lower Bounds for Quantum Simulation
• Perfect State Transfer in Weighted Cubelike Graphs
• A $q$-version of the relation between the hypercube, the Krawtchouk chain and Dicke states
• An Entanglement Monotone from the Contextual Fraction
• Quantum walk mixing is faster than classical on periodic lattices
• Limit distribution of a continuous-time quantum walk with a spatially 2-periodic Hamiltonian
• Conductivity measurements in JCH like models
• Robust Quantum Circuit for Clique Problem with Intermediate Qudits
• Invariance in Quantum Walks
• Quantum Algorithms and Covering Spaces
• Quantum Algorithm for Commutativity Testing of a Matrix Set
• Quantum walks assisted by particle number fluctuations
• QWalkVec: Node Embedding by Quantum Walk
• The Hamiltonians generating one-dimensional discrete-time quantum walks
• Quantum walk on a comb with infinite teeth
• Application of graph theory in quantum computer science
• Photon-Number Conserved Universal Quantum Logic Employing Continuous-Time Quantum Walk on Dual-Rail Qubit Arrays
• Quantum walks: a Markovian perspective
• Quantum walk on a ladder
• Universal scaling hypothesis of quantum spatial search in complex networks
• Response to glassy disorder in coin on spread of quantum walker
• Enhanced spreading in continuous-time quantum walks using aperiodic temporal modulation of defects