On the Relationship Between Continuous- and Discrete-Time Quantum Walk

2008/10/31 by Andrew M. Childs · 433 citations
Computer Science · Mathematics · Physics and Astronomy · #Cloud Computing and Resource Management #Discrete time and continuous time #Hamiltonian (control theory) #Mathematical optimization #Mathematics #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum algorithm #Quantum mechanics #Quantum walk #Quantum-Dot Cellular Automata #Random walk #Statistical physics #quant-ph

paper · pdf · doi:10.1007/s00220-009-0930-1

published in Communications in Mathematical Physics 294(2), 581-603 (Springer Science+Business Media) · 22 pages. v2: improved presentation, new section on Hamiltonian oracles; v3: published version, with improved analysis of phase estimation

openalex publication_date 2009/10/09 · arxiv created 2009/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

Quantum walk is one of the main tools for quantum algorithms. Defined by analogy to classical random walk, a quantum walk is a time-homogeneous quantum process on a graph. Both random and quantum walks can be defined either in continuous or discrete time. But whereas a continuous-time random walk can be obtained as the limit of a sequence of discrete-time random walks, the two types of quantum walk appear fundamentally different, owing to the need for extra degrees of freedom in the discrete-time case. In this article, I describe a precise correspondence between continuous- and discrete-time quantum walks on arbitrary graphs. Using this correspondence, I show that continuous-time quantum walk can be obtained as an appropriate limit of discrete-time quantum walks. The correspondence also leads to a new technique for simulating Hamiltonian dynamics, giving efficient simulations even in cases where the Hamiltonian is not sparse. The complexity of the simulation is linear in the total evolution time, an improvement over simulations based on high-order approximations of the Lie product formula. As applications, I describe a continuous-time quantum walk algorithm for element distinctness and show how to optimally simulate continuous-time query algorithms of a certain form in the conventional quantum query model. Finally, I discuss limitations of the method for simulating Hamiltonians with negative matrix elements, and present two problems that motivate attempting to circumvent these limitations.

Cited by

• Quantum algorithms for scientific computing
• Fourier extensions for matrix-function block encodings with error-independent subnormalization bounds
• Robustness of periodicity in Grover walks under a magnetic vector potential
• Noise-resilient spatial search with lackadaisical quantum walks
• A Primer on Quantum Machine Learning
• Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision
• Discretization of continuous-time quantum walks via the staggered model with Hamiltonians
• A Quantum Walk Enhanced Grover Search Algorithm for Global Optimization
• Feature Encoding in Quantum Machine Learning: A Survey and Practical Guidelines
• Continuum Limits of Lazy Open Quantum Walks
• Quantum Algorithms for Unsupervised Machine Learning and Neural Networks
• Efficient quantum circuits for dense and non-unitary operators
• Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem
• Hamiltonian Simulation by Uniform Spectral Amplification
• Lazy Quantum Walks with Native Multiqubit Gates
• Quantum-driven sampling of the quasi-uniform distribution via quantum walks
• Quantum support vector machine for big data classification
• Quantum linear systems algorithms: a primer
• Quantum Algorithm for a Convergent Series of Approximations towards the Exact Solution of the Lowest Eigenstates of a Hamiltonian
• Quantum Recommendation Systems
• Randomized Algorithms and Lower Bounds for Quantum Simulation
• Exponential Quantum Advantage for Message Complexity in Distributed Algorithms
• Quantum Algorithms in Cybernetics
• Fast-forwardable Lindbladians imply quantum phase estimation
• Multi-target quantum walk search on Johnson graph
• Quantum Krylov Algorithm for Szegö Quadrature
• Improving time dynamics simulation by sampling the error unitary
• Qubit-optimal quantum phase estimation of block-encoded Hamiltonians
• Optimal quantum simulation of linear non-unitary dynamics
• A Symmetry-Based Taxonomy of Quantum Algorithms
• A Quantum Walk-Driven Algorithm for the Minimum Spanning Tree Problem under a Maximal Degree Constraint
• Memory and interfaces in composite dispersion: A probability amplitude functions theory
• Time-Dependent Hamiltonian Simulation via Time-Independent Dynamics in a Larger Space
• Finding Angles for Quantum Signal Processing with Machine Precision
• On quantum computation of Kloosterman sums
• Quantum Fractional Revival on Graphs
• Quantum Fast-Forwarding: Markov Chains and Graph Property Testing
• Quantum Machine Learning For Classical Data
• Quantum walk on a spin network
• Efficient implementation of unitary transformations
• Two Variations of Quantum Phase Estimation for Reducing Circuit Error Rates: Application to the Harrow--Hassidim--Lloyd Algorithm
• Uniform semiclassical observable error bound of Trotterization without the Egorov theorem: a simple algebraic proof
• Controllability of Quantum Walks on Graphs
• Quantum state transfer and periodicity in discrete-time quantum walks under non--Markovian dephasing noise
• Deterministic quantum search on all Laplacian integral graphs
• A universal adiabatic quantum query algorithm
• Search of clustered marked states with lackadaisical quantum walks
• Quantum stabilizer codes from Abelian and non-Abelian groups association schemes
• Ab initio many-fermion structure calculations on a quantum computer
• Quantum algorithms for formula evaluation
• Toward the first quantum simulation with quantum speedup
• Decoherence in one-dimensional Quantum Walk
• Eigenbasis of the Evolution Operator of 2-Tessellable Quantum Walks
• On the relationships between Z-, C-, and H-local unitaries
• Simulating Sparse Hamiltonians with Star Decompositions
• Approximating fractional time quantum evolution
• Quantum oracles for the finite element method
• Simulating quantum dynamics on a quantum computer
• High-order quantum algorithm for solving linear differential equations
• Emerging quantum computing algorithms for quantum chemistry
• ASYMPTOTIC ENTANGLEMENT IN 1D QUANTUM WALKS WITH A TIME-DEPENDENT COINED
• Quantum phase discrimination with applications to quantum search on graphs
• Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters
• Lazy open quantum walks
• Efficient quantum circuits for continuous-time quantum walks on composite graphs
• Simulating Hamiltonian Dynamics with a Truncated Taylor Series
• Connection between continuous and discrete time quantum walks. From D-dimensional lattices to general graphs
• Empirical determination of the simulation capacity of a near-term quantum computer
• Separating Geometry From Interference in Constrained Quantum Optimization
• Quantum gradient descent for linear systems and least squares
• Toward pricing financial derivatives with an IBM quantum computer
• Quantum error correction via multi-particle discrete-time quantum walk
• Element distinctness revisited
• Efficient quantum circuits for dense circulant and circulant like operators. [europepmc]
• Discrete-Time Quantum Walk with Phase Disorder: Localization and Entanglement Entropy. [europepmc]
• Biology and medicine in the landscape of quantum advantages. [europepmc]
• Efficient and practical Hamiltonian simulation from time-dependent product formulas. [europepmc]

Related

• Quantum walks: a comprehensive review
• Application of graph theory in quantum computer science
• Quantum Algorithms and Covering Spaces
• Exact simulation of coined quantum walks with the continuous-time model
• Discrete-Time Quantum Walk - Dynamics and Applications