Quantum Walks
arXiv:1207.7283 · doi:10.2478/v10155-011-0006-6
Abstract
This tutorial article showcases the many varieties and uses of quantum walks. Discrete time quantum walks are introduced as counterparts of classical random walks. The emphasis is on the connections and differences between the two types of processes (with rather different underlying dynamics) for producing random distributions. We discuss algorithmic applications for graph-searching and compare the two approaches. Next, we look at quantization of Markov chains and show how it can lead to speedups for sampling schemes. Finally, we turn to continuous time quantum walks and their applications, which provide interesting (even exponential) speedups over classical approaches.
arXiv comment124 pages, some typos corrected and sentences rephrased
References in corpus (45)
- Quantum Mechanics helps in searching for a needle in a haystack
- Strengths and Weaknesses of Quantum Computing
- Quantum Amplitude Amplification and Estimation
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- Universal computation by quantum walk
- Exponential algorithmic speedup by quantum walk
- Spatial search by quantum walk
- Quantum computers can search rapidly by using almost any transformation
- Quantum Computation by Adiabatic Evolution
- Universal quantum computation using the discrete time quantum walk
- Universal computation by multi-particle quantum walk
- An example of the difference between quantum and classical random walks
- On the relationship between continuous- and discrete-time quantum walk
- Quantum Metropolis Sampling
- Controlling discrete quantum walks: coins and intitial states
- Decoherence can be useful in quantum walks
- Faster quantum walk algorithm for the two dimensional spatial search
- Quantum Simulations of Classical Annealing Processes
- Quantum Speedup by Quantum Annealing
- Quantum random walks with decoherent coins
- Spatial search and the Dirac equation
- A Quantum-Quantum Metropolis Algorithm
- Quantum Walk on a Line with Two Entangled Particles
- Speed-up via Quantum Sampling
- Quantum walks on general graphs
- Optimized quantum random-walk search algorithms
- Quantum information distributors: Quantum network for symmetric and asymmetric cloning in arbitrary dimension and continuous limit
- Quantum walks based on an interferometric analogy
- Simulating sparse Hamiltonians with star decompositions
- Quantum speedup of classical mixing processes
- Quantum search by measurement
- Quantum searches on highly symmetric graphs
- A Quantum Algorithm for the Hamiltonian NAND Tree
- Quantum walks with random phase shifts
- On the digraph of a unitary matrix
- Quantum Speed-up for Approximating Partition Functions
- Lower Bounds on Quantum Query Complexity
- Analysis of Absorbing Times of Quantum Walks
- Finding structural anomalies in graphs by means of quantum walks
- Universal 2-local Hamiltonian Quantum Computing
- Equivalence between discrete quantum walk models in arbitrary topologies
- Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer
- Local Hamiltonians in Quantum Computation
- Quantum simulated annealing
Cited by in corpus (33)
- Modelling and Simulating the Noisy Behaviour of Near-term Quantum Computers
- The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
- Tweezer-programmable 2D quantum walks in a Hubbard-regime lattice
- Quantum Field as a quantum cellular automaton: the Dirac free evolution in one dimension
- Quantum search on graphene lattices
- Driven Quantum Walks
- The Dirac Quantum Cellular Automaton in one dimension: Zitterbewegung and scattering from potential
- The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
- A Comparison of Quantum Walk Implementations on NISQ Computers
- Finding structural anomalies in star graphs: A general approach
- Central limit theorem for reducible and irreducible open quantum walks
- Solutions of a two-particle interacting quantum walk
- Faster quantum mixing for slowly evolving sequences of Markov chains
- Implementation of quantum compression on IBM quantum computers
- Percolated quantum walks with a general shift operator: From trapping to transport
- Quantum search with interacting Bose-Einstein condensates
- Understanding and controlling N-dimensional quantum walks via dispersion relations. Application to the 2D and 3D Grover walks: Diabolical points and more
- Discrete dynamics and non-Markovianity
- Complete classification of trapping coins for quantum walks on the 2D square lattice
- Finding Structural Anomalies in Star Graphs Using Quantum Walks: A General Approach
- A Simple Method for Finding the Scattering Coefficients of Quantum Graphs
- Upperbounds on the probability of finding marked connected components using quantum walks
- Quantum State Discrimination on Reconfigurable Noise-Robust Quantum Networks
- Two-level Quantum Walkers on Directed Graphs I: Universal Quantum Computing
- Null-eigenvalue localization of quantum walks on real-world complex networks
- Thermal state entanglement entropy on a quantum graph
- Lackadaisical quantum walks on 2D grids with multiple marked vertices
- Quantum walks on embedded hypercubes: Nonsymmetric and nonlocal cases
- Short time behavior of continuous time quantum walks on graphs
- Borromean states in discrete-time quantum walks
- Nonclassical oscillations in pre- and post-selected quantum walks
- Analytical expression for variance of homogeneous-position quantum walk with decoherent position
- Attractors and asymptotic dynamics of open discrete-time quantum walks on cycles