By the same authors

From the same journal

From the same journal

Coined quantum walks lift the cospectrality of graphs and trees

Research output: Contribution to journalArticle

Standard

Coined quantum walks lift the cospectrality of graphs and trees. / Emms, David; Severini, Simone; Wilson, Richard C.; Hancock, Edwin R.

In: Pattern recognition, Vol. 42, No. 9, 09.2009, p. 1988-2002.

Research output: Contribution to journalArticle

Harvard

Emms, D, Severini, S, Wilson, RC & Hancock, ER 2009, 'Coined quantum walks lift the cospectrality of graphs and trees', Pattern recognition, vol. 42, no. 9, pp. 1988-2002. https://doi.org/10.1016/j.patcog.2008.10.025

APA

Emms, D., Severini, S., Wilson, R. C., & Hancock, E. R. (2009). Coined quantum walks lift the cospectrality of graphs and trees. Pattern recognition, 42(9), 1988-2002. https://doi.org/10.1016/j.patcog.2008.10.025

Vancouver

Emms D, Severini S, Wilson RC, Hancock ER. Coined quantum walks lift the cospectrality of graphs and trees. Pattern recognition. 2009 Sep;42(9):1988-2002. https://doi.org/10.1016/j.patcog.2008.10.025

Author

Emms, David ; Severini, Simone ; Wilson, Richard C. ; Hancock, Edwin R. / Coined quantum walks lift the cospectrality of graphs and trees. In: Pattern recognition. 2009 ; Vol. 42, No. 9. pp. 1988-2002.

Bibtex - Download

@article{7eae9ded86c446f88dddd7167e8b2142,
title = "Coined quantum walks lift the cospectrality of graphs and trees",
abstract = "In this paper we explore how a spectral technique suggested by coined quantum walks can be used to distinguish between graphs that are cospectral with respect to standard matrix representations. The algorithm runs in polynomial time and, moreover, can distinguish many graphs for which there is no subexponential time algorithm that is proven to be able to distinguish between them. In the paper, we give a description of the coined quantum walk from the field of quantum computing. The evolution of the walk is governed by a unitary matrix. We show how the spectrum of this matrix is related to the spectrum of the transition matrix of the classical random walk. However, despite this relationship the behaviour of the quantum walk is vastly different from the classical walk. This leads us to define a new matrix based on the amplitudes of paths of the walk whose spectrum we use to characterise graphs. We carry out three sets of experiments using this matrix representation. Firstly, we test the ability of the spectrum to distinguish between sets of graphs that are cospectral with respect to standard matrix representation. These include strongly regular graphs, and incidence graphs of balanced incomplete block designs (BIBDs). Secondly, we test our method on ALL regular graphs on up to 14 vertices and ALL trees on up to 24 vertices. This demonstrates that the problem of cospectrality is often encountered with conventional algorithms and tests the ability of our method to resolve this problem. Thirdly, we use distances obtained from the spectra of S+(U-3) to cluster graphs derived from real-world image data and these are qualitatively better than those obtained with the spectra of the adjacency matrix. Thus, we provide a spectral representation of graphs that can be used in place of standard spectral representations, far less prone to the problems of cospectrality. (C) 2008 Elsevier Ltd. All rights reserved.",
keywords = "Graph spectra, Quantum walks, Unitary representations, Strongly regular graphs, Graph matching, Cospectrality, COMPUTER, DESIGNS",
author = "David Emms and Simone Severini and Wilson, {Richard C.} and Hancock, {Edwin R.}",
year = "2009",
month = sep,
doi = "10.1016/j.patcog.2008.10.025",
language = "English",
volume = "42",
pages = "1988--2002",
journal = " Pattern Recognition",
issn = "0031-3203",
publisher = "Elsevier Limited",
number = "9",

}

RIS (suitable for import to EndNote) - Download

TY - JOUR

T1 - Coined quantum walks lift the cospectrality of graphs and trees

AU - Emms, David

AU - Severini, Simone

AU - Wilson, Richard C.

AU - Hancock, Edwin R.

PY - 2009/9

Y1 - 2009/9

N2 - In this paper we explore how a spectral technique suggested by coined quantum walks can be used to distinguish between graphs that are cospectral with respect to standard matrix representations. The algorithm runs in polynomial time and, moreover, can distinguish many graphs for which there is no subexponential time algorithm that is proven to be able to distinguish between them. In the paper, we give a description of the coined quantum walk from the field of quantum computing. The evolution of the walk is governed by a unitary matrix. We show how the spectrum of this matrix is related to the spectrum of the transition matrix of the classical random walk. However, despite this relationship the behaviour of the quantum walk is vastly different from the classical walk. This leads us to define a new matrix based on the amplitudes of paths of the walk whose spectrum we use to characterise graphs. We carry out three sets of experiments using this matrix representation. Firstly, we test the ability of the spectrum to distinguish between sets of graphs that are cospectral with respect to standard matrix representation. These include strongly regular graphs, and incidence graphs of balanced incomplete block designs (BIBDs). Secondly, we test our method on ALL regular graphs on up to 14 vertices and ALL trees on up to 24 vertices. This demonstrates that the problem of cospectrality is often encountered with conventional algorithms and tests the ability of our method to resolve this problem. Thirdly, we use distances obtained from the spectra of S+(U-3) to cluster graphs derived from real-world image data and these are qualitatively better than those obtained with the spectra of the adjacency matrix. Thus, we provide a spectral representation of graphs that can be used in place of standard spectral representations, far less prone to the problems of cospectrality. (C) 2008 Elsevier Ltd. All rights reserved.

AB - In this paper we explore how a spectral technique suggested by coined quantum walks can be used to distinguish between graphs that are cospectral with respect to standard matrix representations. The algorithm runs in polynomial time and, moreover, can distinguish many graphs for which there is no subexponential time algorithm that is proven to be able to distinguish between them. In the paper, we give a description of the coined quantum walk from the field of quantum computing. The evolution of the walk is governed by a unitary matrix. We show how the spectrum of this matrix is related to the spectrum of the transition matrix of the classical random walk. However, despite this relationship the behaviour of the quantum walk is vastly different from the classical walk. This leads us to define a new matrix based on the amplitudes of paths of the walk whose spectrum we use to characterise graphs. We carry out three sets of experiments using this matrix representation. Firstly, we test the ability of the spectrum to distinguish between sets of graphs that are cospectral with respect to standard matrix representation. These include strongly regular graphs, and incidence graphs of balanced incomplete block designs (BIBDs). Secondly, we test our method on ALL regular graphs on up to 14 vertices and ALL trees on up to 24 vertices. This demonstrates that the problem of cospectrality is often encountered with conventional algorithms and tests the ability of our method to resolve this problem. Thirdly, we use distances obtained from the spectra of S+(U-3) to cluster graphs derived from real-world image data and these are qualitatively better than those obtained with the spectra of the adjacency matrix. Thus, we provide a spectral representation of graphs that can be used in place of standard spectral representations, far less prone to the problems of cospectrality. (C) 2008 Elsevier Ltd. All rights reserved.

KW - Graph spectra

KW - Quantum walks

KW - Unitary representations

KW - Strongly regular graphs

KW - Graph matching

KW - Cospectrality

KW - COMPUTER

KW - DESIGNS

UR - http://www.scopus.com/inward/record.url?scp=67349095041&partnerID=8YFLogxK

U2 - 10.1016/j.patcog.2008.10.025

DO - 10.1016/j.patcog.2008.10.025

M3 - Article

VL - 42

SP - 1988

EP - 2002

JO - Pattern Recognition

JF - Pattern Recognition

SN - 0031-3203

IS - 9

ER -