A random walk approach to quantum algorithms
arXiv:quant-ph/0609035 · doi:10.1098/rsta.2006.1901
Abstract
The development of quantum algorithms based on quantum versions of random walks is placed in the context of the emerging field of quantum computing. Constructing a suitable quantum version of a random walk is not trivial: pure quantum dynamics is deterministic, so randomness only enters during the measurement phase, i.e., when converting the quantum information into classical information. The outcome of a quantum random walk is very different from the corresponding classical random walk, due to interference between the different possible paths. The upshot is that quantum walkers find themselves further from their starting point on average than a classical walker, and this forms the basis of a quantum speed up that can be exploited to solve problems faster. Surprisingly, the effect of making the walk slightly less than perfectly quantum can optimize the properties of the quantum walk for algorithmic applications. Looking to the future, with even a small quantum computer available, development of quantum walk algorithms might proceed more rapidly than it has, especially for solving real problems.
14 pages, 4 figures, introductory level, to appear in 2006 Triennial Issue of Phil. Trans. R. Soc. A
References in corpus (22)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Improved Simulation of Stabilizer Circuits
- Multiple Particle Interference and Quantum Error Correction
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- Exponential algorithmic speedup by quantum walk
- Controlling discrete quantum walks: coins and intitial states
- Quantum random walks in optical lattices
- Decoherence can be useful in quantum walks
- Quantum Simulations on a Quantum Computer
- Quantum walk on the line as an interference phenomenon
- An introduction to measurement based quantum computation
- Localization and its consequences for quantum walk algorithms and quantum communication
- On the absence of homogeneous scalar unitary cellular automata
- Threshold Accuracy for Quantum Computation
- Limitations of Quantum Simulation Examined by Simulating a Pairing Hamiltonian using Nuclear Magnetic Resonance
- Quantum walks with infinite hitting times
- Climbing Mount Scalable: Physical-Resource Requirements for a Scalable Quantum Computer
- Complementarity and quantum walks
- The Hidden Subgroup Problem - Review and Open Problems
- Fault Tolerant Quantum Computation with Constant Error
- Status of and performance estimates for QCDOC
Cited by in corpus (63)
- Quantum walks: a comprehensive review
- Realization of quantum walks with negligible decoherence in waveguide lattices
- Decoherence in quantum walks - a review
- Quantum speed-up in collisional battery charging
- Quantum Navigation and Ranking in Complex Networks
- Recurrence properties of unbiased coined quantum walks on infinite -dimensional lattices
- Nonlinear optical Galton board
- Two quantum walkers sharing coins
- Journeys from Quantum Optics to Quantum Technology
- Distribution of chirality in the quantum walk: Markov process and entanglement
- Complex Quantum Networks: a Topical Review
- Implementing Parrondo's paradox with two coin quantum walks
- Quantum Analogue Computing
- Quantum search algorithms on a regular lattice
- Directional correlations in quantum walks with two particles
- Tailoring discrete quantum walk dynamics via extended initial conditions: Towards homogeneous probability distributions
- Quantum search on graphene lattices
- Controlling quantum random walk with a step-dependent coin
- Quantum walks with sequential aperiodic jumps
- Quantum learning by measurement and feedback
- Green's function approach for quantum graphs: an overview
- Recurrences in three-state quantum walks on a plane
- Superdiffusive quantum stochastic walk definable of arbitrary directed graph
- Efficient simulation of sparse Markovian quantum dynamics
- Hybrid classical-quantum linear solver using Noisy Intermediate-Scale Quantum machines
- Quantum state revivals in quantum walks on cycles
- Full-revivals in 2-D Quantum Walks
- Continuous-time quantum walks on dynamical percolation graphs
- Approximating the quantum approximate optimization algorithm with digital-analog interactions
- Electric quantum walks in two dimensions
- Quantum walks: decoherence and coin-flipping games
- N-dimensional alternate coined quantum walks from a dispersion relation perspective
- Efficient implementation of discrete-time quantum walks on quantum computers
- Order from chaos in quantum walks on cyclic graphs
- A quantum dynamical approach to matrix Khrushchev's formulas
- Enhancing entanglement with the generalized elephant quantum walk from localized and delocalized states
- One-Dimensional Lazy Quantum walk in Ternary System
- Quantum walks on random lattices: Diffusion, localization and the absence of parametric quantum speed-up
- Quantum search with interacting Bose-Einstein condensates
- Anyonic Quantum Walks
- Some limit laws for quantum walks with applications to a version of the Parrondo paradox
- Understanding and controlling N-dimensional quantum walks via dispersion relations. Application to the 2D and 3D Grover walks: Diabolical points and more
- Negative correlations can play a positive role in disordered quantum walks
- Continuous-time quantum walks in the presence of a quadratic perturbation
- Green function approach for scattering quantum walks
- Quantum walk, entanglement and thermodynamic laws
- Chirality from quantum walks without quantum coin
- Implementation of the quantum walk step operator in lateral quantum dots
- The walker speaks its graph: global and nearly-local probing of the tunnelling amplitude in continuous-time quantum walks
- Quantum Algorithm for Smoothed Particle Hydrodynamics
- Search of clustered marked states with lackadaisical quantum walks
- Resonant quantum kicked rotor with two internal levels
- Optimizing the walk coin in the quantum random walk search algorithm through machine learning
- Quantum walk on a chimera graph
- Steered discrete-time quantum walks for engineering of quantum states
- Superdiffusivity of quantum walks: A Feynman sum-over-paths description
- Experimental quantum state transfer of an arbitrary single-qubit state on a cycle with four vertices using a coined quantum random walk
- Two-particle coined-quantum walk with long-range interaction
- Optimality in Quantum Data Compression using Dynamical Entropy
- Strong analog classical simulation of coherent quantum dynamics
- A generalization of Schur functions: applications to Nevanlinna functions, orthogonal polynomials, random walks and unitary and open quantum walks
- Spectral quantization of discrete random walks on half-line, and orthogonal polynomials on the unit circle
- Faster Search of Clustered Marked States with Lackadaisical Quantum Walks