×

zbMATH — the first resource for mathematics

A correspondence measure for graph matching using the discrete quantum walk. (English) Zbl 1182.68146
Escolano, Francisco (ed.) et al., Graph-based representations in pattern recognition. 6th IAPR-TC-15 international workshop, GbRPR 2007, Alicante, Spain, June 11–13, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-72902-0/pbk). Lecture Notes in Computer Science 4538, 81-91 (2007).
Summary: In this paper we consider how coined 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 coined 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 have tested the algorithm on graphs derived from the NCI molecule database and found it to significantly reduce the space of possible matchings 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.
For the entire collection see [Zbl 1165.68009].

MSC:
68R10 Graph theory (including graph drawing) in computer science
68Q12 Quantum algorithms and complexity in the theory of computing
68T10 Pattern recognition, speech recognition
92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
Software:
COIL-100
PDF BibTeX XML Cite
Full Text: DOI