Quantum Computation and Information Seminar 

07/04/2006, 16:30 — 17:30 — Room P3.10, Mathematics Building
Simone Severini, U York, UK

Unitarity as a finer sieve in distinguishing combinatorial objects

The problem of distinguishing different combinatorial objects represented by cospectral matrices appears in many diverse mathematical contexts and it has large application in pattern recognition. The problem is related to the traditional question "can we hear the shape of a drum?". In this talk I will give evidence that representing graphs by certain unitary matrices provides a finer sieve in distinguishing nonisomorphic graph which are cospectral with respect to the usual representations, like the adjacency matrix or the laplacian. The matrices considered can be seen as inducing the coherent diffusion of a quantum particle in the graph taken into analysis. Such a quantum evolution depends on the graph. I will show that for certain graphs the quantum evolution helps in distinguishing isomorphism classes. The talk is based on the paper "David Emms, Edwin R. Hancock, Simone Severini and Richard C. Wilson, A Matrix Representation of Graphs and its Spectrum as a Graph Invariant, The Electronic Journal of Combinatorics, 13 (2006), #R34. This is available on the web at the address www.combinatorics.org/Volume_13/PDF/v13i1r34.pdf or www-users.york.ac.uk/~ss54.