Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0504116 · Quantum Information and Computation

Quantum walks on directed graphs

Ashley Montanaro

Published Jan 1, 2007• 35 citations
arXivHTMLPDF

Abstract

We consider the definition of quantum walks on directed graphs. Call a directed graph reversible if, for each pair of vertices $(v_i, v_j)$, if $v_i$ is connected to $v_j$ then there is a path from $v_j$ to $v_i$. We show that reversibility is a necessary and sufficient condition for a directed graph to allow the notion of a discrete-time quantum walk, and discuss some implications of this condition. We present a method for defining a "partially quantum'' walk on directed graphs that are not reversible.

DOI
10.26421/qic7.1-2-5

Related papers

Quantum walks on directed graphs

MontanaroAshley

We consider the definition of quantum walks on directed graphs. Call a directed graph reversible if, for each pair of vertices (vi, vj), if vi is connected to vj then there is a path from vj to vi....

Quantum Information and Computation•Jan 1, 2007•0 citations

Quantum walks on graphs and quantum scattering theory

Edgar Feldman, Mark S. Hillery

We discuss a particular kind of quantum walk on a general graph. We affix two semi-infinite lines to a general finite graph, which we call tails. On the tails, the particle making the walk simply advances one unit at each time step, so that its behavior there is analogous to free propagation We are interested in how many steps it will take the particle, starting on one tail and propagating through the graph (where its propagation is not free), to emerge onto the other tail. The probability to make such a walk in n steps and the hitting time for such a walk can be expressed in terms of the transmission amplitude for the graph, which is one element of its S matrix. Demonstrating this necessitates a study of the analyticity properties of the transmission and reflection amplitudes of a graph. We show that the graph can have bound states that cannot be accessed by a particle entering the graph from one of its tails. Time-reversal invariance of a quantum walk is defined and used to show that the transmission amplitudes for the particle entering the graph from different directions are the same if the walk is time-reversal invariant.

arXiv:quant-ph/0403066•Mar 8, 2004•0 citations

Symmetries in discrete time quantum walks on Cayley graphs

Václav Potoček

We address the question of symmetries of an important type of quantum walks. We introduce all the necessary definitions and provide a rigorous formulation of the problem. Using a thorough analysis, we reach the complete answer by presenting a constructive method of finding all solutions of the problem with minimal additional assumptions. We apply the results on an example of a quantum walk on a line to demonstrate the practical significance of the theory.

arXiv:1211.0172•Nov 1, 2012•1 citation

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 is

•Jan 1, 2009•11 citations

QUANTUM WALKS ON GENERAL GRAPHS

Viv M. Kendon

Quantum walks, both discrete (coined) and continuous time, on a general graph of N vertices with undirected edges are reviewed in some detail. The resource requirements for implementing a quantum walk as a program on a quantum computer are compared and found to be very similar for both discrete and continuous time walks. The role of the oracle, and how it changes if more prior information about the graph is available, is also discussed.

arXiv:quant-ph/0306140•International Journal of Quantum Information•Oct 1, 2006•114 citations

Discrete-Time Quantum Walks on Oriented Graphs

Bruno Chagas, Renato Portugal

The interest in quantum walks has been steadily increasing during the last two decades. It is still worth to present new forms of quantum walks that might find practical applications and new physical behaviors. In this work, we define discrete-time quantum walks on arbitrary oriented graphs by partitioning a graph into tessellations, which is a collection of disjoint cliques that cover the vertex set. By using the adjacency matrices associated with the tessellations, we define local unitary operators, whose product is the evolution operator of our quantum walk model. We introduce a parameter, called alpha, that quantifies the amount of orientation. We show that the parameter alpha can be tuned in order to increase the amount of quantum walk-based transport on oriented graphs.

arXiv:2001.04814•Electronic Proceedings in Theoretical Computer Science•Apr 1, 2020•4 citations
We consider the definition of quantum walks on directed graphs. Call a directed graph reversible if, for each pair of vertices (vi,vj)(v_i, v_j)(vi​,vj​), if viv_ivi​ is connected to vjv_jvj​ then there is a path from vjv_jvj​ to viv_ivi​. We show that reversibility is a necessary and sufficient condition for a directed graph to allow the notion of a discrete-time quantum walk, and discuss some implications of this condition. We present a method for defining a "partially quantum'' walk on directed graphs that are not reversible.
We discuss a particular kind of quantum walk on a general graph. We affix two semi-infinite lines to a general finite graph, which we call tails. On the tails, the particle making the walk simply advances one unit at each time step, so that its behavior there is analogous to free propagation We are interested in how many steps it will take the particle, starting on one tail and propagating through the graph (where its propagation is not free), to emerge onto the other tail. The probability to make such a walk in n steps and the hitting time for such a walk can be expressed in terms of the transmission amplitude for the graph, which is one element of its S matrix. Demonstrating this necessitates a study of the analyticity properties of the transmission and reflection amplitudes of a graph. We show that the graph can have bound states that cannot be accessed by a particle entering the graph from one of its tails. Time-reversal invariance of a quantum walk is defined and used to show that the transmission amplitudes for the particle entering the graph from different directions are the same if the walk is time-reversal invariant.
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 is
The interest in quantum walks has been steadily increasing during the last two decades. It is still worth to present new forms of quantum walks that might find practical applications and new physical behaviors. In this work, we define discrete-time quantum walks on arbitrary oriented graphs by partitioning a graph into tessellations, which is a collection of disjoint cliques that cover the vertex set. By using the adjacency matrices associated with the tessellations, we define local unitary operators, whose product is the evolution operator of our quantum walk model. We introduce a parameter, called alpha, that quantifies the amount of orientation. We show that the parameter alpha can be tuned in order to increase the amount of quantum walk-based transport on oriented graphs.