By the same authors

From the same journal

From the same journal

Graph matching using the interference of discrete-time quantum walks

Research output: Contribution to journalArticlepeer-review

Published copy (DOI)



Publication details

JournalImage and Vision Computing
DatePublished - 4 Jun 2009
Issue number7
Number of pages16
Pages (from-to)934-949
Original languageEnglish


In this paper, we consider how discrete-time quantum walks can be applied to graph-matching problems. The matching problem is abstracted using an auxiliary graph that connects pairs of vertices from the graphs to be matched by way of auxiliary vertices. A discrete-time quantum walk is simulated on this auxiliary graph and the quantum interference on the auxiliary vertices indicates possible matches. When dealing with graphs for which there is no exact match, the interference amplitudes together with edge consistencies are used to define a consistency measure. We also explore the use of the method for inexact graph-matching problems. We have tested the algorithm on graphs derived from the NCI molecule database and found it to significantly reduce the space of possible permutation matchings, typically by a factor of 10(-20)-10(-30), thereby allowing the graphs to be matched directly. An analysis of the quantum walk in the presence of structural errors between graphs is used as the basis of the consistency measure. We test the performance of this measure on graphs derived from images in the COIL-100 database. (C) 2008 Elsevier B.V. All rights reserved.

Bibliographical note

6th International Workshop on Graph-Based Representations in Pattern Recognition, Alicante, SPAIN, JUN 11-13, 2007

    Research areas

  • Graph matching, Discrete time quantum walk, Auxiliary structure, Interference amplitude, Probabilistic model, EDIT DISTANCE, IMAGE SEGMENTATION, ALGORITHM, RELAXATION, SUBGRAPH

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations