Graph matching using the interference of discrete-time quantum walks

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.