On the relationship between continuous- and discrete-time quantum walk
From MaRDI portal
(Redirected from Publication:625458)
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.
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
Cites work
- scientific article; zbMATH DE number 5899272 (Why is no real title available?)
- scientific article; zbMATH DE number 5320343 (Why is no real title available?)
- scientific article; zbMATH DE number 5485493 (Why is no real title available?)
- scientific article; zbMATH DE number 2019633 (Why is no real title available?)
- scientific article; zbMATH DE number 2079375 (Why is no real title available?)
- scientific article; zbMATH DE number 2168577 (Why is no real title available?)
- Adiabatic quantum state generation and statistical zero knowledge
- An example of the difference between quantum and classical random walks
- Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
- Coins make quantum walks faster
- Efficient discrete-time simulations of continuous-time quantum query algorithms
- Efficient quantum algorithms for simulating sparse Hamiltonians
- Exponential algorithmic speedup by a quantum walk
- Faster quantum-walk algorithm for the two-dimensional spatial search
- From quantum cellular automata to quantum lattice gases
- Locality in Distributed Graph Algorithms
- On Some Exponential Sums
- On the Digraph of a Unitary Matrix
- On the absence of homogeneous scalar unitary cellular automata.
- One-dimensional quantum walks
- Optimal phase estimation in quantum networks
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Walk Algorithm for Element Distinctness
- Quantum algorithms for the triangle problem
- Quantum complexity of testing group commutativity
- Quantum computation of zeta functions of curves
- Quantum lower bounds for the collision and the element distinctness problems
- Quantum simulations of classical random walks and undirected graph connectivity
- Quantum verification of matrix products
- Quantum walks on graphs
- Span-program-based quantum algorithm for evaluating formulas
- Spatial search and the Dirac equation
- Universal Quantum Simulators
Cited in
(97)- Connection between continuous and discrete time quantum walks. From \(D\)-dimensional lattices to general graphs
- Transport and localization in quantum walks on a random hierarchy of barriers
- Quantum computation and quantum information
- QUANTUM WALKS ON GENERAL GRAPHS
- Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices
- Controlled transport in chiral quantum walks on graphs
- 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
- Search algorithm on strongly regular graph by lackadaisical quantum walk
- Perfect state transfer in quantum walks on orientable maps
- Quantum algorithm design: techniques and applications
- The spectrum of asymptotic Cayley trees
- Quantum walk and its application domains: a systematic review
- Bounding the costs of quantum simulation of many-body physics in real space
- Speed and entropy of an interacting continuous time quantum walk
- Quantum blind signature scheme based on quantum walk
- Quantum walks and elliptic integrals
- Quantum recommendation systems
- Quantum walks as thermalisations, with application to fullerene graphs
- 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
- The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
- Relation between two-phase quantum walks and the topological invariant
- Analytical expression for variance of homogeneous-position quantum walk with decoherent position
- 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
- On the efficiency of quantum algorithms for Hamiltonian simulation
- Discrete-time quantum walks: continuous limit and symmetries
- Computing scalar products via a two-terminal quantum transmission line
- Quantum algorithms for multiscale partial differential equations
- Unveiling and exemplifying the unitary equivalence of discrete time quantum walk models
- Operations with elements of transferred density matrix via unitary transformations on extended receiver
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Abstract model of continuous-time quantum walk based on Bernoulli functionals and perfect state transfer
- On the von Neumann entropy of certain quantum walks subject to decoherence
- Survival of classical and quantum particles in the presence of traps
- Wave packet spreading with periodic, Fibonacci quasiperiodic, and random nonlinear discrete-time quantum walks
- Crossovers induced by discrete-time quantum walks
- Controllability of quantum walks on graphs
- Quantum circuits for discrete-time quantum walks with position-dependent coin operator
- 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
- Quantum support vector machine based on regularized Newton method
- Quantum walk on a toral phase space
- An introduction to quantum computing for statisticians and data scientists
- One-dimensional continuous-time quantum walks
- Quantum spectral methods for differential equations
- Efficient quantum circuits for continuous-time quantum walks on composite graphs
- \textit{pyCTQW}: a continuous-time quantum walk simulator on distributed memory computers
- A method for exact simulation of quantum dynamics
- Lackadaisical discrete-time quantum walk on Johnson graph
- Hitting time of quantum walks with perturbation
- Quantum fractional revival on graphs
- Directional correlations in quantum walks with two particles
- Solving systems of linear algebraic equations via unitary transformations on quantum processor of IBM quantum experience
- Quantum circuit design for accurate simulation of qudit channels
- Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
- Recovering the original simplicity: succinct and exact quantum algorithm for the welded tree problem
- Continuous-time quantum random walks require discrete space
- Controllability of system dynamics on networks, quantum walks and random walks
- Quantum walk on a comb with infinite teeth
- Correlation between the continuous-time quantum walk and cliques in graphs and its application
- Pseudo-Hermitian continuous-time quantum walks
- Grover search with lackadaisical quantum walks
- Quantum Walks: A Markovian Perspective
- Thermalization in many-particle quantum walks
- The Hamiltonians generating one-dimensional discrete-time quantum walks
- Spectral quantization of discrete random walks on half-line and orthogonal polynomials on the unit circle
- Dynamics of continuous-time quantum walks in restricted geometries
- Relativistic effects and rigorous limits for discrete- and continuous-time quantum walks
- Exact simulation of coined quantum walks with the continuous-time model
- Overview: recent development and applications of reduction and lackadaisicalness techniques for spatial search quantum walk in the near term
- A complete characterization of unitary quantum space
- Discretization of continuous-time quantum walks via the staggered model with Hamiltonians
- Ranking nodes in directed networks via continuous-time quantum walks
- How to realize one-dimensional discrete-time quantum walk by Dirac particle
- Exact solutions and symmetry analysis for the limiting probability distribution of quantum walks
- Approximate locality for quantum systems on graphs
- Investigation of continuous-time quantum walk via modules of Bose–Mesner and Terwilliger algebras
- Perfect edge state transfer on cubelike graphs
- 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
- Simulating continuous-time Hamiltonian dynamics by way of a discrete-time quantum walk
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)
