On the relationship between continuous- and discrete-time quantum walk
From MaRDI portal
Publication:625458
DOI10.1007/S00220-009-0930-1zbMATH Open1207.81029arXiv0810.0312OpenAlexW2098948451WikidataQ56813120 ScholiaQ56813120MaRDI QIDQ625458FDOQ625458
Authors: Andrew M. Childs 
Publication date: 17 February 2011
Published in: Communications in Mathematical Physics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0810.0312
Recommendations
- Simulating continuous-time Hamiltonian dynamics by way of a discrete-time quantum walk
- QUANTUM WALKS ON GENERAL GRAPHS
- Quantum Walks
- Efficient discrete-time simulations of continuous-time quantum query algorithms
- Connection between continuous and discrete time quantum walks. From \(D\)-dimensional lattices to general graphs
Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Quantum mechanics on special spaces: manifolds, fractals, graphs, lattices (81Q35) Quantum stochastic calculus (81S25)
Cites Work
- Universal Quantum Simulators
- Adiabatic quantum state generation and statistical zero knowledge
- Exponential algorithmic speedup by a quantum walk
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Faster quantum-walk algorithm for the two-dimensional spatial search
- Efficient quantum algorithms for simulating sparse Hamiltonians
- From quantum cellular automata to quantum lattice gases
- Quantum complexity of testing group commutativity
- Coins make quantum walks faster
- Title not available (Why is that?)
- Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
- Spatial search and the Dirac equation
- Title not available (Why is that?)
- Quantum verification of matrix products
- One-dimensional quantum walks
- Quantum walks on graphs
- Quantum Walk Algorithm for Element Distinctness
- On Some Exponential Sums
- Quantum simulations of classical random walks and undirected graph connectivity
- Locality in Distributed Graph Algorithms
- On the absence of homogeneous scalar unitary cellular automata.
- An example of the difference between quantum and classical random walks
- Title not available (Why is that?)
- Quantum lower bounds for the collision and the element distinctness problems
- Efficient discrete-time simulations of continuous-time quantum query algorithms
- Optimal phase estimation in quantum networks
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Digraph of a Unitary Matrix
- Quantum computation of zeta functions of curves
- Span-program-based quantum algorithm for evaluating formulas
- Quantum algorithms for the triangle problem
- Title not available (Why is that?)
Cited In (98)
- Quantum computation and quantum information
- Mimicking the Hadamard discrete-time quantum walk with a time-independent Hamiltonian
- Arbitrated quantum signature scheme with quantum walk-based teleportation
- Faster search of clustered marked states with lackadaisical quantum walks
- Simplifying continuous-time quantum walks on dynamic graphs
- Quantum multi-secret sharing via trap codes and discrete quantum walks
- Quantum support vector machine based on gradient descent
- Element distinctness revisited
- An all-pair quantum SVM approach for big data multiclass classification
- Strong convergence of quantum random walks via semigroup decomposition
- Graph matching using the interference of continuous-time quantum walks
- Quantum algorithm design: techniques and applications
- Bounding the costs of quantum simulation of many-body physics in real space
- Quantum walk and its application domains: a systematic review
- Speed and entropy of an interacting continuous time quantum walk
- Quantum walks and elliptic integrals
- Quantum blind signature scheme based on quantum walk
- Quantum recommendation systems
- The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
- A quantum walk with both a continuous-time limit and a continuous-spacetime limit
- General methods and properties to evaluate continuum limits of the 1D discrete time quantum walk
- Relation between two-phase quantum walks and the topological invariant
- Efficient discrete-time simulations of continuous-time quantum query algorithms
- Fast black-box quantum state preparation based on linear combination of unitaries
- Simulation of three-spin evolution under \(XX\) Hamiltonian on quantum processor of IBM-quantum experience
- Analytical expression for variance of homogeneous-position quantum walk with decoherent position
- Discrete-time quantum walks: continuous limit and symmetries
- Unveiling and exemplifying the unitary equivalence of discrete time quantum walk models
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- On the efficiency of quantum algorithms for Hamiltonian simulation
- On the von Neumann entropy of certain quantum walks subject to decoherence
- Survival of classical and quantum particles in the presence of traps
- Crossovers induced by discrete-time quantum walks
- Wave packet spreading with periodic, Fibonacci quasiperiodic, and random nonlinear discrete-time quantum walks
- Controllability of quantum walks on graphs
- Birth and death processes and quantum spin chains
- Eigenbasis of the evolution operator of 2-tessellable quantum walks
- Quantum walks: a comprehensive review
- Random walk quantum clustering algorithm based on space
- Factoring discrete-time quantum walks on distance regular graphs into continuous-time quantum walks
- One-dimensional continuous-time quantum walks
- Quantum spectral methods for differential equations
- A method for exact simulation of quantum dynamics
- \textit{pyCTQW}: a continuous-time quantum walk simulator on distributed memory computers
- Hitting time of quantum walks with perturbation
- Directional correlations in quantum walks with two particles
- Quantum fractional revival on graphs
- Quantum circuit design for accurate simulation of qudit channels
- Continuous-time quantum random walks require discrete space
- Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
- Pseudo-Hermitian continuous-time quantum walks
- Controllability of system dynamics on networks, quantum walks and random walks
- Quantum Walks: A Markovian Perspective
- Grover search with lackadaisical quantum walks
- Thermalization in many-particle quantum walks
- Dynamics of continuous-time quantum walks in restricted geometries
- Relativistic effects and rigorous limits for discrete- and continuous-time quantum walks
- A complete characterization of unitary quantum space
- Exact simulation of coined quantum walks with the continuous-time model
- EXPONENTIAL IMPROVEMENT IN PRECISION FOR SIMULATING SPARSE HAMILTONIANS
- Discretization of continuous-time quantum walks via the staggered model with Hamiltonians
- Approximate locality for quantum systems on graphs
- Exact solutions and symmetry analysis for the limiting probability distribution of quantum walks
- Investigation of continuous-time quantum walk via modules of Bose–Mesner and Terwilliger algebras
- Asymptotic entanglement in 1D quantum walks with a time-dependent coined
- Limitations of discrete-time quantum walk on a one-dimensional infinite chain
- A weak limit theorem for a class of long-range-type quantum walks in 1d
- Brownian-Huygens propagation: modeling wave functions with discrete particle-antiparticle random walks
- Transport and localization in quantum walks on a random hierarchy of barriers
- Simulating continuous-time Hamiltonian dynamics by way of a discrete-time quantum walk
- QUANTUM WALKS ON GENERAL GRAPHS
- Connection between continuous and discrete time quantum walks. From \(D\)-dimensional lattices to general graphs
- Controlled transport in chiral quantum walks on graphs
- Search algorithm on strongly regular graph by lackadaisical quantum walk
- Perfect state transfer in quantum walks on orientable maps
- The spectrum of asymptotic Cayley trees
- Quantum walks as thermalisations, with application to fullerene graphs
- Quantum algorithms for multiscale partial differential equations
- Operations with elements of transferred density matrix via unitary transformations on extended receiver
- Computing scalar products via a two-terminal quantum transmission line
- Abstract model of continuous-time quantum walk based on Bernoulli functionals and perfect state transfer
- Quantum circuits for discrete-time quantum walks with position-dependent coin operator
- Quantum support vector machine based on regularized Newton method
- An introduction to quantum computing for statisticians and data scientists
- Quantum walk on a toral phase space
- Efficient quantum circuits for continuous-time quantum walks on composite graphs
- Lackadaisical discrete-time quantum walk on Johnson graph
- Solving systems of linear algebraic equations via unitary transformations on quantum processor of IBM quantum experience
- Recovering the original simplicity: succinct and exact quantum algorithm for the welded tree problem
- Quantum walk on a comb with infinite teeth
- Correlation between the continuous-time quantum walk and cliques in graphs and its application
- Spectral quantization of discrete random walks on half-line and orthogonal polynomials on the unit circle
- The Hamiltonians generating one-dimensional discrete-time quantum walks
- Overview: recent development and applications of reduction and lackadaisicalness techniques for spatial search quantum walk in the near term
- Ranking nodes in directed networks via continuous-time quantum walks
- How to realize one-dimensional discrete-time quantum walk by Dirac particle
- Perfect edge state transfer on cubelike graphs
- Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices
This page was built for publication: On the relationship between continuous- and discrete-time quantum walk
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q625458)
