arXiv:1606.04030

Exact simulation of coined quantum walks with the continuous-time model

Pascal Philipp, Renato Portugal

Published Jun 13, 2016• 1 citation

Abstract

The connection between coined and continuous-time quantum walk models has been addressed in a number of papers. In most of those studies, the continuous-time model is derived from coined quantum walks by employing dimensional reduction and taking appropriate limits. In this work, we produce the evolution of a coined quantum walk on a generic graph using a continuous-time quantum walk on a larger graph. In addition to expanding the underlying structure, we also have to switch on and off edges during the continuous-time evolution to accommodate the alternation between the shift and coin operators from the coined model. In one particular case, the connection is very natural, and the continuous-time quantum walk that simulates the coined quantum walk is driven by the graph Laplacian on the dynamically changing expanded graph.

DOI: 10.48550/arxiv.1606.04030

Related papers

Generic quantum walk using a coin-embedded shift operator

C. M. Chandrashekar

arXiv:0810.1556Physical Review ANov 5, 200810 citations

Continuous limit of discrete quantum walks

M N Dheeraj, Todd A. Brun

arXiv:1501.06950Physical Review AJun 5, 201517 citations

A method of approximation of discrete Schrödinger equation with the normalized Laplacian by discrete-time quantum walk on graphs

Kei Saito, Etsuo Segawa

arXiv:2308.13741Reviews in Mathematical PhysicsApr 10, 20250 citations

A hybrid quantum walk model unifying discrete and continuous quantum walks

Tianen Chen, Yun Shang

arXiv:2509.09221npj Quantum InformationDec 30, 20252 citations

Connection Between Continuous and Discrete Time Quantum Walks on d-Dimensional Lattices; Extensions to General Graphs

Jan 1, 200911 citations

Connecting Coined Quantum Walks with Szegedy's Model

Renato Portugal, Etsuo Segawa

We analyze the equivalence between discrete-time coined quantum walks and Szegedy's quantum walks. We characterize a class of flip-flop coined models with generalized Grover coin on a graph Γ that can be directly converted into Szegedy's model on the subdivision graph of Γ and we describe a method to convert one model into the other. This method improves previous results in literature that need to use the staggered model and the concept of line graph, which are avoided here.

arXiv:1612.02448Interdisciplinary Information SciencesJan 1, 20179 citations

arXiv:1606.04030

Exact simulation of coined quantum walks with the continuous-time model

Pascal Philipp, Renato Portugal

Published Jun 13, 2016• 1 citation

arXiv HTML PDF

Abstract

DOI: 10.48550/arxiv.1606.04030

Related papers

Generic quantum walk using a coin-embedded shift operator

C. M. Chandrashekar

The study of quantum walk processes has been widely divided into two standard variants, the discrete-time quantum walk (DTQW) and the continuous-time quantum walk (CTQW). The connection between the two variants has been established by considering the limiting value of the coin operation parameter in the DTQW, and the coin degree of freedom was shown to be unnecessary [F. W. Strauch, Phys. Rev. A 74, 030301(R) (2006)]. But the coin degree of freedom is an additional resource which can be exploited to control the dynamics of the QW process. In this paper we present a generic quantum walk model using a quantum coin-embedded unitary shift operation ${U}_{C}$ . The standard version of the DTQW and the CTQW can be conveniently retrieved from this generic model, retaining the features of the coin degree of freedom in both variants.The study of quantum walk processes has been widely divided into two standard variants, the discrete-time quantum walk (DTQW) and the continuous-time quantum walk (CTQW). The connection between the two variants has been established by considering the limiting value of the coin operation parameter in the DTQW, and the coin degree of freedom was shown to be unnecessary [F. W. Strauch, Phys. Rev. A 74, 030301(R) (2006)]. But the coin degree of freedom is an additional resource which can be exploited to control the dynamics of the QW process. In this paper we present a generic quantum walk model using a quantum coin-embedded unitary shift operation ${U}_{C}$. The standard version of the DTQW and the CTQW can be conveniently retrieved from this generic model, retaining the features of the coin degree of freedom in both variants.

arXiv:0810.1556Physical Review ANov 5, 200810 citations

Continuous limit of discrete quantum walks

M N Dheeraj, Todd A. Brun

