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

By Andrew M. Childs. 2008

449 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems

View Paper: https://www.semanticscholar.org/paper/88529a3d7b83997286c7f1d2fadd0fa39f6392c1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Information Systems

Citations in the corpus

Universal quantum computation using the discrete-time quantum walk (2009, background): “t two copies of the continuous time walk propagatingin opposite directions [18]. Childs later showed a direct correspondence between the discrete and continuous time quantum walks on arbitrary graphs [19]. We begin by describing the discrete time quantum walk brieﬂy in section 2 then move on to show”
Exponential improvement in precision for simulating sparse Hamiltonians (2013, methodology): “In the context of time-independent sparse Hamiltonian simulation, the quantum walk-based simulation of [10, 6] achieves linear dependence on t, whereas our upper bound”
Quantum Computation and Quantum Information (2012, methodology): “Quantum walk and quantum Markov chain are currently being investigated for new quantum search algorithms and quantum speed-up of Markov chain based algorithms (Aharonov and Ta-Shma (2003), Childs et al. (2003); Childs (2010); Tulsi (2008); Shenvi, Kempe and Whaley (2003) and Szegedy, 2004).”
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters (2015, methodology): “A quantum walk for any Hamiltonian We begin by reviewing the quantum walk defined in [11, 15].”
Hamiltonian simulation using linear combinations of unitary operations (2012, background): “Recently a new paradigm has been proposed that uses quantum walks rather than product formulas [16, 17].”
k-Boson Quantum Walks Do Not Distinguish Arbitrary Graphs (2010, background): “A detailed description of continuous time quantum walks and their properties can be found in [3].”
Optimal Hamiltonian Simulation by Quantum Signal Processing. (2016, methodology): “the best algorithms to date approach these factors multiplicatively with either linear scaling in time O( τ √ ) [14] or”
Toward the first quantum simulation with quantum speedup (2017, unknown): “n algorithms As discussed in Section 3, there are many diﬀerent quantum algorithms for Hamiltonian simulation, including algorithms based on product formulas [11, 23, 50], discrete-time quantum walks [12, 15, 24, 52], and linear combinations of unitaries [13–15, 27, 51, 52]. The asymptotic performan”
Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision (2015, methodology): “We implement such terms using a quantum walk that has previously been applied to Hamiltonian simulation [Chi10, BC12, BCK15].”
Quantum walks: a comprehensive review (2012, methodology): “Child’s contribution In [110], Childs presents the following mathematical framework for simulating a continuous quantum walk as a limit ( − approximation) of discrete quantum walks (for the sake of clarity and readability of the original paper, we closely follow the notation used in [110]): (a) Let ”