Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCombinatorial necessary conditions for regular graphs to induce periodic quantum walks
92
0
0.0
(
0
)
Authors
Sho Kubota
Ask ChatGPT about the research
No Arabic abstract
We derive combinatorial necessary conditions for discrete-time quantum walks defined by regular mixed graphs to be periodic. If the quantum walk is periodic, all the eigenvalues of the time evolution matrices must be algebraic integers. Focusing on this, we explore which ring the coefficients of the characteristic polynomials should belong to. On the other hand, the coefficients of the characteristic polynomials of $eta$-Hermitian adjacency matrices have combinatorial implications. From these, we can find combinatorial implications in the coefficients of the characteristic polynomials of the time evolution matrices, and thus derive combinatorial necessary conditions for mixed graphs to be periodic. For example, if a $k$-regular mixed graph with $n$ vertices is periodic, then $2n/k$ must be an integer. As an application of this work, we determine periodicity of mixed complete graphs and mixed graphs with a prime number of vertices.
rate research
Read More
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.
We count the numbers of primitive periodic orbits on families of 4-regular directed circulant graphs with $n$ vertices. The relevant counting techniques are then extended to count the numbers of primitive pseudo orbits (sets of distinct primitive periodic orbits) up to length $n$ that lack self-intersections, or that never intersect at more than a single vertex at a time repeated exactly twice for each self-intersection (2-encounters of length zero), for two particular families of graphs. We then regard these two families of graphs as families of quantum graphs and use the counting results to compute the variance of the coefficients of the quantum graphs characteristic polynomial.
This paper explains the periodicity of the Grover walk on finite graphs. We characterize the graphs to induce 2, 3, 4, 5-periodic Grover walk and obtain a necessary condition of the graphs to induce an odd-periodic Grover walk.
In this paper, we simplify the known switching theorem due to Bose and Shrikhande as follows. Let $G=(V,E)$ be a primitive strongly regular graph with parameters $(v,k,lambda,mu)$. Let $S(G,H)$ be the graph from $G$ by switching with respect to a nonempty $Hsubset V$. Suppose $v=2(k-theta_1)$ where $theta_1$ is the nontrivial positive eigenvalue of the $(0,1)$ adjacency matrix of $G$. This strongly regular graph is associated with a regular two-graph. Then, $S(G,H)$ is a strongly regular graph with the same parameters if and only if the subgraph induced by $H$ is $k-frac{v-h}{2}$ regular. Moreover, $S(G,H)$ is a strognly regualr graph with the other parameters if and only if the subgraph induced by $H$ is $k-mu$ regular and the size of $H$ is $v/2$. We prove these theorems with the view point of the geometrical theory of the finite set on the Euclidean unit sphere.
We show the existence of regular combinatorial objects which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, t-designs, and t-wise permutations. In all cases, the sizes of the objects are optimal up to polynomial overhead. The proof of existence is probabilistic. We show that a randomly chosen structure has the required properties with positive yet tiny probability. Our method allows also to give rather precise estimates on the number of objects of a given size and this is applied to count the number of orthogonal arrays, t-designs and regular hypergraphs. The main technical ingredient is a special local central limit theorem for suitable lattice random walks with finitely many steps.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
