arXiv:quant-ph/0210055

The underlying digraph of a coined quantum random walk

Simone Severini B

Published Oct 8, 2002• 3 citations

Abstract

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.

DOI: 10.48550/arxiv.quant-ph/0210055

Related papers

Line digraphs and coined quantum random walks

Simone Severini B

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

Oct 8, 20023 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 eBooksDec 23, 202211 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.07674Physical Review AApr 15, 201617 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

Quantum graph walks I: mapping to quantum walks

Yusuke Higuchi, Norio Konno, Iwao Sato +1 more

We clarify that coined quantum walk is determined by only the choice of local quantum coins. To do so, we characterize coined quantum walks on graph by disjoint Euler circles with respect to symmetric arcs. In this paper, we introduce a new class of coined quantum walk by a special choice of quantum coins determined by corresponding quantum graph, called quantum graph walk. We show that a stationary state of quantum graph walk describes the eigenfunction of the quantum graph.

arXiv:1211.0803Nov 5, 201222 citations

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

Pascal Philipp, Renato Portugal

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.

arXiv:1606.04030Jun 13, 20161 citation