Discrete Quantum Walks and Graph Invariants

Chris Godsil
University of Waterloo, Canada

  • In probability theory a discrete random walk is often defined by the powers of a stochastic matrix, a non-negative matrix with each row summing to 1. In quantum computing a discrete walk is specified by the powers of a unitary matrix. One difficulty is that to be useful, the unitary matrix must satisfy some structural conditions, and in practice this often means that the walk is based on a graph. I will discuss some of the ways interesting walks can be built from graphs. Of course, if a walk is based on a graph, then we might hope for interactions between properties of the graph and properties of the walk. I will discuss this too.

Comparing numbers of walks among graphs

Dragan Stevanovic
Serbian Academy of Sciences and Arts,  Serbia

  • It is well known that the information on numbers of walks is contained in the powers of graph’s adjacency matrix. An ability to compare numbers of walks of arbitrary length between two graphs then implies inequalities between spectral radii and Estrada indices of those graphs. Comparisons of numbers of walks are usually obtained through injective embeddings of the set of walks of one graph into the set of walks of another graph, although some shortcuts are allowed from time to time. In the lecture we will review comparison methods appearing in literature, and specifically those used in recent results such as the proof of Belardo-Li Marzi-Simi\’c conjectured extension of the Li-Feng lemma, Andriantiana and Wagner’s result on greedy tree with given degree sequence, and ordering of starlike trees by the numbers of walks.

Iterative Linear Solvers for Oil Reservoir Simulation

José Roberto P. Rodrigues
Petrobras/Cenpes, Brazil

  • Reservoir simulation is a crucial component of almost every decision in the oil production industry. At the core of these reservoir simulators is the solution of very large systems of linear equations, which is typically the step requiring the highest amount of computer resources. After briefly reviewing the techniques used to model petroleum production and how they lead to the need of solving such large linear systems, this talk will discuss the iterative methods most commonly employed, highlighting specific features which are required by some peculiar aspects of those systems. The impact of modern computer architecture on the design of the linear solvers will be emphasized. Key aspects taken into account in a dedicated solver for petroleum applications currently under development will be shown, as well as results obtained with matrices from real simulations, focusing on performance and scalability.

New spectral coordinates

Carlos Tomei
PUC-RJ, Brazil

  • Inverse problems and integrable systems are practical and theoretical contexts in which appropriate coordinates make a difference. We present such an example which has been very fruitful in both situations: for the understanding of familiar eigenvalue algorithms of the QR family and in the theory of isospectral flows, in which the symplectic structure is essentially bypassed.  These coordinates take into account matrix profiles, extending substantially the better understood case of tridiagonal matrices.

    Joint work with N. Saldanha (PUC-Rio), D. Torres(PUC-Rio) and R. Leite (UFES).



Acima ↑