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

Line digraphs and coined quantum random walks

Simone Severini B

Published Oct 8, 2002• 3 citations
OpenAlex

Abstract

Abstract. In this note, we give a characterization of the adjacency matrix of the line digraph of a regular digraph and we discuss a generalization.On the light of the characterization given, we remark that the underlying digraph of a coined quantum random walk is the line digraph of a regular digraph. 1. A characterization of the adjacency matrix of the line digraph of a regular digraph 1.1. Set-up. The notion of line digraph has been introduced by Harary and Norman [HN60] in 1960. A classic survey on line graphs and digraphs is [HB78]; a recent one is [P95]. Line digraphs are used in the design and analysis of interconnection networks (see e.g. [FYA84]). Line digraphs are also used in algorithms for DIRECTED MAX-CUT [CE90] and TRAVELLING SALESMAN [GKWS98]. Definition 1 (Line digraph). The line digraph − → LD of a digraph ( D = (V, A) is the

Related papers

The underlying digraph of a coined quantum random walk

Simone Severini B

We give a characterization of the line digraph of a regular digraph. We make use of the characterization, to show that the underlying digraph of a coined quantum random walk is a line digraph. We remark the connection between line digraphs and in-split graphs in symbolic dynamics.

arXiv:quant-ph/0210055•Oct 8, 2002•3 citations

Spectral properties of weighted line digraphs

Etsuo Segawa

In this paper, we treat some weighted line digraphs which are induced by a connected and undirected graph. For a given graph $G$, the adjacency matrix of the weighted line digraph $W$ is determined by a boundary operator from an arc-based space to a vertex-based space. We see that depending on the boundary operator and the Hilbert spaces, $W$ has different kind of an underlying stochastic transition operator. As an application, we obtain the spectrum of the positive support of cube of the Grover matrix in a large girth of the graph.

arXiv:1506.02855•Jun 9, 2015•2 citations

Generic quantum walks with memory on regular graphs

Dan Li, Michael Mc Gettrick, Fei Gao +2 more

Quantum walks with memory (QWM) are a type of modified quantum walks that record the walker's latest path. As we know, only two kinds of QWM have been presented up to now. It is desired to design more QWM for research, so that we can explore the potential of QWM. In this work, by presenting the one-to-one correspondence between QWM on a regular graph and quantum walks without memory (QWoM) on a line digraph of the regular graph, we construct a generic model of QWM on regular graphs. This construction gives a general scheme for building all possible standard QWM on regular graphs and makes it possible to study properties of different kinds of QWM. Here, by taking the simplest example, which is QWM with one memory on the line, we analyze some properties of QWM, such as variance, occupancy rate, and localization.

arXiv:1508.07674•Physical Review A•Apr 15, 2016•17 citations

Discrete Quantum Walks on Graphs and Digraphs

Chris D. Godsil, Hanmeng Zhan

Discrete quantum walks are quantum analogues of classical random walks. They are an important tool in quantum computing and a number of algorithms can be viewed as discrete quantum walks, in particular Grover's search algorithm. These walks are constructed on an underlying graph, and so there is a relation between properties of walks and properties of the graph. This book studies the mathematical problems that arise from this connection, and the different classes of walks that arise. Written at a level suitable for graduate students in mathematics, the only prerequisites are linear algebra and basic graph theory; no prior knowledge of physics is required. The text serves as an introduction to this important and rapidly developing area for mathematicians and as a detailed reference for computer scientists and physicists working on quantum information theory.

Cambridge University Press eBooks•Dec 23, 2022•11 citations

Scattering theory and quantum walks

Mark S. Hillery, Edgar Feldman

We study quantum walks on general graphs from the point of view of scattering theory. For a general finite graph we choose two vertices and attach one half line to each. We are interested in walks that proceed from one half line, through the graph, to the other. The particle propagates freely on the half lines but is scattered at each vertex in the original graph. The probability of starting on one line and reaching the other after n steps can be expressed in terms of the transmission amplitude for the graph. An example is presented. Classical random walks on graphs can be used to construct algorithms that solve 2-SAT, graph connectivity problems, and for finding satsifying assignments for Boolean functions. A hope is that recently defined quantum walks will prove similarly useful in the development of quantum algorithms. In fact, it has recently been shown that it is possible to use a quantum walk to perform a search on the hypercube faster than can be done classically [1]. In this problem

•Dec 8, 2003•0 citations

Coined quantum walks on percolation graphs

Godfrey Leung, Paul Knott, Joe Bailey +1 more

Quantum walks, both discrete (coined) and continuous time, form the basis of several quantum algorithms and have been used to model processes such as transport in spin chains and quantum chemistry. The enhanced spreading and mixing properties of quantum walks compared with their classical counterparts have been well studied on regular structures and also shown to be sensitive to defects and imperfections in the lattice. As a simple example of a disordered system, we consider percolation lattices, in which edges or sites are randomly missing, interrupting the progress of the quantum walk. We use numerical simulation to study the properties of coined quantum walks on these percolation lattices in one and two dimensions. In one dimension (the line), we introduce a simple notion of quantum tunnelling and determine how this affects the properties of the quantum walk as it spreads. On two-dimensional percolation lattices, we show how the spreading rate varies from linear in the number of steps down to zero as the percolation probability decreases towards the critical point. This provides an example of fractional scaling in quantum-walk dynamics.

arXiv:1006.1283•New Journal of Physics•Dec 9, 2010•52 citations
Abstract. In this note, we give a characterization of the adjacency matrix of the line digraph of a regular digraph and we discuss a generalization.On the light of the characterization given, we remark that the underlying digraph of a coined quantum random walk is the line digraph of a regular digraph. 1. A characterization of the adjacency matrix of the line digraph of a regular digraph 1.1. Set-up. The notion of line digraph has been introduced by Harary and Norman [HN60] in 1960. A classic survey on line graphs and digraphs is [HB78]; a recent one is [P95]. Line digraphs are used in the design and analysis of interconnection networks (see e.g. [FYA84]). Line digraphs are also used in algorithms for DIRECTED MAX-CUT [CE90] and TRAVELLING SALESMAN [GKWS98]. Definition 1 (Line digraph). The line digraph − → LD of a digraph ( D = (V, A) is the
In this paper, we treat some weighted line digraphs which are induced by a connected and undirected graph. For a given graph GGG, the adjacency matrix of the weighted line digraph WWW is determined by a boundary operator from an arc-based space to a vertex-based space. We see that depending on the boundary operator and the Hilbert spaces, WWW has different kind of an underlying stochastic transition operator. As an application, we obtain the spectrum of the positive support of cube of the Grover matrix in a large girth of the graph.
Quantum walks with memory (QWM) are a type of modified quantum walks that record the walker's latest path. As we know, only two kinds of QWM have been presented up to now. It is desired to design more QWM for research, so that we can explore the potential of QWM. In this work, by presenting the one-to-one correspondence between QWM on a regular graph and quantum walks without memory (QWoM) on a line digraph of the regular graph, we construct a generic model of QWM on regular graphs. This construction gives a general scheme for building all possible standard QWM on regular graphs and makes it possible to study properties of different kinds of QWM. Here, by taking the simplest example, which is QWM with one memory on the line, we analyze some properties of QWM, such as variance, occupancy rate, and localization.
Discrete quantum walks are quantum analogues of classical random walks. They are an important tool in quantum computing and a number of algorithms can be viewed as discrete quantum walks, in particular Grover's search algorithm. These walks are constructed on an underlying graph, and so there is a relation between properties of walks and properties of the graph. This book studies the mathematical problems that arise from this connection, and the different classes of walks that arise. Written at a level suitable for graduate students in mathematics, the only prerequisites are linear algebra and basic graph theory; no prior knowledge of physics is required. The text serves as an introduction to this important and rapidly developing area for mathematicians and as a detailed reference for computer scientists and physicists working on quantum information theory.
We study quantum walks on general graphs from the point of view of scattering theory. For a general finite graph we choose two vertices and attach one half line to each. We are interested in walks that proceed from one half line, through the graph, to the other. The particle propagates freely on the half lines but is scattered at each vertex in the original graph. The probability of starting on one line and reaching the other after n steps can be expressed in terms of the transmission amplitude for the graph. An example is presented. Classical random walks on graphs can be used to construct algorithms that solve 2-SAT, graph connectivity problems, and for finding satsifying assignments for Boolean functions. A hope is that recently defined quantum walks will prove similarly useful in the development of quantum algorithms. In fact, it has recently been shown that it is possible to use a quantum walk to perform a search on the hypercube faster than can be done classically [1]. In this problem
Quantum walks, both discrete (coined) and continuous time, form the basis of several quantum algorithms and have been used to model processes such as transport in spin chains and quantum chemistry. The enhanced spreading and mixing properties of quantum walks compared with their classical counterparts have been well studied on regular structures and also shown to be sensitive to defects and imperfections in the lattice. As a simple example of a disordered system, we consider percolation lattices, in which edges or sites are randomly missing, interrupting the progress of the quantum walk. We use numerical simulation to study the properties of coined quantum walks on these percolation lattices in one and two dimensions. In one dimension (the line), we introduce a simple notion of quantum tunnelling and determine how this affects the properties of the quantum walk as it spreads. On two-dimensional percolation lattices, we show how the spreading rate varies from linear in the number of steps down to zero as the percolation probability decreases towards the critical point. This provides an example of fractional scaling in quantum-walk dynamics.