Quantum Approaches to Graph Similarity

By Maritza Hernandez, Arman Zaribafiyan, & Mohammad Naghibi

At 1QBit we have developed a method of measuring similarity between graphs with the aid of a quantum annealer. In contrast to conventional methods, our method is capable of identifying the reasons for determining that two arbitrary graphs are similar, and can illustrate how much each component of each graph contributes to the decision. Moreover, the method can be used to mine similar patterns in a group of graphs by solving subset matching problems. To validate our approach we apply our method in a biochemical scenario, classifying the toxicity properties of a library of molecules based on their similarity to labelled molecules. Benchmarking results show that this general-purpose similarity determination method can perform as accurately as the best-known classical solution while providing higher sensitivity or higher specificity, and maintaining the same predictive accuracy.

White paper