2019 CMS Winter Meeting

Toronto, December 6 - 9, 2019

Quantum Information on Graphs
Org: Ada Chan (York), Christino Tamon (Clarkson) and Hanmeng Zhan (Montréal)
[PDF]

QIUTING (TINA) CHEN, University of Waterloo
Pair State Transfer  [PDF]

So far the most studied quantum walks are the ones whose Hamiltonians are the adjacency matrices of the underlying graphs and initial states are vertex states $e_a$. This talk focuses on Laplacian pair state transfer, that is, the quantum walks whose initial states are pair states $e_a-e_b$ and Hamiltonians are the Laplacians of the underlying graphs.

We extend some known results of vertex state transfer to Laplacian pair state transfer and introduce some basic properties of Laplacian pair state transfer. We will introduce two useful closure properties for perfect Laplacian pair state transfer. One is that complementation preserves perfect pair state transfer. The other is that if $G$ has vertex state transfer and $H$ has pair state transfer, then with some mild assumption on the pairs of vertex states and pair states that have perfect state transfer, the Cartesian product $G\square H$ also admits perfect pair state transfer. We will talk about one interesting transitivity phenomenon that happens in Laplacian pair state transfer which never happens in vertex state transfer.

WHITNEY DRAZEN, Northeastern University
Fractional Cospectrality  [PDF]

A necessary condition for perfect state transfer between two vertices $u$ and $v$ in a graph with adjacency matrix $A$ is the cospectrality of these vertices. We can characterize cospectrality in terms of the eigenvectors of $A$ at the $u$ and $v$ coordinates. In this talk we consider fractional revival, a more general phenomenon than perfect state transfer. We find an analogous necessary condition on the eigenvectors of $A$ for fractional revival that we call fractional cospectrality. We give several equivalent formulations of this notion and present examples of families of graphs with fractionally cospectral pairs. Additionally, we will discuss when we can glue graphs at their fractionally cospectral pairs and maintain fractional cospectrality.

CHRIS GODSIL
Average states of quantum walks  [PDF]

A state of a finite dimensional quantum system can be specified by a \textsl{density matrix}, a positive semidefinite matrix with trace $1$. The evolution of the system (in the simplest case) is determined by unitary matrices $U(t) := \exp(itA),\qquad (t\ge 0).$ Here $A$ is called the \textsl{Hamiltonian} of the system and must be Hermitian. If the initial state of the system is $D$, then its state at time $t$ will be $U(t)DU(-t)$, which we denote by $D(t)$. For us, the Hamiltonian will be the adjacency matrix of a graph, in which case our quantum system is a \textsl{continuous quantum walk}. Continuous quantum walks are sometimes said to be analogs of classical continuous random walks, but the analogy is weak. In particular although classical random walks converge to a steady state under mild conditions, quantum walks do not.

However we can define the average state of a quantum walk with initial state $D$ to be $\hat{D} := \lim_{T\to\infty} \frac1T \int_0^T D(t)\, dt$ My talk will discuss some of the properties of these average states, and some of their uses.

KRYSTAL GUO, Université de Montréal
Traces of average mixing matrices  [PDF]

A quantum walk is governed by its transition matrix which is unitary; since this process is necessarily non-ergodic and one cannot speak of a stationary distribution, we study the average behaviour of the quantum walk. The average of the mixing matrices contains relevant information about the quantum walk and about the graph. There has been a considerable amount of success in approaching questions about continuous-time quantum walks with tools in linear algebra and algebraic graph theory and we will discuss several recent works in this area, based on joint work with Chris Godsil and Mariia Sobchuk.

REBEKAH HERRMAN, The University of Memphis
Continuous-time quantum walks on dynamic graphs  [PDF]

Continuous-time quantum walks (CTQWs) on static graphs provide efficient methods for search and sampling as well as a model for universal quantum computation. In this talk, we consider an extension of CTQWs to the case of dynamic graphs, in which an ordered sequence of graphs governs free evolution of the quantum walk. We then consider how perfect state transfer during the quantum walk can be used to design dynamic graphs that implement a universal set of quantum logic gates. Additionally, we give explicit examples for a complete logical basis, and we validate implementations using numerical simulations for quantum teleportation and addition circuits. Finally, we discuss how these ideas could be implemented in near-term technologies, such as photonic quantum processors.

MARK KEMPTON, Brigham Young University
Pretty Good Quantum Fractional Revival in Paths  [PDF]

Tools and techniques from algebraic graph theory have found important application in quantum information theory regarding the problem of transferring a quantum state through a network. A graph with adjacency matrix $A$ is said to exhibit perfect state transfer from vertex $u$ to $v$ if $|exp(itA)(u,v)|=1$ for some time $t$. A generalization of perfect state transfer called fractional revival occurs between a pair of nodes when any state initially (at $t=0$) concentrated on those two nodes ends up concentrated on those two nodes at some time $t>0$. Thus perfect state transfer is a special case of fractional revival. We will discuss when fractional revival happens approximately--so-called pretty good fractional revival. We will characterize when pretty good fractional revival can occur in a path graph.

SABRINA LATO, University of Waterloo
Quantum Walks on Oriented Graphs  [PDF]

