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)- Quantum Walks: A Markovian Perspective
- The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
- Quantum algorithm design: techniques and applications
- Factoring discrete-time quantum walks on distance regular graphs into continuous-time quantum walks
- A complete characterization of unitary quantum space
- Survival of classical and quantum particles in the presence of traps
- Quantum walks and elliptic integrals
- Crossovers induced by discrete-time quantum walks
- \textit{pyCTQW}: a continuous-time quantum walk simulator on distributed memory computers
- Controllability of quantum walks on graphs
- A quantum walk with both a continuous-time limit and a continuous-spacetime limit
- Exact simulation of coined quantum walks with the continuous-time model
- On the efficiency of quantum algorithms for Hamiltonian simulation
- Quantum blind signature scheme based on quantum walk
- Quantum spectral methods for differential equations
- Quantum circuit design for accurate simulation of qudit channels
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Investigation of continuous-time quantum walk via modules of Bose–Mesner and Terwilliger algebras
- Quantum recommendation systems
- Grover search with lackadaisical quantum walks
- Element distinctness revisited
- An all-pair quantum SVM approach for big data multiclass classification
- Directional correlations in quantum walks with two particles
- General methods and properties to evaluate continuum limits of the 1D discrete time quantum walk
- 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
- Wave packet spreading with periodic, Fibonacci quasiperiodic, and random nonlinear discrete-time quantum walks
- Quantum fractional revival on graphs
- Analytical expression for variance of homogeneous-position quantum walk with decoherent position
- Transport and localization in quantum walks on a random hierarchy of barriers
- A weak limit theorem for a class of long-range-type quantum walks in 1d
- Mimicking the Hadamard discrete-time quantum walk with a time-independent Hamiltonian
- Arbitrated quantum signature scheme with quantum walk-based teleportation
- Eigenbasis of the evolution operator of 2-tessellable quantum walks
- Bounding the costs of quantum simulation of many-body physics in real space
- Discretization of continuous-time quantum walks via the staggered model with Hamiltonians
- Quantum walk and its application domains: a systematic review
- Quantum computation and quantum information
- Speed and entropy of an interacting continuous time quantum walk
- A method for exact simulation of quantum dynamics
- Thermalization in many-particle quantum walks
- Strong convergence of quantum random walks via semigroup decomposition
- Continuous-time quantum random walks require discrete space
- Limitations of discrete-time quantum walk on a one-dimensional infinite chain
- Approximate locality for quantum systems on graphs
- Quantum walks: a comprehensive review
- Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
- Asymptotic entanglement in 1D quantum walks with a time-dependent coined
- Pseudo-Hermitian continuous-time quantum walks
- Faster search of clustered marked states with lackadaisical quantum walks
- Controllability of system dynamics on networks, quantum walks and random walks
- Simplifying continuous-time quantum walks on dynamic graphs
- Quantum multi-secret sharing via trap codes and discrete quantum walks
- Relation between two-phase quantum walks and the topological invariant
- Dynamics of continuous-time quantum walks in restricted geometries
- Relativistic effects and rigorous limits for discrete- and continuous-time quantum walks
- Efficient discrete-time simulations of continuous-time quantum query algorithms
- Birth and death processes and quantum spin chains
- Hitting time of quantum walks with perturbation
- Simulating continuous-time Hamiltonian dynamics by way of a discrete-time quantum walk
- One-dimensional continuous-time quantum walks
- Graph matching using the interference of continuous-time quantum walks
- Random walk quantum clustering algorithm based on space
- Discrete-time quantum walks: continuous limit and symmetries
- Exact solutions and symmetry analysis for the limiting probability distribution of quantum walks
- Unveiling and exemplifying the unitary equivalence of discrete time quantum walk models
- On the von Neumann entropy of certain quantum walks subject to decoherence
- QUANTUM WALKS ON GENERAL GRAPHS
- Connection between continuous and discrete time quantum walks. From \(D\)-dimensional lattices to general graphs
- Brownian-Huygens propagation: modeling wave functions with discrete particle-antiparticle random walks
- Quantum support vector machine based on gradient descent
- An introduction to quantum computing for statisticians and data scientists
- Computing scalar products via a two-terminal quantum transmission line
- Efficient quantum circuits for continuous-time quantum walks on composite graphs
- Quantum support vector machine based on regularized Newton method
- Perfect state transfer in quantum walks on orientable maps
- Controlled transport in chiral quantum walks on graphs
- Quantum walk on a comb with infinite teeth
- Spectral quantization of discrete random walks on half-line and orthogonal polynomials on the unit circle
- Correlation between the continuous-time quantum walk and cliques in graphs and its application
- Overview: recent development and applications of reduction and lackadaisicalness techniques for spatial search quantum walk in the near term
- Quantum walk on a toral phase space
- The Hamiltonians generating one-dimensional discrete-time quantum walks
- Quantum algorithms for multiscale partial differential equations
- Recovering the original simplicity: succinct and exact quantum algorithm for the welded tree problem
- Perfect edge state transfer on cubelike graphs
- Abstract model of continuous-time quantum walk based on Bernoulli functionals and perfect state transfer
- Quantum walks as thermalisations, with application to fullerene graphs
- The spectrum of asymptotic Cayley trees
- Ranking nodes in directed networks via continuous-time quantum walks
- Lackadaisical discrete-time quantum walk on Johnson graph
- Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices
- Quantum circuits for discrete-time quantum walks with position-dependent coin operator
- Solving systems of linear algebraic equations via unitary transformations on quantum processor of IBM quantum experience
- Operations with elements of transferred density matrix via unitary transformations on extended receiver
- How to realize one-dimensional discrete-time quantum walk by Dirac particle
- Search algorithm on strongly regular graph by lackadaisical 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)
