Quantum walks on general graphs
arXiv:quant-ph/0306140 · doi:10.1142/S0219749906002195
Abstract
Quantum walks, both discrete (coined) and continuous time, on a general graph of N vertices with undirected edges are reviewed in some detail. The resource requirements for implementing a quantum walk as a program on a quantum computer are compared and found to be very similar for both discrete and continuous time walks. The role of the oracle, and how it changes if more prior information about the graph is available, is also discussed.
8 pages, v2: substantial rewrite improves clarity, corrects errors and omissions; v3: removes major error in final section and integrates remainder into other sections, figures removed
References in corpus (8)
- A Quantum Random Walk Search Algorithm
- Spatial search by quantum walk
- Experimental Implementation of Discrete Time Quantum Random Walk on an NMR Quantum Information Processor
- Controlling discrete quantum walks: coins and intitial states
- Quantum random walks in optical lattices
- Quantum quincunx in cavity quantum electrodynamics
- Spatial search and the Dirac equation
- Complementarity and quantum walks
Cited by in corpus (57)
- Quantum walks: a comprehensive review
- Universal quantum computation using the discrete time quantum walk
- Decoherence in quantum walks - a review
- Hitting time for quantum walks on the hypercube
- Limit distributions of two-dimensional quantum walks
- Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
- Quantum walks on quotient graphs
- Hitting time for the continuous quantum walk
- Quantum Walks, Quantum Gates and Quantum Computers
- Quantum Walks
- Wigner formula of rotation matrices and quantum walks
- Green's function approach for quantum graphs: an overview
- Equivalence between discrete quantum walk models in arbitrary topologies
- Scattering model for quantum random walk on the hypercube
- Entanglement dynamics and quasi-periodicity in discrete quantum walks
- Bloch-Landau-Zener dynamics induced by a synthetic field in a photonic quantum walk
- Quantum walks on complex networks with connection instabilities and community structure
- Continuous-time quantum walks on planar lattices and the role of the magnetic field
- Quantum walk on a cylinder
- Percolated quantum walks with a general shift operator: From trapping to transport
- Dirac equation with ultraviolet cutoff and quantum walk
- Nonreversal and nonrepeating quantum walks
- Quantum scattering theory on graphs with tails
- One-Dimensional Quantum Walks with a Position-Dependent Coin
- Quantum walks and their algorithmic applications
- The quantum walk search algorithm: Factors affecting efficiency
- Continuous-time quantum walks in the presence of a quadratic perturbation
- Strong Cospectrality and Twin Vertices in Weighted Graphs
- Discrete dynamics and non-Markovianity
- Green function approach for scattering quantum walks
- Quantum state transfer between twins in weighted graphs
- Study of Quantum Walk over a Square Lattice
- Cycle discrete-time quantum walks on a noisy quantum computer
- Coin dimensionality as a resource in quantum metrology involving discrete-time quantum walks
- Identifying network topologies via quantum walk distributions
- Boundary-induced coherence in the staggered quantum walk on different topologies
- An Infinite Family of Circulant Graphs with Perfect State Transfer in Discrete Quantum Walks
- Enhanced quantum transport in chiral quantum walks
- Scoring Anomalous Vertices Through Quantum Walks
- Pretty good state transfer on double stars
- Where to quantum walk
- Quantum Walk Inspired Neural Networks for Graph-Structured Data
- Perfect state transfer, integral circulants and join of graphs
- Discrete-Time Quantum Walks and Graph Structures
- Quantum Walks on Embeddings
- Perfect state transfer, graph products and equitable partitions
- State Transfer on Graphs
- Bosonic Random Walk Networks for Graph Learning
- The expressive power of quantum walks in terms of language acceptance
- Perfect state transfer on quotient graphs
- Mixing of Quantum Walks on Generalized Hypercubes
- Formal languages analysed by quantum walks
- Local Probability Conservation in Discrete Time Quantum Walks
- Non-uniform mixing of quantum walk on cycles
- Cycle Spaces of Digraphs
- State transfer in Grover walks on unitary and quadratic unitary Cayley graphs over finite commutative rings
- Factoring Discrete Quantum Walks on Distance Regular Graphs into Continuous Quantum Walks