Let $G$ be a strongly regular graph of prime order $p$ with connection degree $k \geq 6$. We prove that the \emph{quantum walk characteristic polynomial} $χ_q(G,λ) \coloneqq \det(λI - U_G)$, where $U_G$ is the coined quantum walk operator on $G$, completely determines $G$ up to isomorphism within the class of strongly regular graphs of the same order.
The proof proceeds in three steps. First, we show that $U_G$ block-diagonalizes under the discrete Fourier transform over $\Z_p$, yielding $p$ blocks $U_G^{(j)}$ of size $k \times k$. Second, we prove an explicit formula \[
χ_q\!\bigl(U_G^{(j)}, λ\bigr) =
(λ-1)^{(k-2)/2}(λ+1)^{(k-2)/2}
\!\left(λ^2 - \tfrac{2\widehat{A}_G(j)}{k}\,λ+ 1\right), \] from which the Fourier coefficient $\widehat{A}_G(j)$ is recovered as the unique real part of an eigenvalue of $U_G^{(j)}$ distinct from $\pm 1$. Third, the inverse discrete Fourier transform recovers the connection set $S$ of $G$, and Turner's theorem (1967) identifies $G$ up to isomorphism. As a consequence, graph isomorphism is decidable in polynomial time within this class using the quantum walk spectrum, without resorting to the general quasi-polynomial algorithm of Babai (2016).
Let G be a strongly regular graph of prime order p with connection degree k≥6. We prove that the \emph{quantum walk characteristic polynomial} χq(G,λ):=det(λI−UG), where UG is the coined quantum walk operator on G, completely determines G up to isomorphism within the class of strongly regular graphs of the same order.
The proof proceeds in three steps. First, we show that UG block-diagonalizes under the discrete Fourier transform over Zp, yielding p blocks UG(j) of size k×k. Second, we prove an explicit formula [
χ_q!\bigl(U_G^{(j)}, λ\bigr) =
(λ-1)^{(k-2)/2}(λ+1)^{(k-2)/2}
!\left(λ^2 - \tfrac{2\widehat{A}_G(j)}{k},λ+ 1\right), ] from which the Fourier coefficient AG(j) is recovered as the unique real part of an eigenvalue of UG(j) distinct from ±1. Third, the inverse discrete Fourier transform recovers the connection set S of G, and Turner's theorem (1967) identifies G up to isomorphism. As a consequence, graph isomorphism is decidable in polynomial time within this class using the quantum walk spectrum, without resorting to the general quasi-polynomial algorithm of Babai (2016).
We study perfect state transfer in Grover walks on two important classes of graphs: strongly regular graphs and strongly walk-regular graphs. The latter class is a generalization of the former. We first give a complete classification of strongly regular graphs that admit perfect state transfer. The only such graphs are the complete bipartite graph K2,2 and the complete tripartite graph K2,2,2. We then show that, if a connected strongly walk-regular graph that is not a strongly regular graph admits perfect state transfer, then its spectrum must be of the form {[k]1,[2k]α,[0]β,[−2k]γ}, and we enumerate all feasible spectra of this form up to k=20 with the help of a computer. These results are obtained using techniques from algebraic number theory and spectral graph theory, particularly through the analysis of eigenvalues and eigenprojections of a normalized adjacency matrix. While the setting is in quantum walks, the core discussion is developed entirely within the framework of spectral graph theory.
Quantum random walks have been shown to be powerful quantum algorithms for certain tasks on graphs like database searching, quantum simulations etc. In this work we focus on its applications for the graph isomorphism problem. In particular we look at how we can compare multi-particle quantum walks and well known classical WL tests and how quantum walks can be used to distinguish hard graphs like CFI graphs which k-WL tests cannot distinguish. We provide theoretical proofs and empirical results to show that a k-QW with input superposition states distinguishes k-CFI graphs. In addition we also prove that a k-1 QW with localized input states distinguishes k-CFI graphs. We also prove some additional results about strongly regular graphs (SRGs).
Graph isomorphism is an essential problem in graph theory and widely used in a variety of applications. With graph size increasing, graph isomorphism become difficult for classical computation since there is no polynomial algorithm for general graphs yet. Considering the advantages of quantum computation over classical computation in various tasks, quantum graph isomorphism algorithms have been studied to explore the potentials of quantum computation in graph isomorphism. In this work, we propose a graph isomorphism algorithm based on continuous-time quantum walks, where we construct the graph certificates from the output probabilities of continuous-time quantum walks on the tested graphs with added self-loops to graph vertices, and distinguish graphs by comparing the graph certificates. Numerous tests on diverse graph classes demonstrate the effectiveness of the proposed GI algorithm, which is not limited to a specific topological structure graph. Moreover, we test the proposed algorithm on classes of strongly regular graphs, and the results show that the distinguishing ability of the algorithm can be improved with the increasement of the added self-loops to distinct vertices.
The continuous-time quantum walk on an oriented circulant graph is determined by the Fourier eigenvalues of its Hermitian adjacency matrix. We classify perfect state transfer (PST) between distinct vertices in every nonempty oriented circulant graph. We show that each such graph is described by an odd primitive quadratic Dirichlet character of conductor Δ, a set of gcd-classes, and a choice between the two orientations of each selected class. For a graph of order n, we derive an explicit formula for every Fourier eigenvalue without assuming that n/Δ is coprime to Δ. We prove that PST occurs only for Δ∈{3,4,8} and give necessary and sufficient conditions on the connection set for each conductor. Equivalently, the square-free radicands of oriented circulant graphs with PST are exactly 1, 2, and 3. More generally, when λj=Dηj with ηj∈Z, congruences satisfied by the integers ηj determine all PST pairs and times, the minimum period, and the largest vertex sets supporting multiple state transfer (MST). In this class, pretty good state transfer is equivalent to PST. We also determine the connected orders and enumerate the resulting graphs.
We give a quantum algorithm for a novel type of black-box problem: identifying a hidden d-regular base graph G on n vertices from oracle access to an obfuscated version of it, rather than traversing it. From G we build the spired graph Gspire in three steps: each vertex is lifted into an exponentially large cluster, with adjacent clusters joined by a random bipartite graph; each cluster is then crowned with a balanced spire; finally, all vertices are randomly relabelled. Specializing to G=K2 recovers the welded-trees graph.
Our algorithm is conceptually simple: a continuous-time quantum walk on Gspire, followed by a single Hadamard test at a classically precomputed time t∗; the algorithm returns the candidate whose predicted amplitude is closest to the measurement. The design rests on a rigorous spectral theory: from the apex of any spire, the walk is confined to a polynomial-dimensional invariant subspace evolving under the adjacency matrix of a simpler towered graph Gtower; that matrix block-diagonalizes into n independent tridiagonal systems of size n, each solved in closed form by a Chebyshev secular equation. Efficient numerics enabled by this decomposition supply t∗ and the predicted amplitudes.
On the prism graphs Ym versus the Möbius ladders Mm (each on n=2m vertices), the numerical study supports a precise conjecture that O(n2/logn) measurements at evolution time of order m2 suffice to distinguish the two families; we have tested 4≤m≤5121 (n up to 10242). By analogy with the welded-trees lower bounds, we further conjecture that any classical algorithm requires queries exponential in n. Together these conjectures point to an exponential quantum speedup for the identification of an obfuscated base graph.
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.