2023 CMS Winter Meeting

Montreal, Dec 1 - 4, 2023

Submission Form Plenary, Prize and Public Lectures By session By speaker Posters

Algebraic Graph Theory for Walking on Graphs
Org: Sooyeong Kim (York University), Hermie Monterde (University of Manitoba), Christopher Van Bommel (Guelph University), Harmony Zhan (Worcester Polytechnic Institute) and Xiaohong Zhang (Université de Montréal)
[PDF]

DAVID FEDER, University of Calgary Two-step perfect quantum state transfer on graphs [PDF]

The criteria for the perfect state transfer (PST) of a quantum state between two vertices of a graph via a continuous-time quantum walk (QW) are now well-established; as these are quite restrictive, only a relatively small number of examples have been found to date. I will discuss an extension of the procedure that allows for perfect transfer between otherwise forbidden vertices, where the QW proceeds in two steps with different choices of edge weights and evolution times for each step. In all cases considered, there exists a specific choice of parameters where edge weights for the second step can be related to those in the first step via switching to a signed graph, equivalent to a unitary transformation on the graph adjacency matrix comprised only of diagonal elements $\pm 1$. Extending the two-step PST to multiple initial and final vertices permits the perfect preparation of maximal eigenstates of the adjacency matrices of induced subgraphs via quantum walk.

CHRIS GODSIL, University of Waterloo Coefficient Matrices [PDF]

If we are working with characteristic polynomials of graphs and $X$ is a graph on $n$ vertices, its \textsl{coefficient matrix} if the $n\times n$ matrix whose $i$-th row is the vector of coefficients of the characteristic polynomial $\phi(x\setminus i,t)$ of the $i$-th vertex-deleted subgraph of $X$.

There is an analog based on matching polynomials. Let $p(X,k)$ denote the number of matchings of $X$. The \textsl{matching polynomial} of $X$ is \[ \mu(X,t) = \sum_{k\ge0} (-1)^{n-2k} p(X,k) t^{n-2k}. \] Matching polynomials share many of the properties of characteristic polynomials---for example their zeros are real, and the matching polynomial of a forest is equal to its characteristic polynomial. In the context of matching polynomials, the \textsl{coefficient matrix} has the coefficients of the polynomials $\mu(X\setminus i,t)$ as its rows.

My talk will introduce these matrices. I will present an application of the characteristic coefficient matrix to a graph invariant arising from continuous quantum walks, and an application of the matching coefficient matrix to the construction of pairs of non-isomorphic graphs with the same matching polynomial.

MARK KEMPTON, Brigham Young University Non-backtracking random walks: mixing rate, Kemeny's constant, and related parameters [PDF]

We will discuss non-backtracking random walks on graphs and spectral properties of matrices associated with them. We will see how many parameters and ideas coming from the theory of random walks on graphs can be modified by a non-backtracking random walk. We will compare these non-backtracking parameters with the usual simple random walk analogues.

SOOYEONG KIM, York University Kemeny's constant and enumerating Braess edges in trees [PDF]

We study the problem of enumerating Braess edges for Kemeny's constant in trees. We obtain bounds and asympotic results for the number of Braess edges in some families of trees.

PAULA KIMMERLING, Washington State University Continuous-Time Quantum Walks on Windmill Graphs [PDF]

Let $A$ be the adjacency matrix of a graph. We will associate this graph with a continuous-time quantum walk by using a transition matrix $U(t) = e^{itA}$. This allows us to create another matrix $\hat{M}$ which is time-independent. $\hat{M}$ gives us some measure of average probability values of a continuous time quantum walk and is called the average mixing matrix. This has been studied extensively on trees and other graphs with distinct eigenvalues.

Our work focuses on graphs which have repeated eigenvalues. In addition to studying the rank and long-term behavior of Dutch Windmill graphs, we extended that same study to French Windmill graphs and Kulli Cycle Windmills. We will compare the behavior of the Windmill graphs to see which ones allow greater transfer of quantum information.

ADAM KNUDSON, Brigham Young University A Nordhauss-Gaddum type problem for the normalized Laplacian spectrum and graph Cheeger constant [PDF]

For a graph $G$ on $n$ vertices with normalized Laplacian eigenvalues $0=\lambda_1(G) \leq \lambda_2(G) \leq\cdots\leq \lambda_n(G)$ and graph complement $G^c$, we prove that \begin{equation*} \max\{\lambda_2(G),\lambda_2(G^c)\}\geq \frac{2}{n^2}. \end{equation*} We do this by way of lower bounding $\max\{i(G), i(G^c)\}$ and $\max\{h(G), h(G^c)\}$ where $i(G)$ and $h(G)$ and denote the isoperimetric number and Cheeger constant of $G$, respectively.

GABOR LIPPNER, Northeastern University Instability of transfer strength [PDF]