Quantum walks can be defined in two quite distinct ways: discrete-time and continuous-time quantum walks (DTQWs and CTQWs). For classical random walks, there is a natural sense in which continuous-time walks are a limit of discrete-time walks. Quantum mechanically, in the discrete-time case, an additional ``coin space'' must be appended for the walk to have nontrivial time evolution. Continuous-time quantum walks, however, have no such constraints. This means that there is no completely straightforward way to treat a CTQW as a limit of a DTQW, as can be done in the classical case. Various approaches to this problem have been taken in the past. We give a construction for walks on $d$ -regular, $d$ -colorable graphs when the coin flip operator is Hermitian: from a standard DTQW we construct a family of discrete-time walks with a well-defined continuous-time limit on a related graph. One can think of this limit as a ``coined'' continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at a spatial search by a DTQW over the two-dimensional (2D) torus (a grid with periodic boundary conditions) of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$, where it was shown that a coined DTQW can search in time $O(\sqrt{N}logN)$ , but a standard CTQW takes $\mathrm{\ensuremath{\Omega}}(N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2D torus exhibits the $O(\sqrt{N}logN)$ scaling, like the coined walk it is derived from. We also look at the effects of graph symmetry on the limiting walk, and show that the properties are similar to those of the DTQW as shown in Krovi and Brun, Phys. Rev. A 75, 062332 (2007).Quantum walks can be defined in two quite distinct ways: discrete-time and continuous-time quantum walks (DTQWs and CTQWs). For classical random walks, there is a natural sense in which continuous-time walks are a limit of discrete-time walks. Quantum mechanically, in the discrete-time case, an additional ``coin space'' must be appended for the walk to have nontrivial time evolution. Continuous-time quantum walks, however, have no such constraints. This means that there is no completely straightforward way to treat a CTQW as a limit of a DTQW, as can be done in the classical case. Various approaches to this problem have been taken in the past. We give a construction for walks on $d$-regular, $d$-colorable graphs when the coin flip operator is Hermitian: from a standard DTQW we construct a family of discrete-time walks with a well-defined continuous-time limit on a related graph. One can think of this limit as a ``coined'' continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at a spatial search by a DTQW over the two-dimensional (2D) torus (a grid with periodic boundary conditions) of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$, where it was shown that a coined DTQW can search in time $O(\sqrt{N}logN)$, but a standard CTQW takes $\mathrm{\ensuremath{\Omega}}(N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2D torus exhibits the $O(\sqrt{N}logN)$ scaling, like the coined walk it is derived from. We also look at the effects of graph symmetry on the limiting walk, and show that the properties are similar to those of the DTQW as shown in Krovi and Brun, Phys. Rev. A 75, 062332 (2007).

arXiv:1501.06950Physical Review AJun 5, 201517 citations

A method of approximation of discrete Schrödinger equation with the normalized Laplacian by discrete-time quantum walk on graphs

Kei Saito, Etsuo Segawa

We propose a class of continuous-time quantum walk models on graphs induced by a certain class of discrete-time quantum walk models with a parameter [Formula: see text]. Here the graph treated in this paper can be applied to both finite and infinite cases. The induced continuous-time quantum walk is an extended version of the (free) discrete-Schrödinger equation driven by the normalized Laplacian: the element of the weighted Hermitian takes not only a scalar value but also a matrix value depending on the underlying discrete-time quantum walk. We show that each discrete-time quantum walk with an appropriate setting of the parameter [Formula: see text] in the long time limit identifies with its induced continuous-time quantum walk and gives the running time for the discrete-time to approximate the induced continuous-time quantum walk with a small error [Formula: see text]. We also investigate the detailed spectral information on the induced continuous-time quantum walk.We propose a class of continuous-time quantum walk models on graphs induced by a certain class of discrete-time quantum walk models with a parameter [Formula: see text]. Here the graph treated in this paper can be applied to both finite and infinite cases. The induced continuous-time quantum walk is an extended version of the (free) discrete-Schrödinger equation driven by the normalized Laplacian: the element of the weighted Hermitian takes not only a scalar value but also a matrix value depending on the underlying discrete-time quantum walk. We show that each discrete-time quantum walk with an appropriate setting of the parameter [Formula: see text] in the long time limit identifies with its induced continuous-time quantum walk and gives the running time for the discrete-time to approximate the induced continuous-time quantum walk with a small error [Formula: see text]. We also investigate the detailed spectral information on the induced continuous-time quantum walk.

arXiv:2308.13741Reviews in Mathematical PhysicsApr 10, 20250 citations

A hybrid quantum walk model unifying discrete and continuous quantum walks

Tianen Chen, Yun Shang

Quantum walks, both discrete and continuous, serve as fundamental tools in quantum information processing with diverse applications. This work introduces a hybrid quantum walk model that integrates the coin mechanism of discrete walks with the Hamiltonian-driven time evolution of continuous walks. Through systematic analysis of probability distributions, standard deviations, and entanglement entropy on fundamental graph structures, we reveal distinctive dynamical characteristics that differentiate our model from conventional quantum walk paradigms. The proposed framework demonstrates unifying capabilities by naturally encompassing existing quantum walk models as special cases. Two significant applications emerge from this hybrid architecture: (1) We develop a novel protocol for perfect state transfer(PST) in general connected graphs, overcoming the limitations of previous graph-specific approaches. A PST on a tree graph has been implemented on a quantum superconducting processor. (2) We devise a quantum algorithm for multiplying K adjacency matrices of n -vertex regular graphs with time complexity O ( n 2 d 1 ⋯ d K ), outperforming classical matrix multiplication ( O ( n 2.371552 )) when vertex degrees d i are bounded. The algorithm’s efficacy for triangle counting is experimentally validated through the quantum simulation on PennyLane. These results establish the hybrid quantum walk as a versatile framework bridging discrete and continuous paradigms while enabling practical quantum advantage in graph computation tasks.Quantum walks, both discrete and continuous, serve as fundamental tools in quantum information processing with diverse applications. This work introduces a hybrid quantum walk model that integrates the coin mechanism of discrete walks with the Hamiltonian-driven time evolution of continuous walks. Through systematic analysis of probability distributions, standard deviations, and entanglement entropy on fundamental graph structures, we reveal distinctive dynamical characteristics that differentiate our model from conventional quantum walk paradigms. The proposed framework demonstrates unifying capabilities by naturally encompassing existing quantum walk models as special cases. Two significant applications emerge from this hybrid architecture: (1) We develop a novel protocol for perfect state transfer(PST) in general connected graphs, overcoming the limitations of previous graph-specific approaches. A PST on a tree graph has been implemented on a quantum superconducting processor. (2) We devise a quantum algorithm for multiplying K adjacency matrices of n -vertex regular graphs with time complexity O ( n 2 d 1 ⋯ d K ), outperforming classical matrix multiplication ( O ( n 2.371552 )) when vertex degrees d i are bounded. The algorithm’s efficacy for triangle counting is experimentally validated through the quantum simulation on PennyLane. These results establish the hybrid quantum walk as a versatile framework bridging discrete and continuous paradigms while enabling practical quantum advantage in graph computation tasks.

arXiv:2509.09221npj Quantum InformationDec 30, 20252 citations

Connection Between Continuous and Discrete Time Quantum Walks on d-Dimensional Lattices; Extensions to General Graphs

I obtain the dynamics of the continuous time quantum walk on a d-dimensional lattice, with periodic boundary conditions, as an appropriate limit of the dynamics of the discrete time quantum walk on the same lattice. This extends the main result of [8] which proved this limit for the case of the quantum walk on the infinite line and the quantum cellular automaton proposed in [1]. By highlighting the main features of the limiting procedure, I then extend it to general graphs. For a given discrete time quantum walk on a general graph, I single out the type of continuous dynamics (Hamiltonians) that can be obtained as a limit of the discrete time dynamics. 1 Generalities on quantum walks; continuous and discrete time Consider a graph G: = {V, E} with a set of vertices V of cardinality N and a set of edges E. We assume G to be undirected and without self-loops. In the interval of time ∆t a certain fraction γ∆t of a quantity pj leaves the location of the j-th vertex to move to a neighboring vertex k. The quantity pj, j = 1,..., N, at time t + ∆t is given by 1 pj(t + ∆t) = pj(t) − deg (j)γ∆tpj(t) + ∑ (k,j)∈E γ∆tpk(t). (1) Define ⃗p the N−vector whose components are the pj’s quantities, and L the Laplacian matrix defined by Ljj = − deg (j), Ljk = 1 if (j, k) ∈ E and Ljk = 0 otherwise. L isI obtain the dynamics of the continuous time quantum walk on a d-dimensional lattice, with periodic boundary conditions, as an appropriate limit of the dynamics of the discrete time quantum walk on the same lattice. This extends the main result of [8] which proved this limit for the case of the quantum walk on the infinite line and the quantum cellular automaton proposed in [1]. By highlighting the main features of the limiting procedure, I then extend it to general graphs. For a given discrete time quantum walk on a general graph, I single out the type of continuous dynamics (Hamiltonians) that can be obtained as a limit of the discrete time dynamics. 1 Generalities on quantum walks; continuous and discrete time Consider a graph G: = {V, E} with a set of vertices V of cardinality N and a set of edges E. We assume G to be undirected and without self-loops. In the interval of time ∆t a certain fraction γ∆t of a quantity pj leaves the location of the j-th vertex to move to a neighboring vertex k. The quantity pj, j = 1,..., N, at time t + ∆t is given by 1 pj(t + ∆t) = pj(t) − deg (j)γ∆tpj(t) + ∑ (k,j)∈E γ∆tpk(t). (1) Define ⃗p the N−vector whose components are the pj’s quantities, and L the Laplacian matrix defined by Ljj = − deg (j), Ljk = 1 if (j, k) ∈ E and Ljk = 0 otherwise. L is

Jan 1, 200911 citations

Connecting Coined Quantum Walks with Szegedy's Model

Renato Portugal, Etsuo Segawa

arXiv:1612.02448Interdisciplinary Information SciencesJan 1, 20179 citations

{U}_{C}

. The standard version of the DTQW and the CTQW can be conveniently retrieved from this generic model, retaining the features of the coin degree of freedom in both variants.

d

-regular,

d

-colorable graphs when the coin flip operator is Hermitian: from a standard DTQW we construct a family of discrete-time walks with a well-defined continuous-time limit on a related graph. One can think of this limit as a ``coined'' continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at a spatial search by a DTQW over the two-dimensional (2D) torus (a grid with periodic boundary conditions) of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$, where it was shown that a coined DTQW can search in time

O(\sqrt{N}logN)

, but a standard CTQW takes $\mathrm{\ensuremath{\Omega}}(N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2D torus exhibits the

O(\sqrt{N}logN)

scaling, like the coined walk it is derived from. We also look at the effects of graph symmetry on the limiting walk, and show that the properties are similar to those of the DTQW as shown in Krovi and Brun, Phys. Rev. A 75, 062332 (2007).