Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPeriodicity for the Fourier quantum walk on regular graphs
73
0
0.0
(
0
)
Authors
Kei Saito
Ask ChatGPT about the research
No Arabic abstract
Quantum walks determined by the coin operator on graphs have been intensively studied. The typical examples of coin operator are the Grover and Fourier matrices. The periodicity of the Grover walk is well investigated. However, the corresponding result on the Fourier walk is not known. In this paper, we present a necessary condition for the Fourier walk on regular graphs to have the finite period. As an application of our result, we show that the Fourier walks do not have any finite period for some classes of regular graphs such as complete graphs, cycle graphs with selfloops, and hypercubes.
rate research
Read More
Dukes (2014) and Konno, Shimizu, and Takei (2017) studied the periodicity for 2-state quantum walks whose coin operator is the Hadamard matrix on cycle graph C_N with N vertices. The present paper treats the periodicity for 3-state quantum walks on C_N. Our results follow from a new method based on cyclotomic field. This method shows a necessary condition for the coin operator of quantum walks to have the finite period. Moreover, we reveal the period T_N of two kinds of typical quantum walks, the Grover and Fourier walks. We prove that both walks do not have any finite period except for N=3, in which case T_3=6 (Grover), =12 (Fourier).
Characterizations graphs of some classes to induce periodic Grover walks have been studied for recent years. In particular, for the strongly regular graphs, it has been known that there are only three kinds of such graphs. Here, we focus on the periodicity of the Grover walks on distance-regular graphs. The distance-regular graph can be regarded as a kind of generalization of the strongly regular graphs and the typical graph with an equitable partition. In this paper, we find some classes of such distance-regular graphs and obtain some useful necessary conditions to induce periodic Grover walks on the general distance-regular graphs. Also, we apply this necessary condition to give another proof for the strong regular graphs.
In this paper, we consider periodicity for space-inhomogeneous quantum walks on the cycle. For isospectral coin cases, we propose a spectral analysis. Based on the analysis, we extend the result for periodicity for Hadamard walk to some isospectral coin cases. For non-isospectral coin cases, we consider the the system that uses only one general coin at the origin and the identity coin at the other sites. In this case, we show that the periodicity of the general coin at the origin determines the periodicity for the whole system.
Strongly walk-regular graphs can be constructed as coset graphs of the duals of projective three-weight codes whose weights satisfy a certain equation. We provide classifications of the feasible parameters in the binary and ternary case for medium size code lengths. Additionally some theoretical insights on the properties of the feasible parameters are presented.
In this paper, we show reduction methods for search algorithms on graphs using quantum walks. By using a graph partitioning method called equitable partition for the the given graph, we determine effective subspace for the search algorithm to reduce the size of the problem. We introduce the equitable partition for quantum walk based search algorithms and show how to determine effective subspace and reduced operator.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