We study the maximum achievable state transfer strength in a scenario where magnetic fields are applied to 3 nodes: the source and the target, as well as a third one. It turns out, this setup behaves in a more subtle way than the case when only the source and the target node receive magnetic fields (that will be described in some detail in Yujia Shi's talk). In particular, we are able to exhibit an instability phenomenon that is absent in the original case: changing the graph structure arbitrarily far from the source and target can lead to a significant increase in the maximum transfer strength.

NEAL MADRAS, York University Must random walk move rapidly on either a graph or its complement? [PDF]

One way to measure how rapidly a random walk moves around a graph $G$ is by the Kemeny constant of the graph. Roughly speaking, if $G$ has $n$ vertices and its Kemeny constant is $O(n)$, then a random walk is not slow to visit a randomly chosen target vertex.

I shall outline a proof that for every $\epsilon>0$, there is a constant $\Psi$ with the following property: If $G$ has $n$ vertices, and every vertex has degree between $\epsilon n$ and $(1-\epsilon)n$, then either $G$ or its complement has its Kemeny constant less than $\Psi n$. The methods are mainly probabilistic, with the spectral gap playing a key role. Some stronger results and open questions will also be described.

This is based on joint work with Sooyeong Kim, Ada Chan, Mark Kempton, Steve Kirkland, and Adam Knudson.

YUJIA SHI, Northeastern University Quantifying Transfer Strength on Graphs with Finite Cospectrality [PDF]

Exploring quantum state transfer dynamics on graphs with finite cospectrality, we expand upon Lin, Yau, and Lippner's work: when vertex cospectrality exceeds distance, quantum state transfer is certain with increasing energy potential. This talk will examine cospectrality versus distance in various scenarios, offering strategies to ensure reliable transfer fidelity within specified potential limits. Additionally, a brief discussion addresses the critical aspect of readout time, providing insights for optimizing quantum information transfer efficiency.

MARIIA SOBCHUK, University of Waterloo Quantum isomorphisms [PDF]

You will learn about recent progress in the area of quantum isomorphisms (as the title unambiguously suggests).

AYSA TAJERI, York University Pretty good state transfer on cycles [PDF]

H. Pal and B. Bhattacharjya have proved, using the adjacency matrix, that the continuous-time quantum walk of a cycle $C_n$ admits pretty good state transfer if and only if $n=2^k$ . \newline The exponential distance matrix of a graph is defined entry-wise by letting the $(u,v)$-entry be $q^{dist(u,v)}$ for some parameter $q$. Using exponential distance matrix as the Hamiltonian of the walk, we show that all the even cycles admit pretty good state transfer.

CHRISTINO TAMON, Clarkson University Do quantum walks obey speed limits? [PDF]

Are there speed limits for state transfer in continuous-time quantum walks? We focus on weighted paths as explicit bounds are known for perfect state transfer (due to Yung and Kay). A simple generalization to fractional revival is described. Then, we briefly discuss violations of these speed limits (within the legal bounds of quantum physics). Along the way, we mention a few other related observations (paradoxical or otherwise) and conclude with some open questions. This talk is based on work done with Alastair Kay and Weichen Xie.

CHRISTOPHER VAN BOMMEL, University of Guelph Fidelities and Readout Times of Quantum State Transfer [PDF]

Continuous-time quantum walks on graphs are a model for the propagation of quantum states in a quantum system. Of particular interest is the measure of the fidelity of transmission, the probability of success of transmitting a quantum state between a source site and a destination site in a given time interval. A fidelity of 1 is the well-known property of perfect state transfer and achieving fidelities arbitrarily close to 1 is the well-known property of pretty good state transfer. In general, time intervals for pretty good state transfer are not explicitly determined. We discuss recent developments regarding classes of graphs for which explicit fidelities of state transfer approaching 1, as well as the required time intervals, can be determined. Joint work with Steve Kirkland.

LUC VINET, IVADO/CRM, Université de Montréal $m$-distance regular graphs and multivariate $P$-polynomial association schemes [PDF]

The notion of $m$-distance regular graphs is introduced and related to multivariate $P$-polynomial schemes.

Work done in collaboration with Pierre-Antoine Bernard, Nicolas Crampé, Meri Zaimi and Xiahong Zhang.

HARMONY ZHAN, Worcester Polytechnic Institute $\epsilon$-uniform mixing in discrete quantum walks [PDF]

If a discrete quantum walk starts with a superposition of outgoing arcs of some vertex, can it get arbitrarily close to a state whose amplitudes have the same absolute value over all the arcs? We investigate this phenomenon in arc-reversal Grover walks on distance regular graphs. In particular, if this happens on a non-bipartite distance regular graph, and the target state respects the neighborhoods, then the Bose-Mesner algebra contains a real Hadamard matrix. This gives rise to 4 infinite families of strongly regular graphs that admit $\epsilon$-uniform mixing.

XIAOHONG ZHANG, Université de Montréal Local uniform mixing [PDF]

Let $X$ be a graph with adjacency matrix $A$, then the transition matrix for the continuous time quantum walk on $X$ at time $t$ is given by \[ U(t) = \exp(itA). \] If for some time $t$, the $j$-th column of $U(t)$ is flat (all the entries of the column have the same modulus), then we say $X$ admits local uniform mixing with respect to vertex $j$ at time $t$. We construct an infinite family of graphs that admits local uniform mixing. They also serve as examples where local uniform mixing at vertex $u$ does not necessarily occur at a rational multiple of the period if $X$ is also periodic at vertex $u$. We also present some graphs that admit local uniform mixing with respect to several vertices at the same time, but those vertices are not in the same orbit.

This is joint work with Chris Godsil.

top of page