A quantum walk on a graph is defined based on a Hermitian matrix associated with the graph, such as the adjacency matrix. Although directed graphs do not have symmetric adjacency matrices, oriented graphs, where every edge has a unique direction, have Hermitian but non-symmetric matrix associated to them. This gives rise to a different kind of quantum walk. In this talk, we discuss some properties of these quantum walks, focusing particularly on the similarities and differences between them and their better-studied counterparts on undirected graphs.

CHI-KWONG LI, College of William and Mary
Quantum channels, and operator system parameters  [PDF]

Levene, Paulsen, Todorov have extended some well-known graph parameters to operator systems associated with quantum channels. In particular, they introduced the quantum complexity as the dimension of the smallest co-domain Hilbert space a quantum channel requires to realize a given operator system as its non-commutative confusability graph. The quantum complexity and a closely related quantum version of orthogonal rank are upper bounds for the Shannon zero-error capacity of a quantum channel. In this talk, we will present some new upper bounds on the complexity of of quantum channels and other operator system parameters.

\medskip\noindent Co-authors: Yiu-Tung Poon and John Watrous.

NATALIE MULLIN
Uniform Mixing in Association Schemes  [PDF]

Continuous-time quantum walks were introduced by Farhi and Gutmann in 1998 as a quantum analogue of classical random walks. In this talk we investigate mixing properties of continuous-time quantum walks from an algebraic perspective. Using the framework of association schemes, we construct families of graph that admit uniform mixing. In contrast, we show that cycles of prime length greater than three never admit uniform mixing.

SARAH PLOSKER, Brandon University
Quantum Information on Complex Hadamard Diagonalizable Graphs  [PDF]

If the Laplacian matrix associated to a graph is diagonalizable by a Hadamard matrix, we say that the graph is Hadamard diagonalizable. In light of recent work on quantum state transfer with respect to Hadamard diagonalizable graphs, showing a direct relationship to cubelike graphs, we extend the notion of Hadamard diagonalizability to allow for complex Hadamard matrices.

MARIIA SOBCHUK, University of Waterloo
Quantum independence and chromatic numbers  [PDF]

The talk will focus on the relations between the quantum independence number and the quantum chromatic number, and their classical counterparts. We will present our graph theoretic insight into the smallest known graphs where the quantum and classical parameters take different values. We will use this reasoning to generalize these examples.

CHRISTOPHER VAN BOMMEL, University of Toronto Mississauga
Quantum Walks, State Transfer, and Modified Paths  [PDF]

Quantum computing is believed to provide many advantages over traditional computing, particularly considering the speed at which computations can be performed. One of the challenges that needs to be resolved in order to construct a quantum computer is the transmission of information from one part of the computer to another. Quantum walks, the quantum analogues of classical random walks, provide one potential method for resolving this challenge. If a quantum walker starts at a vertex of a graph and after some length of time, has probability 1 of being found at a different vertex, we say there is perfect state transfer between the two vertices. If instead, there is a time for which the probability can be made arbitrarily close to 1, we say there is pretty good state transfer between the vertices. We consider the quantum walk model determined by the XY-Hamiltonian, which can be considered as based on the adjacency matrix of the graph, and discuss state transfer results on paths for single and multiple qubit states, as well as paths with small modifications.

LUC VINET, CRM, Université de Montréal
Entanglement in Free Fermionic Systems  [PDF]

The parallel between time and band limiting and entanglement studies of free Fermionic systems on graphs will be illustrated.

TOM WONG, Creighton University
Searching the Complete Bipartite Graph using Coined and Lackadaisical Quantum Walks  [PDF]

The coined quantum walk is a discretization of the Dirac equation of relativistic quantum mechanics, and it is the basis of many quantum algorithms. We investigate how it searches the complete bipartite graph for one of possibly several marked vertices, which can lie in one or both partite sets. Following this, we add a weighted self-loop to each vertex, which permits the walker to stay put. This is a lackadaisical quantum walk, and since the graph can be irregular, the weights of the self-loops in one partite set can naturally differ from the weights in the other set. When the marked vertices lie in one partite set, this yields a speedup over the loopless, regular coined quantum walk, which is consistent with previous works on other graphs. When the marked vertices lie in both partite sets, however, speedups are surprisingly rare.

This is join work with Mason Rhodes.

HANMENG ZHAN, York University
Discrete quantum walks on Cayley graphs  [PDF]

Quantum walks are tools for designing quantum circuits and algorithms. Among all graphs studied in continuous quantum walks, Cayley graphs have received considerable attention, as the group structures provide convenient formulas for the spectra of the walks. In this talk, I will consider certain types of discrete quantum walks, which can also be studied analytically when the underlying graph is a Cayley graph. Some open problems in this less understood area will be presented.

XIAOHONG ZHANG, University of Waterloo
Laplacian state transfer on weighted paths  [PDF]

Assume that $X$ is a weighted graph with Laplacian matrix $L(X)$. Let $U(t) = e^{itL(X)}$. Then $U(t)$ is a complex symmetric unitary matrix. We say that $X$ admits Laplacian perfect state transfer between vertices $j$ and $k$ at time $t=t_0$ if $|(U(t_0))_{j,k}|^2$, the fidelity of Laplacian state transfer between vertices $j$ and $k$ at time $t_0$, is 1. It is known that the unweighted path on $n$ vertices admits Laplacian PST only for $n=2$. In this talk we will see that no weighted path on $n\geq 3$ vertices admits Laplacian perfect state transfer between its end vertices.