Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPeriodicity of quantum walks defined by mixed paths and mixed cycles
64
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper, we determine periodicity of quantum walks defined by mixed paths and mixed cycles. By the spectral mapping theorem of quantum walks, consideration of periodicity is reduced to eigenvalue analysis of $eta$-Hermitian adjacency matrices. First, we investigate coefficients of the characteristic polynomials of $eta$-Hermitian adjacency matrices. We show that the characteristic polynomials of mixed trees and their underlying graphs are same. We also define $n+1$ types of mixed cycles and show that every mixed cycle is switching equivalent to one of them. We use these results to discuss periodicity. We show that the mixed paths are periodic for any $eta$. In addition, we provide a necessary and sufficient condition for a mixed cycle to be periodic and determine their periods.
rate research
Read More
We propose a quantum walk defined by digraphs (mixed graphs). This is like Grover walk that is perturbed by a certain complex-valued function defined by digraphs. The discriminant of this quantum walk is a matrix that is a certain normalization of generalized Hermitian adjacency matrices. Furthermore, we give definitions of the positive and negative supports of the transfer matrix, and clarify explicit formulas of their supports of the square. In addition, we give tables by computer on the identification of digraphs by their eigenvalues.
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.
The independence polynomial of a graph is the generating polynomial for the number of independent sets of each size. Two graphs are said to be textit{independence equivalent} if they have equivalent independence polynomials. We extend previous work by showing that independence equivalence class of every odd path has size 1, while the class can contain arbitrarily many graphs for even paths. We also prove that the independence equivalence class of every even cycle consists of two graphs when $nge 2$ except the independence equivalence class of $C_6$ which consists of three graphs. The odd case remains open, although, using irreducibility results from algebra, we were able show that for a prime $p geq 5$ and $nge 1$ the independence equivalence class of $C_{p^n}$ consists of only two graphs.
We prove new upper bounds on the multicolour Ramsey numbers of paths and even cycles. It is well known that $(k-1)n+o(n)leq R_k(P_n)leq R_k(C_n)leq kn+o(n)$. The upper bound was recently improved by Sarkozy who showed that $R_k(C_n)leqleft(k-frac{k}{16k^3+1}right)n+o(n)$. Here we show $R_k(C_n) leq (k-frac14)n +o(n)$, obtaining the first improvement to the coefficient of the linear term by an absolute constant.
We prove a lower bound on the length of the longest $j$-tight cycle in a $k$-uniform binomial random hypergraph for any $2 le j le k-1$. We first prove the existence of a $j$-tight path of the required length. The standard sprinkling argument is not enough to show that this path can be closed to a $j$-tight cycle -- we therefore show that the path has many extensions, which is sufficient to allow the sprinkling to close the cycle.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
